Zápočet a zkouška

• Podmínkou získání zápočtu je aktivní účast na cvičení.
• Jsou povoleny maximálně čtyři omluvené absence za semestr.

V průběhu semestru budete psát dva testy. Zde se o semestrálních testech dozvíte přesnější informace.

• Testy proběhnou na cvičení, trvání každého testu je 40 minut.
• První test (z logiky) proběhne v desátém týdnu a je hodnocen 0 až 15 body.
• Druhý test (z teorie grafů) proběhne ve čtrnáctém týdnu a je hodnocen 0 až 15 body.
• Testy nebudou mít možnost opravy.
• Student či studentka má možnost nahradit test v případě nemoci.
• Obsahem testu z logiky je probraná látka z logiky v rozsahu prvních osmi týdnů výuky.
• Obsahem testu z grafů je probraná látka z teorie grafů vyjma třináctého a čtrnáctého týdne výuky.
• Součet bodů z obou testů tvoří bonus ze semestru.

Cvičící mají možnost požadovat domácí práci a zadávat domácí úkoly.

Písemná zkouška rozdělena na minimální a standardní část, které probíhají za sebou v jednom dni.

• Z minimální části lze získat maximálně 10 bodů, nutno získat alespoň 8 bodů.
• Ze standardní části lze získat maximálně 60 bodů, nutno získat alespoň 20 bodů.
• Minimální část trvá 40 minut.
• Mezi minimální a standardní částí je oddechový čas přibližně 1 hodina.
• Standardní část trvá 120 minut.
• Součet bodů z minimální části a ze standardní části tvoří body z písemné zkoušky.

Tato část textu byla 25. 4. 2023 upravena kvůli překlepu - v jedné větě se místo “minimální a standardní” části mluvilo o “logické a grafové části”.

Minimum z logické části. Minimum z grafové části. Neformálně komentované řešení jednoho zadání z minimální části.

• Klasifikace zkoušky je určena celkovým bodovým ziskem podle následující tabulky a případně modifikována výsledkem ústní zkoušky (viz níže).
• Celkový bodový zisk je součtem bonusu ze semestru a bodů z písemné zkoušky.

• Ústní zkouška probíhá v den náhledu písemné zkoušky (zpravidla dva dny po písemné zkoušce).
• Na ústní zkoušku se student či studentka může přihlásit jen tehdy, když mají celkový bodový zisk alespoň 70 bodů.
• K absolvování ústní zkoušky mohou být vybraní studenti a vybrané studentky vyzváni. V takovém případě je ústní zkouška povinná.
• Ústní zkouška kontroluje, zda u konkrétního studentka či studentky porozumění látce koresponduje s jeho/její písemnou zkouškou. Dále umožňuje zkoušeným ukázat, že jejich znalosti převyšují jejich výkon u písemné zkoušky.
• V případě zásadní neznalosti studenta/studentky může zkoušející na základě ústní zkoušky udělit známku F (nedostatečně).
• Na základě ústní zkoušky může zkoušející vylepšit známku až o dva stupně.

• Ke zkoušce se dostavte alespoň 10 minut před začátkem a připravte si průkaz totožnosti (index, občanský průkaz, pas).
• Ke zkoušce si vezměte dostatečné množství čistých (nečtverečkovaných, apod.) jednotlivých listů formátu A4 (formát velkého sešitu) a psací potřeby (modré nebo černé barvy, písemnou zkoušku není možné psát tužkou).
• Před začátkem písemné zkoušky si pečlivě pročtěte titulní stranu zadání, vyplňte jméno a příjmení a poznamenejte si své unikátní identifikační číslo a termín náhledu písemky.
• Během písemné zkoušky smíte mít na lavici pouze zadání písemky, papíry, na které zkoušku vypracováváte, vytištěná či přepsaná odvozovací pravidla pro přirozenou dedukci, psací potřeby a občerstvení.
• Vše ostatní (včetně mobilního telefonu) dejte do tašky; tašku zavřete a odložte. Mobilní telefon mějte vypnutý.

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í a konjunktivní 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. 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. 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.”