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.

MA053 Matroid theory and combinatorial optimization

Fakulta informatiky
jaro 2019

Předmět se v období jaro 2019 nevypisuje.

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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Předpoklady
Graph theory MA010, Linear algebra (ANY).
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á 21 mateřských oborů, zobrazit
Cíle předmětu
The aim of this advanced subject is to introduce students to the basics of matroid theory and its connections to combinatorial optimization.
In this course the students will learn the core definitions of matroids and understand their meaning, and be able to use them in theoretical research or in applications of advanced combinatorial optimization.
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.
Literatura
    doporučená 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
Freely accessible 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
Předmět již není vypisován.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích jaro 2008.

MA053 Matroid theory and combinatorial optimization

Fakulta informatiky
jaro 2018

Předmět se v období jaro 2018 nevypisuje.

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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Předpoklady
Graph theory MA010, Linear algebra (ANY).
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á 21 mateřských oborů, zobrazit
Cíle předmětu
The aim of this advanced subject is to introduce students to the basics of matroid theory and its connections to combinatorial optimization.
In this course the students will learn the core definitions of matroids and understand their meaning, and be able to use them in theoretical research or in applications of advanced combinatorial optimization.
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.
Literatura
    doporučená 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
Freely accessible 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
Předmět již není vypisován.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích jaro 2008.

MA053 Matroid theory and combinatorial optimization

Fakulta informatiky
jaro 2017

Předmět se v období jaro 2017 nevypisuje.

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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Předpoklady
Graph theory MA010, Linear algebra (ANY).
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á 21 mateřských oborů, zobrazit
Cíle předmětu
The aim of this advanced subject is to introduce students to the basics of matroid theory and its connections to combinatorial optimization.
In this course the students will learn the core definitions of matroids and understand their meaning, and be able to use them in theoretical research or in applications of advanced combinatorial optimization.
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.
Literatura
    doporučená 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
Freely accessible 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
Předmět již není vypisován.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích jaro 2008.

MA053 Matroid theory and combinatorial optimization

Fakulta informatiky
jaro 2016

Předmět se v období jaro 2016 nevypisuje.

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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Předpoklady
Graph theory MA010, Linear algebra (ANY).
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á 21 mateřských oborů, zobrazit
Cíle předmětu
The aim of this advanced subject is to introduce students to the basics of matroid theory and its connections to combinatorial optimization.
In this course the students will learn the core definitions of matroids and understand their meaning, and be able to use them in theoretical research or in applications of advanced combinatorial optimization.
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.
Literatura
    doporučená 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
Freely accessible 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
Předmět již není vypisován.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích jaro 2008.

MA053 Matroid theory and combinatorial optimization

Fakulta informatiky
jaro 2015

Předmět se v období jaro 2015 nevypisuje.

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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Předpoklady
Graph theory MA010, Linear algebra (ANY).
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 basics of matroid theory and its connections to combinatorial optimization.
In this course the students will learn the core definitions of matroids and understand their meaning, and be able to use them in theoretical research or in applications of advanced combinatorial optimization.
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.
Literatura
    doporučená 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
Freely accessible 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
Předmět je vyučován jednou za dva roky.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích jaro 2008.

MA053 Matroid theory and combinatorial optimization

Fakulta informatiky
jaro 2014

Předmět se v období jaro 2014 nevypisuje.

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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Předpoklady
Graph theory MA010, Linear algebra (ANY).
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 basics of matroid theory and its connections to combinatorial optimization.
In this course the students will learn the core definitions of matroids and understand their meaning, and be able to use them in theoretical research or in applications of advanced combinatorial optimization.
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.
Literatura
    doporučená 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
Freely accessible 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
Předmět je vyučován jednou za dva roky.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích jaro 2008.

MA053 Matroid theory and combinatorial optimization

Fakulta informatiky
jaro 2013

Předmět se v období jaro 2013 nevypisuje.

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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Předpoklady
Graph theory MA010, Linear algebra (ANY).
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 basics of matroid theory and its connections to combinatorial optimization.
In this course the students will learn the core definitions of matroids and understand their meaning, and be able to use them in theoretical research or in applications of advanced combinatorial optimization.
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.
Literatura
    doporučená 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
Freely accessible 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
Předmět je vyučován jednou za dva roky.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích jaro 2008.

MA053 Matroid theory and combinatorial optimization

Fakulta informatiky
jaro 2012

Předmět se v období jaro 2012 nevypisuje.

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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Předpoklady
Graph theory MA010, Linear algebra (ANY).
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 basics of matroid theory and its connections to combinatorial optimization.
In this course the students will learn the core definitions of matroids and understand their meaning, and be able to use them in theoretical research or in applications of advanced combinatorial optimization.
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.
Literatura
    doporučená 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
Freely accessible 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
Předmět je vyučován jednou za dva roky.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích jaro 2008.

MA053 Matroid theory and combinatorial optimization

Fakulta informatiky
jaro 2011

Předmět se v období jaro 2011 nevypisuje.

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.
Předpoklady
Teorie grafu MA010, Linearni algebra (libovolne kody).
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á 23 mateřských oborů, zobrazit
Cíle předmětu
The aim of this advanced subject is to introduce students to basics 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...
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
Metody hodnocení
This is an advanced course, taught in English, and conducted quite informally (seminar-type). Evaluation by a written individual homework assignment (one), and 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
Předmět je vyučován jednou za dva roky.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích jaro 2008.

MA053 Matroid theory and combinatorial optimization

Fakulta informatiky
jaro 2010

Předmět se v období jaro 2010 nevypisuje.

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.
Předpoklady
Teorie grafu MA010, Linearni algebra (libovolne kody).
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á 23 mateřských oborů, zobrazit
Cíle předmětu
The aim of this advanced subject is to introduce students to basics 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...
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
Metody hodnocení
This is an advanced course, taught in English, and conducted quite informally (seminar-type). Evaluation by a written individual homework assignment (one), and 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
Předmět je vyučován jednou za dva roky.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích jaro 2008.

MA053 Matroid theory and combinatorial optimization

Fakulta informatiky
jaro 2009

Předmět se v období jaro 2009 nevypisuje.

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.
Předpoklady
Teorie grafu MA010, Linearni algebra (libovolne kody).
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 basics 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...
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
Metody hodnocení
This is an advanced course, taught in English, and conducted quite informally (seminar-type). Evaluation by a written individual homework assignment (one), and 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
Předmět je vyučován jednou za dva roky.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích jaro 2008.