Kombinatorika a grafy 1 - NDMI011

• Anglický název: Combinatorics and Graph Theory 1
• 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, angličtina
• Způsob výuky: prezenční
• Garant: doc. RNDr. Vít Jelínek, Ph.D.; doc. RNDr. Jiří Fiala, Ph.D.
• Vyučující: doc. RNDr. Martin Balko, Ph.D.; doc. RNDr. Vít Jelínek, Ph.D.; Bc. Jiří Kalvoda; Bc. Václav Lepič; Mgr. David Mikšaník; Bc. Josef Tkadlec, Ph.D.; Hadi Zamani, M.Sc.
• Třída: Informatika Bc.
• Kategorizace předmětu: Informatika > Diskrétní matematika
• Neslučitelnost : NDMA001, NDMX011
• Záměnnost : NDMX011
• Je neslučitelnost pro: NDMI031, NDMX011
• Je prerekvizitou pro: NDMI069, NDMI021, NDMI068, NPFL049
• Je záměnnost pro: NDMA001, NDMI031, NDMX011

Anotace

čeština

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)

angličtina

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

čeština

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)

angličtina

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

čeština

L. Kučera: Kombinatorické algoritmy

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

J. Nešetřil: Teorie grafů

Videozáznamy přednášek

Některá kombinatorická témata pokrývají online dostupná skripta A. Slavík: Kombinatorika

Poslední úprava: Fiala Jiří, doc. RNDr., Ph.D. (26.09.2023)

angličtina

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

čeština

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)

angličtina

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

čeština

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)

angličtina

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)