PředmětyPředměty(verze: 806)
Předmět, akademický rok 2017/2018
   Přihlásit přes CAS
Teorie matroidů - NDMI065
Anglický název: Matroid Theory
Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2017
Semestr: letní
E-Kredity: 6
Rozsah, examinace: letní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
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
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 -
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.
Literatura -
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

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

 
Univerzita Karlova | Informační systém UK