LGR
Z OI wiki
(→Studijní materiály) |
|||
(Není zobrazeno 6 mezilehlých verzí.) | |||
Řádka 17: | Řádka 17: | ||
== Studijní materiály == | == Studijní materiály == | ||
- | [http://math.feld.cvut.cz/demlova/teaching/lgr_vyuka.html Výuka - předmět Logika a grafy] | + | *[https://drive.google.com/drive/folders/0B33G3DM4Z57yN2FyTndHZnM0ZEk Google drive] |
+ | *[http://math.feld.cvut.cz/demlova/teaching/lgr_vyuka.html Výuka - předmět Logika a grafy] | ||
=== Skriptum === | === Skriptum === | ||
Řádka 28: | Řádka 29: | ||
=== Cvičenia === | === Cvičenia === | ||
[http://math.feld.cvut.cz/veronika/vyuka/lgr.htm Web RNDr. Veroniky Sobotíkovej Csc.] | [http://math.feld.cvut.cz/veronika/vyuka/lgr.htm Web RNDr. Veroniky Sobotíkovej Csc.] | ||
+ | |||
+ | === Neoficiální === | ||
+ | [https://ulozto.cz/!wJbbW1nNt6wJ/demlovominimum-pdf demlovominimum.pdf] | ||
== Semestrální písemky == | == Semestrální písemky == | ||
+ | [https://drive.google.com/drive/folders/0B33G3DM4Z57yam4yMm9GWFgyQUU Testy na Google drive] | ||
===2. semestrální písemka=== | ===2. semestrální písemka=== | ||
[http://math.feld.cvut.cz/demlova/teaching/lgr/ukaz-2.pdf Vzorové zadání] | [http://math.feld.cvut.cz/demlova/teaching/lgr/ukaz-2.pdf Vzorové zadání] | ||
Řádka 46: | Řádka 51: | ||
C(L) = 1 + 1 + 1 + 2 + 2 + 3 + 4 = '''14''' | C(L) = 1 + 1 + 1 + 2 + 2 + 3 + 4 = '''14''' | ||
+ | |||
+ | '''2. příklad''' | ||
+ | |||
+ | Tarjanův algoritmus | ||
+ | komponenty souvislosti: | ||
+ | |||
+ | K1 = {1,3,2,8}, | ||
+ | K2 = {7,5,4}, | ||
+ | K3 = {10}, | ||
+ | K4 = {9,6} | ||
+ | |||
+ | '''3. příklad''' | ||
+ | |||
+ | kondenzace komponent souvislosti z př. 2 | ||
+ | |||
+ | K1 -> hrana (3,4) -> K2 | ||
+ | |||
+ | K1 -> hrana (8,10) -> K3 | ||
+ | |||
+ | K1 -> hrana (3,6) -> K4 | ||
+ | |||
+ | K2 -> hrana (4,10) -> K3 | ||
+ | |||
+ | K2 -> hrana (5,9) -> K4 | ||
+ | |||
+ | uvedené hrany jsou jen jako příklady hran v grafu (a tedy oprávnění pro hranu v grafu kondenzace) (můžete uvést jiné) | ||
== Zkoušky == | == Zkoušky == | ||
+ | [https://drive.google.com/drive/folders/0B33G3DM4Z57yam4yMm9GWFgyQUU Zkoušky na Google drive] | ||
+ | === Zkouška 2.6.2013 === | ||
+ | |||
+ | [http://oi.hanx.cz/wiki/index.php/Soubor:2_6_2013_test.jpg zadání] | ||
+ | |||
+ | === Zkouška 7.6.2012 === | ||
+ | |||
+ | [http://oi.hanx.cz/files/LGR/lgr-120607.jpg zadání] | ||
+ | |||
+ | |||
=== Zkouška 2.6.2011. === | === Zkouška 2.6.2011. === | ||
Řádka 89: | Řádka 130: | ||
d) Nakreslit kondenzaci grafu | d) Nakreslit kondenzaci grafu | ||
+ | |||
+ | |||
+ | === Zkouška 18.5.2010. === | ||
+ | |||
+ | [http://oi.hanx.cz/files/LGR/LGR%2018.5.2010.jpg zadání] |
Aktuální verze z 18. 1. 2019, 19:38
|
|
Info o předmětu
- Přednášející: prof. RNDr. Marie Demlová, CSc.
- Cvičící: ing. Tomáš Kroupa, Ph.D.; RNDr. Veronika Sobotíková, CSc.; ...
Pravidla předmětu
Pravidla předmětu na stránkách Katedry matematiky
Studijní materiály
Skriptum
Matematická logika / Marie Demlová, Bedřich Pondělíček v ÚK ČVUT
Grafy a jejich aplikace / Jiří Demel v ÚK ČVUT
přednášky předmětu LGR spojené do jednoho pdf souboru
Cvičenia
Web RNDr. Veroniky Sobotíkovej Csc.
Neoficiální
Semestrální písemky
2. semestrální písemka
Řešení:
1. příklad
Kruskalův algoritmus
{{souřadnice,} (cena)}
K = {{1,2} (1), {6,8} (1), {7,8} (1), {1,4} (2), {2,6} (2), {1,5} (3), {2,8} (3), {2,4} (4), {3,5} (4), {2,3} (5), {2,5} (5), {2,7} (5), {3,7} (5), {4,8} (5), {4,7} (7), {3,4} (10), {1,8} (10), {3,6} (11), {6,7} (11),{1,7} (13),{5,6} (12),{1,3} (15),{1,6} (15),{4,5} (15)}
L = {{1,2} (1), {6,8} (1), {7,8} (1), {1,4} (2), {2,6} (2), {1,5} (3), {3,5} (4)}
C(L) = 1 + 1 + 1 + 2 + 2 + 3 + 4 = 14
2. příklad
Tarjanův algoritmus komponenty souvislosti:
K1 = {1,3,2,8}, K2 = {7,5,4}, K3 = {10}, K4 = {9,6}
3. příklad
kondenzace komponent souvislosti z př. 2
K1 -> hrana (3,4) -> K2
K1 -> hrana (8,10) -> K3
K1 -> hrana (3,6) -> K4
K2 -> hrana (4,10) -> K3
K2 -> hrana (5,9) -> K4
uvedené hrany jsou jen jako příklady hran v grafu (a tedy oprávnění pro hranu v grafu kondenzace) (můžete uvést jiné)
Zkoušky
Zkouška 2.6.2013
Zkouška 7.6.2012
Zkouška 2.6.2011.
1. a) Definujte sémantický důsledek.
b) Rezoluční metoda
c) Zjistit jestli platí tvrzení: pokud S |= a, pak take S |= (a => b) pro libovolné b. (podle mně ne)
2. a) Popiš jazyk v kterém jsou dané formule sentenci (podobně jako u ukázkové zkoušky)
b) Dle definici zjistit jestli množina formuli je splinitelná
c) Které problemy řeší rezoluční metoda?
d) Rezoluční metoda
3. a) Def. orientovaný tah.
b) Def. uzavření eulerovský tah.
c) Podminka aby eul. tah existoval v souvislém grafu
d) Jestli platí stejne i pro nesouvislý graf?
e) Popsat metodu jak najít eul. tah
f) Najít eul. tah
4. a) Def. silné souvislosti
b) Nakreslit graf s daným počtem komponenty souvislosti, vrcholu a hran (jako ukázka)
c) Najít komponenty silné souvislosti
d) Nakreslit kondenzaci grafu