Diskrétní matematika - NDMI002

• Anglický název: Discrete Mathematics
• Podoba výuky: přednáška+cvičení
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2022
• Počet semestrů výuky: 1
• Semestr: zimní
• E-Kredity: 5
• Rozsah, examinace: zimní s.:2/2, Z+Zk [HT]
• Počet míst: neomezen
• Maximální kapacita předmětu: 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
• Forma uskutečňování: prezenční
• Další informace: http://mj.ucw.cz/vyuka/dm/
• Možnost opakovaného zápisu: 2 / 2 / 2 / 2
• Garant: prof. RNDr. Jiří Fiala, Ph.D.; prof. RNDr. Martin Tancer, Ph.D.
• Vyučující: doc. RNDr. Martin Balko, Ph.D.; Bc. Klára Grinerová; Bc. Jan Hartman; Bc. Adam Holda; Bc. Vojtěch Káně; doc. Mgr. Martin Koutecký, Ph.D.; Mgr. Júlia Križanová; Ida Kryštůfková Kantor, M.Sc., Ph.D.; RNDr. Ondřej Pangrác, Ph.D.; Bc. Ján Plachý; Lluís Sabater Rojas; Maximilian Strohmeier, M.Sc.; doc. Hans Raj Tiwary, M.Sc., Ph.D.; doc. Mykhaylo Tyomkyn, Ph.D.
• Třída: Informatika Bc.
• Kategorizace předmětu: Informatika > Diskrétní matematika
• Neslučitelnost : NDMA005
• Je neslučitelnost pro: NDMI030, NUIN025, NDMA006
• Je prerekvizitou pro: NDMI021
• Je záměnnost pro: NUIN025, NDMI030, NDMA005

Anotace

čeština

Ú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)

angličtina

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

Poslední úprava: T_KAM (06.05.2001)

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

čeština

Předmět je zakončen zápočtem a zkouškou. Zápočet je podmínkou pro konání zkoušky.

Pro získání zápočtu je třeba získat 100 bodů udělovaných za písemné testy, případně i za řešení domácích úloh a další aktivity.

V důvodných případech (dlouhodobá nemoc, pobyt v zahraničí apod.) může cvičící stanovit individuální podmínky pro udělení zápočtu.

Poslední úprava: Fiala Jiří, prof. RNDr., Ph.D. (02.09.2026)

angličtina

The course concludes with a credit assessment and an examination. Credit is a condition for taking the exam.

To obtain the credit, students must achieve 100 points awarded for written tests, and where applicable, for completing set assignments and other activities.

In justified cases (long-term illness, stay abroad, etc.) the lecturer may set individual conditions for credit granting.

Poslední úprava: Fiala Jiří, prof. RNDr., Ph.D. (02.09.2026)

Literatura

čeština

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ří, prof. RNDr., Ph.D. (26.09.2023)

angličtina

J. Matoušek, J. Nešetřil: Invitation to Discrete Mathematics, Oxford University Press, 2008, 2nd edition.

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

Kontroly studia předmětu a podmínky pro jejich úspěšné vykonání, způsob hodnocení

čeština

Kontroly studia v rámci předmětu tvoří zejména písemné testy, případně řešení domácích úloh a další aktivity. Tyto kontroly jsou hodnoceny body, které se započítávají do podmínek pro získání zápočtu.

Zkouška ověřuje znalosti odpovídající sylabu předmětu v rozsahu, v jakém byl pokryt na přednáškách, cvičeních a v určeném samostudiu. Je požadována také schopnost aplikovat získané znalosti při řešení úloh.

Zkouška může být písemná, ústní nebo kombinovaná a může mít kontaktní nebo distanční formu. Formát zkoušky určuje vyučující. Při hodnocení zkoušky může být přihlédnuto k výsledku testů psaných v období výuky.

Poslední úprava: Fiala Jiří, prof. RNDr., Ph.D. (02.09.2026)

angličtina

Assessments within the course consist primarily of written tests, or the completion of set assignments and other activities. These assessments are marked on a points basis, which count towards the requirements for obtaining a credit.

The examination assesses knowledge corresponding to the course syllabus to the extent that it has been covered in lectures, seminars and the specified self-study. The ability to apply the acquired knowledge in problem solving is also required.

The examination may be written, oral or a combination of both, and may take the form of a face-to-face or distance assessment. The format of the examination is determined by the lecturer. The results of tests taken during the course may be taken into account when marking the examination.

Poslední úprava: Fiala Jiří, prof. RNDr., Ph.D. (02.09.2026)

Sylabus

čeština

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, prof. RNDr., Ph.D. (28.02.2023)

angličtina

Notation, motivating problems, the concept of a proof, proof by induction.

Combinatorics:

• Relation: mapping (function, permutation), equivalence.

• Partial ordering: chains and antichains, large implies tall or wide.

• 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:

• Probability space (at most countable, all subsets are events).

• Independent events, conditional probability.

• Random variable: distribution function, expectation, linearity, most common distributions.

Graph theory:

• Elementary notions: complete graph, complete bipartite graph, path, cycle, vertex degree, subgraph, isomorphism.

• Handshaking lemma.

• Eulerian graphs: trail, walk, characterisation, including directed case, strong and weak connectivity.

• Trees: various characterisations, existence of a leaf.

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

• Graph coloring: characterisation of bipartite graphs, d-degenerate graphs, 5-color theorem for planar graphs (Kempe's chains).

Optional topics:

• Erdős-Szekeres lemma on monotone subsequences.

• Probabilistic proofs (e.g. existence of a 3-paradoxical tournament).

• Graph score.

• Platonic solids.

• Sperner's lemma, application on the HEX game.

Poslední úprava: Tancer Martin, prof. RNDr., Ph.D. (28.02.2023)