Základy kombinatoriky a teorie grafů - NMIN331

• Anglický název: Foundations of Combinatorics and Graph Theory
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2022
• Semestr: letní
• E-Kredity: 5
• Rozsah, examinace: letní 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í
• Garant: doc. RNDr. Pavel Valtr, Dr.
• Třída: M Bc. MMIB; M Bc. MMIB > Doporučené volitelné; M Bc. OM; M Bc. OM > Zaměření MSTR; M Bc. OM > Povinně volitelné
• Kategorizace předmětu: Informatika > Diskrétní matematika; Matematika > Diskrétní matematika
• Neslučitelnost : NDMA001
• Záměnnost : NDMA001
• Je záměnnost pro: NDMA001
• Ve slož. prerekvizitě: NMAG351

Anotace

čeština

Úvodní kurs, 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. Doporučeno pro zaměření Matematické struktury na Obecné matematice a pro obor MMIB.

Poslední úprava: G_M (16.05.2012)

angličtina

Basics of graph theory and systems of sets. Recommended for specialization Mathematical Structures within General Mathematics and for bachelor's program in Information security.

Poslední úprava: G_M (16.05.2012)

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

čeština

V průběhu semestru bude zadáno několik sérií příkladů, přičemž k dosažení zápočtu je potřeba získat alespoň 20 bodů, což odpovídá zhruba čtvrtině celkového počtu dosažitelných bodů. Termín pro vyřešení a sepsání úkolů bude zhruba do konce semestru a příklady je možné odevzdávat opakovaně, vždy se počítá nejlepší dosažený výsledek. Charakter zápočtu neumožňuje jeho opakování. Zápočet je nutnou podmínkou ke zkoušce.

Poslední úprava: Balko Martin, doc. RNDr., Ph.D. (15.02.2018)

angličtina

The credit for the exercise is given after obtaining at least 20 points for solving home problems, which is roughly a quarter of all points that can be obtained. The deadline for solutions is approximately until the end of the semester and it is possible to hand in the solutions repeatedly, only the best solutions are counted in for each problem. The nature of the conditions does not allow repeated attempts for obtaining the credit. Obtaining the credit is necessary before the exam.

Poslední úprava: Kratochvíl Jan, prof. RNDr., CSc. (18.02.2018)

Literatura

čeština

Literatura dle doporučení učitele.

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (17.04.2013)

angličtina

Literature according to the recommendation of the teacher.

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (17.04.2013)

Požadavky ke zkoušce

čeština

Zkouška je ústní, v nutných případech budu probíhat distančně přes internet. Zkouší se látka podle sylabu v rozsahu předneseném na přednášce. Zkouší se porozumění pojmům a jejich souvislostem, věty včetně důkazů i schopnost aplikovat nabyté znalosti na jednoduché problémy předneseným tématům blízké. Udělení zápočtu je nutnou podmínkou účasti na zkoušce.

Poslední úprava: Valtr Pavel, doc. RNDr., Dr. (11.02.2023)

angličtina

The exam is oral. The knowledge and skills examined correspond to the sylabus in extent presented during the lectures. Common understanding to all notions and their relationship, theorems including proofs and ability to apply the aquired skills to simple situations related to the topics of the class are subject of the examination. Credit from the recitations must be obtained prior to enroling to an exam.

Poslední úprava: Kratochvíl Jan, prof. RNDr., CSc. (18.02.2018)

Sylabus

čeština

Základy NP-úplnosti - nedeterministické Turingovy stroje, Cookova věta, základní NP-úplné problémy (3-splnitelnost, Hamiltonovská kružnice, nezávislá množina, exaktní pokrytí).

Odhady faktoriálu a binomických koeficientů.

Princip inkluze a exkluze a jeho aplikace (šatnářka).

Vytvořující funkce a jejich aplikace.

Konečné projektivní roviny, latinské čtverce a jejich ortogononalita.

Hallova věta a aplikace.

Toky v sítích.

k-souvislost grafů, Mengerovy věty pro (ne)orientovane grafy ve verzích pro vrcholy a hrany.

Základni Ramseyovy věty, věta pro p-tice, Schurova věta a další aplikace.

Poslední úprava: G_M (16.05.2012)

angličtina

Overview of basics of computational complexity and NP-completeness. 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: G_M (16.05.2012)