PředmětyPředměty(verze: 902)
Předmět, akademický rok 2022/2023
   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 [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Virtuální mobilita / počet míst: ne
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
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
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
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: doc. RNDr. Jiří Fiala, Ph.D. (26.07.2022)

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.

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

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

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

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.

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

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.
  • 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, Platónská tělesa.
  • 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).
  • Princip sudosti, skóre grafu.
  • Spernerovo lemma, aplikace na hru HEX.

 
Univerzita Karlova | Informační systém UK