456-0317/01 – Matematické základy informatiky (MZI)
| Garantující katedra | Katedra informatiky | Kredity | 8 |
| Garant předmětu | prof. RNDr. Marie Duží, CSc. | Garant verze předmětu | prof. RNDr. Marie Duží, CSc. |
| Úroveň studia | pregraduální nebo graduální | Povinnost | povinný |
| Ročník | 2 | Semestr | zimní |
| | Jazyk výuky | čeština |
| Rok zavedení | 2003/2004 | Rok zrušení | 2009/2010 |
| Určeno pro fakulty | FEI | Určeno pro typy studia | navazující magisterské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Cílem předmětu je seznámit se základními principy logických důkazových kalkulů a axiomatických teorií, a jejich rozvinutí v oblasti algebry, zejména teorie svazů. Kurs je zaměřen na praktické aplikace v různých oblastech teoretické a aplikované informatiky při zachování exaktnosti jak při formulaci problému, tak při jeho řešení.
Vyučovací metody
Anotace
V předmětu budou prezentovány základní principy formálních logických kalkulů a axiomatických teorií, zejména pak algebraických teorií. Dále budou zdůrazněny souvislosti mezi rigidním pohledem logiky a praktickými aplikacemi v informatice.
Povinná literatura:
M.Duží: Matematická logika. Učební texty VŠB Ostrava.
J.Kolář, O.Štěpánková, M.Chytil: Logika, algebra, grafy. Praha, SNTL 1989.
J.Matoušek, J.Nešetřil. Kapitoly z diskrétní matematiky, Karolinum Praha 2000.
Manna, Z.: Matematická teorie programů. SNTL Praha, 1981.
Doporučená literatura:
Sochor, A.: Klasická matematická logika. Karolinum Praha, 2001.
Švejdar, V.: Logika, neúplnost a složitost. Academia Praha, 2002.
Další studijní materiály
Forma způsobu ověření studijních výsledků a další požadavky na studenta
Podmínky udělení zápočtu:
Práce na zadaném projektu v průběhu semestru, odevzdává se v písemné formě (max. 10 bodů).
Presentace řešení projektu na přednášce (nepovinná - bonus 5 bodů).
Písemný zápočtový test maximum 15 bodů.
Minimální počet bodů pro získání zápočtu = 12
E-learning
Další požadavky na studenta
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Přednášky:
Naivní teorie množin: množinové operace a jejich definice prostředky predikátové logiky 1. řádu (PL1). Kartézský součin, relace, zobrazení.
Sémantické metody predikátové logiky 1. řádu (PL1)
Úvod do formálních (důkazových) kalkulů
Rezoluční metoda ve výrokové logice
Obecná rezoluční metoda v PL1
Přirozená dedukce ve výrokové logice
Přirozená dedukce v PL1
Korektnost a úplnost kalkulu
Presentace řešení samostatných projektů - příkladů.
Teorie relací, typy relací, teorie ekvivalence a uspořádání.
Algebraické teorie, grupy, okruhy, tělesa.
Teorie svazů, konceptuální svazy
Formalizované teorie aritmetiky, Gödelovy výsledky (věty o neúplnosti)
Formální kalkuly Hilbertova typu pro výrokovou logiku a predikátovou logiku
Cvičení:
Důkazy základních tvrzení teorie množin.
Důkaz sporem ve výrokové logice.
Rezoluční metoda ve výrokové logice.
Rozdíl mezi relací a funkcí, matematické i empirické příklady.
Důkazy sémantickým tablem v predikátové logice.
Množinové důkazy v predikátové logice.
Vennovy diagramy a jejich využití.
Důkazy tvrzení a platnosti argumentu obecnou rezoluční metodou.
Důkazy tvrzení a platnosti argumentu přirozenou dedukcí.
Důkazy tvrzení teorie relací a funkcí.
Důkazy základních algebraických vět.
Projekty:
Řešení zadaného problému metodou přirozené dedukce a rezoluční metodou.
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky
Předmět neobsahuje žádné hodnocení.