SubjectsSubjects(version: 845)
Course, academic year 2018/2019
   Login via CAS
Matroid Theory - NDMI065
Title in English: Teorie matroidů
Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
Faculty: Faculty of Mathematics and Physics
Actual: from 2018 to 2018
Semester: summer
E-Credits: 6
Hours per week, examination: summer s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Additional information: http://kam.mff.cuni.cz/~pangrac/vyuka/matroid.html
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
Annotation -
Last update: 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.
Course completion requirements - Czech
Last update: 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.

Literature -
Last update: (05.05.2014)

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

Oxley: Matroid theory.

Truemper: Matroid decomposition.

Requirements to the exam - Czech
Last update: 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.

Syllabus -
Last update: 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.

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html