Algorithmique et programmation

Un algorithme est une suite finie et non ambiguë d'instructions ou d'opérations permettant de résoudre un problème ou d'obtenir un résultat donné. Imaginez que c'est une recette de cuisine très détaillée pour un ordinateur.

Key Concepts:

• Définition d'un algorithme : C'est une méthode pas-à-pas pour accomplir une tâche.
• Caractéristiques d'un algorithme :
  • Fini : Il doit se terminer après un nombre limité d'étapes. Pas de boucles infinies !
  • Déterministe : Pour les mêmes entrées, il doit toujours produire les mêmes sorties.
  • Clair et non ambigu : Chaque instruction doit être parfaitement compréhensible.
  • Effectif : Chaque étape doit pouvoir être réalisée.
  • Général : Il doit pouvoir s'appliquer à une gamme de problèmes similaires, pas un seul cas spécifique.
• Exemples d'algorithmes simples :
  • Recette de cuisine : Une suite d'étapes (mélanger, cuire, etc.) pour préparer un plat. Les ingrédients sont les entrées, le plat est la sortie.
  • Itinéraire : Une série de directions (tourner à gauche, prendre la sortie, etc.) pour aller d'un point A à un point B. Le point de départ et d'arrivée sont les entrées.

En programmation, une variable est comme une boîte nommée dans laquelle on peut stocker des informations. Le type de ces informations est très important.

Key Concepts:

• Déclaration et affectation de variables : En Python, on ne "déclare" pas explicitement le type d'une variable. On l'affecte directement.

  age = 20           # Affecte la valeur 20 à la variable 'age'
  nom = "Alice"      # Affecte la chaîne de caractères "Alice" à 'nom'
  prix_unitaire = 15.50 # Affecte un nombre décimal à 'prix_unitaire'
  

  L'opérateur = est l'opérateur d'affectation.
• Types de données fondamentaux :
  • Entier (int) : Nombres entiers, positifs ou négatifs (ex: 5, -10, 0).
  • Flottant (float) : Nombres décimaux (ex: 3.14, -0.5, 100.0). Attention, on utilise le point . comme séparateur décimal.
  • Chaîne de caractères (str) : Texte, délimité par des guillemets simples '' ou doubles "" (ex: "Bonjour", 'Python').
  • Booléen (bool) : Représente une valeur de vérité, soit True (vrai), soit False (faux). Très utile pour les conditions.
• Opérations de base sur les variables : On peut effectuer des opérations selon le type de la variable.

  a = 10
  b = 5
  somme = a + b    # somme sera 15 (int)
  produit = a * b  # produit sera 50 (int)
  
  texte1 = "Bonjour"
  texte2 = " monde"
  salutation = texte1 + texte2 # salutation sera "Bonjour monde" (str)
  
  est_majeur = True
  print(est_majeur) # Affiche True
  

  Le type d'une variable détermine les opérations qu'on peut lui appliquer.

Les opérateurs sont des symboles qui réalisent des opérations sur des valeurs (appelées opérandes). Une combinaison d'opérandes et d'opérateurs forme une expression.

Key Concepts:

• Opérateurs arithmétiques : Pour les calculs numériques.
  • + : Addition (ex: 5 + 2 donne 7)
  • - : Soustraction (ex: 5 - 2 donne 3)
  • * : Multiplication (ex: 5 * 2 donne 10)
  • / : Division (ex: 5 / 2 donne 2.5 - toujours un float)
  • // : Division entière (quotient) (ex: 5 // 2 donne 2)
  • % : Modulo (reste de la division entière) (ex: 5 % 2 donne 1)
  • ** : Puissance (ex: 5 ** 2 donne 25)
• Opérateurs de comparaison : Comparent deux valeurs et renvoient un booléen (True ou False).
  • <mark> : Égal à (ex: 5 </mark> 5 donne True, 5 == 2 donne False)
  • != : Différent de (ex: 5 != 2 donne True)
  • < : Inférieur à (ex: 5 < 2 donne False)
  • > : Supérieur à (ex: 5 > 2 donne True)
  • <= : Inférieur ou égal à (ex: 5 <= 5 donne True)
  • >= : Supérieur ou égal à (ex: 5 >= 2 donne True)
• Opérateurs logiques : Permettent de combiner des expressions booléennes.
  • and : ET logique. Renvoie True si les deux opérandes sont True. (ex: (5 > 2) and (3 < 1) donne False)
  • or : OU logique. Renvoie True si au moins un des opérandes est True. (ex: (5 > 2) or (3 < 1) donne True)
  • not : NON logique. Inverse la valeur de vérité de l'opérande. (ex: not (5 > 2) donne False) La compréhension des opérateurs est cruciale pour écrire des conditions et des boucles.

Pour interagir avec l'utilisateur, un programme a besoin de prendre des informations (entrées) et d'afficher des résultats (sorties).

Key Concepts:

• Fonction input() pour la saisie utilisateur : Cette fonction permet de demander à l'utilisateur de taper quelque chose au clavier.

  nom_utilisateur = input("Entrez votre nom : ")
  print("Bonjour", nom_utilisateur)
  

  Attention : input() renvoie toujours une chaîne de caractères (str). Si vous attendez un nombre, il faudra le convertir :

  age_str = input("Quel est votre âge ? ")
  age_int = int(age_str) # Convertit la chaîne en entier
  print("Vous avez", age_int, "ans.")
  

  On peut aussi combiner int() et input(): age = int(input("Quel est votre âge ? "))
• Fonction print() pour l'affichage : La fonction print() affiche des informations à l'écran. Elle peut prendre plusieurs arguments séparés par des virgules.

  print("Ceci est un message.")
  nombre = 42
  print("Le nombre est :", nombre)
  

  Par défaut, print() ajoute un espace entre chaque argument et passe à la ligne à la fin.
• Formatage de l'affichage : Pour un affichage plus contrôlé, on peut utiliser les f-strings (chaînes formatées) en Python 3.6+.

  ville = "Paris"
  temperature = 25.3
  print(f"Il fait {temperature}°C à {ville}.")
  # Produit : Il fait 25.3°C à Paris.
  

  Cela permet d'insérer des variables directement dans une chaîne de caractères en utilisant des accolades {}.

Le if est la structure de base pour exécuter du code seulement si une condition est vraie.

Key Concepts:

• Syntaxe de base du if :

  if condition:
      # Bloc de code exécuté si la condition est vraie
      instruction1
      instruction2
  

  La condition est une expression booléenne (qui renvoie True ou False). Le deux-points : est obligatoire après la condition.
• Conditions simples et composées :
  • Simple : Une seule expression booléenne.

    age = 18
    if age >= 18:
        print("Vous êtes majeur.")
    

  • Composée : Utilise les opérateurs logiques and, or, not pour combiner plusieurs conditions.

    temperature = 25
    pluie = False
    if temperature > 20 and not pluie:
        print("C'est une belle journée pour sortir !")
    

• Indentation et blocs de code : En Python, l'indentation (les espaces ou tabulations au début de la ligne) est cruciale. Elle définit les blocs de code. Toutes les lignes d'un même bloc doivent avoir la même indentation.

  if True:
      print("Ceci fait partie du bloc 'if'")
      print("Moi aussi !")
  print("Ceci est en dehors du bloc 'if'")
  

  Une indentation incorrecte provoquera une erreur de syntaxe.

Le if...else permet d'exécuter un bloc de code si la condition est vraie, et un autre bloc si elle est fausse.

Key Concepts:

• Utilisation du else :

  if condition:
      # Bloc de code si la condition est vraie
      instruction_si_vrai
  else:
      # Bloc de code si la condition est fausse
      instruction_si_faux
  

• Exécution alternative de blocs de code : Un seul des deux blocs sera exécuté, jamais les deux.

  nombre = 7
  if nombre % 2 == 0:
      print("Le nombre est pair.")
  else:
      print("Le nombre est impair.")
  

• Exemples pratiques :
  • Vérifier si un utilisateur a le droit d'accéder à une ressource (âge, mot de passe).
  • Calculer une taxe différente selon le montant.
  • Afficher un message personnalisé en fonction du sexe de l'utilisateur.

Quand vous avez plus de deux chemins possibles, if...elif...else est la solution. elif est l'abréviation de "else if".

Key Concepts:

• Gestion de multiples conditions :

  if condition1:
      # Bloc 1 si condition1 est vraie
  elif condition2:
      # Bloc 2 si condition1 est fausse ET condition2 est vraie
  elif condition3:
      # Bloc 3 si condition1 et condition2 sont fausses ET condition3 est vraie
  else:
      # Bloc 4 si aucune des conditions précédentes n'est vraie
  

• Ordre d'évaluation des conditions : Les conditions sont évaluées dans l'ordre, de haut en bas. Dès qu'une condition est vraie, le bloc de code correspondant est exécuté et le reste de la structure if...elif...else est ignoré.

  note = 14
  if note >= 16:
      print("Très bien")
  elif note >= 14: # Seulement si note < 16 et note >= 14
      print("Bien")
  elif note >= 10: # Seulement si note < 14 et note >= 10
      print("Passable")
  else:
      print("Insuffisant")
  

  Si l'ordre des elif était inversé, le résultat pourrait être faux (ex: si note = 16, un elif note >= 10 serait vrai en premier).
• Cas d'utilisation courants :
  • Attribution de mentions (Très bien, Bien, Assez bien...)
  • Catégorisation de données (tranche d'âge, niveau de stock)
  • Menus interactifs où l'utilisateur choisit une option. Utilisez elif pour des choix mutuellement exclusifs.

La boucle while exécute un bloc de code tant qu'une condition est vraie.

Key Concepts:

• Syntaxe et fonctionnement du while :

  while condition:
      # Bloc de code à répéter
      instruction1
      instruction2
  

  La condition est évaluée avant chaque itération. Si elle est True, le bloc est exécuté. Si elle est False, la boucle s'arrête.

  compteur = 0
  while compteur < 5:
      print("Le compteur est :", compteur)
      compteur = compteur + 1 # Incrémentation pour que la condition devienne fausse un jour
  print("Fin de la boucle.")
  

• Condition de continuation de la boucle : La condition doit éventuellement devenir fausse pour que la boucle se termine. Cela implique souvent de modifier une variable à l'intérieur de la boucle (comme compteur ci-dessus).
• Risque de boucle infinie et comment l'éviter : Si la condition ne devient jamais fausse, la boucle ne s'arrêtera jamais. C'est une boucle infinie.

  # Exemple de boucle infinie (NE PAS EXÉCUTER SANS PRÉCAUTION)
  # while True:
  #     print("Je tourne en rond !")
  

  Pour l'éviter, assurez-vous toujours qu'une variable utilisée dans la condition est modifiée de manière à la faire évoluer vers un état où la condition sera fausse. Vérifiez toujours que votre boucle while a une condition de sortie claire.

La boucle for est utilisée pour itérer sur une séquence (parcourir ses éléments un par un).

Key Concepts:

• Itération sur une séquence (range, chaînes, listes) : Une séquence est un ensemble ordonné d'éléments.
  • range() : Génère une séquence de nombres.

    for i in range(5): # i prendra les valeurs 0, 1, 2, 3, 4
        print(i)
    

    range(début, fin, pas) : début (inclus), fin (exclus), pas (par défaut 1). Ex: range(1, 10, 2) → 1, 3, 5, 7, 9
  • Chaînes de caractères : Itère sur chaque caractère.

    mot = "Python"
    for lettre in mot:
        print(lettre)
    

  • Listes : Itère sur chaque élément de la liste. (Voir section suivante sur les listes).

    nombres = [10, 20, 30]
    for num in nombres:
        print(num)
    

• Syntaxe et fonctionnement du for :

  for variable_iteration in sequence:
      # Bloc de code à exécuter pour chaque élément de la séquence
  

  À chaque tour de boucle, variable_iteration prend la valeur de l'élément suivant de la sequence.
• Utilisation de la fonction range() : Très fréquente pour répéter un bloc de code un nombre fixe de fois.

  for _ in range(3): # _ est utilisé quand la variable d'itération n'est pas utilisée dans la boucle
      print("Bonjour !") # Affiche "Bonjour !" 3 fois
  

  range() est très utile pour les boucles basées sur un compteur.

Parfois, on a besoin de modifier le comportement normal d'une boucle : la stopper prématurément ou sauter une itération.

Key Concepts:

• Instruction break pour sortir d'une boucle : L'instruction break arrête immédiatement la boucle la plus proche (que ce soit for ou while). Le programme continue juste après la boucle.

  for i in range(10):
      if i == 5:
          print("J'arrête à 5 !")
          break
      print(i)
  # Output: 0, 1, 2, 3, 4, J'arrête à 5 !
  

• Instruction continue pour passer à l'itération suivante : L'instruction continue arrête l'itération actuelle et passe directement à la prochaine itération de la boucle.

  for i in range(5):
      if i == 2:
          print("Je saute le 2")
          continue
      print(i)
  # Output: 0, 1, Je saute le 2, 3, 4
  

• Exemples d'application :
  • break : Rechercher un élément dans une liste ; dès qu'il est trouvé, inutile de continuer la recherche.
  • continue : Traiter des données, mais ignorer celles qui ne respectent pas un certain critère sans arrêter le processus complet. Ces instructions doivent être utilisées avec parcimonie pour ne pas rendre le code difficile à lire et à comprendre.

Key Concepts:

• Utilité des fonctions (réutilisabilité, modularité) :
  • Réutilisabilité : Écrivez un code une seule fois, utilisez-le partout où vous en avez besoin.
  • Modularité : Découpez un gros problème en petits problèmes gérables, chacun résolu par une fonction. Cela rend le programme plus facile à comprendre, à tester et à maintenir.
  • Abstraction : Vous utilisez une fonction sans avoir besoin de connaître tous les détails de son fonctionnement interne.
• Syntaxe de définition (def) :

  def nom_de_la_fonction(parametre1, parametre2):
      # Bloc de code de la fonction
      instruction1
      instruction2
      # ...
  

  Le mot-clé def est suivi du nom de la fonction, de parenthèses (pour les paramètres) et d'un deux-points :. Le corps de la fonction est indenté.
• Appel de fonction : Pour exécuter le code d'une fonction, on l'appelle par son nom, suivi de parenthèses (avec les arguments si nécessaire).

  def saluer(nom):
      print(f"Bonjour, {nom} !")
  
  saluer("Alice") # Appelle la fonction saluer avec "Alice" comme argument
  saluer("Bob")   # Réutilise la même fonction
  

  Les fonctions sont la base de l'organisation d'un programme.

Les fonctions peuvent prendre des informations en entrée (paramètres) et renvoyer un résultat (valeur de retour).

Key Concepts:

• Passage de paramètres (arguments) : Les paramètres sont les variables listées dans la définition de la fonction. Les arguments sont les valeurs que l'on passe à ces paramètres lors de l'appel de la fonction.

  def addition(a, b): # a et b sont des paramètres
      resultat = a + b
      print(f"La somme de {a} et {b} est {resultat}")
  
  addition(5, 3) # 5 et 3 sont des arguments
  

• Valeurs de retour (return) : L'instruction return permet à une fonction de renvoyer une valeur au code qui l'a appelée. Quand return est exécuté, la fonction s'arrête immédiatement.

  def multiplier(x, y):
      produit = x * y
      return produit # La fonction renvoie la valeur de 'produit'
  
  res = multiplier(4, 6) # res prendra la valeur 24
  print(f"Le produit est : {res}")
  
  # On peut aussi utiliser directement la valeur de retour
  print(f"Le double de 7 est : {multiplier(7, 2)}")
  

• Fonctions sans valeur de retour (procédures) : Une fonction qui n'a pas d'instruction return (ou un return sans valeur) renvoie implicitement la valeur spéciale None (qui signifie "rien" en Python). On les appelle parfois procédures.

  def afficher_message():
      print("Ceci est un simple message.")
  
  valeur = afficher_message()
  print(valeur) # Affiche "Ceci est un simple message." puis "None"
  

  Ces fonctions sont utiles pour effectuer des actions (affichage, modification d'éléments) sans produire de résultat direct.

La portée (scope) d'une variable détermine où elle est accessible dans votre programme.

Key Concepts:

• Variables locales et globales :
  • Variable locale : Définie à l'intérieur d'une fonction. Elle n'est accessible qu'à l'intérieur de cette fonction. Elle est créée à l'appel de la fonction et détruite à la fin de son exécution.

    def ma_fonction():
        variable_locale = 10 # Variable locale
        print(variable_locale)
    
    ma_fonction()
    # print(variable_locale) # Ceci provoquerait une erreur, variable_locale n'existe pas ici
    

  • Variable globale : Définie en dehors de toute fonction (au niveau principal du script). Elle est accessible partout dans le programme, y compris à l'intérieur des fonctions.

    variable_globale = 20 # Variable globale
    
    def autre_fonction():
        print(variable_globale) # Accès à la variable globale
    
    autre_fonction()
    print(variable_globale)
    

  Une fonction peut lire une variable globale, mais pour la modifier, il faut utiliser le mot-clé global (ce qui est généralement déconseillé pour la clarté du code).
• Impact sur la lisibilité et la maintenance du code :
  • L'utilisation excessive de variables globales peut rendre le code difficile à suivre et à déboguer, car n'importe quelle fonction peut les modifier.
  • Privilégiez les variables locales et le passage de paramètres/valeurs de retour pour une meilleure modularité et lisibilité. Cela garantit que les fonctions sont indépendantes et ne créent pas d'effets de bord inattendus.
• Bonnes pratiques :
  • Minimiser l'utilisation de variables globales.
  • Passer les données nécessaires aux fonctions via des paramètres.
  • Renvoyer les résultats des fonctions via return.

Key Concepts:

• Définition et création de listes : Une liste est une collection ordonnée et modifiable d'éléments. Les éléments peuvent être de types différents. Elles sont définies par des crochets [] et les éléments sont séparés par des virgules.

  ma_liste = [1, 2, 3, 4, 5]
  noms = ["Alice", "Bob", "Charlie"]
  melange = [10, "Python", True, 3.14]
  liste_vide = []
  

• Accès aux éléments par indice : Chaque élément d'une liste a un indice (ou index) qui commence à 0.

  fruits = ["pomme", "banane", "cerise"]
  print(fruits[0]) # Affiche "pomme"
  print(fruits[1]) # Affiche "banane"
  print(fruits[-1]) # Accès au dernier élément : "cerise"
  

  Accéder à un indice inexistant provoque une erreur IndexError.
• Modification d'éléments : Les listes sont mutables, ce qui signifie que vous pouvez modifier leurs éléments après leur création.

  mes_notes = [12, 15, 10]
  mes_notes[2] = 13 # La troisième note devient 13
  print(mes_notes) # Affiche [12, 15, 13]
  

Python offre de nombreuses méthodes et fonctions pour manipuler les listes.

Key Concepts:

• Ajout et suppression d'éléments :
  • append(element) : Ajoute un élément à la fin de la liste.

    liste_achats = ["pain", "lait"]
    liste_achats.append("œufs")
    print(liste_achats) # ['pain', 'lait', 'œufs']
    

  • insert(indice, element) : Insère un élément à un indice spécifique.

    liste_achats.insert(1, "fromage") # Insère "fromage" à l'indice 1
    print(liste_achats) # ['pain', 'fromage', 'lait', 'œufs']
    

  • remove(element) : Supprime la première occurrence de l'élément spécifié.

    liste_achats.remove("lait")
    print(liste_achats) # ['pain', 'fromage', 'œufs']
    

  • pop(indice) : Supprime et renvoie l'élément à l'indice spécifié (si l'indice est omis, supprime et renvoie le dernier élément).

    dernier_achat = liste_achats.pop() # Supprime et récupère "œufs"
    print(liste_achats) # ['pain', 'fromage']
    print(dernier_achat) # œufs
    

• Parcours de listes (boucles for) : C'est la manière la plus courante de traiter chaque élément d'une liste.

  nombres = [1, 5, 8, 12]
  for n in nombres:
      print(n * 2) # Affiche 2, 10, 16, 24
  

  Pour obtenir l'indice et la valeur, utilisez enumerate():

  for indice, valeur in enumerate(nombres):
      print(f"L'élément à l'indice {indice} est {valeur}")
  

• Fonctions utiles (len, min, max, sum) :
  • len(liste) : Renvoie le nombre d'éléments dans la liste.

    print(len(nombres)) # Affiche 4
    

  • min(liste) : Renvoie le plus petit élément (si les éléments sont comparables).
  • max(liste) : Renvoie le plus grand élément.
  • sum(liste) : Renvoie la somme des éléments (si numériques).

    print(min(nombres)) # Affiche 1
    print(max(nombres)) # Affiche 12
    print(sum(nombres)) # Affiche 26
    

  Les listes sont des outils très puissants pour organiser des données.

Une liste peut contenir d'autres listes. C'est ainsi que l'on représente des structures de données à plusieurs dimensions, comme des tableaux ou des matrices.

Key Concepts:

• Représentation de données tabulaires : Une liste de listes est parfaite pour représenter des données organisées en lignes et colonnes.

  matrice = [
      [1, 2, 3],  # Première ligne
      [4, 5, 6],  # Deuxième ligne
      [7, 8, 9]   # Troisième ligne
  ]
  

• Accès aux éléments dans un tableau 2D : On utilise deux paires de crochets : matrice[indice_ligne][indice_colonne].

  print(matrice[0])     # Affiche la première ligne : [1, 2, 3]
  print(matrice[1][1])  # Affiche l'élément à la ligne 1, colonne 1 (le 5)
  print(matrice[2][0])  # Affiche l'élément à la ligne 2, colonne 0 (le 7)
  

• Parcours de tableaux : Souvent avec des boucles for imbriquées (une pour les lignes, une pour les colonnes).

  for ligne in matrice:
      for element in ligne:
          print(element, end=" ") # Affiche les éléments sur la même ligne
      print() # Passe à la ligne suivante après chaque ligne de la matrice
  # Output:
  # 1 2 3
  # 4 5 6
  # 7 8 9
  

  On peut aussi parcourir par indices :

  for i in range(len(matrice)): # Pour chaque ligne
      for j in range(len(matrice[i])): # Pour chaque colonne de la ligne i
          print(f"[{i},{j}] = {matrice[i][j]}")
  

Trouver un élément dans une collection de données est une tâche courante. Il existe différentes stratégies.

Key Concepts:

• Principe de la recherche séquentielle (ou linéaire) : Consiste à parcourir tous les éléments d'une liste un par un, du début à la fin, jusqu'à ce que l'élément recherché soit trouvé ou que la fin de la liste soit atteinte.

  def recherche_sequentielle(liste, element_a_chercher):
      for i in range(len(liste)):
          if liste[i] == element_a_chercher:
              return i # Renvoie l'indice si trouvé
      return -1 # Renvoie -1 si non trouvé
  
  ma_liste = [10, 5, 8, 12, 3]
  print(recherche_sequentielle(ma_liste, 8))  # Affiche 2
  print(recherche_sequentielle(ma_liste, 99)) # Affiche -1
  

  Simple à implémenter, mais peut être lent pour de grandes listes.
• Principe de la recherche dichotomique (sur liste triée) : Beaucoup plus efficace que la recherche séquentielle, mais exige que la liste soit triée. L'idée est de diviser la liste en deux à chaque étape.
  1. On compare l'élément recherché avec l'élément du milieu de la liste.
  2. Si c'est égal, on a trouvé.
  3. Si l'élément recherché est plus petit, on répète la recherche dans la moitié gauche de la liste.
  4. Si l'élément recherché est plus grand, on répète la recherche dans la moitié droite de la liste.

  def recherche_dichotomique(liste_triee, element_a_chercher):
      bas = 0
      haut = len(liste_triee) - 1
      while bas <= haut:
          milieu = (bas + haut) // 2
          if liste_triee[milieu] == element_a_chercher:
              return milieu
          elif liste_triee[milieu] < element_a_chercher:
              bas = milieu + 1
          else: # liste_triee[milieu] > element_a_chercher
              haut = milieu - 1
      return -1
  
  liste_triee = [3, 5, 8, 10, 12]
  print(recherche_dichotomique(liste_triee, 8))  # Affiche 2
  print(recherche_dichotomique(liste_triee, 4))  # Affiche -1
  

• Comparaison de l'efficacité des deux méthodes :
  • Séquentielle : Au pire, il faut parcourir toute la liste ($N$ comparaisons pour une liste de taille $N$).
  • Dichotomique : Au pire, il faut diviser la liste en deux $log_2(N)$ fois. C'est beaucoup plus rapide pour de grandes listes. Pour une liste de 1 million d'éléments, la recherche séquentielle prendrait en moyenne 500 000 comparaisons, la dichotomique environ 20. La recherche dichotomique est un excellent exemple de l'importance d'avoir des données organisées (triées).

Trier une liste signifie organiser ses éléments selon un certain ordre (croissant, décroissant). C'est une opération fondamentale.

Key Concepts:

• Principe du tri par sélection :
  1. Trouver le plus petit élément de la liste non triée.
  2. L'échanger avec le premier élément de la liste non triée.
  3. Répéter l'opération pour le reste de la liste (en excluant les éléments déjà triés).

  def tri_selection(liste):
      n = len(liste)
      for i in range(n - 1): # On parcourt jusqu'à l'avant-dernier élément
          min_idx = i
          for j in range(i + 1, n): # Recherche du minimum dans le reste de la liste
              if liste[j] < liste[min_idx]:
                  min_idx = j
          # Échanger l'élément trouvé avec l'élément courant
          liste[i], liste[min_idx] = liste[min_idx], liste[i]
      return liste
  
  ma_liste = [64, 25, 12, 22, 11]
  print(tri_selection(ma_liste)) # Affiche [11, 12, 22, 25, 64]
  

• Principe du tri par insertion :
  1. Considérer le premier élément comme déjà trié.
  2. Pour chaque élément suivant, l'insérer à la bonne place dans la partie déjà triée de la liste, en décalant les éléments plus grands.

  def tri_insertion(liste):
      for i in range(1, len(liste)): # Commence à partir du deuxième élément
          cle = liste[i] # L'élément à insérer
          j = i - 1
          # Déplacer les éléments plus grands que 'cle' vers la droite
          while j >= 0 and cle < liste[j]:
              liste[j + 1] = liste[j]
              j -= 1
          liste[j + 1] = cle # Insérer 'cle' à sa bonne position
      return liste
  
  ma_liste = [12, 11, 13, 5, 6]
  print(tri_insertion(ma_liste)) # Affiche [5, 6, 11, 12, 13]
  

• Comprendre l'idée générale sans implémentation complexe : L'important est de saisir la logique derrière ces algorithmes :
  • Tri par sélection : On sélectionne le bon élément et on le place à la bonne position, puis on recommence.
  • Tri par insertion : On construit la liste triée petit à petit, en insérant chaque nouvel élément à sa place. Il existe d'autres algorithmes de tri plus performants (Merge Sort, Quick Sort) mais leur complexité est au-delà du programme de Terminale. L'objectif est de comprendre que différentes stratégies existent et ont des efficacités différentes.

L'algorithmique et la programmation ne sont pas que des concepts abstraits ; elles servent à résoudre des problèmes réels.

Key Concepts:

• Résolution de problèmes mathématiques simples :
  • Calculer la factorielle d'un nombre.
  • Trouver les nombres premiers jusqu'à une certaine limite.
  • Calculer la suite de Fibonacci.
  • Résoudre des équations simples. Exemple : Calcul de la factorielle

  def factorielle(n):
      if n == 0:
          return 1
      else:
          res = 1
          for i in range(1, n + 1):
              res *= i # res = res * i
          return res
  
  print(f"5! = {factorielle(5)}") # Affiche 5! = 120
  

• Simulation de situations :
  • Modéliser le lancer d'un dé ou d'une pièce.
  • Simuler la propagation d'une épidémie simple.
  • Calculer des probabilités par simulation (méthode de Monte-Carlo). Exemple : Simulation de lancers de dés

  import random # Module pour générer des nombres aléatoires
  
  def lancer_de(nombre_faces=6):
      return random.randint(1, nombre_faces)
  
  print(f"J'ai lancé un dé à 6 faces et j'ai obtenu : {lancer_de()}")
  

• Développement d'un petit programme complet : Combiner toutes les notions (variables, conditions, boucles, fonctions, listes) pour créer un programme fonctionnel. Exemple : Un jeu simple de "Devine le nombre"

  import random
  
  def devine_le_nombre():
      nombre_a_deviner = random.randint(1, 100)
      tentatives = 0
      print("Bienvenue au jeu Devine le nombre !")
      print("J'ai choisi un nombre entre 1 et 100. À vous de deviner.")
  
      while True:
          try:
              proposition = int(input("Entrez votre proposition : "))
              tentatives += 1
              if proposition < nombre_a_deviner:
                  print("Trop petit !")
              elif proposition > nombre_a_deviner:
                  print("Trop grand !")
              else:
                  print(f"Bravo ! Vous avez trouvé le nombre {nombre_a_deviner} en {tentatives} tentatives.")
                  break # Sortir de la boucle while
          except ValueError:
              print("Veuillez entrer un nombre valide.")
  
  # Appel du jeu
  # devine_le_nombre()
  

  La clé est de décomposer le problème en étapes plus petites et de construire le programme progressivement.