Teorie matroidů - NDMI065

• Anglický název: Matroid Theory
• Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2024
• 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: nevyučován
• Jazyk výuky: čeština, angličtina
• Způsob výuky: prezenční
• Další informace: http://kam.mff.cuni.cz/~pangrac/vyuka/matroid.html
• Poznámka: předmět má cyklickou výuku
• Garant: RNDr. Ondřej Pangrác, Ph.D.
• Třída: DS, diskrétní modely a algoritmy; Informatika Mgr. - Diskrétní modely a algoritmy
• Kategorizace předmětu: Informatika > Diskrétní matematika
• Je neslučitelnost pro: NDMX065
• Je záměnnost pro: NDMX065

Anotace

čeština

Úvodní kurz teorie matroidů - definice matroidů (nezávislé množiny, báze, kružnice, ranková funkce), operace na matroidech (dualita a minory), souvislost matroidů, třídy matroidů a jejich reprezentace.

Poslední úprava: T_KAM (18.04.2010)

angličtina

Introduction to matroid theory - definitions (independent sets, basis, cycles, rank function), operations on matroids (duality and minors), matroidal connectivity, classes of matroids and their representations.

Poslední úprava: Pangrác Ondřej, RNDr., Ph.D. (14.01.2005)

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

Na zápočet je potřeba získat 2/3 bodů z aktivity na cvičení. Body je možné doplnit domácími úkoly.

Zápočet je nutnou podmínkou pro konání zkoušky.

Poslední úprava: Pangrác Ondřej, RNDr., Ph.D. (26.02.2019)

Literatura

čeština

D.Král', O.Pangrác: Introduction to Matroid Theory (Lecture Notes), ITI series 430 (2009).

Oxley:Matroid theory

Truemper: Matroid decomposition

Poslední úprava: PANGRAC/MFF.CUNI.CZ (10.04.2010)

angličtina

D. Kráľ, O. Pangrác: Introduction to Matroid Theory (Lecture Notes), ITI Series 430, 2009.

Oxley: Matroid theory.

Truemper: Matroid decomposition.

Poslední úprava: IUUK (05.05.2014)

Požadavky ke zkoušce

Požadavky ke zkoušce odpovídají sylabu předmětu v rozsahu, v jakém byl pokryt na přednáškách a cvičeních.

Zkouška má obvykle ústní podobu s možností písemné přípravy. Zápočet je podmínkou pro konání zkoušky.

Poslední úprava: Pangrác Ondřej, RNDr., Ph.D. (14.02.2019)

Sylabus

čeština

Definice a základní příklady. Dualita a minory. Souvislost matroidů a vztah ke grafové souvislosti. Matroid intersection theorem a jeho aplikace. Reprezentovatelnost, reprezentovatelné, binární a regulární matroidy. Grafové matroidy. Algoritmické aspekty matroidových problémů.

Poslední úprava: PANGRAC/MFF.CUNI.CZ (10.04.2010)

angličtina

Definitions and basic examples. Duality and minors. Connectivity of matroids and comparsion with graph connectivity. Matroid intersection theorem and its applications. Representability, representable, binary and regular matroids. Graphic matroids. Algorithmic aspects of matroids.

Poslední úprava: PANGRAC/MFF.CUNI.CZ (10.04.2010)