Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
36PT Programovací techniky Rozsah výuky:3+2
Přednášející (garant):Hudec B. Typ předmětu:S Zakončení:Z,ZK
Zodpovědná katedra:336 Kreditů:5 Semestr:L

Anotace:
Stěžejní náplní předmětu je specifikace a implementace datových typů včetně souborů dat, výklad metod řazení a vyhledávání v jednorozměrném i vícerozměrném prostoru. Klade se důraz na efektivitu (operační a paměťovou složitost) algoritmů. Jsou zde vyloženy základní metodiky tvorby efektivních algoritmů. Předmět navazuje na předmět Výpočetní technika a programování.

Osnovy přednášek:
1. Základní matematické pojmy. Operační a paměťová složitost algortmů.
2. Metody řazení (výb., vkl., zaměň., Quick-, Heap-, Radix-sort)
3. Vyhledávání, přímý přístup, vyhledávání s rozptylováním
4. Asociativní vyhledávání, hledání půlením a vyhledávácí stromy
5. Vícerozměrné vyhledávání a výpočetní geometrie
6. Datové struktury pro vícerozměrné vyhledávání, indexové soubory
7. Datové typy (Pole, Tabulka, Seznam, Relace, Graf)
8. Implementace datových typů: Zásobník, Fronta, Řetěz, Pole, Tabulka.
9. Implementace datových typů: Seznam, Relace, Graf.
10. Soubory dat, logická a fyzická skladba souborů, implementace souborů, řazení souborů
11. Rekurze a rekurzivní programování
12. Algoritmy prohledávání s návratem, dynamické programování
13. Techniky a zásady návrhu a tvorby programů

Osnovy cvičení:
1. Součty řad
2. Operační a paměťová složitost algoritmů
3. Algoritmus řazení vkládáním v poli a v seznamu
4. Algoritmy řazení Quick-sort, Heap-sort, Merge-sort, Radix-sort
5. Adresní vyhledávání, rozptylování s otevřenou adresací, návrh rozptylovací funkce
6. Vyhledávání binárním půlením, binární vyhledávací stromy
7. K-rozměrné vyhledávací stromy, KD-stromy, vyhledávání na intervalovou shodu, intervalové stromy
8. Segmentové stromy, vyhledání nejbližšího souseda, Voronoiův diagram
9. Specifikace abstraktních datových typů, kontrolní test
10. Implementace polí a tabulek
11. Implementace seznamů, grafů a relací
12. Operace se soubory. Aktualizace a řazení sekvenčních souborů
13. Složitost rekurzivních algoritmů. Algoritmy prohledávání s návratem
14. Zápočet

Literatura Č:
[1] Hudec, B.: Programovací techniky. Skripta ČVUT, Praha 1996
[2] Cormen,T.H., et al.: Introduction to ALGORITHMS. McGraw-Hill, New York 1990
[3] Manoocher, A.: Abstract Data Types and Algorithms. Macmillan Education Ltd., London

Literatura A:
[1] Cormen,T.H., et al.: Introduction to ALGORITHMS. McGraw-Hill, New York 1990
[2] Manoocher, A.: Abstract Data Types and Algorithms. Macmillan Education Ltd., London

Požadavky:

Rozsah výuky v kombinované formě studia: 19+4
Typ cvičení: s
Tento předmět je nabízen také v anglické verzi

Předmět je zahrnut do těchto studijních plánů:
Plán Obor Role Dop. semestr
*SELBE Silnoproudá elektrotechnika ZE Není
*DBEB Elektronika a sdělovací technika ZE Není
*VTBEB Výpočetní technika ZE Není
*SELBEB Silnoproudá elektrotechnika ZE Není
*KBEB Kybernetika a měření ZE Není
*VTBE Výpočetní technika ZE Není
*DBE Elektronika a sdělovací technika ZE Není
*KBE Kybernetika a měření ZE Není
*ZB Před zařazením do oboru S 4
*ZBB Před zařazením do oboru S 4
*VTZE Výpočetní technika S 4


Stránka vytvořena 25. 2. 2002, semestry: Z/2001-2, Z/2002-3, L/2001-2, L/2002-3, připomínky k informační náplni zasílejte správci studijních plánů Návrh a realizace: I. Halaška (K336), J. Novák (K336)