Problémy a algoritmy

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra číslicového návrhu

Anotace:

Studenti se naučí posoudit diskrétní problémy podle složitosti a podle účelu optimalizace (on-line, multikriteriální atd.). Porozumí principům a vlastnostem heuristik a exaktních algoritmů. Dokáží vybrat, aplikovat a experimentálně vyhodnotit vhodnou heuristiku pro praktické problémy.

Od B201 je vypisována nová, ekvivalentní verze předmětu NI-KOP.

Požadavky:

Základy složitosti, asymptotické meze složitosti. Základy teorie grafů. Programování v jakémkoli jazyce, užití fronty, zásobníku, seznamu.

Osnova přednášek:

1. Optimalizace, příklady optimalizačních úloh v praxi. Kombinatorické problémy. Složitost algoritmu a problému.

2. Modely výpočtu. Třídy P, NP. Polynomiální hierarchie.

3. Pojem úplnosti problému. Techniky srovnání složitosti. Třídy NP-úplný, NP-těžký, NPI.

4. Třídy PO a NPO.a jejich struktura. Deterministické aproximační algoritmy. Třídy aproximativních problémů. Pseudopolynomiální algoritmy. Randomizace, randomizované algoritmy.

5. Komunikační a obvodová složitost

6. Praktické nasazení heuristik a exaktních algoritmů. Experimentální vyhodnocení.

7. Lokální metody - stavový prostor, exaktní metody, heuristiky.

8. Simulované ochlazování.

9. Simulovaná evoluce: typy, genetické algoritmy.

10. Pokročilé genetické algoritmy: kompetentní GA, fmGA. Stochastická optimalizace: modely, užití. Bayesovská optimalizace.

11. Tabu prohledávání.

12. Globální metody, typy dekompozice. Exaktní a heuristické globální metody, algoritmus Davis-Putnam jako globální metoda.

13. Rezerva na státní svátky a ceremonie

Osnova cvičení:

1. Cvičení: terminologie, příklady na složitost.

2. Cvičení: příklady stavového prostoru algoritmů.

3. Konzultace; samostudium: dynamické programování.

4. Proseminář: třídy P, NP, důkazy, problémy horší než NP.

5. Proseminář: úplnost, redukce.

6. Konzultace.

7. Konzultace.

8. Konzultace.

9. Proseminář: test.

10. Konzultace.

11. Proseminář: nasazení pokročilých heuristik.

12. Konzultace.

13. Konzultace.

14. Proseminář: náhradní test, zápočty.

Cíle studia:

Mnoho praktických úloh je výpočetně nezvládnutelných. V předmětu se studenti naučí rozlišit ty, kde náročnost příliš rychle roste s velikostí úlohy od úloh principiálně neřešitelných a na velikosti nezávislých. Dále se seznámí s rychlými algoritmy pro přesná, ale hlavně přibližná řešení. Pokročilejší algoritmy jsou inspirovány přírodními procesy a někdy jsou označovány jako softcomputing. Série samostatných prací vede studenta od velmi jednoduchých příkladů až po zvládnutí pokročilých heuristik na prakticky významném problému.

Studijní materiály:

Kučera, L. ''Kombinatorické algoritmy''. Praha: SNTL, 1983.

Garey, M. R., Johnson, D. S. ''Computers and Intractability: A Guide to the Theory of NP-Completeness''. W. H. Freeman, 1979. ISBN 0716710455.

Ausiello, G., Crescenzi, P., Kann, V., Gambosi, G., Spaccamela, A. M. ''Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties''. Springer, 2003. ISBN 3540654313.

Poznámka:

Předmět je nahrazen ekvivalentním NI-KOP // Informace o předmětu a výukové materiály naleznete na https://moodle-vyuka.cvut.cz/course/view.php?id=2217

Další informace:

https://moodle-vyuka.cvut.cz/course/view.php?id=2217

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Mgr. obor Znalostní inženýrství, 2016-2017 (povinný předmět programu)
• Mgr. obor Počítačová bezpečnost, 2016-2019 (povinný předmět programu)
• Mgr. obor Počítačové systémy a sítě, 2016-2019 (povinný předmět programu)
• Mgr. obor Návrh a programování vestavných systémů, 2016-2019 (povinný předmět programu)
• Mgr. obor Webové a softwarové inženýrství, zaměření Informační systémy a management, 2016-2019 (povinný předmět programu)
• Mgr. obor Webové a softwarové inženýrství, zaměření Softwarové inženýrství, 2016-2019 (povinný předmět programu)
• Mgr. obor Webové a softwarové inženýrství, zaměření Webové inženýrství, 2016-2019 (povinný předmět programu)
• Mgr. program Informatika, pro fázi studia bez oboru, 2016-2019 (povinný předmět programu)
• Mgr. obor Systémové programování, zaměření Systémové programování, 2016-2019 (povinný předmět programu)
• Mgr. obor Systémové programování, zaměření Teoretická informatika, 2016-2017 (povinný předmět programu)
• Mgr. obor Znalostní inženýrství, 2018-2019 (povinný předmět programu)