Kalábovi

Kalábovic wikina

Uživatelské nástroje

Nástroje pro tento web


pitel:mat:start

Matematické struktury v informatice

AB = ¬AB

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

Axiomy

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

Struktura = (množina, binární operace)

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

grupoid uzavřenost
pologrupa asociativita2)
monoid neutrální prvek
grupa inverzní prvek

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

Podgrupy

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)!

Struktura = (množina, aditivní operace, multiplikativní operace)

okruh (M, +, ·): ((M, +) = komutativní grupa ∧ (M, ·) = monoid ∧ distributivita3)
obor integrity neexistují dělitelé „nuly“
těleso obor integrity (okruh), kde jsou všechny „nenulové“ prvky invertibilní4)
pole komutativní těleso
  • „Nula“ – neutrální prvek +
  • „Jedinčka“ – neutrální prvek ·
  • Pokud je (M, ·) komutativní monoid, je i struktura komutativní („komutativní okruh“).

Kongruence

g1g2h1h2g1h1g2h2

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

Pravá kongruence: g1g2g1wg2w

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

  1. Reflexivita: a ~ a
  2. Symetrie: a ~ bb ~ a
  3. Tranzitivita: a ~ bb ~ cc ~ a

Homomorfizmus

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í.

Prenexní tvar

  1. Odstranění zbytečných kvantifikátorů5)
  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í)

Metrika

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.

Norma

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)

||x||_p

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

Ortonormalizace

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

Pokud a * v1 + b * v2 = v3 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. φ1 = f1 / ||f1||
  2. hn = fn − (fn · φn−1)6) × φn−1 − (fn · φn−2) × φn−2 − …
  3. φn = hn / ||hn||
  4. Opakuj kroky 2 a 3, dokud máš vektory.

Příklad

  • f1 = (1, 1, 1)
  • f2 = (2, 1, 2)
  • f3 = (−1, 0, 1)
  1. φ1 = f1 / ||f1|| = (1, 1, 1) / sqrt(1² + 1² + 1²) = (1/sqrt(3), 1/sqrt(3), 1/sqrt(3))
  2. f2 · φ1 = (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. h2 = f2 − (f2 · φ1) × φ1 = (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. φ2 = (1/3, −2/3, 1/3) / sqrt(2/3) = (1/sqrt(6), −2/sqrt(6), 1/sqrt(6))
  5. f3 · φ1 = (−1, 0, 1) · (1/sqrt(3), 1/sqrt(3), 1/sqrt(3)) = 0
  6. f3 · φ2 = (−1, 0, 1) · (1/sqrt(6), −2/sqrt(6), 1/sqrt(6)) = 0
  7. h3 = f3 − (f3 · φ1) × φ1 − (f3 · φ2) × φ2 = (−1, 0, 1) − 0 × φ1 − 0 × φ2 = (−1, 0, 1)
  8. φ3 = (−1, 0, 1) / sqrt(2) = (−1/sqrt(2), 0, 1/sqrt(2))

Násobení matic

a2 b2
c2 d2
a1 b1 a1a2 + b1c2 a1b2 + b1d2
c1 d1 c1a2 + d1c2 c1b2 + d1d2

Grafy

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

Nejkratší cesty

  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.

Minimální kostry

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!
1)
A dokazuje B
2)
a(bc) = (ab)c
3)
a(b + c) = ab + ac
4)
Pro každý „nenulový“ prvek platí, že najdeš nějaký jiný prvek, kterým, když ho vynásobíš, dostaneš „jedničku“. To ale neznamená, že by (M, ·) byla grupa, protože pak by existovali dělitelé „nuly“!
5)
xB(y)
6)
Skalární součin: x1x2 + y1y2 + z1z2
/var/www/wiki/data/pages/pitel/mat/start.txt · Poslední úprava: 12. 10. 2017, 14.51:01 autor: pitel