1
Poˇ c´ıtaˇ ce a programov´ an´ı
Probl´ em Ot´azka, kter´a mus´ı b´ yt vyˇreˇsena nebo zodpovˇezena Algoritmus Vsouˇcasnosti pod pojmem algoritmus rozum´ıme koneˇcnou mnoˇzinu pˇr´ıkaz˚ u, kter´a vede k nalezen´ı ˇreˇsen´ı urˇcit´eho probl´emu, pˇriˇcemˇz m´a dalˇs´ı vlastnosti. [Knuth, Raichl] 1. Koneˇ cnost. Algoritmus mus´ı vˇzdycky skonˇcit po vykon´an´ı koneˇcn´eho (moˇzn´a velice velik´eho) poˇctu krok˚ u. Pokud nem´a jenom tuto vlastnost, m˚ uˇze b´ yt takov´ y pˇredpis naz´ yv´an v´ ypoˇ cetn´ı metoda. Pˇr´ıkladem jsou reaktivn´ı syst´emy, kter´e opakovanˇe reaguj´ı se sv´ ym okol´ım, automat na k´avu, ˇr´ıd´ıc´ı programy.[Knuth] 2. Jednoznaˇ cnost. Kaˇzd´ y krok algoritmu mus´ı b´ yt jednoznaˇcnˇe urˇcen. ˇ 3. Vstup. Z´adn´ y nebo v´ıce. 4. V´ ystup. Jeden nebo v´ıce. Program Z´apis, kter´ y vyhovuje pravidl˚ um programovac´ıho jazyka naz´ yv´ame program, pˇriˇcemˇz obecnˇe jde o v´ ypoˇ cetn´ı metodu a pokud splˇ nuje podm´ınku koneˇcnosti jde o algoritmus. Vykon´ an´ı programu M´ame dva zp˚ usoby vykon´an´ı programu: Kompilace Prvn´ım zp˚ usobem jak vykonat program zapsan´ y v programovac´ım jazyce je jeho transformace na posloupnost strojov´ ych instrukc´ı, jej´ı uloˇzen´ı do pamˇeti a vykon´an´ı. K tomu slouˇz´ı pˇ rekladaˇ c (kompil´ ator) a operaˇ cn´ı syst´ em, co jsou opˇet programy a pln´ı uveden´e ˇcinnosti. Interpretace Uveden´ y zp˚ usob vyˇzaduje pro kaˇzdou hardwarovou platformu naps´an´ı nov´eho pˇrekladaˇce programovac´ıho jazyka. Alternativn´ı zp˚ usob je definov´an´ı mezijazyka abstraktn´ıho stroje a vykon´avat pˇreklad programu do tohoto mezijazyka. Vykon´an´ı programu potom bude znamenat vykon´an´ı pˇr´ıkaz˚ u takov´eho jazyka, a protoˇze mezijazyk nen´ı obecnˇe v´az´an na konkr´etn´ı hardwarovou platformu, vykon´an´ı pˇr´ıkaz˚ u mezijazyka se dˇeje programem, kter´ y tyto pˇr´ıkazy ˇ ık´ame, ˇze je interpretuje, a protoˇze m´a pro mezijazyk vykon´a na specifick´em procesoru. R´ funkci stroje, kter´ y re´alnˇe fyzicky neexistuje, naz´ yva se virtu´ aln´ı stroj. Objekt Objekt je runtime entita (1) skl´adaj´ıc´ı se z promˇ enn´ ych, zvan´ ych ˇclensk´e promˇenn´e (member variables), a pˇr´ısluˇsej´ıc´ıch funkc´ı, zvan´ ych metody (methods). V ˇclensk´ ych promˇenn´ ych je obsaˇzen stav objektu, tj. vˇse, co si objekt ”pamatuje”, a metody vyjadˇruj´ı jeho chov´an´ı, tedy vˇse, co objekt ”um´ı”. Tˇ r´ıda Tˇr´ıdou se v podstatˇe rozum´ı obecn´e vlastnosti, kter´e objekt mus´ı m´ıt, aby do n´ı mohl b´ yt zaˇrazen - neboli: tˇr´ıda je popisem, vzorem, pˇredlohou cel´e skupiny podobn´ ych objekt˚ u. V programovac´ım jazyce je tˇr´ıda (class (3) ) pˇresnˇe pops´ana. Z hlediska syntaxe je tˇr´ıda obyˇcejnou deklarac´ı datov´e struktury (podobnˇe jako record v Pascalu nebo struct v C) rozˇs´ıˇrenou o metody. Tˇr´ıda pˇredstavuje objektov´ y typ, objekt se t´eˇz naz´ yv´a instanc´ı tˇr´ıdy. ych Spojov´ e datov´ e struktury Pro probl´emy kde neum´ıme dopˇredu odhadnout poˇcet ukl´adan´ datov´ ych jednotek, protoˇze tyto dynamicky vznikaj´ı nebo zanikaj´ı, se pouˇz´ıv´a mechanizmus jejich spojov´an´ı a tyto datov´e struktury se naz´ yvaj´ı spojov´e. Uchov´avan´a datov´a jednotka je rozˇs´ıˇrena o poloˇzku, naz´ yvanou ukazatel, kter´a ukazuje na dalˇs´ı datovou jednotku. Spr´ avnost program˚ u Testov´an´ım programu, tj. ovˇeˇren´ım, ˇze pro dan´ y vstup z´ısk´ame spr´avn´ y v´ ysledek nem˚ uˇzeme obecnˇe prok´azat spr´avnost programu, protoˇze mnoˇzstv´ı r˚ uzn´ ych vstup˚ u
1
je aˇz na trivi´aln´ı pˇr´ıpady tak velik´e, ˇze toto nen´ı moˇzn´e ani pouˇzit´ım velice rychl´ ych poˇc´ıtaˇc˚ u. Na druh´e stranˇe testov´an´ı m˚ uˇze prok´azat chybu v programu. Sekvence pˇr´ıkaz˚ u (pˇriˇrazen´ı, alternativy a cyklu) umoˇzn ˇuje dok´az´an´ı spr´avnosti programu tak, ˇze m˚ uˇzeme napsat tvrzen´ı o hodnot´ach promˇenn´ ych pˇred vykon´an´ım pˇr´ıkazu, kter´e naz´ yv´ame pˇredpoklad a tvrzen´ı po jeho vykon´an´ı, kter´e naz´ yv´ame d˚ usledek. Anal´ yza program˚ u Anal´ yza algoritmu urˇcuje poˇzadovan´e prostˇredky na jeho vykon´an´ı. Prostˇredky mohou b´ yt ˇcas potˇrebn´ y na v´ ypoˇcet, pamˇeˇt pro uloˇzen´ı dat, ˇs´ıˇrka komunikaˇcn´ıho p´asma pro pˇrenos dat ap. Asymptotick´ a sloˇ zitost – Asymptotick´a sloˇzitost vyjadˇruje limitn´ı r˚ ust ˇcasu v´ ypoˇctu, kdyˇz velikost probl´emu neomezenˇe roste. Obvykle, aˇz na vstupy mal´e velikosti, algoritmus, kter´ y je asymptoticky efektivnˇejˇs´ı je pak lepˇs´ı volbou. Srovn´ an´ı sloˇ zitosti algoritm˚ u Polynomi´ aln´ı algoritmy – Algoritmy, jejichˇz ˇcas v´ ypoˇctu jsou asymptoticky omezeny polynomi´aln´ı funkc´ı velikosti jejich vstupu se naz´ yvaj´ı polynomi´aln´ı a jsou prakticky pouˇziteln´e. Ukazuje se vˇsak, ˇze m´ame-li pro probl´em polynomi´aln´ı algoritmus, ˇcasto se pro takov´ y probl´em najde lepˇs´ı polynomi´aln´ı algoritmus. Nav´ıc, skl´adan´ı polynomi´aln´ıch algoritm˚ u vede opˇet na polynomi´aln´ı algoritmy. Vol´ame-li napˇr´ıklad v polynomi´aln´ım algoritmu konstantn´ı poˇcet metod implementuj´ıc´ıch polynomi´aln´ı algoritmus, ˇcas v´ ypoˇctu sloˇzen´eho algoritmu je polynomi´aln´ı. Exponenci´ aln´ı algoritmy – Algoritmy, kter´e jsou omezeny alespoˇ n exponenci´aln´ı funkc´ı velikosti jejich vstupu, se naz´ yvaj´ı exponenci´aln´ı, a pokud se nepouˇz´ıvaj´ı pouze na vstupy mal´eho rozsahu jsou prakticky nepouˇziteln´e. Na tyto algoritmy vede tzv. metoda hrub´ e s´ıly, kdy v algoritmu zkoum´ame vˇsechny moˇznosti. Rekurze Definov´an´ı funkce nebo procesu pomoc´ı jeho sam´eho. pˇ r´ım´ a rekurze – nast´av´a tehdy, kdyˇz podprogram aktivuje s´am sebe. nepˇ r´ım´ a rekurze – nast´av´a tehdy, aktivuj´ı-li se vz´ajemnˇe dva podprogramy. Rekurzivn´ı ˇ reˇ sen´ı – pravidla • Mus´ı b´ yt definov´ana podm´ınka pro ukonˇcen´ı rekurze. • V kaˇzd´em kroku rekurze mus´ı doj´ıt ke zjednoduˇsen´ı probl´emu. • V algoritmu se nejprve mus´ı ovˇeˇrit, zda nenastala koncov´a situace. Kdyˇz ne, provede se rekurzivn´ı krok. Abstraktn´ı datov´ e typy ADT je matematick´ y model spoleˇcnˇe s operacemi nad t´ımto modelem. Patˇr´ı sem z´ asobn´ık, fronta a seznam. Z´ asobn´ık a fronta jsou dynamick´e mnoˇziny, pro kter´e je specificky definov´ana operace vybr´an´ı prvku z mnoˇziny. Pokud na ADT z´asobn´ık a fronta nahl´ıˇz´ıme jako na posloupnosti vloˇzen´ ych prvk˚ u, v pˇr´ıpadˇe z´asobn´ıku se vkl´ad´an´ı a vyj´ım´an´ı prvk˚ u uskuteˇcn ˇuje na jednom konci posloupnosti a v pˇr´ıpadˇe fronty se prvky vkl´adaj´ı na jednom konci a vyb´ıraj´ı na druh´em konci. ADT seznam je tedy ve srovn´an´ı s ADT z´asobn´ık a fronta, daleko flexibilnˇejˇs´ı. y byl operac´ı vloˇz do Z´ asobn´ık Pro z´asobn´ık operace vyber ze z´asobn´ıku vyjme prvek, kter´ z´ asobn´ıku vloˇzen jako posledn´ı. Tento postup se oznaˇcuje term´ınem last-in, first-out – LIFO y je ve frontˇe vloˇzen´ y nejd´ele. Jin´ ymi Fronta Pro frontu operace vyber z fronty vyjme prvek, kter´ slovy, z prvk˚ u, kter´e jsou ve frontˇe vybere ten, kter´ y byl do fronty vloˇzen jako prvn´ı. Tento postup se oznaˇcuje term´ınem first-in, first-out – FIFO
2
Seznam Seznam je posloupnost. Jde opˇet o dynamickou mnoˇzinu prvk˚ u, kde m˚ uˇzeme prvky vkl´adat a vyj´ımat na libovoln´e pozici v posloupnosti. Dalˇs´ı podtypy – Kruhov´ y spojov´ y seznam, Obousmˇern´ y spojov´ y seznam. Strom Strom je matematick´a abstrakce organizace dynamick´ ych mnoˇzin. Prvky v dynamick´e mnoˇzinˇe organizovan´e jako strom naz´ yv´ame vrcholy. Nˇekter´e vrcholy jsou spojeny a toto spojen´ı naz´ yv´ame hranou. Strom potom m˚ uˇzeme rekurzivnˇe definovat n´asledovnˇe • Jeden vrchol je strom. Tento vrchol je tak´e koˇrenem takov´ehoto stromu. • Nechˇt x je vrchol a T1, T2, ..., Tn jsou stromy. Strom je vrchol x spojen´ y s koˇreny strom˚ u T1, T2, ..., Tn. • V tomto stromˇe je x koˇrenem stromu. Stromy T1, T2, ..., Tn se naz´ yvaj´ı podstromy. Jejich koˇreny jsou (pˇr´ım´ ymi) n´ asledn´ıky vrcholu x a vrchol x je jejich (pˇr´ım´ ym) pˇ redch˚ udcem. Nˇekdy je vhodn´e zahrnout mezi stromy i pr´azdnou mnoˇzinu vrchol˚ u. Vrchol, kter´ y nem´a n´asledn´ıky se naz´ yv´a listem. Vrchol, kter´ y nen´ı listem se naz´ yv´a vnitˇ rn´ım vrcholem. Koˇren stromu nem´a ˇz´adn´e pˇredch˚ udce. Cesta je posloupnost vrchol˚ u, ve kter´e po sobˇe jdouc´ı vrcholy jsou spojeny hranou. D´ elka cesty je poˇcet hran cesty. D´elku cesty z vrcholu k sobˇe sam´emu potom m˚ uˇzeme definovat jako nulovou. Ke kaˇzd´emu vrcholu je z koˇrene pr´avˇe jedna cesta. Hloubka vrcholu ve ´ stromˇe (´ uroveˇ n, na kter´e se nach´az´ı) je definov´ana jako d´elka t´eto cesty. Uroveˇ n (hloubka) koˇrene stromu je tedy nulov´a. V´ yˇ ska stromu je maxim´aln´ı hloubka vrcholu stromu. Pr˚ uchody stromem Z´akladn´ı typy pr˚ uchod˚ u jsou tˇri – preorder, inorder a postorder Pˇr´ım´ y pr˚ uchod (preorder)- navˇst´ıv´ıme vrchol, potom lev´ y a prav´ y podstrom Vnitˇrn´ı pr˚ uchod (inorder)- navˇst´ıv´ıme lev´ y podstrom, vrchol a prav´ y podstrom Zpˇetn´ y pr˚ uchod (postorder)- navˇst´ıv´ıme lev´ y a prav´ y podstrom a potom vrchol y strom anebo vrchol, kter´ y m´a lev´ y a Bin´ arn´ı vyhled´ avac´ı stromy Bin´arn´ı strom je pr´azdn´ prav´ y podstrom, kter´e jsou bin´arn´ı stromy. Bin´arn´ı vyhled´avac´ı strom je potom bin´arn´ı strom, kter´ y splˇ nuje: • Nechˇt x je vrchol stromu. • Je-li y vrchol v lev´em podstromu, potom y.kl´ıˇc < x.kl´ıˇc. • Je-li y vrchol v prav´em podstromu, potom y.kl´ıˇc > x.kl´ıˇc. Vˇsechny operace nad BVS proch´azeli stromem od koˇrene nejv´ıce k jeho list˚ um. Z toho plyne, ˇze ˇcas jejich v´ ypoˇctu je O(h), kde h je hloubka stromu. ˇ v´ Cas ypoˇctu z´akladn´ıch operac´ı nad BVS v pr˚ umˇern´em pˇr´ıpadu je O(log2 n). Grafy a jejich implementace Form´ alnˇe je graf dvojice G = (V, H), kde V je mnoˇzina vrchol˚ u (uzl˚ u) a H je mnoˇzina hran, pˇriˇcemˇz hrana je dvojice (u, v)u, vV . Poˇcet vrchol˚ u grafu G pak je |V | a poˇcet jeho hran je |H|. Mnoˇzinu vrchol˚ u grafu G budeme zapisovat V (G) a mnoˇzinu jeho hran H(G). Plat´ı-li (u, v) 6= (v, u) je hrana orientovan´a, tj. m´a zaˇc´ateˇcn´ı a koncov´ y vrchol. Takov´ y graf naz´ yv´ame orientovan´ y a jsou v nich moˇzn´e hrany z vrcholu do t´ehoˇz vrcholu. V opaˇcn´em pˇr´ıpadˇe (u,v) = (v,u) a graf se naz´ yv´a neorientovan´ y, pˇriˇcemˇz budeme poˇzadovat u 6= v Stupeˇ n vrcholu orientovan´eho grafu je d´an souˇctem poˇctu hran do nˇej vstupuj´ıc´ıch a poˇctu hran z nˇej vystupuj´ıc´ıch. V neorientovan´em grafu je stupeˇ n vrcholu d´an poˇctem incidentn´ıch hran, tj. hran, kter´ ych je vrchol souˇc´ast´ı. 3
Reprezentace grafu Dva standardn´ı zp˚ usoby v informatice pro reprezentaci grafu jsou • seznamy sousednosti • matice sousednosti Seznamy sousednosti Pro kaˇzd´ y vrchol grafu G = (V, H) je vytvoˇren seznam soused˚ u. Seznam soused˚ u pro vrchol u V obsahuje vˇsechny vrcholy v, pro kter´e je (u, v)H. Soused´ıc´ı vrcholy jsou obecnˇe uloˇzeny v seznamech v libovoln´em poˇrad´ı. Celkov´a d´elka seznam˚ u sousednosti pro orientovan´ y graf je zˇrejmˇe 2|H|, protoˇze je-li hrana (u, v)H, potom v je v seznamu soused˚ u u a u je v seznamu soused˚ u v. Poˇzadovan´a velikost pamˇeti tedy v obou pˇr´ıpadech je Θ(|V | + |H|). Reprezentace seznamem sousednosti je vhodn´a i pro ohodnocen´e grafy. Ohodnocen´ım grafu G se naz´ yv´a funkce w : H(G)− > R Je-li (u, v)H(G), w(u, v) se uloˇz´ı ve vrcholu v seznamu soused˚ u vrcholu u. Pˇr´ıkladem m˚ uˇze b´ yt ohodnocen´ı hran reprezentuj´ıc´ıch poˇc´ıtaˇcovou s´ıˇt pˇrenosov´ ymi rychlostmi. Potenci´aln´ı nev´ yhodou reprezentace grafu seznamy sousednosti je zjiˇsˇtov´an´ı existence hrany (u, v), coˇz znamen´a hledat vrchol v v seznamu soused˚ u vrcholu u. Matice sousednosti Oznaˇcme vrcholy ˇc´ısly 1, , |V |. Matice sousednosti je matice S = (sij), i, j = 1, , |V |, pˇriˇcemˇz je-li (i, j)H, sij = 1, jinaksij = 0. Matic´ı sousednosti lze implementovat i ohodnocen´ y graf. Pro ohodnocen´ y graf je suv = w(u, v), je-li (u, v)H(G), suv je hodnota mimo hodnot moˇzn´ ych ohodnocen´ı, nen´ı-li (u, v)H(G). Klasifikace hran Vytvoˇren´ı lesa strom˚ u prohled´an´ım orientovan´eho grafu do hloubky umoˇzn ˇuje zav´est klasifikaci jeho hran. 1. Stromov´ e hrany. Jsou hrany patˇr´ıc´ım strom˚ um lesa. Hrana (u, v) je stromov´a byl-li vrchol v objeven z vrcholu u. 2. Zpˇ etn´ e hrany. Jsou hrany (u, v), kde vrchol v je pˇredkem vrcholu u, tj. vrchol v leˇz´ı na cestˇe z koˇrene DFS stromu do vrcholu u. Hrana (u, u) je povaˇzov´ana za zpˇetnou. 3. Dopˇ redn´ e hrany. Jsou hrany (u, v), kde vrchol u je pˇredkem vrcholu v v DSF stromˇe. 4. Kˇ riˇ zuj´ıc´ı hrany. Vˇsechny ostatn´ı hrany. Spojuj´ı vrcholy jednoho DSF stromu pokud jeden z nich nen´ı pˇredkem druh´eho anebo vrcholy r˚ uzn´ ych strom˚ u lesa DSF strom˚ u. V pˇr´ıpadˇe neorientovan´eho grafu je (u, v)a(v, u) tat´aˇz hrana. Hrana je potom klasifikov´ana podle prvn´ıho z jejich vyj´adˇren´ı, kter´e nalezne algoritmus prohled´av´an´ı do hloubky. Je moˇzn´e uk´azat, ˇze pˇri prohled´av´an´ı neorientovan´eho grafu do hloubky, kaˇzd´a z jeho hran je ˇ stromov´a nebo zpˇetn´a. bud Zpˇetn´e hrany jsou kl´ıˇcem, k nalezen´ı cykl˚ u v grafu. Vznikne-li prohled´an´ım grafu do hloubky zpˇetn´a hrana, graf obsahuje cyklus. Je-li (u, v) zpˇetn´a hrana, potom cesta z v do u a tato hrana tvoˇr´ı cyklus. Obr´acenˇe lze dok´azat, ˇze je-li v grafu cyklus, jeho prohled´an´ım do hloubky mus´ı vzniknout zpˇetn´a hrana. Prohled´ av´ an´ı grafu M´ame prohled´av´an´ı do ˇs´ıˇrky a do hloubky Prohled´ av´ an´ı do ˇ s´ıˇ rky Pro dan´ y graf G = (V, H) vybereme zaˇc´ateˇcn´ı vrchol s a systematick´ ym postupem nalezneme vˇsechny dosaˇziteln´e vrcholy, tj. takov´e, ke kter´ ym vede v grafu G cesta tvoˇren´a posloupnost´ı jeho hran. N´azev prohled´av´an´ı je odvozen z toho, ˇze ze zaˇc´ateˇcn´ıho vrcholu s nalezneme vˇsechny vrcholy ve vzd´alenosti k od vrcholu s pˇredt´ım, neˇz nalezneme vrcholy ve vzd´alenosti 4
k + 1. Jin´ ymi slovy napˇred nalezneme vˇsechny sousedy zaˇc´ateˇcn´ıho vrcholu, potom jejich sousedy atd. Algoritmus pracuje pro orientovan´e i neorientovan´e grafy. Pˇri postupu prohled´av´an´ı je potˇreba m´ıt informaci jestli jsme jiˇz vrchol nalezli. Dalˇs´ı informac´ı, kterou m˚ uˇzeme sledovat je, jestli jsme pro dan´ y vrchol nalezli vˇsechny sousedy. Tyto informace m˚ uˇzeme udrˇzovat tzv. barven´ım vrchol˚ u. Pˇred zaˇc´atkem prohled´av´an´ı jsou vˇsechny vrcholy b´ıl´e a po prvn´ım nalezen´ı je vrchol obarven ˇsedˇe. Nalezli-li jsme vˇsechny jeho sousedy a tedy nem´a b´ıle obarven´e sousedy, je vrchol obarven ˇcernˇe. Algoritmus konˇc´ı se vˇsemi uzly obarven´ ymi ˇcernˇe. Prohled´av´an´ı do ˇs´ıˇrky umoˇzn ˇuje nalezen´ı vzd´alenosti vrchol˚ u grafu od zaˇc´ateˇcn´ıho vrcholu jakoˇz i cesty ze zaˇc´ateˇcn´ıho vrcholu k vrchol˚ um grafu. Vzd´ alenost zaˇc´ateˇcn´ıho vrcholu od sebe sam´eho je 0. Vrcholy nalezen´e jako jeho sousedi maj´ı vzd´alenost o 1 vˇetˇs´ı, tedy 1, vrcholy nalezen´e z vrchol˚ u ve vzd´alenosti 1 maj´ı vzd´alenost o 1 vˇetˇs´ı, tedy 2 atd. Pro nalezen´ı cesty ze zaˇc´ateˇcn´ıho vrcholu k vrcholu grafu staˇc´ı, aby jsme kdyˇz je vrchol poprv´e nalezen do nˇej uloˇzili vrchol, z kter´eho byl nalezen. Tomuto vrcholu budeme ˇr´ıkat pˇ redch˚ udce. Zaˇc´ateˇcn´ı vrchol nem´a pˇredch˚ udce. Pro kaˇzd´ y jin´ y vrchol zn´ame jeho pˇredch˚ udce, pro nˇej jeho pˇredch˚ udce, atd. aˇz pˇrijdeme k vrcholu bez pˇredch˚ udce, tedy k zaˇc´ateˇcn´ımu vrcholu. Vlastnosti prohled´ av´ an´ı do ˇ s´ıˇ rky Vrcholy grafu, jsou pˇri vloˇzen´ı do fronty obarveny ˇsedˇe a jiˇz se nikdy nestanou b´ıl´e, a proto jsou do n´ı vloˇzeny a vybr´any nejv´ıce jednou. Protoˇze vloˇzen´ı a vybr´an´ı z fronty je O(1), trv´an´ı vˇsech tˇechto operac´ı je O(|V |). Seznamy sousednosti vrchol˚ u jsou proch´azen´e kdyˇz je vrchol vybr´an z fronty. Souˇcet jejich d´elek je Θ(|H|) a tedy ˇcas jejich proch´azen´ı je O(|H|). ˇ prohled´av´an´ı do hloubky tedy jeO(|V | + |H|). Cas Prohled´ av´ an´ı do hloubky Na rozd´ıl od prohled´av´an´ı do ˇs´ıˇrky v grafu hled´ame vrcholy, kdyˇz je to moˇzn´e, napˇred do hloubky, tj. do vˇetˇs´ı vzd´alenosti. Tedy, kdyˇz m´a zaˇc´ateˇcn´ı vrchol souseda, d´al hled´ame nˇekter´eho z jeho soused˚ u atd. Kdyˇz projdeme vˇsechny sousedy vr´at´ıme se k vrcholu, z kter´eho byl nalezen a stejn´ ym zp˚ usobem pokraˇcujeme d´al. Algoritmus opˇet pracuje pro orientovan´e i neorientovan´e grafy. Podobnˇe jako u prohled´av´an´ı do ˇs´ıˇrky pouˇzijeme techniku barven´ı uzl˚ u. Na zaˇc´atku prohled´av´an´ı jsou vˇsechny vrcholy obarveny b´ıle, kdyˇz je vrchol poprv´e nalezen je obarven ˇsedˇe. Kdyˇz jsme proˇsli vˇsechny jeho sousedy, je obarven ˇcernˇe, kdy se vr´at´ıme k vrcholu, z kter´eho byl objeven, tedy k jeho pˇredch˚ udci anebo skonˇc´ıme, kdyˇz jde o zaˇc´ateˇcn´ı vrchol, kter´ y nem´a pˇredch˚ udce. Vlastnosti prohled´ av´ an´ı do hloubky Na zaˇc´atku prohled´av´an´ı jsou vˇsechny vrcholy obarveny b´ıle a jejich poloˇzka prechudce je nastavena na -1 pr´avˇe jednou, coˇz trv´a Θ(|V |). Metoda DFS( ) je vol´ana pro b´ıl´e vrcholy a tedy pr´avˇe jednou pro kaˇzd´ y vrchol, protoˇze tento je pˇri vol´an´ı ihned obarven ˇsedˇe. Cyklus for je vykon´an pro vˇsechny sousedy vrcholu, tedy tolikr´at kolik z nˇeho vych´az´ı hran. Poˇcet ˇ jeho vykon´an´ı je tedy omezen souˇctem d´elek seznam˚ u sousednosti, a tedy je O(|H|). Cas v´ ypoˇctu prohled´av´an´ı do hloubky potom je O(|V | + |H|). u, ve kter´e je definovan´e uspoˇr´adan´ı jen pro nˇekter´e Topologick´ eˇ razen´ı Mˇejme mnoˇzinu prvk˚ dvojice, napˇr. prvky jsou ˇcinnosti v ˇcase. Pˇr´ıkladem m˚ uˇze b´ yt mont´aˇz sloˇzit´eho zaˇr´ızen´ı, kdy nˇekter´e u ´kony mus´ıme vykon´avat za sebou a nˇekter´e jsou na sobˇe nez´avisl´e. Zjednoduˇsen´ ym pˇr´ıkladem je obl´ekan´ı, kdy obleˇcen´ı hodinek je nez´avisl´e na vˇsech ostatn´ıch u ´konech, avˇsak pˇred t´ım neˇz si obleˇceme sako, jistˇe si mus´ıme obl´ect koˇsili. Jestliˇze prvky uvaˇzovan´e mnoˇziny zobraz´ıme jako vrcholy grafu a dvojice prvk˚ u (u, v), pro kter´e je definov´ano uspoˇr´adan´ı tak, ˇze u pˇredch´az´ı v, budou tvoˇrit jeho orientovan´e hrany, vznikne orientovan´ y acyklick´ y graf (directed acyclic graph - DAG). Na topologick´e seˇrazen´ı grafu m˚ uˇzeme nahl´ıˇzet jako na um´ıstnˇen´ı jeho vrchol˚ u na horizont´aln´ı pˇr´ımce, pˇriˇcemˇz vˇsechny hrany jsou orientov´any zleva doprava. 5
Algoritmus topologick´eho ˇrazen´ı • Vytvoˇr les strom˚ u prohled´av´an´ım do hloubky. • Kdyˇz je vrchol ukonˇcen pˇridej ho do na zaˇc´atek seznamu. • Vraˇt seznam vrchol˚ u. ˇ v´ Cas ypoˇctu topologick´eho ˇrazen´ı zˇrejmˇe je Θ(|V | + |H|), protoˇze vytvoˇren´ı lesa strom˚ u prohled´av´an´ım do hloubky je Θ(|V |+|H|) a vloˇzen´ı kaˇzd´eho z |V | vrchol˚ u na zaˇc´atek seznamu je O(1). Tabulka s pˇ r´ım´ ym adresov´ an´ım Odpov´ıdaj´ıc´ı abstrakce je organizace dat, kde podle jednoznaˇcn´e hodnoty kl´ıˇce prvku mnoˇziny zpˇr´ıstupˇ nujeme dalˇs´ı hodnoty uloˇzen´e v prvku mnoˇziny (pˇripomeˇ nme, ˇze s t´ımto zp˚ usobem pr´ace s daty jsme se setkali u ADT BVS). V pˇr´ıpadˇe matematick´ ych tabulek je kl´ıˇcem ˇc´ıslo a zjist´ıme jeho logaritmus, pˇrevr´acenou hodnotu, atd. V tabulce startuj´ıc´ıch je kl´ıˇcem startovn´ı ˇc´ıslo a z tabulky zjist´ıme jm´eno startuj´ıc´ıho a pˇr´ıpadnˇe dalˇs´ı uchov´avan´e informace jako vˇek, nejlepˇs´ı dosavadn´ı v´ ykon ap. Pokud vytvoˇr´ıme tabulku pˇrevr´acen´ ych hodnot pro ˇc´ısla od 1 do 1000, potom obsahuje tuto hodnotu pro kaˇzdou hodnotu kl´ıˇce. Efektivn´ı implementace takov´e tabulky je pole, kde kl´ıˇc je pˇr´ımo indexem prvku, ve kter´em je uchov´avan´a hodnota. Nalezen´ı t´eto hodnoty je O(1). Tabulka pˇrihl´aˇsen´ ych u ´ˇcastn´ık˚ u sportovn´ıho kl´an´ı m´a stejnou vlastnost. Pro implementaci t´eto mnoˇziny je moˇzn´e uvaˇzovat spojov´ y seznam, ve kter´em kaˇzd´ y prvek obsahuje startovn´ı ˇc´ıslo, poˇrad´ı, v´ ykon a ukazatel na dalˇs´ı prvek. Nalezen´ı poˇrad´ı a v´ ykonu u ´ˇcastn´ıka se zadan´ ym startovn´ım ˇc´ıslem je potom O(n). Pokud jsou startovn´ı ˇc´ısla pˇridˇelov´ana n´ahodnˇe, m˚ uˇzeme mnoˇzinu u ´ˇcastn´ık˚ u, kteˇr´ı dos´ahli c´ıl, organizovat jako BVS, napˇr´ıklad vytv´aˇren´ım BVS vkl´ad´an´ım vrcholu s uveden´ ymi u ´daji, kdyˇz u ´ˇcastn´ık z´avodu dos´ahl c´ıle. Vyhled´an´ı poˇrad´ı a v´ ykonu u ´ˇcastn´ıka se zadan´ ym startovn´ım ˇc´ıslem je potom, jak jiˇz v´ıme, O(log2 n). Rozptylov´ e tabulky s vnˇ ejˇ s´ım ˇ razen´ım Uvaˇzujme d´ale situaci, ˇze mnoˇzina A prvk˚ u uloˇzen´ ych v tabulce je daleko menˇs´ı neˇz mnoˇzina vˇsech hodnot kl´ıˇce, tedy |A| << |K|. Pokud prvky mnoˇziny resp. ukazatele na nˇe budeme kv˚ uli rychlosti pˇr´ıstupu cht´ıt uchov´avat v poli, abychom nemrhali pamˇet´ı, toto pole by mˇelo m´ıt rozmˇer u ´mˇern´ y |A|. Zat´ım ponechme stranou jeho velikost ve vztahu k poˇctu uloˇzen´ ych prvk˚ u mnoˇziny |A| a oznaˇcme jeho velikost a t´ım i velikost tabulky m, pˇriˇcemˇz m << |K|. V tabulce budou nyn´ı prvky mnoˇziny identifikovan´e sv´ ym kl´ıˇcem zpˇr´ıstupˇ nov´any pomoc´ı indexu s hodnotami 0 aˇz m-1. Potˇrebujeme tedy hodnotu kl´ıˇce prvku transformovat na hodnotu indexu, jin´ ymi slovy mus´ıme definovat funkci: h : K0, 1, ...m − 1, kterou budeme naz´ yvat rozptylovac´ı funkc´ı (hash function). Vzhledem k tomu, ˇze m << |K|, tedy poˇcet vˇsech kl´ıˇc˚ u je daleko vˇetˇs´ı neˇz poˇcet hodnot index˚ u, na kter´e je zobrazujeme, nevyhnutnˇe mus´ı rozptylov´a funkce zobrazit obecnˇe dva a v´ıce r˚ uzn´ ych kl´ıˇc˚ u na stejn´ y index, tj. pro u 6= vau, vK bude h(u) = h(v) V ide´aln´ım pˇr´ıpadˇe, kdy rozptylov´a funkce je dostateˇcnˇe n´ahodn´a, budou vˇsechny kl´ıˇce mnoˇziny uloˇzen´ ych prvk˚ u zobrazeny na r˚ uzn´e hodnoty index˚ u, samozˇrejmˇe za pˇredpokladu m ≥ |A|. Na druh´e stranˇe je moˇzn´e, ˇze v nejhorˇs´ım pˇr´ıpadˇe se kl´ıˇce vˇsech uloˇzen´ ych prvk˚ u zobraz´ı na jeden index. Pˇri n´ahodn´em v´ ybˇeru prvk˚ u nelze kolize obecnˇe vylouˇcit a mus´ıme se zab´ yvat ˇreˇsen´ım t´eto situace. Pˇri postupn´em vkl´ad´an´ı prvk˚ u dynamick´e mnoˇziny do tabulky, v pˇr´ıpadˇe, ˇze prvek m´a b´ yt um´ıstnˇen na pozici v tabulce, kter´a je jiˇz obsazena, v z´asadˇe existuj´ı dvˇe moˇznosti. Prvn´ı je vnˇejˇs´ı zˇretˇezen´ı prvk˚ u, kter´ ych kl´ıˇce rozptylov´a funkce zobraz´ı na stejnou hodnotu. Druhou je otevˇren´e adresov´an´ı, kdy v pˇr´ıpadˇe kolize je prvek mnoˇziny systematicky um´ıstnˇen a n´aslednˇe hled´an v tabulce. V tomto pˇr´ıpadˇe mus´ı b´ yt m ≥ |A|, zat´ımco v prvn´ım pˇr´ıpadˇe pˇrich´az´ı do u ´vahy vˇsechny moˇznosti, tj. m < |A|, m = |A|im < |A|. Vnˇ ejˇ s´ı ˇ retˇ ezen´ı – Anal´ yza
6
Kolize jsou pˇri t´eto metodˇe ˇreˇseny tak, ˇze se vytvoˇr´ı seznam prvk˚ u, jejichˇz kl´ıˇce jsou zobrazeny na stejnou pozici v tabulce. Pˇripomeˇ nme, ˇze do tabulky o m pozic´ıch vkl´ad´ame |A| prvk˚ us r˚ uzn´ ymi kl´ıˇci z mnoˇziny vˇsech kl´ıˇc˚ u o velikosti |K|, pˇriˇcemˇz m << |K|. Pro trivi´aln´ı pˇr´ıpad |A| = 1, kolize nem˚ uˇze vzniknout. Pro |A| ≤ m, m´a rozptylovac´ı funkce ˇsanci pˇridˇelit kaˇzd´emu vkl´adan´emu prvku r˚ uznou pozici, ale je i moˇznost, ˇze vˇsechny prvky budou vloˇzeny na stejnou pozici v tabulce a vytvoˇr´ı seznam d´elky |A|. Prioritn´ı fronta Kdyˇz se procesor stane voln´ ym, pˇridˇel´ı se u ´loze s nejvyˇsˇs´ı prioritou. Bˇehem jej´ıho v´ ypoˇctu mohou pˇrij´ıt dalˇs´ı u ´lohy a kdyˇz jej´ı v´ ypoˇcet skonˇc´ı vybere se opˇet u ´loha s aktu´alnˇe nejvyˇsˇs´ı prioritou, atd. Odpov´ıdaj´ıc´ı abstraktn´ı datov´ y typ, tedy mus´ı poskytovat operace vloˇz prvek a vyber nejvˇetˇs´ı prvek. Takov´ y ADT budeme naz´ yvat prioritn´ı frontou. Element´arn´ı implementace ADT prioritn´ı fronta mohou obdobnˇe jako z´asobn´ık a fronta pouˇz´ıt pole nebo spojov´ y seznam. Prvky prioritn´ı fronty m˚ uˇzeme uchov´avat v uspoˇr´adan´em poli, kdy operace v´ ybˇeru prvku, pˇr´ımo odebere nejvˇetˇs´ı prvek z konce pole, ale vloˇzen´ı prvku mus´ı zachovat uspoˇr´adan´ı. Operace odebr´an´ı maxima se vykon´a v konstantn´ım ˇcase, operace vloˇzen´ı m´a sloˇzitost max. Θ(n) Alternativnˇe m˚ uˇzeme prioritn´ı frontu implementovat neuspoˇr´adan´ ym polem, kdy nevˇetˇs´ı prvek budeme hledat aˇz pˇri jeho vyb´ıran´ı. V tomto pˇr´ıpadˇe operace vloˇzen´ı prvku m´a konstantn´ı ˇcas, kdeˇzto operace v´ ybˇeru nejvˇetˇs´ıho prvku v nejhorˇs´ım pˇr´ıpadˇe potˇrebuje proj´ıt vˇsechny prvky pole. Halda Strom m´a vlastnost haldy, kdyˇz kl´ıˇc v kaˇzd´em vrcholu je vˇetˇs´ı nebo roven kl´ıˇc˚ um v jeho n´asledn´ıc´ıch, pokud je m´a. Ekvivalentnˇe, kl´ıˇc v kaˇzd´em vrcholu je menˇs´ı nebo roven kl´ıˇci v jeho pˇredch˚ udci, pokud ho m´a. Z uveden´e vlastnosti plyne, ˇze ˇz´adn´ y vrchol ve stromˇe s vlastnost´ı haldy nem´a kl´ıˇc vˇetˇs´ı neˇz koˇren. M´ame-li prioritn´ı frontu implementovanou haldou, potom nalezen´ı nejvˇetˇs´ıho prvku je O(1). Jeho v´ ybˇer vˇsak vyˇzaduje n´ahradu prvku, kter´ y byl koˇrenem. Abychom zachovali poˇzadavek u ´pln´eho stromu, nahrad´ıme ho posledn´ım prvkem nejniˇzˇs´ı u ´rovnˇe, coˇz m˚ uˇze v´est k poruˇsen´ı vlastnosti hlady, pokud by tento prvek mˇel menˇs´ı kl´ıˇc, neˇz nˇekter´ y z jeho n´asledn´ık˚ u. Na druh´e stranˇe, vloˇz´ıme-li prvek, bude tento dalˇs´ım listem a pokud m´a vˇetˇs´ı kl´ıˇc neˇz jeho pˇredch˚ udce, opˇet doˇslo k poruˇsen´ı vlastnosti haldy. Uveden´e situace m˚ uˇzeme zobecnit na dva pˇr´ıpady kdy se poruˇs´ı vlastnost haldy a nutno ji obnovit, chceme-li vyuˇz´ıvat jej´ı vlastnost. Algoritmy ˇ razen´ı O(N logN ) Patˇr´ı sem ˇrezen´ı haldou, Shallovo ˇrazen´ı, ˇrazen´ı dˇelen´ım a ˇrazen´ı sluˇcov´an´ım ˇ Razen´ ı haldou Na zaˇc´atku kaˇzd´e iterace, vˇsechny vrcholy s indexy i + 1, i + 2, ..., pocet jsou koˇreny hald. Inicializace: Pˇred prvn´ı iterac´ı je i == pocet/2, tedy i je pˇredch˚ udcem posledn´ıho listu. Jin´ ymi slovy, ˇz´adn´ y z n´asleduj´ıc´ıch vrchol˚ u jiˇz nem´a n´asledn´ıky, jsou tedy listy a t´ım koˇreny jednoprvkov´ ych hald. Udrˇ zov´ an´ı: N´asledn´ıci vrcholu i maj´ı indexy vˇetˇs´ı neˇz i, jsou tedy haldami a metoda dolu( ) vytvoˇr´ı haldu s koˇrenem i, pˇriˇcemˇz zachov´a haldy s koˇreny i + 1, i + 2, ..., pocet. Dekrementov´an´ım i obnov´ıme invariant pˇred dalˇs´ı iterac´ı. Skonˇ cen´ı: Po skonˇcen´ı je i == 0, a tedy kaˇzd´ y vrchol i = 1, 2, ..., pocet je koˇrenem haldy a specielnˇe je n´ım vrchol s indexem 1. Shellovo ˇ razen´ı ˇ Razen´ı vkl´ad´an´ım je pomal´e, kdyˇz prvky v ˇrazen´e posloupnosti jsou vzd´alen´e od sv´e spr´avn´e pozice v seˇrazen´e posloupnosti, protoˇze jsou vymˇen ˇov´any jenom se sv´ ym sousedem. Myˇslenka D. Shella z roku 1959 je podobn´a pro vkl´ad´an´ı. Aby jsme zkr´atili cestu prvku ke spr´avn´e pozici, seˇrad´ıme vkl´ad´an´ım prvky vzd´alen´e h. Cel´a ˇrazen´a posloupnost je nyn´ı 7
organizov´ana jako h podposloupnost´ı zaˇc´ınaj´ıc´ıch prvky na pozic´ıch 0, 1, ..., h-1, kaˇzd´a obsahuj´ıc´ı prvky vzd´alen´e h. Knuth navrhnul zvolit zaˇc´ateˇcn´ı vzd´alenost pˇribliˇznˇe tˇretinovou a postupnˇe ji dˇelit tˇremi. Pˇresnˇeji, posloupnost vzd´alenost´ı jsou prvky posloupnosti 1 4 13 40 121 364 1093 3280 ... coˇz jsou ˇc´ısla tvaru 3i + 1, i = 0, 1, ... . ˇ Razen´ ı dˇ elen´ım Z´ akladem algoritmu je metoda deleni( ), kter´a pˇreuspoˇr´ad´a ˇrazen´e pole tak, aby byly splnˇeny n´asleduj´ıc´ı podm´ınky: 1. Prvek a[i] je na sv´e spr´avn´e koneˇcn´e pozici. 2. Prvky a[l], ..., a[i-1] jsou menˇs´ı nebo rovny a[i]. 3. Prvky a[i+1], ..., a[p] jsou vˇetˇs´ı nebo rovny a[i]. Napˇred mus´ıme zvolit dˇel´ıc´ı prvek, tak´e naz´ yvan´ y pivotem, kter´ y bude pˇri dˇelen´ı um´ıstnˇen na koneˇcnou pozici. Je zˇrejm´e, ˇze uveden´ y rekurzivn´ı algoritmus seˇrad´ı prvky pole, aˇt zvol´ıme jako dˇel´ıc´ı prvek kter´ ykoliv prvek ˇrazen´eho pole. Obecnˇe, na splnˇen´ı uveden´ ych podm´ınek projdeme pole zleva dokud nenalezneme vˇetˇs´ı prvek neˇz dˇel´ıc´ı prvek v a d´ale ho projdeme zprava dokud nenalezneme menˇs´ı prvek neˇz dˇel´ıc´ı prvek. Tyto dva prvky pak vymˇen´ıme. ˇ Razen´ ı sluˇ cov´ an´ım Algoritmus ˇrazen´ı sluˇcov´an´ım je komplement´arn´ı k ˇrazen´ı dˇelen´ı. Nam´ısto dˇelen´ı posloupnosti je algoritmus ˇrazen´ı sluˇcov´an´ım zaloˇzen na sluˇcov´an´ı seˇrazen´ ych podposloupnost´ı. Prvky uspoˇr´adan´ ych pol´ı a a b seˇrad´ıme slouˇcen´ım do pole c jejich postupn´ ym proch´azen´ım od zaˇc´atku a vybr´an´ım menˇs´ıho prvku. Pˇrijdeme-li na konec jednoho z nich pˇrekop´ırujeme zb´ yvaj´ıc´ı prvky druh´eho. Naˇs´ım u ´kolem je ovˇsem seˇradit prvky jednoho pole. Pˇredpokl´adejme, ˇze v poli a jsou dva vzestupnˇe seˇrazen´e u ´seky. Seˇradit je algoritmem ˇrazen´ı sluˇcov´an´ım m˚ uˇzeme tak, ˇze vytvoˇr´ıme pole b s bitonickou posloupnost´ı prvk˚ u pole a, tj. druh´ yu ´sek bude seˇrazen sestupnˇe. Je-li posloupnost a = 1,3,7,2,6 potom odpov´ıdaj´ıc´ı bitonick´a posloupnost je b = 1,3,7,6,2 . Doln´ı omezen´ı pro porovn´ avac´ı ˇ razen´ı Pˇredpokl´adejme, ˇze vˇsechny prvky posloupnosti a1, a2, ..., an jsou r˚ uzn´e. Porovn´ avac´ı ˇrazen´ı m˚ uˇzeme zn´azornit rozhodovac´ım stromem. Ve vnitˇrn´ıch vrcholech jsou prvky, kter´e algoritmus porovn´a a v listech je permutace vˇsech prvk˚ u p˚ uvodn´ı posloupnosti, kter´a je seˇrazena. V prvn´ım kroku porovn´ame prvky s indexy 1 a 2. Ve druh´em kroku jsou-li ve spr´avn´em poˇrad´ı porovn´ame prvky s indexy 2 a 3. Nebyly-li ve spr´avn´e poˇrad´ı jsou algoritmem vymˇenˇeny v prvn´ım kroku a ve druh´em kroku, v tomto pˇr´ıpadˇe porovn´av´ame prvky s indexy 1 a 3. Cel´ y postup pokraˇcuje aˇz v listu stromu jsou indexy v poˇrad´ı, kter´e vyjadˇruje permutaci, ve kter´e jsou prvky a1,a2,a3 seˇrazeny. Jak´ ykoliv spr´avn´ y algoritmus mus´ı v rozhodovac´ım stromu vytvoˇrit kaˇzdou z n! permutac´ı prvk˚ u p˚ uvodn´ı posloupnosti, aby dok´azal seˇradit jakoukoliv vstupn´ı posloupnost. Kaˇzd´a z tˇechto permutac´ı mus´ı b´ yt alespoˇ n v jednom listˇe. T(n) = h Nyn´ı mus´ıme naj´ıt doln´ı omezen´ı vˇsech rozhodovac´ıch strom˚ u. Nechˇt rozhodovac´ı strom o v´ yˇsce h m´a l list˚ u, potom l ≤ 2h. Souˇcasnˇe list˚ u mus´ı b´ yt alespoˇ n tolik kolik je permutac´ı, tedy n! ≤ l. Potom n! ≤ l ≤ 2h a logaritmov´an´ım log2(n!) ≤ h = T (n) Pouˇzit´ım aproximace (n/e)n pro n! je log2(n!) = n ∗ log2n − n ∗ log2e, ˇc´ım dost´av´ame doln´ı omezen´ı pro nejhorˇs´ı pˇr´ıpad Ω(n ∗ log2n). Protoˇze pro ˇrazen´ı haldou a sluˇcov´an´ım je horn´ı omezen´ı ˇcasu v´ ypoˇctu O(n*log2 n) jsou tato ˇrazen´ı asymptoticky optim´aln´ı. 8
Generiˇ cnost Jde o obecnou kategorii, jako vlastnost nebo vztah, povaˇzovanou za rozd´ılnou od vˇec´ı, kter´e jsou jej´ı instanc´ı anebo pˇr´ıkladem. Dˇ ediˇ cnost Obecn´ y zp˚ usob vytvoˇren´ı v´ıce specializovan´e tˇr´ıdy je vytvoˇren´ı podtˇ r´ıdy nˇejak´e tˇr´ıdy, kterou nazveme nadtˇ r´ıdou. Terminologie nen´ı ust´alen´a a jako synonyma se pouˇz´ıvaj´ı tak´e z´ akladn´ı a odvozen´a tˇr´ıda nebo rodiˇcovsk´a tˇr´ıda a tˇr´ıda potomek. Tomuto procesu, jak jsme jiˇz pˇredeslali v pˇredch´azej´ıc´ım ˇcl´anku se ˇr´ık´a dˇediˇcnost. Podtˇr´ıda, odvozen´a tˇr´ıda, potomek dˇed´ı vlastnosti nadtˇr´ıdy, z´akladn´ı tˇr´ıdy, rodiˇce. Podtˇr´ıda, odvozen´a tˇr´ıda: • z´ısk´av´a vˇsechny metody a promˇenn´e nadtˇr´ıdy • m˚ uˇze pˇridat nov´e metody a promˇenn´e tˇr´ıdy • m˚ uˇze pˇredefinovat metody a promˇenn´e rodiˇce Rozhran´ı Rozhran´ı definuje soubor metod bez jejich implementace. Jde tedy o koncepˇcnˇe stejnou myˇslenku jako jsme pouˇzili pˇri ADT, kde jsme pomoc´ı rozhran´ı oddˇelili definici operac´ı a jejich implementaci. Tˇr´ıda, kter´a implementuje rozhran´ı, tedy definovan´ y soubor metod, (tj. jakoby je zdˇed´ı), mus´ı implementovat (tj. jakoby pˇrekr´ yt) vˇsechny metody rozhran´ı. Za pˇredpokladu, ˇze rozhran´ı je implementov´ano nˇejakou tˇr´ıdou, lze k instanc´ım takov´eto tˇr´ıdy pˇristupovat pomoc´ı referenˇcn´ı promˇenn´e typu rozhran´ı obdobnˇe, jako lze pˇristupovat k instanc´ım podtˇr´ıdy pomoc´ı referenˇcn´ıch promˇenn´ ych nadtˇr´ıdy. Algoritmick´ aˇ reˇ sitelnost probl´ em˚ u M´ame-li probl´em formalizov´an ptejme se, jestli existuje ˇ na tuto pro kaˇzd´ y probl´em formalizovan´ y uveden´ ym zp˚ usobem algoritmus. Pro odpovˇed ot´azku je uveden´a abstrakce probl´emu obecnˇejˇs´ı neˇz je nutn´e. Staˇc´ı, omez´ıme-li se na tˇr´ıdu rozhodovac´ıch probl´em˚ u. Rozhodovac´ı probl´emy jsou takov´e, kter´ ych mnoˇzina ˇreˇsen´ı je dvouhodnotov´a ano /ne. Pro rozhodovac´ı probl´emy je zobrazen´ı mnoˇziny instanc´ı na mnoˇzinu ˇreˇsen´ı funkc´ı. Rozhodovac´ı probl´emy m˚ uˇzeme formulovat ve vztahu k obecnˇejˇs´ım probl´em˚ um. Zap´ıˇseme-li ˇreˇsen´ı probl´emu ve tvaru programu pro poˇc´ıtaˇc, instance probl´emu je vstup programu a bude pouˇzit´ım odpov´ıdaj´ıc´ıho k´odov´an´ı vyj´adˇrena jako ˇretˇezec 0 a 1, kter´ y m˚ uˇzeme jednoznaˇcnˇe interpretovat jako pˇrirozen´e ˇc´ıslo (moˇzn´a velice velik´e). Churchova-Turingova teze Ve tˇric´at´ ych letech minul´eho stolet´ı, Alan Turing zavedl pro opis algoritm˚ u form´aln´ı prostˇredek, naz´ yvan´ y Turingovy stroje a Alonzo Church lambda - kalkulus. Uk´azali, ˇze opisuj´ı stejnou mnoˇzinu funkc´ı. Tyto v´ ysledky vedly k Churchovˇe - Turingovˇe tezi, kter´a tvrd´ı, ˇze kaˇzd´ y algoritmus m˚ uˇze b´ yt vykon´an Turingov´ ym strojem. Nav´ıc, kaˇzd´ y program v konvenˇcn´ıch programovac´ıch jazyc´ıch m˚ uˇze b´ yt transformov´an na Turing˚ uv stroj a naopak. Konvenˇcn´ı programovac´ı jazyky a tak´e Java jsou dostateˇcn´e pro vyj´adˇren´ı jak´ehokoliv algoritmu. Tak´e dalˇs´ı formalizace pojmu algoritmu vedly ke stejn´emu v´ ysledku a obecnˇe se pˇredpokl´ad´a platnost Churchove Turingove teze. Churchova - Turingova teze vˇsak nen´ı vˇetou a nem˚ uˇze b´ yt dok´az´ana. M˚ uˇze b´ yt vyvr´acena, bude-li objevena metoda akceptov´ana jako algoritmus, kter´ y nebude moˇzno vykonat Turingov´ ym strojem. Existuje-li tedy rozhodovac´ı probl´em, pro jehoˇz ˇreˇsen´ı neexistuje program, napˇr´ıklad v Javˇe, potom je tento probl´em algoritmicky neˇreˇsiteln´ y a naopak. Rozhodnutelnost Uvaˇzujme vˇsechny rozhodovac´ı programy v Javˇe. Jejich bin´arn´ı tvar m˚ uˇzeme interpretovat jako pˇrirozen´a ˇc´ısla a vyjmenovat je v jejich poˇrad´ı, tedy P0, P1, ..., Pn, ... . Kaˇzd´ y z nich m˚ uˇze m´ıt vstup interpretovan´ y jako pˇrirozen´e ˇc´ıslo 0, 1, 2, ..., k, ... a jeho v´ ystupem je Pn(k) 0, 1.
9
Vytvoˇrme matici, jej´ıˇz prvek v ˇr´adku n a sloupci k je Pn(k). M´a-li kaˇzd´ y rozhodovac´ı probl´em specifikovan´ y nˇejakou funkc´ı f: N 0, 1 aspoˇ n jeden program v Javˇe, jenˇz jej vypoˇc´ıt´a, mus´ı v uveden´e matici existovat ˇr´adek takov´ y, ˇze Px(k) = f(k), k = 0, 1, 2, ... Pro libovoln´e poˇrad´ı ˇr´adk˚ u v matici m˚ uˇzeme definovat odpov´ıdaj´ıc´ı probl´em D. Existuj´ı tedy rozhodovac´ı probl´emy, pro kter´e neexistuj´ı v Javˇe programy a tedy vzhledem k ChurchovˇeTuringovˇe tezi, pro nˇe neexistuj´ı ˇz´adn´e algoritmy. Takov´e probl´emy se naz´ yvaj´ı algoritmicky nerozhodnuteln´e. Probl´em zastaven´ı Prvn´ı algoritmicky nerozhodnuteln´ y probl´em uk´azal v roce 1936 Alan Turing. Jde o probl´em zastaven´ı (halting problem), kter´ y pomoc´ı program˚ u, napˇr´ıklad v Javˇe, m˚ uˇzeme formulovat n´asledovnˇe: Vstup: Program P v Javˇe reprezentov´an jako pˇrirozen´e ˇc´ıslo a jeho vstup k reprezentov´an tak´e jako pˇrirozen´e ˇc´ıslo. V´ ystup: 1 kdyˇz se program P zastav´ı , 0 kdyˇz se program P nezastav´ı. Klasifikace probl´ em˚ u
10
2
Programovac´ı techniky
´ Uvod do technologie programov´ an´ı a programovac´ıch styl˚ u Glob´aln´ı krit´eria na programovac´ı jazyk: • Spolehlivost – typov´a kontrola, vyj´ımeˇcn´e situace ypoˇctu • Efektivita – ef. pˇrekladu a v´ • Strojov´a nez´avislost ˇ • Citelnost a vyjadˇrovac´ı schopnosti ˇ adnˇe definovan´a syntax a s´emantika • R´ ´ v Turingovˇe smyslu: celoˇc´ıseln´a aritmetika, celoˇc´ıseln´e promˇenn´e, sekvenˇcnˇe • Uplnost prov´adˇen´e operace, pˇriˇrazen´ı a cyklus (while). Objektovˇ e orientovan´ y n´ avrh C´ılem n´avrhu je vytvoˇrit takov´ y syst´em, kter´ y m´a vlastnosti: • Robustnost – Spr´avnˇe reagovat na vstupy, kter´e nejsou pro syst´em explicitnˇe definov´any • Pˇ rizp˚ usobivost – Schopnost s minim´aln´ıma zmˇenama fungovat i na jin´ ych platform´ach zitelnost – Vytvoˇrit syst´em, jehoˇz ˇc´asti p˚ ujde pouˇz´ıt i v dalˇs´ıch syst´emech • Znovupouˇ => vytvoˇren´ı znovupouˇziteln´ ych bal´ık˚ u Principy objektovˇe orientovan´eho n´avrhu: • Abstrakce – C´ılem je rozdˇelit sloˇzit´ y syst´em na jednoduˇsˇs´ı ˇc´asti a ty potom ˇreˇsit jednotlivˇe • Zapouzdˇ ren´ı – Skr´ yvat implementaˇcn´ı detaily a uˇzivateli poskytnout jen rozhran´ı na vyˇsˇs´ı u ´rovni, kter´e bude moci snadno pouˇz´ıt a pˇritom ho nemus´ı zaj´ımat vnitˇrek • Modularita – Rozdˇelen´ı syst´emu do samostanˇe funguj´ıch bal´ık˚ u – znovupouˇzitelnost Dalˇs´ı d˚ uleˇzit´ y vlasnosti pˇri objektov´em n´avrhu: • Dˇ ediˇ cnost – Schopnost objektu vyuˇz´ıvat funkce a objekty nadˇrazen´eho objektu • Polymorfismus – Schopnost objektu pˇredefinovat funkˇcnost nadˇrazen´eho objektu, aniˇz by t´ım zmˇenil princip nebo implementaci Z´ akladn´ı UML diagramy UML definuje tyto diagramy: • Diagramy tˇ r´ıd a objekt˚ u – Statick´ y popis syst´emu, jeho objekt˚ u a vztah˚ u mezi nimi • Modely jedn´ an´ı – Zn´azorˇ nuje pˇr´ıpady pouˇzit´ı syst´emu, na kter´e mus´ı syst´em reagovat • Sc´ en´ aˇ re ˇ cinnost´ı – Popisuj´ı sc´en´aˇr pr˚ ubˇehu urˇcit´e ˇcinnosti v syst´emu ace – Spolepr´ace existuj´ıc´ıch objekt˚ u • Diagramy spolupr´ • Stavov´ e diagramy – Dynamick´e chov´an´ı objektu v syst´emu ubˇeh aktivit proces˚ u nebo ˇcinnost´ı • Diagramy aktivit – Pr˚ • Diagramy komponent – Rozdˇelen´ı cel´eho syst´emu na jednotliv´e komponenty a jejich funkci • Diagramy nasazen´ı – Um´ıstˇen´ı funkˇcn´ıch celk˚ u na v´ ypoˇcetn´ı uzly syst´emu Psan´ı program˚ u v Javˇ e Obecnˇe se uv´ad´ı 3 z´akladn´ı kroky: • N´avrh • K´odov´an´ı • Testov´an´ı a ladˇen´ı 11
O tom, v jak´em poˇrad´ı se tyto kroky pouˇz´ıj´ı z´avis´ı na metodice. Implementace abstraktn´ıch datov´ ych typ˚ u z´ asobn´ık Teorie viz ppa2. Z´ asobn´ık by mˇel obsahovat tyto funkce: push – pˇrid´an´ı objektu na vrchol z´asobn´ıku, pop – vybr´an´ı z vrcholu z´asobn´ıku, size – zjiˇstˇen´ı velikosti z´asobn´ıku, isEmpty – zda je z´asobn´ık pr´ azdn´ y, top – stejnˇe jako pop, ale objekt v z´asobn´ıku z˚ ustane. Implementace: polem, spojov´ ym seznamem, java.Utils.Stack Fronta Teorie viz ppa2. Fronta by mˇela obsahovat tyto funkce: enqueue – pˇrid´an´ı na konec fronty, dequeue – odebrani ze zacatku fronty, size – zjiˇstˇen´ı velikosti fronty, isEmpty – zda je fronta pr´azdn´a, front – stejnˇe jako ezueue, ale objekt ve frontˇe z˚ ustane Implementace: polem, spojov´ ym seznamem, java.Utils.LinkedList Seznamy Line´arn´ı posloupnost prvk˚ u Seznam by mˇel obsahovat tyto funkce: first – odkaz na prvn´ı prvek seznamu, last – odkaz na posledn´ı prvek seznamu, before – odkaz na pˇredchoz´ı prvek, after – odkaz na n´asleduj´ıc´ı prvek, isFirst – zda je zadan´ y prvek prvn´ı, isLast – zda je zadan´ y prvek posledn´ı, replacementElement – nahrazen´ı prvku na urˇcen´e pozici, swapElements – vymˇenˇen´ı dvou prvk˚ u na urˇcen´ ych pozic´ıch, insertFirst – vloˇzen´ı na zaˇc´atek, insertLast – vloˇzen´ı na konec, insertBefore – vloˇzen´ı pˇred urˇcenou pozici, insertAfter – vloˇzen´ı za urˇcenou pozici, remove – odstranˇen´ı urˇcen´eho prvku Implementace: obousmˇern´ ym spoj´akem ˇ Rady Vektory Nˇeco jako pole, je to line´arn´ı posloupnost prvk˚ u Vektor by mˇel obsahovat tyto funkce: elemAtRank – vrac´ı prvek na urˇcen´e pozici, replaceAtRank – nahrazuje prvek na urˇcit´e pozici, insertAtRank – vloˇzen´ı prvku na urˇcenou pozici, removeAtRank – odstranˇen´ı prvku z urˇcen´e pozice Implementace: polem Stromov´ e skruktury a jejich implementace Teorie viz ppa2 AVL strom Je to vyv´aˇzen´ y bin´arn´ı vyhled´avac´ı strom, pro kter´ y plat´ı, ˇze pro libovoln´ y vnitˇrn´ı uzel se v´ yˇska lev´eho a prav´eho prvku liˇs´ı maxim´alnˇe o 1. Vyv´aˇzenost se kontroluje po kazd´e operaci, pokud je strom nevyv´aˇzen´ y, mus´ı se vyv´aˇzit. BVS strom Bin´arn´ı vyhled´avac´ı strom. Viz ppa2 B strom B strom ˇr´adu m je strom, kde kaˇzd´ y uzel m´a maxim´alnˇe m n´asledovn´ık˚ u a plat´ı: • Poˇcet kl´ıˇc˚ u v kazd´em uzlu je o jeden menˇs´ı neˇz poˇcet n´asledovn´ık˚ u ´rovni • Vˇsechny listy jsou na stejn´e u • Vˇsechny uzly, kromˇe koˇrenu, maj´ı minim´alnˇe m/2 n´asledovn´ık˚ u Pokud se nˇekter´a z podm´ınek poruˇs´ı, je potˇreba strom vyv´aˇzit Red-black strom Vlastnosti Red-Black strom˚ u: • Kaˇzd´ y uzel stromu je obarven ˇcervenou nebo ˇcernou barvou. 12
• Koˇren stromu je obarven ˇcernˇe. • Listy (nil) jsou ˇcern´e. ˇ • Cerven´ y uzel m´a pouze ˇcern´e syny. • Na kter´ekoliv cestˇe z koˇrene do listu leˇz´ı stejn´ y poˇcet ˇcern´ ych uzl˚ u Pokud se nˇekter´a z podm´ınek poruˇs´ı, je potˇreba strom vyv´aˇzit Skip-list – pouˇ zit´ı a implementace Datov´a struktura, kter´a m˚ uˇze b´ yt pouˇzita jako n´ahrada za stromy. Je to pravdˇepodobnostn´ı alternativa k vyv´aˇzen´ ym strom˚ um, v´ yhody od strom˚ u: • Jednoduch´a implementace • Jednoduch´e algoritmy vloˇzen´ı a zruˇsen´ı ˇ • Casov´ a sloˇzitost je stejn´a jako u strom˚ u (nebo alespoˇ n se jim bl´ıˇz´ı) Vlastnosti skip-listu: • Prvky v seznamu jsou uspoˇr´ad´any u • Prvky maj´ı k ukazatel˚ • Uzel s k-ukazateli se naz´ yv´a uzel u ´rovnˇe k • Ide´ aln´ı skip-list – kaˇzd´ y 2i prvek m´a ukazatel, kter´ y ukazuje o 2i dopˇredu u je mnohon´asobnˇekr´at Tabulky z rozpt´ ylen´ ymi poloˇ zkami Pouˇz´ıvaj´ı se v pˇr´ıpadˇe, ˇze poˇcet kl´ıˇc˚ vˇetˇs´ı, neˇz je velikost tabulky. Pro urˇcen´ı pozice v tabulce tak mus´ıme pouˇz´ıt nˇejakou rozptylovac´ı funkci (hash). Pro r˚ uzn´e kl´ıˇce m˚ uˇzou b´ yt stejn´e poloˇzky v tabulce, tomu ˇr´ık´ame kolize. Poˇzadavky na rozptylovou funkci: • Pro kaˇzd´ y kl´ıˇc je jednoznaˇcnˇe definovan´a a v pˇrijateln´em ˇcase vyˇc´ısliteln´a • Vytv´aˇr´ı minim´aln´ı poˇcet kol´ız´ı • Pravdˇepodobnostn´ı rozloˇzen´ı je rovnomˇern´e Tabulky s otevˇ ren´ ym rozpt´ ylen´ım Kaˇzd´a pozice tabulky je potenci´alnˇe pˇr´ıstupn´a kaˇzd´emu kl´ıˇci. Pokud je pˇri pˇriˇrazen´ı kliˇci pozice tabulky jiˇz toto m´ısto pln´e, mus´ıme definovat jak´ ym zp˚ usobem uloˇz´ıme hodnotu kl´ıˇce: • Konstantn´ı krok – pˇri kolizi posuneme prvek o k pozic • Line´ arn´ı fce – pˇri kolizi pˇrepoˇc´ıt´ame, o kolik se posuneme a fce – pˇri kolizi pˇrepoˇc´ıt´ame, o kolik se posuneme • Kvadratick´ Tabulky s otevˇ ren´ ym rozpt´ ylen´ım a vnitˇ rn´ım ˇ retˇ ezen´ım Pˇri kolizi nepˇrepoˇc´ıt´av´ame, o kolik nebo kam se posunout, ale novou poloˇzku raˇzad´ıme na nejbliˇzˇs´ı dalˇs´ı voln´e m´ısto a na p˚ uvodn´ı poloˇzku (respektive na konec seznamu) uloˇz´ıme ukazatel na tento nov´ y prvek. Tabulky s uzavˇ ren´ ym rozpt´ ylen´ım a vnˇ ejˇ s´ım zˇ retˇ ezen´ım Princip stejn´ y jako viz v´ yˇse, ale pˇri kolizi neukl´ad´ame prvky pˇr´ımo do tabulky, ale ukl´ad´ame je do nov´e tabulky postupnˇe. Ukazatele na tyto poloˇzky z˚ ust´avaj´ı. y kl´ıˇc z´ısk´ame pozici v tabulce. Pokud kl´ıˇc na dan´e pozici Vyhled´ av´ an´ı v tabulk´ ach Pro dan´ nen´ı: • spoˇc´ıt´ame pomoc´ı funkce, o koli se m´ame posunout a posouv´ame se tak dlouho, dokud kl´ıˇc nenademe. 13
• nebo pˇreˇcteme ukazatel na dalˇs´ı prvek a posouv´ame se tak dlouho, dokud ho nenajdeme Algoritmy zpracov´ an´ı textu Vyhled´av´an´ı ˇretˇezc˚ u Algoritmus hrub´ e s´ıly Pro kaˇzdou pozici v textu hled´ame, zda nezaˇc´ın´a stejnˇe jako vzor. V pˇr´ıpadˇe, ˇze ano, ˇ porovn´av´ame dalˇs´ı p´ısmena, v pˇr´ıpadˇe, ˇze ne, posuneme vroz o jednu pozici. Casov´ a sloˇzitost je O(m ∗ n). Rychl´ y je algoritmus pro velkou abecedu, pro malou naopak velice pomal´ y. Boyer-Moore algoritmus Zaloˇzen na zrcadlov´em pˇr´ıstupu k vyhled´av´an´ı. Postupujeme tak, ˇze porovn´av´ame posledn´ı p´ısmeno v ˇretˇezci. Pokud se neshoduje, m´ame nˇekolik moˇznost´ı: • Pokud se posledn´ı znak v textu nal´ez´a v hledan´em ˇretˇezci, posuneme ho tak, aby tyto dva znaky st´aly proti sobˇe • Pokud se posledn´ı znak v textu nenal´ez´a v hledan´em ˇretˇezci, posuneme hledan´ y ˇretˇezec o jeho celou d´elku. • Pokud nelze prov´est krok 2, zarovn´ame ˇretˇezec na konec. V tomto algoritmu je pˇred zaˇc´atkem potˇreba vytvoˇrit funkci last, kter´a si zaindexuje pozice znak˚ u v hledan´em ˇretˇezci. Rychl´ y pro velkou abecedu, pomal´ y pro malou abecedu. KMP algoritmus Vyhled´av´an´ı zleva doprava. Pˇri porovn´av´an´ı a neshodˇe se posov´ame o co nejvˇetˇs´ı ˇc´ast. Tato nejvˇetˇs´ı ˇc´ast je definov´ana jako nejvˇetˇs´ı prefix, kter´ y je i z´aroveˇ n suffixem. Pˇred vyled´av´an´ım mus´ıme nejprve tyto prefixy zaindexovat. Pˇri samotn´em vyhled´av´an´ı se pak posouv´ame o hodnoty v t´eto tabulce. V´ yhodn´ y pro vyhled´av´an´ı v rozs´ahl´ ych textech. Rabin-Karp algoritmus Vytv´aˇr´ıme kontroln´ı souˇcty v hled´anem textu i vzoru. Pˇred samotn´ ym vyhled´av´an´ım vypoˇc´ıt´ame kontroln´ı souˇcet hledan´eho ˇretˇezce a vˇsech podˇretˇezc˚ u stejn´e d´elky v hledan´em textu. Potom porovn´av´ame tyto kontroln´ı souˇcty a pokud se shoduj´ı, porovn´ame i jednotliv´a p´ısmena (m˚ uˇze j´ıt o faleˇsnou shodu hashe – kolizi). Kontroln´ı souˇcet vypoˇc´ıt´ame Hornerov´ ym sch´ematem (ale fakticky lze pouˇz´ıt jakoukoliv hash funkci) Komprese dat C´ılem komprese dat je redukovat objem dat. Kvalitu komprese urˇcuje: • Rychlost komprese • Symetrie/asymetrie kompresn´ıho algoritmu • Kopresn´ı pomˇer Rozdˇ elen´ı kompresn´ıch metod Podle komprese: • Bezztr´atov´a – menˇs´ı kompresn´ı pomˇer, ale zachov´an´ı vˇsech informac´ı • Ztr´atov´a – vˇetˇs´ı kompresn´ı pomˇer, ale kreslen´ı dat Podle metody koprese: • Jednoduch´e – zaloˇzeny na k´odov´an´ı opakuj´ıc´ıch se ˇc´ast´ı • Statistick´e – zoloˇzeny na ˇcetnosti v´ yskyt˚ u znak˚ u 14
• Slovn´ıkov´e – k´odov´an´ı vˇsech vyskytuj´ıc´ıch se posloupnost´ı • Transformaˇcn´ı – zaloˇzeny na ortogon´aln´ı transformaci Princip kompresn´ıch metod – RLE Jednoduch´a metoda komprese. K´odujeme opakuj´ıc´ı se posloupnosti AAAABBBCC = 4A3B2C. Je to bezztr´atov´a komprese, pouˇz´ıt´ı hlavnˇe na obr´ azky – bmp. Huffman Statistick´a metoda k´odov´an´ı Algoritmus k´odov´an´ı: u v k´odovan´em textu. • Zjist´ıme ˇcetnost vˇsech znak˚ • Vytvoˇr´ıme bin´arn´ı strom – seˇrad´ıme znaky podle ˇcetnosti. • Uloˇzen´ı stromu • Nahrazen´ı znak˚ u k´ody podle stromu Algoritmus dek´odov´an´ı: Naˇcteme uloˇzen´ y strom a nahrad´ıme ˇc´ısla znaky. Aritmetick´ e k´ odov´ an´ı Statistick´a metoda. K´odujeme celou zpr´avu jako jedno k´odov´e slovo na intervalu [0, 1). Na zaˇc´atku uvaˇzujeme celo´ y tento interval a jak se zprva prodluˇzuje, ˇ ım je k´odovan´ zpˇresˇ nujeme interval a jeho doln´ı a horn´ı mez se k sobˇe pˇribliˇzuj´ı. C´ y znak pravdˇepodobnˇejˇs´ı, t´ım kratˇs´ı je ten interval a t´ım p´adem potˇrebujme i m´enˇe bit˚ u na jeho z´ apis. Na konec staˇc´ı zapsat libovoln´e ˇc´ıslo z v´ ysledn´eho intervalu. Algoritmus k´odov´an´ı: ych znak˚ u ze souboru. • Zjist´ıme pravdˇepodobnosti jednotliv´ • Stanoven´ı pˇr´ısluˇsn´ ych kumulativn´ıch pravdˇepodobnost´ı. Posloupnost [0, 1) rozdˇel´ıme pro jednotliv´e znaky podle jejich ˇcetnost´ı. • Uloˇzen´ı pouˇzit´ ych pravdˇepodobnost´ı • Vlastn´ı komprese: Zaˇc´ın´ame s cel´ ym intervalem I = [0, 1), doln´ı mez oznaˇc´ıme jako D(I), horn´ı mez jako H(I) a d´elku intervalu jako L(I). Potom pˇreˇcteme prvn´ı znak na vstupu a vypoˇc´ıt´ame nov´ y interval – I = [D(I) + K(i) ∗ L(I), D(I) + K(i + 1) ∗ L(I)). Po naˇcten´ı posledn´ıho znaku zap´ıˇseme hodnotu D(I). Algoritmus dek´ov´an´ı: • Rekonstrukce pouˇzit´ ych pravdˇepodobnost´ı • Vlastn´ı dekomprese: Pˇreˇcteme posledn´ı uloˇzen´e ˇc´ıslo. Pot´e postupnˇe naˇc´ıt´ame znaky na vstupu. Pro naˇcten´ y znak X najdeme takov´e i, aby leˇzelo v intervalu [K(i), K(i+1)). Vytiskneme i a vypoˇc´ıt´ame nov´ y X = (X − K(i))/P (i) LZW Slovn´ıkov´a metoda. K´odujeme opakuj´ıc´ı se posloupnosti. Tyto posloupnosti si postupnˇe ukl´ ad´ame do slovn´ıku (ten ale neukl´ad´ame). K´odujeme hned, nepotˇrebujeme pˇredbˇeˇznou anal´ yzu souboru. Postup pˇri k´odov´an´ı: Pˇreˇcteme prvn´ı znak (S). Z´ısk´ame znak na vstupu (C). Pokud S+C jeˇstˇe nen´ı v tabulce, zak´odujeme S a S = C. Pokud uˇz v tabulce je, pokraˇcujeme d´ale (naˇcten´ı znaku C na vstup). Postup pˇri dek´odov´an´ı: Pˇreˇcteme prvn´ı znak (OLD) a zap´ıˇseme ho na v´ ystup. Z´ısk´ame znak na vstupu (NEW). Jestliˇze NEW nen´ı v tabulce, pak S = OLD + C, jinak S = S+C. Pot´e vyp´ıˇseme S na v´ ystup. C = prvn´ı znak S. Zap´ıˇseme OLD + C do tabulky a OLD = NEW. Pokraˇcujeme pˇreˇcten´ım vstupu (NEW).
15
ˇ asti obraz˚ JPG Ztr´atov´a komprese. Pouˇz´ıv´a se pro komprimaci obr´azk˚ u. C´ u se transformuj´ı do frekvenˇcn´ı oblasti a z´ısk´ame matici frekvenˇcn´ıch koeficient˚ u. Z t´eto matice se odstran´ı frekvence odpov´ıdaj´ıc´ı vyˇsˇs´ım frekvenc´ım, to jsou hrany v obraze. Zb´ yvaj´ıc´ı frekvence se vhodn´ ym zp˚ usobem zkomprimuj´ı. Princip diskr´etn´ı kosinov´e transformace: • Zdrojov´ y obraz rozdˇel´ıme na bloky 8x8 pixel˚ u • Hodbnoty jasu se v kaˇzd´em bloku transformuj´ı z intervalu [0, 2p −1] na interval [2p , 2p −1] • Provedeme transformaci podle jednoho ˇs´ılen´eho vzorce. Frakt´ alov´ a komprese Z´akladn´ı princip spoˇc´ıv´a v rozdˇelen´ı komprinovan´eho obrazu na range bloky (nepˇrekr´ yvaj´ı se) a vyhled´an´ı domain blok˚ u (mohou se pˇrekr´ yvat), kter´e jsou range blok˚ um podobn´e. Domain bloky se mohou vyktytovat ve sv´e z´akladn´ı podobˇe nebo v nˇejak´e transformovan´e podobˇe – otoˇcen´e apod. Algoritmus komprese: • Rozdˇelen´ı obrazu na range bloky, kter´e pokr´ yvaj´ı cel´ y obraz. • Proch´az´ıme obraz a vytv´aˇr´ıme domain bloky, kter´e maj´ı dvojn´asobnou velikost oproti range blok˚ um. Hranice mezi domain bloky jsou pr˚ umˇerov´any a ukl´ad´any do nov´ ych blok˚ u. Tyto bloky pot´e nahrad´ı star´e range bloky. • Nakonec pro kaˇzd´ y range blok najdeme domain blok, kter´ y se mu nejv´ıce podob´a.
16
3
Programovac´ı struktury
Charakteristiky programov´ ych paradigmat Programov´a paradigmata jsou souhrny zp˚ usobu formulace probl´em˚ u, metodologick´ ych prostˇredk˚ u ˇreˇsen´ı, metodik zpracov´an´ı apod. Paradigmata: • Procedur´aln´ı prrogramov´an´ı • OOP • Deklarativn´ı programov´an´ı • Aplikativn´ı programov´an´ı • Funkcion´aln´ı programov´an´ı • Logick´e programov´an´ı • Programov´an´ı ohraniˇcen´ımi • Vizu´aln´ı programov´an´ı • Soubˇeˇzn´e programovn´ı – paraleln´ı, distribuovan´e Koexistence paradigmat: Deklarativn´ı — Programov´an´ı ohraniˇcen´ımi + Aplikativn´ı Aplikativn´ı — Fukcion´aln´ı + Logick´e Logick´ e programov´ an´ı a jazyk Prolog Konstanty – ˇc´ısla, atomy; Promˇ enn´ e – A, ;Struktury – muz(jan), cte (student(jan),kniha(X)) Z´ asady pˇ ri plnˇ en´ı c´ıl˚ u: uˇze b´ yt sloˇzen z nˇekolika c´ıl˚ u • Dotaz m˚ • C´ıle jsou plnˇeny zleva doprava • Pro kaˇzd´ y c´ıl je prohled´av´an´ı datab´aze odzaˇc´atku • Pˇri u ´spˇeˇsn´em porovn´an´ı je m´ısto v datab´azi oznaˇceno ukazatelem. Kaˇzd´ y z c´ıl˚ u m´a vlastn´ı ukazatel • Nen´ı-li nˇekter´ y z c´ıl˚ u splnˇen, aktivuje se mechanismus n´avratu • Splnˇen´ı vˇsech jednotliv´ ych c´ıl˚ u znamen´a splnˇen´ı glob´aln´ıho c´ıle Mechanismus n´ avratu: • Vr´at´ıme se o krok zpˇet, zruˇs´ıme splnˇen´ y c´ıl a pokraˇcujeme ve vyhled´av´an´ı od toho ukazatele d´ale v datab´azi • Najdeme-li nov´ y c´ıl pro tento krok, pokraˇcujeme d´ale ysledek je no • Nenejdeme-li, vrac´ı se opˇet o kroz zpˇet. Pokud jsme na zaˇc´atku, v´ Program – specifikuje mnoˇzinu klauzul´ı, nic v´ıc Fakt – jm´eno relace a argumenty v dan´em uspoˇr´ad´an´ı Pravidlo – vyjadˇruje vztahy, kter´e plat´ı, jsou-li splnˇeny podm´ınky z tˇela Dotaz – tvoˇr´ı jeden nebo v´ıce c´ıl˚ u Definice predik´ atu – poslouplnost klauzul´ı pro jednu relaci Plnˇ en´ı c´ıle – prohled´av´an´ı datab´aze od zaˇc´atku, resp. navr´acen´ı)
od ukazatele (pˇri mechanismu
Rekurzivn´ı definice predik´ atu – obsahuje ukonˇcovac´ı podm´ınku Funktor – urˇcen jm´enem a aritou Seznamy – rekurzivn´ı datov´a struktura ve tvaru [hlava — zbytek]
17
P´ ar z´ akladn´ıch pˇ r´ıkaz˚ u – member(prvek, seznam), last (seznam, prvek), delete (p˚ uvodn´ı, v´ ysledn´ y, prvek), append(seznam1, seznam2, vysledek) Predik´ aty ˇ rezu – pouˇz´ıvaj´ı se, pokud chceme zabr´anit vyhled´av´an´ı dalˇs´ıch alternativ. Odˇr´ızne Zelen´ yˇ rez – nemˇen´ı deklarativn´ı smysl ˇ cerven´ yˇ rez – mˇen´ı deklarativn´ı smysl I/O operace – write, nl, tab (vystup mezery), display, read, put, get, get0 (i pro nezobrazitelne znaky) Funkcion´ aln´ı programov´ an´ı a jazyk Lisp Zaloˇzeny na matematick´ ych funkc´ıch, program definuje funkci a v´ ysledkem je funkˇcn´ı hodnota. Modelem lambda kalkul a kostrukc´ı v´ yraz. V´ yrazy – ˇc´ıst´e a s vedlejˇs´ım efektem, ty mˇen´ı stavovov´ y prostor Vlastnosti ˇ c´ıst´ ych v´ yraz˚ u – hodnata nez´avis´ı na poˇrad´ı vyhodnocov´an´ı, lze tedy vyhodnocovat paralelnˇe, Nahrazen´ı podv´ yrazu jeho hodnotou je nez´avisl´e na v´ yrazu, ve kter´em je uskuteˇcnˇeno, funkce nemˇen´ı stavov´ y prostor. Z´ akladn´ı vlastnost Lispu – vˇse je seznamem. Funkce i data jsou symbolick´ ymi v´ yrazy Charakteristick´ e vlastnosti OOP Z´akladn´ı vlastnosti – Zapouzdˇrenost, dˇediˇcnost, polymofismus. Teorie viz ppa2. Z´ akladn´ı jazykov´ e konstrukce jazyk˚ u – Java Vlastnosti: • Vˇsechna data (krom primitivn´ıch typ˚ u) jsou objekty • Vˇsechny objekty jsou dynamick´e • Pouze jednoduch´a dˇediˇcnost • Vˇsechny metody jsou dynamick´e • Funguje garbage colector, takˇze nepotˇrebujem destruktory • Pˇretˇeˇzov´an´ı – mus´ı se liˇsit parametry • M´a rozhran´ı – implements Statick´ e metody – mohou volat pouze jin´e statick´e metody, nemaj´ı odkaz this (vlastn´ı instance) a mohou zpˇr´ıstupˇ novat pouze statick´a data Vnoˇ ren´ e tˇ r´ıdy – jsou definov´any uvnitˇr jin´e tˇr´ıdy, maj´ı pˇr´ıstup k obaluj´ıc´ı tˇr´ıdˇe (obr´acenˇe neplat´ı) Dˇ ediˇ cnost – pouze jednoduch´e, u metod nelze zeslabit pˇr´ıstupov´a pr´ava k metod´am, kl´ıˇcov´e slovo extends Abstraktn´ı tˇ r´ıdy – nelze vytv´aˇret jejich instance, definuj´ı pouze rozhran´ı a data pro podtˇr´ıdy Final – od tˇr´ıdy nelze dˇedit, metodu nelze pˇrekr´ yt, abstraktn´ı nem˚ uˇze b´ yt final C++ Vlastnosti: • Data nejsou obecnˇe objekty – class, sctruct, union • Objekty jsou statick´e, dynamick´e se oznaˇcuj´ı slovem virtual • V´ıcen´asobn´a dˇediˇcnost • Metody jsou statick´e, dynamick´e se oznaˇcuj´ı slovem virtual • Objekty se sami nezniˇc´ı – destruktory • Nem´a nestatick´e vnoˇren´e tˇr´ıdy 18
• Nem´a rozhran´ı ypoˇcty • Nem´a podporu pro paraleln´ı v´ • Jako jedin´ y jazyk m´a moˇznost pˇretˇeˇzov´an´ı oper´ator˚ u Objektov´ y Pascal Vlastnosti: • Data nejsou obecnˇe objekty – object, class • Objekty jsou statick´e, dynamick´e se oznaˇcuj´ı slovem virtual • Jednoduch´a dˇediˇcnost • Metody jsou statick´e, dynamick´e se oznaˇcuj´ı slovem virtual • Objekty se sami nezniˇc´ı – destruktory • M´a rozhran´ı – interface • Nem´a generick´e typy, statick´e promˇenn´e, ale m´a variantn´ı typ – variant asobnou. Dˇ ediˇ cnost – formy a probl´ emy Dˇediˇcnost m´ame jednoduchou a v´ıcen´ U jednoduch´e v podstatˇe ˇz´adn´e probl´emy nem´ame, jedinˇe, ˇze bychom potˇrebovali dˇedit od v´ıce tˇr´ıd, ale to se d´a vyˇreˇsit rozhran´ım nebo v pˇr´ıpadˇe Javy dˇedˇen´ım ve vnitˇrn´ı tˇr´ıdˇe. U v´ıcen´asobn´e se n´am m˚ uˇzou potkat stejn´ y identifik´atory, metody a pak mus´ıme urˇcit, kter´ y vlastnˇe chceme dˇedit apod. Polymorfismus v programovac´ıch jazyc´ıch Modul´ arn´ı struktura a separ´ atn´ı pˇ reklad programov´ ych jednotek Nejprve se prov´ad´ı anal´ yza a pot´e synt´ eza. U pˇrekladaˇce i interpreta se to lis´ı. Pˇ rekladaˇ c / kompiler Anal´ yza – Lexik´aln´ı anal´ yza, syntaktick´a anal´ yza, s´emantick´a anal´ yza Synt´ eza – Generov´an´ı vnitˇrn´ıho jazyka, optimalizace, generov´an´ı c´ılov´eho k´odu Interpret Anal´ yza – Lexik´aln´ı anal´ yza, syntaktick´a + s´emantick´a Synt´ eza – S´emantick´e zpracov´an´ı, interpretace Lexik´ aln´ı anal´ yza • Zak´odov´an´ı lexik´aln´ıch element˚ u do ˇc´ıseln´e podoby • Vynech´an´ı koment´aˇr˚ u • Lexik´aln´ı anal´ yza se popisuje koneˇcn´ ym automatem – gramatikou Syntaktick´ y analyz´ ator • Struktura je zachycena jako posloupnost gramatick´ ych pravidel • Provede se u ´prava zdrojov´eho k´odu tak, aby se snadno d´ale zpracov´avala – prefixov´a nebo postfixov´a syntaxe apod. • Nakonec se provede optimalizace ´odu Zpracov´ an´ı vyj´ımeˇ cn´ ych situac´ı Delphi, Java i C++ osetrovani vyjimek maji Vyj´ımky – vestavˇ en´ e, uˇ zivatelsk´ e. Vyjimky se pos´ılaj´ı, pokud pro nˇe nen´ı definov´ana akce v dan´e metodˇe, v´ yˇse (toho, kdo tu metodu volal). Vyj´ımka se pos´ıl´a tak dlouho, dokud ji nˇekdo nezachyt´ı a neoˇsetˇr´ı. Posledn´ım krokem je syst´em, kter´ y pˇr´ıpadnˇe program ukonˇc´ı
19
C++ – Try, catch, throw – V´ yjimky jsou vyvol´any pouze explicitnˇe pˇr´ıkazem throw. Vˇsechny vyj´ımky jsou pouze uˇzivatelsky definovan´e, hadrwarov´e v´ yjimky nem´a. Java – Try, catch, throw, finally, throws – Vyj´ımky jsou jak vestavˇen´e, kter´e nelze nijak zpracov´avat, tak i uˇzivatelsk´e. Typy – Error (chyby v JVM), Exception (uˇzivatelsk´e), IOException (I/O), RuntimeException – bˇehov´e chyby (ˇsah´an´ı mimo pamˇet apod.) avislost a deadProbl´ emy paraleln´ıho zpracov´ an´ı Probl´emy jsou dva z´akladn´ı – rychlostn´ı z´ lock ˇ sen´ı – semafor, monitor Reˇ Programov´ e prostˇ redky pro paraleln´ı v´ ypoˇ cty Z´akladn´ı prostˇredky jsou vl´akna (Delphi, C++ i Java) Java obsahuje monitory, kter´e dovoluj´ı pracovat s objektem pouze jednomu vl´aknu, ostatn´ı si musej´ı poˇckat. D´ale obsahuje tvz. synchonized metody, kter´e uzamkou objekt, pokud jsou zavol´any. Klasick´ e v´ yrazov´ e prostˇ redky procedur´ aln´ıch jazyk˚ u: Typov´ y syst´ em Typov´a kontrola m˚ uˇze b´ yt statick´ a a dynamick´ a. Statick´a se kontroluje pˇri pˇrekladu, dynamick´a za bˇehu (nelze pˇri pˇrekladu urˇcit typ). Programovac´ı jazyk m´a siln´ y typov´ y syst´ em, pokud dok´aˇze odhalit vˇsechny chyby typ˚ u. Java m´a t´emˇsˇr siln´ y typov´ y, osatn´ı ne. Kompatibilita – jmenn´a a struktur´aln´ı. Jmenn´a kompatibilita je v pˇr´ıpadˇe, jsou obˇe promˇenn´e definov´any stejn´ ym typem. Struktur´aln´ı je v pˇr´ıpadˇe, ˇze maj´ı obˇe promˇenn´e stejnou strukturu nez´avisle na deklaraci jejich typu. Vˇetˇsina m´a jmenou (u c´eˇcka m´a struktur´aln´ı pouze z´aznamy) Rozsah platnosti – urˇcuje ˇc´ast k´odu, kde je promˇenn´a viditeln´a. M´ame statick´ y a dynamick´ y. Statick´ y rozsah je urˇcen zdrojov´ ym k´odem. Dynamick´ y rozsah je urˇcen posloupnost´ı vol´an´ı funkc´ı nebo ˇc´ast´ı k´odu. Rozsah existence – ˇcasov´e obdob´ı, kdy je promˇenn´a definov´ana Typy – integer, string, boolean, array, asociativn´ı pole, record, set, pointer ... Pˇ r´ıkazy V´ yrazy – aritmetick´ e, logick´ e Klasicky ˇreˇs´ıme takov´e probl´emy jako – precedence oper´ator˚ u, asociativita, arita, poˇrad´ı vyhodnocen´ı, pˇretˇeˇzov´an´ı operand˚ u a dalˇs´ı. Napˇr. u C lze zapsat if (x=y), aˇckoliv x je aritmetick´ y v´ yraz. U Javy a Pascalu lze do podm´ınky zapsat pouze logick´ y v´ yraz Vˇ etven´ı Pascal – case variable of ... 1: pˇrizaz ... end. Java, C – swith (variable) ... case 1: pˇr´ıkaz ... end Cykly Pascal, Java, C – while (podm´ınka) ... Pascal – repeat ... while (podm´ınka), Java, C – do ... while (podm´ınka) Java, C – for(a,b,c) ..., Pascal – for a:=x to y do ... Skoky C, Pascal maj´ı, Java nem´a Podprogramy Pascal – function, procedure C, Java – function Struktura programu
20
