Diskrétní matematika - NMIN105

• Anglický název: Discrete Mathematics
• Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2023
• Semestr: zimní
• E-Kredity: 5
• Rozsah, examinace: zimní s.:2/2, Z+Zk [HT]
• Počet míst: 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
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Další informace: https://kam.mff.cuni.cz/~tancer/DiskretkaM/prednaska.html
• Garant: prof. RNDr. Jaroslav Nešetřil, DrSc.; Mgr. Martin Mareš, Ph.D.
• Třída: 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
• Kategorizace předmětu: Informatika > Diskrétní matematika; Matematika > Diskrétní matematika
• Neslučitelnost : NDMA005
• Záměnnost : NDMA005
• Je záměnnost pro: NDMA005

Anotace

čeština

Poslední úprava: G_M (16.05.2012)

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

angličtina

Poslední úprava: G_M (16.05.2012)

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

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

Poslední úprava: doc. RNDr. Martin Tancer, Ph.D. (02.10.2023)

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.

Literatura

čeština

Poslední úprava: doc. RNDr. Vít Jelínek, Ph.D. (08.09.2022)

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

P.Štěpánek, B.Balcar: Teorie množin, Academia Praha 1986

angličtina

Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (04.02.2018)

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

Požadavky ke zkoušce

Poslední úprava: doc. RNDr. Martin Tancer, Ph.D. (02.10.2023)

Zkouška je písemná s možností ústního dozkoušení. (V případně mimořádných okolností může přednášející rozhodnout o změně formátu zkoušky na zkoušku zcela písemnou, zcela ústní nebo distanční.)

Požadavky u zkoušky odpovídají tomu co bude probráno na přednášce, včetně schopnosti uplatnit probranou teorii při řešení příkladů.

Sylabus

čeština

Poslední úprava: doc. RNDr. Vít Jelínek, Ph.D. (08.09.2022)

Pojem množiny (Cantor), jazyk teorie množin, formule.

Popis množiny výčtem nebo jako množiny prvků "dané vlastnosti".

Základní operace s množinami (vč. potence a sumy) a jejich vlastnosti.

Kartézský součin, (binární) relace, skládání relací.

Funkce, funkce prostá, na, bijekce.

Vlastnosti relací (reflexivita, symetrie, ...).

Relace ekvivalence na množině, rozklad množiny, vzájemný vztah, příklady.

Kombinatorické počítání.

Počet zobrazení (prostých zobrazení) n-prvkové do m-prvkové množiny, počet podmnožin n-prvkové množiny.

Variace, permutace, kombinace.

Kombinační čísla, binomická věta.

Princip inkluze a exkluze.

Asymptotické odhady faktoriálu a kombinačních čísel.

Definice grafu, základní terminologie, izomorfismus grafů.

Stupeň vrcholu, princip sudosti, skóre grafu.

Cesty v grafu, souvislost, komponenty.

Metrika v grafu a pojmy z ní odvozené.

Stromy, jejich charakterizace a vlastnosti, počet stromů na dané množině.

Isomorfismus stromů, kódování stromů.

Kostra grafu, hledání minimální kostry.

Uspořádání, lineární uspořádání, největší/nejmenší, maximální/minimální prvek, řetězec/antiřetězec, supremum/infimum, příklady.

Existence minimálního prvku a věta o lineárním rozšíření pro konečné množiny.

Isomorfismus množin vzhledem k relacím.

Reprezentace částečného uspořádání pomoci inkluze.

Dobré uspořádání, princip indukce pro přirozená čísla.

Eulerovské tahy.

Eulerovské podgrafy a jejich popis pomocí vektorových prostorů (prostor cyklů a řezů).

Rovinné grafy.

Nakreslení grafu do roviny.

Eulerova formule a její důsledky.

Obarvení rovinného grafu pěti barvami.

Rozšiřující témata:

Ramseyova věta pro grafy, vícebarevná Ramseyova věta.

Dolní odhad Ramseyových čísel.

angličtina

Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (02.02.2018)

Notion of a set (Cantor), language of set theory, formula.

Describe a set by enumeration or as a set of elements of a given property.

Basic set operations (including power set and sums) and their properties.

Cartesian product, (binary) relations, composition of relations.

Functions, functions one-to-one, onto, bijections.

Properties of relations (reflexivity, symmetry, ...).

The equivalence relation on a set, the decomposition of a set, the correspondene, examples.

Combinatorial counting.

Number of mappings (injective mappings) from n-element to m-element set, number of subsets of an n-element set.

Variations, permutations, combinations.

Binomial coefficients, binomial theorem.

The Inclusion and Exclusion Principle.

Asymptotic estimates of factorials and binomial coefficients.

Graphs: definition, basic terminology, graph isomorphism.

Vertex degree, the handshaking lemma, graph score.

Paths in a graph, connectivity, components.

Graph metric, derived notions.

Trees: their characterization and properties, the number of trees on a given set.

Tree isomorphism, tree encoding.

Spanning tree, minimum spanning tree algorithms.

Partial order, linear order, the greatest/smallest, maximal/minimal element, chain/antichain, supremum/infimum, examples.

The existence of a minimal element and the linear extension theorem for finite sets.

Isomorphism of sets with respect to relations.

Representation of a partial order by inclusion.

Good ordering, induction principle for natural numbers.

Euler trails.

Euler subgraphs and their description using vector spaces (space of cycles and cuts).

Planar graphs.

Plane drawing of a graph.

Euler formula and its consequences.

Coloring of a planar graph by five colors.

Bonus topics:

Ramsey theorem for graphs, Ramsey multicolored theorem.

Lower bound on Ramsey numbers.