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 2012 do 2013
• 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í
• Garant: doc. RNDr. Pavel Valtr, Dr.; prof. RNDr. Jan Kratochvíl, CSc.
• Vyučující: prof. RNDr. Jan Kratochvíl, CSc.; doc. Mgr. Jan Kynčl, Ph.D.; doc. RNDr. Pavel Valtr, Dr.
• Třída: M Bc. MMIB; M Bc. MMIB > Doporučené volitelné; M Bc. MMIT; M Bc. MMIT > Povinně 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

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

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)

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)