Algorithmes de graphes : parcours, plus court chemin, arbres couvrants, flots.
programmation linéaire : méthode simplex, dualité, modélisation de problèmes NP-complets comme programmes linéaires en nombres entiers.
Plutôt P :
Diviser-pour-régner : multiplication des entiers, élément k minimal, transformée de Fourier rapide.
Programmation dynamique : distance d'édition et distance d'édition en espace linéaire, structure secondaire d'un ARN, stable max d'un arbre.
Algorithmes gloutons : matroïdes et algorithmes gloutons, axiomatiques des matroïdes par bases, circuits, fonction de rang.
Méthode locale : recuit simulé, configurations stables dans les réseaux de Hopfield, mariage stable, coupe maximum d'un graphe (algo facteur 2).
Plutôt NP-complet :
Algorithmes d'approximation : facteur 2 pour VERTEX COVER, facteur 2 et 4/3 pour ordonnancement des tâches, facteur 2 pour NextFit et 3/2 FirstFitDecreasing pour BinPacking. FPTAS pour le Sac à Dos. PTAS pour l'ordonnancement des tâches.
Largeur arborescente d'un graphe: algorithmes à paramètres exacts pour VERTEX COVER dans des graphes de largeur arborescente bornée.
PSPACE : QSAT et Planification ((s,t)-Reachability) sont dans PSPACE (théorème de Savitch).
Randomisation (rappels) : analyse de la complexité en espérance pour Quicksort, algorithmes d'approximation pour CoupeMax et MaxSAT (par randomisation et programmation linéaire). Dérandomisation pour MaxSAT. Comptage approximatif et schéma d'approximation randomise FPTRAS pour les comptage #DNF.
Thèmes complémentaires :
Algorithmes géométriques : diagrammes de Voronoi par diviser pour régner et par balayage, triangulations de Delaunay méthode incrémentale randomisée.
Algorithmes en ligne et compétitivité : analyse en compétitivité de la k-pagination, le list accessing problem, et les k serveurs sur un arbre.
VC-dimension et théorème des epsilon-réseaux, PAC learning.
