PřF:C2142 Návrh algoritmů pro přírodověd - Informace o předmětu
C2142 Návrh algoritmů pro přírodovědce
Přírodovědecká fakultajaro 2024
- Rozsah
- 1/2/0. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: z.
- Vyučující
- RNDr. Tomáš Raček, Ph.D. (přednášející)
- Garance
- RNDr. Tomáš Raček, Ph.D.
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 19. 2. až Ne 26. 5. Po 9:00–9:50 B11/306
- Rozvrh seminárních/paralelních skupin:
C2142/02: Po 19. 2. až Ne 26. 5. Ú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á. 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 50 stud.
Momentální stav registrace a zápisu: zapsáno: 20/50, pouze zareg.: 0/50, pouze zareg. s předností (mateřské obory): 0/50 - Mateřské obory/plány
- Bioinformatika (program PřF, B-BIC)
- Epidemiologie a modelování (program PřF, B-MBB)
- Chemoinformatika a bioinformatika (program PřF, N-BCH)
- 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.
- Výstupy z učení
- 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 %.
- Další komentáře
- Studijní materiály
- Nachází se v prerekvizitách jiných předmětů
- Statistika zápisu (jaro 2024, nejnovější)
- Permalink: https://is.muni.cz/predmet/sci/jaro2024/C2142