Základní kurs oboru oboru informatika, ve kterém jsou uceleně probrány základní partie teorie grafů a množinových systémů jak po strukturální, tak po algoritmické stránce.
Poslední úprava: T_KAM (06.05.2001)
Inclusion-exclusion principle and its applications.
Generating functions.
Finite projective planes, latin squares.
Hall theorem and its applications.
Flows in digraphs.
k-connectivity of graphs.
Ramsey theory.
Poslední úprava: PANGRAC/MFF.CUNI.CZ (08.04.2010)
Podmínky zakončení předmětu -
Zápočet je nutnou podmínkou účasti u zkoušky.
Zápočet bude udělen za zisk 100 bodů udělovaných průběžně za písemné testy, řešení domácích úloh, aktivitu na hodinách, apod. Maximální možný počet bodů, které lze získat, je zhruba 150. Konkrétní pravidla pro zisk zápočtu stanoví cvičící příslušného kroužku.
Z průběžné povahy kontroly neplyne nárok na vypisování opravných termínů testů ani zadávání opravných domácích úloh.
Poslední úprava: Jelínek Vít, doc. RNDr., Ph.D. (06.09.2023)
Irena Penev (Winter 2020/2021): To obtain tutorial credit, students must obtain at least 40% total on HW assignments. The lowest two HW scores will be dropped. To take the exam, students must first obtain tutorial credit.
Poslední úprava: Penev Irena, Ph.D. (29.09.2020)
Literatura -
L. Kučera: Kombinatorické algoritmy
J. Matoušek, J. Nešetřil: Kapitoly z diskrétní matematiky
Poslední úprava: Fiala Jiří, doc. RNDr., Ph.D. (26.09.2023)
J. Matoušek, J. Nešetřil: Invitation to Discrete Mathematics, Oxford University Press (1998)
R. Diestel: Graph Theory (4th edition), Springer (2010)
Poslední úprava: Jelínek Vít, doc. RNDr., Ph.D. (22.11.2012)
Požadavky ke zkoušce -
Forma zkoušky je kombinovaná: písemná a ústní. Požadavky na znalosti u zkoušky odpovídají sylabu předmětu.
Je požadována i schopnost zobecnit a aplikovat získané teoretické znalosti při praktickém řešení úloh.
Poslední úprava: Jelínek Vít, doc. RNDr., Ph.D. (06.09.2023)
Irena Penev (Winter 2020/2021): To take the exam, students must first obtain tutorial credit. The exam will be written, and it will consist of problems similar to HW problems from the tutorial (English section). It will be possible to take the exam online (over Zoom). Depending on the COVID-19 situation, it may or may not be possible to take the exam in person at the Department.
Poslední úprava: Penev Irena, Ph.D. (29.09.2020)
Sylabus -
Dvojí počítání: Spernerova věta, Maximální počet hran grafu bez C4 a bez K3.
Počet koster grafu.
Vytvořující funkce (chápané jako Taylorovy řady), aplikace: Catalanova, Fibonacciho čísla, řešení rekurenci, asymptotika rekurencí.
Konečné projektivní roviny.
Samoopravné kódy, základní pojmy. Hammnigův kód, Hadamardův kód. Existence asymptoticky dobrých kódů (Gilbert-Varshamov). Hammingův dolní odhad.
Maximální párování v grafech, Hallova věta a aplikace (Birkhoff-von Neumannova věta), Tutteho věta.
k-souvislost, Mengerovy věty. Ušaté lemma, struktura 2-souvislých grafů.
Základní Ramseyovy věty, Ramseyova věta pro p-tice, nekonečná Ramseyova věta.
Königova věta o nekonečné větvi.
Poslední úprava: Jelínek Vít, doc. RNDr., Ph.D. (04.10.2023)
Double Counting: Sperner Theorem, The maximum number of edges in a graph without C4 and without K3.
Number of spanning trees (determinant proof) and electrical networks.
Generating functions (understood as Taylor series), applications: Catalan, Fibonacci numbers, solving recurrences, asymptotics of the solution.
Finite projective planes.
Error-correcting codes, basic properties. Hammnig code, Hadamard code. Existence of asymptotically good codes (Gilbert-Varshamov). Hamming's lower bound.
Maximum matching in graphs, Hall's theorem and its applications (Birkhoff-von Neumann theorem), Tutte theorem.
k-connectivity, Menger's theorem. Ear lemma, structure of 2-connected graphs.
Ramsey theorem, Ramsey theorem for p-tuples, Ramsey infinite theorem.
König's theorem on the infinite branch.
Course web page (Irena Penev, Winter 2020/2021): https://iuuk.mff.cuni.cz/~ipenev/NDMI011.html
Poslední úprava: Jelínek Vít, doc. RNDr., Ph.D. (06.09.2023)
