Přehled studia |
Přehled oborů |
Všechny skupiny předmětů |
Všechny předměty |
Seznam rolí |
Vysvětlivky
Návod
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ů:
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) |