Popis předmětu - B0B01LGR

Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
B0B01LGR Logika a grafy Rozsah výuky:3P+2S
Garanti:Demlová M. Role:PV,P Jazyk výuky:CS
Vyučující:Dostál M. Zakončení:Z,ZK
Zodpovědná katedra:13101 Kreditů:5 Semestr:Z,L

Anotace:

Tento předmět se zabývá základy matematické logiky a teorie grafů. Je zavedena syntax a sémantika výrokové logiky a predikátové logiky prvního řádu. Důraz je kladen na pochopení pojmu sémantického 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.

Obsah:

Obsahem předmětu je matematická logika a teorie grafů. Z matematické logiky probereme základy výrokové logiky a logiky prvního řádu (predikátové logiky). Studujeme formální syntax, jazyky logiky jsou přirovnány k programovacím jazykům. Je diskutován praktický problém odvození závěru z daných předpokladů. Zavedeme syntaktická odvozovací pravidla a budeme diskutovat jejich smysluplnost. Standardním způsobem zavedeme význam (sémantiku) výrokové logiky. Prostudujeme sémantický důsledek a jeho vztah k důsledku syntaktickému. V predikátové logice přednostně zavádíme sémantiku a studujeme pravdivost tvrzení predikátové logiky v dané interpretaci. V části týkající se teorie grafů předvedeme praktické problémy, které jsou popsatelné a řešitelné metodami teorie grafů. Zavedeme základní pojmy teorie grafů jako vyjadřovací prostředek k popisu teoretických i praktických úloh. Odvodíme teoretické vlastnosti daných pojmů jako prostředek k tvorbě grafových algoritmů.

Osnovy přednášek:

Výroková logika (cca 4 týdny):
1. Formální jazyk. Jazyk výrokové logiky.
2. Odvozování důsledků (dedukce).
3. Význam a sémantický důsledek.
4. Reserva: pokročilá témata.
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. Dedukce v predikátové logice.
4. Reserva: pokročilá témata.
Teorie grafů: (cca 5 týdnů):
1. Základní pojmy teorie grafů.
2. Kostry.
3. Silná souvislost.
4. Kreslení jedním tahem.
5. Barvení.

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] M. Demlová, B. Pondělíček: Matematická logika. ČVUT Praha, 1997.
[4] J. Demel: Grafy a jejich aplikace, Academia 2002, druhé vydání 2015.
[5] P. Kovář: Teorie grafů, online, 2019.

Požadavky:

Nejsou.

Webová stránka:

http://math.feld.cvut.cz/dostamat/teaching/lgr1920.htm

Klíčová slova:

Výroková logika, predikátová logika, sémantický důsledek, základní pojmy teorie grafů, grafové algoritmy.

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr
BPOI_BO_2018 Před zařazením do oboru P 2
BPOI4_2018 Počítačové hry a grafika P 2
BPOI3_2018 Software P 2
BPOI2_2018 Internet věcí P 2
BPOI1_2018 Základy umělé inteligence a počítačových věd P 2
BPOI1_2016 Informatika a počítačové vědy P 2
BPOI_BO_2016 Před zařazením do oboru P 2
BPOI4_2016 Počítačové hry a grafika P 2
BPOI3_2016 Software P 2
BPOI2_2016 Internet věcí P 2
BPBIO_2018 Před zařazením do oboru PV 5
BPKYR_2016 Před zařazením do oboru P 1


Stránka vytvořena 11.11.2019 17:50:47, semestry: Z,L/2020-1, L/2018-9, Z,L/2019-20, připomínky k informační náplni zasílejte správci studijních plánů Návrh a realizace: I. Halaška (K336), J. Novák (K336)
Za obsah odpovídá: doc. Ing. Ivan Jelínek, CSc.