LGR

Z OI wiki

Obsah 1 Info o předmětu 2 Pravidla předmětu 3 Studijní materiály 3.1 Skriptum 3.2 Cvičenia 3.3 Neoficiální 4 Semestrální písemky 4.1 2. semestrální písemka 5 Zkoušky 5.1 Zkouška 2.6.2013 5.2 Zkouška 7.6.2012 5.3 Zkouška 2.6.2011. 5.4 Zkouška 18.5.2010.

1. semestr 2. semestr 3. semestr 4. semestr 5. semestr 6. semestr Povinné předměty DMA ¤ LAG PR1 ¤ RPH ALG ¤ BP1 ¤ LGR MA2 ¤ PR2 JAG ¤ PSI ¤ SPS APO ¤ BP2 ¤ FYZ OPT SZZ - LS 2012 Inf. a poč. vědy NUM ¤ OSS DS ¤ FLP ¤ ZUI RPZ Počítačové syst. EAM ¤ EM DSP ¤ OSD PKS ¤PSR ¤NVS Softwarové syst. OSS ¤ SI ASS ¤ DS ¤ TUR WA1 Volitelné předměty ACM ¤ EPD ¤ ET1 ¤ FI1 ¤ HI1 ¤ HSD ¤ HT1 ¤ IA+AZK ¤ MME ¤ MMP ¤ MPS ¤ PAP ¤ PPR ¤ PRS ¤ RET ¤ SOJ ¤ UFI Grafický minor PGR ¤ MVR ¤ KMA ¤ MGA ¤ GRT

Info o předmětu

• A0B01LGR - Logika a grafy

• 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

• Google drive
• 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.

Neoficiální

demlovominimum.pdf

Semestrální písemky

Testy na Google drive

2. semestrální písemka

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), {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šky na Google drive

Zkouška 2.6.2013

zadání

Zkouška 7.6.2012

zadání

Zkouška 2.6.2011.

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.

zadání