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

Algoritmy a grafy 1

Zobrazit rozvrh
Kód Zakončení Kredity (ECTS) Rozsah Jazyk výuky
BI-AG1.21 Z,ZK 5 2P+2C česky
Vztahy:
Předmět BI-AG1.21 nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět BIE-AX1.24 (vztah je symetrický)
Předmět je ekvivalentní s BI-AG1,BI-AX1,BIE-AG1,BIE-AG1.21,BIK-AG1,BIK-AG1.21 .
Garant předmětu:
Dušan Knop
Přednášející:
Michal Opler, Tomáš Valla
Cvičící:
Daniel Dvořák, Albert Havliček, Jan Hladký, Emma Hovorková, Radek Hušek, Veronika Jůzková, Dušan Knop, Matěj Kříž, Jiří Kvapil, Michal Opler, Matěj Ptáček, Josef Erik Sedláček, Ondřej Suchý, Jakub Švec, Tomáš Valla, Jan Volec
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:

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 2026/2027:
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
Valla T.
09:15–10:45
(přednášková par. 1)
Dejvice
NTK Ballingův sálmístnost TH:A-942
Švec J.
12:45–14:15
(paralelka 1)
Thákurova 7 (budova FSv)místnost TH:A-942
Švec J.
14:30–16:00
(paralelka 2)
Thákurova 7 (budova FSv)
místnost T9:347
Dvořák D.
12:45–14:15
(paralelka 10)
Dejvice
NBFIT učebnamístnost TH:A-1247
Hladký J.
14:30–16:00
(paralelka 3)
Thákurova 7 (budova FSv)
seminární místnost
místnost TK:BS
Opler M.
14:30–16:00
(přednášková par. 2)
Dejvice
NTK Ballingův sál
Út
místnost TH:A-1242
Knop D.
07:30–09:00
(paralelka 4)
Thákurova 7 (budova FSv)místnost TH:A-1247
Dvořák D.
11:00–12:30
(paralelka 7)
Thákurova 7 (budova FSv)
seminární místnostmístnost TH:A-1442
Hušek R.
16:15–17:45
(paralelka 8)
Thákurova 7 (budova FSv)místnost TH:A-1442
Hušek R.
18:00–19:30
(paralelka 9)
Thákurova 7 (budova FSv)
místnost T9:346
Sedláček J.
07:30–09:00
(paralelka 5)
Dejvice
NBFIT učebna
St
místnost T9:347
Havliček A.
11:00–12:30
(paralelka 11)
Dejvice
NBFIT učebnamístnost T9:301
Havliček A.
14:30–16:00
(paralelka 13)
Dejvice
NBFIT učebna
místnost TH:A-942
Ptáček M.
11:00–12:30
(paralelka 12)
Thákurova 7 (budova FSv)místnost T9:346
Ptáček M.
14:30–16:00
(paralelka 14)
Dejvice
NBFIT učebna
Čt
místnost T9:302
Hovorková E.
07:30–09:00
(paralelka 15)
Dejvice
NBFIT učebnamístnost T9:302
Hovorková E.
09:15–10:45
(paralelka 17)
Dejvice
NBFIT učebna
místnost T9:346
Jůzková V.
07:30–09:00
(paralelka 16)
Dejvice
NBFIT učebnamístnost T9:346
Jůzková V.
09:15–10:45
(paralelka 18)
Dejvice
NBFIT učebna
Pá
místnost TH:A-942

07:30–09:00
(paralelka 19)
Thákurova 7 (budova FSv)místnost TH:A-942
Kvapil J.
11:00–12:30
(paralelka 23)
Thákurova 7 (budova FSv)
místnost TH:A-1242
Kříž M.
07:30–09:00
(paralelka 20)
Thákurova 7 (budova FSv)místnost TH:A-942
Kvapil J.
09:15–10:45
(paralelka 21)
Thákurova 7 (budova FSv)
místnost TH:A-1242
Kříž M.
09:15–10:45
(paralelka 22)
Thákurova 7 (budova FSv)
Rozvrh na letní semestr 2026/2027:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 14. 10. 2026
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 ServiceDesk ČVUT nebo na spravcekos@cvut.cz
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet6546906.html