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

Plan du cours (provisoire)

Toutes les séances sont de 8h30 à 11h45

1. (Mercredi 19 sep 2018) — Introduction

Introduction. Techniques algorithmiques: diviser pour conquérir, glouton, programmation dynamique. Le master théorème illustré sur le problème de la paire de points la plus proche. Compter le nombre d’inversions en O(n log n).

2. (Vendredi 21 sep 2018) - Algorithmes gloutons

Les règles bleu et rouge pour le problème de l’arbre de couverture minimale. Ordonnancement d’intervalles. Ordonnancer sur une machine pour minimiser le temps d’attente pondéré. Codes de Huffman.

3. (Lundi 24 sep 2018) - Programmation dynamique

Plus long/court chemin dans un graphe orienté acyclique. Plus longue sous séquence commune. Distance d’édition de Levenshtein. Multiplication d’une séquence de matrices. Arbre binaire de recherche optimisé pour fréquences données. Propriété de Monge. Plus longue sous séquence croissante.

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

Théorème max-flot min-coupe. Algorithme de Ford Fulkerson. Amélioration de Edmonds-Karp. Couplage cardinalité maximale bi-parti, couverture par sommets. Théorème de Dilworth (réservation de taxis). Problèmes réduisant au problème du flot maximum.

Annonce devoir maison.

5. (Lundi 8 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.

6. (Lundi 15 oct 2018) - Algorithmes d’approximations

2-approximation pour ordonnancer sur une machine pour minimiser le temps d’attente pondéré avec ordre de précédence. Sac à dos. Algorithme de Christofides pour le problème de voyageur de commerce.

7. (Vendredi 19 oct 2018) - Algorithmes randomisé

Coupe minimale dans un graphe. Collecteur de coupons. Boules dans des urnes. Quicksort. (Uwe Schoening pour 2-SAT)

8. (Lundi 22 oct 2018) - Rappels et ouverture

Problème des experts.

9. (Lundi 29 oct 2018)

Examen