Algoritmizace

Podmínkou zápisu předmětu je, že student získal v předchozích semestrech zápočet z následujících předmětů:

Programování (A0B36PRI)
Programování 1 (A0B36PR1)

Přednášející:

Marko Genyk-Berezovskyj (gar.), Radek Mařík

Cvičící:

Marko Genyk-Berezovskyj (gar.), Karel Bartoš, Michal Čáp, Petr Kalina, Radek Mařík, Přemysl Volf

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

URL: http://cw.felk.cvut.cz/doku.php/courses/a4b33alg/start

Rozvrh na zimní semestr 2011/2012:

Rozvrh není připraven

Rozvrh na letní semestr 2011/2012:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út
St	místnost 07:30–09:00 (přednášková par. 1 paralelka 107) místnost KN:E-308 Bartoš K. 09:15–10:45 (přednášková par. 1 paralelka 106) Karlovo nám. Lab K308místnost KN:E-308 Mařík R. 11:00–12:30 (přednášková par. 1 paralelka 105) Karlovo nám. Lab K308místnost KN:E-308 Mařík R. 12:45–14:15 (přednášková par. 1 paralelka 104) Karlovo nám. Lab K308místnost KN:E-308 Volf P. 14:30–16:00 (přednášková par. 1 paralelka 103) Karlovo nám. Lab K308místnost KN:E-308 Čáp M. 16:15–17:45 (přednášková par. 1 paralelka 102) Karlovo nám. Lab K308místnost KN:E-308 Kalina P. 18:00–19:30 (přednášková par. 1 paralelka 101) Karlovo nám. Lab K308
Čt	místnost T2:C3-132 Genyk-Berezovskyj M. Mařík R. 14:30–16:00 (přednášková par. 1) Dejvice Posluchárna
Pá

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)