LGR
Z OI wiki
(→Zkouška 2.6.2011.) |
(→Studijní materiály) |
||
Řádka 23: | Řádka 23: | ||
[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://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 === | === Cvičenia === |
Verze z 9. 6. 2011, 14:27
|
|
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
Výuka - předmět Logika a grafy
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.
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
Zkoušky
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