PředmětyPředměty(verze: 837)
Předmět, akademický rok 2018/2019
   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 2018
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: doc. RNDr. Jiří Fiala, Ph.D.
doc. RNDr. Martin Tancer, 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í).
Podmínky zakončení předmětu -
Poslední úprava: Mgr. Martin Mareš, Ph.D. (15.10.2018)

Zápočet bude udělen za zisk dostatečného počtu bodů udělovaných průběžně za písemné testy, řešení domácích úloh, aktivitu na hodinách, popř. docházku. Přesné podmínky se však individuálně liší u jednotlivých vyučujících a budou popsány níže. Z průběžné povahy kontroly neplyne nárok na vypisování opravných termínů testů. Získání zápočtu je nutnou podmínkou pro skládání zkoušky.

J. Amemori: Je potřeba získat 2/3 bodů za domácí úkoly.

M. Balko: Na zápočet je třeba získat alespoň 90 bodů, přičemž celkem 80 lze získat za dvě písemky a zhruba 80 za průběžně zadávané domácí úkoly.

M. Berg: K udělení zápočtu je potřeba získat alespoň 60 bodů. Celkem 50 bodů půjde získat z domácích úkolů a 25 bodů za každou ze dvou písemek. Další bonusové body je možné získat za aktivitu na cvičení.

J. Pekárek: Je potřeba získat dostatečný počet bodů za domácí úkoly.

J. Syrovátková: Na zápočet je potřeba celkem 280 bodů. Budou se psát 3 písemky, každá za 100 bodů, dále domácí úkoly celkem za 100 bodů. Další body je možné získat za aktivitu na cvičení (dobrovolné domácí úkoly u tabule a podobně).

P. Zeman: Je potřeba získat aspoň 100 bodů za domácí úkoly.

Literatura -
Poslední úprava: G_I (25.01.2007)

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

Požadavky ke zkoušce -
Poslední úprava: Mgr. Martin Mareš, Ph.D. (15.10.2018)

Zkouška se skládá z písemné a ústní části. Ústní část proběhne formou diskuse řešení písemné části a případných doplňujících otázek.

Sylabus -
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (26.01.2018)
  • 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