====== Cvičení ======

^ Týden ^ Náplň ^ Materiály ^ Videa ^ Domácí cvičení ^
| 1  | Indukce. | {{indukce-cviceni.pdf|Matematická indukce - příklady ze cvičení.}} | Nejsou. | Velmi podrobně dokažte matematickou indukcí první rovnost z Úlohy 2 {{indukce-priklady.pdf|v tomto souboru}}. {{indukce-ukol.pdf|Zde je řešení domácího cvičení}} (a jako bonus i řešení nerovnosti z Úlohy 2).|
| 2  | Přirozená dedukce. | {{cv-prir-dedukce-vl.pdf|Přirozená dedukce - příklady ze cvičení.}} {{prirozena-dedukce-vl.pdf|Příklady k procvičení přirozené dedukce i s řešením.}} | [[https://www.youtube.com/watch?v=dsd0wyT2Hmc|Videocvičení z přirozené dedukce 0,]] [[https://www.youtube.com/watch?v=ItRlYulie0w|Videocvičení 1]], [[https://www.youtube.com/watch?v=dMO0BJkoj_o|Videocvičení 2]], [[https://www.youtube.com/watch?v=vkqEcKPb9gA|Videocvičení 3]] | Sestrojte důkaz sekventu <code>a ∨ b, b ⇒ (¬ c ∨ e), a ⇒ (¬c ∨ d) ⊢ c ⇒ (e ∨ d). </code> Sestrojte důkaz sekventu <code>⊢ ((a ⇒ b) ⇒ a) ⇒ a.</code> {{prirozena-dedukce-ukol-1.pdf|Řešení první úlohy.}} {{prirozena-dedukce-ukol-2.pdf|Řešení druhé úlohy.}}|
| 3  | Sémantika výrokové logiky. | {{cv-sem-vl-bez-reseni.pdf|Sémantika výrokové logiky.}} {{cv-sem-vl.pdf|Příklady k procvičení sémantiky výrokové logiky.}} | [[https://www.youtube.com/watch?v=w84ubanTQ9Y|Splnitelnost, tautologie]]. [[https://www.youtube.com/watch?v=OwBWWyy76aE|ÚSS]]. [[https://www.youtube.com/watch?v=xuOQDLP92HA|Velká konjunkce]]. [[https://www.youtube.com/watch?v=YHUZX3Hxh0s|De Morgan]]. [[https://www.youtube.com/watch?v=UBBUoClkF0s|Převod do CNF]]. [[https://www.youtube.com/watch?v=6IL2UsZGKK8|CNF z tabulky]]. [[https://www.youtube.com/watch?v=X85TfXKyzHE|Splnitelnost]]. [[https://www.youtube.com/watch?v=bhT9dBuNG-Y|Sémantický důsledek]]. [[https://www.youtube.com/watch?v=rftvNFLPz68|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. | {{ukazkovy-prvni-test.pdf|Ukázkový test.}} |  |  |
| 5  | Úvod do predikátové logiky. | {{lgr-cv-uvodpl.pdf|Základy predikátové logiky - příklady ze cvičení.}} {{lgr-cv-uvodpl-reseni.pdf|Řešení.}} [[http://web.stanford.edu/class/archive/cs/cs103/cs103.1184/notes/Guide%20to%20Logic%20Translations.pdf|Příručka pro formalisaci tvrzení v predikátové logice. (Stanford, v angličtině.)]] | Nejsou. | {{lgr-dcv-uvodpl.pdf|Vyřešte úlohy z tohoto PDF.}} {{lgr-dcv-uvodpl-reseni.pdf|Výsledky s částečným řešením naleznete zde.}} |
| 6  | Sémantika predikátové logiky. | {{lgr-cv-pokracovanipl.pdf|Sémantika predikátové logiky - příklady ze cvičení.}} {{lgr-cv-pokracovanipl-reseni.pdf|Řešení.}} {{semantika-pl-ulohy.pdf|Příklady k procvičení sémantiky predikátové logiky.}} | Nejsou. | {{lgr-dcv-pokracovanipl.pdf|Vyřešte úlohy z tohoto PDF.}} |
| 7  | Přirozená dedukce. | {{cv-prir-dedukce-pl.pdf|Přirozená dedukce v PL - příklady ze cvičení.}} {{prirozena-dedukce-pl.pdf|Sbírka základních úloh z přirozené dedukce v PL.}} {{prirozena-dedukce-pl-reseni.pdf|Řešení.}} | Nejsou. | Sestrojte důkaz sekventu <code> ∀x(∃y(M(x,y) ∨ M(y,x)) ⇒ M(x,x)), ∃x∃yM(x,y) ⊢ ∃xM(x,x) </code> (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. | {{cv-prir-dedukce-pokrocile.pdf|Úlohy na pokročilou formalisaci a přirozenou dedukci v PL.}} {{cv-prir-dedukce-pokrocile-reseni.pdf|Ř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. | {{ukazkovy-druhy-test.pdf|Ukázkový test.}} {{ukazkovy-druhy-test-reseni.pdf|Stručné řešení ukázkového testu.}} {{ukazkovy-druhy-test-reseni-dedukce.pdf|Řešení úlohy z přirozené dedukce.}} | | |
| 10 | Grafy - základní úlohy. | {{grafy-uvod-nove.pdf|Grafy - příklady ze cvičení.}} | [[https://www.youtube.com/watch?v=qJUFJ9hxyWA|Hyperkrychle.]] [[https://www.youtube.com/watch?v=qGQPOU9o_98|Regulární grafy.]] [[https://www.youtube.com/watch?v=gdPER3w5DtQ|Dostupnost je relace ekvivalence.]] [[https://www.youtube.com/watch?v=I4bSQKad3HE|Zkrácení sledu na cestu.]] [[https://www.youtube.com/watch?v=bO8HAXHY9-A|Vzdálenost je metrika.]][[https://www.youtube.com/watch?v=6dtHkeECem4|Počet sledů dané délky.]] [[https://www.youtube.com/watch?v=1cJUtvM2x7Q|Hodnost matice incidence.]] | |
| 11 | Stromy a eulerovské grafy. | {{grafy-stromy-nove.pdf|Stromy, eulerovské grafy - příklady ze cvičení.}} | [[https://www.youtube.com/watch?v=tGYeTOIGDtM|Stromy: mezi dvěma vrcholy právě jedna cesta.]] [[https://www.youtube.com/watch?v=bbdWMLNXaNU|Stromy: minimálně souvislé.]] [[https://www.youtube.com/watch?v=UW3znNtsK8g| Stromy: maximální bez kružnic.]] [[https://www.youtube.com/watch?v=OrjEfnAhAr4|Minimální kostra: Kruskal.]] [[https://www.youtube.com/watch?v=ZT1j3ZLsxhk|Minimální kostra: Jarník.]] [[https://www.youtube.com/watch?v=wdytCJJhLtQ|Hledání eulerovského tahu.]] [[https://www.youtube.com/watch?v=h2zGKB4Uil4|Kreslení více tahy.]] [[https://www.youtube.com/watch?v=bPIRyhkHlIY|Rozklad na kružnice.]] | |
| 12 | Barvení grafů. | {{barevnost-nezavislost-dominance.pdf|Barevnost, nezávislost, dominance.}} | [[https://www.youtube.com/watch?v=k8mrLmeZpvA|Sekvenční barvení: příklad.]] | |
| 13 | Orientované grafy. | {{grafy-or-grafy-nove.pdf|Orientované grafy - příklady ze cvičení.}} | [[https://www.youtube.com/watch?v=wVW7lxl865Y|Prohledávání do hloubky: příklad.]] [[https://www.youtube.com/watch?v=gju3hhxf9bg|DFS: pseudokód.]] [[https://www.youtube.com/watch?v=PwVzQxV9n6Q|DFS: Python.]] [[https://www.youtube.com/watch?v=Xr4Ka-ZSgAg|Topologické očíslování: příklad.]] [[https://www.youtube.com/watch?v=iL-nBMevUic|Jádro: příklad.]] | Prostudujte algoritmus DFS. Můžete se např. podívat na videa [[https://www.youtube.com/watch?v=wVW7lxl865Y|Prohledávání do hloubky: příklad.]] [[https://www.youtube.com/watch?v=gju3hhxf9bg|DFS: pseudokód.]] [[https://www.youtube.com/watch?v=PwVzQxV9n6Q|DFS: Python.]] |
| 14 | Reserva. | | | |