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

Rozsah výuky v kombinované formě studia: 19+4
Typ cvičení: s, p
Tento 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
*VT Výpočetní technika Z 10


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)