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

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 2P+2C č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, Dušan Knop, Jan Matyáš Křišťan, Šimon Lomič, Josef Malík, Peter Mitura, Petr Nevyhoštěný, Š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ýmI předměty BI-AAG a BI-ZDM, ve kterých 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.

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

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

7 Úvod do randomizace, hešování.

8 Rekurzivní algoritmy a metoda Rozděl a panuj.

9 QuickSort. Speciální algoritmy řazení.

10 Dynamické programování.

11 Minimální kostry grafu.

12 Nejkratší cesty v grafech.

Osnova cvičení:

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. 1. progtest

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

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

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

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

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

9. Rekurzivní algoritmy a metoda Rozděl a panuj.

10. Semestrální písemka.

11. Dynamické programování. 3. progtest

12. Minimální kostry a nejkratší cesty v grafech.

Cíle studia:
Studijní materiály:

[1] Cormen, T. H. - Leiserson, C. E. - Rivest, R. L. - Stein, C.: Introduction to Algorithms, 3rd Edition, MIT Press, 2009, 978-0262033848,

[2] Gibbons, A.: Algorithmic Graph Theory, Cambridge University Press, 1985, 978-0521288811,

[3] Gross, J. L. - Yellen, J. - Zhang, P.: Handbook of Graph Theory, 2nd Edition (Discrete Mathematics and Its Applications), Chapman and Hall/CRC, 2013, 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 2019/2020:
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
Valla T.
11:00–12:30
(přednášková par. 1)
Dejvice
NTK Ballingův sál
místnost TH:A-1247
Malík J.
14:30–16:00
(paralelka 101)
Thákurova 7 (FSv-budova A)
seminární místnost
místnost TH:A-1442
Plachý Š.
16:15–17:45
(paralelka 102)
Thákurova 7 (FSv-budova A)
místnost TH:A-1442
Plachý Š.
18:00–19:30
(paralelka 103)
Thákurova 7 (FSv-budova A)
místnost TK:BS
Tvrdík P.
12:45–14:15
(přednášková par. 2)
Dejvice
NTK Ballingův sál
místnost T9:346
Valla T.
14:30–16:00
(paralelka 201)
Dejvice
NBFIT učebna
místnost TH:A-1342
Červený R.
16:15–17:45
(paralelka 202)
Thákurova 7 (FSv-budova A)
místnost T9:346
Křišťan J.
18:00–19:30
(paralelka 203)
Dejvice
NBFIT učebna
St
místnost TH:A-1442
Nevyhoštěný P.
16:15–17:45
(paralelka 104)
Thákurova 7 (FSv-budova A)
místnost TH:A-1242
Vu T.
18:00–19:30
(paralelka 205)
Thákurova 7 (FSv-budova A)
místnost TH:A-1242
Vu T.
16:15–17:45
(paralelka 204)
Thákurova 7 (FSv-budova A)
místnost TH:A-1342
Mitura P.
18:00–19:30
(paralelka 105)
Thákurova 7 (FSv-budova A)
Čt
místnost TH:A-1342
Knop D.
11:00–12:30
(paralelka 106)
Thákurova 7 (FSv-budova A)
místnost TH:A-1342
Knop D.
12:45–14:15
(paralelka 107)
Thákurova 7 (FSv-budova A)
místnost T9:347
Malík J.
14:30–16:00
(paralelka 108)
Dejvice
NBFIT učebna
místnost TH:A-1342
Blažej V.
16:15–17:45
(paralelka 109)
Thákurova 7 (FSv-budova A)

místnost T9:302
Knop D.
11:00–12:30
(paralelka 206)
Dejvice
NBFIT učebna
místnost TH:A-1242
Šestáková E.
14:30–16:00
(paralelka 208)
Thákurova 7 (FSv-budova A)
místnost TH:A-1242
Šestáková E.
16:15–17:45
(paralelka 209)
Thákurova 7 (FSv-budova A)
místnost TH:A-1242
Šestáková E.
18:00–19:30
(paralelka 210)
Thákurova 7 (FSv-budova A)
místnost T9:302
Knop D.
12:45–14:15
(paralelka 207)
Dejvice
NBFIT učebna
Rozvrh na letní semestr 2019/2020:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 18. 10. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet3458106.html