Discrete Mathematics - NMIN105

• Title: Diskrétní matematika
• Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2024
• 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
• Teaching methods: full-time
• Additional information: https://mj.ucw.cz/vyuka/2425/dm/
• Guarantor: prof. RNDr. Jaroslav Nešetřil, DrSc.; Mgr. Martin Mareš, Ph.D.
• Teacher(s): doc. RNDr. Jiří Fiala, Ph.D.; RNDr. Dominik Krasula; Bc. Ondřej Macháč; Mgr. Martin Mareš, Ph.D.; Mgr. Anna Mlezivová
• Class: M Bc. FM; M Bc. FM > Povinné; M Bc. FM > 1. ročník; M Bc. MMIB; M Bc. MMIB > Povinné; M Bc. MMIB > 1. ročník; M Bc. MMIT; M Bc. MMIT > Povinné; M Bc. OM; M Bc. OM > Povinné; M Bc. OM > 1. ročník
• Classification: Informatics > Discrete Mathematics; Mathematics > Discrete Mathematics
• Incompatibility : NDMA005
• Interchangeability : NDMA005
• Is interchangeable with: NDMA005

Annotation

English

Basic course in discrete mathematics for bachelor's program Mathematics. Elements of set theory (sets, relations), introduction to combinatorics and graph theory.

Last update: G_M (16.05.2012)

Czech

Základní přednáška z diskrétní matematiky pro všechny odborné obory bakalářského programu Matematika.

Last update: G_M (16.05.2012)

Course completion requirements

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.

Last update: Tancer Martin, prof. RNDr., Ph.D. (02.10.2023)

Literature

English

Jiří Matoušek, Jaroslav Nešetřil: Invitation to Discrete Mathematics; Oxford University Press; second edition(December 15, 2008)

Last update: Kynčl Jan, doc. Mgr., Ph.D. (04.02.2018)

Czech

J.Matoušek, J.Nešetřil: Kapitoly z diskrétní matematiky, Karolinum 2010

Last update: Mareš Martin, Mgr., Ph.D. (13.10.2024)

Requirements to the exam

Zkouška je ústní s písemnou přípravou. Zkouší se znalost a porozumění teorii probrané na přednášce a schopnost na uplatnit ji při řešení příkladů.

Last update: Mareš Martin, Mgr., Ph.D. (13.10.2024)

Syllabus

English

Basic techniques:

• proof by contradiction

• proof by induction

• minimal counterexample

• divisibility

• congruences

Combinatorial counting:

• counting strings with different properties

• permutations and two views of them (order vs. bijection)

• characteristic functions of subsets

• k-element subsets and binomial coefficients

• Binomial theorem and its consequences

Discrete probability:

• example problems on probability

• generalization: discrete probability space, elementary and compound events

• conditional probability

• total probability theorem (case analysis)

• Bayes theorem

• independence of events

• product of probability spaces

• random variable and its expectation

Principle of inclusion and exclusion:

• the hatcheck lady problem (permutations with no fixed point)

• principle of inclusion and exclusion

• asymptotic bounds (factorial, binomial coefficients)

Graphs:

• definition of a graph

• examples of graphs

• degree of a vertex, regular graphs, handshaking lemma

• operations on graphs: adding a vertex/edge, subdividing/contracting an edge

• isomorphism of graphs

• a bound on the number of non-isomorphic graphs on N vertices

• subgraphs and induced subgraphs

• path in a graph, connectivity, connected components

• distance in a graph, graph metric

• weighted graphs

• matrices of adjancency and incidence

• powers of adjacency matrix count walks

Trees:

• definition: a tree is a minimal connected graph

• spanning tree of a graph

• a tree is a connected acyclic graph

• a tree on N vertices has N-1 edges

• existence of leaves (average degree is smaller than 2)

• adding/removing a leaf doesn't change if a graph is a tree; induction using leaves

• equivalent characterizations of trees

• rooted trees

Relations and functions:

• ordered pairs and k-tuples

• cartesian product of sets

• relation

• functions as relations

• operations on relations (composition)

Equivalence relations:

• properties of relations (reflexivity, symmetry, transitivity)

• equivalence as a relation

• examples of equivalences

• characterization using equivalence classes

Orders:

• partial and linear (total) order

• minimum/maximum, minimal/maximal element, chain/antichain, supremum/infimum

• on finite sets: existence of a minimal element, linear extension

• isomorphism with respect to relations

• product of orders, inclusion is a power of a 2-element order

• existence of large chains/antichains

• application: Erdős-Szekeres theorem on existence of monotone subsequences

Planar embedding of graphs:

• informal definition of an embedding and its faces

• paths and cycles are planar and so are trees

• K_5 is non-planar

• embedding in a sphere and stereographic projection

• Euler formula

• upper bound on the number of edges of a planar graph

• existence of a vertex of degree at most 5

• Kuratowski's theorem (without proof)

• Platonic solids

Graph coloring:

• history: the 4 color problem

• duality of plane graphs, reduction of coloring of faces to coloring of vertices

• proper coloring, chromatic number

• 2-colorable graphs are those bipartite

• coloring by induction: trees are 2-colorable, planar graphs are 6-colorable

• the 5 color theorem

Graph properties:

• walks and tours in graphs, Eulerian tours

• existence of a closed Eulerian tour

• directed graphs and multigraphs

• strong and weak connectivity

• Eulerian tours in directed multigraphs

• Ramsey theorems

• lower bound on Ramsey numbers (probabilistic method)

Last update: Mareš Martin, Mgr., Ph.D. (13.10.2024)

Czech

Základní techniky:

• důkaz sporem

• důkaz indukcí

• nejmenší protipříklad

• dělitelnost

• počítání s kongruencemi

Kombinatorické počitání:

• počítání řetězců s různými vlastnostmi

• permutace a dva pohledy na ně (pořadí vs. bijekce)

• charakteristické funkce podmnožin

• k-prvkové podmnožiny a kombinační čísla

• Binomická věta a její důsledky

Diskrétní pravděpodobnost:

• příklady úloh na pravděpodobnost

• zobecnění: diskrétní pravděpodobnostní prostor, elementární a složené jevy

• podmíněná pravděpodobnost

• věta o úplné pravděpodobnosti (rozbor případů)

• Bayseova věta

• nezávislost jevů

• součin pravděpodobnostních prostorů

• náhodna veličina a střední hodnota

Princip inkluze a exkluze:

• problém šatnářky (permutace bez pevného bodu)

• princip inkluze a exkluze

• asymptotické odhady (faktoriál, kombinační čísla)

Grafy:

• definice grafu

• příklady grafů

• stupeň vrcholu, regulární grafy, princip sudosti

• operace s grafy: přidání vrcholu/hrany, dělení hrany, kontrakce hrany

• isomorfismus grafů

• odhad počtu neisomorfních grafů na N vrcholech

• podgrafy a indukované podgrafy

• cesta v grafu, souvislost, komponenty

• vzdálenost v grafu, metrika

• ohodnocené grafy

• matice sousednosti a incidence grafu

• mocniny matice sousednosti počítají sledy

Stromy:

• definice: strom je minimální souvislý graf

• kostra grafu

• strom je souvislý graf bez kružnic

• strom na N vrcholech má N-1 hran

• existence listu (průměrný stupeň je menší než 2)

• přidání/odebrání listu nezmění, zda je graf stromem, a indukce přes listy

• věta o ekvivalentních charakterizacích stromu

• zakořeněné stromy

Relace a funkce:

• uspořádané dvojice a k-tice

• kartézský součin množin

• definice relace

• funkce jako relace

• operace s relacemi (skládání)

Ekvivalence:

• vlastnosti relací (reflexivita, symetrie, transitivita)

• ekvivalence jako relace

• příklady ekvivalencí

• popis pomocí ekvivalenčních tříd

Uspořádání:

• částečné a lineární uspořádání

• největší/nejmenší, maximální/minimální prvek, řetězec/antiřetězec, supremum/infimum

• na konečných množinách: existence minimálního prvku, lineární rozšíření

• isomorfismus vzhledem k relacím

• součin uspořádání, inkluze je mocnina dvojprvkového uspořádání

• věta o dlouhém a širokém (existence velkého řetězce nebo antiřetězce)

• aplikace: Erdősova-Szekeresova věta o monotónní podposloupnosti

Kreslení grafů do roviny:

• neformální definice nakreslení a jeho stěn

• cesty a kružnice jsou rovinné, stromy taktéž

• graf K_5 není rovinný (rozbor případů)

• kreslení na sféru a stereografická projekce

• Eulerova formule

• horní odhad počtu hran rovinného grafu

• existence vrcholu stupně nejvýše 5

• Kuratowského věta (bez důkazu)

• platónská tělesa

Barvení grafů:

• Historie: problém čtyř barev

• dualita rovinných grafů, převod barvení stěn na barvení vrcholů

• dobré obarvení grafu, barevnost

• 2-obarvitelné grafy jsou ty bipartitní

• barvení indukcí: stromy jsou 2-obarvitelné, rovinné grafy jsou 6-obarvitelné

• věta o 5 barvách

Vlastnosti grafů:

• sledy a tahy v grafech, eulerovské tahy

• věta o existenci uzavřeného eulerovského tahu

• orientované grafy a multigrafy

• silná a slabá souvislost orientovaných grafů

• rozšíření eulerovských tahů na orientované multigrafy

• Ramseyovy věty

• dolní odhad Ramseyových čísel (pravděpodobnostní metoda)

Last update: Mareš Martin, Mgr., Ph.D. (13.10.2024)