INFO5152 Algoritmi parametrizați și exacti École normale supérieure de Lyon

Codul cursului INFO5152

algoritmi

Intitulat Algoritmi parametrizați și exacți

Perioada semestrului I

Departamentul Departamentul de Informatică

Locația site-ului Monod

Prezentăm instrumente algoritmice pentru a rezolva în mod optim problemele NP-hard mai rapid decât abordarea forței brute. Introducem algoritmi parametrizati și complexitate. Accentul este pus pe tehnici și modul în care acestea exploatează structura de intrare pentru a servi atât algoritmi parametrizati, cât și moderat exponențiali/subexponențiali. De asemenea, evidențiem ipotezele teoretice ale complexității și modul în care acestea permit adesea să completeze algoritmii cunoscuți prin potrivirea esențială a limitelor inferioare condiționate.