Co by studenti a studentky měli znát a umět? Znát pojmy z přednášek a jejich definice, umět s danými pojmy pracovat. Chápat rozdíl mezi syntaxí a sémantikou. Umět rozhodovat o vlastnostech formulí a vztazích mezi nimi. Podrobněji:

• Rozumět syntaxi výrokové logiky. Umět rozhodnout, které řetězce symbolů jsou formule výrokové logiky a které ne. Umět sestavit syntaktický strom formule, a umět ze syntaktického stromu sestavit formuli. Vědět, co je hloubka formule, vědět, co je podformule.
• Ovládat přirozenou dedukci ve výrokové logice. Znát odvozovací pravidla a umět je použít v důkazech. Rozumět rámečkům (boxům) a jejich významu v důkazech.
• Rozumět sémantice výrokové logiky. Znát pravdivostní tabulky logických spojek. Vědět, co je pravdivostní ohodnocení. Umět na základě ohodnocení atomů rozhodnout o ohodnocení jakékoli formule výrokové logiky. Umět vyplnit pravdivostní tabulku libovolné formule výrokové logiky.
• Vědět, co je splnitelná formule, tautologie, kontradikce. Umět u formule výrokové logiky rozhodnout, zda je splnitelná, zda je to tautologie či kontradikce. Vědět, co je splnitelná množina formulí.
• Vědět, co je sémantická ekvivalence formulí, umět rozhodnout, zda je dvojice formulí sémanticky ekvivalentní. Vědět, že sémantická ekvivalence je relace ekvivalence.
• Znát pojem sémantického důsledku a rozumět mu. Umět rozhodnout, zda je daná formule sémantickým důsledkem dané množiny formulí.
• Pro danou formuli výrokové logiky umět nalézt sémanticky ekvivalentní formuli v disjunktivní, konjunktivní a negační normální formě.
• Znát znění věty o korektnosti a úplnosti pro VL. Chápat význam této věty.
• Chápat rozdíl mezi syntaxí a sémantikou.

• Rozumět syntaxi predikátové logiky. Vědět, jak se tvoří termy a formule predikátové logiky a znát rozdíl mezi nimi. Umět rozhodnout, které řetězce symbolů jsou formule jazyka predikátové logiky a které ne. Umět sestavit syntaktický strom termu či formule, a umět ze syntaktického stromu sestavit term či formuli. Umět rozpoznat volné a vázané výskyty proměnné ve formuli.
• Rozumět substituci, umět ve formuli substituovat term za proměnnou. Umět rozpoznat, kdy je term volný pro proměnnou v dané formuli.
• Ovládat přirozenou dedukci v predikátové logice. Znát odvozovací pravidla a umět je použít v důkazech. Umět správně používat deklarace proměnných a svědků. Chápat roli rámečků (boxů) pro obory platnosti (scope) proměnných.
• Rozumět sémantice PL. Rozumět pojmu interpretace jazyka PL, umět interpretace tvořit. Znát pojem kontextu proměnných. Umět vyhodnotit (evaluovat) term v dané interpretaci a kontextu. Umět vyhodnotit pravdivost formule v dané interpretaci a kontextu. Chápat pojem pravdivosti sentence v interpretaci, umět o pravdivosti sentence v interpretaci rozhodnout. Umět nalézt význam formule (s volnými proměnnými). Znát pojem model sentence.
• Znát pojem splnitelná sentence, tautologie, kontradikce. Umět rozhodnout, které z těchto vlastností sentence má. Znát pojem splnitelnosti množiny sentencí, umět rozhodnout, zda je množina sentencí splnitelná.
• Znát pojem sémantického důsledku v PL a rozumět mu. Umět pro sentenci rozhodnout, zda je sémantickým důsledkem množiny formulí. Znát pojem sémantické ekvivalence, umět u dvojice sentencí PL rozhodnout, zda jsou sémanticky ekvivalentní.
• Znát znění věty o korektnosti a úplnosti pro PL. Chápat význam této věty.
• Chápat rozdíl mezi syntaxí a sémantikou.

Rozhodněte, které z následujících formulí jsou sémanticky ekvivalentní formuli (a \/ b) => ~ c.

• c => ~(a \/ b).
• (a => ~b) => c.
• ~c => (a \/ b).
• ((a \/ b) \/ ~c).
• c => (a /\ ~b).

Rozhodněte, které z následujících sentencí predikátové logiky jsou tautologie. (Pracujeme s jazykem, který nemá žádné predikátové, funkční ani konstantní symboly.)

• forall x exists y (x = y).
• exists y forall x (x = y).
• forall x forall y (x = y).
• exists x exists y (x = y).
• forall y exists x (x = y).

Co by studenti a studentky měli znát a umět? Ve zkratce: znát pojmy z přednášek a jejich definice, umět s danými pojmy pracovat. Znát a umět použít algoritmy probrané na přednáškách. Znát základní výsledky z přednášek a umět je využít. Umět sestrojit graf se zadanými vlastnostmi (a případně být schopni rozhodnout, že takový graf neexistuje). Explicitně:

• Znát různé definice pojmu (neorientovaného) grafu a chápat, v čem se liší. Umět sestrojit graf s požadovanou strukturou (počet vrcholů a hran).
• Znát pojem podgrafu, faktoru, podgrafu indukovaného množinou vrcholů. Chápat, v čem se dané pojmy liší, umět je využívat.
• Znát pojem stupně vrcholu v grafu, handshaking lemma, požadavky na počet vrcholů lichého stupně v grafu. Umět sestrojit jednoduché instance grafů s požadovanou strukturou (předepsané stupně vrcholů).
• Znát pojem isomorfismu grafů. Umět u jednoduchých instancí rozhodnout, zda jsou grafy isomorfní či nikoli. Umět sestrojit několik neisomorfních grafů s požadovanou strukturou.
• Znát pojem kružnice, umět rozhodnout, zda zadaný graf obsahuje kružnici.
• Znát pojmy sled, tah, cesta. Umět rozhodnout, zda je něco sled, tah, cesta.
• Znát pojem souvislosti grafu. Umět rozhodnout, zda je zadaný graf souvislý.
• Znát pojem komponenty souvislosti. Umět sestrojit graf s požadovaným počtem komponent souvislosti (a dalšími omezeními).
• Znát pojem vzdálenosti dvou vrcholů. Umět sestrojit graf se zadanými omezeními na vzdálenosti vrcholů.
• Znát pojem eulerovského grafu. Umět sestrojit eulerovský/neeulerovský graf (s danými vlastnostmi), umět o zadaném grafu rozhodnout, zda je či není eulerovský.
• Znát definici stromu, znát vlastnosti stromů. Umět rozhodnout, zda je zadaný graf stromem či nikoli. Umět sestrojit strom o daných vlastnostech (počet listů, vrcholů daného stupně apod.).
• Znát pojem kostry grafu. Umět rozhodnout, zda zadaný graf má kostru či nikoli, umět kostru grafu sestrojit.
• Znát pojem minimální kostry ohodnoceného grafu. (Znát pojem ohodnoceného grafu.) Umět nalézt minimální kostru ohodnoceného grafu.
• Znát pojem obarvení grafu, k *barevnosti, barevnosti grafu. Umět u jednoduchých příkladů rozhodnout o barevnosti grafu. Umět sestrojit graf s danou barevností a dalšími omezeními (jednoduché příklady). Znát a umět použít algoritmus sekvenčního barvení, znát jeho vlastnosti.
• Znát pojem nezávislé množiny v grafu. Znát pojem nezávislosti grafu a základní vlastnosti nezávislosti. Umět najít nezávislost grafu (pro jednoduché příklady), rozhodnout, zda je daná množina vrcholů nezávislá. Umět sestrojit graf s danou nezávislostí (a dalšími omezeními).
• Znát pojem kliky a klikovosti. Umět pro jednoduché příklady grafů nalézt jejich klikovost. Umět nalézt v grafu kliky. Umět sestrojit graf s danou klikovostí a dalšími omezeními (jednoduché příklady).
• Znát různé definice pojmu orientovaného grafu a chápat, v čem se liší. Umět sestrojit orientovaný graf s požadovanou strukturou (počet vrcholů a hran).
• Znát pojem vstupního a výstupního stupně vrcholu v orientovaném grafu. Umět sestrojit orientovaný graf s danou strukturou stupňů vrcholů. Vědět, jak struktura stupňů vrcholů ovlivňuje vlastnosti orientovaného grafu.
• Znát pojem orientovaného sledu, tahu, cesty. Znát pojem cyklu, chápat rozdíl mezi kružnicí a cyklem. Znát pojem orientované dostupnosti.
• Znát pojem silné souvislosti. Znát pojem silně souvislé komponenty. Umět sestrojit graf se zadanými vlastnostmi týkajícími se orientované dostupnosti (např. graf s daným počtem silně souvislých komponent, který splňuje další vlastnosti). Umět pro jednoduché instance nalézt silně souvislé komponenty orientovaného grafu.
• Znát pojem kondensace orientovaného grafu. Umět pro jednoduché instance zkonstruovat kondensaci zadaného orientovaného grafu.
• Znát pojem kořene orientovaného grafu. Znát pojem kořenového stromu. Umět zakořenit neorientovaný strom, umět zkonstruovat orientovaný kořenový strom s danými vlastnostmi.
• Znát pojem acyklického grafu. Znát základní vlastnosti acyklických grafů, umět sestrojit acyklický graf s danými vlastnostmi. Znát pojem topologického očíslování. Umět nalézt topologické očíslování zadaného grafu.
• Umět v jednoduchých případech kombinovat znalosti a schopnosti zmíněné výše.
• Umět v jednoduchých případech rozhodnout, zda graf se zadanými vlastnostmi vůbec sestrojit lze.

Rozhodněte, která z následujících tvrzení jsou pravdivá:

• Každý silně souvislý orientovaný graf obsahuje cyklus.
• Každý orientovaný graf o 10 vrcholech, který má přesně dvě silně souvislé komponenty, obsahuje alespoň 11 hran.
• Každý orientovaný graf G má více vrcholů, než má kondensace grafu G.
• Pro každý orientovaný graf G platí: Pokud je každá hrana v G součástí nějakého cyklu, pak je G silně souvislý.
• Žádný acyklický graf není silně souvislý.

Rozhodněte, která z následujících tvrzení jsou pravdivá:

• Lze zkonstruovat graf o 12 vrcholech, který má klikovost 5 a nezávislost 8.
• Každý graf s barevností 6 má nezávislost alespoň 6.
• Pokud algoritmus sekvenčního barvení obarvil graf G osmi barvami, pak jeho barevnost nemůže být menší než 4.
• Každý graf s klikovostí 5 má barevnost 5.
• Existují alespoň dva neisomorfní grafy se čtyřmi vrcholy, které mají barevnost 3.

Je zadán ohodnocený graf G (množinou vrcholů a seznamem hran spolu s cenou). Pokud má minimální kostru, zapište její cenu a množinu hran, která ji tvoří. Pokud minimální kostru nemá, odpovězte “G nemá minimální kostru.”

Zde je několik příkladů, které se vyskytly v minulých letech ve zkouškových písemkách. Nepokrývají nutně všechny typy příkladů, které můžete u zkoušky potkat, a uvedené počty bodů u daných příkladů již nejsou relevantní.

• Několik typických příkladů, které se mohou objevit v minimální části.
• Neformálně komentované řešení jednoho zadání z minimální části.
• Několik typických příkladů, které se mohou objevit ve standardní části.