Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
X36PAA Problémy a algoritmy Rozsah výuky:2+2
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.

Rozsah výuky v kombinované formě studia: 14+4
Typ cvičení: s, p
Předmět je nabízen také v anglické verzi.

Předmět je zahrnut do těchto studijních plánů:
Plán Obor Role Dop. semestr
MVT01 Výpočetní technika Z 2
MVT04 Výpočetní technika Z 2
MVT05 Výpočetní technika Z 2
MVT03 Výpočetní technika Z 2
MVT02 Výpočetní technika Z 2


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)