XD36PAA | Problémy a algoritmy | Rozsah výuky: | 14+4 | ||
---|---|---|---|---|---|
Přednášející (garant): | Schmidt J. | Typ předmětu: | Z | Zakončení: | Z,ZK |
Zodpovědná katedra: | 336 | Kreditů: | 5 | Semestr: | L |
Anotace:
Absolvent předmětu umí prakticky řešit kombinatorické problémy. Předmět obsahuje nezbytné partie z teorie složitosti, NP-těžkých problémů a jejich aproximovatelnosti. Jsou prezentovány nejdůležitější heuristické algoritmy a procvičováno jejich nasazení, aby student získal intuitivní vhled do jejich práce.
Osnovy přednášek:
1. | Kombinatorické problémy, přehled úloh a metod řešení | |
2. | Analýza složitosti algoritmů | |
3. | Metafora stavového prostoru a metody jeho prohledávání, dynamické programování a aplikace | |
4. | Modely výpočtu, třídy problémů P a NP | |
5. | Třídy problémů NP-úplný a NP-těžký, polynomiální redukce a transformace | |
6. | Měření kvality aproximativních a heuristických metod | |
7. | Lokální metody, typické strategie pohybu stavovým prostorem | |
8. | Princip konstruktivních metod | |
9. | Princip iterativních metod | |
10. | Simulované ochlazování | |
11. | Simulovaná evoluce | |
12. | Tabu prohledávání | |
13. | Globální metody | |
14. | Lineární programování |
Osnovy cvičení:
Cvičení označená "domácí práce" jsou věnována samostatné práci na příslušné úloze
1. | Ukázky problémů, úvod do algoritmů. Zadání 1. domácí práce | |
2. | Konstrukce asymptotických mezí složitosti | |
3. | Příklady stavového prostoru. Odevzdání 1. domácí práce. Zadání 2. domácí práce | |
4. | 2.domácí práce | |
5. | Třídy problémů P a NP, transformace, důkazy. Odevzdání 2. domácí práce. Zadání 3. domácí práce | |
6. | 3. domácí práce | |
7. | Lokální konstruktivní metody. Odevzdání 3. domácí práce. Zadání 4. domácí práce | |
8. | Jednoduché iterativní metody | |
9. | 4. domácí práce | |
10. | Pokročilé iterativní metody. Zadání problému obchodního cestujícího | |
11. | 4. domácí práce | |
12. | 4. domácí práce | |
13. | Prezentace řešení problému obchodního cestujícího | |
14. | Prezentace řešení problému obchodního cestujícího |
Literatura Č:
1. | Schmidt, J. Problémy a algoritmy. Připravované skriptum FEL ČVUT. | |
2. | Kučera, L.: Kombinatorické algoritmy.Praha, SNTL, 1983 | |
3. | Garey, M. R., Johnson, D. S.: Computers and Intractability. San Francisco, W. H. Freeman, 1979. | |
4. | Ausielo, G., et al: Complexity and Approximation. Berlin, Springer 1999. |
Literatura A:
1. | Garey, M. R., Johnson, D. S.: Computers and Intractability. San Francisco, W. H. Freeman, 1979 | |
2. | Ausielo, G., et al: Complexity and Approximation. Berlin, Springer 1999 |
Požadavky:
Vypracování všech domácích prací, aktivní účast na seminářích. Součástí zkoušky je diskuse 4. domácí práce.
Předmět je zahrnut do těchto studijních plánů:
|
Stránka vytvořena 25. 2. 2002, semestry: Z/2001-2, Z/2002-3, L/2001-2, L/2002-3, připomínky k informační náplni zasílejte správci studijních plánů | Návrh a realizace: I. Halaška (K336), J. Novák (K336) |