FI:MA053 Matroid theory - Informace o předmětu
MA053 Matroid theory and combinatorial optimization
Fakulta informatikyjaro 2008
- Rozsah
- 2/1. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: z.
- Vyučující
- prof. RNDr. Petr Hliněný, Ph.D. (přednášející)
- Garance
- prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Petr Hliněný, Ph.D. - Rozvrh
- Po 13:00–15:50 B411
- Předpoklady
- Teorie grafů MA010, Lineární algebra (libovolné kódy).
- Omezení zápisu do předmětu
- Předmět je nabízen i studentům mimo mateřské obory.
Předmět si smí zapsat nejvýše 50 stud.
Momentální stav registrace a zápisu: zapsáno: 0/50, pouze zareg.: 0/50, pouze zareg. s předností (mateřské obory): 0/50 - Mateřské obory/plány
- Aplikovaná informatika (program FI, N-AP)
- Bezpečnost informačních technologií (program FI, N-IN)
- Bioinformatika (program FI, N-AP)
- Informační systémy (program FI, N-IN)
- Informatika (angl.) (program FI, D-IN4)
- Informatika (program FI, D-IN4)
- Informatika (program FI, M-IN)
- Informatika (program FI, N-IN)
- Paralelní a distribuované systémy (program FI, N-IN)
- Počítačová grafika (program FI, N-IN)
- Počítačové sítě a komunikace (program FI, N-IN)
- Počítačové systémy (program FI, N-IN)
- Programovatelné technické struktury (angl.) (program FI, N-IN)
- Teoretická informatika (program FI, N-IN)
- Učitelství výpočetní techniky pro střední školy (program FI, M-SS)
- Učitelství výpočetní techniky pro střední školy (program FI, M-TV)
- Učitelství výpočetní techniky pro střední školy (program FI, N-SS) (2)
- Umělá inteligence a zpracování přirozeného jazyka (program FI, N-IN)
- Zpracování obrazu (program FI, N-AP)
- Cíle předmětu
- The aim of this advanced subject is to introduce students to the basic and selected advanced concepts of matroid theory and its connections to combinatorial optimization. Roughly saying, matroids present an algebraic/geometric generalization of graphs, and everybody should know their connection with the greedy algorithm. However, matroid theory includes much more interesting topic and this subject touches many of them, including some cutting edge development in the recent years. At the end, students should: understand basic principles of matroid theory including applications in optimization; and be able to continue with some scientific work in this area if they choose to.
- Osnova
- What is a matroid, relations to graphs and to linear algebra.
- Matroid representations, finite fields. Duality and minors.
- Matroids and the greedy algorithm.
- Totally unimodular matrices and regular matroids. Seymour's decomposition.
- Matroids and polyhedra, matroid intersection, Edmond's algorithm.
- Excluded minors for matroid representability, Rota's conjecture.
- Towards "matroid minor theory".
- Literatura
- OXLEY, James G. Matroid theory. 1st pub. Oxford: Oxford University Press, 1997, xi, 532. ISBN 0198535635. info
- Výukové metody
- This is an advanced theoretical course, taught in English, and conducted quite informally (a seminar-type lecturing). Students are expected to actively participate in all the lectures and tutorials.
- Metody hodnocení
- Evaluation is based on a mandatory written individual homework assignment (one essay), and on a subsequent oral exam.
- Vyučovací jazyk
- Angličtina
- Navazující předměty
- Informace učitele
- http://www.fi.muni.cz/~hlineny/Teaching/AMT.html
Study texts: * James Oxley, What is a matroid?, 2003. "http://www.math.lsu.edu/~oxley/survey4.pdf" * Alexander Schrijver, A course in combinatorial optimization, 2004. "http://homepages.cwi.nl/~lex/files/dict.pdf" - Další komentáře
- Studijní materiály
Předmět je vyučován jednou za dva roky.
- Statistika zápisu (nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/jaro2008/MA053