Logika a grafy - B0B01LGR

Kredity 5
Semestry oba
Zakončení zápočet a zkouška
Jazyk výuky čeština
Rozsah výuky 3P+2S
Anotace
Tento předmět se zabývá základy matematické logiky a teorie grafů. Je zavedena syntaxe a sémantika výrokové logiky a predikátové logiky prvního řádu. Důraz je kladen na pochopení pojmu důsledku, na vztah mezi formulí a jejím modelem. Dále jsou zavedeny některé základní pojmy teorie grafů a popsány algoritmy k řešení některých základních úloh z teorie grafů.
Cíle studia
Cílem předmětu je seznámit studenty se základy matematické logiky a základy teorie grafů.

Studenti by měli rozlišovat syntax a sémantiku, umět pracovat se syntaktickým i sémantickým důsledkem, a dále by měli být schopni formalisovat ve vhodném jazyce jednoduché praktické úlohy.

Dále by studenti měli být schopni řešit teoretické i praktické grafové úlohy, a měli by být schopni popsat a použít základní grafové algoritmy.
Osnovy přednášek
Výroková logika (3-4 týdny):
1. Formální jazyk. Jazyk výrokové logiky.
2. Odvozování důsledků (přirozená dedukce).
3. Význam a sémantický důsledek.
4. Reserva pro případ zdržení.

Predikátová logika (cca 4 týdny):
1. Jazyk predikátové logiky.
2. Význam a sémantický důsledek v predikátové logice.
3. Odvozování důsledků (přirozená dedukce).
4. Reserva: pokročilá témata.

Teorie grafů: (cca 5-6 týdnů):
Uspořádání témat a výběr pokročilých témat se může lišit.
1. Základní pojmy teorie grafů.
2. Stromy. Minimální kostry.
3. Silná souvislost. Acyklické grafy.
4. Kreslení jedním tahem.
5. Barvení. Rovinné grafy.
6. Reserva: pokročilá témata.
Osnovy cvičení
Řešení teoretických i algoritmických úloh z logiky a teorie grafů.
Upevňování a rozšiřování znalostí a dovedností z přednášek.
Literatura
[1] M. Huth, M. Ryan: Logic in Computer Science: Modelling and Reasoning about Systems. Cambridge University Press, 2004.
[2] J. A. Bondy, U. S. R. Murty: Graph theory with applications. Elsevier Science Ltd/North-Holland, 1976.

V češtině:
[3] J. Velebil: Velmi jemný úvod do matematické logiky. Online 2007.
[4] M. Demlová, B. Pondělíček: Matematická logika. ČVUT Praha, 1997.
[5] J. Demel: Grafy a jejich aplikace. Academia 2002, druhé vydání 2015.
[6] P. Kovář: Teorie grafů. Online, 2019.
Požadavky
Nejsou.