Magisterské státnice z informatiky

Diskrétní modely a algoritmy

Poznámky 2024/25 Cyril Kotecký (je to polotovar, jsou tam chybky): pdf
Poznámky 2025/26 Filip Kastl (pouze Grafové algoritmy): pdf, github (opravy vítány)
Poznámky 2025/26 Filip Úradník: pdf, aktuální verze, mff gitlab

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 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.