A.Kaviþka : sylaby pĜednášek pĜedmČtu „Datové struktury“ v bakaláĜském studiu (Univerzita Pardubice) 2 / 17
Datové struktury prof. Ing. Antonín Kaviþka, Ph.D.
Zápoþet Pro udČlení zápoþtu je nutné nejpozdČji na posledním cviþení v semestru získat nejménČ 9 bodĤ.
Fakulta elektrotechniky a informatiky Katedra softwarových technologií
PĜednášky Teoretické poznatky o základních datových strukturách a jejich algoritmech
Cviþení
Semestrální práce
Maximální možný bodový zisk
Termín nejpozdČji možného odevzdání
A B C D (nepovinná)
4 4 3 4
5. týden 9. týden 12. týden 13. týden
Bodový zisk ze cviþení
Zlepšení klasifikaþního stupnČ maximálnČ o
10 11 12 13
Praktické procviþení implementací vybraných datových struktur a algoritmĤ (s využitím OOP) v rámci semestrálních prací Praktické uplatnČní abstraktních datových struktur
bodĤ bodĤ bodĤ bodĤ
½ 1 1½ 2
Vykonání zkoušky je možné pouze v pĜípadČ obdržení zápoþtu.
A.Kaviþka : sylaby pĜednášek pĜedmČtu „Datové struktury“ v bakaláĜském studiu (Univerzita Pardubice) 3 / 17
A.Kaviþka : sylaby pĜednášek pĜedmČtu „Datové struktury“ v bakaláĜském studiu (Univerzita Pardubice) 4 / 17
Doporuþená literatura a samostudium
Základní teze pĜednášek
Univerzitní knihovna
Wirth: Algoritmy a štruktúry údajov, Alfa 1988 Cenek, Klima, Janáþek: Optimalizace dopravních a spojových procesĤ, Univerzita Žilina, 1994 Volek, J.: Operaþní výzkum I, skripta DFJP UPa, Pardubice 2002 RozšiĜující literatura a Internet Knuth, D. E.: UmČní programování - Základní algoritmy, Computer Press 2008, ISBN: 978-80-251-2025-5 Knuth, D. E.: UmČní programování – Seminumerické algoritmy, Computer Press 2010, ISBN: 978-80-251-2898-5 Lewis, Denenberg: Data Structures and Their Algorithms, AddisonWesley 1997, ISBN 067339736X Cormen a kol.: Introduction to algorithms, MIT Press, Cambridge, 2001, ISBN 0-262-03293-7 Wróblewski: Algoritmy - datové struktury a programovací techniky, Computer Press 2004, ISBN 80-251-0343-9
Úvod do problematiky datových struktur a algoritmĤ Složitost (algoritmĤ a datových struktur) Správa (operaþní) pamČti Elementární organizace implementaþních prvkĤ v pamČti Množina LineárnČ uspoĜádaná množina (Pole, Lineární seznam, Zásobník, Fronta) Hierarchicky uspoĜádaná množina (Strom) Binární relace v množinČ Rozklad množiny na systém disjunktních podmnožin Prioritní fronta Tabulka Algoritmy tĜídČní tabulek Graf Soubory s pĜímým pĜístupem
A.Kaviþka : sylaby pĜednášek pĜedmČtu „Datové struktury“ v bakaláĜském studiu (Univerzita Pardubice) 5 / 17
1.
Úvod do problematiky datových struktur a algoritmĤ
A.Kaviþka : sylaby pĜednášek pĜedmČtu „Datové struktury“ v bakaláĜském studiu (Univerzita Pardubice) 6 / 17
ÚROVNċ:
APLIKAýNÍ
Úkol: Kvalitní realizace cílového modelu na poþítaþi vzhledem k (úspornému) využívání jeho pamČti a efektivitČ (rychlosti) frekventovanČ využívaných výpoþtĤ/algoritmĤ.
FYZICKÁ
DATOVÝ MODEL
PAMċġOVÁ REPREZENTACE
REÁLNÝ SVċT
PotĜeba zpracování údajĤ (spojených s existující nebo projektovanou/ myšlenou realitou) na poþítaþi vede k nutnosti modelování reality:
A. Vymezení objektu zkoumání (realita) B. Vymezení datového modelu na objektu zkoumání (abstrakce reality) C. Cílový model (implementace v pamČti poþítaþe)
ABSTRAKTNÍ (LOGICKÁ)
OBJEKTY
:
Atributy: barva nosnost nápravy umývárna koho veze .......
Datové modelování
TĜída Položka_X Položka_Y Vztah Operace_1 Operace_2
Skupina homogenních objektĤ v realitČ
PAMċġOVÁ MÍSTA S T R U K T U R Y
barva nosnost
veze
Implementace field attribute Boolean Real Pointer
Kritérium (abstrakce): cíl zpracování
A.Kaviþka : sylaby pĜednášek pĜedmČtu „Datové struktury“ v bakaláĜském studiu (Univerzita Pardubice) 7 / 17
Záznam Položka_A Položka_B Vztah
Kritérium: operace nad strukturou a jejich frekvence
A.Kaviþka : sylaby pĜednášek pĜedmČtu „Datové struktury“ v bakaláĜském studiu (Univerzita Pardubice) 8 / 17
Datové struktury a rĤzná použití abstrakce
PĜíklady
Abstrakce - datové modelování
9 ADT - reálné þíslo - nezabývá se konkrétní pamČĢovou reprezentací þísla - pĜíklad operací: +, -, *, /, int apod. - nezamČĜuje se na implementace operací, ale pouze na jejich výsledky
Abstraktní datový typ (Abstract Data Type - ADT) je matematická struktura sestávající ze dvou þástí: a) jedné nebo více domén, tj. tĜíd matematických objektĤ (prvkĤ) b) jedné nebo více matematických operací na prvcích tČchto domén ADT si lze pĜedstavit jako „þernou skĜíĖku“, jež pĜed uživatelem ukrývá (zapouzdĜuje) svoji vnitĜní stavbu. Je-li známo, jaký je použit vstup a operace, je možné urþit výstup (bez nutnosti vČdČt, co se událo uvnitĜ skĜíĖky).
Abstraktní datová struktura (Abstract Data Structure - ADS) pĜedstavuje jednu konkrétní realizaci (instanci) ADT. Je tedy možné uskuteþnit Ĝadu realizací daného ADT. ADS poskytují znovupoužitelnost (reusability) - budování bází struktur nezávislých na uživatelských datech.
ADS - type real ve vyšším programovacím jazyku - relativnČ složitá konkrétní vnitĜní pamČĢová reprezentace – mantisa & exponent - napĜ. sþítání dvou reálných þísel provádČno relativnČ složitým konkrétním algoritmem - uživatel/programátor nepotĜebuje znalost implementace napĜ. sþítání, nýbrž jen výstup/výsledek pĜíslušného algoritmu
A.Kaviþka : sylaby pĜednášek pĜedmČtu „Datové struktury“ v bakaláĜském studiu (Univerzita Pardubice) 9 / 17
A.Kaviþka : sylaby pĜednášek pĜedmČtu „Datové struktury“ v bakaláĜském studiu (Univerzita Pardubice) 10 / 17
9 ADT – poĜadník - doména: à sestává z blíže nespecifikovaných prvkĤ, které jsou vkládány do poĜadníku à z poĜadníku mĤže být odebrán ten jeho prvek, který byl do nČj zaĜazen dĜíve než všechny ostatní prvky v nČm obsažené - operace: à zaĜać nový prvek do poĜadníku à odeber prvek z poĜadníku à je poĜadník prázdný ?
ADS – poĜadník v dynamické zĜetČzené pamČti (DZP) - doména: à sestává z dynamicky alokovaných prvkĤ o stejné pamČĢové velikosti à prvky jsou explicitnČ lineárnČ zĜetČzeny à každý prvek obsahuje referenþní položku, jež odkazuje na pozdČji definovaná uživatelská data - operace: à zaĜać nový prvek na „konec“ zĜetČzení à odeber prvek z „þela“ zĜetČzení à je zĜetČzení prázdné ?
A.Kaviþka : sylaby pĜednášek pĜedmČtu „Datové struktury“ v bakaláĜském studiu (Univerzita Pardubice) 11 / 17
A.Kaviþka : sylaby pĜednášek pĜedmČtu „Datové struktury“ v bakaláĜském studiu (Univerzita Pardubice) 12 / 17
PoĜadník objednávek v internetovém knihkupectví uživatelská aplikace ADS (poĜadník v DZP)
Formy specifikace ADT
- poĜadník, implementovaný v rámci programového vybavení internetového obchodu, pĜedstavuje jednu konkrétní uživatelskou aplikaci ADS - uživatelská data odkazovaná z prvkĤ poĜadníku charakterizují každou jednotlivou objednávku - operace: à zaĜać novČ pĜíchozí objednávku do poĜadníku na poslední místo à odeber objednávku ze zaþátku poĜadníku (tato je pĜipravena ke zpracování) à je poĜadník prázdný?
Algebraická - syntaktický a sémantický popis Grafická - operace se vstupy a výstupy Tabulková - [doména | operace] Jiné - (formalismy symbolických pseudojazykĤ apod.)
Boolean
Další možné uživatelské aplikace ADS (poĜadník v DZP) - poĜadník žadatelĤ o tisk na síĢovČ sdílené tiskárnČ - simulace systémĤ hromadné obsluhy (fronty na obslužné zdroje – knihovny, dopravní uzly, výrobní závody, nemocnice apod.)
ZaĜać
Odeber
Prvek
POěADNÍK
Prázdný?
VytvoĜ
Legenda: o reorganizace
Zruš
o o o
výstup vstup „ ostatní “
A.Kaviþka : sylaby pĜednášek pĜedmČtu „Datové struktury“ v bakaláĜském studiu (Univerzita Pardubice) 13 / 17
A.Kaviþka : sylaby pĜednášek pĜedmČtu „Datové struktury“ v bakaláĜském studiu (Univerzita Pardubice) 14 / 17
Nadále budeme používat následující formu specifikace ADT/ADS:
Kategorizace operací ADT/ADS
ADS PoĜadník (v DZP) Dynamicky alokované homogenní prvky: Prvek (o Následník, o UživatelskáData) VytvoĜ Zruš ZaĜać (pNovýPrvek) Odeber (nPrvek) JePrázdný (nBoolean)
Legenda: p/n o
: :
Konstruktory Destruktory Selektory Prohlídky
konstrukce a inicializace (napĜ.prázdné) struktury zrušení celé struktury zpĜístupĖovací operace bez reorganizace struktury prohlídky celé struktury
Co jsou DATOVÉ STRUKTURY ?
Datové struktury pĜedstavují zpĤsob uchovávání a organizace dat s cílem umožĖovat jejich zpĜístupĖování a modifikace.
vstupní/výstupní parametr referenþní atribut
A.Kaviþka : sylaby pĜednášek pĜedmČtu „Datové struktury“ v bakaláĜském studiu (Univerzita Pardubice) 15 / 17
A.Kaviþka : sylaby pĜednášek pĜedmČtu „Datové struktury“ v bakaláĜském studiu (Univerzita Pardubice) 16 / 17
Klasifikaþní kritéria datových struktur
B. Fyzická (implementaþní) úroveĖ
A. Logická úroveĖ
Vymezení pracovního pamČĢového prostoru à statické struktury - vymezení celého potĜebného pamČĢového prostoru a priori à dynamické struktury run-time alokace/dealokace potĜebných/nepotĜebných úsekĤ pamČti
Charakter pĜístupu ke struktuĜe, resp. jejím prvkĤm à sekvenþní - pĜímý pĜístup možný pouze k nČkterým prvkĤ, další jsou dostupné pouze zprostĜedkovanČ à pĜímý (náhodný) - pĜímý pĜístup k libovolnému prvku struktury Organizaþní struktura à lineární - lineární struktura pĜedstavuje množinu prvkĤ, v níž existuje specifická relace uspoĜádání s vlastností neexistence neporovnatelných prvkĤ - lineární (úplné) uspoĜádání à nelineární - nedisponují výše uvedenou vlastností, lze dále rozlišovat napĜ.: hierarchické, síĢové organizace apod.
Výstavba datových struktur à elementární datové typy (atomické, jednoduché, standardní …) základní stavební kameny urþené (i) množinou hodnot a (ii) množinou operací, jež tyto hodnoty „zpĤsobují“. à strukturované datové typy (složené, kompozitní …) - kompozitní struktury zapouzdĜující více datových typĤ (elementárních a/anebo strukturovaných) Datová struktura je agregací elementárních a strukturovaných datových typĤ do množiny s definovanými vztahy.
A.Kaviþka : sylaby pĜednášek pĜedmČtu „Datové struktury“ v bakaláĜském studiu (Univerzita Pardubice) 17 / 17
Složení struktury à homogenní - struktura složena z (implementaþnČ) homogenních prvkĤ - pozor nesmČšovat s faktem, že domény ADT vždy pracují
s homogenními matematickými objekty à heterogenní - struktura složena z (implementaþnČ) heterogenních prvkĤ
