Základy kombinatoriky a teorie grafů - NMIN331

• Anglický název: Foundations of Algorithms and Graph Theory
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2014 do 2021
• 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

Anotace

čeština

Poslední úprava: G_M (16.05.2012)

Ú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.

angličtina

Poslední úprava: G_M (16.05.2012)

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

Literatura

čeština

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

Literatura dle doporučení učitele.

angličtina

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

Literature according to the recommendation of the teacher.

Sylabus

čeština

Poslední úprava: G_M (16.05.2012)

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.

angličtina

Poslední úprava: G_M (16.05.2012)

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.