Matematické struktury v informatice

A → B = ¬A ∨ B

• Argumentem komplexního čísla je jeho úhel vzhledem k reálné ose. Komplexní číslo má pak tvar r(cosφ + isinφ).

1. A → (B → A)
2. (A → (B → C)) → ((A → B) → (A → C))
3. (¬B → ¬A) → (A → B)

• Modus ponens (pravidlo odloučení) A → B můžeme přepsat na A ⊢ B¹⁾.
• Věta o dedukci je Modus ponens obráceně.
• Pravidlo zobecnění znamená, že někam připíšeš ∀x
• Axiom kvantifikátoru – ∀x(A ⇒ B) → (A ⇒ ∀xB)

http://algebra.matfyz.info/1/struktury.jpg, Template:Algebraic structures

Pokud je operace komutativní, je i struktura komutativní („komutativní grupoid“).

Zmenšíme M, případně upravíme operaci. Musí to ale pořád být grupa (nesmí z M zmizet neutrální a inverzní prvek)!

• „Nula“ – neutrální prvek +
• „Jedinčka“ – neutrální prvek ·
• Pokud je (M, ·) komutativní monoid, je i struktura komutativní („komutativní okruh“).

g₁ ≡ g₂ ∧ h₁ ≡ h₂ ⇒ g₁ ★ h₁ ≡ g₂ ★ h₂

• ★ je libovolná operace ve struktuře
• ≡ znamená kongruence

Pravá kongruence: g₁ ≡ g₂ ⇒ g₁ ★ w ≡ g₂ ★ w

Aby to vůbec mohla být kongruence, musí platit relace ekvivalence!

1. Reflexivita: a ~ a
2. Symetrie: a ~ b ∧ b ~ a
3. Tranzitivita: a ~ b ∧ b ~ c ∧ c ~ a

Zobrazení třeba z (ℂ, +) → (ℝ, ⊕).

f(a + b) = f(a) ⊕ f(b)
a, b ∈ ℂ

Když má ta struktura víc operací, musí se dokazovat pro všechny!

Jádro jsou ty prvky, které se zobrazí na neutrální prvek. Pokud má jádro právě jeden prvek, je homomorfizmus injektivní.

1. Odstranění zbytečných kvantifikátorů⁵⁾
2. Zbavení se spojek kromě ∧, ∨ a ¬
3. Přejmenování proměnných
4. Přesun kvantifikátorů doleva (a odstranění neatomických negací)

Metric (mathematics)

• Musí vždy vyjít kladné číslo.
• Pokud mají 2 body stejné souřadnice, musí vyjít 0.
• Vzdálenost z bodu A do bodu B musí být stejná jako z bodu B do bodu A.
• Trojúhelníková nerovnost.

Norm (mathematics)

Značí se ||x||, v podstatě je to dálka vektoru. Euklidovská norma je sqrt(x² + y² + z²).

• Musí vždy vyjít kladné číslo.
• ||x|| = 0, pouze pokud x je nulový vektor.
• ||ax|| = |a| · ||x||
• ||x + y|| ≤ ||x|| + ||y|| (Trojúhelníková nerovnost)

Norma implikuje metriku: |a, b| = ||a − b||

To jako že najdeme bázi jednotkových a kolmých vektorů.

Pokud a * v₁ + b * v₂ = v₃ má řešení, nejsou vektory lineárně nezávislé, tudíž nejsou bázové a nemá to řešení!

Vstupem je nějaká báze (lineárně nezávislé vektory, je jich tolik, jako má prostor dimenzí).

1. φ₁ = f₁ / ||f₁||
2. h_n = f_n − (f_n · φ_n−1)⁶⁾ × φ_n−1 − (f_n · φ_n−2) × φ_n−2 − …
3. φ_n = h_n / ||h_n||
4. Opakuj kroky 2 a 3, dokud máš vektory.

• f₁ = (1, 1, 1)
• f₂ = (2, 1, 2)
• f₃ = (−1, 0, 1)

1. φ₁ = f₁ / ||f₁|| = (1, 1, 1) / sqrt(1² + 1² + 1²) = (1/sqrt(3), 1/sqrt(3), 1/sqrt(3))
2. f₂ · φ₁ = (2, 1, 2) · (1/sqrt(3), 1/sqrt(3), 1/sqrt(3)) = (2/sqrt(3) + 1/sqrt(3) + 2/sqrt(3)) = 5/sqrt(3)
3. h₂ = f₂ − (f₂ · φ₁) × φ₁ = (2, 1, 2) − 5/sqrt(3) × (1/sqrt(3), 1/sqrt(3), 1/sqrt(3)) = (2, 1, 2) − (5/3, 5/3, 5/3) = (1/3, −2/3, 1/3)
4. φ₂ = (1/3, −2/3, 1/3) / sqrt(2/3) = (1/sqrt(6), −2/sqrt(6), 1/sqrt(6))
5. f₃ · φ₁ = (−1, 0, 1) · (1/sqrt(3), 1/sqrt(3), 1/sqrt(3)) = 0
6. f₃ · φ₂ = (−1, 0, 1) · (1/sqrt(6), −2/sqrt(6), 1/sqrt(6)) = 0
7. h₃ = f₃ − (f₃ · φ₁) × φ₁ − (f₃ · φ₂) × φ₂ = (−1, 0, 1) − 0 × φ₁ − 0 × φ₂ = (−1, 0, 1)
8. φ₃ = (−1, 0, 1) / sqrt(2) = (−1/sqrt(2), 0, 1/sqrt(2))

• Suma stupňů všech uzlů = 2 × počet hran
• Grafy jsou izomorfní tehdy, pokud je dokážeš nakreslit jinak, ale přitom je to pořád stejný graf.
• Při reprezentaci grafu maticí bývají řádky odkud a sloupce kam.
• Artikulace je vrchol, který když odstraníme, zvýší se počet komponent.

1. Sled je libovolná posloupnost uzlů a hran.
2. Tah nesmí opakovat hrany (ale uzly může).
3. Cesta nesmí opakovat ani hrany ani uzly.

1. Dijkstra's algorithm – Neumí záporné smyčky.
2. Floyd–Warshall algorithm – Když na diagonále vyjde záporné číslo, je tam záporná smyčka. Matici následovníku na začátku vyplníme podle čísla sloupce.

Minimum spanning tree

• Kruskal's algorithm – Vybírej nejlevnější hrany dokud nemáš pokryté všechny uzly. Nesmí vzniknout kružnice!
• Prim's algorithm – Zvol si uzel, a z něj jdi nejlevnější hranou. Teď máš 2 uzly, zase přidej nejlevnější hranu. Atd. dokud nemáš všechny uzly. Zase bacha na kružnice!