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

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.21 Z,ZK 5 2P+2C česky
Garant předmětu:
Dušan Knop
Přednášející:
Dušan Knop, Michal Opler
Cvičící:
Suzan Catay, Michal Dvořák, Radek Hušek, Dušan Knop, Jitka Mertlová, Xuan Thang Nguyen, Michal Opler, Josef Erik Sedláček, Martin Slávik, José Gaspar Smutný, Ondřej Suchý, Ondřej Šofr, Tomáš Valla
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.

Navazuje a částečně dále rozvíjí znalosti z předmětu BI-DML.21, ve kterém studenti získají znalosti a dovednosti z kombinatoriky nezbytné pro vyhodnocování časové a paměťové složitosti algoritmů. Dále předmět navazuje na BI-MA1.21, ve kterém ze zavádějí asymptotické odhady funkcí a zejména pak asymptotické značení.

Požadavky:

Předpokládá se schopnost aktivního algoritmického řešení základních typů úloh, znalost programovacího jazyka C++ (zhruba na úrovni vyučované v předmětech BI-PA1.21 a BI-PA2.21) a znalost základních pojmů z matematické analýzy a kombinatoriky (absolvování BI-DML.21 a BI-MA1.21 je doporučeno). Doporučujeme, aby student souběžně studoval BI-AAG.21 a BI-MA2.21.

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. Řadící algoritmy O(n^2).

4. Binární haldy. Nafukovací pole, amortizovaná složitost.

5. Binomiální haldy.

6. Operace a vlastnosti binárních vyhledávacích stromů, způsoby jejich vyvažování, podrobnější diskuze AVL stromů.

7. Randomizované algoritmy, základy pravděpodobnosti, hešování a strategie řešení kolizí.

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

9. QuickSort. Dolní mez složitosti řazení v porovnávacím modelu. Speciální algoritmy řazení.

10. Dynamické programování.

11. Minimální kostra ohodnoceného grafu. Jarníkův a Kruskalův algoritmus a jejich implementace.

12. Algoritmy hledání nejkratších cest v ohodnoceném grafu.

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. Řadící algoritmy O(n^2).

4. Binární haldy. Nafukovací pole, amortizovaná složitost.

5. Binomiální haldy.

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

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í.

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

Cíle studia:

Studenti se naučí techniky důkazů korektnosti jednotlivých základních algoritmů a techniky asymptotické matematiky pro určování jejich složitostí v nejlepším, nejhorším, či průměrném případě. Student rozumí prezentovaným algoritmům a datovým strukturám a je schopný je upravit a aplikovat pro příbuzné problémy.

Studijní materiály:

Česká literatura:

1. J. Matoušek, J. Nešetřil: Kapitoly z diskrétní matematiky, Karolinum, Praha, 2010.

2. M. Mareš, T. Valla: Průvodce labyrintem algoritmů (2. vydání), CZ.NIC, Praha, 2022. https://knihy.nic.cz/

3. J. Demel: Grafy a jejich aplikace, vlastním nákladem, 2015. (dostupné v PDF z https://kix.fsv.cvut.cz/~demel/grafy/)

4. P. Hliněný: Základy teorie grafů pro (nejen) informatiky, skripta FI MUNI ke stažení z webu (https://is.muni.cz/do/rect/el/estud/fi/js10/grafy/Grafy-text10.pdf).

5. P. Kovář: Diskrétní matematika a úvod do teorie grafů - Řešené příklady k procvičeni, dostupné ke stažení (zadání https://homel.vsb.cz/~kov16/files/dim_priklady.pdf a řešení https://homel.vsb.cz/~kov16/files/dim_priklady_resene.pdf)

Anglicky psaná literatura

1. T. H. Cormen, C.E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms. Fourth edition, MIT Press, 2022.

2. K. Mehlhorn, P. Sanders: Algorithms and Data Structures: The Basic Toolbox. Springer 2008.

Poznámka:
Další informace:
https://courses.fit.cvut.cz/BI-AG1
Rozvrh na zimní semestr 2023/2024:
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
Opler M.
11:00–12:30
(přednášková par. 1)
Dejvice
NTK Ballingův sál
místnost T9:346
Smutný J.
12:45–14:15
(paralelka 1)
Dejvice
NBFIT učebna
místnost TH:A-1247
Valla T.
14:30–16:00
(paralelka 3)
Thákurova 7 (budova FSv)
seminární místnost
místnost T9:302
Dvořák M.
16:15–17:45
(paralelka 5)
Dejvice
NBFIT učebna
místnost TH:A-1247
Šofr O.
18:00–19:30
(paralelka 7)
Thákurova 7 (budova FSv)
seminární místnost
místnost T9:346
Smutný J.
14:30–16:00
(paralelka 4)
Dejvice
NBFIT učebna
místnost TH:A-1247
Šofr O.
16:15–17:45
(paralelka 6)
Thákurova 7 (budova FSv)
seminární místnost
místnost T9:302
Dvořák M.
18:00–19:30
(paralelka 8)
Dejvice
NBFIT učebna
místnost TH:D-1122
Knop D.
14:30–16:00
(přednášková par. 2)
Thákurova 7 (budova FSv)
D1122
Út
St
místnost TH:A-1242
Slávik M.
09:15–10:45
(paralelka 9)
Thákurova 7 (budova FSv)
místnost TH:A-1242
Slávik M.
11:00–12:30
(paralelka 10)
Thákurova 7 (budova FSv)
místnost TH:A-1247
Hušek R.
16:15–17:45
(paralelka 11)
Thákurova 7 (budova FSv)
seminární místnost
místnost TH:A-1247
Hušek R.
18:00–19:30
(paralelka 12)
Thákurova 7 (budova FSv)
seminární místnost
místnost T9:343
Nguyen X.
18:00–19:30
(paralelka 13)
Dejvice
NBFIT učebna
Čt
místnost T9:347
Mertlová J.
07:30–09:00
(paralelka 14)
Dejvice
NBFIT učebna
místnost TH:A-1247
Knop D.
09:15–10:45
(paralelka 16)
Thákurova 7 (budova FSv)
seminární místnost
místnost TH:A-1247
Knop D.
07:30–09:00
(paralelka 15)
Thákurova 7 (budova FSv)
seminární místnost

místnost T9:347
Sedláček J.
07:30–09:00
(paralelka 17)
Dejvice
NBFIT učebna
místnost T9:346
Opler M.
09:15–10:45
(paralelka 19)
Dejvice
NBFIT učebna
místnost T9:343
Suchý O.
11:00–12:30
(paralelka 21)
Dejvice
NBFIT učebna
místnost T9:301
Catay S.
12:45–14:15
(paralelka 23)
Dejvice
NBFIT učebna
místnost T9:346
Opler M.
07:30–09:00
(paralelka 18)
Dejvice
NBFIT učebna
místnost T9:343
Suchý O.
09:15–10:45
(paralelka 20)
Dejvice
NBFIT učebna
místnost T9:301
Catay S.
11:00–12:30
(paralelka 22)
Dejvice
NBFIT učebna
Rozvrh na letní semestr 2023/2024:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 17. 6. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet6546906.html