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
V češtině:
| 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. | 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. | |
| 9. | Eulerovy grafy a jejich aplikace. | |
| 10. | Souvislost, stromy, kostry. | |
| 11. | Silná souvislost, acyklické grafy, topologické očíslování vrcholů. | |
| 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. |
| [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.Webová stránka:
https://moodle.fel.cvut.cz/courses/B0B01LGRKlíč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ů:
| Stránka vytvořena 20.1.2021 05:50:34, semestry: Z/2020-1, L/2021-2, L/2020-1, Z/2021-2, 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) |