Výuka - předmět Logika a grafy

Harmonogram

Výukové týdny: 19.2.2018 - 27.5.2018

Týdenní osnova

  1. Formule výrokové logiky, pravdivostní ohodnocení, tautologie, kontradikce, splnitelné formule. Odvozené spojky.
  2. Úplné systémy logických spojek. Sémantický důsledek, tautologická ekvivalence, CNF a DNF, Booleovský kalkul.
  3. Booleovský kalkul. Rezoluční metoda ve výrokové logice.
  4. Dokončení rezoluční metody ve výrokové logice. Predikátová logika, formalizace vět, syntakticky správné formule.
  5. Interpretace predikátové logiky, sémantický důsledek a tautologická ekvivalence v predikátové logice.
  6. Rezoluční metoda v predikátové logice.
  7. Odvozovací systémy ve výrokové i predikátové logice. Věta o úplnosti a její důsledky.
  8. Grafy neorientované a orientované, základní pojmy. Souvislost.
  9. Stromy, minimální kostry, kořenové stromy.
  10. Silná souvislost, acyklické grafy.
  11. Eulerovy grafy a jejich aplikace.
  12. Hamiltonovy grafy a jejich aplikace.
  13. Nezávislé množiny, kliky v grafy. Vrcholové a hranové barvení grafu.
  14. Rovinné grafy.

Literatura

Logika

  • M. Demlová, B. Pondělíček: Matematická logika, ČVUT Praha, 1997.
  • J. Velebil: Velmi jemný úvod do matematické logiky, ke stažení na stránkách J. Velebila
  • M. Demlová: Mathematical Logic, Kernberg Publishing, 2008 (anglicky).

Grafy

  • J. Matoušek, J. Nešetřil: Kapitoly z diskrétní matematiky, Nakladatelství Karolinum, 2000.
  • J. Demel: Grafy a jejich aplikace, Academia, 2015.
  • J. Černý: Základní grafové algoritmy, ke stažení na stránkách J. Černého.

Stručný obsah přednášek - Přednášky.

Zkoušky

Zde najdete informace o zápočtových testech a organizaci zkoušek. Výsledky zkoušek najdete na zde.
Responsible person: doc. RNDr. Martin Bohata, Ph.D.