MLG - zkouška

up:: MLG

Info

• 75min - 6 uloh (60b)
  • 1 = 60-51
  • 2 = 50-41
  • 3 = 40-31
  • F = 30-0
• Příklady
  • 1-2: Logika
  • 1-1: Množiny
  • 2-3: Grafy 2
  • 1-2: Automaty
• Info
  • 1x Slovní úloha
  • lehčí + definice
    • definice = 6b
  • 6 úloh po 10 bodech

Okruh

• 1-2: Logika
  • Pravdivostní tabulka + ❓
    • (tautalogie, kontradikce, splnitelnost, ekvivalence, důsledek)
  • Převod na (uplný) disjunktivní tvar
  • Minimalizace formulí (Quine-McCluskey)
• 1-1: Množiny
  • Množinové operace s reálnými množinami
  • ❓Venuv diagram
  • Klasifikace relace
  • Doplnění relace na T, E nebo U
• 2-3: Grafy 2
  • Skore + ❓
  • Eulerovský tah
  • Kostry
    • Všechny
    • Minimální + ❓
  • Dijkstruv algoritmus + ❓
  • (pre | post | in)fix
  • maximální tok
  • kritický cesta
• 1-2: Automaty
  • Konstrukce
  • Minimalizace

Leaked TESTY

---

Definice

Transclude of MLG_Definice_discord.docx

• MLG definice

---

[Rewind]

Logika

• ❓Tabulka (Důsledky, Ekvivalence)
  • ❓
    • <-> právě tehdy
    • odkaz formule (1)
    • Zadání 1 ⇒ otázka 1 ⇒ Ano
  • 
    • 1->0 = 0
• Disjunktivní tvar
  • Morganovy pravidla
    • A→B ≡ A'vB
    • v (∧) a ()v() = (konjukce)disujkce(-/-)
    • 
  • úplný ⇒ roznásobit
    • každá s každým (ABC)
    • 1. 1 = (BvB')
    • 2. x∧B, x∧¬B
• Minimalizace 1** (Quine)
  • sloupce AB' → 1-1
    • nahradit *
    • postupně - všechny 1 (aby se nevracel 1-3✔, 3-1❌)
  • tabulka
    • co potřebujeme použít?
  • výsledek * = skip ((1-A,1-B,1-C))

Množiny

• ❓Vénův diagram
  • nezapomenout na celek a prvky mimo množinu
  • 
• Relace
  • Binární
    • ( R ↺ | S ⇄ | A → | T {zkratka} )
    • E = R+T+S ⇄
    • U = R+T+A →
  • Nezapnout skupiny

Grafy

Ne

• Skoré 3321 -> 210
  • score = počet hran (čar z bodu)
• Kostry
  • kostra = spojit všechny body s nejmenší počtem hran
  • Izomorfní (všechny) - jdou natáhnout na stejný tvar
  • Minimální
    • Hladový - od nejmenších hran
    • Jarníkův - nejmenší od zvoleného bodu

Both

• Eulerovský tah
  • liché vrcholy / 2 ⇒ start-end
• Dijkstra (shortest path)
  • nezapomenou
    • přičíst minulou hodnotu
    • opsat nepoužité hodnoty
    • vybrat pouze jeden

Orientovaný

• Notace
  • strom ⇒( <- pre | post -> i píše | in ->K-1x, Z-2x )
• Kritická cesta projektu
  • [->|<-]
    • -> MAX
      • (počkat na nejdelší task)
      • nepřehlídnout žádnou hranu !
    • <- MIN (>max: = max)
  • Kritické
    • ?
      • v = vrchol
        • kv - kritický vrchol
      • h = hrana
    • body ⇒ v1=v2
    • cesta ⇒ hrany (kv+h=kv2)
• Minimální tok
  • free|inUse
  • setup
    • vybraní cesty (1.└── 2.┌──)
    • inUse += minHrana
      • write (+{minHrana}) ((+4) └──)
    • repeat (0 in way)
  • max tok = součet hran do T |f|=?
    • (|f|=h1->t + h2->t)
  • min řez = utvar před režem ({S,A,C})

Automaty

( nezapomenout <->, 0,1 )

• Minimalizace
  1. Dosažitelnost
     • -> kam se to dostane?
  2. Skupiny
     • stejné a,b, <-> ⇒ α

Konstrukce

$, ^, _

[x]==[n]

+, :, <