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 [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

Anotace

čeština

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

angličtina

Poslední úprava: T_KAM (06.05.2001)

Introduction to combinatorics and graph theory. We lay stress on active knowledge of basic definitions and methods (relation, mapping, graph, exact formulation of mathematical theorems, problem solving and proofs of simple statements).

Podmínky zakončení předmětu

čeština

Poslední úprava: Mgr. Martin Mareš, Ph.D. (30.09.2020)

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 stanoví cvičící. Z průběžné povahy kontroly neplyne nárok na vypisování opravných termínů testů ani náhradních domácích úkolů.

Zkouška v paralelce M. Mareše bude ústní s písemnou přípravou a bude pokrývat jak řešení příkladů, tak teorii. V paralelce M. Tancera se zkouška skládá z písemné části s řešením příkladů a ústní části z teorie. Podle epidemiologické situace může být písemná část nahrazena ústní, popřípadě může být zkouška u obou zkoušejících být vedena distančně online.

angličtina

Poslední úprava: doc. Hans Raj Tiwary, M.Sc., Ph.D. (25.09.2020)

Hans Raj Tiwary:

For passing the tutorial it is necessary to obtain 50% from weekly homeworks.

Due to the nature of requirements, there will not be additional opportunities to pass the tutorial.

It is necessary to pass the tutorial to be able to take the exam for course credit. It is possible to take the final exam remotely.

Literatura

čeština

Poslední úprava: G_I (25.01.2007)

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

angličtina

Poslední úprava: prof. Mgr. Milan Hladík, Ph.D. (22.11.2012)

J. Matousek, J. Nesetril: Invitation to Discrete Mathematics, Oxford University Press, 2008, 2nd edition.

Požadavky ke zkoušce

čeština

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.

angličtina

Poslední úprava: doc. Hans Raj Tiwary, M.Sc., Ph.D. (25.09.2020)

Hans Raj Tiwary:

There will be a written exam at the end of the semester to test knowledge and understanding of the course material as well as problem solving. The exam will have three parts, one dedicated to each of the above. It is necessary to pass each part in order to pass the exam. There will be three opportunities to take the written exam whose dates will be announced in advance.

Detailed format of the exam can be found on the course webpage.

Sylabus

čeština

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

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. Odhady faktoriálu a binomických koeficientů.

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ěpodobnost. 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, izomorfismus apod.

Charakterizace eulerovských grafů (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ý 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.

angličtina

Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (26.01.2018)

Basic notation, motivating examples, the concept of a proof, proof by induction.

Mappings, relations, equivalences. Permutations.

Basic combinatorial counting (the number of subsets, of subsets of size k, of all mappings, of all injective

mappings, of permutations). The binomial theorem. Estimates the factorial function and binomial

coefficients.

Inclusion-exclusion formula, applications (hatcheck lady).

Probability space (at most countable, all subsets are events). Independent events, conditional probability.

Random variable, distribution function. Expectation, examples of calculation.

Basic notions of graph theory, path/circuit/walk, isomorphism, etc.

Characterisation of Eulerian graphs (including directed case; strong and weak connectedness).

Trees (various characterisations, existence of a leaf).

Planar graphs, Euler's formula, maximum number of edges.

The chromatic number of a graph, characterisation of bipartite graphs, chromatic number of a d-degenerate

graph is at most d+1; 5-colorability of planar graphs (using Kempe's chains).

Partial orderings, chains and antichains, large implies tall or wide, Erdös-Szekeres lemma on monotone

subsequences.

Additional topics: the HEX game, score theorem.