Základní přednáška z diskrétní matematiky pro všechny odborné obory bakalářského programu Matematika.
Poslední úprava: G_M (16.05.2012)
Basic course in discrete mathematics for bachelor's program Mathematics. Elements of
set theory (sets, relations), introduction to combinatorics and graph
theory.
Poslední úprava: G_M (16.05.2012)
Podmínky zakončení předmětu
Pro zápočet je třeba získat 100 bodů z alespoň 150 možných udělovaných průběžně za písemné testy, řešení domácích úloh a další aktivity.
Z průběžné povahy kontroly neplyne nárok na vypisování opravných termínů testů ani zadání náhradních domácích úloh.
V důvodných případech (dlouhodobá nemoc, pobyt v zahraničí, apod.) může cvičící stanovit individuální podmínky na udělení zápočtu.
Zápočet je podmínkou pro konání zkoušky.
Poslední úprava: Tancer Martin, doc. RNDr., Ph.D. (02.10.2023)
Literatura -
J.Matoušek, J.Nešetřil: Kapitoly z diskrétní matematiky, Karolinum 2010
Poslední úprava: Mareš Martin, Mgr., Ph.D. (13.10.2024)
Jiří Matoušek, Jaroslav Nešetřil: Invitation to Discrete Mathematics; Oxford University Press; second edition(December 15, 2008)
Poslední úprava: Kynčl Jan, doc. Mgr., Ph.D. (04.02.2018)
Požadavky ke zkoušce
Zkouška je ústní s písemnou přípravou. Zkouší se znalost a porozumění teorii probrané na přednášce a schopnost na uplatnit ji při řešení příkladů.
Poslední úprava: Mareš Martin, Mgr., Ph.D. (13.10.2024)
Sylabus -
Základní techniky:
důkaz sporem
důkaz indukcí
nejmenší protipříklad
dělitelnost
počítání s kongruencemi
Kombinatorické počitání:
počítání řetězců s různými vlastnostmi
permutace a dva pohledy na ně (pořadí vs. bijekce)
charakteristické funkce podmnožin
k-prvkové podmnožiny a kombinační čísla
Binomická věta a její důsledky
Diskrétní pravděpodobnost:
příklady úloh na pravděpodobnost
zobecnění: diskrétní pravděpodobnostní prostor, elementární a složené jevy
podmíněná pravděpodobnost
věta o úplné pravděpodobnosti (rozbor případů)
Bayseova věta
nezávislost jevů
součin pravděpodobnostních prostorů
náhodna veličina a střední hodnota
Princip inkluze a exkluze:
problém šatnářky (permutace bez pevného bodu)
princip inkluze a exkluze
asymptotické odhady (faktoriál, kombinační čísla)
Grafy:
definice grafu
příklady grafů
stupeň vrcholu, regulární grafy, princip sudosti
operace s grafy: přidání vrcholu/hrany, dělení hrany, kontrakce hrany
isomorfismus grafů
odhad počtu neisomorfních grafů na N vrcholech
podgrafy a indukované podgrafy
cesta v grafu, souvislost, komponenty
vzdálenost v grafu, metrika
ohodnocené grafy
matice sousednosti a incidence grafu
mocniny matice sousednosti počítají sledy
Stromy:
definice: strom je minimální souvislý graf
kostra grafu
strom je souvislý graf bez kružnic
strom na N vrcholech má N-1 hran
existence listu (průměrný stupeň je menší než 2)
přidání/odebrání listu nezmění, zda je graf stromem, a indukce přes listy
věta o ekvivalentních charakterizacích stromu
zakořeněné stromy
Relace a funkce:
uspořádané dvojice a k-tice
kartézský součin množin
definice relace
funkce jako relace
operace s relacemi (skládání)
Ekvivalence:
vlastnosti relací (reflexivita, symetrie, transitivita)