Logo ČVUT
Loading...
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2024/2025
Fakulty | Celoškolská nabídka volitelných předmětů | Katalog předmětů ECTS | Nastavení | English version
Úvodní stránka > Fakulta informačních technologií > katedra teoretické informatiky > Algoritmy a grafy 1

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, Patrik Drbal, Michal Dvořák, Radek Hušek, Dušan Knop, Daniel Král, Michal Opler, Matěj Ptáček, Josef Erik Sedláček, Martin Slávik, Ondřej Suchý, Ondřej Šofr, Petr Šťastný, 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 2024/2025:
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.
09:15–10:45
(přednášková par. 1)
Dejvice
NTK Ballingův sálmístnost TH:A-1247
Dvořák M.
11:00–12:30
(paralelka 1)
Thákurova 7 (budova FSv)
seminární místnostmístnost T9:302
Slávik M.
12:45–14:15
(paralelka 2)
Dejvice
NBFIT učebnamístnost T9:302
Slávik M.
14:30–16:00
(paralelka 3)
Dejvice
NBFIT učebnamístnost TH:A-1242
Ptáček M.
16:15–17:45
(paralelka 4)
Thákurova 7 (budova FSv)místnost TH:A-1242
Ptáček M.
18:00–19:30
(paralelka 5)
Thákurova 7 (budova FSv)
místnost TK:BS
Knop D.
16:15–17:45
(přednášková par. 2)
Dejvice
NTK Ballingův sálmístnost TH:A-1247
Dvořák M.
18:00–19:30
(paralelka 6)
Thákurova 7 (budova FSv)
seminární místnost
Út
místnost T9:301
Catay S.
07:30–09:00
(paralelka 7)
Dejvice
NBFIT učebnamístnost TH:A-1247
Knop D.
09:15–10:45
(paralelka 9)
Thákurova 7 (budova FSv)
seminární místnostmístnost T9:302
Valla T.
11:00–12:30
(paralelka 10)
Dejvice
NBFIT učebnamístnost TH:A-942
Král D.
12:45–14:15
(paralelka 11)
Thákurova 7 (budova FSv)
místnost TH:A-1247
Knop D.
07:30–09:00
(paralelka 8)
Thákurova 7 (budova FSv)
seminární místnost
St
místnost T9:347
Hušek R.
16:15–17:45
(paralelka 12)
Dejvice
NBFIT učebnamístnost T9:347
Hušek R.
18:00–19:30
(paralelka 13)
Dejvice
NBFIT učebna
Čt
místnost T9:301
Sedláček J.
07:30–09:00
(paralelka 14)
Dejvice
NBFIT učebnamístnost T9:301
Sedláček J.
09:15–10:45
(paralelka 16)
Dejvice
NBFIT učebnamístnost T9:347
Šofr O.
16:15–17:45
(paralelka 18)
Dejvice
NBFIT učebnamístnost T9:347
Šofr O.
18:00–19:30
(paralelka 20)
Dejvice
NBFIT učebna
místnost T9:347
Drbal P.
07:30–09:00
(paralelka 15)
Dejvice
NBFIT učebnamístnost T9:347
Drbal P.
09:15–10:45
(paralelka 17)
Dejvice
NBFIT učebnamístnost TH:A-1247
Šťastný P.
16:15–17:45
(paralelka 19)
Thákurova 7 (budova FSv)
seminární místnost
Pá
místnost TH:A-1442
Suchý O.
12:45–14:15
(paralelka 22)
Thákurova 7 (budova FSv)
Rozvrh na letní semestr 2024/2025:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 24. 10. 2024
Copyright © Jiří Kosek, 2010–2022 | Copyright © ČVUT, 2010–2022
Provozuje Výpočetní a informační centrum ČVUT
Dotazy a připomínky zasílejte na HelpDesk ČVUT nebo na spravcekos@cvut.cz
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet6546906.html