Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2018/2019

Problémy a algoritmy

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
MI-PAA Z,ZK 5 2P+1R+1C česky
Přednášející:
Jan Schmidt (gar.)
Cvičící:
Petr Fišer, Jan Schmidt (gar.), Jaroslav Borecký, Robert Hülle
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. Modely výpočtu. Třídy P, NP. Polynomiální hierarchie.

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

4. Třídy PO a NPO.a jejich struktura. Deterministické aproximační algoritmy. Třídy aproximativních problémů. Pseudopolynomiální algoritmy. Randomizace, randomizované algoritmy.

5. Komunikační a obvodová složitost

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

7. Lokální metody - stavový prostor, exaktní metody, heuristiky.

8. Simulované ochlazování.

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

10. Pokročilé genetické algoritmy: kompetentní GA, fmGA. Stochastická optimalizace: modely, užití. Bayesovská optimalizace.

11. Tabu prohledávání.

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

13. Rezerva na státní svátky a ceremonie

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:

Informace o předmětu a výukové materiály naleznete na https://moodle.fit.cvut.cz/courses/MI-PAA/

Rozsah=prednasky+proseminare+cviceni2p+1r+1c

Další informace:
https://moodle.fit.cvut.cz/courses/MI-PAA/
Rozvrh na zimní semestr 2018/2019:
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 TH:A-1042
Borecký J.
09:15–10:45
(přednášková par. 1
paralelka 101)

Thákurova 7 (FSv-budova A)
Hlavickova laborka
místnost TH:A-1042
Fišer P.
16:15–17:45
(přednášková par. 1
paralelka 104)

Thákurova 7 (FSv-budova A)
Hlavickova laborka
místnost TK:BS
Schmidt J.
18:00–19:30
(přednášková par. 1)
Dejvice
NTK Ballingův sál
místnost TH:A-1042
Borecký J.
11:00–12:30
(přednášková par. 1
paralelka 102)

Thákurova 7 (FSv-budova A)
Hlavickova laborka
místnost TH:A-1042
Fišer P.
12:45–14:15
(přednášková par. 1
paralelka 103)

Thákurova 7 (FSv-budova A)
Hlavickova laborka
místnost TH:A-1042
Fišer P.
14:30–16:00
(přednášková par. 1
paralelka 111)

Thákurova 7 (FSv-budova A)
Hlavickova laborka
Út
místnost TH:A-1042
Hülle R.
07:30–09:00
(přednášková par. 1
paralelka 110)

Thákurova 7 (FSv-budova A)
Hlavickova laborka
místnost TH:A-1042
Hülle R.
09:15–10:45
(přednášková par. 1
paralelka 105)

Thákurova 7 (FSv-budova A)
Hlavickova laborka
místnost TH:A-1042
Schmidt J.
12:45–14:15
(přednášková par. 1
paralelka 106)

Thákurova 7 (FSv-budova A)
Hlavickova laborka
místnost TH:A-1042
Schmidt J.
14:30–16:00
(přednášková par. 1
paralelka 107)

Thákurova 7 (FSv-budova A)
Hlavickova laborka
St
Čt

místnost TH:A-1042
Schmidt J.
09:15–10:45
(přednášková par. 1
paralelka 109)

Thákurova 7 (FSv-budova A)
Hlavickova laborka
Rozvrh na letní semestr 2018/2019:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 18. 8. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet1432506.html