ALGO1 : Introduction à l'Algorithmique

Magistère d'Informatique de Rennes - ENS Rennes - Année 2019/2020

Organisation

Liens

Calendrier et détails des cours

mardi 10 sept. 2019
à 14h - 16h

CM1 : Introduction + File de priorité

mardi 17 sept. 2019
à 13h30 - 15h30
(avant séminaire #1)

CM2 : Structures de données pour un ensemble

mardi 24 sept. 2019
à 14h - 16h

CM3 : Diviser pour régner

mardi 1 oct. 2019
à 13h30 - 15h30
(avant séminaire #2)

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,
mardi 8 oct. 2019
à 14h - 16h

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.
mardi 15 oct. 2019
à 13h30 - 15h30
(avant séminaire #3)
Cours mais PAS DE TD (projet programmation) !

CM6 : Algorithmes gloutons

mardi 22 oct. 2019 PAS DE COURS (projet programmation) mais TD jeudi 24 oct. !
DM déjà distribué (sujet en PDF). À rendre le 12 novembre, après les vacances de Toussaint !
mardi 29 oct. 2019 PAS DE COURS ni de TD (vacances)
mardi 5 nov. 2019
à 13h30 - 15h30
(avant séminaire #4

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.
mardi 12 nov. 2019
à 13h30 - 15h30
(avant séminaire #5
DM à rendre (sujet en PDF) le 12 novembre, avant 8h du matin, par courriel à Lilian Besson et Raphaël Truffet.

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.
mardi 19 nov. 2019 PAS DE COURS mais TD jeudi 21 nov. !
mardi 26 nov. 2019
à 13h30 - 15h30
(avant séminaire #6
PAS DE TD

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),
mardi 3 déc. 2019
à 14h - 16h
Dernier cours : donné par Raphaël Truffet

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.
mardi 10 déc. 2019 PLUS DE COURS ni DE TD
Semaine du 16-20 déc. 2019 – jeudi 19 16h30-18h30 (2h)

Examen terminal

Annales



Références

Autre cours sur internet

Autre liens sur internet