Prvy kirchoffov zakon popisuje zakon zachovania elektrickeho naboja. Algebraicky sucet prudov v uzle je rovny 0 => sucet prudov vstupujucich do uzla sa rovna suctu prudov z uzla vystupujucich.
Druhy KZ formuluje zakon zachovania elektrickej energie pre EO. Sucet ubytku napatia na spotrebicoch sa v uzavretej casti obvodu (slucke) rovna suctu elektromotorickych napatia zdroja v tejto casti obvodu => Algebraicky sucet napati v smycke je rovny 0.
Tuesday, June 28, 2011
HW: Prechodove deje
Prechodovy dej je dej, ktory nastave pri prechode z jedneho ustaleneho stavu do druheho. Pricinou su nahle zmeny v obvode.
Prechodovy dej prveho radu sa popisuju na obvodoch RL a RC.
Na RL obvode zacne po pripojenie prechadzat prud a na cievke sa zacne tvorit magneticke pole. To spociatku nema energiu, ale rychlo rastie a na cievke sa zacne indukovat napatie. Toto napatie je spociatku rovnako velke, ako napatie zdroja a na rezistore je rovno 0. Postupne sa napatie na cievke znizi a na rezistore sa bude zvysovat.
Na RC obvode po pripojeni bude prechadzat bude prechadzat vysoky prud, ktory bude obmedzeny iba rezistorom (I = U/R). Takze kondenzator sa najprv bude chovat ako skrat. Postupne sa zacne nabijat, tym vacsie bude jeho napatie a tym nizsi prud v obvode.
Prechodove deje 2 radu vznikaju na RLC obvodoch a riesia sa metodami smyckovych napati a prudov.
Prechodovy dej prveho radu sa popisuju na obvodoch RL a RC.
Na RL obvode zacne po pripojenie prechadzat prud a na cievke sa zacne tvorit magneticke pole. To spociatku nema energiu, ale rychlo rastie a na cievke sa zacne indukovat napatie. Toto napatie je spociatku rovnako velke, ako napatie zdroja a na rezistore je rovno 0. Postupne sa napatie na cievke znizi a na rezistore sa bude zvysovat.
Na RC obvode po pripojeni bude prechadzat bude prechadzat vysoky prud, ktory bude obmedzeny iba rezistorom (I = U/R). Takze kondenzator sa najprv bude chovat ako skrat. Postupne sa zacne nabijat, tym vacsie bude jeho napatie a tym nizsi prud v obvode.
Prechodove deje 2 radu vznikaju na RLC obvodoch a riesia sa metodami smyckovych napati a prudov.
HW: Impulzna a prechodova charakteristika
Naprv jednotkovy skok.
1(t) =
1(t) =
- 0 t < 0
- 1 t > 0
graf uz je snad lahky :). Ak pripojim zdroj napatia o 1V => L{1(t)} = 1/p. Prechodova charakteristika je odpovedou dynamickeho systemu na jednotkovy skok a jej analytickym vyjadrenim je h(t) - prechodova funkcia.
La Placeova transformacia je uzitocna v tom, ze prevadza obraz fcie realnej premennej na funkcie komplexnej premennej.
Impulzna charakteristika je odpovedou na jednotkovy (diracov) impulz pri nulovych pociatocnych podmienkach. Integral diracovho impulzu od -nekonecna do +nekonecna je 1 a je vzdy 0, okrem miesta vzniku.
delta(t) =
- +nekonecno t = 0
- 0 t <> 0
HW: Dioda
Dioda je polovodicova suciastka, ktora ma dva pracovne vyvody, anodu a katodu. Zakladnou funkciou diody je, ze dovoluje tok prudu od anody ku katode. Naopak prud vacsinou netecie.
Ak je na katode kladne napatie a na anode zaporne, tak prud netecie a dioda je zavreta. Takyto tok nazyvame zavernym a pokial je prilis velky, tak diodu prerazi, ci ju moze znicit.
Ak je na katode zaporne napatie a na anode kladne, tak prud tecie. Prud zacina tiect az po prekonani PN prechodu a pokial je napatie prilis velke, tak nam dioda zhori.
Zvlastnym pripadom je Zenerova dioda, ktora je konstruovana tak, ze v zavernom smere dochadza k malemu nedestruktivnemu (zenerovmu) prierazu a vdaka tomu moze fungovat, ako stabilizator napatia.
Prud tecie z anody na katodu!
Idealna dioda ma nulove prahove napatie (teda napatie, ktore otvori diodu), nulovy odpor a nekonecny prud a maximalne zaverne napatie. Samozrejme, nulove zaverne napatie.
Ak je na katode kladne napatie a na anode zaporne, tak prud netecie a dioda je zavreta. Takyto tok nazyvame zavernym a pokial je prilis velky, tak diodu prerazi, ci ju moze znicit.
Ak je na katode zaporne napatie a na anode kladne, tak prud tecie. Prud zacina tiect az po prekonani PN prechodu a pokial je napatie prilis velke, tak nam dioda zhori.
Zvlastnym pripadom je Zenerova dioda, ktora je konstruovana tak, ze v zavernom smere dochadza k malemu nedestruktivnemu (zenerovmu) prierazu a vdaka tomu moze fungovat, ako stabilizator napatia.Prud tecie z anody na katodu!
Idealna dioda ma nulove prahove napatie (teda napatie, ktore otvori diodu), nulovy odpor a nekonecny prud a maximalne zaverne napatie. Samozrejme, nulove zaverne napatie.
HW: Kondenzator
Casto ho volame kapacitor. Kapacitorom je myslena idealna suciastka, ktorej jedinou vlastnostou je kapacita. Z fyzikalneho hladiska je kondenzatorom akekolvek vodive teleso, ktore je obklopene inym vodivym telesom, pricom obe telesa su vzajomne izolovane. Sluzi k uchovaniu elektrickeho naboja a tym k uchovanie potencialnej elektrickej energie.
Kondezator si predstavme ako dve vodive dosky, ktore su oddelene dielektrikom. Dielektrikum je nevodic :) a dve vodive dosky su vlastne elektrody. Na kazdu dosku sa privadzaju elektricke naboje opacnej polarity, ktore sa pritahuju elektrickou silou (nie som isty, ze toto je spravny pojem). No, ale medzi doskami je dielektrikum, ktore nedovoli, aby sa castice s nabojom dostaly do kontaktu a vybili sa.
Takze kapacitor zapojme do obvodu jednosmerneho napatia. Kapacitor sa zacne nabijat, na doskach sa zacne hromadit elektricky naboj, az do chvile, kedy sa vyrovna potencial - na oboch doskach je rovnake napatie. Obvodom v tejto chvili prud neprechadza. Ale, ked sa dosky kondenzatoru prepoja, tak sa elektricky naboj odvedie a dosky sa vybiju. V takomto obvode musime vyuzivat vybijacieho prudu, pretoze kondezator v obvode s jednosmernym zdrojom napatia je vlastne prerusenie obvodu.
V obvode striedaveho prudu je situacia trochu vtipnejsia, pretoze kondenzator sa nabija a vybija a nabija a vybija .... atd. To ma za nasledok fazovy posun (+ PI/2), kedy prud predbehne napatie. Takto sa da menit napriklad kmitocet.
Tym, ze sa kondenzator vybije, tak vznikne vybijaci prud, ktory moze dosahovat velkych hodnot.
Kapacitor sa nabija az na svoje maximum, ktore je rovne velkosti napatia na zdroji.
Vyuzitie podla wiki:
Kondezator si predstavme ako dve vodive dosky, ktore su oddelene dielektrikom. Dielektrikum je nevodic :) a dve vodive dosky su vlastne elektrody. Na kazdu dosku sa privadzaju elektricke naboje opacnej polarity, ktore sa pritahuju elektrickou silou (nie som isty, ze toto je spravny pojem). No, ale medzi doskami je dielektrikum, ktore nedovoli, aby sa castice s nabojom dostaly do kontaktu a vybili sa.
Takze kapacitor zapojme do obvodu jednosmerneho napatia. Kapacitor sa zacne nabijat, na doskach sa zacne hromadit elektricky naboj, az do chvile, kedy sa vyrovna potencial - na oboch doskach je rovnake napatie. Obvodom v tejto chvili prud neprechadza. Ale, ked sa dosky kondenzatoru prepoja, tak sa elektricky naboj odvedie a dosky sa vybiju. V takomto obvode musime vyuzivat vybijacieho prudu, pretoze kondezator v obvode s jednosmernym zdrojom napatia je vlastne prerusenie obvodu.
V obvode striedaveho prudu je situacia trochu vtipnejsia, pretoze kondenzator sa nabija a vybija a nabija a vybija .... atd. To ma za nasledok fazovy posun (+ PI/2), kedy prud predbehne napatie. Takto sa da menit napriklad kmitocet.
Tym, ze sa kondenzator vybije, tak vznikne vybijaci prud, ktory moze dosahovat velkych hodnot.
Vyuzitie podla wiki:
- Fotografický blesk – nahromaděná elektrická energie v kondenzátoru se v krátkém časovém okamžiku vybije a způsobí silný světelný záblesk.
- Stabilizační prvek v elektrických obvodech – paralelním zapojením do elektrického obvodu lze dosáhnout vyhlazení napěťových špiček, a tím rovnoměrnějšího průběhu elektrického proudu.
- Odstranění stejnosměrné složky elektrického proudu – větví s kondenzátorem nemůže projít stejnosměrný elektrický proud, ale střídavý proud ano.
- Odrušovací kondenzátor je nedílnou součástí všech elektrospotřebičů. Používá se samostatně nebo v kombinaci s tlumivkami. Omezuje elektromagnetické rušení vzniklé spínáním nebo rozpojováním elektrického obvodu pod napětím.
- Ladicí součástka v přijímači – změnou kapacity v oscilačním obvodu přijímače se vlastní frekvence obvodu vyrovná vnější frekvenci a dojde k rezonanci, tj. k zesílení přijímaného signálu.
- Počítačová paměť – paměť složená z velkého množství miniaturních kondenzátorů je schopna uchovat informaci ve formě 0 a 1 (0 = není náboj, 1 = je náboj).
- Defibrilátor – přístroj používaný v lékařství k provádění elektrických šoků při zástavě srdce, kdy velké množství náboje projde během krátké doby přes srdeční sval a může tak obnovit srdeční činnost.
- Časovače – většina generátorů střídavého signálu využívá kondenzátory jako součástky, jejichž střídavé nabíjení a vybíjení určuje periodu kmitů.
HW: Bipolarne tranzistory
Bipolarny tranzistor je aktivna polovodicova suciastka. Ma tri susedne odlisne dotovane oblasti, ktore su oddelene dvoma P-N prechodmi a je tak schopna zosilovat elektricke signaly. Tranzistory rozdelujeme na NPN a PNP. My sa budeme zaoberat NPN tranzistormi. Cinnost tranzistoru PNP je analogicka, len s opacnymi polaritami napatia a zamenenym typom nosicov.
Jednotlive oblasti tranzistora sa nazyvaju kolektor, emitor a baza a su rozne dotovane.
Vpravo je schematicka znacka NPN tranzistoru a vlavo PNP tranzistoru.
Cely jav je zalozeny na prechode PN, ktory sme sa ucili na strednej skole, ale nezaskodi si to trochu pripomenut :). Jednotlive oblasti su rozne dotovane. Emitor je silne dotovany, baza ma strednu dotaciu a najmensia koncentracia primesi je v kolektore.
Lavy NP prechod je polovany v priepustnom smere voci strednej casti a pravy PN prechod je polovany tiez voci strednej casti, ale v zavernom smere. Z emitora do baze (zlava doprava), tak majoritne nosice naboje, elektrony, prechadzaju tymto prechodom. Tak sa v blizkosti tohto prechodu v bazi vytvara zvyseny vyskyt elektronov a smerom doprava (ku kolektoru) sa znizuje. Zrekombinuje len mala cast elektronov, pretoze baza je velmi tenka a tak sa elektrony vo vacsej miere nachadzaju aj pri prechode do kolektoru. Ten je v zavernom smere, ale len pre diery, ktore sa nachadzaju v bazi. A tak, elektrony z emitoru, pritahovane kladnym nabojom v kolektore, prechadzaju do kolektoru. Takze uz mame cast NP - PN == NPN :). Takymto pretekanim elektronov je zabezpeceny vznik prudu.
Jednotlive oblasti tranzistora sa nazyvaju kolektor, emitor a baza a su rozne dotovane.Vpravo je schematicka znacka NPN tranzistoru a vlavo PNP tranzistoru.
 |
| zlava: emitor, baza, kolektor |
Cely jav je zalozeny na prechode PN, ktory sme sa ucili na strednej skole, ale nezaskodi si to trochu pripomenut :). Jednotlive oblasti su rozne dotovane. Emitor je silne dotovany, baza ma strednu dotaciu a najmensia koncentracia primesi je v kolektore.
Lavy NP prechod je polovany v priepustnom smere voci strednej casti a pravy PN prechod je polovany tiez voci strednej casti, ale v zavernom smere. Z emitora do baze (zlava doprava), tak majoritne nosice naboje, elektrony, prechadzaju tymto prechodom. Tak sa v blizkosti tohto prechodu v bazi vytvara zvyseny vyskyt elektronov a smerom doprava (ku kolektoru) sa znizuje. Zrekombinuje len mala cast elektronov, pretoze baza je velmi tenka a tak sa elektrony vo vacsej miere nachadzaju aj pri prechode do kolektoru. Ten je v zavernom smere, ale len pre diery, ktore sa nachadzaju v bazi. A tak, elektrony z emitoru, pritahovane kladnym nabojom v kolektore, prechadzaju do kolektoru. Takze uz mame cast NP - PN == NPN :). Takymto pretekanim elektronov je zabezpeceny vznik prudu.
HW: Urcenie pracovnej frekvencie obvodu a metastabilita
Ako casujeme klopny obvod? Musime sa drzat par zasad :)
- vstup musi byt stabilny pred aktivnou hodinovou hranou - Setup Time
- vstup musi zostat stabilny po aktivnej hodinovej hrane - Hold Time
- a musime pocitat s omeskanim klopneho obvodu - Clock-to-Q time
V zapojeni, su vsetky klopne obvody riadene rovnakou hodinovou frekvenciou. Vstupy kombinacnej logiky a vystupy musia byt stabilne pre kazdom takte a pred kazdym taktom (na vystupe).
V kombinacnej logike ale musime vediet identifikovat maximalnu kriticku cestu, co je najdlhsia cesta medzi ktorymkolvek z klopnych obvodov. Maximalna perioda je vlastne funkciou kriotickej cesty a musi byt vacsia, ako Clock-to-Q + najdlhsia cesta cez kombinacnu logiku + Setup.
Maximalnu frekvenciu spocitame ako 1/Tkrit, kde Tkrit je maximalne mozne zpozdeni obvodu - pri kritickej ceste.
Metastabilita je subeh hrany vstupu a aktivnej hrany hodinoveho signalu. Vystup nie je definovany, pretoze je v zakazanom pasme. Jednoduchsie povedane, prave pri aktivnej hrane hodin sa meni hodnota vstupu tak, ze nie je mozne povedat, ci je 1 alebo 0. Metastabilitu nevieme uplne odstranit, pretoze vacsinou ju mozu zapricinovat vstupy, ktore nie su synchronizovane s hodinovym signalom. Riesenim je ich vplyv obmedzit tak, ze ich skusime zosynchronizovat nejakym klopnym obvodom, ktory dame hned na zaciatok.
HW: Programovatelne logicke struktury
Pri navrhoch logickeho systemu je obcas - dost casto :), mat k dispozicii taky system, ktory sa u zakaznika da preprogramovat, zmenit. V takychto pripadoch mozeme pouzit relativne univerzalnu strukturu, ktora je postavena na bazi nejakeho mikroprocesoru, alebo nejakeho mikroprogramovatelneho obvodu. Pozadovanu funkciu obvodu dosiahneme vhodnym obsahom pamati. Neskorsia modifikacia je potom jednoduchsia.
Ak oddelime personifikaciu obvodov od ich realizacie, tak dostaneme cioym ktore nazyvame FPLA, PLD a PAL. U tychto obvodov je ich vnutorna konfiguracia definovana mimo vyrobny zavod a pri vyrobe spojovacich bodov sa pouzivaju tavne poistky, CMOS tranzistory a bistabilne klopne obvody. Tavne poistky su programovatelne iba jednorazovo, zatial co CMOS tranz. je mozne vymazat ultrafialovym svetlom a znovu naprogramovat a bistabilne klopne obvody - teda obvody, ktore stracaju svoju konfiguraciu po vypnuti je mozne preprogramovat tak, ze zmenime obsah zavadzacej pamate - ROM.
PLA je programovatelne pole logickych jednotiek, kde kazdu logicku jednotku je mozne naprogramovat.
FPGA obsahuju komplexne logicke bloky, ktore su prepojene prepojovacim systemom. Je tu moznost kofiguracie uzivatelom a to nielen fcie kazdeho bloku, ale aj prepojenia.
Ak oddelime personifikaciu obvodov od ich realizacie, tak dostaneme cioym ktore nazyvame FPLA, PLD a PAL. U tychto obvodov je ich vnutorna konfiguracia definovana mimo vyrobny zavod a pri vyrobe spojovacich bodov sa pouzivaju tavne poistky, CMOS tranzistory a bistabilne klopne obvody. Tavne poistky su programovatelne iba jednorazovo, zatial co CMOS tranz. je mozne vymazat ultrafialovym svetlom a znovu naprogramovat a bistabilne klopne obvody - teda obvody, ktore stracaju svoju konfiguraciu po vypnuti je mozne preprogramovat tak, ze zmenime obsah zavadzacej pamate - ROM.
PLA je programovatelne pole logickych jednotiek, kde kazdu logicku jednotku je mozne naprogramovat.
FPGA obsahuju komplexne logicke bloky, ktore su prepojene prepojovacim systemom. Je tu moznost kofiguracie uzivatelom a to nielen fcie kazdeho bloku, ale aj prepojenia.
Monday, June 27, 2011
SW: Automaty
DFA: (Q, T, prechodova fcia, pociatocny stav, konecny stav), kde Q je mnozina stavov a T je vst. abeceda.
- prijima regularny jazyk, generovany regularnou gramatikou
- prijima regularny jazyk, generovany regularnou gramatikou
SW: Gramatiky
N - konecna mnozina neterminalov
T - konecna mnozina terminalov
P - konecna mnozina v tvare A->alfa, kde A je z N a alfa je N zjednotenie T
S - startovaci symbol
Bezkontextova
G = (N,T,P,S)
Bezkontextova gramatika sa nezaobera kontextom, ale pouzivame ju k analyze programovacich jazykov.
Regularna gramatika
je bezkontextovou gramatikou, v ktorej kazde pravidlo ma tvar A -> aB alebo A -> a, kde A,B su neterminaly a a,b su terminaly. Vynimkou je pravidlo S -> epsilon, ak sa S neobjavi na pravej strane ziadneho ineho pravidla.
LL1
Bezkontextova gramatika je LL1, ak pre kazdu dvojicu pravidiel A-> alfa | beta plati, ze
T - konecna mnozina terminalov
P - konecna mnozina v tvare A->alfa, kde A je z N a alfa je N zjednotenie T
S - startovaci symbol
Bezkontextova
G = (N,T,P,S)
Bezkontextova gramatika sa nezaobera kontextom, ale pouzivame ju k analyze programovacich jazykov.
Regularna gramatika
je bezkontextovou gramatikou, v ktorej kazde pravidlo ma tvar A -> aB alebo A -> a, kde A,B su neterminaly a a,b su terminaly. Vynimkou je pravidlo S -> epsilon, ak sa S neobjavi na pravej strane ziadneho ineho pravidla.
LL1
Bezkontextova gramatika je LL1, ak pre kazdu dvojicu pravidiel A-> alfa | beta plati, ze
- FIRST(alfa) zjednotenie FIRST(beta) je prazdna mnozina - inak povedane, mame len jednu moznost, ako pokracovat
- to iste pravidlo zavedieme, ak niektora z FOLLOW obsahuje epsilon. FOLLOW zjednotenie FIRST, kde follow obsahuje epsilon a first nie je prazdna mnozina. - jedna sa zase o to, aby sposob pokracovania bol jednoznacne deterministicky.
dalej mame este atributovu gramatiku, co je vlastne LL(1) gramatika a prechodovu gramatiku, co je vystup LL(1) gramatiky
Sunday, June 26, 2011
SW: Procedury a funkcie, blokova struktura a aktivacne zaznamy
Asi je jasne, ze rec bude o podprogramoch. Podporgram moze mat formu procedury, alebo funkcie. Procedura realizuje abstraktni prikaz, pricom funkcia vedie na abstraktnu operaciu, ktora vedie na hodnotu urciteho typu. To znamena, ze funkcia nam nieco vrati. Podprogramy mozu byt jednoduche alebo rekurzivne a otvorene alebo uzavrete. Otvorene su napriklad inline podprogramy v C++, ktorych volanie znamena kopirovanie kodu do volajcieho programu. Uzavrete programy maju svoj vlastny kodovy segment.
Kazdy podprogram ma referencne prostredie, ktore tvori mnozina mien, ktore sa v podprograme daju pouzit pre oznacenie datovych objektov a inych prvkov
Zasobniky pouzite pri volani podprogramu mozu byt roznych typov
Kazdy podprogram ma referencne prostredie, ktore tvori mnozina mien, ktore sa v podprograme daju pouzit pre oznacenie datovych objektov a inych prvkov
- lokalne
- nelokalne
- staticke
- dynamicke - v niektorych jazykoch sa meno najprv hlada lokalne, ak nie je najdene, tak sa pokracuje po call stacku vyssie.
Programy maju aj svoju blokovu struktru, ktora sluzi k uvedeniu prikazov a deklaracii lokalnych datovych objektov. Blokova struktura moze byt tvorena
- prikazom
- telom podprogramu
A deli sa na deklaracnu a prikazovu cast.
Bloky mozu byt do seba vnorovane ako prikazy alebo ako podprogramy. Vznika tak hierarchicka blokova struktura. Existuju pravidla vymedzujuce platnost deklaracii
- lokalne referencne prostredie, ktore je dane lokalnymi deklaraciami
- nelokalne referencne prostredie, ktore je odvodene od ref. prostr. do kotreho je blok vnoreny
Lokalna deklaracia mena zatieni nelokalnu deklaraciu mena. Blok, v ktorom je deklaracia lokalna sa nazyva deklaracnou oblastou a je mozne ju pouzit v jej rozsahu platnosti, cim moze byt cela deklaracna oblast, alebo len ta cast, ktora je vymedzena miestom deklaracie. Priamym menom je mozne deklaraciu oznacit v jej rozsahu priamej viditelnosti.
Podprogramy maju svoje
- vstupne parametre
- vystupne parametre
- vstupno-vystupne parametre
Parametre sa predavaju bud hodnotou, odkazom, alebo menom. Predavanie menom je uz dnes obsolete a predavanie odkazom je vlastne predavanie ukazatelom - ktory moze/nemusi byt skryty. Parametre predavane hodnotou oznacuju vlastne kopirovanie, kedy na vstupe paramter nahradime hodnotou a na vystupe vysledkom.
Podprogramy mozme pretazovat a podprogramy mozu byt genericke - to znamena, ze mozme napisat kod pre vopred neurceny datovy typ, co je dobre pre usporu kodu a pre niektore standardne struktury.
Ked sa podprogram prelozi, tak vznikne kodovy segment podprogramu. Z hlavneho programu volame vlastne zaciatok kodoveho segmentu podprogramu, ktory sa vykona. Navratova adresa do hlavneho programu a vsetky dolezite data (napr. hodnoty premennych) su ulozene na systemovy zasobnik. Otazka je, ze ako pridelit pamat - a to tak isto, ako sme sa ucili pri virtualnej pamati - staticky/dynamicky, teda pri preklade alebo run time. Lokalne datove objekty je mozne alokovat staticky a pri kazdom volani podprogramu sa do pamati dynamicky ulozia ich kopie.
V pripade dynamickej alokacie pamate pouzivame aktivacne zaznamy. Kazdy aktivacny zaznam je urceny jednemu volaniu/aktivacii podprogramu. Je to usek pamate, ktory obsahuje skutocne parametre, navratovu adresu, lokalne premenne a konstanty a pripadne dalsie systemove informacie. Aktivacny zaznam sa vytvori na vrchole zasobnika na zaciatku aktivacie podprogramu a po jeho dokonceni sa zo zasobniku odstrani. Zasobnik obsahuje aktivacny zaznam vsetkych rozpracovanych podprogramov, ale priamo pristupny je len ten na vrchole.
Zasobniky pouzite pri volani podprogramu mozu byt roznych typov
- zasobnik s dynamickym spojom
- ma pridany pointer, ktory umoznuje jednoduchsiu adresaciu premennych a lokalnych parametrov. Takyto zasobnik je dolezity, pokial jazyk podporuje dynamicke typy, pretoze ich velkost nie je znama pri preklade.
- zasobnik so statickym spojom
- sa pouziva pre pristup k premennym, ktore su umiestnene v aktivacnych zaznamoch staticky nadradenych programov. Je realizovany pomocou spojoveho zoznamu.
SW: Algoritmy nahrady stranok
Algoritmus pre nahradu stranok je urceny Replacement Policy, ktora mimo ineho urcuje, kolko ramcov stranok v HP bude alokovane pre kazdy proces (rezidentna velkost) a ci kandidati pre nahradu stranok budu iba stranky partriace procesu, alebo vsetky stranky (aj mimo dany proces - rezidentny proces).
Rezidentna velkost moze byt fixna alebo variabilna, podla toho, ci proces dostane fixny pocet stranok v pamati, alebo nie. Rezidentny rozsah moze byt globalny a lokalny, podla toho ci ovplyvnuje dalsie procesy, alebo nie.
K nahrade stranok dochadza, ak vsetky ramce v HP su obsadene. Do pamate potrebujeme nahrat dalsiu stranku. A toto zabezpecime pomocou algoritmu nahrady stranok. Vacsina z nich pracuje na principe lokality.
Optimalny algoritmus
Optimalny algoritmus sa snazi nahradit stranku, ktora uz pouzivana nebude. Ak taka stranka neexistuje, tak nahradime stranku, ktora bude pouzivana za najdlhsiu dobu od tohto okamziku.
Not Recently Used
Kazdej stranke su priradene bity read a modify, ktore menime podla potreby. R bit je nastaveny na 1, ak ku stranke pristupujeme a M nastavujeme na 1, ak stranku modifikujeme. Bity su ulozene v tabulke stranok a ich modifikaciu sa stara HW. Vynulovane su pri spusteni (not R, not M). Bit R je nulovany periodicky, napriklad prerusenim casovaca. Podla toho vieme, ktore stranky boli pouzite nedavno: (R,M)
NRU nahradzuje od najnizsej kategorie.
Least Recently Used
Dobra aproximacia optimalneho algoritmu. Myslienka na prinicipe casovej lokality, a kstranky boli casto pouzivane v poslednej dobe, tak s velou pravdepodobnostou budu pouzite znovu. Pri vypadku nahradime stranku, ktora nebola pouzita po najdlhsiu dobu.
First In First Out
OS si udrzuje zoznam vsetkych stranok, ktore su v hlavnej pamati vo fronte. Takze tie na zaciatku budu najstarsie a tie na konci budu najmladsie. Pri vypadku stranky nahradzujeme prvu stranku. Tento pristup neuvazuje, ako casto sa ku stranke pristupuje.
Second Chance Algorithm
Jedna sa o FIFO s novou feature. Pridame bit R, ktore pocitaju, ako casto sa ku stranke pristupuje a periodicky sa nuluje. Zoznam prechadzame od zaciatku pri vypadku stranky. A R je 0 - stranka je stara a nepouzivana. Preto ju mozme nahradit. Ak R je 1, tak tento bit vynulujeme a stranku presunieme na koniec zoznamu.
The Clock Algorithm
SCA v cyklickej fronte v smere hodinovych ruciciek. Pri vypadku stranky zacneme hladat od stranky, na ktoru ukazuje rucicka. Ak R = 0, tak stranku nahradime, ak R = 1, tak bit opat vynulujeme a hladame dalej.
Aging Algorithm
NFU nezabuda a preto je tento alg. doplneny o princip starnutia. Obsah citaca je posunuty doprava o jeden bit pred pricitanim bitu R a nahradeny je ten, ktory ma najnizsiu hodnotu citaca.
Working Set Algorithm
Tentokrat trochu iny algoritmus. pre kazdy proces nadefinujeme aktualny virtualny cas a pracovnu mnozinu. Aktualny virtualny cas je mnozstvo casu CPU, ktore proces skutocne vyuzil a pracovna mnozina je mnozstvo stranok, ku ktorym proces pristupoval behom poslednych t jednotiek svojho aktualneho virtualneho casu. Okrem R referenced bit a M modified bit je v tabulke stranok este TLU - last used time. R a M bit upravujeme tak, ako pri NRU a definujeme vek aktualny virtualny cas - cas posledneho pouzitia. Prechadzame tabulku stranok a testujeme R bit.
Rezidentna velkost moze byt fixna alebo variabilna, podla toho, ci proces dostane fixny pocet stranok v pamati, alebo nie. Rezidentny rozsah moze byt globalny a lokalny, podla toho ci ovplyvnuje dalsie procesy, alebo nie.
K nahrade stranok dochadza, ak vsetky ramce v HP su obsadene. Do pamate potrebujeme nahrat dalsiu stranku. A toto zabezpecime pomocou algoritmu nahrady stranok. Vacsina z nich pracuje na principe lokality.
Optimalny algoritmus
Optimalny algoritmus sa snazi nahradit stranku, ktora uz pouzivana nebude. Ak taka stranka neexistuje, tak nahradime stranku, ktora bude pouzivana za najdlhsiu dobu od tohto okamziku.
- kazdej stranke sa priradi cislo indikujuce, kolko instrukcii sa musi vykonat, kym bude stranka zase volana
- nahradime stranku s najvyssim cislom
Tento algoritmus dosahuje najlepsich vysledkov, ale musime poznat buducnost. Sluzi pre porvnavanie s ostanymi algoritmami, az kym niekto nevynajde stroj casu.
Not Recently Used
Kazdej stranke su priradene bity read a modify, ktore menime podla potreby. R bit je nastaveny na 1, ak ku stranke pristupujeme a M nastavujeme na 1, ak stranku modifikujeme. Bity su ulozene v tabulke stranok a ich modifikaciu sa stara HW. Vynulovane su pri spusteni (not R, not M). Bit R je nulovany periodicky, napriklad prerusenim casovaca. Podla toho vieme, ktore stranky boli pouzite nedavno: (R,M)
- C0: 0,0 - stranka nebola dlho citana ani modifikovana
- C1: 0,1 - stranka nebola dlho citana, ale bolo na nu zapisovane
- C2: 1,0 - stranka bola nedavno citana, ale nebolo na jej miesto zapisovane
- C3: 1,1 - stranka bola prednedavnom citana aj modifikovana
NRU nahradzuje od najnizsej kategorie.
Least Recently Used
Dobra aproximacia optimalneho algoritmu. Myslienka na prinicipe casovej lokality, a kstranky boli casto pouzivane v poslednej dobe, tak s velou pravdepodobnostou budu pouzite znovu. Pri vypadku nahradime stranku, ktora nebola pouzita po najdlhsiu dobu.
First In First Out
OS si udrzuje zoznam vsetkych stranok, ktore su v hlavnej pamati vo fronte. Takze tie na zaciatku budu najstarsie a tie na konci budu najmladsie. Pri vypadku stranky nahradzujeme prvu stranku. Tento pristup neuvazuje, ako casto sa ku stranke pristupuje.
Second Chance Algorithm
Jedna sa o FIFO s novou feature. Pridame bit R, ktore pocitaju, ako casto sa ku stranke pristupuje a periodicky sa nuluje. Zoznam prechadzame od zaciatku pri vypadku stranky. A R je 0 - stranka je stara a nepouzivana. Preto ju mozme nahradit. Ak R je 1, tak tento bit vynulujeme a stranku presunieme na koniec zoznamu.
The Clock Algorithm
SCA v cyklickej fronte v smere hodinovych ruciciek. Pri vypadku stranky zacneme hladat od stranky, na ktoru ukazuje rucicka. Ak R = 0, tak stranku nahradime, ak R = 1, tak bit opat vynulujeme a hladame dalej.
Aging Algorithm
NFU nezabuda a preto je tento alg. doplneny o princip starnutia. Obsah citaca je posunuty doprava o jeden bit pred pricitanim bitu R a nahradeny je ten, ktory ma najnizsiu hodnotu citaca.
Working Set Algorithm
Tentokrat trochu iny algoritmus. pre kazdy proces nadefinujeme aktualny virtualny cas a pracovnu mnozinu. Aktualny virtualny cas je mnozstvo casu CPU, ktore proces skutocne vyuzil a pracovna mnozina je mnozstvo stranok, ku ktorym proces pristupoval behom poslednych t jednotiek svojho aktualneho virtualneho casu. Okrem R referenced bit a M modified bit je v tabulke stranok este TLU - last used time. R a M bit upravujeme tak, ako pri NRU a definujeme vek aktualny virtualny cas - cas posledneho pouzitia. Prechadzame tabulku stranok a testujeme R bit.
- ak R == 1, tak CVT = TLU a R = 0
- ak R == 0 && Age > t - nahradime stranku
- ak R == 0 && Age <= t - stranku s najvacsim Age si zapamatame (ak ich je viac, tak vyberame nahodne)
WS-Clock Algorithm
Toto je WS algoritmus v cyklickom poli.
SW: Strankovanie, segmentacia a kombinovane techniky spravy pamate
Jednoduche strankovanie, sa pouziva v strankovanej pamati. Hlavna pamat je v tomto pripade rozdelena na male useky rovnakej velkosti, ktore nazyvame ramce (spomente na APS). Program je zase rozdeleny na male useky rovnakej velkosti - stranky. Velkost stranky a ramca je rovnaka a programy su nahravane do ramcov hlavnej pamate. OS si musi pamatat ramce pridelene jednotlivym procesom. To je zariadene pomocou page table (http://mycvut.blogspot.com/2011/06/hw-virtualna-pamat.html) a musi si pamatat aj volne ramce v pamati.
Virtualnu pamat pouzivame kvoli miestu v pamati, ktore je limitovane. Pomocou virtualnej pamate je proces rozdeleny na mensie kusky a do pamate vkladame len tie kusky, ktore su aktualne pouzivane. Zvysok procesu je ulozeny na disku.
Virtualna pamat je vacsinou kombinovana so strankovanim a to jednourovnovym alebo viacurovnovym. Proces potom pouziva virtualne adresy, ktore tvoria virtualny adresovy priestor virtualnej pamate. Tento priestor je rozdeleny na virtualne stranky. Korespondujuce useky vo fyzickej pamati su nazyvane ramce stranok a su rovnakej velkosti, ako stranky.
Virtualnyu adresu na fyzicku preklada memory management unit. Pri page fault MMU zposobi, aby CPU poziadalo o nahranie stranky do ramca pamate. OS najprv musi uvolnit ramec (casovy princip/princip lokality ?).
Ak by sme pouzivali len jednu tabulku stranok pre proces, tak by sme sa mohli dostat do problemov s jej velkostou a preto pouzivame viacurovnove strankovanie. Proces zvycajne pouziva len podmnozinu adries svojho virtualneho priestoru. V pamati staci mat len tie polozky tabulky stranok, ktore proces potrebuje pri preklade. Zvycajne sa pouziva delenie na 2 - 3 urovne, hoci teoreticky je tento pocet lubovolny (konecne cislo, pls :) ).
Teraz sme v situacii, kedy mame Top Level page table a potom stranky nizsej urovne. Virt. adresa, ktora dorazi obsahuje 3 polozky, super page table address, 2nd level page table address a offset. Tak sa dostaneme na 1 tabulku, z nej sa dostaneme na druhu, kde najdeme polozku a to prelozime na fyzicku adresu s offsetom, ktory len skopirujeme.
Page Table Entry obsahuje
Virtualnu pamat pouzivame kvoli miestu v pamati, ktore je limitovane. Pomocou virtualnej pamate je proces rozdeleny na mensie kusky a do pamate vkladame len tie kusky, ktore su aktualne pouzivane. Zvysok procesu je ulozeny na disku.
Virtualna pamat je vacsinou kombinovana so strankovanim a to jednourovnovym alebo viacurovnovym. Proces potom pouziva virtualne adresy, ktore tvoria virtualny adresovy priestor virtualnej pamate. Tento priestor je rozdeleny na virtualne stranky. Korespondujuce useky vo fyzickej pamati su nazyvane ramce stranok a su rovnakej velkosti, ako stranky.
Virtualnyu adresu na fyzicku preklada memory management unit. Pri page fault MMU zposobi, aby CPU poziadalo o nahranie stranky do ramca pamate. OS najprv musi uvolnit ramec (casovy princip/princip lokality ?).
Ak by sme pouzivali len jednu tabulku stranok pre proces, tak by sme sa mohli dostat do problemov s jej velkostou a preto pouzivame viacurovnove strankovanie. Proces zvycajne pouziva len podmnozinu adries svojho virtualneho priestoru. V pamati staci mat len tie polozky tabulky stranok, ktore proces potrebuje pri preklade. Zvycajne sa pouziva delenie na 2 - 3 urovne, hoci teoreticky je tento pocet lubovolny (konecne cislo, pls :) ).
Teraz sme v situacii, kedy mame Top Level page table a potom stranky nizsej urovne. Virt. adresa, ktora dorazi obsahuje 3 polozky, super page table address, 2nd level page table address a offset. Tak sa dostaneme na 1 tabulku, z nej sa dostaneme na druhu, kde najdeme polozku a to prelozime na fyzicku adresu s offsetom, ktory len skopirujeme.
Page Table Entry obsahuje
- page frame number
- present/absent bit - {1 | 0} => {v RAM | mimo RAM}
- protection bit - su to 3 bity, reading, writing, executing
- modified bit - ked je obsah stranky modifikovany, tak je nastaveny na 1 . Ak je uvolnovany - obsah stranky sa musi ulozit na disk, ak je modified bit = 1
- referenced bit - zmeneny na 1, kedykolvek je k stranke pristupovane, pouziva sa algoritmami pre nahradu stranky.
- disabled bit - dolezity pre stranky, ktore su mapovane na registre I/O zar.
Popri tabulke stranok sa puziva este invertovana tabulka stranok, ktora sa pouzije, ak sa informacia nenajde v page table. V tejto tabulke je na i-tej pozicii ulozena informacia o virtualnej stranke, ktora je nahrana v ramci i.
Segmentace
- virtualny adresovy prostor moze byt rozdeleny na niekolko segmentov. Segment je linearna postupnost adries, s dynamickou dlzkou a s vlastnym stupnom ochrany. Adresa segmentu - logicka adresa - sa sklada z cisla segmentu a offsetu. Cislo segmentu adresuje segment jednoznacne a offset sa zase iba kopiruje. Segmentacia je obvykle viditelna uzivatelovi.
Segmentacia je pre programatora viditelna, narozdiel od strankovania, ktore je transparentne. Segmentacia je vhodna pre dynamicke struktury a modularitu. Strankovanie zase eliminuje externu fragmentaciu.
A ked toto vsetko dame dokopy, tak dostaneme segmentaciu so strankovanim. Virtualny adresovy priestor je rozdeleny na niekolko segmentov. Kazdy segment sa sklada z rovnako velkych stranok, ktore su rovnako velke, ako ramce v hlavnej pamati.
Takze, ak dorazi adresa, tak dorazi virtualna adresa so segment #, page # a offsetom. Segment # urci polozku v segment page table, ktory urci page table, v ktorej pomocou page # najdeme najdeme spravny riadok s fyzickou adresou a pomocou offsetu dokazeme adresovat riadok v hlavnej pamati (v ramci).
SW: Sprava pamati v jednoulohovych a viaculohovych systemoch
na cipe je umiestnena memory management unit, ktora preklada logicke adresy na fyzicke a zabezpecuje dalsie aktivity spravy pamati. jedna sa o hw cast
sw cast tvori memory manager, ako komponenta OS. memory manager udrzuje informacie o volnej a pridelenej pamati, prideluje a uvolnuje pamat, zaistuje swapping procesov.
poziadavku na spravu pamate su
sw cast tvori memory manager, ako komponenta OS. memory manager udrzuje informacie o volnej a pridelenej pamati, prideluje a uvolnuje pamat, zaistuje swapping procesov.
poziadavku na spravu pamate su
- premiestnenie
- pri kompilacii vacsinou nie je zname umiestnenie procesov vo fyzickej pamati a kazdy odkaz do pamate v programe musi byt prepocitany podla aktualneho umiestnenia procesu vo fyzickej pamati. v programe sa mozme dalej odkazovat na dalsie programy. Programy do pamate zavadzame roznymi metodami (loading) - musi mu prechadzat linking (nizsie)
- absolutne zavedenie - kazdy odkaz do pamate v programe obsahuje absolutnu fyzicku adresu. Program musi byt tym padom zavedeny vzdy do danej fyzickej adresy. Pri zostavovani programu musime urcit, kam bude program zavedeny.
- premiestnitelne zavedenie - kazdy odkaz do pamate v programe obsahuje relativnu adresu. informacia o pamatovych odkazoch je ulozena v relocation dictionary. Prepocitanie adries z relativnych na fyzicke sa vykona pri zavedeni programu do pamate.
- dynamicke (run-time) zavedenie - kazdy odkaz do pamate v programe obsahuje relativnu adresu. program je takto zavedeny do pamate. Prepocet sa vykona pri spracovani instrukcie.
- linking
- staticky - vytvori sa load module s relativnymi adresami, vztiahnutymi k zaciatku modulu
- dynamicky - to je pripad, ked load module obsahuje odkazy na dalsie programy
- load-time dynamic linking - odkazy na dalsie programy sa nahradia v okamihu zavedenie
- run-time dynamic linking - odkazy sa nahradia za behu - v okamihu vykonavania instrukcie
- ochrana - ochrana procesov pred neziadanymi pristupmi ostatnych procesov
- zdielanie - umoznenie pristupu k spolocnej pamati
- logicka organizacia - sprava adresovych priestorov (linearnych). SW sa obvykle ale sklada z viacerych modulov
- fyzicka organizacia - fyzicka pamat sa sklada z vicerych urovni, ktore treba spravovat
Zakladne techniky spravy pamate
- v jednoulohovom systeme musi kazdy proces obsahovat ovladace I/O zariadeni. V pamati je len jeden proces a zdiela pamat s jadrom OS.
- vo viaculohovom systeme je pamat rozdelena do
- fixnych oblasti
- dynamickych oblasti
- moze vyuzivat virtualnu pamat so strankovanim/segmentaciou a v navaznosti na to pouzivat jednoduche strankovanie/segmentaciu
pokial je pamat rozdeleny do fixnych oblasti, tak to znamena, ze pri starte systemu je rozdelena do fixnych, ale rozne velkych oblasti. Programy su potom nahravane do rovnako velkych, alebo vacsich oblasti. Tieto oblasti sa uz pocas behu OS nemenia. Takato implementacia je jednoducha a rezijne naklady su male. Kedze pamat je rozdelena na bloky, tak kazdy blok je zviazany s n-bitovym ochrannym klucom, ktory urcuje, ci dana uloha moze pristupit k bloku. Kazdy blok ma k dispozicii bazovy a limitny register, pri kazdom pohybe v pamati (baza+pohyb) je vysledok porovnany s limitnym registrom.
Pruserom je interna fragmentacia, kedze miesto nie je vyuzite na 100% a pocet aktivnych procesov je fixny. Implementacia je mozna pomocou oddelenych vstupnych front pre kazdu oblast, alebo pomocou jednej spolocnej fronty. V pripade roznych front dochadza k nerovnomernemu obsadeniu front.
Spolocna vstupna fronta vybera volnu oblast pomocou strategii
- Best Fit - snaha o najdenie najvacsieho programu, pre danu oblast. Takto su znevyhodnene male ulohy. Pouziva sa pocitadlo, kolkokrat bol proces predbehnuty a ziaden proces nebude predbehnuty viac, ako x-krat.
- First Fit - prva uloha, ktora sa vojde do prvej oblasti, tam bude najebana. Takto sa ale plytva miestom vacsich oblasti, pretoze aj mensi program moze byt umiestneny do velmi velkej oblasti.
Pokial sa pocet oblasti a ich velkosti mozu menit, tak sa jedna o dynamicke oblasti. Procesy vznikaju a zanikaju, oblasti sa menia a presuvaju sa medzi hlavnou pamatou a diskom. Interna fragmentacia je skoro nulova a vyuzitie pamate skoro nulove. Nevyhodou je externa fragmentacia.
V dynamickej pamati moze datovy segment pamati menit svoju velkost behom vypoctu a preto musime alokovat viac pamate, ako je na zaciatku potreba.
Informacie o volnej pamati je mozne udrzovat v
- bitovej mape - pomale. Pamat je rozdelena na alokacne jednotky. Kazda alokacna jendotka ma v bitovej mape korespondujuci bit. Volna alokacna jednotka - suvisly retazec 0.
- zretazenym zoznamom - jedna sa o zoznam volnych a pridelenych pamatovych segmentov, ktory je zoradeny podla adries segmentov. Je to vlastne zoznam segmentov v poradi, kde je vzdy oznaceny proces/diera, pociatocna adresa a dlzka tak, aby bola obsiahnuta cela pamat. Nova alokacia sa deje pomocou
- first fit
- next fit
- best fit
- worst fit
- quick fit - tu sa ale jedna o oddeleny zoznam procesov a dier a v tomto pripade dokonca o niekolkych oddelenych zoznamoch pre diery. kazdy zoznam obsahuje informacie o dierach s urcitym intervalom (takze su vlastne zaradene do zoznamu podla velkosti) a tak je mozne rychlo najst dieru. Najdenie susednych dier pre zlucenie do vacsej diery je casovo narocne.
Saturday, June 25, 2011
SW: Metody vzajomneho vylucenia procesov a vlakien
Zakaz prerusenia
- CPU je pridelovane postupne jednotlivym procesom za pomoci prerusenia od casovaca alebo ineho prerusenia
- proces zakaze vsetky prerusenia pred vstupom do kritickej sekcie a povoli ich az po opusteni kritickej sekcie
- technika je vhodna na kratky cas v ramci jadra
- ale nie je vhodna pre bezne ucely
- pretoze DI blokuje ostatnych uzivatelov
- vo viacprocesorovom CPU ma efekt iba na aktualnom CPU
- zpomali reakcie na prerusenie
- zle napisane programy zablokuju CPU
Aktivne cakanie / blokovanie
- iba jeden proces moze vstupit do kritickej sekcie
- ostatne procesy cakaju, kym nie je volno
- ak sa aktivne caka
- metody aktivneho cakania su
- striktne striedanie
- v takomto pripade nemoze proces vstupit do KS opakovane a jeden proces moze spomalit ostatne procesy
- zdielana premenna
- zdielana premenna indikuje obsadenost kritickej sekcie
- proces v slucke testuje aktualnu hodnotu premennej
- nevyhodou je plytvanie casu
- ak OS pouziva prioritne planovanie, tak moze vzniknut inverzny prioritny problem a to, ze proces s vyssou prioritou bude aktivne cakat, kym proces s nizsou dokonci svoju pracu. Pokial bude priorita fixna, tak dojde k uviaznutiu
- ak sa aktivne blokuje
- proces vykona systemove volanie, ktore ho zablokuje, az kym sa KS uvolni
- proces sa tak dostane do stavu blocked a zaradi sa znovu medzi ostatne procesy
- blokovanie a deblokovanie procesov je vacsinou sucast OS API
- sleep (process)
- wakeup(process)
- musime vediet synchronizovat aj sleep a wakeup, pretoze wakeup moze byt zavolany na proces, ktory este nie je uspany => nastavime wakup waiting bit. Pri pokuse uspat proces sa iba resetuje wakeup waiting bit
Petersonov algoritmus
- je korektnym SW riesenim problemu
- algoritmus funguje takto
- zistime, kolko mame procesov
- pri vstupe do KS musi proces prejavit zaujem o vstup
- dostane sa do poradia
- ak v kritickej sekcii nie je prave iny proces, tak moze vstupit
- inak, musi vyckat poradie
- pri odchode z KS, proces oznami, ze ide prec
Instrukcie TSL
- jedna sa o Test Set and Lock instrukciu
- instrukcia nacita obsah slova z pamate a nastavi ho na nenulovu hodnotu
- CPU zamkne pamatovu zbernicu, aby znemoznilo ostatnym CPU pristup do pamate
- TSL je atomicka instrukcia - je to korektne HW riesenie
- TSL moze byt preto pouzita pri synchronizacii v multiprocesorovych systemoch so zdielanou pamatou
Semafor
- semafor je datovy typ, ktory obsahuje citac a frontu cakajucich procesov
- operacie: init(), down(), up()
- pri init sa citac nastavi na zadane cislo a fronta sa vyprazdni. Zadane cislo vravi, ze kolko procesov moze zdielat nejaky prostriedok sucasne
- z pociatocnej a aktualnej hodnoty vieme urcit, kolko procesov je v danom okamihu v KS
- ak je zavolany down, tak sa citac zmensi o 1, ak je vacsi ako 0. Ak je 0, tak sa zablokuje proces a ulozi do fronty
- ak je nejaky proces vo fronte, tak na up() sa zobudi, inak sa citac zvacsi o 1
- tieto "instrukcie" su vykonavane atomicky
- typom semaforu je binarny semafor = mutex
- citac je nastaveny na 1-cku
- na up() na konci nesmieme zabudnut, pretoze dojde k deadlocku
Monitor je Semafor vyssej urovne. Je to konstrukt vyssich programovacich jazykov
- mnozina procedur, premennych a datovych struktur, ktore su zoskupene dohromady v specialnom module objektu
- len jeden proces moze byt aktivny v ten isty cas
- o vzajomne vylucenie sa stara prekladac
- operacie
- wait(c) - pozastavi volajuci proces na podmienenej premennej c
- signal(c) - spusti niektory z pozastavenych procesov na podmienenej premennej c
- podmienene premenne
- preddefinovany datovy typ, ktory umozni pozastavit, spustit proces
Zasielanie sprav
- vyuziva operacie send a receive
- adresovanie sprav
- priame - sprava je ulozena priamo do priestoru daneho prijemcu
- nepriame - sprava je docasne zdielana v zdielanej datovej strukture, co nam lepsie umoznuje implementovat kolketivne komunikacne algoritmy
- synchronizacia
- blokujuci send a blokujucie recieve
- neblokujuci send, blokujuci recieve
- neblokujuci send/receive
Bariera
- definujeme minimalny pocet procesov, ktore mozu prelomit barieru
- ked proces dorazi k bariere, tak je zablokovany do tej doby, kym vsetkych n procesov nedorazi k bariere
SW: Casovo zavisle chyby a kriticke sekcie
Casovo zavisle chyby vznikaju v dosledku vzajomneho pouzivania zdielanych prostriedkov (pamat, subory). Vysledok vypoctu je potom zavisly na prepinani kontextu (nakolko si navzajom prepisuju data). Detekcia takychto problemov je narocna.
Cast programu, ktora vyuziva zdielane prostriedky sa nazyva kriticka sekcia. Kriticke sekcie viacerych procesov, ktore sa tykaju toho isteho prostriedku, sa nazyvju zdruzene kriticke sekcie. Mi tu ale mame Coffmanovu podmienku, ktora vravi, ze vzajomne vylucenie - nemozete zdielat jeden prostriedok sucasne => nemozete byt v zdruzenej kritickej sekcii sucasne.
Aby bol program korektny, tak musia byt splnene 4 podmienky
Cast programu, ktora vyuziva zdielane prostriedky sa nazyva kriticka sekcia. Kriticke sekcie viacerych procesov, ktore sa tykaju toho isteho prostriedku, sa nazyvju zdruzene kriticke sekcie. Mi tu ale mame Coffmanovu podmienku, ktora vravi, ze vzajomne vylucenie - nemozete zdielat jeden prostriedok sucasne => nemozete byt v zdruzenej kritickej sekcii sucasne.
Aby bol program korektny, tak musia byt splnene 4 podmienky
- dva procesy sa nesmu nachadzat sucasne v kritickej sekcii
- nesmu byt kladene ziadne predpoklady na rychlost a pocet procesorov
- pokial proces bezi mimo kriticku sekciu, tak nesmie byt blokovany inymi procesmi
- ziadny proces nesmie na vstup do kritickej sekcie cakat do nekonecna
A na toto tu mame aj Bernsteinove podminenky, ktore vravia, ze zdielane premenne mozu byt iba citane. Tym zabranime konfliktom, ale hovno vyriesime, pretoze toto su prilis prisne podmienky.
Funkcia jednej premennej
Nech M je podmnožina množiny reálnych čísel. Ak ku každému prvku
x
M priradíme podľa určitého predpisu práve jeden prvok yR, ktorý označíme y = f(x), potom hovoríme, že na množine M je definovaná funkcia jednej reálnej premennej (stručnejšie funkcia).
x
M priradíme podľa určitého predpisu práve jeden prvok yR, ktorý označíme y = f(x), potom hovoríme, že na množine M je definovaná funkcia jednej reálnej premennej (stručnejšie funkcia).Argument x nazývame nezávisle premenná, y je závisle premenná a f jefunkčný predpis. Množinu M nazývame definičným oborom funkcie f a budeme označovať D(f). Množinu všetkých funkčných hodnôt, ktoré funkciaf nadobúda, nazývame oborom hodnôt funkcie f a budeme označovať H(f). Funkcie budeme zvyčajne označovať malými písmenami abecedy f, g, h, u, valebo f(x), g(x), h(x), u(x), v(x), atď.
SW: Pridelovanie zdielanych prostriedkov procesom
Procesy pri svojej cinnosti ziadaju o pridelenie prostriedkov a tie su casto zdielane - to moze sposobit problemy, napriklad deadlock.
Deadlock - je uviaznutie skupiny procesov. K deadlocku dochadza, ak skupina procesov caka jeden na druheho. Uviaznutie mozeme modelovat pomocou alokacneho grafu
A ziada prostriedok S, ale ten je pouzivany procesom B, ktory ziada prostriedok R, ktory je prave pouzivany procesom A. - a to je dost v prdeli, takze musime nieco vymysliet
Aby doslo k uviaznutiu, tak musia byt splnene Coffmanove podmienky - nutne podmienky pre uviaznutie
Deadlock - je uviaznutie skupiny procesov. K deadlocku dochadza, ak skupina procesov caka jeden na druheho. Uviaznutie mozeme modelovat pomocou alokacneho grafu
Aby doslo k uviaznutiu, tak musia byt splnene Coffmanove podmienky - nutne podmienky pre uviaznutie
- vzajomne vylucenie - prostriedok nemoze byt zdielany viacerymi procesmi (1 alebo ziaden)
- podmienka drz a cakaj - proces, ktory ma uz pridelene nejake prostriedky, moze ziadat o dalsie prostriedky
- podmienka neodnimatelnosti - prostriedok, ktory bol uz prideleny nejakemu procesu, mu nemoze byt nasilim odobrany
- podmienka cyklickeho cakania - musi existovat smycka dvoch a viac procesov, v ktorej kazdy proces caka na prostriedok prideleny dalsiemu prostriedku v smycke
Strategie riesenia uviaznutia
- pstrosi algoritmus
- problem ignorujeme
- ked sa stane, tak procesy ukoncime
- nesplnenie jednej z coffmanovych podmienok
- vzajomne vylucenie
- moznost zdielat prostriedky pomocou virtualizacie (napr. tlaciaren)
- podminka drz a cakaj
- kazdy proces musi alokovat vsetky potrebne prostriedky v okamihu spustenia - tu vznika problem efektivneho/optimalneho vyuzivania prostriedkov
- podmienka neodnimatelnosti
- v praxi tazko realizovatelne
- podmienka cyklickeho cakania
- proces bude moct alokovat viac prostriedkov v presne definovanom poradi
- a to len prostriedok s vyssim cislom, ako je maximum z alokovanych prostriedkov
- problem to ocislovat
- detekcia a zotavenie
- ak dojde k uviaznutiu, tak je detekovane a odstranene - to sa da sledovanim alokovanych a volnych prostriedkov a pozadovanych prostriedkov
- algoritmus
- kazdy proces je spociatku neoznaceny
- spravime maticu alokovanych prostriedkov, kde i je proces a j je typ prostriedku
- spravime maticu pozadovanych prostriedkov, kde i je proces a j je typ
- vytvorime vektor existujucich prostriedkov
- vytvorime vektor volnych prostriedkov
- pokusime sa najst neoznaceny proces, ktoreho riadok v matici pozadovanych prostriedkov ma mensie, alebo rovnake hodnoty ako prvky vektora volnych prostriedkov
- ak taky vektor nenajdeme, tak su vsetky procesy uviaznute
- dynamicke zabranenie uviaznutiu pomocou "korektnej" alokacie prostriedkov
- jedna sa o sposob pridelovania na zaklade rozhodnutia, ci je pridelenie bezpecne
- prikladom moze byt bankarov algoritmus
- bezpecny stav je, ze existuje alokacne poradie, ktore zarucuje, ze kazdy proces bude postupne uspokojeny a skonci
- ak by alokacia prostriedkov viedla na nebezpecny stav, tak ziadost bude odmietnuta
- pruser je, ze musime dopredu vediet, ake prostriedky sa po nas budu vyzadovat
SW: Planovanie vlakien
Planovanie mozme rozdelit na
- dlhodobe - urcuje, ktore programy budu zpracovane systemom
- strednodobe -
- kratkodobe - pri preruseni od casovaca, I/O zariadenia, systemove volania, signaly (medzi pamatou a CPU)
- kriteria su z uzivatelskeho hladiska: doba zpracovania, doba odozvy, dosiahnutie medze, predvidatelnost
- z hladiska OS su kriteria priepustnost, vyuzitie procesoru, spravodlivost, presadenie prorit, vyvazenie I/O
- I/O planovanie - urcuje, ktory I/O poziadavok bude obsluzeny volnym zariadenim
- procesy a vlakna mozme rozdelit na orientovane na CPU a orientovane na I/O. Doba vyuzitia CPU je kritickym faktorom.
strategie planovania
- planovanie s predbiehanim
- planovanie bez predbiehania
- dlhodobe - urcuje, ktore programy budu zpracovane systemom
- strednodobe -
- kratkodobe - pri preruseni od casovaca, I/O zariadenia, systemove volania, signaly (medzi pamatou a CPU)
- kriteria su z uzivatelskeho hladiska: doba zpracovania, doba odozvy, dosiahnutie medze, predvidatelnost
- z hladiska OS su kriteria priepustnost, vyuzitie procesoru, spravodlivost, presadenie prorit, vyvazenie I/O
- I/O planovanie - urcuje, ktory I/O poziadavok bude obsluzeny volnym zariadenim
- procesy a vlakna mozme rozdelit na orientovane na CPU a orientovane na I/O. Doba vyuzitia CPU je kritickym faktorom.
strategie planovania
- planovanie s predbiehanim
- proces je zablokovany automaticky po uplynuti nejakeho casoveho kvanta
- je to jedina mozna strategia v real-time a viacuzivatelskych systemoch
- planovanie bez predbiehania
- proces bezi, az kym o nejaku sluzbu nepoziada jadro, alebo kym neskonci
- pouzivalo sa v davkovych systemoch, v real-time systemoch by hrozilo blokovanie jadra
- pouziva sa v niektorych procesoch pre specialne triedy procesov a vlakien
- planovanie v davkovych systemoch
- First Come First Served - FIFO fronta
- bez predbiehania
- ked je beziaci proces zablokovany, tak dalsi z fronty ma volno
- ked je bloknuty proces opat ready, tak sa vlozi do fronty
- jednoduche, ale moze zpomalovat procesy orientovane na I/O
- Shortest Job First
- bez predbiehania, ale predpoklada, ze doba vypoctu bude znama vopred
- planovac teda spusti najskor procesy s najmensou dobou vypoctu
- planovac sa snazi minimalizovat priemernu dobu vypoctu
- Shortest Remaining Time Next
- je to vlastne Shortest Job First, ale s predbiehanim
- na radu sa dostane proces, ktory by mal najrychlejsie skoncit - ked pride poziadavok, tak sa porovna, ze kto bude rychlejsi - aktualny proces vs novy proces? a ten rychlejsi ide
- starvation risk
- planovanie v interaktivnych systemoch
- Round Robin
- planovanie s predbiehanim
- ready procesy cakaju vo FIFO fronte
- kazdy proces ma casove kvantum, po uplynuti ktoreho, sa zaradi na koniec fronty
- dlzka casoveho kvanta je dolezita v tomto pripade - dlha == dlha doba odozvy, kratka == neefektivne pre CPU, 20 - 50ms je kompromis
- Priority Scheduling
- procesy maju pridelenu prioritu
- procesy su zoradene v triedach podla priority
- CPU je priradzovane procesom s najvyssou prioritou - v ramci triedy sa procesy striedaju s pouzitim round robin
- bez predbiehania - problem hladovenia
- s predbiehanim
- staticka/dynamicka priorita
- ak staticka, tak nadalej moze dochadzat k starvation
- ak dynamicka, tak proces, ktory caka dlho, moze dostat zvysenu prioritu
- casove kvanta mozu byt fixne/variabilne - v zavislosti na danej triede
Windows - Priority Scheduling s predbiehanim
SW: Procesy, vlakna
- vsetok beziaci SW v systeme je organizovany ako mnozina beziacich procesov (mimo kernel)
- proces je instancia spusteneho programu
- kazdy proces si alokuje prislusne prostriedky - adresovy priestor, zasobnik a ma atributy - identita, rodicia, informacie o planovani
- kazdy proces implicitne obsahuje jedno vlakno vypoctu - v user space
- ulohou OS je pri vytvoreni procesu nahrat data a kod do pamate a vytvorit zasobnik pre tento proces
- proces potom moze byt ukonceny dobrovolne, nedobrovolne, chybovou hlaskou, inym procesom
OS spravuje tabulku - process control block (1 polozka 1 proces)
- v PCB - identifikacia procesu, stavove informacie procesoru, informacie pre spravu procesu
zatial, co proces sluzi k alokovaniu prostriedkov, tak vlakno je planovane na spustenie na CPU
- vlakno je jednotkou planovanou na spustenie na CPU
- vlakno ma svoj vlastny program counter, registre, zasobnik, lokalne premenne, ale ostatne prostriedky a identita su zdielane
- vlakna v procese zdielaju rovnaky adresovy prostor
- vlakno je na zaciatku len jedno, ale moze vytvarat dalsie vlakna
- jednoprocesorove systemy vyuzivaju tzv. pseudoparalelizmus na simulovanie paralelizmu
- viacprocesorove systemu dokazu spustat viacero vlakien skutocne paralelne
- vlakno sa viac menej nachadza v troch stavoch - Running, Blocked, Ready
- ak su vlakna implementovane v uzivatelskom priestore => proces moze mat svoj vlastny planovaci algoritmus na planovanie a spravu vlakien, vlakna mozu byt implementovane v OS, ktore nepodporuje vlakna a planovanie je rychle. Problem je so systemovymi volaniami, page miss, ziadny clock interrupt
- ak su vlakna implementovane v jadre, tak jadro udrzuje tabulku vlakien a tym eliminujeme problem so sytemovymi volaniami, ale vytvaranie, ukonconvanie a planovanie bude pomalsie . jadro sa stara iba o tieto vlakna
Ak nemame vlakna, ale podporujeme len procesy, tak hovorime o procesorovom modele. Ak mame aj vlakna => vlaknovy model
- proces je instancia spusteneho programu
- kazdy proces si alokuje prislusne prostriedky - adresovy priestor, zasobnik a ma atributy - identita, rodicia, informacie o planovani
- kazdy proces implicitne obsahuje jedno vlakno vypoctu - v user space
- ulohou OS je pri vytvoreni procesu nahrat data a kod do pamate a vytvorit zasobnik pre tento proces
- proces potom moze byt ukonceny dobrovolne, nedobrovolne, chybovou hlaskou, inym procesom
OS spravuje tabulku - process control block (1 polozka 1 proces)
- v PCB - identifikacia procesu, stavove informacie procesoru, informacie pre spravu procesu
zatial, co proces sluzi k alokovaniu prostriedkov, tak vlakno je planovane na spustenie na CPU
- vlakno je jednotkou planovanou na spustenie na CPU
- vlakno ma svoj vlastny program counter, registre, zasobnik, lokalne premenne, ale ostatne prostriedky a identita su zdielane
- vlakna v procese zdielaju rovnaky adresovy prostor
- vlakno je na zaciatku len jedno, ale moze vytvarat dalsie vlakna
- jednoprocesorove systemy vyuzivaju tzv. pseudoparalelizmus na simulovanie paralelizmu
- viacprocesorove systemu dokazu spustat viacero vlakien skutocne paralelne
- vlakno sa viac menej nachadza v troch stavoch - Running, Blocked, Ready
- ak su vlakna implementovane v uzivatelskom priestore => proces moze mat svoj vlastny planovaci algoritmus na planovanie a spravu vlakien, vlakna mozu byt implementovane v OS, ktore nepodporuje vlakna a planovanie je rychle. Problem je so systemovymi volaniami, page miss, ziadny clock interrupt
- ak su vlakna implementovane v jadre, tak jadro udrzuje tabulku vlakien a tym eliminujeme problem so sytemovymi volaniami, ale vytvaranie, ukonconvanie a planovanie bude pomalsie . jadro sa stara iba o tieto vlakna
Ak nemame vlakna, ale podporujeme len procesy, tak hovorime o procesorovom modele. Ak mame aj vlakna => vlaknovy model
SW: Jadro OS
- zakladna sucast OS
- ulohou je sprava OS - teda komunikacia medzi HW a SW
- poskytuje abstrakcnu vrstvu pre zdroje na najnizsom stupni - pamat, CPU, procesory, I/O zariadenia - a to sa deje pomocou mechanizmou komunikacie medzi procesmi a systemovymi volaniami
- jadro vacsinou zacina v kernel rezime, inicializuje sa a potom sa uz nespusta priamo, ale vacsinou v reakcii na rozne vonkajsie udalosti - prerusenia, systemove volania
- obvykle bezi slucka Idle Process, ked nie je akurat nic ine na praci - to je asi najskor nejaky listener
- poskytuje prostriedky pre nizko-urovnove planovanie procesov, komunikaciu medzi procesmi, synchronizaciu, prepinanie kontextu
- zakladnou sluzbou OS je
- ulohou je sprava OS - teda komunikacia medzi HW a SW
- poskytuje abstrakcnu vrstvu pre zdroje na najnizsom stupni - pamat, CPU, procesory, I/O zariadenia - a to sa deje pomocou mechanizmou komunikacie medzi procesmi a systemovymi volaniami
- jadro vacsinou zacina v kernel rezime, inicializuje sa a potom sa uz nespusta priamo, ale vacsinou v reakcii na rozne vonkajsie udalosti - prerusenia, systemove volania
- obvykle bezi slucka Idle Process, ked nie je akurat nic ine na praci - to je asi najskor nejaky listener
- poskytuje prostriedky pre nizko-urovnove planovanie procesov, komunikaciu medzi procesmi, synchronizaciu, prepinanie kontextu
- zakladnou sluzbou OS je
- sprava zdrojov - procesor - komu pridelim procesor?, pamat - sprava pamate, alokacia miesta, swapovanie a I/O zariadenia - zabezpecuje komunikaciu s I/O
- sprava procesov
- multitasking
- pre-emptivny - kazdemu procesu je prideleny procesor na kratke casove kvantum
- kooperativny - procesor bezi az do chvile, kedy dojde k predom definovanej udalosti
- multiprocessing
- sprava behu na roznych procesoroch
- sprava pamate
- pristup k pamati
- alokacia volneho miesta
- virtualna pamat (ak vobec) - zarucuje ochranu pamatoveho priestoru kazdeho procesu a umoznuje system adresovania vacsej casti pamate, ako mame naozaj k dispozicii
- sprava I/O zariadeni
- komunikacie I/O <-> OS a vybavovanie ich poziadavkov
- udrzovanie zoznamu I/O
- systemove volania
- poskytovanie nejakeho API
SW: Struktura 1 a viac-uzivatelskeho OS
Jednouzivatelsky (MS-DOS) nevyzaduje prihlasenie, pretoze nerozlisuje uzivatelske role, nemusi byt real-time, moze byt davkovy. Viacuzivatelsky system umoznuje pracu viacerych uzivatelov sucasne (Time sharing). Podporuje multitasking, multiprogramming alebo oboje.
- rozhranie medzi HW a aplikaciami
- spravuje vypoctove prostriedky - fyzicke a logicke
- abstrahuje zlozitost HW
- poskytuje rozhranie aplikaciam
OS podpora pri sprave HW:
- kernel mod - CPU moze vykonavat vsetky instrukcie zo svojej instrukcnej mnoziny
- user mod - povolena je len ista podmnozina instrukcii
OS podpora pri sprave pamate:
- ochrana pamate
- podpora virtualnej pamate
- preklad logickych adries na fyzicke adresy
Podpora prepinania kontextu
- reakcia na prerusenia - teda asynchronne udalosti
- programovatelny interny casovac - generuje prerusenie po uplynuti nejakeho casoveho kvanta
Podpora efektivnych operacii I/O zariadeni
- DMA, interrupt
vlastnosti OS:
- rozhranie medzi HW a aplikaciami
- spravuje vypoctove prostriedky - fyzicke a logicke
- abstrahuje zlozitost HW
- poskytuje rozhranie aplikaciam
OS podpora pri sprave HW:
- kernel mod - CPU moze vykonavat vsetky instrukcie zo svojej instrukcnej mnoziny
- user mod - povolena je len ista podmnozina instrukcii
OS podpora pri sprave pamate:
- ochrana pamate
- podpora virtualnej pamate
- preklad logickych adries na fyzicke adresy
Podpora prepinania kontextu
- reakcia na prerusenia - teda asynchronne udalosti
- programovatelny interny casovac - generuje prerusenie po uplynuti nejakeho casoveho kvanta
Podpora efektivnych operacii I/O zariadeni
- DMA, interrupt
vlastnosti OS:
- viaculohovy - sprava viacerych procesov na 1-procesorovom systeme (time sharing), ochrana pamati a planovanie procesov
- viacvlaknovy - proces sa moze skladat z niekolkych sucasne beziacich uloh, zahrnuje aj planovanie uloh
- viacprocesorovy - podpora prace s viacerymi procesormi na viacprocesorovm systeme
- viacuzivatelsky - viac userov naraz, identifikacia a vzajomna ochrana uzivatelov
- unifikovane prostredie - prenositelnost medzi platformami
OS moze byt implementovany ako monoliticky system alebo ako layered system. Monoliticky system je implementovany ako jeden proces. Program je rozcleneny na funkcie a procedury. Vacsinou vsetko bezi v kernel mode. Layered system zase rozdeluje pracu medzi vrstvy.
Zakladne komponenty OS:
- Security
- Network management
- file system management
- secondary memory management
- I/O mamagement
- main memory management
- process management
- processor management
SW: Vyssie programovacie jazyky a ich delenie a preklad
Programovacie jazyky patria do zakladneho vybavenia pocitacov.
- vyssie programovacie jazyky
- strojovo orientovane jazyky
Strojovo orientovane jazyky su viazane na konkretny typ procesoru. Patri sem napriklad assembler.
Vyssie programovacie jazyky vyuzivaju abstrakcie od strojovej urovne a podporuju urcite programovacie paradigma.Kazdy z programovacich jazykov ma svoju syntaxiu a semantiku. Syntax je suhrn pravidiel udavajucich tvary jednotlivych konstrukcii a semantika udava vyznam tychto konstrukcii.
Interpretacia programovacieho jazyka
- interpretacna
- kompilacna
Zakladom kompilacnych jazykov je prekladac, ktory kompiluje zapis vo VPJ na cielovy program v jazyku pocitaca. Vacsina prekladacov preklada do jazyku relativnych adries (nie jazyk symbolickych instrukcii), ktory vychadza z konkretnej architektury.
Pri interpretacnej metode sa program preklada do vnutornej formy, ktora nie je strojovym jazykom fyzickeho procesoru, ale jazykom virtualneho pocitaca. Vykonavanie programu zaisti interpret. Tento sposob je sice menej narocny na preklad, ale narocnejsi z hladiska doby vypoctu.
Casna vazba - prekladac vie dopredu - v dobe prekladu, aka metoda sa kedy bude volat.
Pozdni vazba - prekladac nerozhoduje vopred, ale o tom, aka metoda bude volana sa rozhoduje, az ked pride k samotnemu volaniu. V Ccku sa to spravi pomocou virtual a funguje to preto, ze prekladac udrzuje tabulku virtualnych metod
Casna vazba - prekladac vie dopredu - v dobe prekladu, aka metoda sa kedy bude volat.
Pozdni vazba - prekladac nerozhoduje vopred, ale o tom, aka metoda bude volana sa rozhoduje, az ked pride k samotnemu volaniu. V Ccku sa to spravi pomocou virtual a funguje to preto, ze prekladac udrzuje tabulku virtualnych metod
Relace
ok, takze pre pana halasku, co to je relace?
zacnime tym, ze mame nieco, co nazyvame mnozina :). Mnozina je plne urcena svojimi prvkami (vyctom). V mnozine nezalezi na poradi prvkov. Usporiadana k-tica, ktorej prvky sa mozu aj opakovat, sa nazyva variacia.
Relace je zase usporiadana k-tica prvkov. Ak mnozinam A a B definujeme ich kartezsky sucin AxB, ako mnozinu, ktorej prvkami su vsetky usporiadane dvojice (a,b), kde a je z A a b je z B. Cela mnozina AxB sa univerzalna relace - to znamena vratane prazdnej mnoziny. Domena je mnozina vsetkych prvkov z A, ktore su vo vztahu s B. Nakolko su relace mnoziny, tak relace nesmie obsahovat duplicitne prvky.
Este si k tomu dopisme, ze co je zobrazenie a sme fertig. Nech A a B su opat lubovolne mnoziny, zobrazenim A -> B rozumieme predpis, ktory kazdemu prvku z A priradi prvok z B.
zacnime tym, ze mame nieco, co nazyvame mnozina :). Mnozina je plne urcena svojimi prvkami (vyctom). V mnozine nezalezi na poradi prvkov. Usporiadana k-tica, ktorej prvky sa mozu aj opakovat, sa nazyva variacia.
Relace je zase usporiadana k-tica prvkov. Ak mnozinam A a B definujeme ich kartezsky sucin AxB, ako mnozinu, ktorej prvkami su vsetky usporiadane dvojice (a,b), kde a je z A a b je z B. Cela mnozina AxB sa univerzalna relace - to znamena vratane prazdnej mnoziny. Domena je mnozina vsetkych prvkov z A, ktore su vo vztahu s B. Nakolko su relace mnoziny, tak relace nesmie obsahovat duplicitne prvky.
Este si k tomu dopisme, ze co je zobrazenie a sme fertig. Nech A a B su opat lubovolne mnoziny, zobrazenim A -> B rozumieme predpis, ktory kazdemu prvku z A priradi prvok z B.
SW: abstraktne datove typy
- jedna sa o abstrakciu od fyzickej a implementacnej vrstvy, je to vlastne konceptualna uroven
- zdoraznuju co sa s typmi vykonava, ake operacie s datmi vykonavaju
- je to mnozina druhu a dat a prislusnych operacii, ktore su presne specifikovane, nezavisle na implementacii
- tvorene signaturou a semantikou
- signatura = syntax - deklaracia druhov (obor hodnot), deklaracia operacii (mena operacii, druhy a poradie argumentov, druh vysledku)
- semantika = axiomy = popis vlastnosti operacii
samotna datova struktura je realizaciou ADT
ADT
- staticke - pocet a usporiadenie zloziek sa nemeni
- dynamicke - pocet a usporiadanie zloziek sa meni
- homogenne - vsetky komponenty rovnakeho druhu
- heterogenne - rozneho typu
- linearne - bezprostredny naslednik existuje (pole, zoznam)
- nelinearne - bezporostredny naslednik neexistuje (strom, tabulka)
sekvencne ADT - pole, zoznam, zasobnik, fronta
asociativne ADT - tabulka, mnozina
Pole
- postupnost prvkov, ktorym je priradeny index
- homogenne
- staticke - pokial je znamy pocet prvkov vopred
- dynamicke - pokial nie je znamy pocet prvkov
- linearne
- pristup pomocou mapovacej funkcie, ktore hovori, co kam bude ulozene, napriklad urci offset od base address
operacie: init, upper, lower, set, get
Tabulka
- homogenna
- dynamicka
- nelinearna
- polozky su jednoznacne urcene klucom
- operacie: init, insert, delete, search, read
- tabulka je implementovana v poli
- pre male mnozstvo klucov - sekvencne vyhladavanie
- pre vacsie - hash table
Zoznam
- homogenny
- linearny
- dynamicky
- mame ukazovatko a pracujeme nad prvkom, na ktory ukazujeme
- init, insert, delete, beginning?, end?, read, first, last, next, prev, length, empty?, full?, insertBeg, insertEnd, mark
- implementovane v poli
- implementovane ako zasobniky v poli
- v dynamickej pamati - linked list, double linked list, circular linked list
- vzdy mame tri pointre - head, tail, point
- po vlozeni vkladam vpred a ukazovatko nemenim
- po mazani ukazovatko posuniem na dalsiu poziciu
Mnozina
- s aj bez opakovania prvkov
- heterogenna
operacia
- ins, del, in, card
Strom
- strom je acyklicky suvisly graf
- ak ma koren, tak potom to je korenovy strom - koren je vzdy spojeny so vsetkymi uzlami orientovanou cestou
- binarny, usporiadany binarny ...
- empty, leaf?,set left, set right, set info, null
Fronta
FIFO - first in first out (pipe)
- implementovana v poli, linearne, kruhovo
- v dynamickej pamati, ako spojovy zoznam
LIFO - last in first out (buffer)
- pristup len na top
- vkladanie len na top
- implementuje sa v poli, alebo dynamickej pamati, ako spojovy zoznam
- zdoraznuju co sa s typmi vykonava, ake operacie s datmi vykonavaju
- je to mnozina druhu a dat a prislusnych operacii, ktore su presne specifikovane, nezavisle na implementacii
- tvorene signaturou a semantikou
- signatura = syntax - deklaracia druhov (obor hodnot), deklaracia operacii (mena operacii, druhy a poradie argumentov, druh vysledku)
- semantika = axiomy = popis vlastnosti operacii
samotna datova struktura je realizaciou ADT
ADT
- staticke - pocet a usporiadenie zloziek sa nemeni
- dynamicke - pocet a usporiadanie zloziek sa meni
- homogenne - vsetky komponenty rovnakeho druhu
- heterogenne - rozneho typu
- linearne - bezprostredny naslednik existuje (pole, zoznam)
- nelinearne - bezporostredny naslednik neexistuje (strom, tabulka)
sekvencne ADT - pole, zoznam, zasobnik, fronta
asociativne ADT - tabulka, mnozina
Pole
- postupnost prvkov, ktorym je priradeny index
- homogenne
- staticke - pokial je znamy pocet prvkov vopred
- dynamicke - pokial nie je znamy pocet prvkov
- linearne
- pristup pomocou mapovacej funkcie, ktore hovori, co kam bude ulozene, napriklad urci offset od base address
operacie: init, upper, lower, set, get
Tabulka
- homogenna
- dynamicka
- nelinearna
- polozky su jednoznacne urcene klucom
- operacie: init, insert, delete, search, read
- tabulka je implementovana v poli
- pre male mnozstvo klucov - sekvencne vyhladavanie
- pre vacsie - hash table
Zoznam
- homogenny
- linearny
- dynamicky
- mame ukazovatko a pracujeme nad prvkom, na ktory ukazujeme
- init, insert, delete, beginning?, end?, read, first, last, next, prev, length, empty?, full?, insertBeg, insertEnd, mark
- implementovane v poli
- implementovane ako zasobniky v poli
- v dynamickej pamati - linked list, double linked list, circular linked list
- vzdy mame tri pointre - head, tail, point
- po vlozeni vkladam vpred a ukazovatko nemenim
- po mazani ukazovatko posuniem na dalsiu poziciu
Mnozina
- s aj bez opakovania prvkov
- heterogenna
operacia
- ins, del, in, card
Strom
- strom je acyklicky suvisly graf
- ak ma koren, tak potom to je korenovy strom - koren je vzdy spojeny so vsetkymi uzlami orientovanou cestou
- binarny, usporiadany binarny ...
- empty, leaf?,set left, set right, set info, null
Fronta
FIFO - first in first out (pipe)
- implementovana v poli, linearne, kruhovo
- v dynamickej pamati, ako spojovy zoznam
LIFO - last in first out (buffer)
- pristup len na top
- vkladanie len na top
- implementuje sa v poli, alebo dynamickej pamati, ako spojovy zoznam
SW: Viacrozmerne vyhladavanie, geometricke vyhladavanie a algoritmy
pri vsetkych nasledujucich si predom zoradujeme data, aby sme s nimi mohli efektivnejsie manipulovat.
Grahamov algoritmus
- hladanie konvexnej obalky
1. zoradime body podla x
2. najdeme body zhora - horni retez a zdola - dolni retez
- pmin a pmax priradime obalke
- od pmin sa posuvame dalej po x osy a kazdy nasledujuci bod pridaem do obalky
- skontrolujeme uhol pi-1, pi, pi+1 (vektorovy sucin)
- ak konvexny - pridame dalsi bod
- ak konkavny - vypustime bod a vratime sa na pi-1
zlozitost je O(n*log(n))
Jarvisov algoritmus
- algoritmus balenia darcekov
1. vezmeme bod s minimalnou hodnotou y a vodorovnu priamku, ktora nim povedie
2. otocime priamkou okolo bodu, az narazime na novy bod
3. v novom bode povedieme priamku a znovu noou budeme otacat, az kym nenajdeme novy bod
- algoritmus je vhodny pre hladanie konvexnej obalky pre maly pocet bodov
- zlozitost O(kn), kde k je pocet bodov tvoriacich obalku a n je celkoby pocet bodov
Dalsim prikladom je zametacia technika, ktoru sme uz rozoberali, ta sa napriklad hodi na hladanie prisecnikov, alebo minimalnych bodov
Vonoreho diagram sa tiez da najst pomocou sweep line
- jedna sa o planarny graf, ktory nam umozni najst vzdy najblizsieho suseda
- kolko bodov tolko oblasti
- body v otvorenych oblastiach tvoria vrcholy obalky
- uzlom diagramu je stred kruznice opisanej v aspon troch bodoch
- najdenie vonoreho diagramu pomocou zametcej tehcniky je pekny priklad command and conquer pristupu k uloham geometrie
Grahamov algoritmus
- hladanie konvexnej obalky
1. zoradime body podla x
2. najdeme body zhora - horni retez a zdola - dolni retez
- pmin a pmax priradime obalke
- od pmin sa posuvame dalej po x osy a kazdy nasledujuci bod pridaem do obalky
- skontrolujeme uhol pi-1, pi, pi+1 (vektorovy sucin)
- ak konvexny - pridame dalsi bod
- ak konkavny - vypustime bod a vratime sa na pi-1
zlozitost je O(n*log(n))
Jarvisov algoritmus
- algoritmus balenia darcekov
1. vezmeme bod s minimalnou hodnotou y a vodorovnu priamku, ktora nim povedie
2. otocime priamkou okolo bodu, az narazime na novy bod
3. v novom bode povedieme priamku a znovu noou budeme otacat, az kym nenajdeme novy bod
- algoritmus je vhodny pre hladanie konvexnej obalky pre maly pocet bodov
- zlozitost O(kn), kde k je pocet bodov tvoriacich obalku a n je celkoby pocet bodov
Dalsim prikladom je zametacia technika, ktoru sme uz rozoberali, ta sa napriklad hodi na hladanie prisecnikov, alebo minimalnych bodov
Vonoreho diagram sa tiez da najst pomocou sweep line
- jedna sa o planarny graf, ktory nam umozni najst vzdy najblizsieho suseda
- kolko bodov tolko oblasti
- body v otvorenych oblastiach tvoria vrcholy obalky
- uzlom diagramu je stred kruznice opisanej v aspon troch bodoch
- najdenie vonoreho diagramu pomocou zametcej tehcniky je pekny priklad command and conquer pristupu k uloham geometrie
Asociativne a Adresne vyhladavanie - zlozitost
Vyhledávání | Typ | Paměťová složitost P(n) | Vyhledávání Q(n) | Vládání I(n) | Mazání D(n) | Nalezení minima, maxima | Nalezení předchůdce | Nalezení následníka |
| Sekvenční | Asoc. | O(n) | O(n) | O(1) | O(n) | O(n) | N/A | N/A |
| Půlením (binární) | Asoc. | O(n) | O(log n) | O(n) | O(n) | O(1) | N/A | N/A |
| Binární vyhledávací stromy | Asoc. | O(n) | O(h) | O(h) | O(h) | O(h) | O(h) | O(h) |
| Přímý přístup | Adr. | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | N/A | N/A |
| Zřetězené rozptylování | Adr. | O(m + n) | Extrém O(n) Průměrně O(1 + α) | O(1) | Extrém O(n) Průměrně O(1 + α) | Extrém O(n) Průměrně O(1 + α) | N/A | N/A |
| Otevřené rozptylování | Adr. | O(n) | úměrné α | úměrné α | úměrné α | úměrné α | N/A | N/A |
SW: Asociativne vyhladavanie
Asociativne vyhladavanie
- bud je implementovane v poli - vyhladavanie pulenim, sekvencne vyhladavanie
- alebo je implementovane v binarnom vyhladavacom strome
Sekvencne vyhladavanie - vyhladavanie v poli, prechadzanie polom prvok za prvkom a jedneho dna narazim na ten spravny prvok ..
- moze byt v
nezoradenom poli - v kazdom kroku sa pytame, ci sme nasli ten spravny prvok, ak ano, tak vyborne :)
- zlozitost je O(n) pre vsetko, okrem vlozenia
- vlozenie je O(1), pretoze tam ten prvok proste len niekam jebnem a nic ine ma nezaujima
nezoradenom poli so zarazkou - na koniec pola si dame hladany prvok/zarazku, cim zamedzime, aby sme prekrocili hranice pola a hladany prvok vzdy najdeme. Takto usetrime test na koniec pola, ale zlozitost bude stale rovnaka
vyhladavanie pulenim - jedna sa o binarne vyhladavanie, ktore vyuziva metodu rozpolovania intervalu. V takomto poli uz mame zoradene prvky. Vyhladavanie zahajime v polovicke pola a postupujeme vpravo/vlavo, podla toho, ako je pole zoradene. Postup vpravo/vlavo znamena rozdelenie zostavjucej casti pola na dve casti a znova - top-down approach command and conquer. Vyhladavanie takto limitujeme na O(log(n)) a minimum a maximum dokazeme urcit okamzite O(1)
dalsou moznostou asociativneho vyhladavania je Binary Search Tree
- usporiadany, korenovy, binarny strom
- lavy uzol je vzdy mensi ako koren, pravy je vacsi => vsetko vlavo je mensie ako koren a vsetko vpravo je vacise ako koren (alebo uzol, z ktoreho vetvime)
- pamatove zlozitost je O(n), vsetky ostatne su O(h) a h = log(n) u vyvazeneho stromu, n u nudle
- BVS preto vyvazujeme - idealny pripad je, ak pocet uzlov laveho podstromu je rovny poctu uzlov praveho podstromu - toto je prilis silnou podmienkou a preto uvazujeme slabsie podmienky. Vyvazuje sa podla
vysky - AVL strom
vysky a poctu potomkov - 1-2 stromy
vahy podstromu - vahovo vyvazene stromy
pri vyvazovani stromu vlastne rotujeme prvky => leva a prava rotace a levo-prave/pravo-lave rotacie
AVL strom
- vyskovo vyvazeny strom
- prazdny strom = -1
- neprazdny = 1 + vyska dlhsieho potomka
- k vyvazovaniu rotaciou pristupujeme az ked je nahodou uzol mimo <-1,1>
vahovo vyvazene stromy
- oznacene ako stromy s ohranicenym vyvazenim
- list - vaha 1/2
- inak w = (|Ul| + 1) / (|U| + 1), kde Ul je pocet uzlov vlavo a U je pocet uzlov podstromu (vcitane u)
- musime nejako urcit hranicu, ako ma byt strom vyvazeny a to je alfa <= w(u) <= 1-alfa a alfa sa zvacsa urcije ako 0 <= alfa <= 1/2. toto sa vola ohranicene vyvazovanie a strom je stromom s ohranicenym vyvazovanim
dalsim pripadom BVS je cerveno-cierny strom
- uzel je cerveny alebo cierny
- kazdy list je cierny
- ak je uzol cerveny, tak jeho potomkovia su cierny
- kazda jednoducha cesta z u do listu obsahuje rovnaky pocet ciernych uzlov
- koren je cierny
=> cierna vyska stromu, a to je pocet ciernych uzlov na ceste z u -> v (u sa nepocita, alebo je 0)
SW: Adresne vyhladavanie
mozme rozdelit na
- adresuje na zaklade rozptylovacej funkcie h(k)
- zobrazujem mnozinu klucov K z univerza do itnervalu adries <Amin, Amax>
- rozptylovacia funkcia by mala byt jednoducha a rychla a je silne zavisla na vlastnostiach klucov a ich reprezentacii v pamati
- mala by generovat minimum kolizii a rovnomerne vyuzivat adresny priestor
- ak dojde ku kolizi => bud je zla fcia, pretoze vracia prilis blizke hodnoty, alebo spatne pocita, ak to nie je pripad, tak musime kolizie riesit
- kolizie spomaluju aplikaciu
- sposoby riesenia su zretazene rozptylovanie a otevrene rozptylovanie
zretazene rozptylovanie
- mame prvu h(k), napr. h(k) = k mod 3 (takze 3 je potom rozsah adries pre umiestnenie prvkov)
- ak dojde ku kolizii, teda mame synonymum, tak potom prvok zretazim do spojoveho zoznamu za prvok, s ktorym kolidujem
- toto retazenie nazyvam retazou synonym a ma idealne dlzku alfa = n/m, kde alfa > 1, n je pocet prvkov a m velkost tabulky < m
- vkladanie = O(1)
- vyberanie, mazanie = O(n) ak to ide fakt zle, alebo O(1+alfa) priemerne
- vyplati sa, pretoze sa neplytva pamatou
otvorene rozptylovanie
- pocet prvkov je vopred znamy
- tu sa nebudu pouzivat ukazatele, ale bude sa ukladat do pola
- su dve moznosti ako ukladat prvky, ked dojde ku kolizii - Linear Probing a Double Hashing
- Linear Probing v pripade kolizie ulozi prvok na dalsie miesto v poradi, ktore je volne, vytvara tak zhluky, ktore mozu byt az prilis dlhe
- Double hashing pri kolizii pouzije druhu hashovaciu funkciu a ked nevyjde ani to, tak pouzije linear probing,
funkcia moze vyzerat takto: h(k) = (k mod 5 + i*h2(k)) mod 5, h2(k) = (k + 3i)mod5 ak to nevyjde na 1x , tak vloz o 3 pozice dalej (v pripade prveho neuspechu)
problemom je, ako zaplnit tabulku
- tabulka moze byt viac zaplenena, kym zacne klesat vykonnost a operacie trvaju umerne zaplnenosti tabulky, vhodne je tak 3/4, 9/10
- indexovanie klucom
- priamy pristup, pretoze kluc je priamo adresou
- rozsah klucov zodpoveda priamo rozsahu indexov
- asymptoticka zlozitost je theta(1)
- rozptylovanie
- funguje vypoctom adresy z hodnoty kluca
- priemerna zlozitost je omega(1)
- porovnanie klucov
- toto je asociativne vyhladavanie
- patri sem napriklad sekvencne vyhladavanie, BVS,
- zlozitost omega(log(n))
ak mame vela pamate => index. klucom
ak mame vela casu => sekvencne vyhladavanie
ak nemame ani jedno => rozptylovanie
Hashing
- vhodne pre vyhladavanie, ale nevhodne pre triedenie
- adresuje na zaklade rozptylovacej funkcie h(k)
- zobrazujem mnozinu klucov K z univerza do itnervalu adries <Amin, Amax>
- rozptylovacia funkcia by mala byt jednoducha a rychla a je silne zavisla na vlastnostiach klucov a ich reprezentacii v pamati
- mala by generovat minimum kolizii a rovnomerne vyuzivat adresny priestor
- ak dojde ku kolizi => bud je zla fcia, pretoze vracia prilis blizke hodnoty, alebo spatne pocita, ak to nie je pripad, tak musime kolizie riesit
- kolizie spomaluju aplikaciu
- sposoby riesenia su zretazene rozptylovanie a otevrene rozptylovanie
zretazene rozptylovanie
- mame prvu h(k), napr. h(k) = k mod 3 (takze 3 je potom rozsah adries pre umiestnenie prvkov)
- ak dojde ku kolizii, teda mame synonymum, tak potom prvok zretazim do spojoveho zoznamu za prvok, s ktorym kolidujem
- toto retazenie nazyvam retazou synonym a ma idealne dlzku alfa = n/m, kde alfa > 1, n je pocet prvkov a m velkost tabulky < m
- vkladanie = O(1)
- vyberanie, mazanie = O(n) ak to ide fakt zle, alebo O(1+alfa) priemerne
- vyplati sa, pretoze sa neplytva pamatou
otvorene rozptylovanie
- pocet prvkov je vopred znamy
- tu sa nebudu pouzivat ukazatele, ale bude sa ukladat do pola
- su dve moznosti ako ukladat prvky, ked dojde ku kolizii - Linear Probing a Double Hashing
- Linear Probing v pripade kolizie ulozi prvok na dalsie miesto v poradi, ktore je volne, vytvara tak zhluky, ktore mozu byt az prilis dlhe
- Double hashing pri kolizii pouzije druhu hashovaciu funkciu a ked nevyjde ani to, tak pouzije linear probing,
funkcia moze vyzerat takto: h(k) = (k mod 5 + i*h2(k)) mod 5, h2(k) = (k + 3i)mod5 ak to nevyjde na 1x , tak vloz o 3 pozice dalej (v pripade prveho neuspechu)
problemom je, ako zaplnit tabulku
- tabulka moze byt viac zaplenena, kym zacne klesat vykonnost a operacie trvaju umerne zaplnenosti tabulky, vhodne je tak 3/4, 9/10
SW: Quick Sort
- divide & conquer
- zvoli sa pivot, vacsinou prvy v poli
- 2 indexy, ktore sa pohybuju zlava a zprava
- lavy index ide doprava a na prvku >= pivot zastane
- pravy index ide dolava a na prvku <= pivot zastane
- prvky sa prehodia
- lindex++ & pindex++
- ked to dokoncime, tak v lavej casi pola budu prvky < pivot a v pravej > pivot
- pole rozdelime na polovicu a ideme znovu
- O(n^2), ale zalezi na volbe pivota, ak je pivot vhodne zvoleny, tak sa da dosiahnut O(nlog(n))
- zvoli sa pivot, vacsinou prvy v poli
- 2 indexy, ktore sa pohybuju zlava a zprava
- lavy index ide doprava a na prvku >= pivot zastane
- pravy index ide dolava a na prvku <= pivot zastane
- prvky sa prehodia
- lindex++ & pindex++
- ked to dokoncime, tak v lavej casi pola budu prvky < pivot a v pravej > pivot
- pole rozdelime na polovicu a ideme znovu
- O(n^2), ale zalezi na volbe pivota, ak je pivot vhodne zvoleny, tak sa da dosiahnut O(nlog(n))
SW: Radix Sort
- tzv. priehradkove radenie
- pouziva jednotlive zlozky hodnoty, znaky, bity apod.
- napriklad od LSB radi kazdy polozku do priehradok, v jednej priehradke bude vsetko s a na konci, v druhej s b, v tretej c. prepojene to je ako spojovy zoznam.
- potom sa spravi poriadok podla 2 pismenka, pricom sa znovu priehradkuje, alebo teda polozky sa presuvaju z priehradok do inych priehradok podla pismenka. Tie, co boli v priehradke a po prvom radeni, zostanu na vrchu, tie co boli v b budu druhe v poradi, ale napriklad v priehradke pre b
- potom podla 3ieho
- atd. az kym nemame hotovo
- kedze to je spojovy zoznam, tak presuvanie je velmi rychle, pretoze len presuvame pointre
- zlozitost theta(dn), kde d je dlzka najdlhsieho prvku (napr. pocet pismen)
- pouziva jednotlive zlozky hodnoty, znaky, bity apod.
- napriklad od LSB radi kazdy polozku do priehradok, v jednej priehradke bude vsetko s a na konci, v druhej s b, v tretej c. prepojene to je ako spojovy zoznam.
- potom sa spravi poriadok podla 2 pismenka, pricom sa znovu priehradkuje, alebo teda polozky sa presuvaju z priehradok do inych priehradok podla pismenka. Tie, co boli v priehradke a po prvom radeni, zostanu na vrchu, tie co boli v b budu druhe v poradi, ale napriklad v priehradke pre b
- potom podla 3ieho
- atd. az kym nemame hotovo
- kedze to je spojovy zoznam, tak presuvanie je velmi rychle, pretoze len presuvame pointre
- zlozitost theta(dn), kde d je dlzka najdlhsieho prvku (napr. pocet pismen)
SW: Shell sort
je to bubble sort, ktory porovnava prvky vzdialene o vzdielenost d a tuto vzdialenost meni pri kazdom priechode (?)
dosahuje lepsej zlozitosti ako bubble sort a to O(nlog(n)), prisom bubble ma theta(n^2).
dosahuje lepsej zlozitosti ako bubble sort a to O(nlog(n)), prisom bubble ma theta(n^2).
SW: Merge Sort
metoda divide and conquer
neozradene pole rozdelime na mensie pole a to dalej na mensie pole a mensie pole a potom odspodu zlievame policka dokopy
nakolko musime rozdelit theta(log(n)), zlievanie theta(n) => theta(n) je priemerny pripad
neozradene pole rozdelime na mensie pole a to dalej na mensie pole a mensie pole a potom odspodu zlievame policka dokopy
nakolko musime rozdelit theta(log(n)), zlievanie theta(n) => theta(n) je priemerny pripad
Friday, June 24, 2011
SW: Heap sort
Heap Sort - mame haldu a odoberame koren, haldu vzdy opravime a znovu vezmeme koren. na miesto korena vzdy vlozime najposlednejsi prvok - najvacsi a prerobime haldu.
dostaneme opacne zoradene pole
theta(n(log(n)))
dostaneme opacne zoradene pole
theta(n(log(n)))
SW: Heap
Halda je binarny strom, kde plati, ze hodnota predchodcu musi byt mensia, ako hodnota jeho naslednika. Takze vieme, ze koren BS bude vzdy najnizsi prvok.
Haldu ukladame ako pole a plati, ze ak index prvku je k => 2k je lavy naslednik a 2k+1 je pravy naslednik, samozrejme, ak prvy index je 1.
- vkladat do haldy znamena prekopat pole, takze pri vlozeni musime preradit prvky - ak vlozime novy prvok, tak nam musi prebehnut haldou a najst si poziciu, podla toho musime prekopat aj nizsie urovne.
- vyberat znamena tiez prekopat prvky a preradit pole - teda vlastne nam staci prehodit najlavejsi prvok a prekopat tu cast stromu, kde sa deju zmeny
pri odstranovani korena, dame na miesto korena najposlednejsi prvok a nechame znovu zoradit. Ak vyberieme iny prvok, tak musime to iste spravit aj s tym prvkom.
haldu tvorime v poli, takze na zaciatku mame pole, ktora nema vlastnost byt haldou. na vystupe mame pole, ktore je haldou. pole - binarny strom - si rozdelime do podhald a kazdu zoradime, potom postupujeme vyssie a vyssie ... a potom mame hotovo :)
oprav koren = log(n)
vytvor haldu = O(n.log(n))
zorad haldu = theta(n.log(n))
Haldu ukladame ako pole a plati, ze ak index prvku je k => 2k je lavy naslednik a 2k+1 je pravy naslednik, samozrejme, ak prvy index je 1.
- vkladat do haldy znamena prekopat pole, takze pri vlozeni musime preradit prvky - ak vlozime novy prvok, tak nam musi prebehnut haldou a najst si poziciu, podla toho musime prekopat aj nizsie urovne.
- vyberat znamena tiez prekopat prvky a preradit pole - teda vlastne nam staci prehodit najlavejsi prvok a prekopat tu cast stromu, kde sa deju zmeny
pri odstranovani korena, dame na miesto korena najposlednejsi prvok a nechame znovu zoradit. Ak vyberieme iny prvok, tak musime to iste spravit aj s tym prvkom.
haldu tvorime v poli, takze na zaciatku mame pole, ktora nema vlastnost byt haldou. na vystupe mame pole, ktore je haldou. pole - binarny strom - si rozdelime do podhald a kazdu zoradime, potom postupujeme vyssie a vyssie ... a potom mame hotovo :)
oprav koren = log(n)
vytvor haldu = O(n.log(n))
zorad haldu = theta(n.log(n))
SW: Counting sort
efektivny algoritmus pre maly rozsah vstupnych dat. Vyuziva pomocne pole pre pocitanie. pomocne pole si uklada pocet vyskytov prvku. potom nastavi vyskyt kazdeho vacsieho prvku na hodnotu toho pred nim + 1 a uz len kopiruje data do vysledneho pola.
http://users.cs.cf.ac.uk/C.L.Mumford/tristan/CountingSort.html.
nic super zlozite, ale pre naozaj velke pole by to bolo velmo neefektivne
zlozitost je theta(n) pre rozumny rozsah vstupnych dat
http://users.cs.cf.ac.uk/C.L.Mumford/tristan/CountingSort.html.
nic super zlozite, ale pre naozaj velke pole by to bolo velmo neefektivne
zlozitost je theta(n) pre rozumny rozsah vstupnych dat
SW: Bubble Sort
- tu ide o porovnanie dvoch prvkov medzi sebou
- ak su v nespravnom poradi, tak vymenime
- potom pohyb + 1
- takto sa prvym priebehom dostaneme k tomu, ze najvacsi prvok je na konci pola
- druhym priebehom sa posunieme tam, ze zaradime 2 najvyssi prvok na koniec pola
- potrebujeme n-1 priebehov a v kazdom priebehu spravime n testov
=> 1/2(n^2 - n) => theta n^2
- ak su v nespravnom poradi, tak vymenime
- potom pohyb + 1
- takto sa prvym priebehom dostaneme k tomu, ze najvacsi prvok je na konci pola
- druhym priebehom sa posunieme tam, ze zaradime 2 najvyssi prvok na koniec pola
- potrebujeme n-1 priebehov a v kazdom priebehu spravime n testov
=> 1/2(n^2 - n) => theta n^2
SW: Insertion sort
Narozdiel od selection sortu vkladame prvky na adekvatnu poziciu.
- vezmeme 1. prvok pola
- vezmeme druhy prvok pola
- je druhy prvok mensi alebo vacsi ako prvy?
- ak mensi => tak ich vymenime
- ak vacsi, tak porovname prvok 3 s prvkom 2
- ak vacsi => ideme dalej
- ak mensi => tak porovname s 1 a vymenime tam, kde je potreba
- postupujeme az na koniec pola
takze v najhorsom porovname prvky
2 : 1
3 : 2 : 1
4 : 3 : 2 : 1
n : n - 1 : ... : n - n + 1 => 1/2(n^2 - n)
ale pruser je, ze nerobime len testy, ale aj presuny => ze spravime 1/2(n^2 - n) presunov v najhorsom pripade ... takze nasa zlozitost bude theta n^2 v najhorsom pripade, aj priemernom a n-1 v najlepsom, teda ak radime zoradene pole
SW: Selection Sort
Jeden z algoritmov riadenia vyberom
- prejdeme pole
- najdeme najnizsi prvok
- prvok umiestnime na zaciatok pola
- posunieme sa o policko dalej
=> 1x prejdeme n prvkov, 2x n-1 prvkov v k tom kroku teda mame n-k-1 prvkov =>
(n-1) + (n-2) + (n-3) + .... + (n - n + 1) = 1/2 (n^2 - n) => theta n^2
SW: Algoritmy radenia vyberom
Sem patri Selection sort, Insertion sort, Bubble sort, Counting sort, Heap Sort, Merge sort, Shell sort, Radix sort, Quick sort
Stabilny algoritmus znamena, ze zachovava poradie prvkov s rovnakym klucom.
Zlozitosti:
Stabilny algoritmus znamena, ze zachovava poradie prvkov s rovnakym klucom.
Zlozitosti:
| Algoritmus | Asymptotická operační (časová) složitost | Paměťová složitost | Přístup | Stabilní | |||
| Minimální | Střední | Maximální | "Průměrná" | ||||
| Řazení výběrem (Select Sort) | Θ(n²) | Θ(n²) | Θ(n²) | Θ(n²) | Θ(1) | přímý | dle implementace |
| Řazení vkládáním (Insert Sort) | Θ(n) | Θ(n²) | Θ(n²) | O(n²) | Θ(1) | přímý | ano |
| Řazení zaměňováním (Bubble Sort) | Θ(n) | Θ(n²) | Θ(n²) | O(n²) | Θ(1) | přímý | ano |
| Řazení haldou (Heap Sort) | Θ(n · log n) | Θ(n · log n) | Θ(n · log n) | Θ(n · log n) | Θ(1) | přímý | ne |
| Quicksort | Θ(n · log n) | Θ(n · log n) | Θ(n²) | Θ(n · log n) | Θ(log n) | přímý | ne |
| Řazení sléváním (Merge Sort) | Θ(n · log n) | Θ(n · log n) | Θ(n · log n) | Θ(n · log n) | Θ(n) | sekvenční | ano |
| Přihrádkové řazení (Radix Sort) | Θ(n · d) | Θ(n · d) | Θ(n · d) | Θ(n · d) | O(n) | přímý | ano |
Subscribe to:
Posts (Atom)