INFO5152 Paraméterezett és pontos algoritmusok École normale supérieure de Lyon

Az INFO5152 tanfolyam kódja

pontos

Paraméterezett és pontos algoritmusok

1. félévi időszak

Tanszék Számítástudományi Tanszék

Monod telephelye

Bemutatunk algoritmikus eszközöket az NP-nehéz problémák optimális megoldására, mint a durva erő megközelítése. Bemutatjuk a paraméterezett algoritmusokat és a komplexitást. A hangsúly a technikákon és azon van, hogyan használják ki az input struktúrát mind a paraméterezett, mind a mérsékelten exponenciális/szubexponenciális algoritmusok kiszolgálására. Kiemeljük továbbá a bonyolultságelméleti feltételezéseket és azt, hogy ezek hogyan teszik lehetővé az ismert algoritmusok kiegészítését a feltételes alsó határok lényegében egyezésével.