Rozvrh denně dopoledne 9.00 - 11.45, odpoledne 12.30 - 14.30, 14.45 - 16.00.
. Úpravy možné po dohodě s lektorem.
Učebny:
E-301 – výklad od 9:00 a od 12.30
E-132 a E-230 – praktika od cca 10:00 a od cca 13:30.
Vše v budově E v areálu FEL ČVUT na Karlově náměstí.
____________________________________________________________________________________________
Vedou Filip Kubiš a Michal Kučera.
Na praktikách asistují Daniel Aschermann, Jan Blaha, Martin Rýpar, Alexandr Zemek.
Slidy: Úvodní grafový přehled ( pdf).
Vzorová úloha Lokální zpracování a prohledávání grafu, bezprostřední okolí vrcholů grafu, typická úloha: počet trojúhelníků.
Úloha 1.
Načtěte nevážený graf ze souboru a vypište k každému uzlu jeho seznam hran. Stáhněte si data s obrázky.
Úloha 2.
Načtěte vážený graf ze souboru a vypište k každému uzlu jeho seznam hran. Stáhněte si data s obrázky.
Úloha 3.
V daném grafu zjistěte pro každý možný stupeň uzlu D, kolik je takových hran, jejichž oba koncové uzly mají tento stupeň D. Pro každý stupeň tento počet hran vypište. Porovnejte své výsledky s ukázkovými. Stáhněte si data s obrázky.
Úloha 4.
Jindra vyrazí z uzlu A, který má určitý stupeň D. Pak jde do některého jeho sousedního uzlu B a nezajímá se o stupeň uzlu B. Z uzlu B se přesune do uzlu C, který je sousedem B a není to A. Jindra trvá na tom, že stupeň D startovního uzlu A i stupeň cílového uzlu C musejí být stejné. Určete, kolik je v daném grafu možností procházek podle Jindrových pravidel. Vypište toto jediné číslo na výstup. Stáhněte si data s obrázky.
Úloha 5.
Řekneme, že hrana H je lokálně minimální, pokud její váha je striktně menší než váha kterékoli hrany, která s H sdíli jeden uzel. Najděte v daném váženém grafu všechny lokálně minimální hrany a vypište je v rostoucím lexikografickém pořadí jejich krajních uzlů. Stáhněte si data s obrázky.
Úloha 6.
Určete, kolik je trojúhelníků v každém grafu úlohy 4. Trojúhelník je trojice uzlů, v níž každý uzel sousedí se zbylými dvěma uzly.
Úloha 7.
Určete, kolik je kružnic délky 4 v každém grafu úlohy 4. Kružnice nesmí obsahovat příčku, tj. první a třetí uzel v kružnici nesmí spolu sousedit a druhý a čtvrtý uzel v kružnici spolu nesmí sousedit.
Další úložky:
____________________________________________________________________________________________
Vede Petr Ryšavý.
Na praktikách asistují Martin Rýpar, Alexandr Zemek.
Slidy: Prohledávání grafu
seq.txt
. Na každém řádku máte jeden z příkazů insert <number>
a remove
. Příkaz insert <number>
vloží číslo <number>
do zásobníku. Příkaz remove
odstraní prvek ze zásobníku a vypíše ho na standardní výstup.
graph.txt
jako neorientovaný graf. Ten je definovaný ve stejném formátu jako včera.
graph.txt
jako orientovaný graf.
____________________________________________________________________________________________
Vede Petr Ryšavý
Na praktikách asistují Martin Rýpar, Alexandr Zemek.
Slidy: Prioritní fronta, halda
Poučení:
Úkoly:
remove
chápejte jako extract-min
.
extract-min
hledejte minimum naivně pomocí procházení celého pole.
seq.txt
, operace remove
ignorujte.
Další úlohy:
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3644
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1895
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3146
____________________________________________________________________________________________
Vede Petr Ryšavý
Na praktikách asistují Daniel Aschermann, Jan Blaha.
Poučení
Slidy: Dijkstrův algoritmus
Data pro testování Dijkstry: txt, výsledek (jako pro neorientovaný graf), implementace v Javě (2018) a Pythonu (2019).
____________________________________________________________________________________________
Vede Petr Ryšavý
Na praktikách asistují Daniel Aschermann, Jan Blaha.