PředmětyPředměty(verze: 806)
Předmět, akademický rok 2017/2018
   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 2017
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: RNDr. Martin Tancer, Ph.D.
Mgr. Jan Kynčl, Ph.D.
doc. 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í).
Podmínky zakončení předmětu -
Poslední úprava: Mgr. Jan Kynčl, Ph.D. (11.10.2017)

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 přihlášení se ke zkoušce.

J. Amemori: Pro zisk zápočtu je potřeba získat 140 bodů. Za domácí úkoly a písemky bude možné získat alespoň 210 bodů. Dále je možné body získávat za občasné bonusové příklady. Písemky budou na každém cvičení krom posledního; na posledním cvičení bude "speciální písemka" na které bude možné v případě potřeby dohnat zmeškané body za předchozí písemky.

R. Hušek: Na zápočet je potřeba nasbírat 30 bodů z 50 možných. Budou písemky za 40 bodů a domácí úkoly za 10 bodů. Bonusové body bude možné získávat za aktivitu v hodině.

P. Korcsok: Na získání zápočtu je potřeba aspoň 60 bodů, z toho aspoň 20 bodů z domácích úloh a aspoň 20 bodů z písemek. Celkem sa dá získat 50 bodů za domácí úlohy a 50 bodů za písemky, bonusové body bude možné získat za aktivitu v hodině.

M. Mareš: Zápočet si lze vysloužit za získání alespoň 128 bodů za domácí úkoly. Každý domácí úkol lze řešit 14 dní od zadání za plný počet bodů, pak na cvičení bude poskytnuta nápověda a poté bude možné získat poloviční počet bodů.

J. Novotná: V průběhu semestru budou vypsány domácí úkoly za 40 bodů, velká písemka za 20 bodů a malé písemky dohromady za 20 bodů. Pro získání zápočtu bude třeba získat dohromady alespoň 50 bodů, přičemž alespoň 12 bodů z velké písemky nebo z malých písemek. Dále bude možné získávat bonusové body za aktivitu.

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ě).

M. Tancer: Pro zisk zápočtu je potřeba získat alespoň 70 bodů. V průběhu semestru budou vypsány dvě písemky dohromady na 100 bodů. Dále bude možné body získávat za aktivitu, příležitostné domácí úkoly a docházku (5 bodů při max. dvou absencích). Po skončení semestru bude "speciální písemka" na které bude možné v případě potřeby dohnat zmeškané body za obě předchozí písemky.

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: RNDr. Martin Tancer, Ph.D. (13.10.2017)

Forma zkoušky se liší u jednotlivých přednášejících, jak popíšeme níže. Teoretická část zkoušky bude z látky odpřednesené jednotlivými přednášejícími na přednášce a dále na zkoušce budou/mohou být početní příklady z této látky.

J. Kynčl: Zkouška bude ústní, studenti budou mít čas na přípravu řešení otázek a příkladů před jejich prezentováním zkoušejícímu.

M. Tancer: Zkouška bude mít písemnou a ústní část. Písemná část je povinná, ústní část je nepovinná, ale může sloužit k vylepšení známky, jak bude popsáno níže. Ústní část probíhá týž den jako písemná část. Z písemné části je možné získat známky 1, 2, 3, 3- nebo 4. Na ústní části lze vylepšit pouze známky 2, 3 nebo 3- (maximálně o jeden stupeň, známku 3- nejlépe na známku 3), nevylepšená známka 3- se počítá jako 4. V případě opakování termínu je potřeba psát opět i písemnou část.

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