Logika a grafy - letní semestr 2018/2019

Hledáte výsledky zkoušek? Podívejte se na stránku s výsledky zkoušek zde.

Zde naleznete dosavadní zadání písemných prací.

Osnovu předmětu naleznete zde.

Přečtěte si požadavky na zápočet a zkoušku.

Přednášky

Účast na přednáškách je silně doporučena.

Přednášky budou dělit semestr zhruba na třetiny podle témat:

Všichni jste již prošli předmětem Diskrétní matematika od Petra Habaly. Očekávám tedy, že do předmětu Logika a grafy přicházíte se znalostí logiky na úrovni kapitoly 1 učebnice Petra Habaly a se znalostí indukce na úrovni kapitoly 5 staré (kompletní) verse učebnice Petra Habaly. Vaše znalosti budeme formalisovat a rozšiřovat.

Pokud si nejste jisti svými znalostmi indukce, můžete si je utříbit četbou Kapitoly 1 knihy Diskrétní matematika Jiřího Velebila. Konkrétně jde o podkapitoly 1.1, 1.2 a 1.4. Pokud je na vás text příliš složitý, přečtěte si nejdříve Chapter 2: Iteration, Induction, and Recursion z knihy Foundations of Computer Science Ala Aho a Jeffa Ullmana. (Pro vás zajímavý by mohl být i Chapter 5: The Tree Data Model. Naopak Chapter 12 a Chapter 13 jsou pro úvod do logiky možná až příliš elementární.)

Sdílím s vámi příklady na procvičení výrokové logiky od prof. Demlové. První část příkladů jsem pro vás poměrně dopodrobna vyřešil.

Pokud si chcete zkontrolovat své řešení nějaké úlohy, mohou vám pomoci nástroje na stránce Logictools. Nástroje umí například zjišťovat splnitelnost množiny formulí, napsat pravdivostní tabulku formule, syntaktický strom formule, převést formuli do CNF, a tak dále.

Nahrál jsem skript generující klausule pro sudoku ve formátu automatického dokazovače Prover9 a hledače konečných modelů Mace4. Tyto nástroje můžete nalézt na stránkách Williama McCunea.

Přehled přednášek:

Pondělí 22. 4. 2019 je Velikonoční pondělí, přednáška (ani cvičení) se nekoná.

Četba:

  1. První a druhý týden: Přečtěte první a druhou kapitolu úvodu do logiky.
  2. Třetí a čtvrtý týden: Přečtěte kapitolu 4.1 z úvodu do logiky.
  3. Pátý a šestý týden: Přečtěte kapitolu 3 z úvodu do logiky.
  4. Sedmý týden: Přečtěte kapitolu 4 z úvodu do logiky.

Cvičení

Účast na cvičeních je povinná.

Informace a materiály ke cvičením naleznete na stránkách cvičících.

Kdo máte cvičení v pondělí, pozor! Nekoná se cvičení v pondělí 22. 4. 2019.

Kdo máte cvičení ve středu, pozor! Nekonají se cvičení v tyto tři termíny: 1. 5. 2019, 8. 5. 2019, 15. 5. 2019. Středeční cvičení se ale konají ve formální středy, tj. ve čtvrtek 9. 5. 2019 a v úterý 14. 5. 2019. Tyto změny jsem nevymyslel já, viz harmonogram akademického roku.

Kdo máte cvičení ve čtvrtek, pozor! Nekoná se cvičení ve čtvrtek 9. 5. 2019, neboť je tento den středa.

Konsultace

Konsultace domlouvejte především se svými cvičícími. V případě nutnosti přednášející vyhlásí hromadnou konsultaci e-mailem.

Doporučená literatura

Jemný úvod do látky ze semestru: Doplňující čtivo: Doporučené knihy v angličtině: Nevím, zda je to legální, ale obě knihy jsou webovými vyhledávači k nalezení pod svým názvem v PDF ze stránek výzkumných institucí. Obě doporučuji pokročilým studentkám a studentům.

Zpět na stránku Výuka


Organizace semestru a požadavky k zápočtu a zkoušce z Logiky a grafů

Organizace semestru:

  1. Během semestru se píší dva testy. Každý test je na 40 minut čistého času, maximální bodový zisk je 20 bodů, nutný zisk je 10 bodů.
    • 1.test v 5. nebo 6. týdnu semestru: náplní je výroková logika, starší ukázku testu najdete zde. Pozor, nutný bodový zisk je 10 bodů.
    • 2.test v 10. nebo 11. týdnu semestru: náplní je predikátová logika, starší ukázku testu najdete zde. Pozor, nutný bodový zisk je 10 bodů.
  2. Opravné testy za nedostatečný výsledek nebo náhradní testy za neúčast na testu ze závažných důvodů (důvody posoudí cvičící) - z jiného důvodu právo psát náhradní test nevzniká - se budou psát v posledním týdnu semestru bez rozlišení studijních skupin a budou organizovány centrálně. Každý test je možno opravovat pouze jednou. Výsledek náhradního/opravného testu se student dozví od svého cvičícího.

  3. Získání zápočtu: Pro získání zápočtu je nutná aktivní účast na cvičeních a zisk alespoň 10 bodů z každého ze dvou pisemných testů, které se budou psát během semestru. Cvičící na prvním cvičení specifikují, co považují za aktivní účast na cvičení.

Organizace zkoušek a klasifikace:

  1. Zkoušky budou organizovány ve velkých zkouškových termínech.
  2. Na zkoušku se mohou přihlásit pouze ti, kteří mají udělen zápočet. Přihlašovat se lze pouze prostřednictvím systému KOS.

  3. Písemná zkouška: 150 minut čistého času, 3 příklady, maximální bodový zisk 100 bodů.
  4. Okruhy pro jednotlivé příklady písemné části zkoušky: 1. příklad - výroková logika, 2. příklad - predikátová logika, 3. příklad - grafy.
    Zde je ukázka písemné zkoušky ve formátu PDF.
  5. Na titulní straně zadání bude stát Vaše unikátní identifikační číslo, pod kterým bude zveřejněn výsledek písemné zkoušky. Dále na titulní straně zadání stojí datum, čas a místo možného náhledu písemné zkoušky. Zde je ukázka titulní strany ve formátu PDF.

  6. Kdo napsal zkouškovou písemku na méně než 50 bodů nebo nezískal z každého příkladu nutný počet bodů, získává známku F (nedostatečně).
  7. Kdo napsal zkouškovou písemku na 50 a více bodů a získal z každého příkladu alespoň nutný počet bodů, obdrží bodový bonus ze semestru. Bonus se počítá takto: za každý test, který nebyl opravný a ze kterého dostal student více než 10 bodů, se jako bonus započítá počet získaných bodů mínus 10. (Tj. získá-li např. student v prvním testu 18 bodů a v druhém 10 bodů, započítá se mu jako bonus 8 bodů z prvního testu a z druhého testu nic. Body z opravného testu se do výsledku zkoušky nezapočítávají stejně tak jako body z domácích úkolů.)
  8. Zkoušející rozhoduje o tom, kdo může či musí podstoupit ústní zkoušku. U ústní zkoušky je možné získat minimálně -20 bodů a maximálně +20 bodů. Datum, čas a místo možné ústní zkoušky stojí na zadání písemné zkoušky.

  9. Klasifikace je určena následovně:

    < 55F nedostatečně
    55-68E dostatečně
    69-82D uspokojivě
    83-96C dobře
    97-109B velmi dobře
    > 109A výborně

Pokyny k písemné zkoušce:

  1. 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).
  2. 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).
  3. Před začátkem písemné zkoušky si pečlive pročtete 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.
  4. 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, 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í telefony vypněte.

Zpět na stránku Výuka