2016 vbp 1. ze 132

Algoritmizace I

Ak. rok 2015/2016

© vbP

1. ze 132

Algoritmizace I

Ing. Vladimír Beneš, Ph.D. vedoucí katedry

Petrovický

K101 – katedra informatiky a kvantitativních metod

E-mail:

[email protected]

Telefon:

251 114 534, 731 425 276

Konzultační hodiny:

středa 15:45 – 17:45

Ak. rok 2015/2016

© vbP

2. ze 132

Algoritmizace I

Hodinová dotace  Prezenční studium  1 semestr

1/2 KZ 6 kreditů

 Kombinované studium  1 semestr

Ak. rok 2015/2016

12/4 KZ 6 kreditů

© vbP

3. ze 132

Algoritmizace I

Požadavky ke klasifikovanému zápočtu  Prezenční studium  Kombinované studium  Kompletní vypracování dané úlohy (přihlášení v ISu)  Analýza úlohy  Algoritmizace  (Odladěný zdrojový kód programu v jazyce C++)

Ak. rok 2015/2016

© vbP

4. ze 132

Algoritmizace I Studijní literatura  Literatura základní  HEROUT, Pavel. Učebnice jazyka C. České Budějovice : Kopp, 1997. ISBN 80-85828-21-9.  BENEŠ, Vladimír. Programování I. Elektronická studijní opora. Praha : BIVŠ, 2011.  PRATA, Stephen. Mistrovství v C++. Brno : Computer Press, 2004. ISBN 80-251-0098-7.

 Literatura doporučená  KADLEC, Václav. Učíme se programovat v jazyce C. Praha : Computer Press, 2002. ISBN 80-7226-715-9.  MILKOVÁ, E. a kol. Algoritmy, základní konstrukce v příkladech a jejich vizualizace. Hradec Králové : Gaudeamus, 2010.

 KNUTH, Donald, E. Umění programování.1. díl, Základní algoritmy. Brno : Computer Press, 2008,. ISBN 978-80-2512025-5. Ak. rok 2015/2016

© vbP

5. ze 132

Algoritmizace I

Obsah  Algoritmus  Datové struktury

 Odvozené datové struktury  Třídění

Ak. rok 2015/2016

© vbP

6. ze 132

Algoritmizace I

ALGORITMUS

Ak. rok 2015/2016

© vbP

7. ze 132

Algoritmizace I Algoritmus

Algoritmus je základní matematický pojem. • Nelze jej tedy definovat. • Musíme se tedy uchýlit pouze k opisu. V případě PROGRAMOVÁNÍ jde o transformaci množiny vstupních dat na množinu výstupních dat.

Ak. rok 2015/2016

© vbP

8. ze 132

Algoritmizace I Algoritmus

Opisná „DEFINICE“ Je to postup, jak řešit danou úlohu pomocí počítače. Sestává z posloupnosti jednoduchých předem stanovených kroků (ekementárních operací, instrukcí) a vede od vstupních měnitelných údajů až k žádaným výstupním údajům (výsledku).

Ak. rok 2015/2016

© vbP

9. ze 132

Algoritmizace I Vlastnosti algoritmu

 Je ELEMENTÁRNÍ Skládá se z konečného počtu jednoduchých (snadno realizovatelných) činností, které označujeme jako kroky.

Ak. rok 2015/2016

© vbP

10. ze 132


 Je DETERMINOVANÝ Po každém kroku lze určit, zda popisovaný proces skončil. Pokud neskončil, pak musí být dáno, kterým krokem má pokračovat.

Ak. rok 2015/2016

© vbP

11. ze 132


 Je KONEČNÝ Počet opakování jednotlivých kroků je vždy konečný. Algoritmus tedy musí skončit po konečném počtu kroků.

Poznámka: příklad s instrukcí

Ak. rok 2015/2016

1 GOTO 1

© vbP

12. ze 132


 Je REZULTATIVNÍ Vede ke správnému výsledku.

Ak. rok 2015/2016

© vbP

13. ze 132


 Je HROMADNÝ Algoritmus můžeme použít k řešení celé (velké) skupiny (třídy) podobných úloh. Poznámka: např. řešení kvadratické rovnice, soustavy lineárních algebraických rovnic

Ak. rok 2015/2016

© vbP

14. ze 132

Algoritmizace I Poznámka 1.

Pojem algoritmus se dá formalizovat např. pomocí matematické konstrukce označované jako • Turingův stroj • procesorová jednotka, tvořená konečným automatem, • program ve tvaru pravidel přechodové funkce, • pravostranně nekonečné páska pro zápis mezivýsledků.

• Churchova teze Ke každému algoritmu existuje ekvivalentní Thuringův stroj.

Ak. rok 2015/2016

© vbP

15. ze 132


Konečný automat = velice jednoduchý počítač, který může být v jednom z několika stavů, mezi kterými přechází na základě symbolů, které čte ze vstupu

Ak. rok 2015/2016

© vbP

16. ze 132


Pojem algoritmus se dá formalizovat také např. pomocí • teorie parciálně rekurzivních funkcí • v teorii vyčíslitelnosti se takto označují funkce v jistém smyslu „složitější“ než tzv. primitivně rekurzivní funkce

Ak. rok 2015/2016

© vbP

17. ze 132

Algoritmizace I Metoda SHORA DOLŮ a ZDOLA NAHORU

1. Daný problém musíme vyřešit. 2. Známe-li řešení, potřebujeme jej zapsat jako algoritmus 3. Postup řešení rozkládáme na jednodušší operace – elementární kroky tj. metoda SHORA DOLŮ

Poznámka: řešení kvadratické rovnice (analýza a řešení)

Ak. rok 2015/2016

© vbP

18. ze 132

Algoritmizace I Metoda SHORA DOLŮ a ZDOLA NAHORU

Kromě metody SHORA DOLŮ se setkáváme i s metodou ZDOLA NAHORU: • Postupně z elementárních kroků vytváříme prostředky, které umožní zvládnout daný problém • Vytváříme nový procesor tím, že ho učíme nové operace Použijeme vyšší programovací jazyk (procedury, knihovna procedur nebo systém pro vytváření programů (CASE))

Ak. rok 2015/2016

© vbP

19. ze 132

Algoritmizace I Základní složky (konstrukce) algoritmu  Posloupnost (sekvence)

• tvořena jedním nebo několika kroky (provedou se právě jednou v daném pořadí) • nemusí jít o kroky elementární • dalším zjemňováním se mohou rozpadnout na součásti, které samy tvoří posloupnosti, cykly nebo podmínky

Ak. rok 2015/2016

© vbP

20. ze 132

Algoritmizace I Základní složky (konstrukce) algoritmu  Cyklus (iterace) • část algoritmu, která se opakuje dokud je splněna podmínka opakování • cyklus se vždy skládá z podmínky opakování a z těla cyklu (tj. operací, které se opakují) • vyhodnocení podmínky může být před provedením (v C while nebo for), resp. po skončení těla cyklu (v C do-while) nebo i uvnitř těla cyklu (podmíněný skok nebo kombinace podmínky a break) Ak. rok 2015/2016

© vbP

21. ze 132

Algoritmizace I Základní složky (konstrukce) algoritmu

 Podmíněná operace (selekce) • představuje vždy větvení algoritmu • tvořena podmínkou a 1, 2 nebo více výběrovými složkami • pokud je jedna ze složek vybrána, provede se jednou • v C příkazy if a switch (v kombinaci s příkazem break)

Ak. rok 2015/2016

© vbP

22. ze 132

Algoritmizace I Základní složky (konstrukce) algoritmu Podprogram • opakuje-li se určitá část algoritmu na několika místech (může používat různá data) • na elementární kroky ji rozložíme pouze jednou (např. narazíme-li na ni poprvé) • na ostatních místech se na ni odvoláme jako na • dílčí algoritmus nebo • podprogram (procedura, resp. funkce) Ak. rok 2015/2016

© vbP

23. ze 132

Algoritmizace I Algoritmus a data

• struktura vstupních, výstupních, ale i vnitřních dat spoluurčuje strukturu programu • posloupnosti datových položek různých druhů odpovídá posloupnost různých příkazů Poznámka: Přirozeným prostředkem pro zpracování rekurzivních datových struktur (stromy nebo seznamy) jsou obvykle rekurzivní algoritmy! Ak. rok 2015/2016

© vbP

24. ze 132

Algoritmizace I Časová a paměťová náročnost algoritmů • potřebné množství operační paměti • doba pro provedení algoritmu • rozsah vstupních údajů • celkový počet elementárních operací (instrukcí) Poznámka: Ve skutečnosti zpravidla stačí orientovat se podle vybraných skupin instrukcí, které jsou časově nejnáročnější (if)!

Ak. rok 2015/2016

© vbP

25. ze 132

Algoritmizace I Popis algoritmů

 Jazyk pro popis programů • Program Description Language (PDL) • slovní popis algoritmu, dnes velmi častý • „lehce“ upravený programovací jazyk, např. Pascal (Pseudopascal) Poznámka: • Tradičním jazykem pro popis algoritmů býval Algol 60. • Slovní popis programu se může stát základem dobrého komentáře k výslednému programu. Ak. rok 2015/2016

© vbP

26. ze 132


 Strukturogramy • grafické znázornění algoritmu • tvarově i barevně odlišné znázornění (sekvence, iterace, selekce)

Poznámka: • Základem obdélník; v záhlaví označení algoritmu nebo dílčí operace; uvnitř kroky, které algoritmus tvoří

Ak. rok 2015/2016

© vbP

27. ze 132


 Vývojové diagramy • klasický prostředek (ČSN 36 4030, ÚNM, Praha 1974) • graficky náročné (úpravy hotových VD) Poznámka: Spíše než logickou strukturu programu zdůrazňují druh operací.

Ak. rok 2015/2016

© vbP

28. ze 132

Algoritmizace I  Vývojové diagramy

mezní značka (začátek, resp. konec algoritmu) sekvence předem definovaná činnost (podprogram) selekce (rozhodování)

Ak. rok 2015/2016

© vbP

29. ze 132


iterace (začátek, resp. konec iteračního cyklu) vstup, resp. výstup dat spojka komentář (poznámka)

Ak. rok 2015/2016

© vbP

30. ze 132


• obrazce (značky) propojeny čarami (svisle, vodorovně) • implicitní směr shora dolů, zleva doprava, jinak šipky

Ak. rok 2015/2016

© vbP

31. ze 132

Algoritmizace I PŘÍKLAD

Výpočet kořenů (reálných i komplexních) kvadratické rovnice ax2 + bx + c = 0, Vstupní data: Výstupní data:

Ak. rok 2015/2016

kde a ≠ 0

a, b, c x1, x2

© vbP

32. ze 132


Výpočet kořenů (reálných i komplexních) kvadratické rovnice ax2 + bx + c = 0, Vstupní data: Výstupní data:

Ak. rok 2015/2016

kde a ≠ 0

a, b, c x1, x2

© vbP

33. ze 132




Analýza úlohy



Zápis algoritmu (VD)



Zdrojový kód v jazyce C++



Odladění programu (testování)

Ak. rok 2015/2016

© vbP

34. ze 132

Algoritmizace I

DATOVÉ STRUKTURY

Ak. rok 2015/2016

© vbP

35. ze 132

Algoritmizace I Datové struktury

• Základními kameny, součástí výkladu o algoritmech • Souvisejí s algoritmy, které se používají pro práci s nimi Datové struktury rozdělujeme na: • základní datové struktury • odvozené datové struktury

Ak. rok 2015/2016

© vbP

36. ze 132

Algoritmizace I Základní datové struktury PROMĚNNÁ • pojmenované místo v paměti počítače • vytváří se na základě deklarace • jméno (identifikátor) • datový typ Specifikací datového typu určujeme • množinu hodnot, které budeme moci do proměnné ukládat • množinu operací, které budeme moci s proměnnou provádět • velikost proměnné (množství paměti) Ak. rok 2015/2016

© vbP

37. ze 132

Algoritmizace I Základní datové struktury DRUHY PROMĚNNÝCH • globální proměnné • vytvoří se při spuštění programu • existují po celou dobu běhu programu • v C jde o proměnné deklarované mimo těla funkcí

• lokální proměnné • deklarované v těle podprogramů (funkcí) • vznikají při volání PP, zanikají při ukončení PP

• dynamické proměnné • vznikají a zanikají za běhu programu (na základě příkazů) • jejich existence není vázána na podprogramy nebo bloky Ak. rok 2015/2016

© vbP

38. ze 132

Algoritmizace I Základní datové struktury POLE • homogenní datová struktura • posloupnost proměnných stejného datového typu (složky) • v paměti jsou uložené v nepřetržité řadě (chápány jako celek) • v deklaraci určujeme: • jméno (identifikátor) pole • datový typ složek • délku pole (počet složek) • se složkami pracujeme pomocí indexů (mapovací funkce)

Ak. rok 2015/2016

© vbP

39. ze 132

Algoritmizace I Základní datové struktury POLE • jednorozměrná pole (vektory) • vícerozměrná pole • pole s n indexy označujeme jako n-rozměrná • konkrétně • dvojrozměrné pole (matice) • třírozměrné pole (kubická matice) • mapovací funkce podstatně složitější než u jednorozměrného pole • záleží i na uložení vícerozměrných polí v program. jazycích Ak. rok 2015/2016

© vbP

40. ze 132

Algoritmizace I Základní datové struktury VÍCEROZMĚRNÉ POLE • grafické znázornění dvourozměrného pole PV

Přístupový vektor PV

PV1

a11

a12

...

a1n

PV2

a21

a22

...

a2n

PV3

a31

a32

...

a3n

PVm-1

am-11 am-12

...

am-1n

PVm

am1 am2

...

amn

Řádky pole A Ak. rok 2015/2016

© vbP

41. ze 132

Algoritmizace I Základní datové struktury VÍCEROZMĚRNÉ POLE Na počítačích, kde je velikost ukazatele rovna 1 (tj. ukazatel zabírá právě jednu adresovatelnou jednotku paměti), znamená použití PV zrychlení výpočtu (odpadá většina násobení). Na počítačích, kde je velikost ukazatele větší než 1, je použití PV stejně náročné jako výpočet mapovací funkce.

Ak. rok 2015/2016

© vbP

42. ze 132

Algoritmizace I Základní datové struktury ZÁZNAM (STRUKTURA) • skupina proměnných chápaná jako jeden celek • jde o strukturu nehomogenní (složky jsou různých datových typů) • práce s jednotlivými složkami = kvalifikace • spolu se jménem proměnné typu záznam uvedeme také jméno složky (relativní adresa vzhledem k počátku proměnné typu záznam) • složky jsou uloženy v paměti v pořadí uvedeném v deklaraci • velikost záznamu může být větší než součet velikostí jednotlivých složek (překladač může vložit prázdná místa pro „přehlednost“) Ak. rok 2015/2016

© vbP

43. ze 132

Algoritmizace I Základní datové struktury VARIANTNÍ ZÁZNAM (v C je to UNIE) • představuje skupinu proměnných „přeložených přes sebe“ • všechny složky začínají na stejné adrese • velikost variantní části je rovna velikosti největší složky • přístup ke složkám variantního záznamu je totožný s přístupem ke složkám „běžného“ záznamu

Ak. rok 2015/2016

© vbP

44. ze 132

Algoritmizace I Základní datové struktury OBJEKT • definice objektového typu specifikuje: • atributy (složky datového typu) • metody (funkční a procedurální složky) Poznámka: • instance (proměnná objektového typu) obsahuje pouze atributy (atributy instancí) • atributy třídy jsou (vlastně) globální proměnné (ukládají se nezávisle na instancích třídy) Ak. rok 2015/2016

© vbP

45. ze 132

Algoritmizace I Základní datové struktury OBJEKT Poznámka: • pro ukládání atributů instancí platí stejná pravidla jako pro ukládání složek záznamů • skryté atributy • překladač může (pro zajištění správné funkce objektů) přidat do třídy skryté atributy • pro uživatele nejsou tyto atributy přístupné!

Ak. rok 2015/2016

© vbP

46. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury

SEZNAM (list) • struktura představující posloupnost složek • složky jsou uspořádány podle určitého klíče • dle hodnoty dat uložených ve složkách • dle hodnoty funkce vypočítané na základě těchto dat • dle pořadí v jakém byly složky do seznamu přidávány

Ak. rok 2015/2016

© vbP

47. ze 132


SEZNAM (list) • seznam je uspořádaná datová struktura • složky ale nemusí být uloženy dle daného pořadí • na následující (předchozí) prvek ukazuje ukazatel (pointer, link, spojka) • první prvek seznamu = hlava seznamu (head) • zbytek seznamu po odtržení hlavy = ohon (tail) • seznam může být také prázdný

Ak. rok 2015/2016

© vbP

48. ze 132


SEZNAM (list) • seznam je dynamická datová struktura • v programu deklarujeme pouze ukazatel na hlavu seznamu • jednotlivé složky (prvky) seznamu dynamicky • alokujeme • rušíme • seznam je rekurzivní datovou strukturou • každá složka (prvek) seznamu obsahuje odkaz na položku stejného typu Ak. rok 2015/2016

© vbP

49. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury JEDNOSMĚRNÝ SEZNAM • nejjednodušší varianta seznamu • každý prvek obsahuje odkaz na následující prvek • při práci s jednosměrným seznamem používáme zarážku • poslední prvek seznamu neobsahuje užitečná data • poslední prvek seznamu slouží jako zarážka při prohledávání • např. v Pascalu NIL, v C NULL • uchováváme tedy (kromě ukazatele na hlavu) také ukazatel na tuto zarážku Ak. rok 2015/2016

© vbP

50. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury OPERACE S JEDNOSMĚRNÝM SEZNAMEM Vytvoření prázdného seznamu 1. Deklarujeme jako proměnné ukazatel na prvek (např. typ uPrvek) • ukazatel na hlavu seznamu hlava • ukazatel na zarážku konec 2. Vytvoříme dynamickou proměnnou typu Prvek • její adresu uložíme do proměnných hlava a konec 3. Do složky hlavâ.Další (tj. do složky Další nově vytvořené dynamické proměnné) vložíme hodnotu NIL, resp. NULL Ak. rok 2015/2016

© vbP

51. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury OPERACE S JEDNOSMĚRNÝM SEZNAMEM Přidání nového prvku na konec seznamu 1. Požadovaná data vložíme do složky zarážky 2. Alokujeme nový prvek (novou dynamickou proměnnou typu Prvek) Její adresu uložíme do složky Další zarážky a do konec. Nově alokovaný prvek převezme roli zarážky. 3. Do složky Další nové zarážky vložíme hodnotu NIL, resp. NULL.

Ak. rok 2015/2016

© vbP

52. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury OPERACE S JEDNOSMĚRNÝM SEZNAMEM Vyhledání prvku v seznamu (např. hledáme hodnotu dd) 1. Do pomocné proměnné p typu uPrvek vložíme ukazatel na hlavu seznamu. 2. Do zarážky vložíme hledanou hodnotu, tj. přiřadíme koneĉ.D = dd. 3. Prohledáváme postupně seznam. Platí-li p̂.D = dd, skončíme. Jinak do p uložíme adresu následujícího prvku seznamu. 4. Obsahuje-li po skončení p adresu zarážky, seznam hledaný prvek neobsahuje. V opačném př. obsahuje p adresu hledaného prvku. Ak. rok 2015/2016

© vbP

53. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury OPERACE S JEDNOSMĚRNÝM SEZNAMEM Vložení nového prvku za daný prvek seznamu

Předpokládejme: • známe adresu p prvku, za který chceme vložit do jednosměrného seznamu nový prvek • využijeme pomocnou proměnnou q typu uPrvek

Ak. rok 2015/2016

© vbP

54. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury OPERACE S JEDNOSMĚRNÝM SEZNAMEM Vložení nového prvku za daný prvek seznamu

1. Alokujeme novou proměnnou typu Prvek a uložíme do ní potřebná data. Adresa nové proměnné je uložena v pomocné proměnné q. 2. Do q̂.Další uložíme adresu prvku, který bude v seznamu následovat, tj. obsah proměnné p̂.Další. 3. Do p̂.Další uložíme adresu nově vloženého prvku, tj. obsah proměnné q. Ak. rok 2015/2016

© vbP

55. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury OPERACE S JEDNOSMĚRNÝM SEZNAMEM Vymazání prvku za daným prvkem seznamu

Chceme ze seznamu odstranit prvek, který následuje za prvkem s adresou uloženou v proměnné p. K tomu potřebujeme pomocnou proměnnou q.

Ak. rok 2015/2016

© vbP

56. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury OPERACE S JEDNOSMĚRNÝM SEZNAMEM Vymazání prvku za daným prvkem seznamu

1. Do q uložíme p̂.Další (to je adresa mazaného prvku). 2. Do p̂.Další uložíme p̂.Další ̂.Další (to je adresa prvku, který leží za mazaným prvkem). 3. Zrušíme prvek, na který ukazuje q.

Ak. rok 2015/2016

© vbP

57. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury OPERACE S JEDNOSMĚRNÝM SEZNAMEM Smazání daného prvku seznamu

Chceme smazat prvek, na který ukazuje ukazatel p. To je složitější, neznáme prvek před tím, který chceme smazat. Jak „napojit“ předcházející a následující prvek?  Umíme smazat prvek, který leží za označeným prvkem. Na datech v mazaném prvku nezáleží. Přesuneme do něj tedy obsah prvku následujícího a ten pak smažeme. Ak. rok 2015/2016

© vbP

58. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury OPERACE S JEDNOSMĚRNÝM SEZNAMEM Smazání daného prvku seznamu

1. Přesuneme obsah p ̂.Další ̂.D do p ̂.D (nyní prvky p ̂ a p ̂ .Další ̂ obsahují stejná data). 2. Smažeme prvek s adresou p ̂ .Další.

Ak. rok 2015/2016

© vbP

59. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury OPERACE S JEDNOSMĚRNÝM SEZNAMEM Smazání celého seznamu Seznam nepotřebujeme (nepoužíváme): • je třeba jej smazat, tj. uvolnit dynamicky přidělenou paměť Seznam je: • prázdný • skládá se z hlava + ohon Algoritmus mazání je rekurzivní. Ak. rok 2015/2016

© vbP

60. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury OPERACE S JEDNOSMĚRNÝM SEZNAMEM Smazání celého seznamu 1. Je-li seznam prázdný, tedy konec. Jinak ulož adresu hlavy do pomocné proměnné. 2. Do ukazatele na hlavu vlož adresu hlavy ohonu. Smaž hlavu. 3. Smaž ohon, tj. seznam, který zbyl po smazání hlavy.

Ak. rok 2015/2016

© vbP

61. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury JINÉ TYPY SEZNAMŮ Dvousměrný seznam (double-linked list) • každý prvek obsahuje odkaz nejen na následující prvek, ale i na předcházející prvek • dvousměrný seznam lze procházet v obou směrech • od hlavy k poslednímu prvku • od posledního prvku k hlavě

Ak. rok 2015/2016

© vbP

62. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury JINÉ TYPY SEZNAMŮ Kruhový seznam (cyklický) • může být jednosměrný i dvousměrný • obvykle se nepoužívá zarážka

• poslední prvek odkazuje na první prvek • pokud jde o seznam dvousměrný, pak i první prvek odkazuje na prvek poslední

Ak. rok 2015/2016

© vbP

63. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury STROM • rekurzivní datová struktura Abstraktní definice stromu se základním typem T je rekurzivní: Strom se základním typem T je buď prázdná struktura nebo prvek typu T, na který je připojen konečný počet disjunktních stromových struktur se základním typem T (označujeme je jako podstromy).

Ak. rok 2015/2016

© vbP

64. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury STROM • prvky stromu se označují jako vrcholy, resp. uzly • vrchol, ke kterému není připojen žádný podstrom označujeme jako koncový vrchol, resp. list • vrchol, který sám není připojen k žádnému jinému vrcholu označujeme jako kořen • kořen spolu se všemi podstromy, které jsou k němu připojeny, tvoří celý strom • prvky, které nejsou listy, označujeme jako vnitřní vrcholy stromu

Ak. rok 2015/2016

© vbP

65. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury STROM Je-li G kořen podstromu připojeného k uzlu C, říkáme také, že G je (přímým) následovníkem C a C je (přímým) předchůdcem G. A B D J

Ak. rok 2015/2016

C

E K

© vbP

F L

G M

N

H

I

O

66. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury STROM Kořen je vrchol, který nemá žádného předchůdce. List je vrchol, který nemá žádného následovníka.

Ak. rok 2015/2016

A B

D

E

J

K L

© vbP

C

F

G

M N

H

I

O

67. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury STROM Dodatek k definici stromu: Nechť počet podstromů připojený k libovolnému z vrcholů daného stromu nepřesáhne n. Potom takový strom označujeme jako n-ární. Nejčastěji: • n = 2  binární strom • n = 3  ternární strom Číslo n („-aritu“) označujeme jako typ stromu. Ak. rok 2015/2016

© vbP

68. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury STROM A

Příklad: B

C

Ternární strom D

J

Ak. rok 2015/2016

E

K

F

L

© vbP

G

M

N

H

I

O

69. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury STROM Pojmy: • kořen stromu je na první úrovni • uzly, následovníci kořene, jsou na druhé úrovni • obecně: • je-li uzel R na úrovni i a uzel S je následovníkem R, pak uzel S je na úrovni i+1

Ak. rok 2015/2016

© vbP

70. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury STROM Pojmy: Nechť x je úroveň vrcholu X. Chceme-li projít stromem od kořene k vrcholu X, musíme projít x hran (včetně hrany, která vstupuje do kořene). Pak místo o úrovni vrcholu často hovoříme o délce vnitřní cesty daného vrcholu.

Ak. rok 2015/2016

© vbP

71. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury STROM Pojmy: Součet délek cest všech uzlů v daném stromě se nazývá délka vnitřní cesty stromu. Průměrná délka vnitřní cesty stromu je dána vztahem 𝑃𝑖 =

1 𝑛

𝑛 𝑖=1 𝑛𝑖

∙𝑖

ni je počet uzlů na i-té úrovni stromu Ak. rok 2015/2016

© vbP

72. ze 132


STROM

A B

Pojmy: Zvláštní vrcholy

F D J

Ak. rok 2015/2016

C E

K

H

G L

© vbP

M

N

I

O

73. ze 132


A

STROM

B

C

Pojmy:

F D J

E K

H

G L

M

N

I O

Délka vnější cesty stromu = součet délek cest všech zvláštních vrcholů. Průměrná délka vnější cesty stromu: mi = počet zvláštních vrcholů na i-té úrovni (m je celkový počet zvl. vrcholů) Ak. rok 2015/2016

© vbP

74. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury STROM Pojmy: Stromy nejčastěji reprezentujeme jako dynamické datové struktury. Vrcholy stromu mohou být např. záznamy: • obsahují ukazatele na kořeny připojených podstromů (nebo NULL, není-li podstrom připojen)

• užitečné informace jsou uloženy ve složce typu data (podobně jako u seznamu) Ak. rok 2015/2016

© vbP

75. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury BINÁRNÍ STROMY

• Ke každému vrcholu jsou připojeny dva podstromy (jeden nebo oba mohou být prázdné) • Jeden označujeme jako levý, druhý jako pravý podstrom

Ak. rok 2015/2016

© vbP

76. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury BINÁRNÍ STROMY Nejčastěji se setkáváme s binárními stromy s následujícím uspořádáním dat: Pro každý vrchol U platí, že všechny údaje, uložené v levém podstromu, připojenému k U, jsou menší, než je údaj uložený v U, a všechny údaje, uložené v pravém podstromu, připojenému k U, jsou větší, než je údaj uložený v U. Binární strom je přístupný pomocí ukazatele na kořen. Vrcholy alokujeme dynamicky. Ak. rok 2015/2016

© vbP

77. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury BINÁRNÍ STROMY Při procházení binárního stromu využíváme některou z metod: • přímé zpracování

(preorder)

(zpracujeme data v kořeni, pak levý podstrom, poté pravý podstrom)

• vnitřní zpracování (inorder) (projdeme levý podstrom, pak kořen, nakonec pravý podstrom)

• zpětné zpracování (postorder) (zpracováváme v pořadí levý podstrom, pravý podstrom, kořen)

Ak. rok 2015/2016

© vbP

78. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury OPERACE S BINÁRNÍMI STROMY Vytvoření binárního stromu • Vytvoříme prázdný binární strom • strom se skládá ze záznamů (struktur) typu vrchol • musíme mít ukazatel na kořen stromu • musíme mít proměnnou typu ukazatel na vrchol Vytvoření prázdného stromu = přiřazení hodnoty NULL této proměnné typu ukazatel na vrchol

Ak. rok 2015/2016

© vbP

79. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury OPERACE S BINÁRNÍMI STROMY Zrušení binárního stromu • Je-li strom, na který t (ukazatel na kořen) ukazuje, prázdný, skončíme • Smažeme levý podstrom připojený k vrcholu, na který ukazuje t • Smažeme pravý podstrom připojený k vrcholu, na který ukazuje t • Smažeme vrchol, na který ukazuje t Ak. rok 2015/2016

© vbP

80. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury OPERACE S BINÁRNÍMI STROMY Vložení nového vrcholu Máme data dd a chceme je zařadit do stromu • Pokud tam takový údaj ještě není, přidáme do stromu nový vrchol; jinak není třeba dělat nic • Přidáváme-li vrchol do prázdného stromu, alokujeme pro něj paměť • Uložíme do něj potřebná data a adresu vrcholu uložíme do ukazatele na kořen Ak. rok 2015/2016

© vbP

81. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury OPERACE S BINÁRNÍMI STROMY Vložení nového vrcholu V nedprázdném stromě • vyjdeme od kořene a porovnáme dd s hodnotou v něm • je-li dd menší než uložená hodnota • zařadíme nový vrchol do levého podstromu • jinak jej zařadíme do pravého podstromu

Ak. rok 2015/2016

© vbP

82. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury OPERACE S BINÁRNÍMI STROMY Vyhledání údaje ve stromu 1. Je-li strom prázdný, hledaný údaj v něm není; konec 2. Jinak porovnáme dd s hodnotou v kořeni; jsou-li si rovny, nalezli jsme hledaný údaj; konec 3. Jinak je-li dd menší než hodnota uložená v kořeni, prohledáme levý podstrom připojený ke kořeni; Provedeme s ním tento algoritmus a skončíme 4. Jinak prohledáme pravý podstrom a skončíme Ak. rok 2015/2016

© vbP

83. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury OPERACE S BINÁRNÍMI STROMY Zrušení vrcholu 1. Rušíme list. V takovém případě uvolníme dynamickou paměť přidělenou tomuto uzlu a odstraníme odkaz na rušený vrchol v jeho předchůdci (nebo ukazatel na kořen, jestliže měl strom jen jeden vrchol) 2. Rušíme vrchol, který má jen jednoho následovníka (analogie rušení prvku seznamu). Adresu rušeného prvku uložíme do pomocné proměnné; odkaz v předchůdci upravíme tak, aby ukazoval na následovníka a vrchol zrušíme. Ak. rok 2015/2016

© vbP

84. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury OPERACE S BINÁRNÍMI STROMY Zrušení vrcholu 3. Rušíme vrchol, který má dva následovníky. Nastává problém, čím zrušený vrchol nahradit. Kromě hodnoty dd, která nás již nezajímá, obsahuje také odkazy na své následovníky, které je třeba uchovat. Výsledkem této operace musí být opět uspořádaný binární strom.

Ak. rok 2015/2016

© vbP

85. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury OPERACE S BINÁRNÍMI STROMY Zrušení vrcholu V tomto případě se používá následujícího triku: 1. Najdeme nejpravější vrchol levého podstromu připojeného k rušenému vrcholu (označíme jej Q; to je vrchol, v němž je uložena největší z hodnot menších než v rušeném vrcholu). Nalezený vrchol má nejvýše jednoho následovníka (jinak by nemohl být nejpravější). 2. Hodnotu z vrcholu Q přeneseme do vrcholu, který chceme zrušit. 3. Zrušíme vrchol Q. Analogicky nejlevější vrchol pravého podstromu, … Ak. rok 2015/2016

© vbP

86. ze 132


B-STROM (b-tree) • datová struktura podobná stromu

• vrcholy tohoto stromu se nazývají stránky

Ak. rok 2015/2016

© vbP

87. ze 132


B-STROM (b-tree) Pro b-strom řádu n platí: • kořenová stránka obsahuje alespoň jednu položku • každá stránka obsahuje maximálně 2n položek (ulož. údajů)

• každá stránka (kromě kořenové) obsahuje minimálně n položek

Ak. rok 2015/2016

© vbP

88. ze 132


B-STROM (b-tree) Pro b-strom řádu n platí: • Každá stránka je buď • listovou stránkou (nemá žádné následovníky),

• nebo má m+1 následovníků, kde m je počet položek v ní uložených. • Všechny listové stránky jsou na stejné úrovni.

Ak. rok 2015/2016

© vbP

89. ze 132


B-STROM (b-tree) B-stromy 1. řádu: • stránky obsahují 1 nebo 2 položky Takové b-stromy se často nazývají 2-3-stromy: • každá stránka kromě listů má 2 - 3 následovníky. Takové stromy se nazývají také • binární b-stromy, • resp. bb-stromy. Ak. rok 2015/2016

© vbP

90. ze 132


B-STROM (b-tree) B-strom 2. řádu (jeho stránky tedy obsahují 2 – 4 údaje) 07 11 13

3 9 13

Ak. rok 2015/2016

21 23 25 27

60 70

31 33 35

41 43 45 47

© vbP

51 53

61 63 65

91. ze 132


B-STROM (b-tree) Přidání údaje do b-stromu

(1)

a) Vyhledáme listovou stránku, do které nový údaj patří; pokud je v ní místo, (obsahuje méně než 2n údajů), vložíme nový údaj a skončíme. b) Je-li stránka zaplněná, obsahovala by 2n+1 údajů; údaj zařadíme na „správné“ místo a takto vzniklou přeplněnou stránku rozdělíme na dvě po n údajích a prostřední údaj přesuneme do předchůdce (když stránka předchůdce nemá, vytvoříme ho). Ak. rok 2015/2016

© vbP

92. ze 132


B-STROM (b-tree) Přidání údaje do b-stromu

(2)

V předchůdci se může situace opakovat.

Z toho plyne: b-strom roste pouze tak, že se rozdělí kořenová stránka.

Ak. rok 2015/2016

© vbP

93. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury B-STROM (b-tree) Odstranění údaje z b-stromu a) Odstraňovaný údaj neleží v listové stránce Vyhledáme nejbližší menší údaj (nejpravější prvek v levém podstromu připojeném k tomuto prvku). b) Tedy: Odstraňujeme-li m-tý prvek ve stránce S, vyhledáme největší prvek v (m - 1)-tém podstromu, připojeném k S. Tento „náhradní“ prvek bude ležet v listovní stránce. Jeho hodnotu přeneseme na místo mazaného prvku a smažeme „náhradní“ prvek v listu. Ak. rok 2015/2016

© vbP

94. ze 132


B-STROM (b-tree) Odstranění údaje z b-stromu b) Odstranění prvku z listu Poté, co prvek z listu S vyjmeme, musíme se přesvědčit, kolik prvků v něm zůstalo (žádná stránka kromě kořene nesmí mít méně prvků než n).

Pokud v listu S zůstalo alespoň n prvků, skončíme. Ak. rok 2015/2016

© vbP

95. ze 132


B-STROM (b-tree) Odstranění údaje z b-stromu b) Odstranění prvku z listu Pokud bude list S obsahovat n-1 prvků, pokusíme se „vypůjčit si“ potřebný prvek ze sousední stránky (se společným předchůdcem). Ta musí mít n+1 prvků. Pokud má pouze n prvků (nemůžeme si od ní „půjčit“), musíme tyto dvě stránky sloučit (to můžeme, neboť obě tyto listové stránky mají dohromady pouze 2n-1 prvků). Atd. Ak. rok 2015/2016

© vbP

96. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury ZÁSOBNÍK (stack) Jde o datovou strukturu, do které „odkládáme“ data v průběhu zpracování. Data ze zásobníku odebíráme v obráceném pořadí, než jsme data vkládali: • poslední uloženou položku musíme vyjmout jako první • předposlední uloženou položku musíme vyjmout jako druhou

• atd.

Ak. rok 2015/2016

© vbP

97. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury ZÁSOBNÍK (stack)

vložení další položky

vyjmutí položky vrchol zásobníku

dno zásobníku

Ak. rok 2015/2016

© vbP

98. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury ZÁSOBNÍK (stack) • Položku, která neleží na vrcholu zásobníku, nelze vyjmout. • Známe-li její polohu, můžeme ji přečíst (získat její hodnotu, aniž byla ze zásobníku vyjmuta). Implementace zásobníku: • pomocí pole (musíme si neustále pamatovat index posledně vloženého prvku, který je na vrcholu zásobníku)

• pomocí seznamu (definujeme hlavu seznamu jako vrchol zásobníku) Ak. rok 2015/2016

© vbP

99. ze 132


FRONTA Datová struktura podobná zásobníku. Má odlišnou vnitřní strukturu: • prvky do fronty vkládáme na jedné straně (konec)

• prvky z fronty vybíráme na druhém konci (čelo) • prvky ve frontě uloženy dle pořadí vložení • prvky z fronty vybíráme ve stejném pořadí

• prvek lze z fronty vyjmout jen je-li „na řadě“ (na čele fronty) Ak. rok 2015/2016

© vbP

100. ze 132


FRONTA Frontu reprezentujeme pomocí pole, resp. seznamu (jako zásobník) vyjmutí položky

vložení položky

čelo fronty

Ak. rok 2015/2016

konec fronty

© vbP

101. ze 132


FRONTA Fronta s prioritami Priorita prvku je funkce hodnoty v prvku uložené. Fronta s prioritami: • prvky vkládáme v pořadí, ve kterém přišly • prvky vybíráme v pořadí závislém na jejich prioritě Prioritu lze uplatnit i při vkládání. Fronty s prioritami se implementují pomocí seznamů. Ak. rok 2015/2016

© vbP

102. ze 132


FRONTA Fronta kruhová Např. pole Q[0, 1, 2, … , n-1] a po prvku Q[n-1] bude následovat prvek Q[0]. Pro obsluhu kruhové fronty potřebujeme ukazatel • f na čelo fronty • ukazatel r na konec fronty

Ak. rok 2015/2016

© vbP

103. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury [n-1]

FRONTA

[0] [1]

Fronta kruhová [2]

Ak. rok 2015/2016

© vbP

104. ze 132


FRONTA Fronta kruhová Při každé operaci vkládání, resp. výběru kontrolujeme, zda f = r. • rovnost nastane po výběru prvku, pak je fronta prázdná. • rovnost nastane po vložení prvku, pak je fronta již plná.

Ak. rok 2015/2016

© vbP

105. ze 132


TABULKA Tabulka symbolů je datová struktura umožňující rychle zjistit, zda se v ní někde daný prvek vyskytuje. Umožňuje: • snadno prvek vložit • snadno prvek vyjmout Takové tabulky se využívají v kompilátorech při lexikální analýze (např. zda již byl daný identifikátor deklarován). Ak. rok 2015/2016

© vbP

106. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury TABULKA Tabulka symbolů Roli tabulky symbolů mohou hrát binární stromy.

Nemáme-li žádné apriorní informace o statistickém rozdělení vkládaných prvků, nebudou vytvořené stromy příliš optimální. Proto se obvykla používají hešové tabulky: • souvislá oblast paměti pro ukládání prvků – hesel • tabulka je rozdělena na tzv. koše (např. K(1), K(2), …, K(k)) • v každém z košů může být s hesel (každý koš má s pozic, často se volí s=1). Ak. rok 2015/2016

© vbP

107. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury GRAFY Orientovaný graf G definujeme jako dvojici G = {U,H}, kde • U je množina uzlů,

• H UxU je množina orientovaných hran. O orientované hraně e = , kde i a j jsou uzly, říkáme, že jde z uzlu i do uzlu j. Orientovaný graf může také obsahovat hranu . Někdy též zapisujeme i → j, resp. i → i. Ak. rok 2015/2016

© vbP

108. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury GRAFY Ztotožníme-li hranu s hranou <j, i>, jde o neorientovaný graf. Definujeme-li zobrazení h: H → R, které jednotlivým hranám přiřadí číselné hodnoty, pak hovoříme o ohodnoceném grafu. Posloupnost orientovaných hran , , …, označujeme jako cestu z uzlu i do uzlu j.

Cesta, jejíž počáteční uzel je roven uzlu koncovému, je cyklus.

Ak. rok 2015/2016

© vbP

109. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury GRAFY

4 4 3

3

5

5

2 1

1

2

Orientovaný graf Ak. rok 2015/2016

Neorientovaný graf © vbP

110. ze 132

Algoritmizace I Odvozené (abstraktní) datové struktury MNOŽINY Množiny s prvky ordinálních typů Ordinálními typy mohou být • znaky, • intervaly, • výčtové typy, • (seznamy objektů).

Ak. rok 2015/2016

© vbP

111. ze 132

Algoritmizace I Třídění

TŘÍDĚNÍ

Ak. rok 2015/2016

© vbP

112. ze 132

Algoritmizace I Třídění

Pojmy: Třídění = uspořádání dané posloupnosti dat podle určitého klíče v neklesající, resp. nerostoucí pořadí. Prvky tříděné posloupnosti budou stejného datového typu.

Obecně jde o záznamy (struktury). Klíčem bude: • některá ze složek záznamu • funkce vypočítaná na základě celého záznamu Ak. rok 2015/2016

© vbP

113. ze 132

Algoritmizace I Třídění Pojmy: Vnitřní třídění • známe počet prvků posloupnosti • všechny prvky posloupnosti jsou uloženy ve vnitřní paměti počítače

Vnější třídění • neznáme počet prvků posloupnosti • všechny prvky posloupnosti jsou uloženy ve vnější paměti se sekvenčním přístupem (magnetická páska, disk) Ak. rok 2015/2016

© vbP

114. ze 132

Algoritmizace I Vnitřní třídění TŘÍDĚNÍ PŘÍMÝM VÝBĚREM

1. Ve zdrojové posloupnosti najdeme prvek s nejmenším klíčem. 2. Vyměníme tento prvek s prvkem na první pozici.

3. Nyní máme na první pozici prvek s nejmenším klíčem. Máme-li utřídit zbytek posloupnosti, opakujeme tyto kroky se zbylými n-1 prvky, dokud je n > 1.

Ak. rok 2015/2016

© vbP

115. ze 132

Algoritmizace I Vnitřní třídění TŘÍDĚNÍ PŘÍMÝM VÝBĚREM

Příklad:

Ak. rok 2015/2016

3

2

17

1

8

5

1

2

17

3

8

5

1

2

17

3

8

5

1

2

3

17

8

5

1

2

3

5

8 17

1

2

3

5

8 17 © vbP

neutříděno

plně utříděné 116. ze 132

Algoritmizace I Vnitřní třídění TŘÍDĚNÍ BUBLINKOVÉ (bublesort)

1. Opakovaně procházíme polem 2. Porovnáváme dva sousední prvky

3. Pokud relace nevyhovuje, prohodíme je Při prvním průchodu „vyplave“ nejlehčí prvek na hladinu, při druhém průchodu „vyplave“ 2. nejlehčí prvek, atd. Ak. rok 2015/2016

© vbP

117. ze 132


Vylepšení algoritmu  • při průchodu polem registrujeme uskutečněné výměny prvků

• v okamžiku, kdy při průchodu polem nenastala žádná výměna, je pole uspořádané

Ak. rok 2015/2016

© vbP

118. ze 132


Vylepšení algoritmu  • zapamatujeme si i index prvku, kterého se týkala poslední výměna • za tímto prvkem již nebyly žádné další výměny • tj. prvky jsou již uspořádány • tento úsek již nemusíme procházet 

Ak. rok 2015/2016

© vbP

119. ze 132


Vylepšení algoritmu  • evidentně záleží na „směru pohybu“ v tříděném poli • „pohyb“ zleva doprava  „nejtěžší“ prvek „vybublá“ nejrychleji • „pohyb“ zprava doleva  „nejlehčí“ prvek „vybublá“ nejrychleji • kombinujme (střídejme) tedy oba směry pohybu v tříděném poli  třídění PŘETŘÁSÁNÍM

Ak. rok 2015/2016

© vbP

120. ze 132

Algoritmizace I Vnitřní třídění SHELLOVO TŘÍDĚNÍ (Shellsort)

Příčina neefektivnosti předchozích algoritmů • vyměňujeme pouze sousední prvky • nejmenší prvek např. na konci pole  potřebujeme n výměn • preferujme výměnu prvků na „velké vzdálenosti“

Ak. rok 2015/2016

© vbP

121. ze 132


Donald L. Shell (1.3.1924–2.11.2015), americký počítačový vědec Myšlenka • přeuspořádejme pole tak, že vezmeme-li každý h-tý prvek, dostaneme setříděné pole (pole setříděné s krokem h) • pole setříděné s krokem h představuje h proložených nezávislých polí Ak. rok 2015/2016

© vbP

122. ze 132


Myšlenka • při Shellově třídění třídíme • nejprve s krokem h1 • pak s krokem h2 (h2 < h1), atd. • nakonec třídíme s krokem hn = 1 (dostaneme plně setříděné pole) • při každém z průchodů třídíme pole, které je již částečně utříděné  můžeme očekávat, že bude třeba jen málo výměn Ak. rok 2015/2016

© vbP

123. ze 132

Algoritmizace I Vnitřní třídění RYCHLÉ TŘÍDĚNÍ (quicksort) (třídění rozdělováním)

Myšlenka • nejefektivnější je výměna prvků v poli na velké vzdálenosti • mějme pole seřazené v opačném pořadí  potřebujeme jen n/2 výměn

• porovnáme prvky na obou koncích pole a vyměníme je • pak postoupíme o jedno pole ke středu a zopakujeme porovnání

Ak. rok 2015/2016

© vbP

124. ze 132

Algoritmizace I Vnitřní třídění RYCHLÉ TŘÍDĚNÍ (quicksort) (třídění rozdělováním) Myšlenka • pokud pole není seřazené v obráceném pořadí, nemůže být náš postup tak přímočarý • vyjdeme z principu Rozděl a panuj

• zvolíme náhodně prvek x • uspořádáme pole tak, aby vlevo od x byly menší prvky a vpravo od x byly větší prvky • máme 3 části • vlevo jsou prvky menší než x • prvek x je už na svém místě • vpravo jsou prvky větší než x Ak. rok 2015/2016

© vbP

125. ze 132

Algoritmizace I Vnitřní třídění RYCHLÉ TŘÍDĚNÍ (quicksort) (třídění rozdělováním) Myšlenka • pokud pole obsahuje pouze 3 prvky • za x volíme prostřední (pokud jde o velikost, tj. medián) • předeslaným procesem získáme uspořádané pole  • pokud pole obsahuje pouze 2 prvky • za x volíme kterýkoli z nich • a je to  Ak. rok 2015/2016

© vbP

126. ze 132

Algoritmizace I Vnitřní třídění RYCHLÉ TŘÍDĚNÍ (quicksort) (třídění rozdělováním) Algoritmus 1. Zvolíme x a rozdělíme popsaným způsobem tříděné pole na úseky a1, …, as, , an Platí, že • ai <= x pro i=1, 2, …, s-1 • as = x • ai >= x pro i=s+1, …, n

Ak. rok 2015/2016

© vbP

127. ze 132

Algoritmizace I Vnitřní třídění RYCHLÉ TŘÍDĚNÍ (quicksort) (třídění rozdělováním) Algoritmus 2. Proces rozdělení opakujeme pro úseky • a1, …, as • as+1, …, an 3. Dále pak pro jejich části, až dospějeme k úsekům délky 1 4. … 5. A ty už budou automaticky utříděné 

Ak. rok 2015/2016

© vbP

128. ze 132

Algoritmizace I Vnitřní třídění RYCHLÉ TŘÍDĚNÍ (quicksort) (třídění rozdělováním) Algoritmus – rozdělení pole na dvě části 1. Vyjdeme od prvního prvku pole a budeme hledat prvek, který je větší než x.

2. Zároveň budeme pole prohledávat od konce, až narazíme na prvek, který je menší než x. 3. Tyto dva prvky zaměníme. 4. Až se oba směry prohledávání setkají uprostřed pole, skončíme. Ak. rok 2015/2016

© vbP

129. ze 132

Algoritmizace I Některé základní algoritmy 1. Záměna dvou daných prvků 2. Seřazení tří daných prvků dle velikosti 3. Nalezení dané hodnoty v daném poli • jednorozměrné pole • dvourozměrné pole 4. Nalezení extrémní velikosti prvku a jeho polohy v daném poli • jednorozměrné pole • dvourozměrné pole 5. Součet, resp. součin prvků daného číselného pole (vektor, matice) Ak. rok 2015/2016

© vbP

130. ze 132

Algoritmizace I Některé základní algoritmy 6. Záměna minimálního a maximálního prvku v daném poli 7. Součet, resp. součin matic 8. Záměna dvou řádků matice 9. Matice „převlečená naruby“ (s využitím algoritmu v úloze 8) 10. Nalezení v absolutní hodnotě maximálního prvku v řádku (resp. sloupci) matice a jeho záměna s prvkem diagonálním

Ak. rok 2015/2016

© vbP

131. ze 132

Programování I

Děkuji za pozornost

Ak. rok 2015/2016

© vbP

132. ze 132

2016 vbp 1. ze 132

Recommend Documents