Problémy a algoritmy

Přednášející:

Jan Schmidt (gar.)

Cvičící:

Petr Fišer, Jan Schmidt (gar.), Pavel Kordík, Jan Pospíšil

Předmět zajišťuje:

katedra číslicového návrhu

Anotace:

Studenti se naučí posoudit diskrétní problémy podle složitosti a podle účelu optimalizace (on-line, multikriteriální atd.). Porozumí principům a vlastnostem heuristik a exaktních algoritmů. Dokáží vybrat, aplikovat a experimentálně vyhodnotit vhodnou heuristiku pro praktické problémy.

Požadavky:

Základy složitosti, asymptotické meze složitosti. Základy teorie grafů. Programování v jakémkoli jazyce, užití fronty, zásobníku, seznamu.

Osnova přednášek:

1. Optimalizace, příklady optimalizačních úloh v praxi. Kombinatorické problémy. Složitost algoritmu a problému.

2. Stav, stavový prostor, prohledávací prostor. Základní techniky pro exaktní algoritmy.

3. Řešitelné problémy. Modely výpočtu. Třídy P, NP. Polynomiální hierarchie. Třídy PO a NPO.

4. Pojem úplnosti problému. Techniky srovnání složitosti. Třídy NP-úplný, NP-těžký. Struktura NP a NPO.

5. Deterministické aproximační algoritmy. Třídy aproximativních problémů. Pseudopolynomiální algoritmy. Randomizace, randomizované algoritmy.

6. Praktické nasazení heuristik a exaktních algoritmů. Experimentální vyhodnocení.

7. Jednoduché lokální heuristiky ve stavovém a prohledávacím prostoru.

8. Simulované ochlazování.

9. Simulovaná evoluce: typy, genetické algoritmy.

10. Pokročilé genetické algoritmy: kompetentní GA, fmGA, metoda sobeckého genu. Použití v multikriteriální optimalizaci.

11. Stochastická optimalizace: modely, užití. Bayesovská optimalizace.

12. Tabu prohledávání.

13. Globální metody, typy dekompozice. Exaktní a heuristické globální metody, algoritmus Davis-Putnam jako globální metoda.

Osnova cvičení:

1. Cvičení: terminologie, příklady na složitost.

2. Cvičení: příklady stavového prostoru algoritmů.

3. Konzultace; samostudium: dynamické programování.

4. Proseminář: třídy P, NP, důkazy, problémy horší než NP.

5. Proseminář: úplnost, redukce.

6. Konzultace.

7. Konzultace.

8. Konzultace.

9. Proseminář: test.

10. Konzultace.

11. Proseminář: nasazení pokročilých heuristik.

12. Konzultace.

13. Konzultace.

14. Proseminář: náhradní test, zápočty.

Cíle studia:

Mnoho praktických úloh je výpočetně nezvládnutelných. V předmětu se studenti naučí rozlišit ty, kde náročnost příliš rychle roste s velikostí úlohy od úloh principiálně neřešitelných a na velikosti nezávislých. Dále se seznámí s rychlými algoritmy pro přesná, ale hlavně přibližná řešení. Pokročilejší algoritmy jsou inspirovány přírodními procesy a někdy jsou označovány jako softcomputing. Série samostatných prací vede studenta od velmi jednoduchých příkladů až po zvládnutí pokročilých heuristik na prakticky významném problému.

Studijní materiály:

Kučera, L. ''Kombinatorické algoritmy''. Praha: SNTL, 1983.

Garey, M. R., Johnson, D. S. ''Computers and Intractability: A Guide to the Theory of NP-Completeness''. W. H. Freeman, 1979. ISBN 0716710455.

Ausiello, G., Crescenzi, P., Kann, V., Gambosi, G., Spaccamela, A. M. ''Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties''. Springer, 2003. ISBN 3540654313.

Poznámka:

Rozsah=prednasky+proseminare+cviceni2p+1r+1c, Prednasejici: Ing. Jan Schmidt Ph.D.

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 T9:345 Kordík P. 12:45–14:15 (přednášková par. 1 paralelka 106) Dejvice NBFIT HW ucebnamístnost T9:155 Schmidt J. 14:30–16:00 (přednášková par. 1) Dejvice Posluchárna
Út	místnost T9:345 Kordík P. 12:45–14:15 (přednášková par. 1 paralelka 101) Dejvice NBFIT HW ucebnamístnost T9:345 Fišer P. 14:30–16:00 (přednášková par. 1 paralelka 102) Dejvice NBFIT HW ucebnamístnost T9:345 Fišer P. 16:15–17:45 (přednášková par. 1 paralelka 103) Dejvice NBFIT HW ucebnamístnost T9:345 Fišer P. 18:00–19:30 (přednášková par. 1 paralelka 104) Dejvice NBFIT HW ucebna
St	místnost T9:345 Pospíšil J. 11:00–12:30 (přednášková par. 1 paralelka 107) Dejvice NBFIT HW ucebnamístnost T9:345 Pospíšil J. 12:45–14:15 (přednášková par. 1 paralelka 108) Dejvice NBFIT HW ucebnamístnost T9:345 Fišer P. 16:15–17:45 (přednášková par. 1 paralelka 109) Dejvice NBFIT HW ucebnamístnost T9:345 Fišer P. 18:00–19:30 (přednášková par. 1 paralelka 105) Dejvice NBFIT HW ucebna
Č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ů:

• Zaměření Softwarové inženýrství - verze pro ty, kteří se zapsali v roce 2010 (povinný předmět oboru)
• Zaměření Webové inženýrství - verze pro ty, kteří se zapsali v roce 2010 (povinný předmět oboru)
• Počítačová bezpečnost - verze pro ty, kteří se zapsali v roce 2010 (povinný předmět oboru)
• Projektování číslicových systémů - verze pro ty, kteří se zapsali v roce 2010 (povinný předmět oboru)
• Počítačové systémy a sítě - verze pro ty, kteří se zapsali v roce 2010 (povinný předmět oboru)
• Znalostní inženýrství - verze pro ty, kteří se zapsali v roce 2010 (povinný předmět oboru)
• Zaměření Informační systémy a management - verze pro ty, kteří se zapsali v roce 2010 (povinný předmět oboru)
• Společný plán před přiřazením do oboru, verze pro ty, kteří se zapsali v roce 2010 (VO)
• Společný plán před přiřazením do oboru, verze pro ty, kteří se zapsali v roce 2011 (VO)
• Zaměření Informační systémy a management - verze pro ty, kteří se zapsali v roce 2011 (povinný předmět oboru)
• Zaměření Softwarové inženýrství - verze pro ty, kteří se zapsali v roce 2011 (povinný předmět oboru)
• Zaměření Webové inženýrství - verze pro ty, kteří se zapsali v roce 2011 (povinný předmět oboru)
• Znalostní inženýrství - verze pro ty, kteří se zapsali v roce 2011 (povinný předmět oboru)
• Počítačová bezpečnost - verze pro ty, kteří se zapsali v roce 2011 (povinný předmět oboru)
• Projektování číslicových systémů - verze pro ty, kteří se zapsali v roce 2011 (povinný předmět oboru)
• Počítačové systémy a sítě - verze pro ty, kteří se zapsali v roce 2011 (povinný předmět oboru)
• Společný plán před přiřazením do oboru, verze pro ty, kteří se zapsali v roce 2012 (VO)
• Počítačová bezpečnost - verze pro ty, kteří se zapsali v roce 2012 (povinný předmět oboru)
• Projektování číslicových systémů - verze pro ty, kteří se zapsali v roce 2012 (povinný předmět oboru)
• Zaměření Informační systémy a management - verze pro ty, kteří se zapsali v roce 2012 (povinný předmět oboru)
• Zaměření Softwarové inženýrství - verze pro ty, kteří se zapsali v roce 2012 (povinný předmět oboru)
• Zaměření Webové inženýrství - verze pro ty, kteří se zapsali v roce 2012 (povinný předmět oboru)
• Znalostní inženýrství - verze pro ty, kteří se zapsali v roce 2012 (povinný předmět oboru)
• Počítačové systémy a sítě - verze pro ty, kteří se zapsali v roce 2012 (povinný předmět oboru)