Teorie matroidů - NDMI065

• Anglický název: Matroid Theory
• Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2014 do 2014
• Semestr: zimní
• E-Kredity: 6
• 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
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Další informace: http://kam.mff.cuni.cz/~pangrac/vyuka/matroid.html
• 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

Anotace

čeština

Poslední úprava: T_KAM (18.04.2010)

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

angličtina

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

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.

Literatura

čeština

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

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

Oxley:Matroid theory

Truemper: Matroid decomposition

angličtina

Poslední úprava: IUUK (05.05.2014)

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

Oxley: Matroid theory.

Truemper: Matroid decomposition.

Sylabus

čeština

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

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

angličtina

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

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.