Algoritmizace

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra kybernetiky

Anotace:

Výuka algoritmizace probíhá tak, aby byla minimálně závislá na

programovacím jazyku, nicméně cvičená a přednášená v Javě. Výklad

datových struktur, základních algoritmů, funkcí, rekurze,

iterace. Stromy. Řazení a vyhledávání. Student je schopen aktivně

sestavovat algoritmy netriviálních úloh a hodnotit jejich efektivitu.

Požadavky:

Programování 1

Osnova přednášek:

1. Algoritmy, programy, programovací jazyky, úvodní přehled problematiky.

2. Jednorozměrná pole, jednoduché úlohy v 1D poli

3. Řazení v jednorozměrném poli (mergesort, quicksort, heapsort)

4. Vyhledávání v jednorozměrném poli

5. 2D pole, jednoduché úlohy v 2D poli

6. Řetězce, jednoduché úlohy zpracování textu, textové´ soubory

7. Asymptotická složitost, časová a paměťová náročnost algoritmů z bodů 3.- 6.

8. Jednoduché rekurzivní postupy, rekurzivní funkce, pokročilé techniky programování

9. Pojem souboru, sekvenční soubory, pojem záznamu, soubor záznamů

10. Datové typy seznam, zásobník, fronta, operace s nimi, jejich využití

11. Spojové struktury, lineární spojové seznamy, obecné spojové seznamy, stromy

12. Stromy, jejich vlastnosti. Binární stromy. Základní prohledávání.

13. Základní algoritmy úloh lineární algebry a matematické analýzy

14. Rezerva

Osnova cvičení:

1. Vstupní test, zopakování základů práce ve vývojovém prostředí, příklady na procedury, parametry, jednoduchá třída, zadání semestrální práce.

2. Práce s jednorozměrnými poli,

3. Řazení a hledání v jednorozměrných polích

4. Práce s vícerozměrnými poli

5. Zpracování textu, řetězce

6. Zjišťování časové a paměťové náročnosti algoritmů

7. Sekvenční soubory

8. Implementace abstraktních datových typů

9. Rekurze a iterace

10. Spojové struktury, lineární spojové seznamy, obecné spojové seznamy

11. Konstrukce stromů, hledání ve stromech

12. Test, konzultace k semestrální úloze

13. Základní algoritmy úloh lineární algebry a geometrie, matematické analýzy

14. Zápočet

Cíle studia:

Semestrální projekt skládající se z empirického hodnocení algoritmů řazení a hledání, porovnání iterační a rekurzivních algoritmů a odladění grafického výstupu vybraných algoritmů lineární algebry a matematické analýzy Tři fáze průběžné konzultace a kontroly podle jednotlivých úloh se závěrečným předvedením a obhajobou

Studijní materiály:

[1] Sedgewick, R: Algorithms (Fundamentals, Data structures, Sorting,

Searching), Addison Wesley, 2003

[2] Weiss, M: Data structures and Algorithm Analysis in Java, Addison Wesley, 1999

[3] Keogh, J: Data Structures Demystified, McGraw-Hill, 2004, český překlad 2006

[4] Wróblevski, P: Algorytmy, Helion, 2003, český překlad

Poznámka:

Rozsah výuky v kombinované formě studia: 14p+6c

Další informace:

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Otevřená informatika - Počítačové systémy (povinný předmět programu)
• Otevřená informatika - Informatika a počítačové vědy (povinný předmět programu)
• Otevřená informatika - Softwarové systémy (povinný předmět programu)
• Otevřená informatika, před rozřazením do oborů (povinný předmět programu)