C2142 Návrh algoritmů pro přírodovědce

Přírodovědecká fakulta
jaro 2015
Rozsah
1/2. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: z.
Vyučující
doc. RNDr. Radka Svobodová, Ph.D. (přednášející)
RNDr. Tomáš Raček (přednášející)
Garance
prof. RNDr. Zdeněk Glatz, CSc.
Národní centrum pro výzkum biomolekul - Přírodovědecká fakulta
Dodavatelské pracoviště: Národní centrum pro výzkum biomolekul - Přírodovědecká fakulta
Rozvrh
Út 12:00–12:50 B11/205
  • Rozvrh seminárních/paralelních skupin:
C2142/01: Čt 12:00–13:50 C04/118, T. Raček
C2142/02: Čt 14:00–15:50 C04/211, T. Raček
Předpoklady
Základní zkušenost s libovolným programovacím jazykem je výhodou, není však úplně nezbytná.
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Předmět si smí zapsat nejvýše 60 stud.
Momentální stav registrace a zápisu: zapsáno: 0/60, pouze zareg.: 0/60, pouze zareg. s předností (mateřské obory): 0/60
Mateřské obory/plány
Cíle předmětu
Představit studentům stěžejní principy pro návrh efektivních algoritmů a datových struktur na zajímavých problémech z oblasti přírodních věd.
Na konci tohoto kurzu budou studenti umět popsat a aplikovat známé algoritmy pro řešení obvyklých problémů.
Navíc budou schopni navrhovat nové přístupy pro konkrétní aplikace s důrazem na efektivitu řešení.
Absolventi také získají schopnost kriticky posoudit a vybrat optimální řešení pro méně obvyklé problémy.
Osnova
  • 1. Od problému k algoritmu. Specifikace, korektnost.
  • 2. Úvod do složitosti. Ukázky přírodovědných problémů s logaritmickou, polynomiální a exponenciální složitostí.
  • 3. Základní datové struktury (spojový seznam, fronta, zásobník). Aplikace v biologii a chemii.
  • 4. Motivace k vyhledávání dat, řadicí algoritmy (binární půlení, Selection sort, Merge sort). Aplikace při zpracování chemoinformatických a bioinformatických dat.
  • 5. Vyhledávací stromy, haldy (BST, Heap sort). Aplikace při zpracování chemoinformatických a bioinformatických dat.
  • 6. Hashování, indexy. Možnosti využití v biologii a počítačové chemii.
  • 7. Základní pojmy teorie grafů, jejich reprezentace, metody prohledávání (BFS, DFS). Molekulový graf.
  • 8. Nejkratší vzdálenosti (Dijkstra, Bellman-Ford, Floyd-Warshall). Využití při práci s molekulovým grafem.
  • 9. Kostry (Prim, Kruskal). Využití při zpracování molekulového grafu.
  • 10. Přístupy k řešení problémů (hrubá síla, hladové algoritmy, rozděl a panuj). Aplikace v oblasti chemoinformatiky a bioinformatiky.
  • 11. Těžké problémy (TSP, SAT, P vs. NP). Ukázky těžkých problémů v přírodních vědách.
  • 12. Pokročilé datové struktury (AVL, B+ stromy, Union-Find). Aplikace v biologii a chemii.
Literatura
    doporučená literatura
  • Introduction to algorithms. Edited by Thomas H. Cormen. 3rd ed. Cambridge, Mass.: MIT Press, 2009. 1 online r. ISBN 0262533057. info
Výukové metody
Standardní přednáška doplněná cvičeními. Nepovinné domácí úkoly.
Metody hodnocení
Závěrečná písemná zkouška. Pro úspěšné ukončení zkouškou je potřeba alespoň 60 % bodů, pro ukončení zápočtem pak 40 %.
Informace učitele
http://www.fi.muni.cz/~xracek/c2142_spring2015/index.html
Další komentáře
Studijní materiály
Předmět je zařazen také v obdobích jaro 2014, jaro 2016, jaro 2017, jaro 2019, jaro 2020, jaro 2021, jaro 2022.