Datové struktury a algoritmy

Podmínkou zápisu předmětu je dřívější úspěšné absolvování předmětů:

Logika (AD7B01LOG)
Matematická analýza (AD7B01MAA)
Pravděpodobnost a statistika (AD7B01PST)

Předmět nesmí být zapsán současně s:

Datové struktury a algoritmy (YD36DSA)

Přednášející:

Michal Píše (gar.), Petr Matyáš

Cvičící:

Michal Píše (gar.), Petr Matyáš

Předmět zajišťuje:

katedra počítačů

Anotace:

Složitost a správnost algoritmu; sekvence; rozptylování (asociativní pole); třídění a hledání; prioritní fronty; setříděné sekvence; generická optimalizace, softwarově-inženýrský pohled na algoritmizaci.

Požadavky:

Základní znalost programování, schopnost exaktního myšlení.

Osnova přednášek:

1. Časová složitost

2. Správnost algoritmu

3. Průměrná složitost

4. Randomizované algoritmy

5. Sekvence

6. Hashování

7. Třídění a hledání

8. Prioritní fronty

9. Setříděné sekvence

10. Generická optimalizace

11. Softwarově-inženýrský přístup k algoritmizaci

Osnova cvičení:

1. Časová složitost

2. Správnost algoritmu

3. Průměrná složitost

4. Randomizované algoritmy

5. Sekvence

6. Hashování

7. Třídění a hledání

8. Prioritní fronty

9. Setříděné sekvence

10. Generická optimalizace

11. Softwarově-inženýrský přístup k algoritmizaci

Cíle studia:

Cílem předmětu DSA je:

- naučit studenty knihovničku fundamentálních algoritmů,

- naučit studenty tyto algoritmy adekvátně přizpůsobovat,

- naučit studenty rozpoznávat situace, ve kterých se tyto algoritmy dají s úspěchem použít,

- naučit studenty analyzovat efektivitu algoritmů,

- naučit studenty formálně uvažovat o správnosti algoritmů a

- procvičit exaktní myšlení a vyjadřování.

Studijní materiály:

1. K. Mehlhorn, P. Sanders: Algorithms and Data Structures: The Basic Toolbox

2. K. Weihe: A Software Engineering Perspective on Algorithmics

3. Webová stránka předmětu: http://edux.feld.cvut.cz/courses/A7B36DSA/

Poznámka:

Rozvrh na zimní 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
Čt
Pá	místnost KN:E-126 Matyáš P. 11:00–12:30 LICHÝ TÝDEN (přednášková par. 1) Karlovo nám. Trnkova posluchárna K5

Rozvrh na letní semestr 2011/2012:

Rozvrh není připraven

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

• Inteligentní systémy (STM-A7B-přechodné) (povinný předmět programu)
• Manažerská informatika (STM-A7B-přechodné) (povinný předmět programu)
• Web a multimedia (STM-A7B-přechodné) (povinný předmět programu)
• Softwarové inženýrství (STM-A7B-přechodné) (povinný předmět programu)
• Inteligentní systémy (STM-A7B) (povinný předmět programu)
• Manažerská informatika (STM-A7B) (povinný předmět programu)
• Softwarové inženýrství (STM-A7B) (povinný předmět programu)
• Web a multimedia (STM-A7B) (povinný předmět programu)