Diskrétní matematika - NMIN105
Anglický název: Discrete Mathematics
Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2024
Semestr: zimní
E-Kredity: 5
Rozsah, examinace: zimní s.:2/2, Z+Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: vyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
Další informace: https://mj.ucw.cz/vyuka/2425/dm/
Garant: prof. RNDr. Jaroslav Nešetřil, DrSc.
Mgr. Martin Mareš, Ph.D.
Vyučující: doc. RNDr. Jiří Fiala, Ph.D.
RNDr. Dominik Krasula
Bc. Ondřej Macháč
Mgr. Martin Mareš, Ph.D.
Mgr. Anna Mlezivová
Třída: M Bc. FM
M Bc. FM > Povinné
M Bc. FM > 1. ročník
M Bc. MMIB
M Bc. MMIB > Povinné
M Bc. MMIB > 1. ročník
M Bc. MMIT
M Bc. MMIT > Povinné
M Bc. OM
M Bc. OM > Povinné
M Bc. OM > 1. ročník
Kategorizace předmětu: Informatika > Diskrétní matematika
Matematika > Diskrétní matematika
Neslučitelnost : NDMA005
Záměnnost : NDMA005
Je záměnnost pro: NDMA005
Výsledky anket   Termíny zkoušek   Rozvrh ZS   Nástěnka   
Anotace -
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)
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)
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)
  • ekvivalence jako relace
  • příklady ekvivalencí
  • popis pomocí ekvivalenčních tříd

Uspořádání:

  • částečné a lineární uspořádání
  • největší/nejmenší, maximální/minimální prvek, řetězec/antiřetězec, supremum/infimum
  • na konečných množinách: existence minimálního prvku, lineární rozšíření
  • isomorfismus vzhledem k relacím
  • součin uspořádání, inkluze je mocnina dvojprvkového uspořádání
  • věta o dlouhém a širokém (existence velkého řetězce nebo antiřetězce)
  • aplikace: Erdősova-Szekeresova věta o monotónní podposloupnosti

Kreslení grafů do roviny:

  • neformální definice nakreslení a jeho stěn
  • cesty a kružnice jsou rovinné, stromy taktéž
  • graf K_5 není rovinný (rozbor případů)
  • kreslení na sféru a stereografická projekce
  • Eulerova formule
  • horní odhad počtu hran rovinného grafu
  • existence vrcholu stupně nejvýše 5
  • Kuratowského věta (bez důkazu)
  • platónská tělesa

Barvení grafů:

  • Historie: problém čtyř barev
  • dualita rovinných grafů, převod barvení stěn na barvení vrcholů
  • dobré obarvení grafu, barevnost
  • 2-obarvitelné grafy jsou ty bipartitní
  • barvení indukcí: stromy jsou 2-obarvitelné, rovinné grafy jsou 6-obarvitelné
  • věta o 5 barvách

Vlastnosti grafů:

  • sledy a tahy v grafech, eulerovské tahy
  • věta o existenci uzavřeného eulerovského tahu
  • orientované grafy a multigrafy
  • silná a slabá souvislost orientovaných grafů
  • rozšíření eulerovských tahů na orientované multigrafy
  • Ramseyovy věty
  • dolní odhad Ramseyových čísel (pravděpodobnostní metoda)

Poslední úprava: Mareš Martin, Mgr., Ph.D. (13.10.2024)