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)
Hadi Zamani (Winter 2024/2025): To obtain tutorial credit, students must obtain at least 60/90 points from the HW assignments, or at least 60/100 points from the quizzes (best 2 of 3 quizzes count), or at least 100 points in total. To take the exam, students must first obtain tutorial credit.
Poslední úprava: Tkadlec Josef, Bc., Ph.D. (14.10.2024)
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)
Josef Tkadlec (Winter 2024/2025): To take the exam, students must first obtain tutorial credit. The exam has a combined form: written and oral. In the written part, you might be required to state a definition/theorem from the lecture; to prove a theorem from the lecture; and/or to solve a problem related to the material covered in the lecture/tutorial.
Poslední úprava: Tkadlec Josef, Bc., Ph.D. (14.10.2024)
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.
Poslední úprava: Tkadlec Josef, Bc., Ph.D. (14.10.2024)
