Týden | Náplň | Materiály | Videa | Domácí cvičení |
1 | Indukce. | Matematická indukce - příklady ze cvičení. | Nejsou. | Velmi podrobně dokažte matematickou indukcí první rovnost z Úlohy 2 v tomto souboru. Zde je řešení domácího cvičení (a jako bonus i řešení nerovnosti z Úlohy 2). |
2 | Přirozená dedukce. | Přirozená dedukce - příklady ze cvičení. Příklady k procvičení přirozené dedukce i s řešením. | Videocvičení z přirozené dedukce 0, Videocvičení 1, Videocvičení 2, Videocvičení 3 | Sestrojte důkaz sekventu a ∨ b, b ⇒ (¬ c ∨ e), a ⇒ (¬c ∨ d) ⊢ c ⇒ (e ∨ d).
Sestrojte důkaz sekventu ⊢ ((a ⇒ b) ⇒ a) ⇒ a.
Řešení první úlohy. Řešení druhé úlohy. |
3 | Sémantika výrokové logiky. | Sémantika výrokové logiky. Příklady k procvičení sémantiky výrokové logiky. | Splnitelnost, tautologie. ÚSS. Velká konjunkce. De Morgan. Převod do CNF. CNF z tabulky. Splnitelnost. Sémantický důsledek. Sémantický důsledek 2. | Zahrajte si https://nandgame.com/ a vyřešte všechny úlohy z úrovně Logic Gates: Nand, Invert, And, Or, Xor. |
4 | Test z výrokové logiky. | Ukázkový test. | | |
5 | Úvod do predikátové logiky. | Základy predikátové logiky - příklady ze cvičení. Řešení. Příručka pro formalisaci tvrzení v predikátové logice. (Stanford, v angličtině.) | Nejsou. | Vyřešte úlohy z tohoto PDF. Výsledky s částečným řešením naleznete zde. |
6 | Sémantika predikátové logiky. | Sémantika predikátové logiky - příklady ze cvičení. Řešení. Příklady k procvičení sémantiky predikátové logiky. | Nejsou. | Vyřešte úlohy z tohoto PDF. |
7 | Přirozená dedukce. | Přirozená dedukce v PL - příklady ze cvičení. Sbírka základních úloh z přirozené dedukce v PL. Řešení. | Nejsou. | Sestrojte důkaz sekventu ∀x(∃y(M(x,y) ∨ M(y,x)) ⇒ M(x,x)), ∃x∃yM(x,y) ⊢ ∃xM(x,x)
(Každý, kdo miluje či je milován, miluje sám sebe. Někdo někoho miluje. Tedy někdo miluje sám sebe.) |
8 | Přirozená dedukce. | Úlohy na pokročilou formalisaci a přirozenou dedukci v PL. Řešení. | Nejsou. | Formalisujte a proveďte důkazy všech úsudků z materiálů k tomuto týdnu. Vypracujte ukázkový test z PL. |
9 | Test z predikátové logiky. | Ukázkový test. Stručné řešení ukázkového testu. Řešení úlohy z přirozené dedukce. | | |
10 | Grafy - základní úlohy. | Grafy - příklady ze cvičení. | Hyperkrychle. Regulární grafy. Dostupnost je relace ekvivalence. Zkrácení sledu na cestu. Vzdálenost je metrika.Počet sledů dané délky. Hodnost matice incidence. | |
11 | Stromy a eulerovské grafy. | Stromy, eulerovské grafy - příklady ze cvičení. | Stromy: mezi dvěma vrcholy právě jedna cesta. Stromy: minimálně souvislé. Stromy: maximální bez kružnic. Minimální kostra: Kruskal. Minimální kostra: Jarník. Hledání eulerovského tahu. Kreslení více tahy. Rozklad na kružnice. | |
12 | Barvení grafů. | Barevnost, nezávislost, dominance. | Sekvenční barvení: příklad. | |
13 | Orientované grafy. | Orientované grafy - příklady ze cvičení. | Prohledávání do hloubky: příklad. DFS: pseudokód. DFS: Python. Topologické očíslování: příklad. Jádro: příklad. | Prostudujte algoritmus DFS. Můžete se např. podívat na videa Prohledávání do hloubky: příklad. DFS: pseudokód. DFS: Python. |
14 | Reserva. | | | |