Kombinatorika pro bioinformatiky - NDMI089

• Anglický název: Combinatorics for bioinformatics
• Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2023
• Semestr: zimní
• E-Kredity: 5
• Rozsah, examinace: zimní s.:2/2, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština, angličtina
• Způsob výuky: prezenční
• Další informace: https://iuuk.mff.cuni.cz/~pangrac/vyuka/kgbi23/
• Garant: RNDr. Ondřej Pangrác, Ph.D.
• Vyučující: RNDr. Ondřej Pangrác, Ph.D.
• Třída: Informatika Bc.
• Kategorizace předmětu: Informatika > Diskrétní matematika

Anotace

čeština

Základní přednáška z kombinatoriky a grafů určená pro studenty bioinformatiky.

Poslední úprava: IUUK (09.03.2015)

angličtina

An introductionary course on combinatorics and graph theory for students of bioinfomatics.

Poslední úprava: IUUK (09.03.2015)

Podmínky zakončení předmětu

Zápočet je udělen, pokud student získá alespoň 50% bodů ze všech písemek a domácích úkolů v průběhu semestru.

Zkouška předmětu je kombinovaná, sestává z písemné a ústní části, které jsou hodnoceny souhrnou známkou. Písemná část zkoušky sestává z několika příkladů v rozsahu 60-90 minut, témata korespondují se sylabem přednášky a odpovídají látce procvičované na cvičeních. Požadavky ústní části zkoušky odpovídají sylabu předmětu se zřetelem na látku prezentovanou na přednášce v aktuálním akademickém roce.

Poslední úprava: Pangrác Ondřej, RNDr., Ph.D. (27.09.2020)

Literatura

čeština

J. Matoušek, J. Nešetřil: Kapitoly z diskrétní matematiky

Poslední úprava: Pangrác Ondřej, RNDr., Ph.D. (01.10.2019)

angličtina

J. Matoušek, J. Nešetřil: An Invitation to Discrete Mathematics

Poslední úprava: Pangrác Ondřej, RNDr., Ph.D. (01.10.2019)

Požadavky ke zkoušce

Zápočet je nutnou podmínkou pro konání zkoušky.

Zkouška předmětu je kombinovaná, sestává z písemné a ústní části, které jsou hodnoceny souhrnou známkou. Písemná část zkoušky sestává z několika příkladů v rozsahu 60-90 minut, témata korespondují se sylabem přednášky a odpovídají látce procvičované na cvičeních. Požadavky ústní části zkoušky odpovídají sylabu předmětu se zřetelem na látku prezentovanou na přednášce v aktuálním akademickém roce.

Poslední úprava: Pangrác Ondřej, RNDr., Ph.D. (13.10.2017)

Sylabus

čeština

Základní značení, relace, ekvivalence, uspořádání.

Funkce a jejich druhy (injekce, surjekce), permutace.

Základní kombinatorické počítání (počet podmnožin, k-prvkových podmnožin, všech zobrazení, prostých zobrazení, permutací). Binomická věta.

Princip inkluze a exkluze a jeho aplikace.

Základy diskrétní pravděpodobnosti.

Základní pojmy z grafů, základní typy grafů (prázdný, úplný, bipartitní atd.), izomorfismus. Cesty a kružnice v grafech, souvislost.

Stromy (různé charekterizace, existence listu), kostra grafu.

Rovinné grafy, Eulerova formule, maximální počet hran.

Barevnost grafu, d-degenerovaný graf má barevnost nejvýš d+1, 5-barevnost rovinných grafů (přes Kempeho řetězce).

Charakterizace eulerovských grafů.

Hranová a vrcholová k-souvislost, Mengerova a Ford-Fulkersonova věta.

Poslední úprava: Pangrác Ondřej, RNDr., Ph.D. (01.10.2019)

angličtina

Basic notions, binary relations, equivalences and partially ordered sets.

Functions and their properties, permutations.

Combinatorial counting, Binomial theorem.

Principle of inclusion and exclusion and its applications.

Discrete probability.

Graphs - notions and examples. Paths and circuits in graphs, connectivity.

Trees, spanning trees of graphs.

Planar graphs, Euler's formula, max. number of edges.

Graph colorings, d-degenerate graphs. Five color theorem for planar graphs.

Eulerian graphs.

Higher connectivity, Menger's and Ford-Fulkerson's theorems.

Poslední úprava: Pangrác Ondřej, RNDr., Ph.D. (01.10.2019)