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
Role:PV, P Rozsah výuky:3P+2S
Katedra:13101 Jazyk výuky:CS
Garanti:Demlová M. Zakončení:Z,ZK
Přednášející:Dostál M. Kreditů:5
Cvičící:Dostál M., Gollová A., Žukovec N. Semestr:Z,L

Webová stránka:

https://cw.fel.cvut.cz/wiki/courses/b0b01lgr/

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.

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 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 (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.

Klíčová slova:

Výroková logika, predikátová logika, syntaktický a 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
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
BPKYR_2016 Před zařazením do oboru P 1
BPBIO_2018 Před zařazením do oboru PV 5
BPKYR_2021 Před zařazením do oboru P 1
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


Stránka vytvořena 28.3.2024 17:52:19, semestry: Z,L/2023-4, Z/2024-5, 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)