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

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.), Dušan Knop
Cvičící:
Pavel Tvrdík (gar.), Václav Blažej, Radovan Červený, Radek Hušek, Dušan Knop, Jan Matyáš Křišťan, Josef Malík, Jakub Pečenka, Štěpán Plachý, Josef Erik Sedláček, Šimon Schierreich, Jiřina Scholtzová, Eliška Šestáková, Ondřej Šofr, 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.

Na tento předmět obsahově navazuje magisterský předmět

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/

Na tento předmět navazuje v magisterském studiu předmět Paralelní a distribuované programování.

Další informace:
https://courses.fit.cvut.cz/BI-AG1/
Rozvrh na zimní semestr 2020/2021:
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 TK:BS
Knop D.
09:15–10:45
(přednášková par. 1)
Dejvice
NTK Ballingův sál
místnost TH:A-942
Pečenka J.
18:00–19:30
(paralelka 1)
Thákurova 7 (FSv-budova A)
místnost TH:A-1247
Scholtzová J.
11:00–12:30
(paralelka 23)
Thákurova 7 (FSv-budova A)
seminární místnost
místnost TK:BS
Tvrdík P.
16:15–17:45
(přednášková par. 2)
Dejvice
NTK Ballingův sál
Út
místnost TH:A-1242
Malík J.
07:30–09:00
(paralelka 4)
Thákurova 7 (FSv-budova A)
místnost T9:302
Knop D.
09:15–10:45
(paralelka 5)
Dejvice
NBFIT učebna
místnost T9:302
Knop D.
07:30–09:00
(paralelka 3)
Dejvice
NBFIT učebna
místnost TH:A-1242
Malík J.
09:15–10:45
(paralelka 6)
Thákurova 7 (FSv-budova A)
St
místnost TH:A-1247
Červený R.
16:15–17:45
(paralelka 7)
Thákurova 7 (FSv-budova A)
seminární místnost
místnost TH:A-1242
Hušek R.
18:00–19:30
(paralelka 9)
Thákurova 7 (FSv-budova A)
místnost TH:A-1242
Hušek R.
16:15–17:45
(paralelka 8)
Thákurova 7 (FSv-budova A)
místnost TH:A-1247
Červený R.
18:00–19:30
(paralelka 10)
Thákurova 7 (FSv-budova A)
seminární místnost
Čt
místnost T9:346
Schierreich Š.
07:30–09:00
(paralelka 11)
Dejvice
NBFIT učebna
místnost T9:346
Schierreich Š.
09:15–10:45
(paralelka 12)
Dejvice
NBFIT učebna
místnost TH:A-1242
Sedláček J.
16:15–17:45
(paralelka 15)
Thákurova 7 (FSv-budova A)
místnost TH:A-1242
Sedláček J.
18:00–19:30
(paralelka 16)
Thákurova 7 (FSv-budova A)
místnost T9:346
Křišťan J.
16:15–17:45
(paralelka 14)
Dejvice
NBFIT učebna
místnost T9:346
Křišťan J.
18:00–19:30
(paralelka 17)
Dejvice
NBFIT učebna

místnost TH:A-942
Šofr O.
09:15–10:45
(paralelka 18)
Thákurova 7 (FSv-budova A)
místnost T9:301
Šestáková E.
16:15–17:45
(paralelka 21)
Dejvice
NBFIT učebna
místnost T9:301
Šestáková E.
18:00–19:30
(paralelka 22)
Dejvice
NBFIT učebna
místnost TH:A-942
Šofr O.
11:00–12:30
(paralelka 19)
Thákurova 7 (FSv-budova A)
místnost T9:301
Vu T.
14:30–16:00
(paralelka 20)
Dejvice
NBFIT učebna
místnost T9:301
Vu T.
12:45–14:15
(paralelka 24)
Dejvice
NBFIT učebna
Rozvrh na letní semestr 2020/2021:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 19. 1. 2021
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet3458106.html