====== Zápočet a zkouška ====== ===== Požadavky k získání zápočtu ===== ==== Aktivní účast a docházka ==== * Podmínkou získání zápočtu je aktivní účast na cvičení. * Jsou povoleny maximálně čtyři omluvené absence za semestr. ==== Semestrální testy ==== 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**. ==== Domácí úkoly ==== Cvičící mají možnost požadovat domácí práci a zadávat domácí úkoly. ===== Organisace zkoušek a klasifikace ===== ==== Písemná zkouška ==== 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". === Požadavky k minimální a standardní části === * [[courses:b0b01lgr:zapocet_a_zkouska#Minimální znalosti a schopnosti z logiky|Minimum z logické části.]] * [[courses:b0b01lgr:zapocet_a_zkouska#Minimální znalosti a schopnosti z teorie grafů|Minimum z grafové části.]] * {{minimum.pdf|Několik typických příkladů, které se mohou objevit v minimální části.}} * {{minimum-komentar.pdf|Neformálně komentované řešení jednoho zadání z minimální části.}} * {{standard.pdf|Několik typických příkladů, které se mohou objevit ve standardní části.}} Tato část je pravidelně upravována: přidávám zkouškové příklady k procvičení. ==== Klasifikace zkoušky ==== * 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**. ^ Celkový bodový zisk ^ Známka ^ | <50 | F | | 50 - 59 | E | | 60 - 69 | D | | 70 - 79 | C | | 80 - 89 | B | | 90 - 100 | A | ==== Ústní zkouška ==== * Ú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ě. ===== Pokyny k písemné zkoušce ===== * 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ý. ===== Minimální znalosti a schopnosti===== ==== Minimální znalosti a schopnosti z logiky ==== 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. === Několik příkladů možných otázek === == Úloha (2 body, testuje schopnost detekovat sémantickou ekvivalenci) == 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)%%. == Úloha (2 body, testuje schopnost detekovat tautologie) == 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)%%. ==== Minimální znalosti a schopnosti z teorie grafů ==== 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. === Několik příkladů možných otázek === == Úloha (2 body, testuje porozumění silné souvislosti) == 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ý. == Úloha (2 body, testuje porozumění barevnosti, klik, nezávislých množin) == 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. == Úloha (1 bod, testuje schopnost nalézt minimální kostru) == 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."