LGR
Z OI wiki
(→Studijní materiály) |
|||
(Není zobrazeno 23 mezilehlých verzí.) | |||
Řádka 12: | Řádka 12: | ||
== Pravidla předmětu == | == Pravidla předmětu == | ||
- | [http://math.feld.cvut.cz/demlova/teaching/ | + | [http://math.feld.cvut.cz/demlova/teaching/lgr/lgr_zkousky.html Pravidla předmětu na stránkách Katedry matematiky] |
<br /> | <br /> | ||
== Studijní materiály == | == Studijní materiály == | ||
- | http://math.feld.cvut.cz/demlova/teaching/lgr_vyuka.html | + | *[https://drive.google.com/drive/folders/0B33G3DM4Z57yN2FyTndHZnM0ZEk Google drive] |
- | [http://aleph.cvut.cz/F/FNPB4Y855DDMGJIJ3KKAVPA1KKK55S2S1UC5DDK78199BT57EX-01978?func=full-set-set&set_number=283941&set_entry=000004&format=999 | + | *[http://math.feld.cvut.cz/demlova/teaching/lgr_vyuka.html Výuka - předmět Logika a grafy] |
- | < | + | |
+ | === Skriptum === | ||
+ | [http://aleph.cvut.cz/F/FNPB4Y855DDMGJIJ3KKAVPA1KKK55S2S1UC5DDK78199BT57EX-01978?func=full-set-set&set_number=283941&set_entry=000004&format=999 Matematická logika / Marie Demlová, Bedřich Pondělíček v ÚK ČVUT] | ||
+ | |||
+ | [http://aleph.cvut.cz/F/FNPB4Y855DDMGJIJ3KKAVPA1KKK55S2S1UC5DDK78199BT57EX-02659?func=full-set-set&set_number=283949&set_entry=000007&format=999 Grafy a jejich aplikace / Jiří Demel v ÚK ČVUT] | ||
+ | |||
+ | [http://www.uloz.to/9311889/aaa-lgr-pdf přednášky předmětu LGR spojené do jednoho pdf souboru] | ||
+ | |||
+ | === Cvičenia === | ||
+ | [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 == | ||
+ | [https://drive.google.com/drive/folders/0B33G3DM4Z57yam4yMm9GWFgyQUU Testy na Google drive] | ||
+ | ===2. semestrální písemka=== | ||
+ | [http://math.feld.cvut.cz/demlova/teaching/lgr/ukaz-2.pdf Vzorové zadání] | ||
+ | |||
+ | '''Ř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), <del>{2,8} (3)</del>, <del>{2,4} (4)</del>, {3,5} (4), <del>{2,3} (5)</del>, <del>{2,5} (5)</del>, <del>{2,7} (5)</del>, <del>{3,7} (5)</del>, <del>{4,8} (5)</del>, <del>{4,7} (7)</del>, <del>{3,4} (10)</del>, <del>{1,8} (10)</del>, <del>{3,6} (11)</del>, <del>{6,7} (11)</del>,<del>{1,7} (13)</del>,<del>{5,6} (12)</del>,<del>{1,3} (15)</del>,<del>{1,6} (15)</del>,<del>{4,5} (15)</del>} | ||
+ | |||
+ | 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š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. === | ||
+ | |||
+ | [http://oi.hanx.cz/files/LGR/lgr-2-6-2011.jpg foto] | ||
+ | |||
+ | '''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 | ||
+ | |||
+ | |||
+ | === 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