Rozvrh denně přibližně dopoledne 9.00 - 11.45, odpoledne 12.30 - 14.30, 14.45 - 16.00.
. Úpravy možné po dohodě s lektorem.
Učebna: E-132 Budova E v areálu FEL ČVUT na Karlově náměstí.
____________________________________________________________________________________________
Vedou Dan Hubáček, Michal Kučera (dopol), Jan Blaha (odpol)
Na praktikách asistují Dan Hubáček, Michal Kučera(dopol), Jan Blaha(odpol), Adéla Atassi
.
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:
K těmto úložkám se lze vracet i později a slouží jako záchytný bod pro ty, kdo už vše zvládli nebo znají z dřívějška apod. Pokaždé je vhodné si úlohu maximálně rozmyslet bez klávesnice a formulovat abstraktně (v grafu daném tak a tak hledáme to či onou pomocí určité metody). Konzultace vlastních nápadů s kolegy (lektory) je doporučena.
____________________________________________________________________________________________
Vedou Jan Blaha, Michal Kučera
Na praktikách asistují DJan Blaha, Michal Kučera, Adéla Atassi
.
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.
____________________________________________________________________________________________
Vedou Dan Hubáček, Jan Blaha
Na praktikách asistují Dan Hubáček, Jan Blaha, Adéla Atassi
.
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
____________________________________________________________________________________________
Vedou Jakub Dupák, Marko Berezovský
Na praktikách asistují Jakub Dupák, Marko Berezovský
.
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).
____________________________________________________________________________________________
Vedou Jakub Dupák, Dan Hubáček
Na praktikách asistují Jakub Dupák, Dan Hubáček
.