PředmětyPředměty(verze: 806)
Předmět, akademický rok 2017/2018
   Přihlásit přes CAS
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 2017
Semestr: zimní
E-Kredity: 5
Rozsah, examinace: zimní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
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 -
Poslední úprava: (09.03.2015)

Základní přednáška z kombinatoriky a grafů určená pro studenty bioinformatiky.
Literatura -
Poslední úprava: (09.03.2015)

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

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

Požadavky ke zkoušce
Poslední úprava: RNDr. Ondřej Pangrác, Ph.D. (20.09.2017)

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

Zápočet je možno získat splněním jednoho z následujících kritérií:

1) ziskem alespoň 50% bodů ze všech písemek v průběhu semestru (každá písemka je na 10-15 minut, celkem bude přibližně 6 písemek),

2) ziskem alespoň 60% bodů z písemek psaných během semestru, přičemž až dvě zameškané písemky mohou být napsány v oprvném termínu (konec semestru, během zkouškového),

3) ziskem alespoň 60% bodů dle bodu 2), kdy je navíc možné získat dodatečné body za aktivní účast na cvičení nebo průběžně zadávané domácí úkoly (dodatečný bod dopovídá 5%, lze takto nahradit nejvýše 20%).

Sylabus -
Poslední úprava: (09.03.2015)

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.

 
Univerzita Karlova | Informační systém UK