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 2015 do 2016
• 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í
• Způsob výuky: prezenční
• Garant: RNDr. Ondřej Pangrác, Ph.D.
• Třída: Informatika Bc.
• Kategorizace předmětu: Informatika > Diskrétní matematika

Anotace

čeština

Poslední úprava: IUUK (09.03.2015)

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

angličtina

Poslední úprava: IUUK (09.03.2015)

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

Literatura

čeština

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

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

T. Valla, J. Matoušek: Kombinatorika a grafy I

angličtina

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

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

Sylabus

čeština

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

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).

Toky v sítích.

Hallova věta a její aplikace, max. párování v bipartitním grafu.

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

angličtina

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

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.

Flows in networks.

Hall's theorem and its applications, matchings in bipartite graphs.

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