Návrh algoritmů pro přírodovědce
C2142
Masarykova univerzita1. 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.