Algorithmique avancée

École Centrale-Supélec - parcours Informatique et Systèmes Avancés - Tronc commun - cours IS3005AD

intervenants: Christoph Dürr, Nguyễn Kim Thắng

Livres

[cote de la bibliothèque]

Plan du cours

Ce plan peut être sujet à des ajustements. Toutes les séances sont de 8h30 à 11h45, dans l’amphi F209 pour le cours, puis en F209 et F207 pour les petites classes.

1. (Vendredi 14 sep 2018) — Diviser pour régner et algorithmes gloutons

cours 11:00-12:30

Introduction. Diviser pour régner: Compter le nombre d’inversions en O(n log n). Glouton: Ordonnancement d’intervalles. Ordonnancer sur une machine pour minimiser le temps d’attente pondéré.

1. (Lundi 17 sep 2018) — Diviser pour régner et algorithmes gloutons

exercices. 10:15-11:45

Exercice des cartes bancaires. Placement d’antennes. Problème de cache.

2. (Mercredi 19 sep 2018) - Programmation dynamique

Plus long/court chemin dans un graphe orienté acyclique. Plus longue sous séquence commune. Multiplication d’une séquence de matrices. Voyageur de commerce.

exercices. corrigés Arbre binaire de recherche optimal. Distance d’édition de Levenshtein. Corriger un mot bien parenthésé. Parenthéser une expression booléenne. Partage équitable. Rendu de monnaie.

3. (Lundi 24 sep 2018) - Algorithme par balayage

Plus longue sous séquence croissante. Plus grand rectangle sous un histogramme.

exercices. corrigésPlus grand carré dans une grille. Plus long chemin dans un arbre. Jeux avec des pièces alignées. Pavage par des dominos.

4. (Lundi 1 oct 2018) - Flots et coupes 1

Théorème max-flot min-coupe. Algorithme de Ford Fulkerson. Amélioration de Edmonds-Karp.

Problèmes réduisant au problème du flot maximum.

5. (Lundi 8 oct 2018) - Flots et coupes 2

Algorithme de Dinic ou de Goldberg et Tarjan. Couverture par sommets dans les graphes bipartis (Bipartite Vertex Cover).

Problèmes réduisant au problème du couplage.

Annonce devoir maison.

6. (Lundi 15 oct 2018) - NP-complétude

Les classes P, NP, APX. Preuves de NP-complétude. Réductions. Exemples: sac à dos, partition, couplage numérique en 3 dimensions. Non approximabilité de la clique maximale, ensemble indépendant.

7. (Vendredi 19 oct 2018) - Algorithmes d’approximations

2-approximation pour équilibrage de charge. Sac à dos. Algorithme de Christofides pour le problème de voyageur de commerce.

2-approximation pour ordonnancer sur une machine pour minimiser le temps d’attente pondéré avec ordre de précédence. Couverture par sommets (Vertex Cover). Couverture des ensembles (Set Cover). (evt. Bin Packing)

8. (Lundi 22 oct 2018) - Algorithmes randomisés

Rappel probabilités. Coupe minimale dans un graphe. Collecteur de coupons.

Boules dans des urnes. Quicksort. (evt. Uwe Schoening pour 2-SAT)

-1. (Lundi 22 novembre 2018) - Examen

de 13:45 à 16:45.

Toutes les notes sont autorisées. Mais pas de livres. Ni de calculatrices.