Problémy a algoritmy

Předmět je náhradou za:

Problémy a algoritmy (36PAA)

Přednášející:

Jan Schmidt

Cvičící:

Jan Schmidt, Petr Fišer, Jan Koutník

Předmět zajišťuje:

katedra počítačů

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.

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.

Osnova 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í

Osnova 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

Cíle studia:

Studijní materiály:

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.

Poznámka:

Rozsah výuky v kombinované formě studia: 14+4

Typ cvičení: s, p

Předmět je nabízen také v anglické verzi.

Rozvrh na zimní semestr 2011/2012:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po	místnost Schmidt J. 14:30–16:00 (přednášková par. 1)
Út	místnost Fišer P. 14:30–16:00 (přednášková par. 1 paralelka 102)
St
Čt
Pá

Rozvrh na letní semestr 2011/2012:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• MVT01-Výpočetní technika - softwarové inženýrství- strukturované studium (povinný předmět)
• MVT02-Výpočetní technika - systémové programování- strukturované studium (povinný předmět)
• MVT03-Výpočetní technika - počítačová grafika- strukturované studium (povinný předmět)
• MVT04-Výpočetní technika - počítačové sítě a internet- strukturované studium (povinný předmět)
• MVT05-Výpočetní technika - projektování číslicových systémů- strukturované studium (povinný předmět)