Scheda di revisione: Algorithmique et structures de données

📋 Plan du Cours

1. Fondations et correction algorithmique
2. Complexité et choix des structures
3. Tableaux, listes et structures linéaires
4. Hachage, recherches et tris
5. Récursivité et programmation dynamique
6. Arbres et structures hiérarchiques
7. Graphes et parcours
8. Chemins, arbres couvrants et DSU
9. Paradigmes et techniques de résolution

📖 1. Fondations et correction algorithmique

🔑 Notions clés & Définitions

• Algorithme : Une suite finie, ordonnée et non ambiguë d’instructions qui transforme des entrées en sorties.
• Invariant : Une propriété qui reste vraie à chaque itération d’une boucle.
• Correction totale : Combine la correction partielle, garantie par les préconditions, postconditions et invariants, avec la terminaison.

📝 Points essentiels

⚡ Une affectation comme x ← x + 1 modifie la valeur de x et ne constitue pas une égalité mathématique.

⚡ Une boucle tant que peut ne jamais s’exécuter, tandis qu’une boucle répéter...jusqu’à s’exécute au moins une fois.

💡 Astuce mémo

Précondition → invariant → terminaison → postcondition

📖 2. Complexité et choix des structures

🔑 Notions clés & Définitions

• Complexité amortie : Garantit un coût moyen sur une séquence d’opérations, comme append en O(1) amorti pour un tableau dynamique.

📝 Points essentiels

★ À maîtriser

🧮 Formule — L’ordre croissant usuel des complexités est O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ) puis O(n!).

⚡ O(g) est une borne supérieure, Ω(g) une borne inférieure et Θ(g) une croissance précise à constante près.

Compléments

🧮 Formule — Les récurrences T(n)=T(n−1)+O(1), T(n)=T(n/2)+O(1), T(n)=2T(n/2)+O(n) et T(n)=2T(n−1)+O(1) donnent respectivement O(n), O(log n), O(n log n) et O(2ⁿ).

⚡ Un TAD décrit les opérations et leur comportement, tandis qu’une structure de données est une implémentation concrète de ce TAD.

💡 Astuce mémo

Coût dominant, opération critique

📖 3. Tableaux, listes et structures linéaires

📝 Points essentiels

★ À maîtriser

• Un tableau est contigu, indexé de 0 à n−1, et permet l’accès A[i] en O(1).

🧮 Formule — Dans un tableau dynamique, l’ajout en fin coûte O(1) amorti, tandis qu’une insertion ou suppression au milieu coûte O(n) à cause des décalages.

🧮 Formule — Avec les préfixes cumulés P[0]=0 et P[i+1]=P[i]+A[i], la somme A[l..r] vaut P[r+1]−P[l] et se calcule en O(1) après un prétraitement O(n).

⚡ Une liste chaînée permet l’insertion après un nœud connu en O(1), mais l’accès au iᵉ nœud et la recherche coûtent O(n).

⚡ Une pile traite le dernier élément arrivé en premier, une file le premier arrivé en premier et une deque permet les opérations aux deux extrémités.

Compléments

🔄 Processus — La détection de cycle de Floyd utilise un pointeur lent et un pointeur rapide en O(n) temps et O(1) mémoire.

💡 Astuce mémo

Indice, lien, extrémité

📖 4. Hachage, recherches et tris

🔑 Notions clés & Définitions

• Collision de hachage : Une collision survient lorsque plusieurs clés produisent le même indice de hachage et se gère notamment par chaînage ou adressage ouvert.
• Tri stable : Conserve l’ordre relatif des éléments ayant des clés égales.

📝 Points essentiels

★ À maîtriser

⚡ Des clés égales produisent le même hash, mais deux hashes égaux n’impliquent pas que les clés soient égales.

⚡ La recherche linéaire fonctionne sur des données triées ou non en O(n) dans le pire cas, tandis que la recherche binaire exige un tableau trié et un accès direct pour fonctionner en O(log n).

⚡ Le tri par insertion est adapté aux petites données ou aux séquences presque triées, le tri fusion garantit O(n log n) et la stabilité, tandis que le tri rapide a un pire cas O(n²).

Compléments

🧮 Formule — Le facteur de charge d’une table de hachage est α=n/m, où n est le nombre de clés et m la capacité.

🧮 Formule — Le tri par comptage coûte O(n+k) et convient lorsque l’univers des valeurs, de taille k, reste petit par rapport à n.

💡 Astuce mémo

Clé, ordre, stabilité

📖 5. Récursivité et programmation dynamique

🔑 Notions clés & Définitions

• Récursivité : Une fonction récursive résout un problème en appelant une version plus petite de ce problème et doit posséder un cas de base ainsi qu’une progression vers ce cas.
• Mémoïsation : Une approche top-down qui mémorise les résultats des sous-problèmes déjà calculés.
• Programmation dynamique : Exploite des sous-problèmes chevauchants et une sous-structure optimale en définissant des états, des transitions et des cas de base.

📝 Points essentiels

• Chaque appel récursif conserve ses paramètres, ses variables locales et son adresse de retour, ce qui donne une mémoire O(profondeur).

🔄 Processus — Une recette de programmation dynamique consiste à définir l’état minimal, la transition, les cas de base, le mode de calcul, l’ordre de calcul et éventuellement la reconstruction.

💡 Astuce mémo

Cas de base → sous-problèmes

📖 6. Arbres et structures hiérarchiques

🔑 Notions clés & Définitions

• Arbre : Un graphe connexe sans cycle et possède n−1 arêtes lorsqu’il contient n nœuds.
• ABR : Dans un arbre binaire de recherche, les clés du sous-arbre gauche sont inférieures à la clé du nœud et celles du sous-arbre droit lui sont supérieures selon la convention choisie.

📝 Points essentiels

★ À maîtriser

⚡ La profondeur est la distance entre la racine et un nœud, tandis que la hauteur est le plus long chemin d’un nœud vers une feuille.

🧮 Formule — Dans un ABR, la recherche, l’insertion et la suppression coûtent O(h), soit O(log n) si l’arbre est équilibré et O(n) s’il est dégénéré.

Compléments

• Pour A(B(D,E),C(F,G)), les parcours préordre, infixe, postordre et largeur sont respectivement ABDECFG, DBEACFG, DEBFGCA et ABCDEFG.

⚡ Un trie traite un mot de longueur L en O(L), un segment tree traite une requête ou une mise à jour d’intervalle en O(log n), et un B+ arbre favorise les requêtes par intervalle sur disque.

💡 Astuce mémo

Racine → branches → feuilles

📖 7. Graphes et parcours

🔑 Notions clés & Définitions

• Graphe : G=(V,E) contient des sommets et des arêtes ou arcs, et peut être orienté ou non orienté, pondéré ou non pondéré.

📝 Points essentiels

★ À maîtriser

⚡ Une matrice d’adjacence utilise O(V²) mémoire et teste une arête en O(1), tandis qu’une liste d’adjacence utilise O(V+E) mémoire et convient mieux aux graphes clairsemés.

⚡ BFS utilise une file et explore par niveaux, alors que DFS utilise une pile ou la récursion et explore en profondeur.

🧮 Formule — Avec une liste d’adjacence, BFS et DFS coûtent O(V+E) en temps et O(V) en mémoire.

📌 Un tri topologique n’existe que pour un DAG, et l’algorithme de Kahn utilise les degrés entrants et une file.

Compléments

🧮 Formule — Dans un graphe non orienté, la somme des degrés vaut 2E, tandis que dans un graphe orienté la somme des degrés entrants et celle des degrés sortants valent chacune E.

💡 Astuce mémo

BFS en largeur, DFS en profondeur

📖 8. Chemins, arbres couvrants et DSU

🔑 Notions clés & Définitions

• Relaxation : Relâcher (u,v,w) consiste à mettre à jour d[v] et le prédécesseur si d[u]+w<d[v].
• Arbre couvrant minimal : Relie tous les sommets d’un graphe non orienté connexe avec V−1 arêtes et un poids total minimal.

📝 Points essentiels

★ À maîtriser

⚡ BFS convient aux arêtes de même coût, Dijkstra aux poids non négatifs, Bellman-Ford autorise les poids négatifs et détecte les cycles négatifs atteignables.

🧮 Formule — Les complexités de Dijkstra avec tas, Bellman-Ford et Floyd-Warshall sont respectivement O((V+E)log V), O(VE) et O(V³), avec O(V²) mémoire pour Floyd-Warshall.

⚡ Prim ajoute à un arbre l’arête sortante la moins chère, tandis que Kruskal trie les arêtes et ajoute celles qui ne créent pas de cycle grâce à Union-Find.

Compléments

🧮 Formule — Union-Find fournit find et union, et la compression de chemin combinée au rang donne un coût amorti O(α(n)).

💡 Astuce mémo

Relaxer ou connecter

📖 9. Paradigmes et techniques de résolution

🔑 Notions clés & Définitions

• Backtracking : Construit un choix, explore récursivement puis l’annule lorsqu’une impasse est atteinte.

📝 Points essentiels

★ À maîtriser

⚡ Le diviser-régner divise puis combine, le glouton choisit localement de manière irréversible avec une preuve nécessaire, et la programmation dynamique réutilise des sous-solutions.

🧮 Formule — KMP coûte O(n+m), Kadane O(n), LCS et la distance d’édition O(nm), LIS O(n log n) et le sac à dos 0/1 O(nC).

⚡ Un tas de taille k trouve un top-k en O(n log k), tandis que Quickselect trouve le kᵉ élément en O(n) moyen et O(n²) dans le pire cas sans trier toute la collection.

Compléments

⚡ Deux pointeurs, fenêtre glissante, préfixes cumulés, pointeur lent/rapide, pile monotone, recherche sur réponse, sweep line, masques de bits et meet-in-the-middle sont des techniques adaptées respectivement aux tableaux, intervalles, agrégats, cycles, prochains maxima, prédicats monotones, événements, petits ensembles d’états et divisions en deux moitiés.

💡 Astuce mémo

Diviser, choisir, mémoriser

📊 Tableaux de synthèse

Structures et opérations dominantes

Besoin	Structure	Coût clé
Accès par indice	Tableau	O(1)
Insertion locale	Liste chaînée	O(1) si le nœud est connu
Dernier arrivé	Pile	O(1) aux extrémités
Premier arrivé	File	O(1) aux extrémités
Clé-valeur	Hachage	O(1) moyen
Minimum répété	Tas	O(log n)

⚠️ Pièges & confusions fréquents

1. Affectation et égalité mathématique ne sont pas interchangeables.
2. Big-O ne représente ni un temps exact ni nécessairement le pire cas.
3. L’indice A[n] est hors limites pour un tableau de taille n.
4. Une collision est normale et ne constitue pas nécessairement une erreur.
5. Sans progression vers le cas de base, la récursion peut être infinie.
6. Un arbre n’est pas un graphe quelconque sans contrainte de connexité.
7. La représentation choisie modifie les coûts de mémoire et de parcours.