# Magisterské státnice z informatiky ## Diskrétní modely a algoritmy - Poznámky 2024/25 Cyril Kotecký (je to polotovar, jsou tam chybky): ![pdf](/Magisterské státnice z informatiky/diskretni-mgr-kotecky.pdf) - Poznámky 2025/26 Filip Kastl (pouze Grafové algoritmy): ![pdf](/Magisterské státnice z informatiky/diskretni-mgr-grafove-kastl.pdf), [github](https://github.com/Pheeck/mff-statnice-grafove-algoritmy) (opravy vítány) - Poznámky 2025/26 Filip Úradník: ![pdf](/Magisterské státnice z informatiky/diskretni-mgr-uradnik.pdf), [aktuální verze](https://gitlab.mff.cuni.cz/uradnikf/bc_lec/-/jobs/artifacts/master/raw/out/2526l_mgr_statnice.pdf?job=build), [mff gitlab](https://gitlab.mff.cuni.cz/uradnikf/bc_lec/-/tree/master/2526l/mgr_statnice?ref_type=heads) Btw, nikdo neví, co se má člověk učit na podtéma "Nelineární optimalizační problémy s podmínkami celočíselnosti." Asi branch and bound a možná zmínit, jak se dají nelineární celočíselné podmínky někdy přepsat na lineární celočíselné (např. násobení dvou 0/1 proměnných). ## Ostatní programy - *Taky sem přispějte svoje poznámky!* ## Jednotlivé dojmy ### Diskrétní modely a algoritmy - 12. června 2026 Ve stejný den byly obhajoby diplomových prací i ústní zkouška. Od 9:00 ráno probíhaly obhajoby. Pak studenti odešli z místnosti a komise se dohodla na hodnocení diplomek a připravila si otázky k ústnímu zkoušení. Ústní zkoušení pak trvalo ~4h, ale první student odešel (úspěšně) už po 2-3h. Nebyl stanovaný žádný horní limit na délku zkoušky. Jenom v nějakém bodě už člověk začíná pozorovat, jak ostatní studenti odcházejí a říká si, že zkoušející by třeba už radši byli někde jinde (ale zkoušející byli vřelí a nepřipadalo mi, jako by dávali najevo nějakou netrpělivost). Zkoušeli doc. Klazar, prof. Tancer a prof. Loebl. Obešli nás a každému zadali konkrétní podtémata studentových okruhů. Tedy např. já jsem měl Složitostní třídy a jejich vztahy od Tancera, Vyhledávací stromy ((a,b), splay), Intervalové soustavy a "Tak nějak obecné celočíselné programování, řekněte mi třeba něco o unimodularitě a celočíselných/racionálních polyhedrech" od Loebla a Testování planarity grafů od Klazara. Hranice toho, co je vlastně "podtéma" a tedy co vám může zkoušející zadat jsou takové vágní, zdá se mi. Pak jsme měli čas psát ke každému tématu, co víme. Bylo hodně na nás, o čem se rozepíšeme. Měli jsme se ozvat, když jsme s nějakým tématem byli hotovi a přišel za námi odpovídající zkoušející a pročetl si naše papíry. Někteří zkoušející chtěli, abychom jim trochu text slovně komentovali, jiní naopak chtěli, aby vše ideálně prostě bylo na papíře. Když zkoušející uznal za vhodné (záleželo na kvalitě textu a na stylu zkoušejícího), doptával se na nějaké další otázky, třeba i odešel a nechal studenta odpověď na svou otázku v klidu sepsat. Všichni studenti byli zkoušeni simultánně. Byli jsme instruováni, abychom okruhy řešili v předepsaném pořadí (asi aby se simultánní zkoušení zkoušejícím lépe organizovalo/paralelizovalo). [Zde](https://www.mff.cuni.cz/cs/studenti/bc-a-mgr-studium/statni-zaverecne-zkousky/magisterske-statni-zkousky-studijniho-programu-informatika) se píše, že > Přiměřená znalost technických detailů může být vyžadována tam, kde > je nezbytná pro doložení pochopení základních principů. Můžu dosvědčit, že opravdu tak nějak to bylo. Důkazů jsem vlastně moc nesepsal. On na to totiž ani nebyl moc čas. Máte méně než hodinu na podtéma a podstatný kus zabijete už jenom úvodem do problematiky a urovnáváním si myšlenek. Není šance, že byste např. popsali Boyer-Myrvoldové algoritmus na planaritu grafů se všemi detaily natož abyste ještě dokazovali jeho korektnost. V tom konkrétním případě jsem prostě algoritmus popisoval dostatečně dlouho, než zkoušející uznal, že se orientuji. Ale nějaké hlavní myšlenky důkazů nebo náznaky větších důkazů jsem napsal. Třeba jsem ukázal (v jiném podtématu), že unimodularita implikuje celočíselné vrcholy. > Zkouška má přehledový charakter – hodnocení se soustředí na pochopení > základních principů tématu, u kterých se vyžaduje odpovídající schopnost > vyjadřování (formálně přesné definice a tvrzení, technicky správná > terminologie, používání obvyklých notací) a vnímání souvislostí včetně > aplikací. Tenhle výňatek taky odpovídá mému zážitku. Určitě se vyplatí znát dobře základní definice, věty, problémy a dokazovací techniky z daného okruhu. A taky je dobré mít i přehled o pokročilejších věcech a souvislostech. Zaprvé chcete umět napsat aspoň něco ke každému podtématu a zadruhé nechcete být ztracení, když se vás na něco zkoušející doptá. Sice to neumím dokázat, ale hodilo se mi vědět, že Chvátal rank každého racionálního polyhedru je konečný (já teda trochu tušil už před zkouškou, že prof. Loebl mě nejspíš bude zkoušet z celoč. prog. a že zvlášť o Chvátalovy řezy by se mohl zajímat a pak jsem je schválně name-dropnul v přípravě (a pak jsem napsal špatně jejich definici, :D)). ### Softwarové a datové inženýrství - circa zimní termín 2025/2026 Píšu svou zkušenost ze státnic z oboru Softwarové a datové inženýrství (na zkoušce jsme byli jen 3 studenti a 3 zkoušející, takže se to v jiných případech může lišit). V místnosti byla určena místa k sezení, po usazení přišli postupně 3 různí zkoušející se seznamem témat ze studijního plánu, každý měl na starost jeden z okruhů a vybral konkrétní téma. Po zadání témat jsme měli 30 minut na vypracování otázky, následovalo cca 15 minut diskuze se zkoušejícím, který měl spíše doplňující otázky k tomu, co jsme si připravili. Potom zkoušející řekl buď známku, nebo informaci, že mu to stačí (předpokládám, že to by bylo za 1). Tohle se opakovalo třikrát s různými zkoušejícími - tedy by se dalo říct 3x45min. Po posledním zkoušení (někdy po 11. hodině, začátek byl v 9) jsme šli na chvíli na chodbu a poté jsme se od komise dozvěděli výslednou známku. Celkově mi přišlo hodnocení vstřícné a zkoušející byli velmi příjemní. Do detailů se moc nezabíhalo, spíše šlo o celkový přehled.