Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod

---

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 (cca 4 týdny): Predikátová logika (cca 4 týdny): Teorie grafů: (cca 6 týdnů):

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:

V češtině:

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ů:

---