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., Gollová A. Kreditů:5
Cvičící:Dostál M., Gollová A. Semestr:Z,L

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 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. Probereme resoluční metodu ve výrokové i predikátové logice. 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:

1. Formule výrokové logiky, pravdivostní ohodnocení, tautologie, kontradikce, splnitelné formule.
2. Tautologická ekvivalence formulí. CNF a DNF, Karnaughovy mapy, Booleovský kalkul.
3. Sémantický důsledek. Rezoluční metoda ve výrokové logice.
4. Přirozená dedukce ve výrokové logice. Věta o úplnosti.
5. Predikátová logika, syntakticky správné formule, sentence.
6. Interpretace predikátové logiky, model sentence. Tautologická ekvivalence sentencí a sémantický důsledek.
7. Rezoluční metoda v predikátové logice.
8. Grafy neorientované a orientované, základní pojmy. Souvislost, stromy, kostry.
9. Kořenové stromy, silná souvislost, acyklické grafy, topologické očíslování vrcholů a hran.
10. Eulerovy grafy a jejich aplikace.
11. Hamiltonovy grafy a jejich aplikace.
12. Nezávislé množiny, kliky v grafu. Vrcholové barvení grafů.
13. Rovinné grafy.

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 http://math.feld.cvut.cz/gollova/lgr.html

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 2.7.2020 11:50:28, semestry: Z,L/2020-1, 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.