Algoritmai

Algoritmų analizės problemos. Kombinatoriniai objektai ir jų vaizdavimo būdai. Grafai ir jų vaizdavimas. Algoritmai ir jų sudėtingumas. Viršutiniai algoritmų sudėtingumo įverčiai. Apatiniai algoritmų sudėtingumo įverčiai. Funkcijų augimo greičiai ir kombinatorinis sprogimas. Teorema "Skaldyk ir valdyk". Sveikųjų dvejetainių skaičių daugyba. Matricų daugyba Strassen‘o metodu. Dinaminis programavimas. Fibonacci skaičiai ir kuprinės pakavimo uždaviniai. Dinaminis programavimas. Matricų daugybos tvarka. Paieška su grįžimu. N valdovių uždavinys. Minimalaus skaidinio uždavinys. Šakų ir rėžių metodas, jo taikymas keliaujančio pirklio uždaviniui. Darbų paskirstymo uždavinys. Godūs algoritmai. Minimalus karkasas ir keliaujančio pirklio uždavinys. Paieška grafuose gilyn ir platyn. Karkasai ir grafo komponentės. Oilerio grafai. Trumpiausi keliai grafuose. Grafų izomorfizmas. Kalbų ir uždavinių ryšys. Uždavinių sudėtingumas klasė P. Sudėtingumo klasės NP ir co-NP. NP-pilnumas. Sudėtingumo klasė NPC. Uždavinys CIRCUIT-SAT. Uždavinai SAT,3_KNF_SAT, CLIQUE(k) ir VERTEX_COUER(k).