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

Přírodovědecká fakulta
jaro 2016
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 11:00–11:50 C04/211
  • Rozvrh seminárních/paralelních skupin:
C2142/01: St 11:00–12: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á. 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 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). 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. Online. Edited by Thomas H. Cormen. 3rd ed. Cambridge, Mass.: MIT Press, 2009. 1 online r. ISBN 0262533057. [citováno 2024-04-24] info
  • COMPEAU, Phillip a Pavel PEVZNER. Bioinformatics algorithms : an active learning approach. Online. La Jolla, Calif.: Active Learning Publishers, 2014. xxii, 362. ISBN 9780990374602. [citováno 2024-04-24] 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 2017, jaro 2019, jaro 2020, jaro 2021, jaro 2022, jaro 2023, jaro 2024, jaro 2025.