Předměty

Váš prohlížeč nepodporuje JavaScript nebo je jeho podpora vypnutá. Některé funkce nemusejí být dostupné.

Teorie matroidů - NDMI065

Anglický název:	Matroid Theory
Zajišťuje:	Informatický ústav Univerzity Karlovy (32-IUUK)
Fakulta:	Matematicko-fyzikální fakulta
Platnost:	od 2023
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, angličtina
Způsob výuky:	prezenční
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

Výsledky anket Termíny zkoušek Rozvrh LS Nástěnka

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.

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

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

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.

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

Požadavky ke zkoušce

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

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.

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