MA053 Matroid theory and combinatorial optimization

Fakulta informatiky
jaro 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
předmět má 20 mateřských oborů, zobrazit
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