PředmětyPředměty(verze: 964)
Předmět, akademický rok 2024/2025
   Přihlásit přes CAS
Teorie matroidů - NDMX065
Anglický název: Matroid Theory
Zajišťuje: Studijní oddělení (32-STUD)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2022
Semestr: letní
E-Kredity: 6
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í
Je zajišťováno předmětem: NDMI065
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
Prerekvizity : {NXXX007, NXXX008, NXXX009}
Neslučitelnost : NDMI065
Záměnnost : NDMI065
Výsledky anket   Termíny zkoušek   Rozvrh LS   Nástěnka   
Anotace -
Ú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)
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 -

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

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)
 
Univerzita Karlova | Informační systém UK