| 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
|
| 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 redblobgames
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 à 16h |
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
|