Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Matroid Theory - NDMI065

Title:	Teorie matroidů
Form of teaching:	lecture+practicals
Guaranteed by:	Computer Science Institute of Charles University (32-IUUK)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2026
Duration in semesters:	1
Semester:	summer
E-Credits:	5
Hours per week, examination:	summer s.:2/2, C+Ex [HT]
Capacity:	unlimited
Maximum number of enrolled students:	unlimited
Min. number of students:	unlimited
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	not taught
Language:	Czech, English
Teaching methods:	full-time
Additional information:	http://kam.mff.cuni.cz/~pangrac/vyuka/matroid.html
Repeated enrollment:	2 / 2 / 2 / 2
Note:	the course is taught as cyclical

Guarantor:	RNDr. Ondřej Pangrác, Ph.D.
Class:	DS, diskrétní modely a algoritmy Informatika Mgr. - Diskrétní modely a algoritmy
Classification:	Informatics > Discrete Mathematics
Is incompatible with:	NDMX065
Is interchangeable with:	NDMX065

Opinion survey results Schedule Noticeboard

Annotation -

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.

Last update: Pangrác Ondřej, RNDr., Ph.D. (14.01.2005)

Course completion requirements - Czech

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.

Last update: Pangrác Ondřej, RNDr., Ph.D. (26.02.2019)

Literature -

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

Oxley: Matroid theory.

Truemper: Matroid decomposition.

Last update: IUUK (05.05.2014)

Course assessment methods and requirements for successful completion, grading scheme - Czech

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.

Last update: Pangrác Ondřej, RNDr., Ph.D. (14.02.2019)

Syllabus -

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.

Last update: PANGRAC/MFF.CUNI.CZ (10.04.2010)