Algorithmique et programmation avancée

En programmation, les variables sont des conteneurs nommés qui stockent des informations. Chaque variable a un type de données qui détermine la nature des informations qu'elle peut contenir et les opérations que l'on peut effectuer dessus.

Key Concepts:

• Types de données primitifs: Ce sont les types de base. En Python, bien que tout soit un objet, on distingue des types simples comme :
  • int (entiers) : 5, -10
  • float (nombres à virgule flottante) : 3.14, 0.5
  • str (chaînes de caractères) : "bonjour", 'Python'
  • bool (booléens) : True, False (vrai ou faux)
• Déclaration et affectation:
  • La déclaration d'une variable lui donne un nom.
  • L'affectation (ou assignation) lui donne une valeur.
  • En Python, la déclaration et l'affectation se font souvent en même temps : age = 20.
  • On peut réaffecter une nouvelle valeur à une variable : age = 21.
• Portée des variables: La portée d'une variable définit les parties du programme où elle est accessible.
  • Variable locale : définie à l'intérieur d'une fonction, elle n'est accessible que dans cette fonction.
  • Variable globale : définie en dehors de toute fonction, elle est accessible partout dans le programme. Utiliser le mot-clé global pour modifier une variable globale dans une fonction.

# Exemple de portée
variable_globale = "Je suis globale"

def ma_fonction():
    variable_locale = "Je suis locale"
    print(variable_globale) # Accès à la variable globale
    print(variable_locale)

ma_fonction()
# print(variable_locale) # Erreur, variable_locale n'est pas accessible ici
print(variable_globale)

Les listes sont des collections ordonnées et modifiables d'éléments. Elles sont très flexibles et peuvent contenir des éléments de types différents. En Python, elles sont l'équivalent des tableaux dans d'autres langages, mais avec plus de fonctionnalités.

Key Concepts:

• Définition et indexation:
  • Une liste se définit avec des crochets [].
  • ma_liste = [10, "hello", 3.14, True]
  • Les éléments sont accédés par leur indice, qui commence à 0 pour le premier élément.
  • ma_liste[0] donne 10. ma_liste[1] donne "hello".
  • Les indices négatifs permettent d'accéder aux éléments depuis la fin : ma_liste[-1] donne True.
• Opérations courantes (ajout, suppression, accès):
  • Ajout:
    • append(element): ajoute un élément à la fin. ma_liste.append(False)
    • insert(indice, element): insère un élément à un indice spécifique. ma_liste.insert(1, "nouvel élément")
  • Suppression:
    • remove(element): supprime la première occurrence d'un élément. ma_liste.remove(3.14)
    • pop(indice): supprime et retourne l'élément à l'indice donné (par défaut le dernier). dernier_element = ma_liste.pop()
    • del ma_liste[indice]: supprime l'élément à l'indice donné.
  • Accès et modification:
    • Accès par indice : element = ma_liste[2]
    • Modification par indice : ma_liste[0] = 20
  • Tranches (slicing) : Permet d'extraire une sous-liste. ma_liste[début:fin:pas]
    • ma_liste[1:3] : éléments d'indice 1 et 2.
    • ma_liste[:] : copie de la liste.
    • ma_liste[::-1] : inverse la liste.
• Parcours de listes:
  • Avec une boucle for sur les éléments :

    for element in ma_liste:
        print(element)
    

  • Avec une boucle for sur les indices (pour accéder à l'indice et à la valeur) :

    for i in range(len(ma_liste)):
        print(f"L'élément à l'indice {i} est {ma_liste[i]}")
    

  • La compréhension de liste est une manière concise de créer des listes : carres = [x*x for x in range(5)] donne [0, 1, 4, 9, 16].

Ces deux structures sont des collections non ordonnées.

Key Concepts:

• Paires clé-valeur (dictionnaires):
  • Un dictionnaire (dict) est une collection non ordonnée de paires clé:valeur. Chaque clé doit être unique et immuable (nombre, chaîne de caractères, tuple). Les valeurs peuvent être de n'importe quel type.
  • mon_dict = {"nom": "Alice", "age": 30, "ville": "Paris"}
  • Accès aux valeurs: par la clé. mon_dict["nom"] donne "Alice".
  • Ajout/Modification: mon_dict["profession"] = "Développeur"
  • Suppression: del mon_dict["ville"] ou valeur = mon_dict.pop("age")
  • Parcours:

    for cle, valeur in mon_dict.items():
        print(f"{cle}: {valeur}")
    

    for cle in mon_dict.keys(): # Parcours des clés
        print(cle)
    

    for valeur in mon_dict.values(): # Parcours des valeurs
        print(valeur)
    

• Propriétés des ensembles (unicité):
  • Un ensemble (set) est une collection non ordonnée d'éléments uniques. Il n'y a pas de doublons.
  • mon_set = {1, 2, 3, 3, 4} donnera {1, 2, 3, 4}.
  • Utile pour éliminer les doublons d'une liste : liste_avec_doublons = [1, 2, 2, 3]; unique_elements = set(liste_avec_doublons)
  • Opérations ensemblistes:
    • Union (| ou union()): A | B
    • Intersection (& ou intersection()): A & B
    • Différence (- ou difference()): A - B
    • Appartenance (in): 2 in mon_set
  • Les ensembles sont très efficaces pour vérifier l'appartenance d'un élément.

Il est courant de combiner les structures de données pour représenter des informations plus complexes.

Key Concepts:

• Listes de listes: Représentent souvent des matrices ou des tableaux à deux dimensions.
  • matrice = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
  • Accès : matrice[0][1] donne 2 (ligne 0, colonne 1).
• Dictionnaires de listes: Une clé peut pointer vers une liste de valeurs.
  • eleves = {"Alice": ["Maths", "Physique"], "Bob": ["Chimie", "SVT"]}
  • Accès : eleves["Alice"][0] donne "Maths".
• Dictionnaires de dictionnaires: Pour des données encore plus structurées.
  • carnet_adresses = {"Alice": {"ville": "Paris", "tel": "06..."}, "Bob": {"ville": "Lyon", "tel": "07..."}}
  • Accès : carnet_adresses["Alice"]["ville"] donne "Paris".
• Accès aux éléments imbriqués: Se fait en chaînant les opérateurs d'indexation [] ou d'accès par clé.
  • Comprendre la structure pour accéder aux données est crucial. Visualisez-les comme des boîtes contenant d'autres boîtes.

La recherche est l'action de trouver un élément spécifique dans une collection de données.

Key Concepts:

• Principe de la recherche séquentielle:
  • Parcourt la collection élément par élément, du début à la fin, jusqu'à ce que l'élément soit trouvé ou que la fin de la collection soit atteinte.
  • Avantage: Fonctionne sur n'importe quelle collection, qu'elle soit triée ou non.
  • Inconvénient: Peut être très lente pour de grandes collections.

  def recherche_sequentielle(liste, element):
      for i in range(len(liste)):
          if liste[i] == element:
              return i # Retourne l'indice si trouvé
      return -1 # Retourne -1 si non trouvé
  

• Prérequis pour la recherche dichotomique:
  • La collection doit être triée. C'est une condition impérative.
• Principe de la recherche dichotomique (binaire):
  • Divise la collection en deux moitiés à chaque étape.
  • Compare l'élément recherché avec l'élément du milieu de la collection.
  • Si l'élément est égal, il est trouvé.
  • S'il est plus petit, la recherche continue dans la moitié gauche.
  • S'il est plus grand, la recherche continue dans la moitié droite.
  • Ce processus est répété jusqu'à ce que l'élément soit trouvé ou que la sous-collection devienne vide.

  def recherche_dichotomique(liste_triee, element):
      gauche, droite = 0, len(liste_triee) - 1
      while gauche <= droite:
          milieu = (gauche + droite) // 2
          if liste_triee[milieu] == element:
              return milieu
          elif liste_triee[milieu] < element:
              gauche = milieu + 1
          else: # liste_triee[milieu] > element
              droite = milieu - 1
      return -1
  

• Complexité des algorithmes de recherche:
  • Recherche séquentielle:
    • Pire cas : $O(n)$ (l'élément est le dernier ou n'est pas présent).
    • Meilleur cas : $O(1)$ (l'élément est le premier).
    • Cas moyen : $O(n)$.
  • Recherche dichotomique:
    • Pire cas : $O(\log n)$. La taille du problème est divisée par deux à chaque étape.
    • Meilleur cas : $O(1)$ (l'élément est au milieu).
    • Cas moyen : $O(\log n)$.
  • Pour de grandes listes, la recherche dichotomique est exponentiellement plus rapide que la recherche séquentielle, à condition que la liste soit triée.

Le tri par sélection est un algorithme de tri simple.

Key Concepts:

• Principe du tri par sélection:
  1. Trouver le plus petit (ou plus grand) élément dans la partie non triée de la liste.
  2. L'échanger avec le premier élément de la partie non triée.
  3. Répéter l'opération pour la partie restante de la liste, en réduisant la partie non triée d'un élément à chaque fois.
• Implémentation pas à pas:

  def tri_selection(liste):
      n = len(liste)
      for i in range(n - 1): # Parcourt de 0 à n-2
          min_idx = i
          for j in range(i + 1, n): # Recherche le min dans la partie non triée
              if liste[j] < liste[min_idx]:
                  min_idx = j
          # Échange l'élément courant avec le plus petit trouvé
          liste[i], liste[min_idx] = liste[min_idx], liste[i]
      return liste
  

• Analyse de la complexité:
  • Le tri par sélection effectue toujours le même nombre de comparaisons, quelle que soit l'organisation initiale de la liste.
  • Boucle externe n-1 fois. Boucle interne n-i fois.
  • Nombre total de comparaisons : $(n-1) + (n-2) + ... + 1 = \frac{n(n-1)}{2}$.
  • Nombre d'échanges : $n-1$.
  • Complexité temporelle : $O(n^2)$ dans tous les cas (meilleur, pire, moyen).
  • Complexité spatiale : $O(1)$ (tri en place, ne nécessite pas d'espace supplémentaire significatif).

Le tri par insertion est un autre algorithme de tri simple, souvent comparé à la façon dont on trie des cartes dans une main.

Key Concepts:

• Principe du tri par insertion:
  1. On considère que le premier élément est déjà trié.
  2. Pour chaque élément restant (à partir du deuxième), on le prend et on l'insère à sa place correcte dans la partie déjà triée de la liste.
  3. Cela implique de décaler les éléments plus grands vers la droite pour faire de la place.
• Comparaison avec le tri par sélection:
  • Le tri par sélection trouve le minimum et le place.
  • Le tri par insertion prend un élément et l'insère à sa place dans la partie déjà triée.
  • Le tri par insertion peut être plus rapide que le tri par sélection sur des listes presque triées.
• Cas favorable et défavorable:

  def tri_insertion(liste):
      for i in range(1, len(liste)): # Parcourt à partir du deuxième élément
          cle = liste[i] # L'élément à insérer
          j = i - 1
          # Déplace les éléments plus grands que 'cle' d'une position vers la droite
          while j >= 0 and cle < liste[j]:
              liste[j + 1] = liste[j]
              j -= 1
          liste[j + 1] = cle # Insère 'cle' à sa place
      return liste
  

  • Complexité temporelle:
    • Pire cas : $O(n^2)$ (liste triée en ordre inverse). Chaque élément doit être décalé jusqu'au début.
    • Meilleur cas : $O(n)$ (liste déjà triée). Seulement $n-1$ comparaisons, pas de décalage.
    • Cas moyen : $O(n^2)$.
  • Complexité spatiale : $O(1)$ (tri en place).
  • Le tri par insertion est efficace pour de petites listes ou des listes presque triées.

Le Quicksort est un algorithme de tri très efficace, basé sur la stratégie "diviser pour régner".

Key Concepts:

• Principe de la division pour régner:
  1. Diviser: Choisir un élément de la liste, appelé pivot. Réorganiser la liste de manière à ce que tous les éléments plus petits que le pivot viennent avant lui, et tous les éléments plus grands viennent après lui. Le pivot est maintenant à sa place finale.
  2. Régner: Appliquer récursivement le Quicksort aux sous-listes des éléments plus petits et plus grands que le pivot.
  3. Combiner: Les sous-listes étant triées en place, aucune étape de combinaison n'est nécessaire.
• Choix du pivot:
  • Le choix du pivot est crucial pour la performance de Quicksort.
  • Un mauvais choix (par exemple, toujours le premier ou le dernier élément sur une liste déjà triée) peut conduire au pire des cas.
  • Stratégies courantes : premier élément, dernier élément, élément du milieu, ou un élément aléatoire.
  • Une bonne stratégie est de choisir la médiane de trois (premier, milieu, dernier) pour réduire la probabilité du pire cas.
• Complexité moyenne et pire cas:

  def quicksort(liste):
      if len(liste) <= 1:
          return liste
      else:
          pivot = liste[len(liste) // 2] # Choix simple du pivot
          inferieurs = [x for x in liste if x < pivot]
          egaux = [x for x in liste if x == pivot]
          superieurs = [x for x in liste if x > pivot]
          return quicksort(inferieurs) + egaux + quicksort(superieurs)
  

  • Complexité temporelle:
    • Cas moyen : $O(n \log n)$. C'est l'un des algorithmes de tri les plus rapides en pratique.
    • Pire cas : $O(n^2)$. Se produit lorsque le pivot est toujours le plus petit ou le plus grand élément, ce qui entraîne des sous-listes très déséquilibrées.
  • Complexité spatiale : Dépend de l'implémentation, $O(\log n)$ en moyenne pour la pile d'appels récursifs, $O(n)$ dans le pire cas si non optimisé (comme l'implémentation ci-dessus qui crée de nouvelles listes).
  • Le Quicksort est souvent préféré pour sa rapidité en moyenne.

Key Concepts:

• Définition d'une fonction récursive: Une fonction qui, dans sa définition, s'appelle elle-même.
• Cas de base et cas récursif:
  • Le cas de base (ou condition d'arrêt) : C'est la condition qui met fin à la récursion. Sans cas de base, la fonction s'appellerait indéfiniment, provoquant une erreur de "profondeur de récursion maximale dépassée".
  • Le cas récursif : La fonction s'appelle elle-même avec une version plus petite du problème. Le problème doit converger vers le cas de base.
• Exemples simples (factorielle, Fibonacci):
  • Factorielle ($n!$): Le produit de tous les entiers positifs inférieurs ou égaux à $n$. $n! = n \times (n-1)!$ et $0! = 1$.

    def factorielle(n):
        if n == 0: # Cas de base
            return 1
        else: # Cas récursif
            return n * factorielle(n - 1)
    

  • Suite de Fibonacci ($F_n$): Où chaque nombre est la somme des deux précédents, commençant par $F_0=0$ et $F_1=1$.

    def fibonacci(n):
        if n <= 1: # Cas de base
            return n
        else: # Cas récursif
            return fibonacci(n - 1) + fibonacci(n - 2)
    

  • Ces exemples illustrent bien la décomposition d'un problème en sous-problèmes identiques mais plus simples.

La plupart des problèmes résolubles par récursivité peuvent aussi être résolus par itération (boucles for, while).

Key Concepts:

• Conversion d'un algorithme récursif en itératif:
  • Un algorithme itératif utilise des boucles pour répéter des actions.
  • Exemple de factorielle itérative :

    def factorielle_iterative(n):
        resultat = 1
        for i in range(1, n + 1):
            resultat *= i
        return resultat
    

  • Exemple de Fibonacci itérative :

    def fibonacci_iterative(n):
        if n <= 1:
            return n
        a, b = 0, 1
        for _ in range(2, n + 1):
            a, b = b, a + b
        return b
    

• Avantages et inconvénients:
  • Récursivité:
    • Avantages: Code souvent plus concis et élégant pour certains problèmes (ex: parcours d'arbres, Tours de Hanoï). Reflète mieux la définition mathématique de certains problèmes.
    • Inconvénients: Peut être moins performante (coût des appels de fonction et gestion de la pile d'appels). Risque de RecursionError (dépassement de la pile) si la profondeur de récursion est trop grande.
  • Itération:
    • Avantages: Généralement plus rapide et utilise moins de mémoire car pas de pile d'appels récursifs à gérer. Pas de risque de débordement de pile.
    • Inconvénients: Le code peut être plus complexe à écrire pour certains problèmes récursifs par nature.
• Gestion de la pile d'appels:
  • Lorsqu'une fonction est appelée, ses variables locales et l'adresse de retour sont stockées sur la pile d'appels (appelée "stack" en anglais).
  • Pour une fonction récursive, chaque appel ajoute une nouvelle "frame" à la pile. Si la récursion est trop profonde, la pile peut déborder.
  • Python a une limite de récursion par défaut (environ 1000 appels), modifiable avec sys.setrecursionlimit().

Key Concepts:

• Parcours d'arbres (préfixe, infixe, postfixe):
  • Les arbres sont des structures de données récursives par nature. Le parcours d'un arbre est un excellent exemple d'application de la récursivité.
  • Parcours préfixe (NLR - Nœud, Gauche, Droite): Traite le nœud, puis traverse récursivement le sous-arbre gauche, puis le sous-arbre droit.
  • Parcours infixe (LNR - Gauche, Nœud, Droite): Traverse récursivement le sous-arbre gauche, puis traite le nœud, puis traverse récursivement le sous-arbre droit. Utile pour obtenir les éléments d'un arbre binaire de recherche triés.
  • Parcours postfixe (LRN - Gauche, Droite, Nœud): Traverse récursivement le sous-arbre gauche, puis le sous-arbre droit, puis traite le nœud.
• Problème des tours de Hanoï:
  • Un problème classique qui illustre parfaitement la récursivité. L'objectif est de déplacer $n$ disques d'une tour de départ à une tour d'arrivée, en utilisant une tour auxiliaire, sans jamais placer un disque plus grand sur un plus petit.
  • La solution est récursive :
    1. Déplacer $n-1$ disques de la tour de départ à la tour auxiliaire.
    2. Déplacer le plus grand disque (le $n$-ième) de la tour de départ à la tour d'arrivée.
    3. Déplacer les $n-1$ disques de la tour auxiliaire à la tour d'arrivée.
• Backtracking (introduction):
  • Le backtracking (ou retour sur trace) est une technique algorithmique pour résoudre des problèmes combinatoires. Elle explore toutes les solutions possibles en construisant une solution étape par étape et en "retournant en arrière" (backtracking) lorsque la solution partielle ne peut pas être complétée ou ne mène pas à une solution valide.
  • Souvent implémentée de manière récursive.
  • Exemples : résolution de Sudoku, problème des 8 reines, trouver tous les chemins dans un labyrinthe.

Key Concepts:

• Classes et objets:
  • Une classe est un plan (ou un modèle) pour créer des objets. Elle définit les caractéristiques (attributs) et les comportements (méthodes) communs à tous les objets de ce type.
  • Un objet est une instance concrète d'une classe. Chaque objet a ses propres valeurs pour les attributs définis par sa classe.
  • Exemple: Class: Voiture, Objet: ma_voiture (une voiture spécifique de couleur rouge, modèle Clio).
• Attributs et méthodes:
  • Les attributs sont les données (variables) associées à un objet. Ils décrivent l'état de l'objet (ex: couleur, modele pour une voiture).
  • Les méthodes sont les fonctions qui opèrent sur les données de l'objet. Elles décrivent le comportement de l'objet (ex: demarrer(), accelerer() pour une voiture).
• Encapsulation:
  • C'est le principe de regrouper les données (attributs) et les méthodes qui les manipulent au sein d'une seule unité (la classe).
  • Elle permet de masquer les détails d'implémentation internes d'un objet et de n'exposer qu'une interface publique. Cela protège les données de l'objet contre les modifications externes non autorisées et rend le code plus robuste et facile à maintenir.
  • En Python, l'encapsulation est souvent réalisée par convention (préfixer les attributs avec _ ou __ pour indiquer qu'ils sont privés), mais elle n'est pas strictement imposée comme dans d'autres langages.

Key Concepts:

• Syntaxe de définition d'une classe:
  • On utilise le mot-clé class, suivi du nom de la classe (conventionnellement en CamelCase).

  class MaClasse:
      # Attributs de classe (partagés par toutes les instances)
      nombre_instances = 0
  
      # Méthodes
      def une_methode(self):
          print("Ceci est une méthode.")
  

• Constructeur (__init__):
  • C'est une méthode spéciale appelée automatiquement lors de la création d'un nouvel objet (instanciation).
  • Elle est utilisée pour initialiser les attributs de l'objet.
  • Le premier paramètre des méthodes d'instance est toujours self, qui représente l'instance de l'objet elle-même.

  class Personne:
      def __init__(self, nom, age):
          self.nom = nom  # Attribut d'instance
          self.age = age  # Attribut d'instance
          Personne.nombre_instances += 1 # Incrémente l'attribut de classe
  
      def saluer(self):
          return f"Bonjour, je m'appelle {self.nom} et j'ai {self.age} ans."
  

• Création d'instances d'objets:
  • Pour créer un objet (instancier une classe), on appelle la classe comme une fonction.

  # Instanciation de la classe Personne
  personne1 = Personne("Alice", 30)
  personne2 = Personne("Bob", 25)
  
  print(personne1.saluer()) # Appelle une méthode de l'objet
  print(personne2.age)      # Accède à un attribut de l'objet
  print(Personne.nombre_instances) # Accède à l'attribut de classe
  

Ces concepts sont clés pour la réutilisabilité et la flexibilité du code.

Key Concepts:

• Héritage:
  • Permet à une nouvelle classe (classe enfant ou dérivée) d'acquérir les attributs et méthodes d'une classe existante (classe parente ou base).
  • Cela modélise une relation "est un" (par exemple, une Voiture est un Vehicule).
  • La classe enfant peut ajouter de nouveaux attributs/méthodes ou modifier/redéfinir ceux de la classe parente.

  class Vehicule:
      def __init__(self, marque):
          self.marque = marque
      def afficher_marque(self):
          return f"Marque: {self.marque}"
  
  class Voiture(Vehicule): # Voiture hérite de Vehicule
      def __init__(self, marque, modele):
          super().__init__(marque) # Appelle le constructeur de la classe parente
          self.modele = modele
      def afficher_details(self):
          return f"{self.afficher_marque()}, Modèle: {self.modele}"
  

  • ma_voiture = Voiture("Renault", "Clio")
  • print(ma_voiture.afficher_details())
• Polymorphisme:
  • Signifie "plusieurs formes". En POO, cela permet à des objets de classes différentes de répondre à la même méthode de manière différente.
  • Les objets de différentes classes peuvent être traités de manière uniforme s'ils partagent une interface commune (méthodes avec le même nom).
  • La surcharge de méthodes n'existe pas en Python dans le sens strict d'autres langages (méthodes avec le même nom mais signatures différentes). En revanche, le polymorphisme par substitution est très présent : on peut substituer un objet d'une classe fille à un objet de sa classe mère.
  • Surcharge de méthodes (Redéfinition): Une méthode de la classe parente est redéfinie dans la classe enfant pour avoir un comportement spécifique.

    class Chien(Animal):
        def crier(self):
            return "Woof!"
    class Chat(Animal):
        def crier(self):
            return "Miaou!"
    
    def faire_crier(animal):
        print(animal.crier()) # Polymorphisme: la même méthode crier()
                              # est appelée sur différents types d'objets
    

• Avantages de l'héritage:
  • Réutilisabilité du code: Évite de réécrire le même code.
  • Maintenance facilitée: Les modifications dans la classe parente se propagent aux enfants.
  • Extensibilité: Facile d'ajouter de nouvelles fonctionnalités via de nouvelles classes dérivées.

Python utilise des méthodes spéciales (aussi appelées "méthodes magiques" ou "dunder methods" pour "double underscore") pour implémenter des comportements d'objets.

Key Concepts:

• Méthodes d'affichage (__str__, __repr__):
  • <mark>__str__(self)</mark>: Définit la représentation "informelle" ou "lisible par l'utilisateur" d'un objet. C'est ce qui est affiché par print(objet) ou str(objet).
  • <mark>__repr__(self)</mark>: Définit la représentation "officielle" ou "non ambiguë" d'un objet, utilisée par les développeurs pour le débogage. C'est ce qui est affiché par défaut dans l'interpréteur Python ou par repr(objet). Idéalement, eval(repr(objet)) devrait recréer l'objet.

  class Point:
      def __init__(self, x, y):
          self.x = x
          self.y = y
      def __str__(self):
          return f"Point({self.x}, {self.y})"
      def __repr__(self):
          return f"Point(x={self.x}, y={self.y})"
  
  p = Point(1, 2)
  print(p)     # Affiche: Point(1, 2) (utilise __str__)
  print(repr(p)) # Affiche: Point(x=1, y=2) (utilise __repr__)
  

• Opérateurs surchargés:
  • Les méthodes spéciales permettent de définir le comportement des opérateurs standards (+, -, *, /, ==, <, etc.) pour les objets de votre classe.
  • Exemples:
    • __add__(self, other) pour l'opérateur +
    • __eq__(self, other) pour l'opérateur ==
    • __len__(self) pour la fonction len()

  class Vecteur:
      def __init__(self, x, y):
          self.x = x
          self.y = y
      def __add__(self, autre):
          return Vecteur(self.x + autre.x, self.y + autre.y)
      def __eq__(self, autre):
          return self.x <mark> autre.x and self.y </mark> autre.y
  
  v1 = Vecteur(1, 2)
  v2 = Vecteur(3, 4)
  v3 = v1 + v2 # Appelle v1.__add__(v2)
  print(v3.x, v3.y) # Affiche: 4 6
  print(v1 == Vecteur(1, 2)) # Affiche: True (appelle v1.__eq__(Vecteur(1,2)))
  

• Propriétés (@property):
  • Permettent de gérer l'accès aux attributs de manière contrôlée, comme s'il s'agissait d'attributs directs, mais en exécutant des méthodes (getters, setters, deleters) en arrière-plan.
  • Utile pour la validation des données ou pour des attributs calculés.

  class Carre:
      def __init__(self, cote):
          self._cote = cote # Attribut "privé" par convention
  
      @property # Getter
      def cote(self):
          return self._cote
  
      @cote.setter # Setter
      def cote(self, valeur):
          if valeur < 0:
              raise ValueError("Le côté ne peut pas être négatif")
          self._cote = valeur
  
      @property # Attribut calculé
      def surface(self):
          return self._cote * self._cote
  
  c = Carre(5)
  print(c.cote)    # Accède au getter
  print(c.surface) # Accède à l'attribut calculé
  c.cote = 10      # Accède au setter
  # c.cote = -2    # Lance une ValueError
  

  • Les propriétés permettent de modifier l'implémentation interne d'un attribut sans changer la manière dont il est utilisé de l'extérieur, garantissant une meilleure encapsulation.

Interagir avec des fichiers est une tâche courante en programmation.

Key Concepts:

• Ouverture et fermeture de fichiers:
  • La fonction open() est utilisée pour ouvrir un fichier. Elle retourne un objet fichier.
  • Syntaxe : fichier = open("nom_du_fichier.txt", "mode")
  • Il est crucial de fermer le fichier après utilisation pour libérer les ressources système et s'assurer que toutes les écritures sont bien enregistrées. fichier.close()
  • La meilleure pratique est d'utiliser le mot-clé with, qui garantit que le fichier est automatiquement fermé, même en cas d'erreur :

    with open("mon_fichier.txt", "r") as f:
        contenu = f.read()
    # Le fichier est automatiquement fermé ici
    

• Modes d'accès (lecture, écriture, ajout):
  • "r": Lecture (Read). C'est le mode par défaut. Le fichier doit exister.
  • "w": Écriture (Write). Crée un nouveau fichier s'il n'existe pas. Si le fichier existe, son contenu est tronqué (effacé) avant l'écriture.
  • "a": Ajout (Append). Crée un nouveau fichier s'il n'existe pas. Si le fichier existe, les nouvelles données sont ajoutées à la fin.
  • "x": Création exclusive. Crée un nouveau fichier. Lève une erreur si le fichier existe déjà.
  • "r+": Lecture et écriture.
  • Vous pouvez ajouter b pour le mode binaire (ex: "rb", "wb").
• Lecture ligne par ligne ou en bloc:
  • Lecture en bloc (read()): Lit tout le contenu du fichier dans une seule chaîne de caractères.

    with open("data.txt", "r") as f:
        tout_le_contenu = f.read()
    

  • Lecture ligne par ligne (readline()): Lit une seule ligne à la fois.

    with open("data.txt", "r") as f:
        premiere_ligne = f.readline()
        deuxieme_ligne = f.readline()
    

  • Lecture de toutes les lignes (readlines()): Retourne une liste de toutes les lignes du fichier.

    with open("data.txt", "r") as f:
        liste_de_lignes = f.readlines() # Chaque ligne inclut le caractère de fin de ligne '\n'
    

  • Itération sur l'objet fichier: La manière la plus efficace de lire un fichier ligne par ligne.

    with open("data.txt", "r") as f:
        for ligne in f:
            print(ligne.strip()) # .strip() pour enlever les espaces et '\n'
    

  • Écriture (write(), writelines()):

    with open("output.txt", "w") as f:
        f.write("Ceci est la première ligne.\n")
        f.write("Ceci est la deuxième ligne.\n")
        lignes = ["Ligne 3\n", "Ligne 4\n"]
        f.writelines(lignes) # Écrit une liste de chaînes
    

Les fichiers CSV (Comma Separated Values) sont un format courant pour stocker des données tabulaires.

Key Concepts:

• Format CSV:
  • Un fichier texte où chaque ligne représente un enregistrement de données.
  • Les champs de chaque enregistrement sont séparés par un délimiteur, souvent une virgule (,), un point-virgule (;) ou une tabulation (\t).
  • La première ligne contient souvent les en-têtes de colonne.
  • Exemple:

    Nom,Age,Ville
    Alice,30,Paris
    Bob,25,Lyon
    

• Lecture et écriture avec le module csv:
  • Le module csv de Python est spécialement conçu pour manipuler ce format. Il gère les guillemets et les caractères spéciaux.
  • Lecture: Utilise csv.reader (pour les listes) ou csv.DictReader (pour les dictionnaires).

    import csv
    with open('personnes.csv', 'r', newline='') as fichier_csv:
        lecteur = csv.reader(fichier_csv) # Retourne des lignes comme listes
        # lecteur = csv.DictReader(fichier_csv) # Retourne des lignes comme dictionnaires
        for ligne in lecteur:
            print(ligne)
    

  • Écriture: Utilise csv.writer ou csv.DictWriter.

    import csv
    donnees = [
        ['Nom', 'Age', 'Ville'],
        ['Charlie', 35, 'Marseille'],
        ['Dana', 28, 'Bordeaux']
    ]
    with open('nouvelles_personnes.csv', 'w', newline='') as fichier_csv:
        ecrivain = csv.writer(fichier_csv)
        ecrivain.writerows(donnees) # Écrit toutes les lignes
    

• Traitement des données tabulaires:
  • Le module csv simplifie grandement l'analyse et la génération de données tabulaires.
  • DictReader et DictWriter sont particulièrement utiles car ils permettent d'accéder aux colonnes par leur nom (comme un dictionnaire), ce qui rend le code plus lisible et robuste aux changements d'ordre des colonnes.
  • ==Toujours utiliser newline='' lors de l'ouverture de fichiers CSV== pour éviter les problèmes de double espacement entre les lignes sur certains systèmes d'exploitation.

La gestion des erreurs est cruciale pour créer des programmes robustes et fiables.

Key Concepts:

• Types d'erreurs (syntaxe, exécution):
  • Erreurs de syntaxe (SyntaxError): Erreurs détectées par l'interpréteur avant l'exécution du code. Elles empêchent le programme de démarrer (ex: parenthèse manquante, mot-clé mal orthographié).
  • Erreurs d'exécution (Exceptions): Erreurs qui se produisent pendant l'exécution du programme. Le programme démarre mais s'arrête brutalement si l'exception n'est pas gérée.
    • NameError: Variable non définie.
    • TypeError: Opération incompatible avec le type de données.
    • ValueError: Valeur inappropriée (ex: int("abc")).
    • ZeroDivisionError: Division par zéro.
    • FileNotFoundError: Fichier non trouvé.
    • IndexError: Indice hors limites pour une liste/chaîne.
    • KeyError: Clé non trouvée dans un dictionnaire.
• Blocs try-except-finally:
  • Permet de gérer les exceptions de manière contrôlée, évitant l'arrêt brutal du programme.
  • <mark>try</mark>: Le code potentiellement risqué est placé ici.
  • <mark>except [ExceptionType] as e</mark>: Si une exception se produit dans le bloc try, le contrôle passe au bloc except correspondant. Vous pouvez spécifier le type d'exception à intercepter et la récupérer dans une variable e.
  • <mark>else</mark>: (Optionnel) Le code dans ce bloc est exécuté si aucune exception ne s'est produite dans le bloc try.
  • <mark>finally</mark>: (Optionnel) Le code dans ce bloc est toujours exécuté, qu'une exception se soit produite ou non et qu'elle ait été gérée ou non. Idéal pour le nettoyage (fermeture de fichiers, libération de ressources).

  try:
      nombre = int(input("Entrez un nombre: "))
      resultat = 10 / nombre
  except ValueError:
      print("Erreur: Ce n'est pas un nombre valide.")
  except ZeroDivisionError:
      print("Erreur: Division par zéro impossible.")
  except Exception as e: # Intercepte toute autre exception
      print(f"Une erreur inattendue s'est produite: {e}")
  else:
      print(f"Le résultat est: {resultat}")
  finally:
      print("Fin du bloc try-except.")
  

• Lever des exceptions (raise):
  • Vous pouvez explicitement lever une exception à l'aide du mot-clé raise si une condition d'erreur spécifique est rencontrée dans votre code.
  • raise ValueError("L'âge ne peut pas être négatif")
  • Ceci est utile pour signaler des problèmes à d'autres parties du programme ou à l'utilisateur, et pour créer vos propres types d'exceptions personnalisées.

Key Concepts:

• Mesure de l'efficacité:
  • La complexité algorithmique mesure les ressources (temps et espace) qu'un algorithme utilise en fonction de la taille de ses entrées.
  • Elle ne mesure pas le temps réel d'exécution (qui dépend de la machine, du langage, etc.) mais plutôt la croissance des ressources requises lorsque la taille des données d'entrée augmente.
• Temps d'exécution et espace mémoire:
  • Complexité temporelle: Le nombre d'opérations élémentaires effectuées par l'algorithme. C'est la ressource la plus souvent analysée.
  • Complexité spatiale: La quantité de mémoire supplémentaire utilisée par l'algorithme (au-delà de l'espace nécessaire pour stocker les entrées).
• Indépendance de la machine:
  • L'analyse de complexité est indépendante de la machine et des facteurs externes. Elle se concentre sur le nombre d'opérations abstraites (comparaisons, affectations, additions, etc.) qu'un algorithme effectue.
  • Un algorithme $O(n)$ sera toujours plus rapide qu'un algorithme $O(n^2)$ pour de grandes valeurs de $n$, quelle que soit la puissance de l'ordinateur.

La notation Grand O ($\mathcal{O}$) est la plus courante pour décrire la complexité.

Key Concepts:

• Définition du Grand O:
  • La notation $\mathcal{O}(g(n))$ décrit la limite supérieure du temps d'exécution (ou de l'espace mémoire) d'un algorithme.
  • Elle indique comment le temps d'exécution croît avec la taille de l'entrée $n$ dans le pire des cas.
  • On ignore les constantes et les termes d'ordre inférieur car ils deviennent négligeables pour de très grandes valeurs de $n$. Par exemple, $3n^2 + 2n + 5$ est $\mathcal{O}(n^2)$.
• Exemples de complexités:
  • $\mathcal{O}(1)$ (Complexité constante): Le temps d'exécution ne dépend pas de la taille de l'entrée. Ex: accéder à un élément d'une liste par son indice, ajouter/supprimer un élément d'un dictionnaire.
  • $\mathcal{O}(\log n)$ (Complexité logarithmique): Le temps d'exécution croît très lentement avec la taille de l'entrée. Souvent associé aux algorithmes qui divisent le problème en deux à chaque étape. Ex: recherche dichotomique.
  • $\mathcal{O}(n)$ (Complexité linéaire): Le temps d'exécution croît proportionnellement à la taille de l'entrée. Ex: recherche séquentielle, parcours d'une liste.
  • $\mathcal{O}(n \log n)$ (Complexité linéaire-logarithmique): Très efficace pour le tri. Ex: Tri rapide (en moyenne), Tri fusion.
  • $\mathcal{O}(n^2)$ (Complexité quadratique): Le temps d'exécution croît avec le carré de la taille de l'entrée. Souvent dû à des boucles imbriquées. Ex: Tri par sélection, Tri par insertion (pire cas).
  • $\mathcal{O}(2^n)$ (Complexité exponentielle): Le temps d'exécution croît très rapidement. Généralement inacceptable pour des entrées de taille moyenne. Ex: résolution de problèmes par force brute.
• Comparaison des ordres de grandeur:
  • $\mathcal{O}(1) < \mathcal{O}(\log n) < \mathcal{O}(n) < \mathcal{O}(n \log n) < \mathcal{O}(n^2) < \mathcal{O}(2^n) < \mathcal{O}(n!)$
  • Il est crucial de choisir des algorithmes avec une complexité aussi basse que possible pour les grandes quantités de données.

Key Concepts:

• Complexité des tris et recherches:
  • Recherche séquentielle: $\mathcal{O}(n)$
  • Recherche dichotomique: $\mathcal{O}(\log n)$ (sur liste triée)
  • Tri par sélection: $\mathcal{O}(n^2)$
  • Tri par insertion: $\mathcal{O}(n^2)$ (pire cas), $\mathcal{O}(n)$ (meilleur cas)
  • Tri rapide (Quicksort): $\mathcal{O}(n \log n)$ (moyen), $\mathcal{O}(n^2)$ (pire cas)
• Impact des boucles et appels de fonctions:
  • Une seule boucle sur $n$ éléments : $\mathcal{O}(n)$.
  • Deux boucles imbriquées sur $n$ éléments : $\mathcal{O}(n^2)$.
  • Une fonction qui s'appelle récursivement en divisant le problème en deux : $\mathcal{O}(\log n)$.
  • Une fonction qui s'appelle récursivement $k$ fois pour un problème de taille $n$, où $k$ est une constante : $\mathcal{O}(k^n)$ ou $\mathcal{O}(n^k)$ selon le type de récursion.
  • L'analyse repose sur le comptage des opérations dominantes en fonction de $n$.
• Meilleur, pire et cas moyen:
  • Meilleur cas: La complexité minimale possible pour une entrée donnée. Souvent moins pertinente en pratique.
  • Pire cas: La complexité maximale possible. C'est la plus importante car elle garantit la performance minimale de l'algorithme.
  • Cas moyen: La complexité moyenne sur toutes les entrées possibles. Souvent plus représentative de la performance réelle mais plus difficile à calculer.
  • La notation Grand O se réfère généralement au pire cas, sauf indication contraire.