ČeskyEnglish

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:3+2
Garanti:Demlová M. Role:P Zakončení:Z,ZK
Vyučující:Demlová M.
Zodpovědná katedra:13101 Kreditů:5 Semestr:Z,L

Anotace:

Základy matematické logiky a teorie grafů. Jedná se zejména o tyto partie výrokové ohodnocení, sémantický důsledek a tautologická ekvivalence formulí, CNF a DNF, úplné systémy logických spojek, rezoluční metoda ve výrokové logice. V predikátové logice je důraz kladen na porozumění formulím a jejich interpretaci; je uvedena rezoluční metoda v predikátové logice jako základ programovacího jazyka Prolog. V teorii grafů se jedná o úvod do teorie grafů s důrazem na jejich využití. Je zaveden orientovaný i neorientovaný graf, studují se pojmy souvislosti i silné souvislosti grafů, stromy a kostry, eulerovské grafy. Jsou probírány hamiltonovské grafy, nezávislé množiny a barvení vrcholů grafu jako příklady obtížně řešitelných úloh..

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. Predikátová logika, syntakticky správné formule, sentence.
5. Interpretace predikátové logiky, tautologická ekvivalence sentencí a sémantický důsledek.
6. Rezoluční metoda v predikátové logice.
7. Aplikace rezoluční metody. Přirozená dedukce jako příklad úplného a bezesporného odvozovacího systému. Věta o úplnosti.
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é a hranové barvení grafů.
13. Rovinné grafy.

Osnovy cvičení:

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. Predikátová logika, syntakticky správné formule, sentence.
5. Interpretace predikátové logiky, tautologická ekvivalence sentencí a sémantický důsledek.
6. Rezoluční metoda v predikátové logice.
7. Aplikace rezoluční metody. Přirozená dedukce jako příklad úplného a bezesporného odvozovacího systému. Věta o úplnosti.
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é a hranové barvení grafů.
13. Rovinné grafy.

Literatura:

[1] M. Demlová, B. Pondělíček: Matematická logika. ČVUT Praha, 1997.
[2] Matoušek, J., Nešetřil, J.: Kapitoly z diskrétní matematiky, Nakladatelství Karolinum, 2000.
[3] Demel, J.: Grafy a jejich aplikace, Academia 2002, druhé vydání 2015.

Požadavky:

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

Plán Obor Role Dop. semestr
BPOI2_2016 Internet věcí 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
BPOI1_2016 Informatika a počítačové vědy P 2
BPKYR_2016 Před zařazením do oboru P 1


Stránka vytvořena 25.7.2017 17:54:30, semestry: L/2016-7, Z,L/2017-8, Z/2018-9, 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.