ALGO1 : Introduction à l'Algorithmique

CM1 : Introduction + File de priorité

• Organisation du cours : dates, objectifs, intervenants, contacts, évaluation, suite (→ ALGO2).
• Algorithmes. Type abstrait (interface) VS structure de données (implémentation).
• Structures linéaires : tableaux, liste chaînée, file, liste doublement chaînée.
• File de priorité. Implémentations naïves avec des structures linéaires.
• Implémentation avec un tas. Bonus (à voir vous-même) : Construction d'un tas en temps linéaire.
• Problème du tri. Tri par file naïve : tri sélection ou insertion (sous optimal en $\mathcal{O}(n^2)$). Tri par tas : variante du tri sélection mais utilisant un tas.
• (traité en CM2) Preuve de complexité en $\mathcal{O}(n \log(n))$. Optimalité du tri par tas (cf. borne inf. en $\Theta(n \log(n))$ pour les tris par comparison).
• Liens : planches CM1, code CM1, Queue Array, Linked List, Listes chaînées (2ème version), Heap, Heap Sort, Comparison Sort.

CM2 : Structures de données pour un ensemble

• Discussion autour des tableaux / vecteurs de bits.
• Petits ensembles d'entiers dans $\{0,\dots,31\}$ représentés par un seul entier 32 bits (exemple en OCaml, doc en Java, doc en C++).
• Table de hachage. Exemples de fonctions de hachage. (Démonstration visuelle ?).
• Traité en TD2 : Arbres binaires de recherche (ABR) : définitions, recherche d'un élément, ajout et suppression. Notion de structure persistante. Fiche sur les ABR.
• À travailler par vous même (avec les feuilles) : Équilibrage d'ABR, B-arbres. Fiche sur les B-arbres.
• Liens : pas de planches (au tableau), code CM2 (contient tout). Visualisations : Différentes fonctions de hachage, autre explication, Binary Search Tree (BST), BST (2ème version), BST (3ème version), B-Tree (B-arbres).

CM3 : Diviser pour régner

• Théorème fondamental / "master theorem" (preuve en PDF si besoin).
• Rappels & applications : recherche dans un tableau trié, tri fusion, enveloppe convexe en 2D (démo)…
• Multiplication de grands nombres entiers : algorithme de Gauss-Karatsuba. (Démonstration en ligne)
• Multiplication de matrices dans $\mathbb{D}^{n \times n}$ : algorithme de Strassen (Straßen).
• Traité en TD3 : Transformation de Fourier rapide (FFT).
• (à chercher vous-même si très curieux) Multiplication de polynômes. Passage de la représentation par coefficients et par valeurs via FFT et FFT inverse (dans ce poly).
• Liens : code CM3 (tout), note de cours sur la FFT (Jeff Erikson), Karatsuba implémenté en Python et R, Straßen implémenté en Python/C++/Java.

CM4 : Graphes, et parcours en profondeur

• Vocabulaire sur les graphes : sommets, arêtes, voisins, degrés, arbre, etc.
• Implémentation des graphes : matrice d'adjacence ou listes d'adjacence. Graphes "creux".
• Parcours en profondeur : algorithme, lemme des sommets non vus, complexité linéaire.
• À explorer (en profondeur !) par vous même : Tri topologique, composantes fortement connexes : algorithme de Kosaraju.
• Liens : code CM4 (tout), et des visualisations : Deep First Search (DFS), Topological Sort with DFS, Connected Component,

CM5 : Parcours en largeur

• Algorithme de parcours en largeur : distance des plus courts chemins.
• Adaptation pour un graphe pondéré positivement : algorithme de Dijkstra.
• Différents Dijkstra : naïvement avec un tableau, puis une file de priorité min non mutable, puis mutable. On évoque les tas de Fibonacci sans les prouver.
• Correction de l'algorithme de Dijkstra.
• À travailler par vous même Algorithme A*. (Démo sur le site d'un tutoriel à IJCAI-ECAI 2018, voir la belle démo), notamment avec ce mini-cours.
• Liens : code CM5 (rapide), (Dijkstra en C++), et des visualisations : Breath First Search, Dijkstra.

CM6 : Algorithmes gloutons

• Rappels : concept, rendus de monnaie, etc.
• Arbre couvrant minimal. (Application à la génération de labyrinthes).
• Algorithme de Kruskal : exemple et correction.
• Union find : version simple et compression de chemins.
• Liens : code CM6 (rapide), Kruskal, Kruskal Minimum Spanning Tree.

CM7 : Programmation dynamique

• Exemple du problème de la multiplication de chaînes de matrices pour expliquer :
  • qu'il faut se concentrer sur la quantité à optimiser,
  • définir des sous-problèmes,
  • trouver une relation par récurrence,
  • écrire un algorithme itératif, et pas récursif, qui construise la solution dans le bon ordre
  • décorer l'algorithme pour construire une solution au problème (en plus de trouver la valeur optimale de la quantité à optimiser).
• Plus longue sous-suite croissante.
• Plus longue sous-séquence commune à deux chaînes de caractères.
• Calculs des plus courts chemins dans un graphe orienté valué : algorithmes de Bellmann-Ford, de Floyd-Warshall.
• Pour les curieux-es : regardez de votre côté le lien entre algorithme de Floyd-Warshall et multiplication de matrice dans le sous-anneau $(\mathbb{R}, \min, +)$.
• Pour les curieux-es : regardez de votre côté les problèmes du sac à dos avec et sans répétition.
• Bonus : Mémoïzation = transformation d'un algorithme récursif naïf en récursif optimisé par programmation dynamique. Mémoïzation implémentée en Python et OCaml, exemples avec les calculs des séquences de Fibonnaci, de la factorielle.
• Liens : code CM7, Bellman Ford's Shortest Path, Floyd Warshall's Shortest Path, Floyd, Knapsack problem.

CM8 : Flots

• Problème du flot maximal.
• Algorithme de Ford-Fulkerson.
• Correction de Ford-Fulkerson : flot maximal = coupe minimale.
• Réduction : exemple du couplage maximal.
• Liens : code CM8 (rapide), Planches pour ce cours.

CM9 : Programmation linéaire

• Introduction avec l'exemple de l'artisan ébéniste.
• (pour les curieux-euses) Résolution avec l'outil lp_solve sous GNU/Linux, et scipy.optimize.linprog avec Python.
• Discussion sur programmation linéaire réelle, entière, mixte.
• Conversion de programme linéaire : problèmes sous formes standards et canoniques.
• Algorithme du simplexe : exécution sur l'exemple de l'artisan ébéniste.
• Discussions : espace des solutions non borné. Prétraitement pour se ramener à un problème canonique avec solution basique s'il y a une solution, ou détecter que l'espace des solutions est vide.
• Réduction à la programmation linéaire : plus court chemin, flots, flot de coût minimum, sac à dos.
• Bonus : correction et terminaison (partielle) de l'algo du simplexe admise.
• Liens : code CM9 (rapide),

CM10 : Algorithmes de recherche de solutions

• Exemples : sac à dos, voyageur de commerce, SAT.
• "Backtracking".
• Idée générale du "backjumping".
• Réduction à SAT : exemple du jeu Picross (démonstration), branch and bound illustré sur sac à dos.
• "Local search" pour voyageur de commerce, pour dessiner des diagrammes d'Euler (démonstration).
• Liens : Hamiltonean cycles.

Examen terminal

• Indications.

Annales

• Regardez la page du cours ALGO1 au département de maths : Examen 2017, Examen 2018.