FI:MA052 Advanced Graph Theory II - Informace o předmětu
MA052 Advanced Graph Theory II
Fakulta informatikyjaro 2009
- Rozsah
- 2/1. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k, z.
- Vyučující
- prof. RNDr. Petr Hliněný, Ph.D. (přednášející)
RNDr. Robert Ganian, Ph.D. (pomocník) - 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
- Čt 14:00–16:50 B411
- Předpoklady
- Teorie grafů MA010. Dále je vhodná úvodní znalost výpočetní složitosti a predikátové logiky.
- 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 30 stud.
Momentální stav registrace a zápisu: zapsáno: 0/30, pouze zareg.: 0/30, pouze zareg. s předností (mateřské obory): 0/30 - 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 (program FI, M-IN)
- Informatika (program FI, N-IN)
- Matematická informatika (program FI, B-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
- Tzv. strukturální teorie grafů zažívá v poslední době nebývalý rozmach spojený s Teorií grafových minorů Robertsona a Seymoura, což je jeden z nejhlubších výsledků dosažených v diskrétní matematice vůbec.
Mimo jiné z této teorie vyplývá existence polynomiálních algoritmů pro velkou třídu grafových problémů, kde často ani není jasné, proč by měly být tyto problémy algoritmicky řešitelné.
Náplní přednášky je uvedení do celé oblasti strukturální teorie grafů a jejích aplikací.
Jsou vyloženy či alespoň naznačeny principy, na kterých tato teorie i její algoritmická využití stojí.
Velký důraz je kladen především na "šířkové" parametry grafů jako je tree-width nebo branch-width.
Studenti se především naučí nejnovější velmi pokročilé poznatky zmíněné oblasti teorie grafů. - Osnova
- Repetition of basic graph terms.
- Connectivity on graphs, different measures. Menger's theorem. Linking, submodular functions.
- Width decompositions and measures: tree-width, branch-width. Algorithmic applications.
- Minors and their basic properties, well-quasi-ordering, WQO on trees.
- Planar graphs, drawing on surfaces, forbidden minors.
- The Graph Minor Theorem, an outline.
- Advanced width measures: clique-width, rank-width.
- MS2- and MS1-theorems.
- Literatura
- DIESTEL, Reinhard. Graph theory. New York: Springer, 1998, xiv, 286. ISBN 0387982108. 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/AGTS.html
Free online access to the course book: Diestel, Reinhard. Graph theory. "http://diestel-graph-theory.com/GrTh.html"
Supplementary literature (in Czech): Petr Hliněný. Teorie grafů, "http://www.fi.muni.cz/~hlineny/Vyuka/GT/". - Další komentáře
- Předmět je vyučován jednou za dva roky.
- Statistika zápisu (jaro 2009, nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/jaro2009/MA052