|
Lecturer(s)
|
-
Adámek Adam, Ing.
-
Klika Zdeněk, Ing. Ph.D.
|
|
Course content
|
1. Complexity of algorithms - revision and extension of knowledge. Abstract data types 2. Searching and sorting algorithm - medians, quantils, bucket sort, radix sort, comparison of sorting algorithms 3. Data structures I - stack, queue, list, dictionary, inverted list 4. Data structures II - balanced searching trees (AVL, Red-Black, B), hash tables, graphs, sets 5. Graph algorithms - shortest path (Dijkstra, Floyd-Warshall), minimum spanning tree (Prim-Jarnik, Kruskal), bipartite graphs 6. Sets algorithms - generating of permutations and subsets 7. Text algorithms - string agreement, aproximate agreement, shortest and longest common subsequence 8. Data compression I - lossless algorithms (RLE, LZW, Huffman, arithmetic coding) 9. Data compression II - lossy methods (JPEG, wavelet compression, fractal compression 10. Cryptography - introduction, basic algorithms. 11. Programmer practice - using suitable data structures,effect of cache on program running, effect of floating point implementation of real numbers on calculation
|
|
Learning activities and teaching methods
|
Seminar classes, Lecture
- Contact hours
- 65 hours per semester
- Undergraduate study programme term essay (20-40)
- 30 hours per semester
- Preparation for an examination (30-60)
- 40 hours per semester
|
| prerequisite |
|---|
| Knowledge |
|---|
| algoritmizovat jednoduché problémy |
| programovat v některém ze základních programovacích jazyků (Java, C, Pascal) |
| Skills |
|---|
| analyzovat zadání jednoduché úlohy |
| vytvořit jednoduchý program v základním programovacím jazyce |
| napsat a odladit jednoduchý program ve vývojovém prostředí pro daný jazyk |
| vytvořit uživatelskou a programátorskou dokumentaci pro vytvořený program |
| Competences |
|---|
| N/A |
| learning outcomes |
|---|
| Knowledge |
|---|
| vyjmenovat a použít a implementovat základní datové struktury používané v informatice (zásobník, fronta, speciální vyhledávací stromy, slovníky, hashovací tabulky, množiny, grafy) |
| používat a implementovat základní algoritmy řazení a vyhledávání, grafové algoritmy (nejkratší cesta, minimální kostra grafu, toky v sítích) |
| používat a implementovat algoritmy zpracování textů, kombinatorické algoritmy a algoritmy komprese dat |
| vyjmenovat a vysvětlit základní algoritmy používané v kryptografii |
| Skills |
|---|
| analyzovat problém a zvolit vhodné datové struktury a algoritmy |
| vytvořit program v některém ze základních programovacích jazyků |
| vytvořit uživatelskou a programátorskou dokumentaci pro řešený problém |
| zhodnotit řešení problému, popř. navrhnout možné modifikace řešeného problému, které se nepodařilo realizovat |
| teaching methods |
|---|
| Knowledge |
|---|
| Lecture |
| Practicum |
| Skills |
|---|
| Practicum |
| Individual study |
| Competences |
|---|
| Practicum |
| Individual study |
| assessment methods |
|---|
| Knowledge |
|---|
| Written exam |
| Seminar work |
| Skills |
|---|
| Written exam |
| Skills demonstration during practicum |
| Seminar work |
| Competences |
|---|
| Skills demonstration during practicum |
| Seminar work |
| Individual presentation at a seminar |
|
Recommended literature
|
-
Cormen, Thomas H. Introduction to algorithms. MIT Press, 2009. ISBN 978-0262033848.
-
Goodrich, Michael T.; Tamassia, Roberto. Data structures and algorithms in Java. John Wiley & Sons, 2005. ISBN 0-471-73884-0.
-
McConnell, Steve. Dokonalý kód : umění programování a techniky tvorby software. Vyd. 1. Brno : Computer Press, 2005. ISBN 80-251-0849-X.
-
Sedgewick, Robert. Algorithms in Java. Pts. 1-4, Fundamentals, data structures, sorting, searching. 3rd ed. Boston : Addison-Wesley, 2003. ISBN 0-201-36120-5.
-
Skiena, Steven S. The algorithm design manual. 2nd ed. New York : Springer, 2008. ISBN 978-1-848-00-069-.
-
Töpfer, Pavel. Algoritmy a programovací techniky. 1. vyd. Praha : Prometheus, 1995. ISBN 80-85849-83-6.
|