SubjectsSubjects(version: 837)
Course, academic year 2018/2019
   Login via CAS
Combinatorics for bioinformatics - NDMI089
Title in English: Kombinatorika pro bioinformatiky
Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
Faculty: Faculty of Mathematics and Physics
Actual: from 2017
Semester: winter
E-Credits: 5
Hours per week, examination: winter s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Guarantor: RNDr. Ondřej Pangrác, Ph.D.
Class: Informatika Bc.
Classification: Informatics > Discrete Mathematics
Annotation -
Last update: (09.03.2015)
An introductionary course on combinatorics and graph theory for students of bioinfomatics.
Course completion requirements - Czech
Last update: RNDr. Ondřej Pangrác, Ph.D. (12.10.2017)

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 odpovídá 5%, lze takto nahradit nejvýše 20%).

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.

Literature -
Last update: (09.03.2015)

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

Requirements to the exam - Czech
Last update: 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.

Syllabus -
Last update: (09.03.2015)

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.

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html