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

Přírodovědecká fakulta
jaro 2019
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, Ph.D. (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
Po 18. 2. až Pá 17. 5. Út 12:00–12:50 C04/211, Čt 14:00–15:50 C04/211
Předpoklady
Základní zkušenost s libovolným programovacím jazykem je výhodou, není však úplně nezbytná. Příklady jsou demonstrovány v jazyce Python.
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 20 stud.
Momentální stav registrace a zápisu: zapsáno: 0/20, pouze zareg.: 0/20, pouze zareg. s předností (mateřské obory): 0/20
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). Využití při práci s molekulovým grafem.
  • 9. Kostry (Prim, Kruskal, Union-Find). Využití při zpracování molekulového grafu.
  • 10. Přístupy k řešení problémů I (hrubá síla, rekurzivní algoritmy, rozděl a panuj, hladové algoritmy). Aplikace v oblasti chemoinformatiky a bioinformatiky.
  • 11. Přístupy k řešení problémů II (backtracking, dynamické programování, heuristiky). Aplikace v biologii a chemii.
  • 12. Těžké problémy (TSP, P vs. NP). Ukázky těžkých problémů v přírodních vědách.
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
  • COMPEAU, Phillip a Pavel PEVZNER. Bioinformatics algorithms : an active learning approach. La Jolla, Calif.: Active Learning Publishers, 2014, xxii, 362. ISBN 9780990374602. 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
Nachází se v prerekvizitách jiných předmětů
Předmět je zařazen také v obdobích jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2020, jaro 2021, jaro 2022, jaro 2023, jaro 2024, jaro 2025.