Algorithmique 2
Passer de « comment écrire un algorithme » à « quelle structure choisir » : récursivité, diviser pour régner, listes, arbres, graphes.
Commencer : Principe et mécanisme de la récursivité- C1Non commencé
Récursivité
2 leçons · 12 hObjectif. Écrire une fonction qui s'appelle elle-même, prouver qu'elle s'arrête, et surtout savoir dérouler sa pile d'appels — sans quoi tout le reste du semestre reste opaque.
- Principe et mécanisme de la récursivitéVous êtes iciCas de base et cas récursif, déroulé de la pile d'exécution, preuve de terminaison ; récursivité simple, multiple, croisée et terminale ; coût mémoire des appels.7 h · en cours
- Récursif contre itératifTransformer une boucle en récursion et l'inverse ; quand la récursion clarifie et quand elle coûte ; les appels redondants de Fibonacci naïf.5 h · non commencée
- C2Non commencé
Diviser pour régner
2 leçons · 12 hObjectif. Couper un problème en deux, résoudre les moitiés, recoller — et savoir calculer ce que cette stratégie coûte réellement.
- Tris efficacesTri fusion — découpe, fusion, stabilité — et tri rapide — partitionnement, choix du pivot, pire cas ; comparaison expérimentale avec les tris élémentaires.8 h · non commencée
- Analyse des algorithmes récursifsÉquations de récurrence, résolution par déroulement et par arbre d'appels ; pourquoi n log n est la borne des tris par comparaison ; dichotomie récursive.4 h · non commencée
- C3Non commencé
Structures de données linéaires
2 leçons · 12 hObjectif. Cesser de tout mettre dans un tableau : choisir une structure d'après les opérations qu'on va lui demander, et payer le bon prix.
- Listes chaînéesCellule et chaînage, listes simplement et doublement chaînées, insertion, suppression, parcours ; coûts comparés au tableau ; listes circulaires.7 h · non commencée
- Piles et filesLIFO et FIFO, implémentation par tableau et par liste ; évaluation d'expressions, parenthésage, pile d'appels, files d'attente.5 h · non commencée
- C4Non commencé
Arbres
2 leçons · 11 hObjectif. Passer du linéaire au hiérarchique, et obtenir en log n ce qui coûtait n — à condition que l'arbre reste équilibré.
- Arbres binairesRacine, nœud, feuille, hauteur ; représentations ; parcours préfixe, infixe, suffixe et en largeur ; arbre d'expression.6 h · non commencée
- Arbres de recherche et tasABR : insertion, recherche, suppression, dégénérescence et équilibrage en survol ; tas binaire, file de priorité et tri par tas.5 h · non commencée
- C5Non commencé
Graphes et paradigmes
2 leçons · 8 hObjectif. Modéliser ce qui n'est ni linéaire ni hiérarchique, puis prendre du recul sur trois grandes manières de chercher une solution.
- GraphesMatrice et listes d'adjacence, parcours en profondeur et en largeur, connexité, détection de cycle, plus court chemin en nombre d'arêtes, Dijkstra en introduction.5 h · non commencée
- Paradigmes algorithmiquesAlgorithme glouton et rendu de monnaie, retour sur trace, et première approche de la programmation dynamique par mémoïsation.3 h · non commencée