ALGO1 : Introduction à l'algorithmique

Magistère de Mathématiques de Rennes - ENS Rennes - Année 2019/2020

Intervenants

Cours : François Schwarzentruber
Travaux dirigés : Léo Henry
DM (pour les élèves du département mathématiques) : modification de pages Wikipedia
mardi 3 septembre 2019 à 8h

Introduction

Algorithme de Gale et Shapley. Terminaison. Variant. Correction. Invariant. Algorithme sous-spécifié (plusieurs exécutions). Démonstration que ce qui proposent sont favorisés.

Exposé de Judicaël Courant sur les mariages stages et les affectations des lycées dans le supérieur.
mardi 10 septembre 2019 à 8h

File de priorité

Type abstrait (interface) VS structure de données (implémentation). File. Liste doublement chaînée. File de priorité. Implémentation naïve. Implémentation avec un tas. Construction d'un tas en temps linéaire. Problème du tri. Tri par tas : variante du tri sélection mais utilisant un tas. Type abstrait : file de priorité. Optimalité du tri par tas.
mardi 17 septembre 2019 à 8h

Structures de données pour un ensemble

Arbres binaires de recherche : définitions, recherche d'un élément, ajout et suppression. Notion de structure persistante. Fiche sur les ABR
Equilibrage : B-arbres. Fiche sur les B-arbres
Vecteurs de bits. Table de hachage. Exemples de fonctions de hachage. Démonstration
mardi 24 septembre 2019 PAS DE COURS
mardi 1 octobre 2019 à 8h

Diviser pour régner

Théorème fondamental
Multiplication de nombres : algorithme de Karatsuba
Multiplication de matrices : algorithme de Strassen
Transformation de Fourier rapide
Multiplication de polynômes. Passage de la représentation par coefficients et par valeurs via FFT et FFT inverse.
mardi 8 octobre 2019 à 8h

Parcours en profondeur

Implémentation des graphes : matrice d'adjacence ou listes d'adjacence.

Parcours en profondeur : algorithme, lemme des sommets non vus, complexité linéaire, pre/post, classification des arcs
Tri topologique : magnets pour habiller le savant Cosinus
Composantes fortement connexes : algorithme de Kosaraju
(correction débutée)
mardi 15 octobre 2019 à 8h Correction de l'algorithme de Kosaraju

Parcours en largeur

Algorithme de parcours en largeur : distance des plus courts chemins
Correction admise
Adaptation pour un graphe pondéré positivement : algorithme de Dijkstra
Correction de l'algorithme de Dijkstra
Algorithme A*
Implémentation de Dijkstra en C++
Demo sur le site d'un tutorial à IJCAI-ECAI 2018
mardi 22 octobre 2019 PAS DE COURS
mardi 29 octobre 2019 PAS DE COURS (vacances)
mardi 5 novembre 2019 à 8h

Algorithmes gloutons

Arbre couvrant minimal
Algorithme de Kruskal : exemple et correction
Union find : version simple et compression de chemins
Magnets qui illustrent la compression de chemins
mardi 12 novembre 2019 à 8h

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
Explication de l'art de trouver des sous-problèmes avec sac à dos sans répétition
mardi 19 novembre 2019 PAS DE COURS
mardi 26 novembre 2019 à 8h

Flots

Problème du flot maximal
Algorithme de Ford-Fulkerson
Correction de Ford-Fulkerson : flot maximal = coupe minimale
Réduction : exemple du couplage maximal.
mardi 26 novembre 2019 à 16h

Programmation linéaire

Introduction avec l'exemple du chocolatier. Résolution avec l'outil lp_solve sous linux
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.
mardi 3 décembre 2019 à 8h

Algorithme 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)
lundi ??/12/2019 – ??h TERMINAL : sujet


Examens des années précédentes

Références

Autre cours sur internet