Discrete Mathematics - NDMI002

• Title: Diskrétní matematika
• Guaranteed by: Department of Applied Mathematics (32-KAM)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2022
• Semester: winter
• E-Credits: 5
• Hours per week, examination: winter s.:2/2, C+Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: Czech, English
• Teaching methods: full-time
• Teaching methods: full-time
• Additional information: http://mj.ucw.cz/vyuka/dm/
• Guarantor: doc. RNDr. Jiří Fiala, Ph.D.; doc. RNDr. Martin Tancer, Ph.D.
• Teacher(s): Mgr. Todor Antić; Sudatta Bhattacharya, M.Sc.; Bc. Barbora Dohnalová; Bc. Vojtěch Gaďurek; Bc. Klára Grinerová; Mgr. Tomáš Hons; Ida Kantor, M.Sc., Ph.D.; Bc. Petr Martinek; Lluís Sabater Rojas; doc. RNDr. Martin Tancer, Ph.D.; doc. Hans Raj Tiwary, M.Sc., Ph.D.; Bc. Josef Tkadlec, Ph.D.; Mgr. Mikuláš Zindulka
• Class: Informatika Bc.
• Classification: Informatics > Discrete Mathematics
• Incompatibility : NDMA005
• Is incompatible with: NDMA006, NDMI030
• Is pre-requisite for: NDMI021
• Is interchangeable with: NDMI030, NDMA005

Annotation

English

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

Last update: T_KAM (06.05.2001)

Czech

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

Last update: T_KAM (06.05.2001)

Course completion requirements

English

For credit you need to get 100 points out of at least 150 possible continuously awarded for tests, homework and other activities.

The ongoing nature of the inspection does not imply a right to request corrective tests nor alternative homework assignments.

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

Credit is a condition for taking the exam.

The exam can be written, oral or combined. The exam may be arranged in contact or distant form.

The exam format is decided by the educator(s).

Result of tests accomplished during the teaching period may be taken into account at the exam.

Last update: Fiala Jiří, doc. RNDr., Ph.D. (26.07.2022)

Czech

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.

Last update: Fiala Jiří, doc. RNDr., Ph.D. (26.07.2022)

Literature

English

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

Last update: Fiala Jiří, doc. RNDr., Ph.D. (05.08.2022)

Czech

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

Last update: Fiala Jiří, doc. RNDr., Ph.D. (26.09.2023)

Requirements to the exam

English

The requirements for the exam correspond to the syllabus of the subject to the extent that it was covered in lectures, tutorials and self-study.

The ability to apply the acquired knowledge in problem solving is also required.

Credit is a condition for taking the exam.

Last update: Fiala Jiří, doc. RNDr., Ph.D. (26.07.2022)

Czech

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.

Last update: Fiala Jiří, doc. RNDr., Ph.D. (26.07.2022)

Syllabus

English

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.

Last update: Tancer Martin, doc. RNDr., Ph.D. (28.02.2023)

Czech

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.

Last update: Tancer Martin, doc. RNDr., Ph.D. (28.02.2023)