PředmětyPředměty(verze: 902)
Předmět, akademický rok 2022/2023
   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 2021
Semestr: zimní
E-Kredity: 5
Rozsah, examinace: zimní s.:2/2 [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Virtuální mobilita / počet míst: 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/kgbi20/
Garant: RNDr. Ondřej Pangrác, Ph.D.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Diskrétní matematika
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
Anotace -
Poslední úprava: IUUK (09.03.2015)
Základní přednáška z kombinatoriky a grafů určená pro studenty bioinformatiky.
Podmínky zakončení předmětu
Poslední úprava: RNDr. Ondřej Pangrác, Ph.D. (27.09.2020)

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.

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

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

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

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.

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

Charakterizace eulerovských grafů.

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

 
Univerzita Karlova | Informační systém UK