36PAA | Problémy a algoritmy | Rozsah výuky: | 3+2 | ||
---|---|---|---|---|---|
Přednášející (garant): | Muzikář Z., Schmidt J., Sysala T. | Typ předmětu: | Z | Zakončení: | Z,ZK |
Zodpovědná katedra: | 336 | Kreditů: | 6 | Semestr: | L |
Anotace:
Mnohé na první pohled jednoduché úlohy nelze na počítači prakticky řešit, protože by výpočet trval déle než je jeho životnost. Jak lze rozpoznat takové úlohy a jak lze navrhnout v praxi použitelné algoritmy - o tom je tento kurz. Použitý matematický aparát je minimalizován. Důraz je kladen na poznatky použitelné v inženýrské praxi a na souvislosti mezi jednotlivými metodami.
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, úplné prohledávání | |
4. | Systematické metody prohledávání | |
5. | Modely výpočtu: třídy problémů P a NP | |
6. | Třídy problémů NP-úplný a NP-těžký, polynomiální redukce | |
7. | Měření kvality aproximativních metod | |
8. | Lokální konstruktivní metody | |
9. | Princip lokálních iterativních metod | |
10. | Simulované ochlazování | |
11. | Simulovaná evoluce | |
12. | Tabu prohledávání | |
13. | Globální metody: princip a typické strategie | |
14. | Lineární programování: celočíselné a 0-1 programování, relaxace |
Osnovy cvičení:
1. | Ukázky problémů, úvod do algoritmů | |
2. | Složitost | |
3. | Stavový prostor | |
4. | Domácí práce 2. | |
5. | Třídy problémů P a NP, transformace, důkazy | |
6. | Domácí práce 3. | |
7. | Lokální konstruktivní metody | |
8. | Pondělí velikonoční | |
9. | Jednoduché iterativní metody | |
10. | Pokročilé iterativní metody | |
11. | Domácí práce 4. | |
12. | Domácí práce 4. | |
13. | Prezentace řešení problému obchodního cestujícího | |
14. | Prezentace řešení problému obchodního cestujícího, zápočet |
Literatura Č:
[1] | Kučera, L.: Kombinatorické algoritmy. SNTL, Praha 1983 | |
[2] | Plesnik, J.: Grafové algoritmy. Veda, Bratislava 1983 | |
[3] | Garey, M.R., Johnson, D.S.: Computers and Intractability. W.H.Freeman, San Francisco 1979 |
Literatura A:
[1] | Garey, M.R., Johnson, D.S.: Computers and Intractability. W.H.Freeman, San Francisco 1979 |
Požadavky:
|
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) |