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

Algoritmy a grafy 1

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
BI-AG1 Z,ZK 6 2+2 česky
Přednášející:
Pavel Tvrdík (gar.), Tomáš Valla
Cvičící:
Pavel Tvrdík (gar.), Václav Blažej, Radovan Červený, Jiří Chludil, Roman Jelínek, Jan Matyáš Křišťan, Šimon Lomič, Josef Malík, Peter Mitura, Štěpán Plachý, Jiřina Scholtzová, Ondřej Suchý, Eliška Šestáková, Tomáš Valla, Tung Anh Vu
Předmět zajišťuje:
katedra teoretické informatiky
Anotace:

Předmět pokrývá to nejzákladnější z efektivních algoritmů, datových struktur a teorie grafů, které by měl znát každý informatik. Spolupracuje se souběžně vyučovaným předmětem BI-ZDM, ve kterém studenti získají znalosti a dovednosti nezbytné pro vyhodnocování operační a paměťové složitosti algoritmů a naučí se prakticky používat asymptotickou matematiku.

Požadavky:

Předpokládá se schopnost aktivního algoritmického řešení základních typů úloh, znalost nějakého vyššího programovacího jazyka (Java, C++) a znalost základních pojmů z matematické analýzy a kombinatoriky. Předmět předpokládá, že student souběžně studuje BI-AAG a BI-ZDM.

Osnova přednášek:

1. Motivace a úvod do teorie grafů

2. Základní definice a pojmy teorie grafů I

3. Základní definice a pojmy teorie grafů II

4. Řadící algoritmy O(n^2). Binární haldy a HeapSort.

5. Nafukovací pole, amortizovaná složitost, binomiální haldy

6. Vyhledávací stromy a jejich vyvažování

7. Pravděpodobnostní algoritmy a jejich složitost. QuickSort.

8. Rekurzivní algoritmy a metoda Rozděl a panuj. Lineární řazení

9. Rozptylování (hešování) a vyhledávací tabulky

10. Dynamické programování

11. Minimální kostry grafu

12. Nejkratší cesty v grafech

13. Rezerva

Osnova cvičení:
Cíle studia:
Studijní materiály:

Cormen, T. H., Leiserson, C. E., Rivest, R. L. Introduction to Algorithms. The MIT Press, 2001. ISBN 0262032937.

Gross, J. L. - Yellen, J. - Zhang, P. Handbook of Graph Theory, 2nd Edition (Discrete Mathematics and Its Applications). Chapman and Hall/CRC, 2013. ISBN 978-1439880180.

Poznámka:

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

Další informace:
https://courses.fit.cvut.cz/BI-AG1/
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
Út
místnost TK:BS
Tvrdík P.
12:45–14:15
(přednášková par. 1)
Dejvice
NTK Ballingův sál
místnost TH:A-1342
Plachý Š.
14:30–16:00
(paralelka 101)
Thákurova 7 (FSv-budova A)
místnost TH:A-1242
Vu T.
16:15–17:45
(paralelka 102)
Thákurova 7 (FSv-budova A)
místnost TK:BS
Valla T.
14:30–16:00
(přednášková par. 2)
Dejvice
NTK Ballingův sál
místnost T9:346
Lomič Š.
16:15–17:45
(paralelka 104)
Dejvice
NBFIT učebna
St
místnost TH:A-1342
Scholtzová J.
09:15–10:45
(paralelka 108)
Thákurova 7 (FSv-budova A)
místnost TH:A-1442
Křišťan J.
16:15–17:45
(paralelka 106)
Thákurova 7 (FSv-budova A)
místnost TH:A-1442
Mitura P.
18:00–19:30
(paralelka 107)
Thákurova 7 (FSv-budova A)
místnost TH:A-1342
Valla T.
11:00–12:30
(paralelka 109)
Thákurova 7 (FSv-budova A)
místnost TH:A-1242
Blažej V.
16:15–17:45
(paralelka 201)
Thákurova 7 (FSv-budova A)
místnost T9:346
Jelínek R.
18:00–19:30
(paralelka 202)
Dejvice
NBFIT učebna
Čt
místnost T9:301
Malík J.
11:00–12:30
(paralelka 203)
Dejvice
NBFIT učebna
místnost T9:301
Malík J.
12:45–14:15
(paralelka 204)
Dejvice
NBFIT učebna
místnost T9:302
Šestáková E.
14:30–16:00
(paralelka 205)
Dejvice
NBFIT učebna
místnost T9:302
Šestáková E.
16:15–17:45
(paralelka 206)
Dejvice
NBFIT učebna
místnost T9:302
Šestáková E.
18:00–19:30
(paralelka 207)
Dejvice
NBFIT učebna

místnost TH:A-1442
Červený R.
09:15–10:45
(paralelka 208)
Thákurova 7 (FSv-budova A)
místnost TH:A-1442
Červený R.
11:00–12:30
(paralelka 209)
Thákurova 7 (FSv-budova A)
místnost TH:A-1442
Křišťan J.
12:45–14:15
(paralelka 210)
Thákurova 7 (FSv-budova A)
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 21. 3. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet3458106.html