ALGO2 : Algorithmique avancée

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

Intervenants

Cours : François Schwarzentruber
TD : Santiago Sara Bautista
Poly du cours

Plan du cours

Séance 1 : SAT : apprentissage de clauses

SAT, DPLL. Apprentissage de clauses. Algorithme CDCL.

Séance 2 : Etude théorique de CDCL

Terminaison. Correction et complétude.

Séance 3 : Dualité en programmation linéaire

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.

Séance 4 : Dualité en programmation linéaire (Démonstrations)

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.

Séance 5 : 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.

Séance 6 : Algorithmes d'approximation

Algorithme de Christofides. Approximation par rounding puis programmation dynamique. Sac à dos. Idée pour TSP euclidien. Algo et démonstration de correction de TSP euclidien

Séance 7 : Algorithmes probabilistes

Algorithme de Karger pour MIN-CUT. Amélioration de l'algorithme de Karger.

Séance 8 : 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.

Séance 9 : Chaîne de Markov

Irréductibilité, apériodicité. Réversibilité. Echantillonnage de Gibbs. Recuit simulé (idée). Algorithme de Propp-Wilson.

Séance 10 : Chaîne de Markov

Recuit simulé. Algorithme de Propp-Wilson.

Séance 11 : Largeur arborescente (treewidth)

Complexité paramétrée. Paramétrisation. Décomposition arborescente. Largeur arborescente.

Séance 12 : Largeur arborescente (suite)

Programmation dynamique pour ensemble indépendant, 3-coloration. Logique monadique du second ordre. Théorème de Courcelle (admis).

Séance 13 : Algorithmique quantique (séance annulée)

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

Examens des années précédentes

Références bibliographes

Aller voir à la fin de chaque fiche de cours.