PředmětyPředměty(verze: 802)
Předmět, akademický rok 2016/2017
   Přihlásit přes CAS
Diskrétní matematika - NDMI002
Anglický název: Discrete Mathematics
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2016 do 2016
Semestr: zimní
E-Kredity: 5
Rozsah, examinace: zimní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Garant: prof. RNDr. Martin Loebl, CSc.
Mgr. Jan Kynčl, Ph.D.
Hans Raj Tiwary, M.Sc., Ph.D.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Diskrétní matematika
Neslučitelnost : NDMA005
Anotace -
Poslední úprava: T_KAM (06.05.2001)

Úvod do kombinatoriky a teorie grafů. Důraz je kladen na aktivní zvládnuti základních pojmů a metod (relace, zobrazení, graf; přesná formulace matematických tvrzení, řešení příkladů a dokazovaní jednoduchých tvrzení).
Literatura -
Poslední úprava: G_I (25.01.2007)

J. Matousek, J. Nesetril: Kapitoly z diskretni matematiky, nakladatelstvi Carolinum, Praha, 2000

Sylabus -
Poslední úprava: G_I (31.05.2012)

  • Základní značení, motivační příklady, co je důkaz, důkaz indukcí.
  • Funkce, relace, ekvivalence. Permutace.
  • Základní kombinatorické počítání (počet podmnožin, k-prvkových podmnožin, všech zobrazení, prostých zobrazení, permutací). Binomická věta.
  • Princip inkluze a exkluze a jeho aplikace (šatnářka).
  • Pravděpodobnostní prostor (nejvýš spočetný, všechny podmnožiny jsou jevy). Nezávislé jevy, podmíněná pravděpodnost. Náhodná veličina, distribuční funkce. Střední hodnota a její výpočet. (Základní diskrétní pravděpodobnostní rozdělení).
  • Základní pojmy z grafù, cesta/tah/sled, izomorsmus apod.
  • Charakterizace eulerovských grafù (též orientovaný případ, silná a slabá souvislost).
  • Stromy (různé charekterizace, existence listu).
  • Rovinné grafy, Eulerova formule, maximální počet hran.
  • Barevnost grafu, charakterizace bipartitních grafù, d-degenerovaný graf má barevnost nejvýš d+1, 5-barevnost rovinných grafù (přes Kempeho řetězce).
  • Částečné uspořádání, řetězce a antiřetězce, věta o dlouhém a širokém, Erdösovo-Szekeresovo lemma o monotónní podposloupnosti.

Rozšiřující témata: hra HEX; věta o skóre.

 
Univerzita Karlova | Informační systém UK