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

Na této stránce budou s předstihem specifikována témata jednotlivých cvičení, naleznete zde také materiály s úlohami k samostatnému studiu. U vybraných týdnů budou k disposici nepovinné domácí úlohy.

==== Nepravidelnosti ====



  * V 8. výukovém týdnu odpadají pondělní cvičení. Důvodem je státní svátek.
  * V 11. výukovém týdnu odpadají čtvrteční cvičení. Důvodem je náhrada výuky, viz [[https://intranet.fel.cvut.cz/cz/education/harmonogram.html|harmonogram]].
  * Ve 12. výukovém týdnu odpadají úterní cvičení. Důvodem je náhrada výuky, viz [[https://intranet.fel.cvut.cz/cz/education/harmonogram.html|harmonogram]].

==== Časový plán ====


^ Týden ^ Náplň ^ Materiály ^ Videa ^ Domácí cvičení ^
| 1  | Indukce. | {{indukce-cviceni.pdf|Matematická indukce - příklady ze cvičení.}} | Nejsou. | Promyslete, co by mohl znamenat pojem //podformule formule φ//, a pokuste se tento pojem definovat.  |
| 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 <code>a ∨ b, b ⇒ (¬ c ∨ e), a ⇒ (¬c ∨ d) ⊢ c ⇒ (e ∨ d). </code> Sestrojte důkaz <code>⊢ ((a ⇒ b) ⇒ a) ⇒ a.</code> Řešení druhého úkolu: {{prirozena-dedukce-ukol-1.pdf|první část}}, {{prirozena-dedukce-ukol-2.pdf|druhá část}}. |
| 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]]. | Zpracujte si doma {{vl-test-ukazka.pdf|ukázkový první test}}. |
| 4  | Test z výrokové logiky. | {{vl-test-ukazka.pdf|Ukázkový první test}}. Pokud je pro vás test příliš těžký, můžete nejprve zkusit {{vl-test-ukazka2.pdf|jednoduchou variantu}}. Pokud se chcete připravit na všechno, zpracujte i {{vl-test-ukazka3.pdf|těžkou variantu}}. {{vl-cv1-reseni.pdf|cv1-reseni}} |  |  |
| 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í.}} {{semantika-pl-ulohy.pdf|Příklady k procvičení sémantiky predikátové logiky.}} |  | {{lgr-dcv-pokracovanipl.pdf|Vyřešte úlohy z tohoto PDF.}} {{lgr-dcv-pokracovanipl-odpovedi.pdf|Odpovědi.}} |
| 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í.}} |  | Sestrojte důkaz <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í.}} |  | Zpracujte si doma {{pl-test-ukazka.pdf|ukázkový druhý test}}. |
| 9  | Test z predikátové logiky. | | |  |
| 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.]] | Vyřešte úlohy z {{grafy-dcv1.pdf|tohoto souboru}}. |
| 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.]] | Vyřešte úlohy z {{grafy-dcv2.pdf|tohoto souboru}}. |
| 12 | Barvení grafů. | {{barevnost-nezavislost-dominance.pdf|Barevnost, nezávislost, dominance.}} | [[https://www.youtube.com/watch?v=k8mrLmeZpvA|Sekvenční barvení: příklad.]] | Vyřešte úlohy z {{grafy-dcv3.pdf|tohoto souboru}}. |
| 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. | | | |