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

mardi 8 oct. 2019
à 14h - 16h

CM5 : Parcours en largeur

mardi 15 oct. 2019
à 13h30 - 15h30
(avant séminaire #3)
Cours mais PAS DE TD (projet programmation) !

CM6 : Algorithmes gloutons

  • Rappels : concept, rendus de monnaie, etc.
  • Arbre couvrant minimal.
  • Algorithme de Kruskal : exemple et correction.
  • Union find : version simple et compression de chemins.
  • Liens : Kruskal, Kruskal Minimum Spanning Tree.
mardi 22 oct. 2019 PAS DE COURS (projet programmation) mais TD jeudi 24 oct. !
DM déjà distribué à rendre 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
DM à rendre !

CM7 : Programmation dynamique

  • Exemple du problème de la plus longue sous-suite croissante 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,
    • décorer l'algorithme pour construire une solution au problème.
  • Algorithme de Bellmann-Ford.
  • Algorithme de Floyd-Warshall.
  • Sac à dos avec et sans répétition.
  • Mémoïzation expliquée avec le sac avec répétition. Mémoïzation implémentée en Python et OCaml.
  • Explication de l'art de trouver des sous-problèmes avec sac à dos sans répétition.
  • Liens : Bellman Ford's Shortest Path, Floyd Warshall's Shortest Path, Floyd, Knapsack problem.
mardi 12 nov. 2019
à 13h30 - 15h30
(avant séminaire #5

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 : TODO.
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 du chocolatier.
  • 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.
  • Réduction à la programmation linéaire : plus court chemin, flots, flot de coût minimum, sac à dos.
  • Conversion de programme linéaire : problèmes standards et canoniques.
  • Algorithme du simplexe : exécution sur l'exemple du chocolatier.
  • 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.
  • Correction et terminaison de l'algo du simplexe admise.
  • Liens : TODO.
mardi 3 déc. 2019
à 14h - 16h
Dernier cours

CM10 : Algorithmes de recherche de solutions

  • Exemple : 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
? ? déc. 2019 – ??h (2h)

Examen terminal

Annales



Références

Autre cours sur internet

Autre liens sur internet