Fiche de révision : Algorithmique et structures de données

📋 Plan du Cours

1. Tuples et affectations parallèles
2. Listes et chaînes de caractères
3. Dictionnaires piles et files
4. Tris et recherches itératifs
5. Fichiers et tableaux Python
6. Tableaux et calcul matriciel NumPy
7. Tracé graphique avec Matplotlib
8. Récursivité et tris avancés
9. Arbres binaires et parcours
10. Arbres spécialisés et recherche
11. Complexité algorithmique
12. Graphes et parcours

📖 1. Tuples et affectations parallèles

🔑 Notions clés & Définitions

• Tuple : Structure non mutable dont le contenu ne peut pas être modifié.

📝 Points essentiels

• La concaténation de deux tuples avec + place leurs éléments bout à bout, par exemple (1,2,3) + (4,0) donne (1,2,3,4,0).

• L'affectation parallèle permet d'écrire (a,b,c) = (1,2,3) et d'échanger deux valeurs avec (a,b) = (b,a).

💡 Astuce mémo

Tuple immuable, affectation parallèle modifiable

📖 2. Listes et chaînes de caractères

🔑 Notions clés & Définitions

• Chaîne de caractères : Séquence de type str, indexable et non mutable.

★ À maîtriser

• Les indices négatifs d'une liste commencent à la fin : L[-1] désigne le dernier élément et L[-2] l'avant-dernier.

• Pour une liste L, L[a:b] extrait les éléments d'indice a inclus à b exclu, tandis que L[a:], L[:b], L[:] et L[:-1] sélectionnent respectivement la fin depuis a, le début jusqu'à b-1, toute la liste et toute la liste sauf le dernier élément.

Compléments

• La méthode append ajoute un élément à la fin d'une liste, del(L[a:b]) supprime une tranche et L.sort() trie la liste.

💡 Astuce mémo

Une liste indexée comme une chaîne, avec une fin repérée par -1

📖 3. Dictionnaires piles et files

🔑 Notions clés & Définitions

• Pile : Structure LIFO dans laquelle le dernier élément entré est le premier sorti, et seul le sommet est directement accessible.
• File : Structure FIFO dans laquelle les éléments sont ajoutés à la queue et retirés à la tête.

📝 Points essentiels

• Un dictionnaire associe des valeurs à des clés, qui permettent d'ajouter ou de modifier une valeur avec D[clé] = valeur et de supprimer une clé avec del(D[clé]) ou D.pop(clé).

💡 Astuce mémo

Pile LIFO : dernier entré, file FIFO : premier entré

📖 4. Tris et recherches itératifs

📝 Points essentiels

• Le tri par sélection cherche le maximum dans la partie non triée, l'échange avec le dernier élément de cette partie, puis recommence vers la gauche.

• Le tri par insertion parcourt la liste et insère chaque élément à sa position dans la partie déjà triée en décalant les éléments supérieurs.

📌 La recherche séquentielle examine les éléments successivement, tandis que la recherche dichotomique divise par deux une liste triée à chaque étape.

💡 Astuce mémo

Comparer, sélectionner, insérer puis rechercher séquentiellement ou par dichotomie

📖 5. Fichiers et tableaux Python

📝 Points essentiels

📌 La fonction open(chemin, mode) ouvre un fichier ; le mode r lit, w écrit en écrasant ou crée le fichier, a ajoute sans écraser et r+ permet la lecture et l'écriture.

• Un fichier ouvert doit être fermé avec close() à la fin du programme.

• read(t) lit t caractères à partir de la position courante, readline() lit une ligne et readlines() renvoie la liste de toutes les lignes.

💡 Astuce mémo

Ouvrir, lire ou écrire, puis fermer

📖 6. Tableaux et calcul matriciel NumPy

🔑 Notions clés & Définitions

• Tableau bidimensionnel : Liste dont chaque élément est une liste représentant une ligne, avec un nombre de lignes et de colonnes.

📝 Points essentiels

• La fonction array() transforme une liste ou une liste de listes en tableau NumPy, et append, delete et insert permettent respectivement d'ajouter, supprimer et insérer des éléments.

• La fonction reshape transforme la forme d'un tableau sans changer ses éléments, par exemple arange(15).reshape(5,3) produit 5 lignes et 3 colonnes.

• dot(A,B) calcule le produit matriciel de deux matrices, tandis que vdot(A,B) calcule le produit scalaire de deux vecteurs.

💡 Astuce mémo

Un tableau devient une matrice par reshape puis matrix

📖 7. Tracé graphique avec Matplotlib

📝 Points essentiels

• Dans matplotlib.pyplot, plot trace une courbe, xlabel et ylabel nomment les axes, title ajoute un titre, grid ajoute une grille, legend ajoute une légende et show affiche la figure.

💡 Astuce mémo

Tracer, nommer, quadriller, légender, afficher

📖 8. Récursivité et tris avancés

🔑 Notions clés & Définitions

• Récursivité : Méthode dans laquelle une fonction s'appelle elle-même jusqu'à l'atteinte d'une condition de base.

📝 Points essentiels

• Les formes de récursivité sont:

  • Simple : un appel récursif par étape
  • Multiple : plusieurs appels récursifs par étape
  • Imbriquée : un appel récursif est utilisé comme paramètre
  • Mutuelle : plusieurs fonctions récursives s'appellent entre elles

• Le tri fusion divise récursivement une liste jusqu'à obtenir des listes d'un élément, puis fusionne les sous-listes triées.

💡 Astuce mémo

Cas de base atteint → appels récursifs arrêtés

📖 9. Arbres binaires et parcours

🔑 Notions clés & Définitions

• Arbre binaire : Soit vide, soit constitué d'une racine et de deux sous-arbres binaires disjoints, gauche et droit.

📝 Points essentiels

• La profondeur d'un nœud est sa distance à la racine, dont la profondeur vaut 0, et la hauteur d'un arbre est la profondeur maximale de ses nœuds.

📌 Le parcours préfixe visite la racine puis les sous-arbres gauche et droit selon NGD, le parcours infixe suit GND et le parcours suffixe suit GDN.

• Le parcours en largeur explore un arbre niveau par niveau, tandis que le parcours en profondeur explore complètement une branche avant de passer à la suivante.

💡 Astuce mémo

Préfixe NGD, infixe GND, suffixe GDN

📖 10. Arbres spécialisés et recherche

🔑 Notions clés & Définitions

• Arbre binaire de recherche : Place les valeurs inférieures dans le sous-arbre gauche et les valeurs supérieures dans le sous-arbre droit, sans nœuds égaux.
• Arbre maximier : Arbre parfait dans lequel chaque nœud a une valeur supérieure à celle de ses deux fils.

★ À maîtriser

• Pour rechercher une valeur dans un arbre binaire de recherche, on la compare à la racine puis on poursuit dans le sous-arbre droit si elle est supérieure ou dans le sous-arbre gauche si elle est inférieure.

Compléments

• Dans la représentation linéaire d'un arbre parfait, le fils gauche du nœud d'indice i est à l'indice 2i+1 et le fils droit à l'indice 2i+2.

💡 Astuce mémo

Maximier : tamiser, échanger, réduire

📖 11. Complexité algorithmique

🔑 Notions clés & Définitions

• Complexité algorithmique : Estime le nombre d'opérations de base nécessaires selon la taille des données d'entrée afin d'évaluer le coût d'exécution d'un algorithme.

📝 Points essentiels

• Les classes usuelles comprennent $\Theta(1)$ constante, $\Theta(\log(n))$ logarithmique, $\Theta(n)$ linéaire, $\Theta(n\log(n))$ quasi-linéaire et $\Theta(n^2)$ quadratique.

📌 Pour obtenir une notation O, on ignore les constantes multiplicatives et additives et on conserve seulement le terme dominant.

• Une recherche dichotomique sur une liste triée a une complexité $\Theta(\log_2(n))$ car le nombre d'éléments restants est divisé par deux à chaque étape.

💡 Astuce mémo

Taille de l’entrée → opérations exécutées → classe de complexité

📖 12. Graphes et parcours

🔑 Notions clés & Définitions

• Graphe non orienté : Couple (X,E) où X est un ensemble de sommets et E un ensemble de parties à deux éléments de X appelées arêtes.
• Graphe orienté : Couple (V,A) où V est un ensemble de sommets et A un ensemble d'arcs, chaque arc étant un couple de sommets.

📝 Points essentiels

📐 Formule - Dans un graphe non orienté, la somme des degrés des sommets vaut $S=2a$, où a est le nombre d'arêtes.

📌 Un graphe connexe possède une chaîne entre toute paire de sommets, et il admet un cycle eulérien si et seulement si tous ses sommets sont de degré pair.

• Le parcours en profondeur DFS marque un sommet, visite récursivement chaque voisin non visité, puis recommence depuis un nouveau sommet si des sommets restent non visités.

• Le parcours en largeur BFS utilise une file pour visiter d'abord les sommets à une distance donnée, puis ceux du niveau suivant.

💡 Astuce mémo

DFS explore une branche, BFS explore un niveau

📊 Tableaux de synthèse

Structures linéaires

Parcours des structures