PředmětyPředměty(verze: 953)
Předmět, akademický rok 2023/2024
   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 2022
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, angličtina
Způsob výuky: prezenční
Způsob výuky: prezenční
Další informace: http://mj.ucw.cz/vyuka/dm/
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
Je neslučitelnost pro: NDMA006, NDMI030
Je prerekvizitou pro: NDMI021
Je záměnnost pro: NDMI030, NDMA005
Anotace -
Ú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í).
Poslední úprava: T_KAM (06.05.2001)
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.

Zkouška může být písemná, ústní nebo kombinovaná. Zkouška může mít kontaktní nebo distanční formu.

Formát zkoušky určuje vyučující.

U zkoušky může být přihlédnuto k výsledku testů psaných v období výuky.

Poslední úprava: Fiala Jiří, doc. RNDr., Ph.D. (26.07.2022)
Literatura -

J. Matoušek, J. Nešetřil: Kapitoly z diskrétní matematiky, nakladatelství Karolinum, Praha, 5. vydání, 2022

videozáznamy přednášek J. Nešetřila

některá kombinatorická témata pokrývají online dostupná skripta A. Slavík: Kombinatorika, MFF UK

Poslední úprava: Fiala Jiří, doc. RNDr., Ph.D. (26.09.2023)
Požadavky ke zkoušce -

Požadavky ke zkoušce odpovídají sylabu předmětu v rozsahu, v jakém byl pokryt na přednáškách, cvičeních a určeném samostudiu.

Je požadována i schopnost aplikovat získané znalosti při řešení úloh.

Zápočet je podmínkou pro konání zkoušky.

Poslední úprava: Fiala Jiří, doc. RNDr., Ph.D. (26.07.2022)
Sylabus -

Značení, motivační úlohy, co je důkaz, důkaz indukcí.

Kombinatorika:

  • Relace: zobrazení (funkce, permutace), ekvivalence.
  • Částečné uspořádání: řetězce a antiřetězce, věta o dlouhém a širokém.
  • Kombinatorické počítání: počet podmnožin, k-prvkových podmnožin, všech zobrazení, prostých zobrazení, permutací.
  • Binomická věta. Odhady faktoriálu a binomických koeficientů.
  • Princip inkluze a exkluze a jeho aplikace (šatnářka).

Pravděpodobnost:

  • Pravděpodobnostní prostor (nejvýš spočetný, všechny podmnožiny jsou jevy).
  • Nezávislé jevy, podmíněná pravděpodobnost.
  • Náhodná veličina: distribuční funkce, střední hodnota, linearita, základní diskrétní pravděpodobnostní rozdělení.

Teorie grafů:

  • Základní pojmy: úplný graf, úplný bipartitní graf, cyklus, cesta, stupeň vrcholu, podgraf, izomorfismus.
  • Princip sudosti.
  • Eulerovské grafy: tah, sled, charakterizace, též orientovaný případ, silná a slabá souvislost.
  • Stromy: různé charakterizace, existence listu.
  • Rovinné grafy: Eulerova formule, maximální počet hran.
  • Barevnost grafu: charakterizace bipartitních grafů, d-degenerované grafy, věta o pěti barvách pro rovinné grafy (Kempeho řetězce).

Rozšiřující témata:

  • Erdősovo-Szekeresovo lemma o monotónní podposloupnosti.
  • Pravděpodobnostní důkaz (např. existence 3-paradoxního turnaje).
  • Skóre grafu.
  • Platónská tělesa.
  • Spernerovo lemma, aplikace na hru HEX.

Poslední úprava: Tancer Martin, doc. RNDr., Ph.D. (28.02.2023)
 
Univerzita Karlova | Informační systém UK