ALGO2 : Algorithmique avancée

Licence 3 d'informatique (parcours recherche) et magistère de Mathématiques de Rennes - ENS Rennes - Année 2021/2022

Intervenants

Cours : François Schwarzentruber
TD : Nicolas Waldburger

Plan du cours

Séance 1 : Programmation linéaire réelle

Programmation liénaire réelle dans P (admis). Programme canonique. Programme équationnel. Tableau. Solution basique. Variables dans la base et hors base. Algorithme du simplexe. Terminaison avec règle de Bland. Prétraitement pour obtenir un tableau avec solution basique. Programmation linéaire réelle

Séance 2 : Dualité en programmation linéaire (séance à diviser en deux la prochaine année)

Motivation pour certificat. Programme dual. Illustration avec le problème du calcul d'un plus court chemin. Théorème de dualité faible et forte. Coefficients magiques. Théorème des écarts complémentaires. Interprétration physique de la dualité. Matrices totalement unimodulaires. Théorème de König. Théorème min-max de Von Neumann dans les jeux à sommes nulles. Dualité en programmation linéaire

Séance 3 : Algorithmes d'approximation

Algorithmes PTAS, FPTAS. Classes de complexité PTA, FPTA, APX. Couverture de sommets. Couverture de sommets pondérés et relaxation linéaire. Innapproximalité du problème de voyageur de commerce (TSP). TSP avec inégalité triangulaire. Algorithme de Christofides. Algorithmes d'approximation

Séance 4 : Algorithmes d'approximation

Approximation par rounding puis programmation dynamique. Sac à dos. TSP euclidien. Algo et démonstration de correction de TSP euclidien

Séance 5 : Algorithmes probabilistes

Tri rapide randomisé. Algorithme de Freivalds. Algorithme de Karger. Classes de complexité probabilistes Algorithmes probabilistes Skip lists - Listes à sauts

Séance 6 : Méthode probabiliste et dérandomisation

Maxcut. Existence d'une solution, prouvée via un argument probabiliste. Dérandomisation avec la méthode des probabilités conditionnelles. Théorème d'Adleman. Méthode probabiliste et dérandomisation

Séance 7 : A l'intérieur d'un solveur SAT

Algorithme DPLL. Apprentissage de clauses. A l'intérieur d'un solveur SAT

Séance 8 : Algorithmes online

Location de ski. Ratio compététif. Robot aveugle. Arbre de Steiner online. Mise en cache. Algorithmes en ligne

Séance 9 : Largeur arborescente (treewidth)

Complexité paramétrée. Paramétrisation. Décomposition arborescente. Largeur arborescente. Programmation dynamique pour ensemble indépendant, 3-coloration. Logique monadique du second ordre. Théorème de Courcelle (admis). Largeur arborescente

Séance 10 : Algorithmique quantique

Etat quantique. Etat de Bell. Algorithme de Grover. Algorithme QFT (quantum Fourier Transform). Idée générale de l'algorithme de Shor. Algorithmique quantique Version imagée de l'algorithme quantique avec des chats

Références bibliographes

Aller voir à la fin de chaque fiche de cours.