this dir | view | cards | source | edit | dark top

Diskrétní matematika

Diskrétní matematika
Cvičení
  1. topinky – za 6 minut
Cvičení
  1. indukce – viz sešit

lze indukovat tak, že dokážeme platnost tvrzení pro n=1n = 1, n=2n = 2 a následně pro n+2n + 2

Přednáška

zkouška

Přednáška

a\ba \backslash b (a dělí b)

a\bc:b=aca \backslash b \equiv \exists c : b = a \cdot c

Přednáška

prvočíslo

definicetvrzenıˊdu˚kazveˇtadefinice \rightarrow tvrzení \xrightarrow{důkaz} věta

Přednáška

důkaz sporem

Přednáška

důkaz indukcí

Přednáška

příklad – pro X = {1, 2, 3, 4, 5}

Přednáška

Df: pro relace RX×YR \subseteq X × Y definujeme inverzní relaci R1Y×XR^{-1} \subseteq Y × X

xX,Y:yR1xxRy\forall x \in X, \forall \in Y: yR^{-1}x \equiv xRy

Přednáška

Df: pro relace RX×YR \subseteq X×YSY×ZS \subseteq Y×Z definujeme jejich složení RSX×Z:R \circ S \subseteq X×Z:

xX,zZ:x(RS)z(yY:xRyySz)\forall x \in X, \forall z \in Z: x(R \circ S)z \equiv (\exists y \in Y: xRy \land ySz)

Přednáška

příklad

Přednáška

Značení: f:XYf: X → Y

Přednáška

příklady

Přednáška

skládání funkcí

Přednáška

Df: Funkce f:xyf:x→y je

Přednáška

pro ff prostou: f1f^{-1} je funkce z Y' do X

přičemž Y' je množina všech obrazů, tedy všech f[X]f[X]

Přednáška

Df: relace R na X je

Přednáška

Df: (částečné) Uspořádání na množině X je relace R na X, která je reflexivní, antisymetrická a tranzitivní

Přednáška

Df: relace bezprostředního předchůdce

Přednáška

Df: pro ČUM (X,)(X,\leq) je xXx \in X:

Přednáška

Dk: zvolíme x1Xx_1 \in X libovolně

Přednáška

Df: AXA \subseteq X pro ČUM (X,)(X, \leq) je

Přednáška

Df: [n]:={1,,n}[n] := \{1, \dots, n\}

n-prvková množina od 1 do n

Přednáška

binomické koeficienty, binomická věta

Přednáška

n kuliček do k přihrádek

Přednáška

šatnářka

Přednáška

odhady faktoriálu

Přednáška

značení

Přednáška

rozšíření grafů

Přednáška

příklady

Přednáška

izomorfismus grafů

Přednáška

pokud vezmeme n vrcholů, kolik existuje grafů s touto množinou vrcholů?

Přednáška

indukovaný podgraf – vyberu si vrcholy z původního grafu a do nového grafu zdědím všechny hrany mezi nimi

Přednáška

cesta v grafu

Přednáška

odebrání vrcholu – musím odebrat odpovídající hrany

Přednáška

(V,E):EV2{(x,x)xV}(V,E): E \subseteq V^2 \setminus \{(x,x)|x\in V\}

nepovolíme smyčky (v podstatě zakážeme diagonálu na relaci)

Přednáška

dva druhy souvislosti

Přednáška

popis grafů pomocí matic

Přednáška

pro souvislý graf definujeme vzdálenost mezi dvěma vrcholy = počet hran v nejkratší cestě mezi dvěma vrcholy

Přednáška

důkaz Eulerovy formule (strom má o jeden vrchol víc než hran)

nejdřív musíme otrhat listy a potom je zpátky přidat – nestačí dokázat, že můžeme přidávat listy k grafu o jednom vrcholu a bude to platit stále

Přednáška

věta o charakterizaci stromů – pro graf G jsou tato tvrzení ekvivalentní

Přednáška

definice křivky

Přednáška

stěny nakreslení

Přednáška

které grafy jsou rovinné

Přednáška

kreslení na sféru

Přednáška

operace pro G rovinný

Přednáška

Kuratowského věta

G je nerovinný    \iffG obsahuje podgraf izomorfní s dělením K5K_5 nebo K3,3K_{3,3}

Přednáška

Dk: Zvolíme vv pevně, pak indukcí podle ee.

Přednáška

je-li G maximální rovinný s aspoň 3 vrcholy, ve všech jeho nakresleních jsou všechny stěny trojúhelníky (říká se jim rovinné triangulace)

Přednáška

počet hran pro triangulace

Přednáška

dk: doplníme do G hrany, až získáme maximální rovinný G'

v=v, ee, e=3v6, e3v6v'=v,\ e'\geq e,\ e'=3v'-6,\ e\leq 3v-6

Přednáška

důsledky

Přednáška

rovinný graf bez trojúhelníků

Přednáška

příklady

Přednáška

barvení stromu

Přednáška

věta: graf má barevnost nejvýše dva     \iff neobsahuje lichou kružnici

tedy bipartitní grafy jsou ty, které neobsahují liché kružnice

Přednáška

dk:

Přednáška

graf G je k-degenerovaný \equiv \exists \leq lineární uspořádání na V(G)V(G) t. ž. vV(G){u<v{u,v}E(G)}k\forall v \in V(G) |\lbrace u<v | \lbrace u,v \rbrace \in E(G) \rbrace| \leq k

Přednáška

dk #1: indukcí podle V|V|

Přednáška

dk #2:

Přednáška

příklady barvení z praxe

Přednáška

pravděpodobnostní prostor

Přednáška

diskrétní pravděpodobnostní prostor

Přednáška

příklad: n hodů mincí

Přednáška

pravděpodobnostní závorky

Přednáška

příklad (Bertrandův paradox)

Přednáška

příklad

Přednáška

definice nezávislých jevů

Přednáška

jevy jsou po 2 nezávislé, pokud pro libovolnou dvojici z množiny jevů platí, že se pravděpodobnost průniku rovná součinu pravděpodobností

Přednáška

příklad

Přednáška

příklad

Přednáška

míchání karet

Přednáška

věta o linearitě střední hodnoty

důkaz pomocí roztržení sumy

Přednáška

příklad


Přednáška

náhodná veličina

Přednáška

střední hodnota – vážený průměr X (jako „váhy“ použijeme pravděpodobnosti)

Přednáška

jevy J1,,JnJ_1,\dots,J_n

Přednáška

neorientovaný graf GG

Přednáška

algoritmus: rozdělíme VV na L,PL,P náhodně

pokud X<49100EX\lt{49\over 100}\cdot |E|, znovu

Přednáška

věta: Markovova nerovnost

Přednáška

důkaz

Přednáška

důkaz efektivity algoritmu výše

Přednáška

věta o Dlouhém a Širokém

Přednáška

Erdősovo-Szekeresovo lemma

Přednáška

klasifikace platónských těles pomocí rovinných grafů

Hurá, máš hotovo! 🎉
Pokud ti moje kartičky pomohly, můžeš mi koupit pivo.