https://www.512.cz/index.php?feed=atom&target=Acolade&title=Speci%C3%A1ln%C3%AD%3AP%C5%99%C3%ADsp%C4%9Bvky%2FAcolade 2026-10-20T17:36:02Z Z FAV wiki MediaWiki 1.17.0 https://www.512.cz/index.php?title=Kontrola_konzistence_souborov%C3%A9ho_syst%C3%A9mu,_mechanismy_ochrany_p%C5%99ed_neopr%C3%A1vn%C4%9Bn%C3%BDm_p%C5%99%C3%ADstupem 2014-02-20T06:49:08Z

<p>Acolade: kategorizace</p> <hr /> <div>== Kontrola konzistence informace o diskových blocích souborů ==<br /> <br /> Program vytvoří 2 tabulky, obsahující čítač pro každý blok<br /> * Tabulka počtu výskytů bloku v souboru<br /> * Tabulka počtu výskytů bloku v seznamu volných bloků (seznam nebo bitová mapa)<br /> <br /> Je-li FS konzistentní, bude mít každý blok 1 buď v první, nebo ve druhé tabulce<br /> <br /> [[Soubor:Kontrola-fs.png|400px]]<br /> <br /> Možné chyby:<br /> 0-0: blok se nevyskytuje v žádné tabulce, není zavažné pouze redukuje kapacitu - vložení do seznamu volných bloků<br /> 0-2: blok je dvakrát nebo vícekrát v seznamu volných (!) - smazání jednoho záznamu ze seznamu volných bloků<br /> 1-1: blok patří souboru a zároveň je na seznamu volných (!) - vyjmeme ze seznamu volných bloků<br /> 2-0: blok patří do dvou nebo více souborů, nejzávažnější problém, nejspíše už došlo ke ztrátě dat (!!!) - alokujeme nový blok, problémový soubor do něj umístíme a upravíme i-uzel druhého souboru. Informujeme uživatele o problému.<br /> <br /> == Kontrola konzistence adresářové struktury ==<br /> <br /> Projdeme celý adresářový strom, kontrolujeme zda odpovídá počet odkazů v i-uzlu (i) s počtem výskytů v adresářích (a)<br /> * i = a - vše je OK<br /> * i &gt; a - soubor by nebyl zrušen ani po zrušení všech odkazů v adresářích<br /> * i &lt; a - soubor by byl zrušen po zrušení i odkazů, ale v adresářích budou ještě jména<br /> * a = 0 , i &gt; 0 - ztracený soubor, na který není v adresáři odkaz<br /> <br /> <br /> == Žurnálování ==<br /> <br /> Před každým zápisem na disk vytvoří na disku záznam popisující plánované operace, pak provede operace a záznam zruší. Výpadek – na disku najdeme žurnál o všech operacích, které mohly být v době havárie rozpracované, zjednodušuje kontrolu konzistence fs.<br /> <br /> <br /> == Mechanismy ochrany ==<br /> <br /> * Soubor je třeba chránit před neoprávněným přístupem<br /> * Systém musí uchovávat informace o přístupových právech subjektů k objektům<br /> * Informace může být ve dvou různých podobách: ACL nebo CL<br /> <br /> * Subjekt – entita schopná přistupovat k objektům (většinou proces)<br /> * Objekt – cokoliv, k čemu je potřeba omezovat přístup pomocí přístupových práv (např. soubor)<br /> <br /> <br /> Mechanismus ACL (Access Control Lists)<br /> * S každým objektem sdružen seznam subjektů, které mohou k objektu přistupovat<br /> * Pro každý uvedený subjekt je v ACL množina přístupových práv k objektu<br /> * sbjekty se zpravidla sdružují do skupin (učitelé, studenti, admini...)<br /> * ntfs<br /> <br /> <br /> Mechanismus Capability Lists<br /> * S každým subjektem sdružen seznam objektů, ke kterým může přistupovat a jakým způsobem<br /> * Problém: zjištění, kdo všechno má k objektu přístup + zrušení přístupu velmi obtížné<br /> * Řešení: odkaz neukazuje na objekt, ale na nepřímý objekt; systém může zrušit nepřímý objekt, tím neplatní odkazy na objekt ze všech C-seznamů.<br /> * někter=é distribuované systémy<br /> <br /> Mechanismus ACL se používá častěji.<br /> <br /> {{fav-kiv-bzinf}}<br /> <br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Syst%C3%A9my_soubor%C5%AF 2014-02-20T06:49:01Z

<p>Acolade: kategorizace</p> <hr /> <div>Téměř všechny aplikace potřebují trvale uchovávat data<br /> <br /> Hlavní požadavky:<br /> * Možnost uložit velké množství dat<br /> * informace musí zůstat zachována i po ukončení procesu<br /> * data musejí být přístupná více procesům<br /> <br /> při přístupu k zařízení mají všechny procesy společné problémy<br /> * alokace prostoru na disku<br /> * pojmenování dat<br /> * ochrana dat před neoprávněným přístupem<br /> * zotavení po havárii<br /> <br /> souborový systém:<br /> * konvence pro ukládání a přístup k souborům<br /> * část OS, která poskytuje mechanismus pro ukládání a přístup k datům<br /> <br /> uživatelské rozhraní:<br /> * konvence pro pojmenování souborů<br /> * typy souborů<br /> * způsob přístupu<br /> * atributy a přístupová práva<br /> * služby OS pro práci se soubory<br /> <br /> Windows: NTFS, FAT12, FAT16, FAT32, ISO 9660 (CD-ROM)<br /> <br /> Linux: ext2, ext3, ReiserFS, JFS, XFS, FAT12 až 32, ISO 9660, Minix, VxFS, OS/2 HPFS, SysV fs, UFS, NTFS read-only<br /> <br /> * soubor – pojmenovaná množina záznamů, které lze zpracovávat jako celek<br /> * záznam – strukturovaný datový objekt tvořený konečným počtem pojmenovaných položek<br /> <br /> <br /> atributy - informace sdružené se souborem, liší se podle jednotlivých OS / FS<br /> * příznaky (hidden, archive, temporary, read-only...)<br /> * velikost, datum vytvoření, poslední modifikace...<br /> <br /> Veškeré I/O jsou dnes (díky UNIXu) prováděny jako práce se soubory - interní struktura souboru OS nezajímá, adresář je také soubor<br /> <br /> Základní operace pro práci se soubory<br /> * otevření<br /> * vytvoření<br /> * čtení<br /> * zápis<br /> * nastavení pozice v souboru<br /> * zavření souboru<br /> <br /> <br /> == Virtuální FS ==<br /> <br /> [[Soubor:Fs.png]]<br /> <br /> Kód společný pro všechny typy FS, volán aplikacemi, udržuje informaci o otevřeném souboru, ověřuje přístupová práva.<br /> <br /> <br /> Typy FS<br /> * kontunuální alokace (jen u read-only médií - např CD)<br /> * seznam diskových bloků (blok obsahuje data a odkaz na další blok)<br /> * FAT<br /> <br /> <br /> <br /> == FAT ==<br /> <br /> <br /> Implementace:<br /> * Každému bloku odpovídá jedna položka v tabulce FAT<br /> * Položka FAT obsahuje číslo dalšího bloku souboru<br /> * Řetězec odkazů je ukončen speciální značkou, která není platným číslem bloku (-1)<br /> <br /> [[Soubor:Fat.jpg]]<br /> <br /> Nevýhodou FAT je velikost tabulky (80 GB disk, bloky 4 kB =&gt; 20 mil položek, každá položka alespoň 3 byty =&gt; 60 MB FAT)<br /> <br /> * FAT 12 - 12 bitů, 2&lt;sup&gt;12&lt;/sup&gt; = 4096 bloků, diskety<br /> * FAT 16 - 16 bitů, 2&lt;sup&gt;16&lt;/sup&gt; = 65536 bloků<br /> * FAT 32 - 2&lt;sup&gt;28&lt;/sup&gt; bloků, blok 4-32KB, cca 8TB<br /> <br /> <br /> <br /> == I-uzly ==<br /> <br /> S každým souborem sdružená datová struktura i-uzel. I-uzel obsahuje atributy souboru, diskové adresy prvních N bloků a jeden nebo více odkazů na diskové bloky obsahující další diskové adresy. Tradiční FS pro Linux a UNIX<br /> <br /> <br /> [[Soubor:I-uzly.jpg]]<br /> <br /> Výhoda: Po otevření souboru můžeme zavést i-uzel a případný blok obsahující další adresy do paměti =&gt; urychlý přístup k souboru<br /> <br /> Implementace adresářů: tabulka obsahující jméno souboru a číslo jeho i-uzlu.<br /> <br /> Info o volných blocích = seznam, jeho začátek je v superbloku na začátku partition<br /> <br /> Adresáře - většinou se jedná o speciální typ souboru<br /> <br /> Info o volných blocích v paměti - bitová mapa<br /> <br /> {{fav-kiv-bzinf}}<br /> <br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Ovl%C3%A1d%C3%A1n%C3%AD_perifern%C3%ADch_za%C5%99%C3%ADzen%C3%AD,_RAID 2014-02-20T06:48:53Z

<p>Acolade: kategorizace</p> <hr /> <div>Principy I/O software:<br /> # obsluha přerušení (nejnižší úroveň v OS)<br /> # ovladač zařízení<br /> # SW vrstva OS nezávislá na zařízení<br /> # uživatelský I/O SW<br /> <br /> [[Soubor:Obsluha-io.png]]<br /> <br /> <br /> == Obsluha přerušení ==<br /> <br /> * Řadič vyvolá přerušení ve chvíli dokončení I/O požadavku<br /> * Ovladač zadá I/O požadavek, usne, po příchodu přerušení ho obsluha vzbudí<br /> * Obsluha přerušení je časově kritická, musí být co nejkratší<br /> <br /> <br /> == Ovladače zařízení ==<br /> <br /> * Ovladače obsahují veškerý kód závislý na I/O zařízení, jediný zná HW podrobnosti<br /> * Ovladači předán příkaz vyšší vrstvou; pokud ještě obsluhuje předchozí požadavek, zařadí nový požadavek do fronty; zadá příkazy řadiči; zablokuje se do vykonání požadavku; po dokončení zkontroluje, zda nenastala chyba; předá výsledek vyšší vrstvě; spustí další požadavek<br /> <br /> <br /> == SW vrstva OS nezávislá na zařízení ==<br /> <br /> * Poskytuje I/O funkce společně pro všechna zařízení daného druhu<br /> * Definuje rozhraní s ovladači<br /> * Poskytuje jednotné rozhraní uživatelskému SW<br /> <br /> <br /> == I/O SW v uživatelském režimu ==<br /> <br /> * Programátor používá v programech I/O funkce nebo příkazy jazyka<br /> * Spooling = způsob obsluhy vyhrazených I/O v multiprogramovém systému (požadavky se zařadí do fronty a počkají až na ně přijde řada)<br /> <br /> <br /> <br /> == Funkce ovladače zařízení ==<br /> <br /> * ovladači předán příkaz vyšší vrstvou<br /> * požadavek zařazen do fronty (může ještě obsluhovat předchozí)<br /> * ovladač zadá příkazy řadiči (přijde na řadu), např. nastavení hlavy, přečtení sektoru<br /> * zablokuje se do vykonání požadavku (neblokuje při rychlých operacích, např. zápis do registru)<br /> * vzbuzení obsluhou přerušení (dokončení operace) - zkontroluje, zda nenastala chyba<br /> * pokud OK, předá výsledek (status + data) vyšší vrstvě<br /> <br /> <br /> <br /> == RAID 0 ==<br /> <br /> * není redundantní<br /> * ztrata 1 disku = ztrata celeho pole<br /> * duvod pouziti - vykon napr. strih videa<br /> <br /> <br /> == RAID 1 mirroring ==<br /> <br /> * zrcadleni na 2 disky stejnych kapacit<br /> * totozne informace<br /> * vypadek 1 disku - nevadi<br /> * jednoducha implementace - casto ciste sw<br /> * nevyhoda - vyuzijeme jen polovinu kapacity zapis - pomalejsi (2x) cteni - rychlejsi (radic - lze stridat pozadavky mezi disky)<br /> <br /> <br /> == RAID 5 ==<br /> <br /> * redundantni pole s distribuovanou paritou<br /> * minimialne 3 disky<br /> * rezie: 1 disk z pole n disku, pr. 5 disku 100GB, 400GB pro data<br /> * vypadek 1 disku nevadi cteni - vykon ok zapis - pomalejsi 1 zapis - cteni starych dat, cteni stare parity, vypocet nove parity, zapis novych dat, zapis nove parity<br /> <br /> <br /> == RAID 6 ==<br /> <br /> * RAID 5 + navic dalsi paritni disk<br /> * odolne proti vypadku dvou disku<br /> * rekonstrukce pole pri vypadku - trva dlouho po dobu rekonstrukce neni pole chraneno proti vypadku dalsiho disku, narocna cinnost - muze se objevit dalsi chyba, radic disk odpoji a ...<br /> <br /> <br /> == RAID 10 ==<br /> <br /> * kombinace RAID 0 (stripe) a RAID 1 (zrcadlo)<br /> * min. pocet disku 4 rezie 100% diskove kapacity navic<br /> * nejvyssi vykon v bezpecnych typech polich podstatne rychlejsi nez RAID 5, pri zapisu odolnost proti ztrate az 50% disku x RAID 5<br /> <br /> <br /> == Hot spare ==<br /> Disk který se aktivuje až při výpadku. Nahradí poškozený disk a pole je opět funkční (hot spare disk pak pouze vyměníme za nový)<br /> <br /> {{fav-kiv-bzinf}}<br /> <br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Algoritmy_nahrazov%C3%A1n%C3%AD_str%C3%A1nek_pam%C4%9Bti 2014-02-20T06:48:45Z

<p>Acolade: kategorizace</p> <hr /> <div>== Relokace při zavedení do paměti ==<br /> <br /> Program volá instrukci na adrese 66 ale sám v paměti běží až od adresy 1000. Tedy instrukce se nechází na adrese 1066. - Při zavedení programu do paměti provede Linker modifikaci, aby adresy souhlasily<br /> <br /> <br /> == Mechanismus báze a limitu (Dynamická relokace) ==<br /> <br /> Jednotka správy paměti (MMU) mezi procesorem a pamětí obsahuje dva registry:<br /> * báze - počáteční adresa oblasti<br /> * limit - velikost oblasti<br /> <br /> Dostává adresu od CPU a pževádí ji na adresu v paměti<br /> <br /> <br /> <br /> == Pojmy ==<br /> * virtuální paměť - stránky (pages) stejné délky<br /> * fyzická paměť - rámce (stejné délky)<br /> * rámec může obsahovat právě jednu stránku<br /> * na známém místě v paměti tabulka stránek, poskytuje mapování virtuálních stránek na rámce<br /> <br /> <br /> <br /> == Výpadek stránky ==<br /> * Pokud všechny rámce obsazené a nastane výpadek stránky, je nutné některou stránku vyhodit a rámec uvolnit (dojde k přerušení, zavede se požadovaná stránka, program může pokračovat v běhu)<br /> * Vyhození<br /> ** Pokud byla stránka modifikována, zapíše se na disk<br /> ** Pokud oproti kopii na disku nebyla modifikovaná, bude pouze uvolněna<br /> * Otázka - kterou stránku vyhodit?<br /> <br /> Tabulka stránek procesu - v MMU, obsahuje stránky daného procesu, mapuje číslo stránky na fyzickou adresu rámce, řeší realokaci a ochranu<br /> <br /> <br /> == Algoritmus FIFO ==<br /> <br /> * Udržujeme seznam všech stránek v pořadí, ve kterém byly zavedeny<br /> * Vyhazujeme nejstarší stránku (je možné, že se vyhodí stránka, která se bude brzy potřebovat)<br /> <br /> <br /> <br /> == Algoritmus MIN/OPT ==<br /> <br /> * V paměti je množina stránek, každá stránka je označena počtem instrukcí, po který se k ní nebude přistupovat<br /> * V okamžiku výpadku stránky se vybere stránka s nejvyšším označením<br /> * Algoritmus je optimální, tj. vybere se stránka, která bude zapotřebí nejvzdáleněji v budoucnosti<br /> * Není realizovatelný (neexistuje způsob, jakým by OS mohl zjistit, která stránka bude zapotřebí jako příští)<br /> <br /> <br /> <br /> == Algoritmus Least Recently Used ==<br /> <br /> nejdele nepouzita (pohled do minulosti)<br /> <br /> * princip lokality<br /> ** stranky pouzivane v poslednich instrukcich se budou pravdepodobne pouzivat i v nasledujicich<br /> ** pokud se stranka dlouho nepouzivala, pravdepodobne nebude brzy zapotrebi<br /> <br /> Vyhazovat zbozi, na kterem je v prodejne nejvice prachu = nejdele nebylo pozadovano<br /> <br /> * Obtizna implementace<br /> * sw reseni (neni pouzitelne)<br /> ** seznam stranek v poradi referenci<br /> ** vypadek - vyhozeni stranky ze zacatku seznamu<br /> ** zpomaleni cca 10x, nutna podpora hw<br /> * hw reseni - citac<br /> ** MMU obsahuje citac (64bit), pri kazdem pristupu do pameti zvetsen<br /> ** kazda polozka v tabulce stranek - pole pro ulozeni citace<br /> ** odkaz do pameti<br /> ** obsah citace se zapise do polozky pro odkazovanou stranku<br /> ** vypadek stranky - vyhodí se stranka s nejnizsim cislem<br /> <br /> Realizece čítače pomocí matice<br /> <br /> <br /> == Algoritmus Not-Recently-Used ==<br /> <br /> * Bit R - nastaven na 1 při čtení nebo zápisu do stránky<br /> * Bit M - nastaven na 1 při zápisu do stránky; označuje, že se stránka má při vyhození zapsat na disk<br /> <br /> Na začátku mají všechny stránky R=0, M=0, bit R je OS nastavován periodicky na 0<br /> <br /> 4 kategorie:<br /> * Třída 0: R=0, M=0<br /> * Třída 1: R=0, M=1<br /> * Třída 2: R=1, M=0<br /> * Třída 3: R=1, M=1<br /> <br /> Algoritmus vyhodí stránku z nejnižší neprázdné třídy, výběr mezi stránkami ve stejné třídě je náhodný<br /> Jednoduchý, efektivně implementovatelný, ale nevýkonný<br /> <br /> (R = referenced)<br /> <br /> <br /> == Algoritmus Second Chance ==<br /> <br /> * Vychází z algoritmu FIFO<br /> * Vyhledává nejstarší stránku, která nebyla referencována v poslední době<br /> * Pokud byly všechny referencovány =&gt; FIFO<br /> <br /> Snaží se zabranit vyhozeni casto pouzivane - dle bitu R nejstarsi stranky R = 0 ... stranka je nejstarsi, nepouzivana, vyhodime. Pokud R = 1 ... nastavme<br /> R=0, presuneme na konec seznamu stranek (jako by byla nove zavedena) a vezmeme další v pořadí.<br /> <br /> [[Soubor:Second-chance.jpg]]<br /> <br /> <br /> == Algoritmus Clock ==<br /> <br /> Optimalizace datovych struktur algoritmu Second Chance<br /> * Stranky udrzovany v kruhovem seznamu<br /> * Ukazatel na nejstarsi stranku { &quot;rucicka hodin\<br /> * Vypadek stranky { najit stranku k vyhozeni<br /> * Stranka kam ukazuje rucicka<br /> ** ma-li R=0, stranku vyhodime a rucicku posuneme o jednu pozici<br /> ** ma-li R=1, nastavime R na 0, rucicku posuneme o 1 pozici, opakovani,..<br /> * Od SC se lisi pouze implementaci<br /> * Varianty Clock pouzivaji napr. BSD UNIX<br /> <br /> <br /> == Algoritmus Aging ==<br /> <br /> * Každá položka má pole „stáří“, na počátku = 0<br /> * Při každém přerušení časovače - posun pole „stáří“ o 1 bit vpravo, zleva se přidá hodnota bitu R, nastavení R na 0 <br /> * Při výpadku stránky se vyhodí stránka, jejíž pole „stáří“ má nejnižší hodnotu<br /> <br /> {{fav-kiv-bzinf}}<br /> <br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Spr%C3%A1va_hlavn%C3%AD_pam%C4%9Bti,_metody_p%C5%99id%C4%9Blov%C3%A1n%C3%AD_pam%C4%9Bti,_virtu%C3%A1ln%C3%AD_pam%C4%9B%C5%A5 2014-02-20T06:48:36Z

<p>Acolade: kategorizace</p> <hr /> <div>Ideál programátora<br /> * Pameť nekonecně velká, rychlá, levná<br /> * Zároveň persistentní (uchovává obsah po vypnutí)<br /> * Bohužel neexistuje<br /> <br /> Reálný počítač - hierarchie paměti (&quot;pyramida&quot;)<br /> # Registry CPU<br /> # Malé množství rychlé cache paměti<br /> # Stovky MB až gigabajty RAM paměti<br /> # GB na pomalých, levných, persistentních discích <br /> <br /> <br /> Modul pro spravu pameti<br /> * informace o prideleni pameti<br /> * ktera cast je volna pridelena (a kteremu procesu)<br /> * pridelovani pameti na zadost<br /> * uvolneni pameti, zarazeni k volne pameti<br /> * odebira pamet' procesum<br /> * ochrana pameti<br /> ** pristup k pameti jineho procesu<br /> ** pristup k pameti OS<br /> <br /> Funkce MMU (memory managment unit)<br /> * Dostava adresu od CPU, prevadi na adresu do fyzicke pameti<br /> * Nejprve zkontroluje, zda adresa neni vetsi nez limit Ano - vyjimka, Ne - k adrese pricte bazi<br /> * Pokud baze 1000, limit 60<br /> ** Adresa 55 - ok, vysledek 1055<br /> ** Adresa 66 - není ok, vyjimka<br /> <br /> Tri varianty rozdeleni pameti<br /> * OS ve spodni casti adresniho prostoru v RAM (minipocitace)<br /> * OS v horni casti adresniho prostoru v ROM (zapouzdrene 2. systemy)<br /> * OS v RAM, ovladace v ROM (PC { MS DOS v RAM, BIOS v 3. ROM)<br /> <br /> <br /> <br /> <br /> Část OS, která spravuje paměť, se nazývá správce paměti<br /> * Udržuje informaci, které části paměti se používají a které jsou volné<br /> * Alokuje paměť procesům podle potřeby<br /> * Zařazuje paměť do volné paměti po uvolnění procesem<br /> <br /> * Jednoprogramové systémy bez odkládání a stránkování<br /> ** Nejjednodušší - spouštíme pouze jeden program v jednom čase<br /> ** Dovoluje procesu použít veškerou paměť, kterou nepotřebuje OS<br /> ** Po skončení procesu je možné spustit další proces<br /> * Multiprogramování s pevným přidělením paměti<br /> * Nejjednodušší schéma = rozdělit paměť na n oblastí (mohou být i různé velikosti)<br /> ** V historických systémech se provádělo ručně při startu zdroje<br /> ** Po načtení úlohy je obvykle část oblasti nevyužitá<br /> ** Snaha umístit úlohu do nejmenší oblasti, do které se vejde<br /> * Multiprogramování s proměnnou velikostí oblasti<br /> * Každé úloze je přidělena paměť podle požadavku<br /> * Obsazení paměti se postupně mění, jak úlohy přicházejí a končí<br /> * Zlepšuje využití paměti<br /> * Postupem času může vzniknout mnoho malých volných oblastí<br /> * OS musí vědět, která paměť je volná a která alokovaná<br /> <br /> <br /> == Nejpoužívanější způsoby správy paměti ==<br /> níže<br /> <br /> <br /> == Správa paměti pomocí bitových map ==<br /> <br /> * Paměť rozdělena do alokačních jednotek stejné délky<br /> * S každou alokační jednotkou sdružen jeden bit (0 = volno, 1 = obsazeno), tyto bity jsou pohromadě v bitové mapě<br /> ** menší alokační jednotky = větší bitmapa<br /> ** Větší alokační jednotky = více nevyužité paměti, protože velikost procesu nebude přesně násobek alokační jednotky<br /> * Výhoda - konstantní velikost bitmapy<br /> * Nevýhoda - pokud požadujeme úsek paměti velikosti N alokačních jednotek, musí se v bitmapě vyhledat N po sobě následujících nulových bitů (drahá operace)<br /> <br /> <br /> == Správa paměti pomocí seznamů ==<br /> <br /> * Myšlenka udržovat seznam alokovaných a volných oblastí<br /> * Každá položka seznamu obsahuje:<br /> ** Informaci, zda se jedná o proces nebo díru (P nebo H)<br /> ** Počáteční adresu oblasti<br /> ** Délku oblasti<br /> <br /> * Práce se seznamem:<br /> ** Pokud proces skončí, nahradí se dírou<br /> ** Pokud jsou vedle sebe dvě díry, sloučí se<br /> * Seznam je dobré mít seřazený podle počáteční adresy oblasti<br /> * zároveň je seznam obousměrný, takže se snadno vrací<br /> <br /> Možnosti alokace:<br /> * Algoritmus first fit<br /> ** Prohledávání seznamu, dokud se nenajde dostatečně velká díra<br /> ** Rychlý<br /> ** díra se rozdělí na proces a zbytek díry<br /> <br /> * Algoritmus next fit<br /> ** Prohledávání začne tam, kde skončilo předchozí<br /> ** o trochu pomalejší než first-fit<br /> <br /> * Algoritmus best fit<br /> ** Prohledá celý seznam, vezme nejmenší díru, do které se proces vejde<br /> ** Pomalejší, protože prohledává celý seznam<br /> ** zase ale najde nejlepší místo (byť na druhou stranu pak zbyte spousta malých nepoužitelných děr)<br /> <br /> Možná vylepšení<br /> * oddělěné seznamy děr a perocesů (rychlejší alokace, pomalejší dealokace<br /> * seznam děr seřazený podle velikosti (rychlé best fit, opět náročná dealokace)<br /> * místo samostatného seznamu děr lze využít samotné díry, které na sebe odkazují - úspora paměti<br /> <br /> == Mechanismus „buddy system“ ==<br /> <br /> [[Soubor:Buddy-system.jpg]]<br /> <br /> * Mějme seznamy volných bloků velikosti 1,2,4,8,16 … alokačních jednotek až do seznamu bloků velikosti celé paměti<br /> * Na začátku veškerá paměť volná, všechny seznamy jsou prázdné kromě seznamu obsahující 1 položku velikosti paměti<br /> * Přijde-li požadavek, zaokrouhlí se nahoru na mocninu 2<br /> * Blok se rozdělí na 2 bloky, pokud ještě moc velké, jeden z nich se zase rozdělí na 2 bloky atd.<br /> * Uvolnění paměti: pokud jsou volné oba sousední bloky stejné velikosti, spojí se do jednoho<br /> * Neefektivní ve využití paměti, ale rychlý<br /> <br /> <br /> Příklady použití:<br /> * Buddy system - jádro Linuxu, běží ve fyzické paměti<br /> * First fit, Next fit - malloc v C<br /> * Bitová mapa - SWAP v Linuxu<br /> <br /> <br /> <br /> == Virtuální paměť ==<br /> <br /> * Problém, že programy jsou větší než dostupná fyzická paměť<br /> * Chceme, aby ve skutečné paměti byla realizovaná pouze část adresového prostoru, zbytek může být odložen na disku<br /> * Procesor používá tzv. virtuální adresy<br /> * Pokud je požadovaná část virtuálního paměťového prostoru ve fyzické paměti, MMU převede virtuální adresu na fyzickou<br /> * Pokud není ve fyzické paměti, OS jí musí přečíst z disku<br /> * Většina systémů virtuální paměti používá techniku nazývanou stránkování<br /> <br /> <br /> {{fav-kiv-bzinf}}<br /> <br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Pl%C3%A1nov%C3%A1n%C3%AD_proces%C5%AF_v_interaktivn%C3%ADch_syst%C3%A9mech 2014-02-20T06:48:24Z

<p>Acolade: kategorizace</p> <hr /> <div>Základní stavy procesu<br /> * běžící<br /> * připravený - čeká na CPU<br /> * blokovaný - čeká na zdroj nebo zprávu<br /> * novy (new) - proces byl právě vytvořen<br /> * ukončený (terminated) - proces byl ukončen<br /> <br /> Správce procesů - udržuje tabulku procesů. Záznam o konkretním procesu - PCB (Process Control Block) - souhrn dat potrebnych k řízení procesu.<br /> <br /> Plánovač vs. dispatcher<br /> <br /> * dispatcher předává řízení procesu vybranému short time planovacem<br /> ** prepnuti kontextu<br /> ** prepnuti do user modu<br /> ** skok na vhodnou instrukci daneho programu<br /> * vice pripravenych procesu k behu { planovac vybere, ktery spusti jako prvni<br /> * planovac procesu (scheduler) - pouziva planovaci algoritmus (scheduling algorithm)<br /> * Preemptivni vs. non-preemptive planovani<br /> <br /> <br /> <br /> == Plánování v interaktivních systémech ==<br /> - preemptivní<br /> <br /> * Základní problém - každý proces je jedinečný a nepredikovatelný, nedá se říci, jak dlouho poběží, než se zablokuje<br /> * Aby proces neběžel příliš dlouho, má počítač vestavěné hodiny, které provádějí pravidelné přerušení<br /> * Při přerušení se vyvolá obslužný podprogram přerušení v jádře<br /> * OS rozhodne, zda dovolí procesu pokračovat nebo zda dá CPU jinému procesu<br /> <br /> <br /> <br /> == Algoritmus cyklické obsluhy (Round RObin) ==<br /> <br /> * Každému procesu je přiřazen časový interval = časové kvantum, po které může běžet<br /> * Pokud běží ještě na konci kvanta, je provedena preempce a je naplánován a spuštěn další připravený proces<br /> * Pokud proces skončil, nebo se zablokoval ještě před spotřebováním časového kvanta, je také naplánován a spuštěn další připravený proces<br /> * Délka časového kvanta:<br /> ** Krátké: vysoká režie<br /> ** Dlouhé: vyšší efektivita, může zhoršovat dobu odpovědi<br /> * znevýhodnění I/O vázaných úloh, protože zpravidla využijí pouze malou část kvanta a zablokují se (výpočetně vázané úlohy jsou zvýhodněné)<br /> <br /> <br /> == Prioritní plánování ==<br /> <br /> * Interaktivní procesy mohou mít vyšší prioritu než procesy běžící na pozadí<br /> ** Staticky - např. při startu procesu<br /> ** Dynamicky - např. pokud mají I/O procesy vyšší prioritu, budou se moci po krátkém použití CPU opět zablokovat. S délkou běhu klesá dynamická priorita<br /> * celková priorita = statická + dynamická<br /> * rozdělení procesů do priotitních tříd, v nich je využíváno round robin<br /> <br /> <br /> <br /> == Plánovač spravedlivého sdílení ==<br /> <br /> * Přidělovat čas každému uživateli proporciálně bez ohledu na to, kolik má procesů<br /> <br /> <br /> == Plánování pomocí loterie ==<br /> <br /> * Procesy obdrží tikety (losy)<br /> * Plánovač vybere náhodně jeden tiket<br /> * Vítězný proces obdrží cenu - 1 kvantum času na CPU<br /> * Důležitější procesy mohou obdržet více tiketů, aby se zvýšila jejich šance na výhru<br /> * Spolupracující procesy si mohou předávat losy<br /> <br /> <br /> == Plánování vláken ==<br /> Buď jsou vlákna plánována v OS nebo ve vlastním procesu (obvykle pomocí RR)<br /> <br /> <br /> {{fav-kiv-bzinf}}<br /> <br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Pl%C3%A1nov%C3%A1n%C3%AD_%C3%BAloh_a_proces%C5%AF_v_d%C3%A1vkov%C3%BDch_syst%C3%A9mech 2014-02-20T06:48:17Z

<p>Acolade: kategorizace</p> <hr /> <div>* Non-preemtivní plánování: proces si podrží kontrolu nad CPU dokud se jí nevzdá<br /> * Preemtivní - proces lze přerušit během CPU burstu a naplánovat jiný<br /> <br /> Bere se ohled na:<br /> * průchodnost (počet úloh dokončených za časovou jednotku)<br /> * průměrnou dobu obrátky (průměrná doba od zadání úlohy do systému do dokončení úlohy)<br /> * využití CPU<br /> <br /> == First-Come First-Served (FCFS) ==<br /> <br /> * Někdy používán název FIFO<br /> * Zpracování podle času příchodu úlohy, „kdo dřív přijde, ten dřív mele“<br /> * Nepreemptivní FCFS je nejjednodušší plánovací algoritmus (úloha běží dokud neskončí)<br /> * Je spravedlivý<br /> * Během I/O operací se CPU nevyužívá, ale přesto je blokováno stávajícím procesem<br /> <br /> == Shortest Job First (SJF) ==<br /> <br /> * Předpoklad, že je předem známá doba vykonávání úlohy<br /> * Nepreemptivní, jedna fronta příchozích úloh, plánovač vybere vždy úlohu s nejkratší dobou běhu<br /> * Nevýhodou je, že na dlouho trvající úlohy se nemusí vůbec dostat<br /> <br /> == Shortest Remaining Time (SRT) ==<br /> <br /> * Preemptivní varianta SJF<br /> * Plánovač vždy vybere úlohu, jejíž zbývající doba běhu je nejkratší<br /> * Např. právě prováděné úloze to bude trvat 10 min., do systému přijde úloha trvající 1 minutu - systém prováděnou úlohu pozastaví a nechá běžet novou úlohu<br /> * Problém: možnost vyhladovění úloh<br /> <br /> == Multilevel Feedback ==<br /> <br /> * N rozdílných prioritních úrovní, každá úroveň má svou frontu úloh<br /> * Úloha vstoupí do systému s nejvyšší prioritou<br /> * Na každé prioritní úrovni je stanoveno maximu času CPU, které může úloha na této úrovni obdržet<br /> ** Pokud úloha překročí limit, její priorita se sníží<br /> ** Na nejnižší úrovni může proces běžet neustále nebo může být překročení považováno za chybu<br /> * Procesor obsluhuje nejvyšší neprázdnou frontu<br /> * Výhoda: rozlišuje mezi I/O a CPU úlohami (upřednostňuje I/O)<br /> <br /> {{fav-kiv-bzinf}}<br /> <br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Klasick%C3%A9_probl%C3%A9my_meziprocesov%C3%A9_komunikace_%E2%80%93_producent-konzument_aj. 2014-02-20T06:48:10Z

<p>Acolade: kategorizace</p> <hr /> <div>Meziprocesova komunikace: // tady by to chtělo rozvést a doplnit...<br /> * Predavani zprav<br /> * Primitiva send, receive<br /> * Mailbox, port<br /> * RPC<br /> * Ekvivalence semaforu, zprav, ...<br /> * Bariera, problem vecericich filozofu<br /> <br /> <br /> <br /> Problem sdilene pameti<br /> *umisteni objektu ve sdilene pameti<br /> * Bezpecnost - globalni data pristupna kteremukoliv procesu bez ohledu na semafor<br /> * Procesy bezi na ruznych strojich, komunikuji spolu po siti Reseni - predavani zprav<br /> <br /> <br /> == Predavani zprav ==<br /> <br /> * send, receive<br /> * Zavedeme 2 primitiva<br /> ** send (adresat, zprava) - odeslani zpravy<br /> ** receive (odesilatel, zprava) - prijem zpravy<br /> ** Send - Zprava (lib. datovy objekt) bude zaslana adresatovi<br /> ** Receive - Prijem zpravy od urceneho odesilatele Prijata zprava se ulozi do promenne &quot;zprava&quot;<br /> <br /> Synchronizace - blokující (synchronní) (recieve) / neblokující (asynchronní) (send)<br /> <br /> * blokující send<br /> ** čeká na převzetí správy příjemcem<br /> * neblokující send<br /> ** vrací se ihned po odeslání zprávy<br /> ** většina systémů<br /> * blokující receive<br /> ** není-li ve frontě žádná zpráva, zablokuje se<br /> ** většina systémů<br /> * neblokující receive<br /> ** není-li zpráva, vrací chybu<br /> <br /> problémy, které nejsou u semaforů ani monitorů, zvláště při komunikaci po síti<br /> * ztráta zprávy (potvrzení o přijetí (acknowledgement))<br /> * ztráta potvrzení (číslování zpráv, duplicitní zprávy se ignorují)<br /> * problém autentizace (zprávy je možné šifrovat)<br /> <br /> lokální komunikace<br /> * rendezvous - eliminuje frontu zpráv, send zavolán dříve než receive – odesílatel zablokován, vyvolán send i receive – zprávu zkopírovat z odesílatele přímo do příjemce<br /> * využití mechanismu virtuální paměti paměť obsahující zprávu je přemapována z procesu odesílatele do procesu příjemce<br /> <br /> typické aplikace typu klient - server <br /> * WWW klient x WWW server (Apache, IIS)<br /> * účetní aplikace x databázový systém (Oracle, MySQL)<br /> <br /> <br /> == Volání vzdálených procedur (RPC - Remote Procedure Call) ==<br /> <br /> # Klient zavolá spojku klienta, reprezentující vzdálenou proceduru<br /> # Spojková procedura argumenty zabalí do zprávy, pošle ji serveru<br /> # Spojka serveru zprávu přijme, vezme argumenty a zavolá proceduru<br /> # Procedura se vrátí, návrat. hodnotu pošle spojka serveru zpět klientovi<br /> # Spojka klienta přijme zprávu obsahující návrat. hodnotu a předá ji volajícímu<br /> <br /> dnes nejpoužívanější jazyková konstrukce pro<br /> implementaci distribuovaných systémů a<br /> programů bez explicitního předávání zpráv<br /> <br /> <br /> <br /> == Ekvivalenty uvedených primitiv ==<br /> Lze implementovat semafory pomocí zpráv a zprávy pomocí semaforů<br /> <br /> Lze ukázat, že je možné implementovat<br /> * Semafory pomocí monitoru<br /> * Monitory pomocí semaforů<br /> <br /> <br /> <br /> == Bariéry ==<br /> <br /> [[Soubor:Bariera.png]]<br /> <br /> <br /> == Producent-konzument ==<br /> <br /> * Dva procesy sdílejí společnou paměť (buffer) pevné velikosti N položek<br /> * Jeden proces je producent - generuje nové položky a ukládá je do vyrovnávací paměti<br /> * Paralelně běží proces konzument, který data vyjímá a spotřebovává<br /> * Procesy mohou běžet různými rychlostmi =&gt; musí být zabezpečeno, aby nedošlo k přetečení/podtečení:<br /> ** Konzument musí být schopen čekat na producenta, nejsou-li data<br /> ** Producent musí být schopen čekat na konzumenta, je-li buffer plný<br /> <br /> Klasicky se zde sdílená paměť řeší pomocí pole, kde se z jedné strany položky přidávají a z druhé odebírají. Index kam zapisovat/odebírat počítáme modulo velikost pole. Kolizím zabráníme pomocí dvou semaforů, kde jeden obsahuje informaci o počtu plných prvků pole (f) a druhý o počtu prázdných prvků (e).<br /> * přidání prvku: P(e), V(f)<br /> * odebrání prvku: P(f), V(e)<br /> <br /> <br /> == Problém večeřících filosofů ==<br /> <br /> * 5 filosofů sedí kolem kulatého stolu<br /> * Každý filosof má před sebou talíř se špagetami<br /> * Mezi každými dvěma talíři je vidlička<br /> * Špagety jsou tak klouzavé, že filosof potřebuje 2 vidličky, aby mohl jíst<br /> * Když filosof dostane hlad, pokusí se vzít 2 vidličky; pokud uspěje, nějakou dobu jí, pak položí vidličky a pokračuje v přemýšlení<br /> * Problémy: uvíznutí(deadlock) (všichni filozofové zvednou levou vidličku, žádný z nich už nemůže pokračovat), vyhladovění (pokud by filozofové vzali najednou levou vidličku, budou běžet cyklicky - vidí, že pravá není volná, položí…)<br /> * Řešení - Dijkstra (pomocí semaforů)<br /> <br /> == Problém čtenářů a písařů ==<br /> <br /> * Představme si velkou databázi, množina procesů se pokouší souběžně číst a zapisovat<br /> * Více požadavků čtení - akceptovatelné<br /> * Při zápisu nesmí nikdo jiný přistupovat, ani žádní čtenáři<br /> * První čtenář, který dostane přístup do databáze, provede P(w), další pouze zvětšují čítač<br /> * Po skončení čtenáři zmenšují čítač, poslední provede V(w)<br /> * Semafor w zabrání vstupu písaře, pokud jsou čtenáři<br /> * Semafor w také zabrání vstupu čtenářům, je-li písař<br /> * toto je s předností čtenářů<br /> <br /> * nebo to jde udělat tak, že když chce vstoupit písař, tak už tam nepustí další čtenáře (s předností písařů)<br /> <br /> <br /> == Problémy ==<br /> <br /> <br /> * Uvíznutí (Deadlock) - cyklické čekání dvou či více procesů na událost, kterou může vyvolat pouze některý z nich, nikdy k tomu však nedojde<br /> * Vyhladovění (starvation) - proces se nedostane k požadovaným zdrojům<br /> <br /> <br /> {{fav-kiv-bzinf}}<br /> <br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Probl%C3%A9m_uv%C3%ADznut%C3%AD_proces%C5%AF,_graf_alokace_zdroj%C5%AF 2014-02-20T06:47:22Z

<p>Acolade: kategorizace</p> <hr /> <div>V množině procesů nastalo uvíznutí, jestliže každý proces množiny čeká na událost, kterou může způsobit pouze jiný proces množiny. Protože všechny čekají, žádný z nich událost nevygeneruje, nevzbudí jiný proces.<br /> <br /> Podmínky vzniku uvíznutí (musejí být splněny všechny 4, 1-3 jsou předpoklad pro 4):<br /> * Vzájemné vyloučení: každý zdroj je buď dostupný, nebo je výhradně přiřazen právě jednomu procesu<br /> * „hold and wait“: proces držící výhradně přiřazené zdroje může požadovat další zdroje<br /> * Nemožnost odejmutí: jednomu přiřazené zdroje nemohou být procesu násilně odejmuty<br /> * Cyklické čekání: musí být cyklický řetězec dvou nebo více procesů, kde každý z nich čeká na zdroj držený dalším členem<br /> <br /> * tyto 4 podmínky mohou být modelovány pomocí orientovaných grafů = graf alokace zdrojů<br /> * graf má 2 typy uzlů:<br /> ** proces - zobrazujeme jako kruh<br /> ** zdroj - zobrazujeme jako čtverec<br /> * význam hran:<br /> ** od zdroje k procesu: zdroj držen procesem<br /> ** od procesu ke zdroji: proces je blokován čekáním na zdroj<br /> * cyklus v grafu je nutnou a postačující podmínkou pro vznik uvíznutí<br /> <br /> [[Soubor:Alokace-zdroju.jpg]]<br /> <br /> Strategie zacházení s uvíznutím:<br /> # Ignorování = „pštrosí algoritmus“<br /> # Detekce a zotavení (odejmutí zdroje, zrušení změn, zrušení procesu)<br /> # Dynamické zabrání (pečlivá alokace zdrojů - systém rozhodne zda je bezpečné požadovaný zdroj přidělit) - mělo by předejít uvíznutí (bankéřův algoritmus)<br /> # Prevence pomocí strukturální negace jedné z podmínek pro vznik uvíznutí<br /> <br /> {{fav-kiv-bzinf}}<br /> <br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Monitory 2014-02-20T06:47:15Z

<p>Acolade: kategorizace</p> <hr /> <div>Monitor je synchronizační primitivum, které se používá pro řizeni přístupu ke sdíleným prostředkům. Jeho zvláštností<br /> je, že jde o speciální konstrukci programovacího jazyka (musí ho tedy implementovat překladač), typicky implementovanou pomocí jineho synchronizačního primitiva. Výhodou monitoru oproti jiným primitivum je jeho<br /> vysokoúrovňovost - snadněji se používá a je bezpečnější. Při jeho použití je méně pravděpodobné, že programátor<br /> udělá chybu.<br /> <br /> <br /> * Monitor je speciální typ modulu, ve kterém jsou sdružena data a procedury, které s nimi mohou manipulovat<br /> * Monitory musí umět rozpoznat překladač a přeložit je do odpovídajícího kódu<br /> * Procesy mohou volat procedury monitoru, ale nemohou přímo přistupovat k datům monitoru<br /> * V monitoru může být v jednu chvíli AKTIVNÍ pouze jeden proces; ostatní jsou při pokusu o vstup do monitoru pozastaveny.<br /> * Monitory poskytují speciální typ proměnné nazývané podmínka<br /> * Podmínky mohou být definovány a použity pouze uvnitř monitoru<br /> * Nad podmínkami jsou definovány dvě operace:<br /> ** c.wait - volající bude pozastaven nad podmínkou c. Pokud je některý proces připraven vstoupit do monitoru, bude mu to dovoleno<br /> ** c.signal - pokud existuje jeden nebo více procesů pozastavených nad podmínkou c, reaktivuje jeden z pozastavených procesů, tj. bude mu dovoleno pokračovat v běhu uvnitř monitoru pokud nad podmínkou nespí žádný proces, nedělá nic<br /> <br /> Pozor, pokud by signál pouze vzbudil proces, běžely by v monitoru dva.<br /> Možná řešení:<br /> * Hoare - proces volající c.signal se pozastaví a vzbudí se až poté co předchozí rektivovaný proces opustí monitor nebo se pozastaví<br /> * Hansen - Signal smí být uveden pouze jako poslední příkaz v monitoru. Po volání signal musí proces opustit monitor<br /> <br /> V Javě jsou monitory implementovány pomocí klíčového slova synchronized. Zde je problém více vláken v monitoru vyřešen tak, že čekající může běžet až poté, co proces volající signál opustí monitor.<br /> <br /> {{fav-kiv-bzinf}}<br /> <br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Semafory,_jejich_pou%C5%BEit%C3%AD_a_implementace 2014-02-20T06:47:08Z

<p>Acolade: kategorizace</p> <hr /> <div>Semafor = proměnná, obsahuje nezáporné celé číslo<br /> <br /> Semaforu, lze přiřadit hodnotu pouze při deklaraci<br /> <br /> Nad semafory pouze operace P(s) a V(s):<br /> * Operace P(S): pokud S&gt;0, sníží S o 1, jinak pozastaví proces<br /> * Operace V(S): pokud je nad semaforem S zablokovaný jeden nebo více procesů, vzbudí jeden z nich (náhodně), jinak zvýší S o 1<br /> <br /> Operace P i V jsou nedělitelné (atomické) akce, tj. jakmile započne akce nad semaforem, nikdo k němu nemůže přistoupit. Když se několik procesů pokouší přistoupit současně ke stejnému semaforu, operace se provedou sekvenčně v libovolném pořadí.<br /> <br /> Vzájemné vyloučení pomocí semaforů:<br /> * Vytvoříme semafor s počáteční hodnotou 1<br /> * Před vstupem do KS voláme P(s), po vystoupení V(s)<br /> * Je-li libovolný proces v KS, je s=0, jinak s=1<br /> <br /> Implementace<br /> * Procesům poskytneme možnost se pozastavit při operaci P<br /> * Aktivace operací V<br /> <br /> <br /> S každým semaforem s je sdruženo:<br /> * Celočíselná proměnná s.c, dovolíme jí nabývat i záporných hodnot, pak absolutní hodnota s.c vyjadřuje počet blokovaných procesů<br /> * Binární semafor s.mutex (mutual exclusion) pro vzájemné vyloučení při operaci nad semaforem<br /> * Seznam blokovaných procesů s.L<br /> <br /> Proces, který nemůže dokončit operaci P bude zablokován a uložen do seznamu blokovaných procesů. Pokud při operaci V není seznam prázdný, vybere se ze seznamu jeden proces a odblokuje se.<br /> <br /> Pozor, mutex není binární semafor. Mutex může na rozdíl od semaforu odemknout pouze vlákno, které ho zamklo.<br /> <br /> {{fav-kiv-bzinf}}<br /> <br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Prost%C5%99edky_pro_synchronizaci_proces%C5%AF 2014-02-20T06:46:57Z

<p>Acolade: kategorizace</p> <hr /> <div>Zakázání přerušení<br /> * V systému se sdílením času přepíná CPU mezi procesy pouze jako důsledek přerušení<br /> * Zakážeme-li přerušení, k přepínání nedochází<br /> * Nejjednodušší řešení, možné pouze v jednoprocesorovém systému<br /> * Není dovoleno v uživatelském režimu<br /> <br /> Řešení s aktivním čekáním<br /> Základní předpoklady o systému:<br /> # Zápis a čtení ze společné datové oblasti jsou nedělitelné operace<br /> # Kritické sekce nemohou mít přiřazenou prioritu<br /> # Relativní rychlost procesů je neznámá<br /> # Proces se může pozastavit mimo kritickou sekci<br /> <br /> Průběžně se testuje, zra už může proces do kritické sekce vstoupit - plýtvání časem CPU<br /> <br /> <br /> Petersonovo řešení<br /> * Na začátku není v kritické sekci žádný proces<br /> * Proces 0 volá enter_CS(0)<br /> ** Nastaví interested[0]:=true, turn:=0;<br /> ** Protože interested[1]=false, nebude čekat ve smyčce<br /> * Pokud proces 1 volá enter_CS(1)<br /> ** Nastaví interested[1]:=true, turn:=1;<br /> ** Bude čekat ve smyčce, dokud se interested[0] nenastaví na false (voláním leave_CS(0))<br /> * Co kdyby oba procesy volaly enter_CS téměř současně?<br /> ** Oba nastaví interested na true<br /> ** Oba nastaví turn na své číslo; „téměř souběžný zápis“ se ale provede sekvenčně, tj. nejdříve nastaví turn jeden, hodnota bude přepsána druhým<br /> ** Oba se dostanou do while, proces 0 projde, proces 1 aktivně čeká<br /> <br /> <br /> Spin-lock s instrukcí TSL<br /> <br /> Většina současných počítačů má instrukci, která otestuje hodnotu a nastaví paměťové místo v jedné nedělitelné operaci (TSL - „Test and Set Lock“) - HW podpora<br /> <br /> * Proměnná zámek - na počátku 0<br /> * Proces, který chce vstoupit do KS otestuje<br /> ** Pokud 0 nastaví na 1 a vstoupí do KS<br /> ** Pokud 1 čeká<br /> * Problém časového souběhu (pokud by TSL nebyla atomická):<br /> ** Jeden proces přečte, vidí 0<br /> ** Druhý proces je naplánován, přečte, vidí 0, nastaví na 1, vstoupí do KS<br /> ** Po naplánování první zapíše 1 a máme 2 procesy v KS<br /> * Řešení vyžaduje HW podporu<br /> <br /> <br /> <br /> Další možnosti<br /> * [[Semafory, jejich použití a implementace|Semafory]]<br /> * Mutexy - někdy nepotřebujeme použít schopnost semaforů čítat, tj. stačila by nám pouze jejich schopnost zajistit vzájemné vyloučení =&gt; mutex<br /> * [[Monitory]]<br /> <br /> <br /> Předávání zpráv - primitiva send a receive<br /> # Čeká-li primitivum send na převzetí zprávy příjemcem, je blokující (synchronní). Ve většině systémů je neblokující.<br /> # Pokud při zavolání recese není ve frontě žádná zpráva, může se recese buď zablokovat, nebo se může vrátit s chybou. Ve většině systémů je blokující.<br /> <br /> <br /> {{fav-kiv-bzinf}}<br /> <br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Probl%C3%A9m_kritick%C3%A9_sekce 2014-02-20T06:46:49Z

<p>Acolade: kategorizace</p> <hr /> <div>== Časový souběh ==<br /> <br /> Pokud procesy sdílejí společnou paměť, kterou čtou a zapisují, může nastat časový souběh. Hledání časových souběhů v reálných programech není jednoduché, protože časový souběh se obvykle projevuje nedeterministicky a programy běží po většinu času bez problémů.<br /> <br /> Příklad - Přístup do souboru<br /> <br /> * 2 procesy chtějí vytvořit soubor a zapsat do něj<br /> * 1. proces – zjistí, že soubor není<br /> * ... přeplánování ...<br /> * 2. proces – zjistí, že soubor není, vytvoří a zapíše<br /> * 1. proces – pokračuje, vytvoří a zapíše znehodnotí činnost druhého procesu<br /> <br /> Řešení - časový souběh by nenastal, pokud by čtení+modifikace proběhli atomicky, tj. jako jedna nedělitelná operace. Zařídit HW většinou není praktické. SW řešení - v jednom okamžiku dovolíme číst a zapisovat společná data pouze jednomu procesu.<br /> <br /> == Kritická sekce ==<br /> <br /> = místo programu, kde je prováděn přístup ke společným datům<br /> <br /> Dobré řešení musí mít 3 vlastnosti:<br /> # Vzájemné vyloučení: žádné 2 procesy nesmějí být současně uvnitř své kritické sekce<br /> # Proces běžící mimo svou kritickou sekci nesmí blokovat jiné procesy<br /> # Žádný proces nesmí na vstup do své kritické sekce čekat nekonečně dlouho<br /> <br /> {{fav-kiv-bzinf}}<br /> <br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Paraleln%C3%AD_procesy,_prost%C5%99edky_pro_popis_paraleln%C3%ADch_proces%C5%AF,_vl%C3%A1kna 2014-02-20T06:46:43Z

<p>Acolade: kategorizace</p> <hr /> <div>* Všechen SW běžící na počítači je organizován jako množina sekvenčních procesů<br /> * Proces = běžící program včetně obsahu čítače instrukcí, registrů, proměnných, běží ve vlastní paměti<br /> * Koncepčně má každý proces vlastní virtuální CPU<br /> <br /> Při pseudoparalelním běhu je v jednu chvíli aktivní pouze jeden proces. Po nějakém čase se OS rozhodne pozastavit běh procesu a spustit běh dalšího. Po dostatečně dlouhém čase všechny procesy vykonají část své činnosti.<br /> <br /> <br /> == Základní stavy procesů ==<br /> <br /> Následující stavy procesů se vyskytují ve všech víceúlohových systémech:<br /> * vytvořený (created) - proces je vytvořen buď příkazem uživatele (u terminálu), nebo na žádost operačního systému o provedení služby, či na žádost jiného procesu (rodiče)<br /> * připravený (ready) nebo čekající (waiting) - připravený pro vstup do stavu běžící, čeká pouze na přidělení procesoru<br /> * běžící (running) - procesu je přidělen procesor a právě se provádí příslušné programy<br /> * blokovaný (blocked) - proces je převeden do tohoto stavu v případě, kdy čeká na dokončení nějaké vstupně-výstupní operace, případně na skončení jiného procesu, uvolnění zdroje, synchronizační primitivum a podobně<br /> * ukončený (terminated) - proces skončil<br /> <br /> [[Soubor:Stavy-procesu.jpg]]<br /> <br /> Lepší obrázek z přednášek:<br /> <br /> [[Soubor:Graf-stavu-procesu.png]]<br /> <br /> <br /> Precedenční grafy<br /> * Acyklický orientovaný graf<br /> * Běh procesu Pi je vyjádřen orientovanou hranou grafu<br /> * Vztahy mezi procesy znázorněny spojením hran<br /> <br /> Abstraktní primitiva fork, join a quit<br /> * Conway 1963<br /> * Jeden z prvních mechanismů, možnost obecného popisu paralelních aktivit<br /> * Funkce primitiv:<br /> **fork X - provedení primitiva „fork x“ způsobí spuštění nového vlákna od příkazu označeného návěštím x; nové vlákno bude běžet paralelně s původním vláknem.<br /> ** quit - ukončí vlákno<br /> ** join t, Y - atomicky provede: t:=t-1; if t = 0 then goto Y;<br /> * Abstraktní primitiva cobegin a coend<br /> ** Explicitně specifikuje sekvenci programu, která má být spuštěna paralelně<br /> ** Cobegin má formát:<br /> cobegin<br /> C1 || C2 || … || Cn<br /> coend<br /> <br /> * Výsledkem je vytvoření samostatného vlákna pro všechna Ci<br /> * Každé Ci běží nezávislé na ostatních vláknech v konstrukci cobegin / coend<br /> * Program pokračuje za coend až po skončení posledního Ci<br /> <br /> Vlákna<br /> * Vlakna v procesu sdileji adresni prostor, otevrene soubory (atributy procesu)<br /> * Vlakna maji soukromy citac instrukci, obsah registru, soukromy zasobnik<br /> * Mohou mit soukrome lokalni promenne<br /> * Puvodne vyuzivana zejmena pro VT vypocty na multiprocesorech (kazdé vlakno vlastni CPU, spolecna data)<br /> <br /> <br /> == PCB ==<br /> <br /> = process control block<br /> <br /> OS (konkrétně správce procesů) udržuje tabulku nazývanou tabulka procesů<br /> * PCB obsahuje všechny info potřebné pro opětovné spuštění procesu<br /> * Konkrétní obsah PCB – různý<br /> * Pole správy procesů, správy paměti, správy souborů<br /> <br /> Položky PCB<br /> * Identifikátor procesu, uživatele<br /> * Stavová informace procesoru (registry, PC, SP, styv CPU)<br /> * Plánovací parametry procesu<br /> * Odkazy na rodiče a potomky<br /> * Čas spuštení, čas spotřebovaný na CPU<br /> * Nastavení meziprocesorové komunikace<br /> * Popis paměti, data, zásobník<br /> * Otevřené soubory, aktuální pracovní adresář...<br /> <br /> PCB<br /> <br /> [[Soubor:Pcb.png]]<br /> <br /> == Vlákna ==<br /> <br /> Jeden proces se může skládat z jednoho nebo více vláken.<br /> <br /> Vlákna v procesu sdílejí adresní prostor, ale mají vlastní čítač instrukcí, obsah registrů, zásobník. Taky mohou mít soukromé lokální proměnné.<br /> <br /> * interaktivní procesy (něco beží na pozadí a zároveň probíhá komunikace s uživatelem)<br /> * www server (každý klient jedno vlákno)<br /> * textový procesor (vstup dat, formátoování textu)<br /> <br /> Multithreading - více vláken. Proces začíná s jedním vláknem, další si vytváří za běhu.<br /> <br /> Režije na vytvoření vlákna a přepnutí kontextu je menší než u procesů.<br /> <br /> Vlákna popisujeme pomocí Precedenčních grafů<br /> <br /> <br /> == Precedenční graf ==<br /> <br /> Acyklický orientovaný graf, popisuje vztahy mezi procesy.<br /> <br /> <br /> [[Soubor:Precedencni-grafy.png]]<br /> <br /> Lze také zapsat pomocí funkcí:<br /> * P(a,b) - paralelní běh 2 vláken (a,b)<br /> * S(a,b) - sériový běh 2 vláken (a,b)<br /> např: S (p1, S(P(p2, P(S(p3, P(p4,p5)), p6)), P(p7,p8))<br /> <br /> <br /> {{fav-kiv-bzinf}}<br /> <br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Proces,_implementace_procesu,_konstrukce_pro_vytv%C3%A1%C5%99en%C3%AD_proces%C5%AF 2014-02-20T06:46:40Z

<p>Acolade: kategorizace</p> <hr /> <div>Proces = program, který běží<br /> * Má vlastní adresový prostor, ve kterém běží<br /> * V adresním prostoru má kód spustitelného programu, data, zásobník<br /> * S procesem sdruženy registry a další informace potřebné k běhu programu<br /> * Stavy: běžící, připraven, blokován<br /> <br /> <br /> <br /> == Základní stavy procesů ==<br /> <br /> Následující stavy procesů se vyskytují ve všech víceúlohových systémech:<br /> * vytvořený (created) - proces je vytvořen buď příkazem uživatele (u terminálu), nebo na žádost operačního systému o provedení služby, či na žádost jiného procesu (rodiče)<br /> * připravený (ready) nebo čekající (waiting) - připravený pro vstup do stavu běžící, čeká pouze na přidělení procesoru<br /> * běžící (running) - procesu je přidělen procesor a právě se provádí příslušné programy<br /> * blokovaný (blocked) - proces je převeden do tohoto stavu v případě, kdy čeká na dokončení nějaké vstupně-výstupní operace, případně na skončení jiného procesu, uvolnění zdroje, synchronizační primitivum a podobně<br /> * ukončený (terminated) - proces skončil<br /> <br /> <br /> <br /> [[Soubor:Stavy-procesu.jpg]]<br /> <br /> <br /> == Implementace procesu ==<br /> <br /> OS udržuje tabulku nazývanou TABULKA PROCESŮ - každý proces v ní má položkou nazývanou PCB (Process Control Block). PCB obsahuje všechny informace, které musejí být uchovány, je-li proces přepnut ze stavu „běžící“ do „připraven“ nebo „blokován“ - tak aby bylo proces možné znovu spustit. Konkrétní obsah se liší mezi systémy, ale většina obsahuje:<br /> * Správa procesu<br /> ** Identifikátory<br /> ** Stavová informace procesoru<br /> ** Stav procesu<br /> ** Plánovací parametry procesu<br /> ** Odkazy na rodiče a potomky<br /> ** Nastavení meziprocesové komunikace<br /> * Správa paměti<br /> ** Popis paměti = ukazatel, velikost, přístupová práva<br /> ** Úsek paměti s kódem programu<br /> ** Data<br /> ** Zásobník<br /> * Správa souborů<br /> ** Prostředí (aktuální adresář, …)<br /> ** Otevřené soubory<br /> <br /> Konstrukce<br /> pid = fork();<br /> if (pid == 0)<br /> jsem potomek;<br /> else<br /> jsem rodič;<br /> <br /> {{fav-kiv-bzinf}}<br /> <br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Vyvol%C3%A1n%C3%AD_slu%C5%BEeb_OS,_zpracov%C3%A1n%C3%AD_p%C5%99eru%C5%A1en%C3%AD 2014-02-20T06:46:26Z

<p>Acolade: kategorizace</p> <hr /> <div>Většina moderních CPU: 2 řežimy:<br /> * Privilegovaný - režim jádra, všechny instrukce jsou povoleny, v tomto běží pouze OS<br /> * Uživatelský - některé instrukce (I/O) jsou zakázány, v tomto běží ostatní programy<br /> <br /> Aby uživ. aplikace mohla provádět zakázané instrukce, musí požádat OS o jejich provedení následujícím způsobem (Vyvolání služby):<br /> <br /> * Aplikace si uloži parametry pro službu na předem určené místo (registry, zásobník,...)<br /> * Zavolá metodu volání služby jádra (např. v C je to syscall( ))<br /> * Ta podle parametrů zjistí jaká složba je požadována, která přepne CPU do režimu jádra, a vyvolá obsluhu<br /> * Ta službu provede a při návratu do uživatelského programu přepne CPU zpět do uživatelského režimu<br /> <br /> [[Soubor:Vyvolani-sluzby.jpg]] <br /> <br /> Programovací jazyky skrývají volání funkcí jádra tak, aby vypadaly jako běžné knihovní funkce.<br /> <br /> <br /> == Zpracování přerušení ==<br /> <br /> Přerušení je událost, která pokud nastane, je třeba ji v krátkém čase obsloužit. Je tedy přerušeno vykonávání instrukcí, provedena obsluha události a po té se pokračuje v předchozí činnosti. Provedení tohoto je v režimu jádra. <br /> <br /> Druhy:<br /> * HW přerušení (vnější) - generuje jej I/O zařízení, asynchronně, například přijetí paketu, stisknutí klávesy,... Stará se o ně řadič přerušení (priority atd)<br /> * Vnitřní přerušení - generuje proces, například dělení nulou, výpadek stránky, ...<br /> * Softwarové - synchronní, generováno aplikací jako takovou, záměrně, volání služby OS je příkladem<br /> <br /> <br /> [http://cs.wikipedia.org/wiki/P%C5%99eru%C5%A1en%C3%AD Přerušení na Wiki]<br /> <br /> '''Vektor přerušení''' - ukazatel, kde pro daný typ přerušení (a jeho číslo) začíná program pro jeho obsluhu.<br /> <br /> Obsluha:<br /> * Přijde signalizace přerušení<br /> * Je dokončena právě prováděná instrukce v CPU<br /> * Adresa další instrukce je uložena na zásobník<br /> * Do PC (Program Counter - ukazatel CPU na další instrukci) je nastavena instrukce, na kterou ukazuje odpovídající vektor přerušení)<br /> * Přepnutí kontextu (Obsluha je samostatný proces)<br /> * Obsluha uloží stav registrů a obecně stav CPU do zásobníku<br /> * Provede obsluhu přerušení<br /> * Provede (I)RET<br /> * Plánovač opět přepne kontext podle dat v zásobníku a původní proces pokračuje v činnosti (kromě zpoždění tedy neví, že přerušení proběhlo, musí tedy naslouchat všem výstupům obsluh přerušení, které jej zajímají)<br /> <br /> {{fav-kiv-bzinf}}<br /> <br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Rozd%C4%9Blen%C3%AD_OS,_architektura_a_komponenty_OS._Z%C3%A1kladn%C3%AD_funkce_OS 2014-02-20T06:46:19Z

<p>Acolade: kategorizace</p> <hr /> <div><br /> <br /> == Rozdělení ==<br /> <br /> Podle úrovně sdílení CPU<br /> * Jednoprocesový - např. MS DOS; v daném čase je v paměti aktivní jeden program<br /> * Multiprocesový - např. UNIX, WinNT; aby se využilo systémových zdrojů (sdílení CPU, paměti) je v hlavní paměti více než jeden program. V současnosti nejčastěji v systémech pro více uživatelů.<br /> <br /> Podle typu interakce/požadavků na odezvu<br /> * Dávkový systém - uživatelské úlohy se zadávají jako sekvenční dávky, během zpracování není interakce mezi uživatelem a jeho úlohou.<br /> * Interaktivní - dovolí uživatelům interakce s jejich úlohami<br /> * OS reálného času - konkrétní aplikace mají přísné požadavky na čas odpovědi. OS se těmto požadavkům podřizují. Vhodné pro multimédia, virtuální realitu. 2 typy:<br /> ** Hard real time: zaručuje odezvu systému v ohraničeném čase<br /> ** Soft real time: RT úlohy mají prioritu před vším ostatním, avšak nezaručuje odezvu v ohraničeném čase. <br /> <br /> Dle velikosti HW<br /> * superpočítač<br /> * telefon<br /> * čipová karta<br /> <br /> Míra distribuovanosti<br /> * Klasické - centralizované 1 and more CPU<br /> * ParalelnÍ<br /> * SÍŤOVÉ<br /> * Distribuované virtuální uniprocesor - Uživatel neví kde běží programy, kde jsou soubory<br /> <br /> Další možnosti dělení OS:<br /> * podle počtu uživatelů<br /> ** jedno / více uživatelské<br /> * podle funkcí<br /> ** univerzální<br /> ** specializované<br /> <br /> == Architektura ==<br /> <br /> OS = jádro + systémové nástroje<br /> <br /> Dělíme na<br /> * Monolitické jádro – jádro je jeden funkční celek (GNU/Linux)<br /> * Mikrojádro – malé jádro, oddělitelné části pracují jako samostatné procesy v user space (GNU/Hurd)<br /> * Hybridní jádro - kombinace (Win XP, Win Vista...)<br /> <br /> '''Monolitické jádro'''<br /> * Jeden spustitelný soubor<br /> * Uvnitř moduly pro jednotlivé funkce (filesys, procesy)<br /> * Jeden program, řízení se předává voláním podprogramů<br /> * Příklady: UNIX, Linux, MS DOS<br /> <br /> Typickou součástí jádra je např. souborový systém<br /> <br /> Linux je monolitické jádro OS, s podporou zavádění<br /> modulů za běhu systému<br /> <br /> [[Soubor:Monoliticke-jadro.png]]<br /> <br /> '''Mikrojádro'''<br /> * Model klient – server<br /> * Většinu činností OS vykonávají samostatné procesy mimo jádro (servery, např. systém souborů)<br /> * Poskytuje pouze nejdůležitější nízkoúrovňové funkce<br /> ** Nízkoúrovňová správa procesů<br /> ** Adresový prostor, komunikace mezi adresovými prostory<br /> ** Někdy obsluha přerušení, vstupy/výstupy<br /> * Pouze mikrojádro běží v privilegovaném režimu<br /> ** Méně pádů systému<br /> <br /> Výhody<br /> * vynucuje modulární strukturu<br /> * Snadnější tvorba distribuovaných OS (komunikace přes síť)<br /> Nevýhody<br /> * Složitejší návrh systému<br /> * Režie<br /> Příklady: QNX, Hurd, OSF/1, MINIX, Amoeba<br /> <br /> [[Soubor:Mikrojadro.png]]<br /> <br /> == Komponenty OS ==<br /> * správa procesů<br /> * správa hlavní paměti<br /> * soubory<br /> * správa zařízení - I/O subsystém<br /> * síť (networking) .. viz KIV/UPS<br /> * ochrana a bezpečnost<br /> * uživatelské rozhraní<br /> <br /> <br /> <br /> * Procesy; proces = běžící program; potřebuje minimálně:<br /> ** Čas CPU = být vykonán<br /> ** Paměť = mít kde běžet<br /> ** Vstupy a výstupy = soubory a I/O zařízení<br /> * Správa hlavní paměti<br /> ** Alokace a dealokace paměti podle potřeby<br /> ** Udržuje informace, která část paměti je používána a kým<br /> * Soubory<br /> ** Vytváření/ rušení souborů/adresářů<br /> ** Mapování souborů na vnější paměť<br /> ** Rozvrhování diskových operací<br /> * I/O podsystém<br /> ** Správa paměti pro buffering, caching, spooling<br /> ** Společné rozhraní ovladačů zařízení<br /> ** Ovladače pro specifická zařízení<br /> * Síť<br /> * Ochrana a bezpečnost = ke zdrojům smí přistupovat pouze autorizované procesy<br /> * Uživatelské rozhraní - CLI, GUI<br /> <br /> <br /> {{fav-kiv-bzinf}}<br /> <br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Grafov%C3%A9_algoritmy_(cesta_%E2%80%93_Dijkstra,_Floyd-Warshal,_kostra_%E2%80%93_Prim-Jarnik),_reprezentace_grafu_(matice,_seznam_sousednosti),_z%C3%A1klady_kryptografie_(symetrick%C3%A9,_asymetrick%C3%A9_%C5%A1ifrov%C3%A1n%C3%AD) 2014-02-20T06:44:57Z

<p>Acolade: kategorizace</p> <hr /> <div>//Detaily viz PPA 11, 12, 13<br /> <br /> <br /> == Reprezentace grafu ==<br /> <br /> '''Seznam sousednosti''' - každý vrchol má seznam svých sousedů. Je-li graf neorientovaný, hrany jsou v seznamech dvakrát<br /> <br /> '''Matice sousednosti''' - matice v * v, kde v je pořet vrcholů, a v ní jsou '1' tam, kde je hrana. Na diagonále jsou smyčky, případně ohonocení vrcholů. Pro neorientovaný hraf je matice symetrická.<br /> <br /> Graf může mít v*v-1 hran, podle očekávaného počtu se tedy rozhodneme, kterou možnost zvolíme.<br /> <br /> <br /> == Dijkstrův algoritmus ==<br /> <br /> = algoritmus pro hledání nejkratší cesty v ohodnoceném hrafu grafu.<br /> <br /> - hrany mají kladné hodnocení<br /> <br /> - většinou se bavíme o neorientovaném grafu, funguje však i pro orientované<br /> <br /> - probírán 1000x, takže jen opakování:<br /> <br /> Máme ohodnocený graf a dva vrcholy, u a v, a hledáme cestu z u do v<br /> <br /> Začneme v u, a tomu přiřadíme vzdálenost 0<br /> <br /> Podíváme se na všechny okolní body všech již označených bodů<br /> <br /> Posuneme se na ten, který má nejkratší vzdálenost od u (tedy musíme do vzdálenosti připočítat i vzdálenost předchozího bodu od počátku. Tohle je extrémně důležité, protože jinak bychom nalezli MST (konkrétně primův algoritmus), a tomu přiřadíme vzdálenost odpovídající součtu vzdálenosti předchozího bodu (od u) a délky cesty tohoto bodu od jeho předchůdce.<br /> <br /> Opakujeme 3 a 4, dokud nenalezneme cílový bod v.<br /> <br /> kombinace BFS (pro zjištění všech okolních nejkratších cest) a DFS (pro posun po prvcích). Algoritmus zastaví, pokud najde žádanou cestu.<br /> <br /> '''Implementace'''<br /> <br /> tabulkou, kdy ke každému vrcholu zapisujeme vzdálenosti, vybíráme v každé řádce nejmenší a tu označíme. Vyhledávání minima by bylo však O(v) (projdeme všechny sousedy vrcholu a hledáme nejbližší) pro všechny hrany, tedy celkem O(v2)<br /> <br /> jinak, například pomocí prioritní fronty s možností úpravy. všechny nalezené a neoznačené okolní vrcholy umístíme do prioritní fronty s prioritou jejich vzdálenosti (opět jde o součet délky cesty do předchozího bodu a délky cesty od předchozího bodu do vkládaného bodu), vybereme zepředu fronty, ten prvek označíme, zapamatujeme si, odkud jsme na něj přišli pro pozdější rekonstrukci cesty, a vložíme jeho okolní vrcholy. pokud již ve frontě jsou, upravíme jejich prioritu, je li to nutné. Složitost, pokud je fronta implementována haldou, je O(h + v log v), h protože procházíme všechny hrany a v log v protože pro každý vrchol musíme haldu obnovit. <br /> <br /> <br /> == Floyd-Warshallův algoritmus ==<br /> <br /> = algoritmus pro hledání nejkratší cesty pro všechny páry (u, v) v grafu.<br /> <br /> - Rychlejší, než Dijsktra pro všechny výchozí body (Dijsktra najde od zadaného vrcholu všechny nejkratší cesty, pokud jej na cílovém vrcholu nezastavíme), pokud je graf hustý (tedy hran je v2) -&gt; Dijsktra by byl (pomocí haldy) O(h + v log v), tedy O(v2 + v log v), tedy horší než v3, při implementaci polem dokonce v4<br /> <br /> - Složitost O(v3)<br /> <br /> '''Algoritmus'''<br /> <br /> [[Soubor:Floyd-warshall-1.jpg]] <br /> <br /> Pracuje s maticí sousednosti w, kde jsou hrany označeny jejich délkou (cenou, vzdáleností, ...) a nehrany označeny nekonečnem.<br /> d je matice aktuálne spoctených nejkratších vzdáleností<br /> mezi je matice nejkratších mezicest, je nainicializována na -1 (null)<br /> <br /> V každém kroku algoritmu zjištuji, jestli existuje mezi vrcholy i,j kratší cesta pres vrchol k, pokud ano, nastavím vzdálenost v d[i][j] na novou velikost a do mezi[i][j] zaznamenám vrchol k. V podstatě procházím všechny buňky matice D v kříži, který protíná prvek (i, j). Pokud jsem dříve nalezl optimální cestu do bodu, je tato cesta ideální, pokud neexistuje cesta přímá. (Víme, že v bodě D[i,j] jsou na začátku všechny hrany. Může se ale stát, že existuje kratší cesta přes jiný vrchol, než po hraně v matici sousednosti. Kde tu cestu najdu? Buď končí ve vrcholu i, nebo ve vrcholu j, každopáně bude v řádce j, nebo sloupci i. a jde přes jiný vrchol. Pokud tedy znám cesty z tohoto vrcholu do ostatních vrcholů, můžu najít cestu z vrcholu i do jiného, třeba x, a z x do j tak, že délka z i -&gt; x + x -&gt; j je kratsí, než doposud nalezená nejkratší cesta)<br /> <br /> [[Soubor:Floyd-warshall-2.jpg]] <br /> <br /> i = 3, j = 4, tedy cesta z i do j. V matici sousednosti byla 10, ale pokud půjdeme z vrcholu 4 do vrcholu 1 a z něj do vrcholu 3, tato cesta bude kratší (9 &lt; 10). Do matice mezi si tedy uložíme vrchol 1 a v matici D (tato) změníme délu nejlepší cesty z i do j na 9 (tmavomodré pole)<br /> <br /> // Nechápu, proč je to v přednáškách vysvětleno tak přes ruku. Vždycky. Stačí vždy jen říct jak a proč, a je to hned jasné. Výpis programu v polopascalovskym kodu nikdo nechápe.<br /> <br /> <br /> == Prim-Jarníkův algoritmus ==<br /> <br /> = algoritmus pro řešení úlohy minimal spanning tree (MST), tedy problému, kdy pro zadaný graf ((ne)orientovaný, ohodnocený) hledáme kostru (strom), která bude mít nejmenší možné celkové ohodnocení (součet ohodnocení hran bude minimální)<br /> <br /> - užití - nejlevnější spojení všech uzlů grafu (elektrifikace domů, stavění silnic po povodni, ...). Nejkratší vzdálenost od elektrárny nemusí nutně být nejlepší (pokud je na mapě kratší vzdálenost, ale v cestě je hora, určitě to není nejlepší řešení)<br /> <br /> = hledáme pro každá vrchol nejkratší cestu ke stromu<br /> <br /> =&gt; neplést si Dijktrou, ten také hledá nejkratší cestu, ale z výchozího vrcholu<br /> <br /> Obrázek naznačí rozdíl:<br /> <br /> [[Soubor:Prim-jarnik.jpg]]<br /> <br /> <br /> Dijsktra použije hranu 4-&gt;5, protože pak bude vždálenost 5 od 1 = 4 ( s hranou 3 -&gt; 5 by byla 5)<br /> Prim použije hranu 3-&gt;5, protože je levnější, než hrana 4 -&gt; 5, a tedy hodnota stromu je 7, což je menší než 8.<br /> <br /> Tím je vlastně i popsán algoritmus. Je podobný jako Dijsktra, ale v bodě 4 kontrolujeme pouze váhu hrany, níkoliv součet cesty do předchozího bodu a váhy. Implementace je stejná, řadíme podle vah hran (opět ignorujeme předchozí cesty)<br /> <br /> <br /> <br /> == Základy kryptografie ==<br /> <br /> Šifrujeme, protože nechceme, aby třetí osoba věděla, o co se jedná<br /> <br /> ochrana citlivých přenášených dat<br /> <br /> ochrana před odposlechem<br /> <br /> ochrana před neautorizovaným přístupem<br /> <br /> ....<br /> <br /> '''Šifrování''' = transformace dat do nečitelné podoby<br /> <br /> '''Dešifrování''' = zpětný proces rekonstrukce šifrované zprávy pomocí tajného klíče<br /> <br /> '''Kryptografie''' - věda o tvorbě šifer<br /> <br /> '''Kryptoanalýza ''' - věda o prolamování šifer (nejjednodušší: frekvenční analýza. Anglické texty obsahují velké množství výskytů slova THE, můžeme tedy dedukovat, že nejčastější 3 písmenná slova substitučně šifrovaného textu jsou právě THE (například PQX), a můžeme tyto písmena použít (T-&gt;P, H-&gt;Q, E-&gt;X)<br /> <br /> '''Dělění'''<br /> <br /> [[Z hlediska zpracování zprávy:]] <br /> <br /> ''Blokové šifry'' - pracují s celými bloky dat (obvykle 8-128 bytů)<br /> <br /> ''Proudové šifry (streamové)'' - pracují s jednotlivými bitu zprávy zvlášť, jsou považovány za méně bezpečné, jsou pomalejší než šifry blokové<br /> <br /> [[Z hlediska šifrování:]]<br /> <br /> ''Symetrické šifry'' - odesilatel i příjemce sdílí jedno tajemství (klíč) nutné k šifrování a zašifrování zprávy<br /> <br /> ''Asymetrické šifry'' - odesilatel a příjemci šifrují a dešifrují zprávu různými klíči, nemusí spolu sdílet žádné tajemství. Nevýhoda: je o několik řádů pomalejší než symetrická kryptografie<br /> <br /> <br /> '''Symetricky'''<br /> <br /> Je nejpoužívanějším typem šifrovacího algoritmu<br /> <br /> Používá stejný šifrovací klíč k šifrování i dešifrování- což je jeho největší slabina<br /> <br /> Je velmi rychlý a používá se při velkém množství dat<br /> <br /> Klíč se musí dostat od odesilatele k adresátovi bezpečným kanálem (cestou), aby adresát mohl zprávu dešifrovat. Často osobní předání.<br /> Pokud takový bezpečný kanál existuje, je často jednodušší zprávu nešifrovat a poslat ji rovnou tímto kanálem. <br /> <br /> Příklady: AES (ve wifi, je nutné fyzicky zadat klíč do zařízení i do pořítače), A5 (v mobilních telefonech, klíč je na SIM a u uperátora) a DES (nejpoužívanější šifra na světě)<br /> <br /> [[Soubor:Symetricke-sifrovani.jpg]] <br /> <br /> '''Nesymetricky'''<br /> <br /> Používá jiný klíč k zašifrování a jiný klíč zpátky k dešifrování<br /> <br /> První z nich se nazývá veřejný, ostatní ho musejí znát. Druhý klíč se nazývá privátní<br /> <br /> Asymetrický šifrovací systém (systém s veřejným klíčem) je založen na principu jednocestné funkce, což jsou operace, které lze snadno provést pouze v jednom směru: ze vstupu lze snadno spočítat výstup, z výstupu však je velmi obtížné nalézt vstup. <br /> Nejběžnějším příkladem je například násobení: je velmi snadné vynásobit dvě i velmi velká čísla, avšak rozklad součinu na činitele (tzv. faktorizace) je velmi obtížný. (Na tomto problému je založen např. algoritmus RSA.)<br /> <br /> [[Soubor:Asymetricke-sifrovani.jpg]]<br /> <br /> <br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Komprese_dat,_rozd%C4%9Blen%C3%AD_kompresn%C3%ADch_metod,_princip_kompresn%C3%ADch_metod_(Huffmann,_aritmetick%C3%A9_k%C3%B3dov%C3%A1n%C3%AD,_LZW,_JPG,_frakt%C3%A1lov%C3%A1_komprese) 2014-02-20T06:44:46Z

<p>Acolade: kategorizace</p> <hr /> <div>Algoritmy pro kompresi dat používáme pro snížení velikosti přenášených dat<br /> * z paměťových důvodů<br /> * ušetření šířky pásma<br /> * urychlení přenosu a zkrácení doby odezvy<br /> * archivace dat, zálohy<br /> * obrana proti virům<br /> * distribuce software<br /> * ...<br /> <br /> '''Kvalita komprese''' - úrověň zmenšení, poměr komprese = před/po. Symetrické metody potřebují stejný čas ke komprimaci jako k dekomprimaci<br /> <br /> <br /> == Rozdělení kompresních metod ==<br /> <br /> * '''Bezztrátová''' - po komprimaci a dekomprimaci je výsledek k nerozeznání od originálu, 100% shoda. Metody jsou méně efektivní. Použijeme na text, obecné soubory<br /> * '''Ztrátová''' - po komprimaci a dekomprimaci je výsledek rozdílný, cílem je však aby byl co nejvíce podobný. Více efektivní. Použijeme na zvuk, obraz, video.<br /> <br /> <br /> == Metody komprese ==<br /> <br /> * '''Jednoduché''' - založené na kódování opakujících se posloupností znaků (Run-Length Encoding - RLE)<br /> * '''Statistické''' - založené na četnosti výskytu znaků v komprimovaném souboru (Huffmanovo kódování, Aritmetické kódování)<br /> * '''Slovníkové''' - založené na kodování všech vyskytujících se posloupností (Lempel-Ziv-Welch - LZW)<br /> * '''Transformační''' - založené na ortogonálních popř. jiných transformacích (JPEG, waveletová komprese, fraktálová komprese)<br /> <br /> == RLE ==<br /> <br /> RLE (Run Length Encoding) – kódování délkou běhu<br /> <br /> Nejjednodušší komprimační algoritmus, nahrazuje opakující se znaky jedním znakem a číslem vyjadřujícím počet okpakování (AAAAABBBBBCCD -&gt; 5A5B2C1D)<br /> Pro text k ničemu, pro obraz celkem dobrá komprese (zvláště obrazy používající malou paletu barev)<br /> Problém: pokud se znak neopakuje, dochází k expanzi (ABC -&gt; 1A1B1C) - Řešení pomocí escape sekvencí (označíme si, co je délka a co ne) a poté komprimujeme pouze opakující se znaky. Escape znak nesmí být obsažen v původním textu.<br /> <br /> <br /> [[Soubor:Komprese-rle.png|frame|center|Ukázka komprese bitového souboru pomocí RLE. Ukládáme vždy počet nul a jedniček v řadě.]]<br /> <br /> == Huffmanovo kódování ==<br /> <br /> Statistická metoda. Vyhledáme četnosti všech znaků v řetězci a tyto znaky podle četnosti zakódujeme tak, aby nejkratší kód odpovídal nejčastějšímu znaku. Kódy jsou binární, nejčastější znak bude tedy reprezentován 1 bitem na rozdíl od 8(16) bitů potřebných pro uložení ASCII(UTF) znaku. Jená se o prefixový kód, takže žádný znak není prefixem jiného znaku -&gt; kódy pro jednotlivé znaky mají různou délku a není potřeba označovat jejich konec (každý znak kreprezentuje jeden list stromu).<br /> <br /> Kódy vytvoříme Huffmannovým stromem:<br /> <br /> * Jednotlivé znaky označíme jako listy stromu<br /> * Tyto listy uložíme do seznamu S (S obsahuje uzly stromu, na začátku tedy pouze listy)<br /> * Seznam S seřadíme podle četnosti<br /> * Vybereme z S dva prvky M,N s nejnižšími četnostmi m, n, m &lt; n<br /> * Vytvoříme uzel p, kde vlevo je M a vpravo je N, a jeho četnost bude m+n<br /> * Vložíme p do S a zpět na bod 3 dokud v S není jen jeden uzel<br /> <br /> Strom samozřejmě musíme přenášet spolu s komprimovanými daty. Strom můžeme reprezentovat řetězcem tak, že jej projdeme DFS algoritmem a pro haždý vrchol uložíme 0 a pro každý list 1 a znak tohoto listu. Při načítání čteme nuly a vytváříme uzly (směrem doleva). Pokud narazíme na 1, zapíšeme písmeno a vrátíme se do nejbližšího pravého uzlu (pravý uzel rodiče, případně nejvíce levý prvek podstromu - u rodiče vpravo)<br /> <br /> Při dekompresi procházíme strom a rekonstruujeme zprávu.<br /> <br /> <br /> [[Soubor:Huffman.png]]<br /> <br /> == Aritmetické kódování ==<br /> <br /> Také statistická metoda. <br /> Aritmetické kódování na rozdíl od jiných metod nepracuje na principu nahrazování vstupního znaku specifickým kódem. Místo toho se kódovaný vstupní proud znaků nahradí jediným reálným číslem z intervalu &lt;0,1).<br /> <br /> Na základě pravděpodobnosti výskytu jednotlivých symbolů vstupní abecedy je každému symbolu přiřazena odpovídající poměrná část intervalu &lt;0,1). Při kódování je pak celý interval &lt;0,1) postupně omezován z obou stran na základě postupně přicházejících symbolů (Interval ořízneme jen na tu část, které odpovídá pravděpodovnost písmene v textu, a tento interval opět rozdělíme podle pravděpodobností pro další písmeno). <br /> <br /> Kódovaná hodnota se reprezentuje libovolným reálným číslem, které leží ve výsledném intervalu získaném po přečtení všech vstupních symbolů. Vzhledem k tomu, že z takto reprezentované hodnoty nelze při dekódování určit konec zprávy, je třeba navíc ke zprávě přidat zpeciální znak označující konec, případně musí být uložena i délka původní posloupnosti. <br /> <br /> Příklad: kódujeme zprávu 'abaabcda'<br /> <br /> [[Soubor:Aritmeticke-kodovani.jpg]] <br /> <br /> Co z toho číst?<br /> * První řádka ukazuje pravděpodovnosti písmen (ty vypočteme jako četnost písmene / písmen celkem)<br /> * Dále vidíme, jak bude interval (a podintervaly) rozdělený. 'a' jako nejpravděpodobnější písmeno dostane největší část intervalu atd...<br /> * A dále už kódujeme. Jdeme zleva do prava. Přijde písmeno 'a', vybereme tedy spodní interval. Tento opět rozdělíme na stené části jako interval původní a přijde 'b'. Opět vybereme odpovídající interval, který rozdělíme atd.<br /> * Zvýrazněná část intervalu se na obrázku vždy zazoomuje ;) (jsou tam šipky).<br /> * Na konci máme jen jeden interval, vybereme tedy číslo , které do něj patří. Zpráva je zakódována v desetinné části tohoto čísla (a ano, celá zpráva je reprezentována jedním číslem)<br /> <br /> == LZW ==<br /> <br /> Z přednášek, doplněno:<br /> Slovníkový algoritmus. Využívá skupin znaků označených kódy a přenos kódů, které mají menší velikost než původní skupiny.<br /> Princip:<br /> Jednoprůchodová metoda (nevyžaduje předběžnou analýzu souboru. Ve výsledku se jen posunujeme po souboru jedním ukazatelem.)<br /> Vyhledávání opakujících se posloupností znaků, ukládání těchto posloupností do slovníku pro další použití a přiřazení jednoznakového kódu těmto posloupnostem.<br /> Kódy musí mít délku (počet bitů) větší než délka původních znaků (např. pro ASCII znaky (8 bitů) se obvykle používá délka kódu 12 bitů popř. větší. Na osmi bitech kódu by se dal uložit pouze slovník o 256 slovech(posloupnostech znaků), což odpovídá pouze počtu písmen, což je k ničemu.)<br /> Při průchodu komprimovaným souborem se vytváří slovník (počet položek slovníku odpovídá hodnotě 2(počet bitů kódu), kde prvních 2(počet bitů původních znaků) položek jsou znaky původní abecedy a zbývající položky tvoří posloupnosti znaků obsažené v komprimovaném souboru (používáme tedy i kódy z již komprimovaného souboru k vytvýření nových kódů).<br /> Při dekompresi procházíme kódy, a podle tabulky je rozebíráme na menší a menší, až se dostaneme na elementární znaky, které vypíšeme.<br /> <br /> Aby to celé fungovalo, musíme slovník na dekomprimační straně &quot;naučit&quot; slova od menších po větší. Musíme proto na začátku souboru definovat elementární znaky, a z nich poté skládat slovník. Pro ASCII tedy prvních 256 znaků tabulky může odpovídat 1:1 ASCII abecedě, až poté následuje slovník. Pokud při dekompresi narazíme na neznámý kód, víme, že je složen z předchozích 2 kódů. Proto se jej naučíme, a příště už víme, co zapsat (případně jak jej rozložit). Tabulka na obou stranách tedy je stavěna stejně, jen používána z jiné strany (při komprimaci ukládáme kódy, pri dekomprimaci jejich znaky)<br /> <br /> Pro obrázky viz přednášky z PT, jsou celkem snadno pochopitlené, i když místo &quot;kód&quot; občas autor používá &quot;znak&quot; či &quot;nový znak&quot;, což je trochu matoucí.<br /> <br /> <br /> == JPG ==<br /> <br /> V současné době patří mezi nejvíce používané komprese u obrázků<br /> Je vhodná pro komprimaci fotek, nevhodná pro např. technické výkresy (čarové výkresy) - dochází k viditelnému rozmazání (na webové aplikace pomalu převlédá png (zejména kvůli neztrátovosti a průhlednosti))<br /> <br /> Princip:<br /> části obrazu se transformují do frekvenční oblasti (výsledkem je matice „frekvenčních“ koeficientů, bezztrátový převod)<br /> z matice koeficientů se odstraní koeficienty odpovídající vyšším frekvencím ( rychlejší změny jasu - např. hrany v obraze, zde jsou ztáty)<br /> zbývající koeficienty se vhodným způsobem zkomprimují (huffman, aritmeticky)<br /> <br /> <br /> [[Soubor:Jpg-1.jpg]]<br /> [[Soubor:Jpg-2.jpg]]<br /> <br /> <br /> <br /> <br /> == Fraktálová komprese ==<br /> <br /> Fraktál je obraz, který je matematicky popsatelný a tím jej lze libovolně přibližovat a oddalovat bez stráty informace. Také lze fraktál popsat jako soubor matematicky popsaných sebepodobných částí, jejichž spojováním dostáváme také sebepodobný obraz ve větším detailu (jako když děláme koláž z fotek, které dohromady a z dálky vypadají jako fotka)<br /> <br /> Toho lze využít pro kompresi. Pokud se podíváme na libovolný obrázek, často zjistíme, že některé jeho části jsou si podobné<br /> <br /> [[Soubor:Fraktalova-komprese.jpg]]<br /> <br /> Tyto malé kousky (frakce) lze pomocí rotace, změny velikosti a posunu otočit tak, že si budou velmi podobné (nebo dokonce budou stejné). V obrazu tedy můžeme na takový kousek mít pouze jednu, a v ostatních výskytech pouze uložit tyto operace.<br /> <br /> V praxi obrázek rozřežeme na shluky 2x2 pixely (range bloky), a pak hledáme, kde jinde v obrazu je můžeme najít (domain bloky). Domain bloky se mohou překrývat, range bloky se nepřekrývají. Postupujeme tak, že Domain blok vytvoříme jako dvojnásobek range bloku, a v obrazu postupujeme zleva do prava. V bloku uděláme průměr hodnot pixelů pod ním tak, abychom získali blok velikosti range bloku, a poté hledáme, kterému range bloku je takto zmenšený domain blok podobný. Uložíme si operace, které s domainblokem musíme udělat, aby byl range bloku podobný (rotace, překlopení, posun...) Pokud je domainblok složen z domainbloků, postupujeme rekurzivně. Tím, pomocí podobnosti, získáme komprimovaný obraz.<br /> <br /> <br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Algoritmy_zpracov%C3%A1n%C3%AD_text%C5%AF_%E2%80%93_operace_s_%C5%99et%C4%9Bzci,_porovn%C3%A1n%C3%AD_se_vzorem_(KMP,_Boyer-Moore_algoritmus),_nejdel%C5%A1%C3%AD_spole%C4%8Dn%C3%BD_pod%C5%99et%C4%9Bzec_(LCS_algoritmus),_vzd%C3%A1lenost_mezi_%C5%99et%C4%9Bzci,_datov%C3%A1_struktura_Trie_a_pou%C5%BEit%C3%AD 2014-02-20T06:44:36Z

<p>Acolade: kategorizace</p> <hr /> <div>Tak tahle otázka je očistec. Kdo tohle všechno vysvětlí za 15 minut je borec, i když bych řekl, že je tam rozsekaj na menší otázky.<br /> <br /> <br /> <br /> == Obecně ==<br /> <br /> Vyhledáváme podřetězec P v řetězci T. T je string s textem, P je string s maskou (pattern)<br /> <br /> Podřetězec je část řetězce [i..j]. T je délky n, P je délky m.<br /> <br /> Prefix je část řetězce (či podřetězce) od začátku, suffix je část řetězce (či podřetězce) od konce.<br /> <br /> <br /> <br /> == Brutální síla ==<br /> <br /> Indexem jdeme po T a kontrolujeme, jestli podřetězec začínající na tomto indexu neodpovídá P (tedy kontrolujeme m prvků od indexu směrem do prava.<br /> V nejhorším případě O(nm), což je pomalé<br /> <br /> T: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaah<br /> <br /> P: aah<br /> <br /> P v T najdeme až úplně na konci, pro každé 'a' v T (kromě třetího od konce) znovu hledáme písmena P v řetězci T zcela zbytečně<br /> <br /> <br /> == Boyer-Moore (BM) algoritmus ==<br /> <br /> V tomto algoritmu prohledáváme P od konce, a hledáme výskyt v T. Do T ukazuje index i, do P index j.<br /> <br /> Mohou nastat 4 případy:<br /> <br /> 1) T[i] není v P vůbec, posuneme i dále o délku P (zarovnáme P na další písmeno v T, tedy T[i+1]<br /> <br /> (obrázky v přednáškách jsou křivé, tak se mi to snad povedlo odstranit)<br /> <br /> [[Soubor:Boyer-moore-1.jpg]]<br /> <br /> 2) T[i] odpovídá P[j] - posuneme se v obou do leva a opakujeme (jako v brutální síle)<br /> <br /> 3) T[i] není P[j], ale T[i] je v P před indexem j -&gt; zarovnáme P do prava tak, aby T[i] odpovídal jeho výskytu v P a opakujeme<br /> <br /> [[Soubor:Boyer-moore-2.jpg]] <br /> <br /> 4) T[i] není P[j], ale T[i] je v P za indexem j -&gt; posuneme se do prava o 1 a opakujeme (nemůžeme se vracet, ale ani posunout o více dále)<br /> <br /> [[Soubor:Boyer-moore-3.jpg]]<br /> <br /> Pokud nalezneme celý pattern, vrátíme i. Algoritmus je pro texty rychlejší, než brute force, i tak je však jeho složitost O(mn + A), kde A je velikost abecedy. Pro velké abecedy funguje rychle, ale např pro binární soubory funguje pomalu.<br /> <br /> '''Dodatek:''' Algoritmus si v preprocesingu zjistí, na které pozici má které písmena (směrem od leva). Je-li patern tedy například &quot;ABRAKADABRA&quot;, A dostane index 10, B dostane index 8, K = 4, D = 6 a R = 9. Pro ostatní písmena přiřadíme -1. Naimplementujeme tedy funkci Last(char input), která podle písmene vrátí tento index, a pak pro případy 3 a 4 porovnáváme Last(T[i]) a j, a tím pak víme, jestli i posunout na Last(T[i]) (pokud je Last(T[i]) &lt; j) nebo pouze i++<br /> <br /> <br /> == Knuth‐Morris‐Pratt (KMP) algoritmus ==<br /> <br /> Jako brutal force jde zleva do prava, ale nedělá otrocky všechny porovnání. Pokud narazíme na neshodu, je možné se posunout o více než o jedno písmeno. <br /> <br /> Otázka zní o kolik?<br /> <br /> Odpověď, o maximální prefix P( 0 .. j-1 ), který je suffixem P( 1 .. j-1 ). Suffix a prefix se nesmí překrývat.<br /> <br /> Proč? Protože najdeme-li kus P (od začátku, tedy prefix), víme, že znaky tohoto prefixu odpovídají textu. Je tedy netřeba je kontrolovat znovu. Může se ale stát, že konec nalezeného podřetězce je také obsažen v začátku tohoto podřetězce. Takovou shodou je samozřejmě celá nalezená část P, proto hledáme od P+1. Takže jdeme od konce nalezeného kusu P zleva a zprava, a ve chvíli, kdy nenalezneme shodu, víme, o kolik se můžeme posunout. Tohle se samozřejmě dá předpočítat do tabulky, a pak je vše O(1)<br /> <br /> [[Soubor:Kmp.jpg]]<br /> <br /> (i.e. P[j] != T[i]), pak<br /> k = j‐1;<br /> j = F(k); // získání nové hodnoty j, kde F(k) je právě předpočítaná tabulka společných částí P<br /> <br /> <br /> == Trie ==<br /> <br /> Trie je struktura pro předspracování textu pro pozdější rychlé vyhledávání. V každém uzlu standartní Trie je písmeno a délka cesty k vrcholu je také pozicí písmene ve slově, tedy je-li hloubka písmene 'E' v Trie rovna 3, víme, že je to třetí písmeno (např. slova Trie)<br /> <br /> Standartní trie má v každém uzlu právě jedno písmeno. Vyhledávání je O(d * m) kde d je velikost abecedy (v každém uzlu musíme projít všechna písmena, abychom zjistili, že tam písmeno je), m je délka slova. Paměťově je Trie nejvýše složitosti O(n) kde n je délka původního textu. Pokud se slova překrývají, paměťi je potřeba méně.<br /> <br /> Rychlost se dá na úkor paměti vylepšit tak, že v každém uzlu připravíme celou abecedu a při hledání převedeme písmeno na index v této abecedě, tím pádem záskáme v O(1) čase pointer na další písmeno ve slově.<br /> <br /> <br /> == Komprimovaná trie ==<br /> <br /> Jako trie, ale sklukujeme, tedy ve vrcholech stromu písmena, která jsou společná pro všechna slova, tedy pro slova 'ahoj' a 'ahojky' bude mít trie 2 vrcholy, 'ahoj' a pod ním 'ahojky'. Tuto Trie lze převést na standartní pouhým rozdělením shluků, standartní Trie převedeme na kompaktní sloučením vrcholů s rodiči, kteří mají pouze jeden odkaz na vrchol (tento vrchol)<br /> <br /> Pak je ještě suffixová Trie, které ukládá všechny sufixy slov, v komprimované podobě. Umožňuje vyhledávat i uprostřed slova.<br /> <br /> <br /> == LCS - Longest common subsequence ==<br /> <br /> Tohle je skoro nemožný vysvetlit na statickym papiru....<br /> <br /> Cílem algoritmu je najít nejdelší společný podřetězec libovolného počtu řetězců. To je problém NP-těžký, což je masakr. <br /> My se ale omezíme na porovnávání 2 řezězců, což je v polynomiálním čase řešitelné (dynamicky).<br /> <br /> Brutální síla by dělala to, že by našla všechny podřetězce obou řetězců, a ty porovnávala (také brutální silou) Podřetězců je však řekněme n!, brutální síla je n2, takže (n!)2. Dynamicky to lze dělat rychleji. Použijeme tedy rovnou dynamické programování, protože to nám dovoluje pamatovat si so už jsme našli, a neztrácet čas znovuobjevováním nalezeného.<br /> <br /> Nechť Li,j = maximální délka společných řetězců končících v Ai a Bj . Vytvoříme si tedy dvojrozměrnou tabulku, do které si tyto Li,j budeme zapisovat.<br /> <br /> Nyní, je-li písmeno na pozici i v řetězci A stejné, jako písmeno na pozici j v řetezci B, víme, že jde o společný podřetězec (délky 1). Nevíme však, zda předchozí písmena nebyla také podřetězcem (zatím)<br /> <br /> Víme ale následující: Pokud existoval pořetezec pro indexy i-1 a j-1 (tedy pro předchozí písmena v obou řetězcích), bude v tabulce na příslušné pozici, tedy vlevo nahoře od Li,j tedy Li-1,j-1. Na této pozici je tím pádem dosavadně nalezená délka společného podřetězce, který končí na indexech i-1 a j-1. Pokud by i předchozí indexy daly stejné písmeno, musíme tuto délku dále diagonálně propagovat, a tedy<br /> <br /> Ai = Bj -&gt; Li,j = Li-1,j-1 + 1 -&gt; společný řetězec končící na indexu i-1,j-1 pokračuje<br /> <br /> Ai &lt;&gt; Bj -&gt; Li,j = 0 -&gt; není společný (pokud na i-1 a j-1 byl, na tomto indexu končí)<br /> <br /> Takto vyplníme celou tabulku, přičemž nulté řádky budou nulové (abychom nevyšli pro první písmena z hranice pole)<br /> <br /> [[Soubor:Lcs.jpg]]<br /> <br /> Problém: Jak zjistit, kde je řešení nejlepší? Ano, můžeme najít maximum v tabulce, ale to je další O(M + N) operace, a máme tabulku plnou nul, toho lze využít. Algoritmus tedy modifikujeme tak, že bude zachovávat i dosavadně nejlepší nalezenou délku společného podřetězce v každém bodě. toho docílíme úpravou druhého pravidla, tedy<br /> <br /> Ai = Bj -&gt; Li,j = Li-1,j-1 + 1<br /> Ai &lt;&gt; Bj -&gt; Li,j = max (Li-1,j, Li,j-1)<br /> <br /> Nejlepší nalezené řešení je nahoře, nebo vlevo. Tím se tabulka naplní, a my budeme znát nejlepší délku v pravém spodním rohu tabulky<br /> <br /> [[Soubor:Lcs-2.jpg]] <br /> <br /> Nyní ale nevíme, kde ta písmena jsou. Je tedy nutné si to ukládat do druhé tabulky (onačit si, kudy jsme na které pole přišli, z leva, ze shora (při zpětném průchodu pouze posun), nebo šikmo (při zpětném průchodu výpis a posun)) a následně zrekonstruovat zpětným průchodem. V přednáškách jsou šipky, ukazující kudy se budeme vracet. Při provádění pravidla 2 si samozřejmě tuto informaci musíme také propagovat, pomatujeme si tedy, odkud jsme na každé pole přišli ( v druhé tabulce si to lze označit třeba 0, 1 pro nahoru a do leva, 2 pro šikmo )<br /> <br /> A konečně...<br /> <br /> <br /> == Vzdálenost mezi řetězci ==<br /> <br /> '''Hammingova metrika:''' na stejně dlouhé řetězce, jen je porovnáme, a v O(n) čase víme, kolik změn písmen musíme provést (Auto, Zutá = 2)<br /> <br /> '''Levensteinova metrika:''' někdy také edit distance, máme operace změnit/přidat/odebrat písmeno, abychom dostali z jednoho řetězce ten druhý. Jde o celočíselné vyjádření podobnosti řetězců, například<br /> <br /> P=abcdefghijkl, T=bcdeffghixkl, P odpovídá T po 3 změnách (v T přidat a, ubrat f a zaměnit x za j)<br /> <br /> '''Algoritmus:'''<br /> Postup podobný jako u LCS, ale<br /> matice je D[i,j]<br /> a prvky vyplňujeme takto <br /> <br /> máme 3 možné způsoby úpravy řetězce<br /> <br /> 1. P[i]=T[j] , s = D[i-1,j-1] (shoda) jinak D[i-1,j-1] + 1 (substituce, platíme cenu za změnu znaku)<br /> <br /> 2. v = D[i-1,j] + 1 (znak navíc v P, neposouváme pointer v T (při úpravách) a platíme cenu za vkládání)<br /> <br /> 3. r = D[i,j-1] + 1 (znak navíc v T, neposouváme pointer v P (při úpravách) a platíme cenu za rušení)<br /> <br /> minimem z s, v a r získáme pole D[i,j]<br /> <br /> [[Soubor:Vzdalenost-mezi-retezci.jpg]]<br /> <br /> Řešení je opšt ve spodním pravém rohu a zpět postupujeme po stejných číslech (žádná změna) nebo menších (změna, jdeme-li šikmo, substituce, jdeme-li nahoru rušení, do leva vkládání)<br /> <br /> <br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Tabulky_s_rozpt%C3%BDlen%C3%BDmi_polo%C5%BEkami,_vyhled%C3%A1v%C3%A1n%C3%AD_v_tabulk%C3%A1ch 2014-02-20T06:44:26Z

<p>Acolade: kategorizace</p> <hr /> <div>To samé jako PPA2 14 a 15,<br /> <br /> jen doplňky/opakování/upřesnění:<br /> <br /> '''Vnitřní zřetězen'''í - synonyma (položky s kolizemi) se ukládají do volných míst<br /> <br /> '''Vnější zřetězení''' - synonyma se ukládají do seznamů pod klíči<br /> <br /> <br /> <br /> == Otevřené rozptýlení - hash funkce ==<br /> <br /> Kolize:<br /> <br /> 1) nedefinované chování při kolizi - nutno dodefinovat<br /> <br /> 2) lineární posun - při kolizi vkládáme na první volné místo lineárně (na indexech 1,2,3,4 od původní polohy<br /> <br /> 3) kvadratický posun - při kolizi hledáme první volné místo na indexech podle kvadratické funkce (vzdálenosti 1, 4, 9, 16...)<br /> <br /> 4) opakovaný hash - hashovací fci použijeme víckrát pokud dojde ke kolizi<br /> <br /> <br /> <br /> == Uzavřené rozptýlení - přímé adresování ==<br /> <br /> metody 2) a 3) nejsou vhodné, vzniká shlukování (clustering), proto je dobré použít způsob 4) nebo lepší hash funkci<br /> <br /> <br /> <br /> == Tabulky s uzavřeným rozptýlením a vnějším zřetězením ==<br /> <br /> = kombinace obou<br /> <br /> - adresujeme přímo, při kolizi si ale do tabulky na konec uložíme, kam budeme vnitžně zřetězovat. Hash funkce tedy může být při kolizi (třeba náhodná), nebo tabulku rozdělíme na 2 části, jednu pro vyhledávání klíčů, a druhou pro ukládání synonym. ta už může být dynamicky alokovaná.<br /> <br /> <br /> <br /> == Metoda rozptýlených indexů ==<br /> <br /> To co bylo v předchozím případě v tabulce vyjmeme, a vytvoříme vedle. Uděláme si mapu synonym (synonyma v seznamu pro každý klíč) a tyto pak ukazují na index do pole.<br /> <br /> <br /> <br /> == Vyhledávání ==<br /> <br /> Má samozřejmě smysl jen pokud nemáme orákulum (= hashovací fci). Pokud orákulum máme, není třeba hledat protože ideální orákulum vždy ví, kam se podívat pro správná data (The all-knowing Oracle is never surprised. How can she be, she knows everything. -- The Matrix: Revolution), reálné ví aspoň kde hledat.<br /> <br /> Jelikož je při přímém adresování orákulum pouhý index do tabulky (mno, to moc orákulum není, orákulum vždy ví, kam jít, aby nebyla kolize), alespoň nám napoví odkud hledat.<br /> <br /> <br /> '''Sekvenční:'''<br /> <br /> Hledáme klíč lineárně, pokud na něj narazíme, vrátíme hodnotu<br /> <br /> + snadná implementace<br /> <br /> + tabulka nemusí být uspořádaná<br /> <br /> - pomalé hledání<br /> <br /> '''Binární'''<br /> <br /> Jako sekvenční, ale klíče musí být seřazeny, a nad nimi vytvoříme BVS, tedy hledáme vždy v půlce intervalu<br /> <br /> + rychlejší (O(log n))<br /> <br /> - nutnost udržovat tabulku seřazenou<br /> <br /> '''Fibonacciho'''<br /> <br /> Jako binární, ale nerozdělujeme v polovině, ale podle Fibonacciho posloupnosti (tedy ne 1:1 -&gt; 1:(1:1) -&gt; 1:((1:1): 1) ale (1:1) -&gt; (1:(1:2)) - &gt; (1:((2:3):2))<br /> <br /> Prvky vybíráme jako dvojice, první z dvojice je ve Fibonacciho posloupnosti na pozici odpovídající úrovni vnožení stromu (výška větve, ve které hledáme)<br /> <br /> Fibonacciho ppst: a1 = 1, a2 = 1, ai = ai-1 + ai - 2 , tedy 1,1,2,3,5,8,13,21,34,55, ....<br /> <br /> '''Podle sekundárního klíče'''<br /> <br /> Jen pouze pokud sekundární klíč existuje v datech, např seznam jmen, jméno je primární (není, ale pro vysvětlení řekněme, že je) a rok je sekundární. Vyhledáme jména v sekundárním klíči a v nich pak hledáme jméno podle primárního klíče.<br /> <br /> Sekundární klíče máme v seznamu, který obsahuje seznam primárních klíčů zabulky pro každý sekundární klíč<br /> <br /> <br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Skip-list_-_pou%C5%BEit%C3%AD_a_implementace 2014-02-20T06:44:18Z

<p>Acolade: kategorizace</p> <hr /> <div>Skiplist je alternativa ke stromům, která je snadno implementovatelná. Operace se skiplistem jsou podobné složitosti jako u stromů (O(n log n)), ale paměťová náročnost může být o něco větší.<br /> <br /> Skiplist si lze představit následovně: seznam, ve kterém některé prvky ukazují i na vzdálenější prvky než jsou prvky bezprostředně následující. Tyto ukazatele &quot;přeskakují&quot; položky seznamu, odtud skiplist.<br /> <br /> Maximální výška uzlu = Maxlevel, každý prvek může mít 1 &lt;= k &lt;= Maxlevel ukazatelů na další prvky<br /> <br /> <br /> [[Soubor:Skip-list.jpg]]<br /> <br /> <br /> Popisky (obrázek je z přednášky):<br /> * '''a)''' vidíme nejjednoduší skiplist se skokem 1, tedy lineární spojový seznam<br /> * '''b)''' skiplist se skokem 2. Každý druhý prvek obsahuje kromě hodnoty a ukazatele na následníka také ukazatel na následovníka následovníka (next[next[x]]). Už touto změnou zkrátíme vyhledávání na polovinu, jelikož abychom se dostali na prvek např. 25, stačí nám pouze 5 skoků (&gt; 6, &gt;9, &gt;17, &gt;21, &gt;25) na rozdíl od seznamu, kde jich je 9<br /> * '''c)''' skiplist se skokem 4. na prvek 25 se dostaneme pouze 2 skoky<br /> * '''d)''' skiplist se skokem 8. na prvek se dostaneme 1 skokem =&gt; ideální skip-list: každý 2i-tý prvek má ukazatel, který ukazuje o 2i prvků dopředu <br /> * '''e)''' skiplist s náhodným skokem - ?? skoků, ale ve velkém skiplistu je rychlejší, než lineární seznam, a operace přidání a odebírání jsou jednodušší<br /> <br /> Výhody:<br /> * Skiplist je extrémně rychlý (vyhledávání je log n)<br /> * Velmi snadná implementace (pouze pole ukazatelů v každém prvku)<br /> <br /> Nevýhody:<br /> * Pomalé operace insert a delete (je nutné reorganizovat skiplist)<br /> <br /> Řešení: skiplist s náhodnými velikostmi uzlů. Potom:<br /> * Vložení - najdeme místo, kam prvek patří, pomatujeme si všechny předchůdce. Po nalezení vložíme prvek s náhodnou výškou 1 &lt; k &lt; Maxlevel, a napojíme všechny předchůdce do výšky tohoto prvku (samozřejmě na obě strany, předchůdci ukazují na tento prvek, a ten ukazuje na prvky, na které předchůdci ukazovali původně)<br /> * Mazání - opačný proces, najdeme prvek a pomatujeme si předchůdce. Pro všechny předchůdce do výšky hledaného prvku upravíme ukazatele (předchůdci budou ukazovat na prvky, na které ukazoval hledaný prvek). Hledaný prvek smažeme.<br /> <br /> Tento skip-list není zcela log n, a nelze (díky náhodnosti) jeho složitost určit. S vysokou pravděpodobností však všechny operace budou rychlejší než O(n) (samozřejmě můžeme mít smůlu a všechny prvky budou náhodně výšky 1).<br /> <br /> {{fav-kiv-bzinf}}<br /> <br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Stromov%C3%A9_struktury_(Avl,_BVS,_B,_Red-Black)_a_jejich_implementace 2014-02-20T06:44:11Z

<p>Acolade: kategorizace</p> <hr /> <div>Strom je ADT uchovávající prvky v hierarchické struktuře předcůdce-následovník. Použití v reprezentaci znalostí a stavového prostoru, popis scény při zpracování obrazu, v databázových systémech, systémech souborů, pro rozhodovací stromy, komprese dat, raytracing. <br /> <br /> * '''Obecné stromy''' - uzly mohou mít libovolný počet následovníků. Implementace pomocí ukazatelů, ve vrcholech spojový seznam následovníku.<br /> * '''N-ární stromy''' - uzel má nejvýše n následovníků. Implementace ukazateli, ve vrcholech pole následovníků. <br /> * '''Binární stromy''' - uzel má nejvýše dva následovníky. Implementace ukazateli a výčtem následovníků, případne polem.<br /> <br /> Binární strom, kde nalevo od každého prvku jsou k prvky s nižším klíčem a napravo s vyšším (příp. obráceně), je binární vyhledávací strom (BVS). Kořenem obyčejného BVS je první vložený prvek, další prvky se vkládají nalevo nebo napravo od něj. Při postupném vkládání seřazené posloupnosti ale takový strom degraduje na lineární seznam, což zvyšuje složitost vyhledávání. Proto je na místě snaha o vyvážení stromu.<br /> <br /> <br /> == AVL ==<br /> <br /> (Adelson-Velsky, Landis)<br /> <br /> BVS zachovávající pravidlo, že podstromy každého vrcholu se mohou výškou lišit nejvýše o 1. Vyvážení kontrolováno po každém vložení a výberu. Vrchol obsahuje navíc položku informující o rozdílu výšek obou jeho podstromu (-2, -1 levá strana, 0 vyvážený, 1, 2 pravá strana). Vložení stejné jako u BVS, po vložení prepocet rozdílu výšek (v každém kořenu na cestě z vloženého prvku do kořenu stromu sledujeme, jak se jeho vyvýžení změní). Při nevyváženosti v některém vrcholu rotace v tomto vrcholu.<br /> <br /> Rotace:<br /> * '''Jednoduchá''' - nevyváženost způsobuje levá větev levého podstromu nebo pravá větev pravého podstromu. Kontrolujeme, zda kořen podstromu má stejné znamínko jako kořen nadstromu ???<br /> * '''Dvojitá''' - nevyváženost způsobuje pravá vetev levého podstromu nebo levá větev pravého podstromu. Provedeme nejdříve rotaci spodní větve, a tím se dostaneme na předchozí problém. <br /> <br /> Odebrání stejné jako u BVS - nahrazení prvku symetrickým následovníkem, po odstranění prvku prepočty rozdílu výšek kontrola vyváženosti smerem ke kořeni (od původní pozice symetrického následovníka - prvky prohozeny a zde odstraňován).<br /> <br /> // přidat obrázek<br /> <br /> == Red-Black ==<br /> <br /> Další modifikace BVS. Vrcholy obsahují navíc položku s informací o barve (cervená nebo cerná). <br /> Pravidla: <br /> koren je vždy cerný, <br /> cesty od korene do každého listu obsahují stejný pocet cerných vrcholu (cerná výška stromu), <br /> cervený vrchol má pouze cerné následovníky. <br /> <br /> Vkládaný vrchol je na zacátku vždy cervený, postupne od jeho pozice ke koreni kontrola pravidel a prípadná náprava<br /> <br /> - přebarvením vrcholů: pokud je rodič červený a jeho bratr také, oba přebarvíme na černé a jejich rodiče na černé) <br /> - pokud bratr rodiče červený není, přebarvíme na černo pouze rodiče a provedeme rotace <br /> - pokud je rodič levým synem, a vkládaný také, provedeme rotaci do prava (rodič se stane kořenem)<br /> - pokud je rodič levý, ale vkládaný pravý, provedeme nejprve rotaci do leva (vkládaný se stane rodičem) a tím získáme předchozí problém, tedy přebarvíme a zarotujeme do prava podle vkládaného prvku, který se stane kořenem. <br /> <br /> Rotace jsou stejné jako u AVL stromu. Odebrání - nahrazení symetrickým následovníkem, ten ale obarven barvou odebíraného vrcholu, a po té postupujeme stejně jako při vkládání, tedy od místa odebrání kontrola pravidel smerem ke koreni.<br /> <br /> <br /> == B-strom ==<br /> <br /> B-strom řádu m má v každém vrcholu nejvýše m následovníků. <br /> <br /> Pravidla:<br /> * klíčů ve vrcholu je o 1 méně než následovníků<br /> * všechny listy jsou stejně hluboko<br /> * všechny vrcholy mají nejvýše m následovníků<br /> * všechny vrcholy kromě kořene mají alespoň m&lt;sup&gt;2&lt;/sup&gt; následovníků<br /> * kořen je buď list nebo má alespoň 2 následovníky<br /> <br /> Ve vrcholech klíce serazené, vrcholy razeny jako u BVS (menší klíce vlevo, vetší vpravo). Pri vkládání se pridávají klíce do listu, pokud je v listu prekrocen maximální pocet (pretecení stránky), je list rozdelen uprostred a prostrední klíc vložen do rodice (zde opet kontrola prekrocení poctu). Odebereme-li klíc z listu a ten má potom príliš málo podtecení stránky), muže si vypujcit od sousedu (klíc z rodice do vrcholu, klíc ze souseda do rodice), pokud sousedi mají minimální pocet, dojde ke sloucení vrcholu s jedním sousedem a klícem z rodice. Pri odebírání z vnitrních vrcholu je nutné místo vždy zaplnit - klíc od potomka. Nemají-li potomci dost klícu, sloucí se dva potomci do jednoho. Implementace ukazateli s následovníky seznamem nebo polem, prípadne pomocí dvourozmerných polí (jedno pro klíce, jedno pro indexy následovníku, index korenu).<br /> <br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Abstraktn%C3%AD_datov%C3%A9_typy_z%C3%A1sobn%C3%ADk_fronta,_seznamy,_%C5%99ady,_vektory_a_jejich_implementace 2014-02-20T06:44:03Z

<p>Acolade: kategorizace</p> <hr /> <div>Zásobník, fronta, seznam viz. PPA2<br /> Obousměrná fronta - výběr a vložení možné na obou koncích (zásobník a fronta dohromady)<br /> <br /> Vektor - v podstatě spojový seznam, nebo seznam pomocí pole, kde má každá položka index od začátku, a tedy přístup pomocí indexů, a indexy jsou přerovnány (nevznikají díry). Nejde o pole, pokud do pole na index 3 uložíme hodnotu, bude vždy na indexu 3, ve vektoru se může posunovat prodáváním/mazáním prvků před ním.<br /> = ADT seznam, kde místo iterátoru použijeme indexer<br /> <br /> Řada - WTF? O tom jsem nikdy neslyšel, v přednáškách to není, na netu nic<br /> <br /> - SPEKULACE: Představil bych si ADT, kde je každý prvek stejného typu (do vektoů či seznamu by teoreticky bylo možné uložit i různé prvky, do řady ne. Otázkou je proč by to někdo potřeboval, když pak by bylo možné například ukládat pouze diference od předchozího objektu a možná ušetřit místo??<br /> <br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=%C3%9Avod_do_technologie_programov%C3%A1n%C3%AD_a_programovac%C3%ADch_styl%C5%AF,_objektov%C4%9B_orientovan%C3%BD_n%C3%A1vrh,_z%C3%A1kladn%C3%AD_UML_diagramy,_psan%C3%AD_program%C5%AF_v_Jav%C4%9B 2014-02-20T06:43:57Z

<p>Acolade: kategorizace</p> <hr /> <div>== Úvod ==<br /> Programování je proces vytváření software splňující určité funkce. K programování využíváme programovací jazyky, dříve procedurální (nestrukturované (asembler) - bez podprogramů, pouze skoky v programu (goto), nebo strukturované (basic, c, pascal) - podprogramy, skoky jen velmi vyjímečně), dnes nejčastěji objektově zaměřené (objekty jsou stavební kameny a obalují funkce, využití technik OOP).<br /> <br /> Dříve bylo programování spojeno s testováním, nyní je proces rozdělen do několika fází:<br /> <br /> '''Analýza''' - Sbírání informací od zákzníka či zadavatele<br /> <br /> '''Návrh''' - Návrh SW tak, aby splňoval požadavky analýzy<br /> <br /> '''Kódování''' - Implementace návrhu<br /> <br /> '''Ladění''' - Testování a odstraňování chyb<br /> <br /> <br /> == Styly ==<br /> <br /> '''Vodopád''' - fáze jdou za sebou, nevracíme se, ani neodbočujeme (nejstarší), týmy se zapojují do procesu pokud je na řadě jejich blok<br /> <br /> '''Formální''' - návrh je matematicky zcela do detailu popsán a jednotlivé bloky modelu jsou poté 1:1 implementovány<br /> <br /> '''Evoluční''' - začíná se malým funkčním SW, na který nabalujeme další funkce, ale nevíme, jaké funkce bude v budoucnu mít<br /> <br /> '''Iterativní''' - proces je rozdělen na iterace, v každé iteraci je naplánováno několik funkčností, iterace stejně dlouhé, po iteraci je SW vždy v kompletní spustitelné podobě<br /> <br /> '''Komponentový''' - využití hotových komponent, či implementace vlastních, po té stavění SW z komponent jako z kostek<br /> <br /> <br /> == Objektově orientovaný návrh ==<br /> <br /> OO umožňuje, a klade si za cíle:<br /> <br /> '''Znovupoužitelnost''' - abstraktní části kódu jsou univerzální a je tedy možné je používat stále dokola<br /> <br /> '''Robustnost''' - návrh předpokládá všechny vstup, nejen ty, které jsou očekávané<br /> <br /> '''Přispůsobivost''' - návrh lze pouze s minimálními zásahy do kódu použít na různých platformách<br /> <br /> <br /> == Pilíře OO návrhu ==<br /> <br /> '''Dědičnost, Zapouzdření, Polymorfysmus''' - PPA2<br /> <br /> '''Modularita''' - rozdělení programu na bloky - moduly<br /> <br /> '''Abstrakce''' - Návrh na abstraktní úrovni je snadno implementovatelný<br /> <br /> <br /> == Jazyk UML ==<br /> <br /> Jazyk pro abstraktní návrh OO SW, modelování SW před implementací, navrhujeme pouze strukturu, nikoliv funkčnost.<br /> Typy UML:<br /> <br /> '''diagram tříd a objektů''' - popisují statickou strukturu systému<br /> <br /> '''modely jednání (diagram případů užití)''' - dokumentují možné případy použití systému, události, na které musí systém reagovat<br /> <br /> '''scénáře činností (diagramy posloupností)''' - popisují scénář průběhu určité činnosti, těchto činností je model jednání složen<br /> <br /> '''diagramy spolupráce''' - zachycují komunikaci spolupracujících objektů<br /> <br /> '''stavové diagramy''' - popisují dynamické chování objektu nebo systému<br /> <br /> '''diagramy aktivit''' - průběh aktivit procesu nebo činností<br /> <br /> '''diagramy komponent''' - popisují rozdělení systému na funkční celky a definují náplň jednotlivých komponent<br /> <br /> '''diagramy nasazení''' - popisují umístění funkčních celků<br /> <br /> <br /> Pro návrh diagramu tříd máme následující parametry:<br /> <br /> Atributy a metody - definujeme viditelnost a vlastnosti (+ public, # protected, - private, / readonly, in/out směr)<br /> <br /> Třída: obdélník, název tučně, pak seznam atributá a metod<br /> <br /> Objekt: Název:Třída<br /> <br /> Dědičnost - šipka od potomka k rodiči, může být i vícenásobná<br /> <br /> Asociace - 0..1 1..1 0..N 1...N --&gt; šipka od první třídy a ta obsahuje odkazy/využívá x..y objektů druhé třídy (např Podvozek 1 ---&gt; 4 Kola ), nad šipkou název činnosti (pokud možno lepší než &quot;má&quot;)<br /> <br /> Kompozice - je li objekt v kompozici s jiným, je na něj silně vázán (například seznam a položka seznamu. seznam může existovat i bez položek, ale položka bez seznamu ne), značka prázdný kosočtverec<br /> <br /> Agregace - volná vazba, abstrakce &quot;používá&quot;, objekty však mohou fungovat i nezávisle na sobě (například počítače v síti), značka plný kosočtverec<br /> <br /> <br /> == Java ==<br /> <br /> '''Návrh''' - UML diagramy, CRC karty (karty, kde je pro každá blok sloupec Má za úkol a Vyžaduje). Je li toho na kartě příliš, je vhodné zvážit její rozdělení<br /> <br /> '''Implementace''' - podle návrhu, karta odpovídá třídě. <br /> <br /> '''Ladění a testování''' - kontrolní výpisy, logování, watch na proměnných, ..., po té test pro různá data (generovaná, &quot;nepříjemná&quot;) a sledování správnosti, rychlosti, využití zdrojů, uvolnění<br /> <br /> '''Dokumentace''' - štábní kultura, konvence pojmenovávání, komentáře, Javadoc komentáře a generovaná dokumentace<br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Kategorie:Fav-kiv-bzinf 2014-02-20T06:42:04Z

<p>Acolade: založení</p> <hr /> <div>Kategorie okruhů státní závěrečné zkoušky<br /> <br /> [[KIV/BZINF - Státnice pro informatiky]]</div>

Acolade https://www.512.cz/index.php?title=Klasifikace_probl%C3%A9m%C5%AF 2014-02-20T06:37:56Z

<p>Acolade: kategorizace</p> <hr /> <div>Rozhodovací problémy lze dělit do tříd složitosti<br /> P (polynomiální) - problém je řešitelný pomocí (deterministického) Turingova stroje (&lt;http://cs.wikipedia.org/wiki/Turing%C5%AFv_stroj&gt;) v Polynomiálním čase (např problém řazení), lze dokázat, že všechny problémy P jsou podmnožinou problémů skupiny NP (NP problém s jednou větví, NP problém bez hádání či nápovědy)<br /> NP (nedeterministicky polynomiální) - Polynomiální čas, ale nedeterministický Turingův stroj (takový, který může rozvětvit program v libovolném kroku na více větví, ve kterých hledá řešení současně (zcela paralelně), případně lze mluvit o stroji, který &quot;uhodne&quot; kterou větví se vydat, případně mu něco &quot;napoví&quot; kudy se má vydat, aby řešení bylo správné. Také lze mluvit o problémech, jejichž řešení lze ověřit v polynomiálním čase (zpětný postup, zjištění, zda je nalezené řešení opdpovídající problému), níkoliv jej získat - pokud bychom všechny větve umístili řekněme do zásobníku (zásobníkový Touringův stroj), čas pro nalezení řešení by nutně nebyl polynomiální. Je otázkou, zda lze pro NP problémy najít P řešení.<br /> NP-těžké - Problémy, na které lze v polynomiálním čase převést všechny problémy NP, nemusí však nutně v NP samy o sobě být (nemusí být ani rozhodovací)<br /> NP-úplné - NP-těžké problémy, které jsou ve třídě NP, jde tedy o nejtěžší NP úlohy<br /> <br /> [[Soubor:Np-problemy.jpg]] <br /> <br /> A dále je tu složitost problémů, viz 6<br /> <br /> {{fav-kiv-bzinf}}<br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Algoritmick%C3%A1_%C5%99e%C5%A1itelnost_probl%C3%A9m%C5%AF 2014-02-20T06:37:23Z

<p>Acolade: kategorizace</p> <hr /> <div>Problém definujeme jako binární relaci mezi množinou instancí problému I (tj. množinou všech možností vstupu) a množinou rešení S. Dve instance mohou mít stejné rešení, stejne tak jedna muže mít více rešení. Algoritmická rešitelnost zkoumá, zda pro všechny formulovatelné problémy lze nalézt algoritmus rešení.<br /> <br /> Ve 30.l. 20.st. objevil Alan Turing formální opis algoritmu - Turinguv stroj, ve spojení s Alonzem Churchem vytvorili Churchovu-Turingovu tezi a sice, že každý algoritmus (ne problém!) lze vykonat Turingovým strojem. Tezi lze vyvrátit nalezením algoritmu nevykonatelného TS. Moderní programovací jazyky pak byly navrženy tak, aby libovolný program šlo prevést na TS a naopak. Problém, který nelze vyrešit pomocí TS, tedy ani pomocí programu, je pak algoritmicky nerešitelný.<br /> <br /> Vytvoríme-li takový rozhodovací problém (rešení je ano/ne), který pro každý rozhodovací algoritmus a alespon jeden jeho vstup dává pro tento vstup opacnou odpoved, než daný algoritmus se stejným vstupem, takový problém není rešitelný žádným z techto algoritmu a je tedy nerozhodnutelný. <br /> <br /> První takový problém - problém zastavení - našel sám Turing: program má o všech vytvoritelných programech rozhodnout, zda pro každý ze vstupu<br /> daný program zastaví (tehdy vrací jeho výstup v podobe prirozeného císla + 1) nebo nezastaví (pak vrací 0). Takový program to ale nedokáže rozhodnout sám o sobe (pokud by byl vytvoritelný, patril by mezi zkoumané programy také a musel by ve svém výstupu vrátit svuj výstup + 1, což nejde).<br /> <br /> {{fav-kiv-bzinf}}<br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Rozhran%C3%AD 2014-02-20T06:37:17Z

<p>Acolade: kategorizace</p> <hr /> <div>Objektově orientované jazyky poskytují pro realizaci tříd, kromě dědičnosti, dalši prostředek - rozhraní. Rozhraní definuje soubor metod bez jejich implementace (podobně jako kompletně virtuální třída). Analogie je v rozepsané kuchařce, kdy víme co to bude za jídlo a z čeho budeme vařit, ale postup neznáme. Třída, která implementuje toto rozhrani (tj. implementuje - definuje - všechny jeho metody), je po té v polymorfovatelná do ukazatele definovaného tímto rozhraním, což znamená, ze klient ví, že tato třída má implementované všechny metody, které potřebuje (a které jsou definované v rozhraní).<br /> <br /> // trochu divoký vysvětlení<br /> <br /> Deklarace rozhraní je podobná deklaraci třídy<br /> <br /> interface jmeno {<br /> // hlavicky metod, všechny samozřejmě virtuální a abstraktní<br /> }<br /> <br /> V Javě se implementace rozhraní zapiše pomoci kličoveho slova implements<br /> <br /> Trida implements Rozhrani {<br /> ...<br /> }<br /> <br /> V jiných jazycích (C++, C#, ...) používáme dvojtečku, přičemž první třída za dvojtečkou je obvykle dědění, ostatní jsou implementace rozhraní (i když v C++ je to jedno, tam můžeme implementovat i dědit od více tříd). Implementovat můžeme i několik rozhraní (například implements Cloneable, Runnable)<br /> <br /> Může se stát, že 2 rozhraní mají stejné metody k implementaci. Implementovat je tedy možné <br /> * '''Implicitně''' - Implementujeme metodu první nalezené metody s tímto jménem ve všech rozhraních, nebo selže, záleží na jazyku<br /> * '''Explicitně''' - Implementujeme metodu tak, že řekneme kterou metodu kterého rozhraní implementujeme např:<br /> public this.type Cloneable.Clone() {<br /> // tělo <br /> }<br /> <br /> Nejsilnější zbraní rozhraní je, že odděluje kód od definic (vhodné např. pro pluginové systémy) a je sdružuje třídy do jedné skupiny funkčnosti.<br /> <br /> <br /> {{fav-kiv-bzinf}}<br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=D%C4%9Bdi%C4%8Dnost 2014-02-20T06:37:10Z

<p>Acolade: kategorizace</p> <hr /> <div>Základním stavebním blokem OOP je dědičnost. Dědění je způsob deklarace třídy tak, že využijeme jinou třídu jako předka. <br /> Naše děděná třída tedy může <br /> <br /> Převzít metody a atributy předka<br /> Definovat nové metody a atributy<br /> Přepsat metody a atributy předka<br /> <br /> Ve většině jazyků jsou všechny třídy implicitně děděny od třídy Object. Ve většině jazyků (snad kromě C++) zle dědit pouze od jedné třídy. Pro další dědění lze použít rozhraní. <br /> <br /> V Javě dědíme pomocí klíčového slova extends, tedy<br /> <br /> Class B extends A {<br /> }<br /> <br /> V jiných jazycích (C++, C#, ...) používáme dvojtečku, přičemž první třída za dvojtečkou je obvykle dědění, ostatní jsou implementace rozhraní (i když v C++ je to jedno, tam můžeme implementovat i dědit od více tříd)<br /> <br /> S pojmem dědění úzce souvisí i pojem Polymorfismus. Ten nám umožňuje nejen hiearchii objektů rozšiřovat, ale také ji využívat opačným směrem, tedy dědí-li třída B od třídy A, můžeme použít konstrukci (přiřazení)<br /> <br /> B b = new B();<br /> A a = b;<br /> <br /> To je extrémně důležité pro ADT, kdy vytvoříme strukturu pro A, a můžeme do ní ukládat objekty A i B.<br /> <br /> Otázka je, pokud voláme metody A.Metoda, a metoda B tuto metodu má také, co se děje?<br /> Pro snažší pochopení řekněme, že máme typ pointeru a typ objektu. V předchozí ukázce je a typu A a b typu B, ale typ pointeru a je A a typ objektu (pod tímto pointerem) a je B.<br /> <br /> Některé jazyky podporují Virtualitu metod. Virtuální metoda je metoda, která (je li překryta) je volána vždy z typu objektu, který překrývá. Pokud překryta není (nebo pokud je volána z třídy, která tuto virtuální metodu obsahuje), volá se ona. Voláme-li tedy a.Metoda() z předchozího příkladu, zavolá se ve skutečnosti b.Metoda(), protože a ukazuje na typ b. Java má všechny metody virtuální. <br /> <br /> Druhou možností je použít nevirtuální metody. Taková metoda nemůže být překryta, nicméně může být znovu vytvořena (předefinována řekněme) pro daná objekt. V praxi to znamená, že je volána z typu Pointeru který na objekt ukazuje, tedy voláme li a.Metoda() zavoláme opravdu a.Metoda().<br /> <br /> Za poslední zmínku stojí Kovariance typů. Ta znamená, že je li typ kovariantní, lze vzájemně přiřazovat obalující typy, tedy lze provést např.<br /> <br /> pokud B extends A: <br /> <br /> List&lt;A&gt; a = new List&lt;B&gt;();<br /> <br /> tedy je li B potomkem A, je li List&lt;B&gt; potomkem List&lt;A&gt;. Tento mechanismus však ve většině jazyků nefunguje, a je nutné vytvořit List&lt;A&gt; a naskládat do něj objekty B, a při výběru je jeden po druhém přetypovat zpět na B, jelikož List&lt;A&gt; vrací objekty typu A.<br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Generi%C4%8Dnost 2014-02-20T06:37:03Z

<p>Acolade: kategorizace</p> <hr /> <div>Genericita je možnost programovaciho jazyka definovat místo typů jen „vzory typů“, kde typy proměnných, použité v definici typu (rozuměj v typu jako ADT), jsou vyvedeny vně definice jako parametry a jsou určeny později klientskou aplikací. Základnim užitím genericity jsou třidy kontejnerů, které jsou určené k udržování skupin objektů určitého typu, například vzor třidy Seznam je definovan vlastně jako Seznam&lt;G&gt;, kde G je typ objektů, ktere mohou být do seznamu vloženy (kouzlo genericity vynikne pak v kombinací s dědičností, kdy do seznamu mohou být vloženy nejen objekty typu G, ale i objekty všech možnych dědiců třídy (typu) G). Konkrétní typ, použitelný v textu programovacího jazyka pak vzniká, když G nahradíme skutečným existujícím typem.<br /> <br /> Příklad:<br /> <br /> Máme List&lt;T&gt; kde T je libovolný typ. Když List alokujeme, použijeme List&lt;int&gt; intList = new List&lt;int&gt;(), a tento list poté akceptuje jen čísla typu int.<br /> <br /> Extrémní případy dovolují mnohé šílenosti, jako třeba <br /> List &lt; List &lt; List &lt; HodnotaTabulky &gt; &gt; &gt;<br /> je seznam tabulek :D<br /> <br /> Pokud definujeme vzor (template, proto se používá T), používáme místo int prostě zástupce T<br /> <br /> Např.<br /> <br /> public interface List&lt;T&gt; { // vytváříme interface, který říká, že nad typem &lt;T&gt; bude list<br /> void add(T x); // Operace přidání prvku (typu &lt;T&gt;)<br /> Iterator&lt;T&gt; iterator(); // Struktura má iterátor, který definujeme níže<br /> }<br /> <br /> public interface Iterator&lt;T&gt; { // Iterátor pohybující se po prvcích typu &lt;T&gt;<br /> T next(); // Metoda vrací další prvek v pořadí<br /> boolean hasNext(); // Jen aby bylo vidět, že nemusíme jen vracet &lt;T&gt;<br /> }<br /> <br /> Což je takhle k ničemu, protože typ T kromě hodnoty nemá nic, co bychom mohli využít. Použijeme tedy obalení do třídy, např<br /> <br /> public class Wrapper {<br /> T value;<br /> Wrapper next();<br /> }<br /> <br /> a s tou pak pracujeme.<br /> <br /> V některých jazycích lze T omezit, třeba jen na typy implementující Iterable.<br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Doln%C3%AD_omezen%C3%AD_pro_porovn%C3%A1vac%C3%AD_%C5%99azen%C3%AD 2014-02-20T06:36:57Z

<p>Acolade: kategorizace</p> <hr /> <div>Celkem HC otázka, asi nejtěžší z PPA, kvůli matematice, kterou my programátoři moc nemusíme (kdo říká, že to není pravda, tak lže sám sobě, nebo neumí programovat s tím, co je k dispozici a vše si musí do podrobna analyzovat)<br /> <br /> Zkoumejme dolni omezeni počtu porovnani T(n) pro porovnávaci algoritmy řazení.<br /> <br /> [[Soubor:Dolni-omezeni.jpg]]<br /> <br /> <br /> Předpokladejme, že všechny prvky posloupnosti a1, a2, ..., an jsou různé. Porovnavací řazeni můžeme znázornit rozhodovacim stromem. Ve vnitřních vrcholech jsou prvky, ktere algoritmus porovná a v listech je permutace všech prvků původni posloupnosti, ktera je seřazena.<br /> <br /> Přiklad rozhodovaciho stromu pro řazeni vkladanim tři prvků:<br /> Jakykoliv 100% správný algoritmus (brutální síla) musi vytvořit každou z n! permutací prvků původní posloupnosti a zjistit, která je seřazená. Každou z takových permutací umístíme do stromu, ve kterém je v kořenech naznačeno porovnání, kterým se k permutacím dostaneme.<br /> <br /> Nejhoršim připadem počtu porovnani vykonanych algoritmem řazeni je nejdelši cesta od kořene stromu k listu, je tedy rovna vyšce stromu T(n) = h . <br /> <br /> Nyní musíme najít dolní omezení všech rozhodovacích stromů. Nechť rozhodovaci strom o výšce h má l listů, potom l = 2h (binární strom má maximálně 2h listů). Současně listů musi byt alespoň tolik, kolik je permutaci, tedy n! = l. <br /> Potom n! = l = 2h a po logaritmování (zjištění délky cesty, každá vrstva x grafu má 2x možných cest (2x listů), takže číslo vrstvy a tedy i délka ke kořeni je funkce inverzní, tedy log2x)<br /> <br /> log2 (n!) = log2 2h = h log22 = h * 1 = h = počet porovnání, kterým se dostneme k permutaci<br /> <br /> Použitim aproximace (n/e)n = n! je<br /> <br /> log2(n!)=n * log2 (n/e) = log2 n- n* log2 e,<br /> <br /> čim dostavame dolni omezeni pro nejhorši připad Ω(n*log2 n). (n * konstanta = n)<br /> <br /> Protože pro řazeni haldou a slučovanim jsou shora omezeny časem vypočtu Ω(n*log2 n), jsou tato řazeni asymptoticky optimalni.<br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Algoritmy_%C5%99azen%C3%AD_O(N_logN) 2014-02-20T06:36:50Z

<p>Acolade: kategorizace</p> <hr /> <div>// přidat ukázky<br /> <br /> Společné pro všechny: Řadíme stromem.<br /> <br /> == Řazení haldou (heapsort) ==<br /> <br /> Na začátku je neseřazené pole. Postupně obnovujeme nad tímto polem haldu pro první dva, tři, čtyři atd. prvky, až<br /> máme na poli vytvořenu haldu. Následně zaměníme nejvyšší prvek (vyjmeme ho) s posledním a obnovíme<br /> vlastnost haldy na n−1 prvcích. Obnovení haldy je O(log n) a obnovujeme po každém výběru, tedy O(n log2n) <br /> To opakujeme až zbude jednoprvková halda a celé pole je seřazené. Nestabilní (složitost závisí na vstupních datech).<br /> <br /> V kostce: na poli uděláme haldu a max prvky vyměňujeme s posledními prvky haldy a haldu obnovujeme.<br /> <br /> <br /> == Shellovo řazení (shellsort) ==<br /> <br /> Posloupnost rozdělíme na podposloupnosti s krokem h (každý h-tý počínaje prvním, počínaje druhým až<br /> počínaje h − 1-ním), které nezávisle seradíme vkládáním (insertsortem). Následne snižujeme hodnotu h a<br /> provádíme totéž až do serazení s h = 1. Prvky daleko od své výsledné pozice se k ní dostanou v menším<br /> počtu kroků, než u obyčejného insertsortu.<br /> <br /> * Shell - počátecní h = polovina délky pole, snížení vydělením dvěma<br /> * Knuth - posloupnost 3i + 1, počáteční h = její prvek v nejbližší třetině délky pole<br /> <br /> Jednoduchý a efektivní algoritmus, složitá analýza, nestabilní.<br /> <br /> V kostce: rozdělení do stromu podle kroku (třeba na osminy), insertsort větví, a pak insertsort čtvrtin, polovin, konec<br /> <br /> Poměrně zajímavě udělaná ukázka z kartama: http://www.youtube.com/watch?v=QG8hs0wqmqk<br /> <br /> == Řazení dělením (splitsort, quicksort) ==<br /> <br /> Určíme prvek, jehož hodnota bude rozdělovat pole (pivot). Procházíme z obou stran pole a menší hodnoty<br /> vpravo prohazujeme s vetšími vlevo, až se oba průchody potkají. Na tuto pozici přesuneme pivot - vlevo jsou<br /> hodnoty menší, vpravo vetší. Totéž provedeme s částí pole vlevo od pivotu i vpravo od nej. Rekurze končí,<br /> je-li předán pouze jeden prvek k seřazení. Nejčasteji se pivot určuje jako krajní prvek pole (nezasahuje pak<br /> do procesu dělení). Lze použít zásobník místo rekurze. Snadno implementovatelné, nestabilní.<br /> <br /> V kostce: rozdělení do stromu podle pivotů (prvek velikostně cca uprostřed podstromu, ideálně medián, ale může být i náhodný), <br /> v každém podstromu vzájemně vyměníme větší a menší prvky než pivot.<br /> <br /> Výukové videjko: http://www.youtube.com/watch?v=y_G9BkAm6B8<br /> <br /> == Řazení slucováním (mergesort) ==<br /> <br /> Pole je rekurzivně rozdělováno na poloviny. Dojdeme až na úroveň dvojic prvku, které seřadíme (sloučíme).<br /> O úroven výše opět po dvojicích sloučíme (kopírujeme vždy menší prvek z obou polí a posuneme se za nej)<br /> a postupujeme až sloučíme obě poloviny původního pole. Je to nejčasteji používaná metoda a je stabilní.)<br /> <br /> V kostce: jako když mícháme karty - 2 balíčky a děláme [[Soubor:Mergesort.jpg]] <br /> ???????<br /> <br /> . Procházíme 2 podstromy a řadíme posunem <br /> 2 indexů, jeden v každém podstromu, a vždy zapíšeme větší prvek pod jedním z indexů, který posuneme<br /> <br /> Bezva video - http://www.youtube.com/watch?v=GCae1WNvnZM<br /> <br /> <br /> Nestabilní metody lze &quot;zestabilnit&quot; například zpřeházením dat na vstupu.<br /> <br /> Radix sort =???<br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Halda 2014-02-20T06:36:41Z

<p>Acolade: kategorizace</p> <hr /> <div>Halda je datová struktura, která má následující vlastnosti:<br /> <br /> * Jde o strom<br /> * Pokud C je potomkem P, potom hodnota h(C) &lt;= h(P)<br /> <br /> Tato halda se nazývá MaxHeap (maximální halda), protože má v kořeni vždy větší prvek. Existuje také minHeap (minimální halda), které je seřazena opačně. <br /> <br /> <br /> == Implementace ==<br /> <br /> Nejjednodušší haldou může být seřazené pole či seznam. Nejčastěji se však používá binární halda, a pojmem halda tuto binární haldu většinou myslíme, existují však i další (binominální, Fibonacciho, měkká ...)<br /> <br /> Binární halda má ještě jednu vlastnost, vyváženost (vlastnost tvaru, úplnost stromu). Ta říká, že je halda buď vyvážená (všechny listy jsou na stejné úrovni h) a nebo je plněna zleva do prava.<br /> <br /> <br /> == Vlastnosti ==<br /> <br /> Vyhledání nejvyššího prvku v haldě je triviální (jde o kořen haldy, tedy O(1))<br /> <br /> Vkládání prvku probíhá tak, že jej vložíme do nejnižší úrovně haldy, co nejvíce doleva. Pokud je tímto porušena vlastnost haldy, vyměníme prvek s jeho rodičem a opakujeme, dokud není vlastnost haldy zcela obnovena.<br /> <br /> Mazání prvku je podobné. V binární haldě jej provádíme tak, že najdeme prvek, který je na nejnižší úrovni zcela vlevo (mimochodem, to se dá v poli zařídit indexem, v objektech ukazatelem), vyměníme jej s mazaným prvkem a obnovíme vlastnost haldy. Mazaný prvek z haldy po té samozřejmě vyjmeme.<br /> <br /> Implementace na poli:<br /> Má-li prvek na indexu k v poli potomky, jsou na indexech 2k+1 a 2k+2. Splněním doplňkového pravidla haldy v poli nebudou mezery, a pozice pro vložení prvku či výměnu prvku při mazání je na konci pole<br /> <br /> Implementace objektově<br /> Jako spojová struktura, je však nutné udržovat pointer na rodiče nejnižší úrovně (to může být problematické a pomalé)<br /> <br /> {{fav-kiv-bzinf}}<br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Prioritn%C3%AD_fronta 2014-02-20T06:35:57Z

<p>Acolade: kategorizace</p> <hr /> <div>Speciální případ ADT podobne jako zásobník a fronta, výběr odebere prvek s nejvyšší či nejnižší prioritou (maximová resp. minimová PF) Vkládat lze prvky s libovolnou prioritou. <br /> <br /> <br /> '''Implementace:''' polem / spoj.seznamem<br /> <br /> <br /> == Složitost podle přístupu: ==<br /> <br /> Rozhraní<br /> * vytvoření prázdný fronty<br /> * test prázdné fronty<br /> * vložení a výběr prvku<br /> <br /> '''Lazy:''' <br /> Pole či seznam je neuspořádaný, vkládáme prvek vždy na konec v poli (O(1)) a na začátek v seznamu (O(1)). Při výběru musíme najít maximum, v obou případech O(n)<br /> <br /> '''Eager:'''<br /> Pole či seznam je uspořádaný, prvek vkládáme tak, aby byla struktura seřazena. Vložení je O(n), ale výběr je O(1) (ze začátku seznamu / konce pole)<br /> <br /> '''Kombinace:'''<br /> Implementace pomocí BVS nebo haldy - vložení i výber O(log2n)<br /> <br /> <br /> == Modifikovatelná prioritní fronta ==<br /> <br /> Pomocí haldy, a <br /> # přidáme mapu prvek-&gt;pozice v haldě. Změnou priority a obnovením haldy je možné v O(log2n) prioritu i měnit <br /> # bez mapy je hledání prvku v haldě další O(log2n) čas, celkem tedy hledání O(log2n) + obnovení haldy O(log2n)<br /> <br /> Pokud proritu příliš neměníme, způsob 1 je výhodnější, ale paměťově náročnější<br /> <br /> {{fav-kiv-bzinf}}<br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Rozptylov%C3%A9_tabulky_s_s_vn%C4%9Bj%C5%A1%C3%ADm_%C5%99et%C4%9Bzen%C3%ADm 2014-02-20T06:35:51Z

<p>Acolade: kategorizace</p> <hr /> <div>HASH<br /> Pokud máme množinu záznamů, ve které mohou v klíčích existovat duplicity pro různé hodnoty (například tabulka slov podle prvího písmena). Pro tento přístup je nemožné používat přímé adresování, jelikož by docházelo ke kolizím.<br /> <br /> [[Soubor:Rozptylova-tabulka.jpg]]<br /> <br /> Můžeme ale v poli využít prázdná místa a do nich duplicitní hodnoty ukládat. Vyhladávání a ukládání potom obecně nebude v konstantním čase. Můžeme tedy například uložit duplicitní hodnotu do následujícího prázdného místa v tabulce. Problémy jsou však následující:<br /> <br /> Můžeme zabrat místo pro klíč, který má na toto místo právoplatný nárok (kolize tedy nastanou nejen pro hodnoty se stejným klíčem, ale i obecně pro libovolný klíč)<br /> Odsuneme-li i tento klíč, dojde k vytváření shluků (a nabalovíní dalších klíču na tyto shluky, na obr. skluk od písmene A)<br /> Dochází také k fragmentaci, je tedy nutné hledat až do prvního prázdného klíče, což je při shlukování a vyšší saturaci tabulky pomalé<br /> <br /> <br /> Tento přístup tedy použijeme, pokud vímě, že jsou klíče hodnot rovnoměrně rozmístěny, a že hodnot není více než klíčů, a nazývá se vnitřní zřetězení.<br /> <br /> Vnější zřetězení znamená, že ke kažnému klíči přiřadíme seznam hodnot. Nedochází tedy ke kolizím, ale vyhledání hodnoty je O(m), kde m je počet hodnot ke každému klíči, tedy nejhůže O(n) (všechny hodnoty jsou v jednom klíči). Tento způsob však zvládá i situace, kde je více hodnot než klíčů<br /> <br /> Rozptýlení klíčů.<br /> <br /> Pro vnitřní zřetezení lze použít lepší vyhledáváci (a ukládací) funkci, než lineární posun, třeba kvadratickou fci. Kvadratická funkce se může protonout s jinou kv. fcí s jiným počátkem jen jednou) Tím omezíme clustery a kolize, a ukládání a hledání je rychlejší.<br /> <br /> Pro vnější zřetezení, nebo pokud je při vnitřním zřetězení mnoho podobných klíčů, je vhodné použít orákulum, rozptylovou (hashovací) funkci. Ta má 2 vlastnosti:<br /> <br /> Namapuje hodnoty do rozsahu počtu klíčů<br /> Ideálně zruší nebo alespoň naruší vztahy mezi podobnými klíči<br /> <br /> Příklad: Slovník se vnitřním zřetězením. Slovo převedeme na číslo součtem ASCII hodnot znaků<br /> <br /> Vlastnost 1: na toto číslo použijeme operaci modulo. Tato operace je pomalá (jde o dělení), použijeme tedy ideálně velikosti tabulky, které jsou mocninou 2, a po té je dělení pouhým bitovým posunem<br /> Vlastnost 2: vazby v tomto postupu existují (například anagramy se namapují do stejného pole). Použijeme tedy například následující postup: (( (1. písmeno * (2k+1) ) + 2. písmeno) * (2k+1)) + ... Tím zrušíme vazby mezi podobnými slovy. (2k+1) použijeme, protože jde o bitový posun a přičtení 1, což je velmi rychlé a 1 přičítáme, protože by poté modulo ztratilo význam.<br /> <br /> Mohli bychom použít i kdyptografické hashování, jako MD5, to je však pro O(1) přístup k seznamům příliš pomalé.<br /> <br /> {{fav-kiv-bzinf}}<br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Tabulka_s_p%C5%99%C3%ADm%C3%BDm_adresov%C3%A1n%C3%ADm 2014-02-20T06:35:46Z

<p>Acolade: kategorizace</p> <hr /> <div>Máme skupinu záznamů, které jsou jednoznačně identifikovány klíčem a mají přiřazenou hodnotu (například slova ve slovníku, nebo seznam studentů podle osobního čísla). Takováto struktura se nazývá ADT Tabulka.<br /> <br /> Složitost operací lze podle způsobu implementace rozdělit následovně:<br /> <br /> <br /> == Tabulka obsahuje mnoho hodnot vzhledem k počtu klíčů ==<br /> (např. seznam otázek k SZZ z předmětu PPA2). Zde je vhodné použít pole, otázky jsou číslovány, a tyto čísla použít jako index do pole otázek. Každá otázka pak má Předmět, zadání, .... Hledání v takové tabulce je pak O(1). Do této skupiny by mohly patřit i problémy, kdy je možné prvky v lineárním čase indexovat tak, že je tento index získán v konstantním čase (například den v roce pro adresování stránky v deníku)<br /> <br /> <br /> == Tabulka obsahuje mnoho klíčů a méně hodnot ==<br /> (Například počty výskytů slov této otázky. Čěština má cca 300 000 slov, ale v textu jich unikátních bude hrstka). Pro takové problémy se implementace pomocí pole nehodí, protože plýtváme pamětí (vetšina pole bude hodnota 0). <br /> Pro adresování tedy použijeme například spojový seznam. Vložení klíče je O(1), ale hledání klíče je O(n), protože musíme projít všechny položky a pro <br /> každou se podívat, jaký klíč obsahuje. <br /> Toto lze zrychlit použitím například BVS, potom bude hledání O(log n) a zásid také O(log n), kde n je počet klíčů stromu. Pokud bychom měli příklad se slovy v článku, bylo by rychlejší použít například strukturu Trie, která má vyhledávání a zápis závislý na délce slova (za předpokladu, že Trie použije v každém uzlu tabulku s přímým adresováním podle znaku. Použijeme trochu více paměti, ale pořád méně než při ad 1)<br /> <br /> <br /> == Tabulka obsahuje mnoho hodnot pro menší množství klíčů ==<br /> Tato možnost se přímým adresováním řešit nedá, klíče nejsou unikátní. Je nutné použít rozptylové tabulky<br /> <br /> {{fav-kiv-bzinf}}<br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Topologick%C3%A9_%C5%99azen%C3%AD 2014-02-20T06:35:40Z

<p>Acolade: kategorizace</p> <hr /> <div>Máme množinu prvků, ve které je definována množina dvojic, které jsou uspořádánvy v určitém pořadí. Tuto množinu lze zakreslit jako orientovaný graf, kdy každá hrana reprezentuje pořadí prvků. <br /> <br /> Jako příklad může posloužit proces oblékání.<br /> <br /> [[Soubor:Topologicke-razeni-1.jpg]] <br /> <br /> Dvojice jsou (musíme obléci):<br /> * Ponožky dříve než boty<br /> * Spodky dříve než kalhoty<br /> * Kalhoty dříve než boty<br /> * Košili dříve než sako<br /> * a hodinky nezávisle na zbytku<br /> <br /> V grafu vidíme, že obsahuje 3 komponenty, a že neobsahuje cykly. Pokud orientovaný graf neobsahuje cykly, nazývá se orientovaný acyklický graf (anglicky DAG, directed acyclyc graph). V takovém grafu lze nalézt uspořádání takové, že prvky budou chronologicky za sebou podle toho, v jakém pořadí je třeba je projít (vykonat jejich akce, obléci daný kus oblečení), např. takto<br /> <br /> <br /> Jedním z algoritmů je Topologické řazení pomocí DSF:<br /> <br /> Projdeme graf pomocí DFS, a při každé operaci (každém obarvení: nalezení/přesun na vrchol (šedá) a dokončení vyhledávání okolních vrcholů (černá)) pamatujeme čas, ve kterém jsme operaci provedli. První číslo udává &quot;čas&quot; nalezení vrcholu, druhé &quot;čas&quot; zpracování vrcholu.<br /> Pokud je vrchol dokončen, vložíme jeho prvek jej do zásobníku<br /> Výběrem všech prvků zásobníku získáme pořadí, ve kterém lze prvky [vykonat, použít, vypsat] tak, že jsou splněny jejich závislosti na poředí vykonání<br /> <br /> [[Soubor:Topologicke-razeni-2.jpg]]<br /> <br /> Na obrázku je vidět, že seřazení může být různé pro různé výchozí body hledání (v našem případě spodky, košile, sako). Je úplně jedno, v jakém vrcholu začneme graf prohledávat, protože díky ukládání do zásobníku se ve výsledku vždyy seřadí tak, jak potřebujeme. (př: když začneme od kalhot, tak se na dno zásobníku uloží boty a nad ně kalhoty. Tady jsme skončili, takže pokračujeme v prohledávání od jiného nenavštíveného uzlu - třeba od spodků. Ty se tedy uloží nad boty a kalhoty, takže když vybíráme ze zásobníku, dostaneme správně spodky-&gt;kalhoty-&gt;boty. Pokud bychom místo spodků pokračovali třeba ponožkami, nic se nestane, jen bude do této podloupnoosti vložen ještě prvek ponožky: spodky-&gt;ponožky-&gt;kalhoty-&gt;boty, ale posloupnost bude stále zachována taková, aby položky následovaly tak jak mají.)<br /> <br /> {{fav-kiv-bzinf}}<br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Prohled%C3%A1v%C3%A1n%C3%AD_graf%C5%AF 2014-02-20T06:35:34Z

<p>Acolade: kategorizace</p> <hr /> <div>== Barvení grafu ==<br /> Pro přehlednost při procházení grafem jednostlivé vrcholy obarvujeme<br /> <br /> * '''bílá''' - tento vrchol algoritmus ještě nezpracoval<br /> * '''šedá''' - vrchol byl navštíven, ale ještě se k němu budeme vracet<br /> * '''černá''' - vrchol je zpracován, už se k němu vracet nebudeme<br /> <br /> Na začátku jsou všechny vrcholy samozřejmě bílé a postupně během průchodu je teprve bravujeme.<br /> <br /> Prohledávací algoritmus končí v případech, kdy:<br /> * nalezneme požadovaný vrchol<br /> * nebo jsou všechny vrcholy grafu obarvené na černo<br /> <br /> <br /> == Prohledávání do šírky ==<br /> (breadth-first search, BFS) <br /> <br /> Realizace pomocí fronty<br /> <br /> Vybereme počátecní vrchol, obarvíme na šedo a projdeme všechny jeho sousedy. Nenalezneme-li řešení, obarvíme počáteční vrchol na černo a pokračujeme výběrem každého z jeho sousedů a opet projdeme jejich sousedy, které obarvujeme. Sousedy zatím nevybíráme, zpracováváme nejprve vrcholy právě vybraného vrcholu tak dlouho, dokud tento není obarven na černo.<br /> <br /> Lze také k vrcholům ukládat předchudce a pocet hran od pocátecního vrcholu, címž získáme (nejkratší) cestu k počátečnímu vrcholu a její délku. Prohledáním celého grafu získáme BFS strom. Implementace pomocí fronty, složitost O(|H| + |V|).<br /> <br /> <br /> == Prohledávání do hloubky ==<br /> (depth-first search, DFS) <br /> <br /> Realizace pomocí zásobníku<br /> <br /> Z počátecního vrcholu jdeme do jeho prvního souseda, z něj do jeho prvního souseda atd., které obarvujeme na šedo. Vybíráme ze sousedů vrcholy, které jsou bílé, které okamžite barvíme na šedo. Pokud projdeme všechny vrcholy, obarvíme vrchol na černo. a vracíme se na šedý vrchol.<br /> Pokračujeme do nalezení hledaného vrcholu nebo prohledání všech.<br /> <br /> Prohledáním celého grafu získáme DFS strom. Implementace rekurzí nebo zásobníkem, složitost O(|H|+|V |). <br /> <br /> <br /> <br /> Hrany orientovaného grafu: Stromové hrany (patrící do stromu, jejich směr je od výchozího vrcholu), Zpětné hrany (opačná hrana ke hraně stromové, vytváří malý cyklus, směr je do výchozího bodu), dopředné (nemusí ležet ve strome, ale její vyrcholy v něm leží, jakésy zkratky stromem) a križující (opacné k dopredným, nebo hrany mezi stromy lesa). Zpětné a křižující hrany indikují cykly v grafu.<br /> <br /> Je-li graf rozdelen do nekolika izolovaných cástí, zbudou po prvním prohledávání bílé vrcholy. Mužeme vybrat jeden jako další pocátecní a znovu z neho spustit vyhledávání, prípadne postup opakovat, pokud zustanou opet bílé vrcholy. Získáme tím les stromů.<br /> <br /> Jsou-li grafy orientovány, je vhodné začínat na vrcholu, do kterého nevede hrana, aby nedošlo ke zbytečnému roztržení grafu na komponenty<br /> <br /> {{fav-kiv-bzinf}}<br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Grafy_a_jejich_implementace 2014-02-20T06:35:27Z

<p>Acolade: kategorizace</p> <hr /> <div>Graf je reprezentován množinou vrcholů (uzlů) V, které mohou být spojeny určitým počtem hran H. Graf je poté definován jako G(V,H)<br /> <br /> * '''Neorientovaný graf''': Hrany grafu nejsou orientované, tedy pokud vede hrana z uzlu 1 do uzlu 5, vede i z uzlu 5 do uzlu 1 a platí tedy (u1, u2) = (u2, u1)<br /> * '''Orientovaný graf''': Hrany grafu jsou orientované (jednosměrné), tedy pokud vede hrana z uzlu 1 do uzlu 5, nevede automaticky zpět z uzlu 5 do uzlu 1 a platí tedy (u1, u2) != (u2, u1)<br /> <br /> <br /> * '''Ohodnocený graf''': Každá hrana má přižezenou svoji hodnotu (číslo). Tyto hodnoty pak udávají například délku hrany, propustnost nebo třeba cenu za přechod po dané hraně.<br /> * '''Neohodnocený graf''': Všechhny hrany grafu jsou si rovny (v podstatě jsou všechny ohodnoceny stejným číslem), takže nemá smysl uchocácat informaci o jejich ohodnocení.<br /> <br /> <br /> == Implementace grafu pomocí spojového seznamu (seznam sousednosti) ==<br /> <br /> [[Soubor:Graf-spojovy-seznam.jpg|500px]]<br /> <br /> Máme seznam vrcholů a pro každý z nich máme seznam vrcholů, se kterými sousedí. Lze tak implementovat všechny 3 typy grafů (v obousměrných budou sousednosti v seznamech obou vrcholů sdílejících hranu, ohodnocení vrcholů je uloženo v seznamu vrcholů, ohodnocení hran je v seznamu sousednosti)<br /> <br /> Problém metody je v složitosti hledání existence hrany, jelikož musíme procházet seznamy sousednost (Pro velké grafy pomalé, na druhou stranu pro řídké grafy méně pamětově náročné)<br /> <br /> == Implementace grafu pomocí matice sousednosti ==<br /> <br /> Stejný graf jako v předchozím případě<br /> <br /> [[Soubor:Graf-seznam-sousednosti.jpg]] <br /> <br /> Vytvoříme matici v*v prvků, kde v je počet vrcholů a hrany reprezentujeme jedničkami, zbytek matice jsou nuly.<br /> <br /> Vidíme, že neorientovaný graf produkuje symetrickou matici, je tedy možné horní polovinu zanedbat a ušetřit tak paměť. Věškeré operace jsou O(1) (pokud použijeme 2rozměrné pole), paměťově je však tato implementace náročnější, jelikož alokujeme paměť i pro místa, kde hrany nejsou. Tato metoda je tedy vhodná pro časté vyhledávání ve větších grafech.<br /> <br /> Ohodnocení lze provést uložením hodnoty místo jedniček, na diagonále lze ohodnotit vrcholy.<br /> <br /> <br /> // co třeba hledání kostry grafu a podobný vylomeniny?<br /> <br /> {{fav-kiv-bzinf}}<br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Strom,_pr%C5%AFchody_stromem,_bin%C3%A1rn%C3%AD_vyhled%C3%A1vac%C3%AD_stromy 2014-02-20T06:35:21Z

<p>Acolade: kategorizace</p> <hr /> <div>Strom je ADT - matematicky jde o typ grafu, který neobsahuje cykly.<br /> <br /> <br /> == Definice ==<br /> <br /> * '''Vrchol (uzel)''' - jeden prvek stromu. Má jednoho předchůdce a 0 - N následovníků.<br /> * '''Hrana (větev)''' - spojení dvou vrcholů<br /> * '''List''' - nrchol bez následovníků<br /> * '''Kořen''' - vrchol, který nemá žádné předchůdce. Z kořene je pak možné se dostat do jakéhokoliv uzlu stromu. Každý strom má jen jeden kořen.<br /> * '''Podstrom''' - // dopsat<br /> * '''Cesta stromem''' - cesta od libovolného vrcholu ke kořeni stromu. Tato cesta je ve stromu unikátní.<br /> * '''Hloubka vrcholu''' - délka cesty od kořene do daného vrcholu.<br /> * '''Výška stromu''' - nejdelší možná cesta ve stromu.<br /> <br /> <br /> // přidat obrázek s popisem částí stromu<br /> <br /> [[Soubor:Strom.jpg]]<br /> <br /> <br /> <br /> <br /> <br /> Implementace: <br /> Objektově - každá prvek má ukazatele Parent a např. pole ukazatelů Childern, výodné, jednoduché<br /> Polem - složité pro obecné stromy, je nutné ukládat indexy kořenů podstromů, počty podstromů těchto kořenů a data vrcholů jako taková. Speciálně lze implementovat stromy s konstatntním počtem podstromů v každém vrcholu (BVS, Octree, ...), kde je implementace jednodušší<br /> <br /> Adresářová struktura, sportovní výsledky, reprezentace stromů v přírodě :), ....<br /> <br /> <br /> == Průchod stromem ==<br /> <br /> '''Do šířky''' - Projdeme vrcholy po patrech, tedy kořen, postupně kořeny jeho podstromů, kořeny všech těchto podstromů atd. Jelikož ve stromech obecně neznáme sousedy, musíme se často vracet. Měřením cesty vrcholů však múžeme prohledávání do šířky převést na prohledávání do hloubky, i když ne zrovna elegantní (vyhledáme všechny vrcholy o hloubkách 0, pak 1, pak 2, ...)<br /> <br /> '''Do hloubky''' - Procházíme vrcholy do hloubky, tedy dojdeme-li do vrcholu, projdeme jeho podstromy a poté se teprve vracíme<br /> <br /> <br /> Procházení stromu může být průchod do hloubky dvojího druhu, podle priority operací:<br /> * '''Preorder''' - Nejprve vyzvedneme data vrcholu a poté projdeme postupně všechny podstromy<br /> preorder(node) {<br /> print node.value<br /> if node.left ≠ null then preorder(node.left) <br /> if node.right ≠ null then preorder(node.right)<br /> }<br /> <br /> * '''Postorder''' - Nejprve projdeme všechny podstromy, a poté vyzvedneme data vrcholu<br /> postorder(node) {<br /> if node.left ≠ null then postorder(node.left) <br /> if node.right ≠ null then postorder(node.right)<br /> print node.value<br /> }<br /> <br /> <br /> Procházení binárního stromu má navíc ještě jeden způsob:<br /> * '''Inorder''' - Projdeme levý podstrom, poté vyzvedneme data vrcholu, a poté pravý podstrom. Při výpisu BVS touto metodou dojdeme k seřazenému poli.<br /> <br /> == Binární vyhledávací strom (BVS) ==<br /> <br /> BVS je binární strom (strom, který má maximálně 2 podstromy v kažném vrholu) vytvořený tak, že kořen levého podstromu každého vrcholu má nižší hodnotu než tento vrchol a ten má nižší hodnotu než kořen pravého podstromu.<br /> <br /> Pri přidáváni vrcholu začínáme u kořene, a rozhodujeme se, kterou hranou jít dále, tedy je li vkládaný prvek menší , nebo větší než tento kořen. Takto postupujeme i vybraným podstromem až najdeme místo, kam vrchol umístit. Umístěný vrchol je vždy listem stromu.<br /> <br /> Mazání je složitější. Nejprve vrchol najdeme ve stromu a podle toho jaký je:<br /> * Pokud je listem, je to triviální<br /> * Pokud vrchol má pouze jeden podstrom, vrchol smažeme a na jeho místo umístíme kořen jeho (jediného) podstromu<br /> * Pokud má dva, vydáme se doprava a poté jdeme stále doleva dokud nenarazíme na list, který smažeme, ale jeho hodnotu přiřadíme původně mazanému vrcholu.<br /> <br /> Tento strom je nevyvážený, tedy může nastat situace, kdy bude jeden podstrom kořenu mít výrazně větší výšku než podstrom druhý.<br /> První vložený prvek bude vždy kořen stromu. Při načítání prvků do stromu je tedy vhodné alespoň pro tento prvek nalézt medián.<br /> <br /> Přidání prvku do pole a mazání je maximálně O(n) (pro strom, který byl vytvořen ze seřazené posloupnosti - je to tedy pouze lineární spojový seznam), očekávaná složitost operací je však O(log2 n) jelikož je strom v každém vrcholu rozdělen na 2 skupiny hodnot.<br /> <br /> {{fav-kiv-bzinf}}<br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Z%C3%A1sobn%C3%ADk,_fronta,_seznam 2014-02-20T06:35:14Z

<p>Acolade: kategorizace</p> <hr /> <div>Všechny tyto ADT implementují IsEmpty (prázdná struktura) a Size (pošet prvků ve struktuře)<br /> <br /> <br /> == Zásobník ==<br /> <br /> Interface: operace Push, Pop, Peek<br /> * '''Push''' vkládá data do zásobníku za sebe<br /> * '''Pop''' vybírá nejpozději vložená data<br /> * '''Peek''' vrátí nejpozději vložená data bez výběru prvku ze struktury<br /> = LIFO pamět (Last In First Out)<br /> <br /> Všechny operace jsou O(1)<br /> <br /> [[Soubor:Zasobnik.jpg]]<br /> <br /> Head: vrchol zásobníku<br /> <br /> <br /> Implementace objektově: <br /> * Prvky (objekty) obsahují data a ukazují na nižžší prvky v zásobníku (na prvky pod sebou)<br /> * '''Konstruktor:''' Vytvoříme ukazatel Head, který nastavíme na null<br /> * '''Modifikátor:''' Push vytvoří pro data nový prvek, který ukazuje na prvek Head (Head bude předchozí), a změní ukazatel Head na vytvořený prvek<br /> * '''Selektor:''' Peek vrátí data prvku Head, pokud Head != null. Pop vrátí stejná data jako Peek, ale před návratem změní ukazatel Head na předchozí prvek (Head = Head.Previous)<br /> <br /> <br /> Implementace na poli:<br /> * Máme pole typu stejného jako data<br /> * '''Konstruktor:''' Alokace pole a indexu Head, nastavení Head na -1<br /> * '''Modifikátor:''' Push zvýší index Head o 1 a zapíše data do pole na tento index. Pokud je index mimo pole, zvětšení pole (např. 2x), a po té zápis<br /> * '''Selektor:''' Peek vrátí prvek pole pod indexem Head, pokud Head &gt;= 0. Pop jako peek, ale před návratem provede Head--, pokud Head &gt;= 0.<br /> <br /> == Fronta ==<br /> <br /> Interface: operace Push, Pop, Front<br /> * '''Push''' vkládá data do fronty za sebe<br /> * '''Pop''' vybírá nejdříve vložená data<br /> * '''Peek''' vrátí nejdříve vložená data bez výběru prvku ze struktury<br /> = FIFO pamět (First In First Out)<br /> <br /> [[Soubor:Fronta.jpg]]<br /> <br /> First: začátek fronty; Last: konec fronty<br /> <br /> <br /> Implementace objektově: <br /> * Prvky obsahují data a ukazují na následující prvky fronty<br /> * '''Konstruktor:''' Vytvoříme pouze ukazatele First a Last, ukazující na null.<br /> * '''Modifikátor:''' Push vytvoří pro data nový prvek, upraví prvek Last (pokud != null) tak, aby ukazoval na tento prvek, a změní ukazatel Last na tento prvek. Je-li ukazatel First nastaven na null, nastaví tento také na vytvořený prvek.<br /> * '''Selektor:''' Front vrátí data prvku First, pokud First != null. Pop vrátí stejná data jako Front, ale před návratem změní ukazatel First na následující prvek, pokud First != null (First = First.Next)<br /> <br /> <br /> Implementace na poli (cyklicky):<br /> Máme pole typu stejného jako data a indexy First a Last. Indexy neukazují přímo do pole, nýbrž je proveden přepočet (Index mod Delka pole)<br /> abychom využili celé pole. Tato fronta má omezenou délku.<br /> * '''Konstruktor:''' Alokace pole a indexů, nastavení Last na -1 a First na -1<br /> * '''Modifikátor:''' Pokud ((Last + 1) mod Delka) != (First mod Delka), Push provede Last++ a zapíše data do pole na tento index, jinak chyba (plná fronta). Pokud First = -1, pak First = 0 (první prvek).<br /> * '''Selektor:''' Front vrátí prvek pole pod indexem First, pokud First &lt;= Last. Pop jako Front, ale před návratem provede First++.<br /> <br /> Speciálním případem je například prioritní fronta, která řadí prvky ve frontě podle priority<br /> <br /> == Seznam ==<br /> <br /> Interface - Iterator nad seznamem: Add, Remove, Get; First, Next, IsLast, případně další (Previous, Last, IndexOf, ...)<br /> <br /> [[Soubor:Seznam.jpg]]<br /> <br /> * '''Add''' vkládá data na pozici iterátoru. Složitost dle implementace.<br /> * '''Remove''' maže data na pozici iterátoru<br /> * '''Get''' vrátí data na pozici iteratoru<br /> * '''First''' vrátí iterátor na začátek seznamu<br /> * '''Next''' posune iterátor dále<br /> * '''IsLast''' indikuje koncová prvek<br /> * (Previous v obousměrných seznamech posune iterator na předchozí prvek)<br /> * (Last posune iterator na poslední prvek)<br /> * (IndexOf vyhledá prvek ve struktuře)<br /> = struktura, do které je možné libovolně zapisovat a číst (na libovolné pozici)<br /> <br /> Iterator: ukazatel do struktury<br /> <br /> Implementace objektově - nástřel: <br /> <br /> [[Soubor:Zasovnik-fronta-seznam-objektove.jpg]]<br /> <br /> Prvky ukazují na následující prvky seznamu. Iterátor je dobré implementovat tak, že ve skutečnosti ukazuje na předchozí prvek (Pokud tedy seznam není obousměrný, pak máme metodu Previous a je to jedno). Metoda add vloží prvek za prvek, na který ukazuje iterátor tak, že pouze upraví ukazatele prvků:<br /> <br /> Remove je opačný proces, Get vrátí data (Tedy Iterator.Next.Data), První prvek seznamu si uložíme, abychom se mohli rychle vracet, stejně jako poslední prvek. Next provede Iterator.Next = Iterator.Next.Next. Kontrolujeme, zda nejsme mimo seznam.<br /> <br /> * Obousměrný seznam: Prvky mají i ukazatele na předchozí prvky, a je tedy možné se po nich pohybovat na obě strany.<br /> * Kruhový seznam: Poslední prvek neukazuje na null, ale na první prvek. Tyto seznamy jsou použitelné ve speciálních případech (například nastavení segmentů sedmisegmentovky pro digitální hodiny)<br /> <br /> Implementace na poli (nástřel):<br /> Pole má nevýhodu, že je nutné přesunout prvky doprava od iterétoru, pokud vkládáme prvky. Při mazání lze prvky posunout doleva, nebo do pole uložit hodnotu, která se zcela jistě nebude v poli nebude vyskytovat, nebo vytvořit stínové pole, ve kterém si smazané prvky označíme, a při posunu iterátoru je poté vynecháme. Tento přístup je dobrý pokud pole často upravujeme.<br /> <br /> {{fav-kiv-bzinf}}<br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Abstraktn%C3%AD_datov%C3%A9_typy 2014-02-20T06:34:35Z

<p>Acolade: kategorizace</p> <hr /> <div>ADT je matematický model dat a operace nad těmito daty. Využívá základních datových typů pro konstrukci komplexnějších ADT, které využíváme pro snadnější organizaci dat a často pro optimalizaci algoritmů. <br /> <br /> <br /> == Abstraktní datový typ ==<br /> <br /> * je zcela oddělený blok, s klientským programem komunikuje pomocí rozhraní<br /> * je nezávislý na implementaci, na venek se projevuje jen veřejnými metodami<br /> * vše ostatní, kromě ovládacích metod, je uživateli skryto (samotná data a přístup k nim např.) (integrita)<br /> * je (klientsky) nezávislým blokem, může jej využívat kdokoliv, kdo zná rozhraní (pokud je ADT tedy třeba v DLL knihovně, můžeme jej používat i z jiných jazyků) (modularita)<br /> * je pevně a jasně definován<br /> <br /> <br /> ADT definuje a podporuje tyto operace<br /> * '''kostruktor''' - vytvoří istanci ADT<br /> * '''selektor''' - vyhledá žádaný prvek (indexer, At(), Pop()...)<br /> * '''modifikátor''' - upraví data ve struktuře (indexer, Push(), Add()...)<br /> <br /> Těmito operacemi jsou data jako taková uživateli skryta. Dynamická množina - množina dat, které předchozí operace podporuje, základ většiny ADT<br /> <br /> Příklady ADT:<br /> * Seznam<br /> * Fronta<br /> * Zásobník<br /> * Trie<br /> * Binární vyhledávací strom<br /> * Hashmapa<br /> * ...<br /> <br /> ADT je často využíváno návrhovými vzory. V některých jazycích lze ADT vytvořit jako generické, tedy vhodné pro uchování libovolného datového typu (např List&lt;int&gt;). Tyto generické ADT jsou také často v jazyce již implementovány jako knihovny (C# v Generics, C++ v Standard Template Library). U jazyků, které toto nepodporují lze využít Objekt, a ten přetypovávat, což není ideální, ale funguje. U jazyků nemajících objekt je to horší, musíme přijít s vlastní specifickou implementací.<br /> <br /> {{fav-kiv-bzinf}}<br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Rekurze 2014-02-20T06:34:29Z

<p>Acolade: kategorizace</p> <hr /> <div>Rekurzí rozumíme sebevolání, tedy kód, který volá sám sebe či svojí část (přímá rekurze), případně volá kód, který posléze volá kód volající (nepřímá rekurze).<br /> <br /> Rekurze je vhodná pro řešení rekurzivních problémů (například výpočet faktoriálu nebo Fibonacciho posloupnosti, fraktály), je však paměťově velmi náročný (každé rekurzivní volání vyžaduje vlastní paměťový prostor), doporučuje se tedy pouze pro vhodné problémy (rekurzivní výpis řetězce na obrazovku je nesmysl).<br /> <br /> Rekurze musí mít následující podmínky: <br /> * musí být konečná, tedy musí existovat vstup, pro který rekurzivní funkce nevolá sama sebe, tedy musí být testována tato konečnost před voláním sebe sama<br /> * problém se musí rekurzí zjednodušovat, aby rekurze ke koncové podmínce dospěla (případně můžeme definovat maximální počet vnoření jako pojistku)<br /> <br /> <br /> == Typy rekurze ==<br /> <br /> * '''Přímá''' - metoda volá sama sebe<br /> * '''Nepřímá''' - metoda volá metodu, která volá zpětně ji<br /> <br /> <br /> * '''Lineární''' - metoda volá pouze jednu svoji kopii (faktorial)<br /> * '''Stromová''' - metoda volá více svých kopií (Fibonacci, průchod adresářovou strukturou, často Divide &amp; Conquer algoritmy)<br /> <br /> Rekurze však často umožňuje zjednodušení kódu a ušetření času při programování. Často lze rekurzivní problémy řešit také čistě iteračním algoritmem, nebo použitím zásobníku.<br /> <br /> Příklad: Procházení adresářové struktury.<br /> Vytvoříme metodu ProjdiAdresář(string cesta);<br /> <br /> Iteračně (nesmysl?):<br /> <br /> # Vytvoříme ukazatel na položku adresářové struktury ukazující &quot;před?&quot; výchozí adresář a uložíme tuto hodnotu do vedlejší proměnné<br /> # Posuneme ukazatel na další položku adresáře<br /> # Je-li pod ukazatelem označená položka, nebo prázdno, vrátíme se na předchozí položku a zpět na 2, nebo ukončíme, pokud jsme na uložené položce &quot;před?&quot;<br /> # Je-li pod ukazatelem adresář, označíme jej jako zpracovaný (i když je otázka jak) a posuneme ukazatel na jeho první položku<br /> # Je-li pod ukazatelem soubor, [otevře, vypíše název, zpracuje, přidá do vlastní datové struktury,...], a označíme soubor jako zpracovaný <br /> # Zpět na bod 2<br /> <br /> Zásobníkem: <br /> <br /> # Načte obsah adresáře 'cesta' do zásobníku<br /> # Prochází položky zásobníku:<br /> ## Je - li položka soubor, [otevře, vypíše název, zpracuje, přidá do vlastní datové struktury,...]<br /> ## Je - li položka adresář, načte jeho obsah do zásobníku<br /> # Opakuje body 2 a 3 dokud není zásobník prázdný<br /> <br /> Rekurzivně:<br /> <br /> # Načíst obsah adresáře 'cesta' a prochází jednotlivé položky<br /> # Narazí - li na soubor, [otevře, vypíše název, zpracuje, přidá do vlastní datové struktury,...]<br /> # Narazí - li na adresář, volá sama sebe na jeho cestu<br /> <br /> Vidíme, že pro rekurzi neimplementujeme vlastní zásobník (viz však níže), a kód je přehlednější (Rekurze cca 5 řádek, iteračně mnohem více)<br /> <br /> Pár slov k implementaci rekurze:<br /> V imperativním programování je většinou rekurze vnitřně řešena jak jinak než na zásobníku, jelikož je stav volající funkce uložen na vnitřní zásobník. Technicky vzato je tedy rekurze nahrazena zásobníkovým způsobem. Pri chybě rekurze (nesplnění koncové podmínky) většina jazyků vyhodí Stack Overflow (přetečení zásobníku) případně Access violation (Chyba přístupu do chráněné paměti), záleží na způsobu vnitřní implementace zásobníku.<br /> <br /> // http://www.abclinuxu.cz/clanky/ruzne/komiks-xkcd-244-stolni-rpg pro ty, to ví co je Dungeons &amp; Dragons<br /> <br /> == Příklady ==<br /> <br /> Výpočet faktoriálu: <br /> <br /> int faktorial(int f) {<br /> if (f &lt;= 1) <br /> return 1;<br /> else <br /> return f * faktorial(f - 1);<br /> }<br /> <br /> Fibonacciho posloupnost:<br /> <br /> int fibonacci(int n) {<br /> if (n &lt;= 2)<br /> return 1;<br /> else<br /> return fibonacci(n - 1) + fibonacci(n - 2);<br /> }<br /> <br /> {{fav-kiv-bzinf}}<br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Anal%C3%BDza_program%C5%AF 2014-02-20T06:34:21Z

<p>Acolade: kategorizace</p> <hr /> <div>Analýza programu se zabývá nároky programu na zdroje, tedy čas, paměť, šířka pásma... Máme-li problém, lze pro jeho řešení zpravidla použít více algoritmů, a každý algoritmus může mít několik implementací. Analýza programů se zabývá právě vztahem implementace řešení původního problému vzhledem k požadovanému zdroji.<br /> <br /> <br /> == Časová náročnost ==<br /> <br /> Nejčastěji nás zajímá časová náročnost programu. Analyzujeme, jakou dobu bude implementovanému algoritmu trvat výpočet. Tuto dobu ovlivňuje způsob implementace (počet nutně provedených operací) a velikost vstupních dat (počet prvků, které algoritmus zpracovává, případně jejich uspořádání). Definujeme elementární čas pro všechny operace c&lt;sub&gt;operace&lt;/sub&gt; a jejich skádáním počítáme celkový čas potřebný pro provedení algoritmu. <br /> <br /> Příklad: Naplnění již alokovaného pole náhodnými čísly (c#)<br /> <br /> for (int i = 0, i &lt; pole.Length; i++)<br /> {<br /> pole[i] = rand.Next();<br /> }<br /> <br /> * máme pole délky n = pole.Length:<br /> * alokace proměnné trvá c&lt;sub&gt;aloc&lt;/sub&gt;<br /> * operace přiřazení trvá c&lt;sub&gt;přiřazení&lt;/sub&gt;<br /> * operace porovnání trvá c&lt;sub&gt;porovnání&lt;/sub&gt;<br /> * operaci inkrementace lze definovat jako c&lt;sub&gt;inkrement&lt;/sub&gt; = c&lt;sub&gt;přiřazení&lt;/sub&gt; + c&lt;sub&gt;součet&lt;/sub&gt;<br /> * řekněme, že generování náhodného čísla trvá konstantní čas c&lt;sub&gt;rand&lt;/sub&gt;<br /> <br /> <br /> <br /> * Inicializace cyklu for: alokace + přiřazení = c&lt;sub&gt;aloc&lt;/sub&gt; + c&lt;sub&gt;přiřazení&lt;/sub&gt;<br /> * Běh cyklu: porovnání (i &lt; length) + přiřazení (do pole) + náh. číslo + inkrementace (i++) = c&lt;sub&gt;porovnání&lt;/sub&gt; + c&lt;sub&gt;přiřazení&lt;/sub&gt; + c&lt;sub&gt;rand&lt;/sub&gt; + c&lt;sub&gt;inkrement&lt;/sub&gt;<br /> * Cyklus for proběkne n-krát, tedy: n * ( c&lt;sub&gt;porovnání&lt;/sub&gt; + c&lt;sub&gt;přiřazení&lt;/sub&gt; + c&lt;sub&gt;rand&lt;/sub&gt; + c&lt;sub&gt;inkrement&lt;/sub&gt; )<br /> * Celkem: c&lt;sub&gt;aloc&lt;/sub&gt; + c&lt;sub&gt;přiřazení&lt;/sub&gt; + n * ( c&lt;sub&gt;porovnání&lt;/sub&gt; + c&lt;sub&gt;přiřazení&lt;/sub&gt; + c&lt;sub&gt;rand&lt;/sub&gt; + c&lt;sub&gt;inkrement&lt;/sub&gt; )<br /> <br /> == Asymptotická složitost ==<br /> <br /> Ve většině případů neznáme čas potřebný pro konstantní operace, ale víme, že je velmi malý. Dobu výpočtu předchozího příkladu můžeme tedy přepsat na '''a''' + '''n''' * '''b''', kde '''a''' a '''b''' jsou doby, které mají určitou délku, která nás však přísliš nezajímá.<br /> <br /> Více než doba výpočtu nás tedy zajímá počet operací, které je třeba vykonat (stejně budou operace na každém systému vykonávány jinou dobu (PC vs. mobilní telefon např.)). Složitostí programu myslíme právě počet operací potřebný pro výpočet vzhledem k počtu prvků na vstupu algoritmu, omezený shora a/nebo zdola. Tato složitost se pro libovolný počet prvků asymptoticky blíží k určité funkci. Nás zajímá, ke které.<br /> Rozlišujeme také složitost algoritmu a složitost problému (ta by měla patřit do otázky PPA1).<br /> <br /> <br /> '''Theta notace''' Θ(f(x)) vyjadřuje A.S., omezenou složitostní funkcí c&lt;sub&gt;1,2&lt;/sub&gt; * f(x) shora, resp zdola. Hledáme tedy 2 konstatnty, pro které je analyzovaná složitost omezena.<br /> <br /> Tato notace říká, že algoritmus nebude asymptoticky složitější než c&lt;sub&gt;1&lt;/sub&gt; * f(x), a nebude rychlejší než c&lt;sub&gt;2&lt;/sub&gt; * f(x).<br /> To znamená, že problém lze řešit algoritmem, který nebude asymptoticky složitější než c&lt;sub&gt;1&lt;/sub&gt; * f(x), ale zároveň nikdy nebude lepší než c&lt;sub&gt;2&lt;/sub&gt; * f(x).<br /> <br /> '''Omikron notace''' O(f(x)) vyjadřuje A.S. omezenou funkcí c * f(x) pouze shora. Jinými slovy, jde o maximální možnou složitost algoritmu. Jde o první podmínku theta notace. <br /> <br /> '''Omega notace''' Ω(f(x)) vyjadřuje A.S. omezenou funkcí c * f(x) pouze zdola. Říká, že algoritmus pro alespoň jeden vstup bude této složitosti. Druhá podmínka theta notace.<br /> <br /> Pokud platí omikron a omega notace pro stejnou f(x), mluvíme o theta notaci.<br /> <br /> Konstanty v notaci zanedbáváme, jelikož vzhledem k většímu n nehrají roli. Sčítáním složitostí tedy nedochází k jejich zhoršení, jsou-li stejného řádu (např n&lt;sup&gt;2&lt;/sup&gt; + n&lt;sup&gt;2&lt;/sup&gt; = 2n&lt;sup&gt;2&lt;/sup&gt; =&gt; n&lt;sup&gt;2&lt;/sup&gt;, 200 operací je asymptoticky stejné jako 100, ale n&lt;sup&gt;2&lt;/sup&gt; + n&lt;sup&gt;3&lt;/sup&gt; =&gt; n&lt;sup&gt;3&lt;/sup&gt; , 100 * 100 operací je vzhledem k 100 * 100 * 100 zanedbatelné).<br /> <br /> Předchozí příklad je tedy složitosti Θ(n) , jelikož je vždy lineární vzhledem k délce pole (netrvá kratší, ani delsí dobu/počet operací)<br /> <br /> == Očekávaná složitost ==<br /> <br /> Většina algoritmů je asymptoticky omezena pro extrémní případny na vstupu (např. Quicksort je Ω(n) (pole již seřazeno) a O(n2) (pole je seřazeno opačně)). Chování algoritmu má však očekávanou složitost, která nastává pro většinu případů (jak víme O(n logn) pro QuickSort). Využívá se také Theta/Omikron/Omega notací.<br /> <br /> Je-li algoritmus závislý na vstupních datech (resp. na jejich uspořádání), a potřebujeme, aby složitost byla pokud možno vždy očekávaná, lze využít náhodného přeuspořádání dat na vstupu (za předpokladu, že je to možné - např. pro řazení ano, pro výpis znaků na obrazovku evidentně ne). Toto přeuspořádání může být konstatní složitosti (např 100x přeházíme vzájemně prvky pole s náhodnými indexy pokud je pole rozumné odpovídající délky), případně lineární, složitost algoritmu tedy neovlivňuje (za předpokladu, že algoritmus samotný není očekávané sublineární časové složitosti).<br /> <br /> <br /> <br /> == Klasifikace složitosí ==<br /> <br /> '''Polynomiální''' - složitost O(n * c) kde c je konstanta. Polynomiální algoritmy jsou použitelné. Ideální jsou algoritmy rychlejší (lineární, logaritmické,...), ne vždy je však možné takový algoritmus vymyslet.<br /> <br /> '''Exponenciální''' - složitost O(c&lt;sup&gt;n&lt;/sup&gt;). Tyto algoritmy nejsou příliš dobré, a je vhodné se zamyslet a pokusit se vymyslet jiný, polynomiálně složitý algoritmus. Zpravidla algoritmy hrubé síly jsou této složitosti, jelikož procházejí všechny kombinace vstupu a hledají řešení. Pro malé n jsou však použitelné díky menší režii a přípravě, paměťovým nárokům atd.<br /> <br /> <br /> Postupy výše lze aplikovat i na složitosti paměťové, šířky pásma, ...<br /> <br /> {{fav-kiv-bzinf}}<br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Spr%C3%A1vnost_program%C5%AF 2014-02-20T06:34:08Z

<p>Acolade: kategorizace</p> <hr /> <div>Testováním programu, tj. ověřením, že pro daný vstup získáme správný výsledek, nemůžeme obecně prokázat správnost programu. Množství vstupů je většinou tak veliké, že testování není možné ani za použití velice rychlých počítačů. Na druhé straně testování může alespoň prokázat chybu v programu. Protože empirickým testováním nemůžeme zaručit správnost programu, musíme ho nahradit analytickým přístupem pro porozumění správnosti programu. Sekvence příkazů (přiřazení, alternativy a cyklu) umožňuje dokázání správnosti programu tak, že můžeme napsat tvrzení o hodnotách proměnných před vykonáním příkazu, které nazýváme předpoklad a tvrzení po jeho vykonání, které nazýváme důsledek.<br /> <br /> <br /> == Příkazy sekvenčně ==<br /> <br /> Například pokud máme dva příkazy sekvenčně za sebou, tak vyjdeme z požadovaného<br /> důsledku druhého příkazu. Na základě důsledku stanovíme požadovaný předpoklad pro druhý<br /> příkaz, což je také požadovaný důsledek pro první příkaz atd. až získáme hodnoty možných<br /> vstupů.<br /> <br /> <br /> == Příkazy alternativy ==<br /> <br /> Příkazy alternativy zachovávají sekvenční vykonávání příkazu.<br /> <br /> <br /> == Příkazy cyklu ==<br /> <br /> Pro pochopení příkazů opakování zavedeme pojem invariant cyklu.<br /> Pro invariant cyklu musíme obecně ukázat tři vlastnosti:<br /> * '''Inicializace''' - je splněn před vykonáním prvního cyklu.<br /> * '''Udržování''' - je-li splněn pře vykonáním cyklu, zůstává splněn i po něm.<br /> * '''Skončení''' - když příkaz cyklu skončí, invariant nám ukáže správnost algoritmu (dokážeme-li, že inicializace platí, a cyklus je udržován pro všechny iterace).<br /> <br /> Přiklad na řazeni pole vkládáním:<br /> * '''Inicializace''': Po začátečním přiřazení i = 1 je pole s prvky s indexy 0, ..., i-1 osahující jeden prvek triviálně seřazeno.<br /> * '''Udržování''': Cyklus while posouvá již seřazené prvky a[i-1], a[i-2], ... o jednu pozici doprava dokud se nenajde správné místo pro a[i]. Výsledkem je, že prvky pole a[0] ... a[i] jsou seřazeny. Invariant je tedy splněn i pro následující opakování, kdy i je v hlavičce cyklu inkrementováno.<br /> * '''Skončení''': Cyklus for skončí když i=n, kde n je počet prvků pole. Dosazením do textu invariantu cyklu dostáváme, že prvky s indexy 0 ... n-1 obsahují seřazené původní prvky pole, co je to co jsme požadovali.<br /> <br /> <br /> {{fav-kiv-bzinf}}<br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Spojov%C3%A9_datov%C3%A9_struktury 2014-02-20T06:33:58Z

<p>Acolade: kategorizace</p> <hr /> <div>Pokud potřebujeme ukládat data do paměti a nevíme předem, kolik jich bude (kolik prvků bude nutné uložit), nebo mění-li se v runtimu jejich počet, používáme spojové datové struktury. Každý prvek - záznam - struktury je reprezentován např. jako objekt, který ukazuje na svého následovníka (ukazatel, pointer), případně na další objekty (předchozí, začátek...). Ukazatel je vlastně adresa objektu, takže pomocí něho můžeme k jiným objektům přistupovat. <br /> <br /> Vyhledávání prvků struktury je většinou iterační, posunujeme se z jednoho objektu na druhou (na rozdíl od pole, kde přistupujeme přímo, indexem). Díky tomu je vyhledávání ve spojových datových strukturách pomalejší než v polích (kde je O(1)), ale zato není potřeba předem alokovat velké množství paměti, kterou si spojová datová struktura bere až za běhu programu (na rozdíl od statickéého pole, kde se alokuje při spuštění).<br /> <br /> Jednotlivé záznamy mohou obsahovat metody pro operace se strukturou (zápis, vložení, čtení, posun po prvcích) a, pokud vyžadujeme dědičnost, je možné implementovat spojové struktuře rozhraní, které potřebné operace implementuje.<br /> <br /> Příkladem jsou:<br /> * fronty<br /> * zásobníky<br /> * seznamy (jednosměrné, obousměrné)<br /> * stromy<br /> * skip-list<br /> * ...<br /> <br /> {{fav-kiv-bzinf}}<br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Objekt,_t%C5%99%C3%ADda 2014-02-20T06:33:31Z

<p>Acolade: kategorizace</p> <hr /> <div>== Třída ==<br /> <br /> '''Třída:''' Elementární stavební prvek objektově orientovaného programování. Obsahuje předpis, podle kterého lze vytvořit instanci třídy - objekt. Obsahuje členské atributy a metody. <br /> <br /> '''Zapouzdření:''' Třída zapouzduje atributy a funkce jako &quot;její&quot;. Na venek komunikuje pomocí rozhraní, nebo odhaluje některé atributy či metody pomocí přístupových práv, většinou<br /> * Public - veřejné, k třídě či jejím public atributům a metodám lze přistupovat odkudkoliv<br /> * Protected - třídě či jejím protected atributům a metodám lze přistupovat pouze z ní (this v případě objektu, statický přístup) nebo z odděděných tříd<br /> * Private - třídě či jejím private atributům a metodám lze přistupovat pouze z ní<br /> <br /> Některé jazyky podporují i další práva, např Internal v jazyce C#, který dovoluje přistupovat k třídě z její assembly (aplikace, ddl knihovna,...)<br /> <br /> '''Typy tříd:'''<br /> * &quot;Klasická&quot; třída - dovoluje instancování na objekty, každá instance dostane přidělenu vlastní paměť<br /> * Statická třída a členové - klíčové slovo static - Třída, která není instancovatelná, a její metody jsou přístupné pouze statickým způsobem, tedy Třída.Metoda() (nikoliv instanceTřídy.Metoda()). Klasická třída může obsahovat statické členy, které jsou pro včechny případné instance společné (například static parametr počet instancí, který se v konstruktoru zvýší). V jazycích, které statické třídy nepodporují se používá návrhový vzor singleton.<br /> * Abstraktní třída - abstract - obsahuje abstraktní metody, není instancovatelná. Je nutné od ní oddědit a abstraktní metody doimplementovat (např abstraktní třída Čtečka s metodou Čti(), od které dědí FlashČtečka, DiskČtečka, CDROMČtečka....(To není zrovna dobrý příklad, jelikož čtení provádí OS, ale jako idea je to OK))<br /> * Koncová třída (final v Javě, sealed v C#, v C++ není) - třída, kterou nelze dědit<br /> <br /> <br /> == Objekt ==<br /> <br /> '''Objekt:''' Instance třídy, obraz třídy v paměti, referenční datový typ. Přebírá atributy a metody své třídy. Je nutné jej vytvořit pomocí operátoru new, případně uvolnit pomocí většinou delete (pokud není garbage collector). <br /> <br /> '''Třída vs Struktura:''' Třída a struktura (struct, record,...) mohou mít společné vlastnosti. Rozdíly se projevují podle jazyka, většinou je však platný ten rozdíl, že členské prvky struktury jsou public zatímco členské prvky třídy jsou private. V C# je další rozdíl v uložení (třída v paměti, struktura na zásobníku). Java struktury nemá, používá se final class<br /> <br /> '''Konstruktor a destruktor:''' Metoda, která inicializuje, respektive uvolňuje třídu do/z paměti. Většinou nastavuje atributy třídy na výchozí hodnoty.<br /> <br /> '''Gettery a Settery:''' Veřejné metody, které nastavují privátní atributy objektu či třídy. Používáme je, abychom zamezili entitám využívající atributy třídy nastavit tyto atributy na nesmyslné hodnoty.<br /> <br /> {{fav-kiv-bzinf}}<br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Vykon%C3%A1n%C3%AD_programu 2014-02-20T06:32:44Z

<p>Acolade: kategorizace</p> <hr /> <div>Vykonávání programu je hlavní činnost počítače. Hlavními částmi, které se podílí na výpočtu, jsou procesor a hlavní paměť.<br /> V hlavní paměti je uložen program ve strojovém kódu jako posloupnost instrukcí a dat (von Neumannova koncepce ). V procesoru (CPU) se vykonávají instrukce, sekvenčně, pokud není pořadí změněno instrukcemi skoku. Programy lze tedy větvit na základě podmínek a pořadí vykonávání instrukcí je závislé na jejich splnění.<br /> <br /> Drtivá většina programů napsána ve vyšších jazycích, je proto nutné je upravit tak, aby jim počítač rozuměl, tedy jednotlivé příkazy převést na instrukce procesoru. K tomu existují 2 postupy:<br /> <br /> '''Kompilace:'''<br /> Program je přeložen najednou do strojové podoby, která je platformově závislá. Operační systém tento program nahraje do operační paměti a spustí. O překlad se stará překladač nebo kompilátor, který přeloží příkazy vstupního souboru na instrukce. Jelikož je v konvenčních pratformách použito jednoho adresního prostoru pro jednu aplikaci, některé prog. jazyky také vyžadují také linker, který převádí adresy jednotlivých funkcí a instrukcí (obsažených v jednotlivých modulech programu) z abstraktní podoby na konečnou absolutní. Kompilovaný program je platformově závislý a vyžaduje specifický překladač pro danou platformu, jeho běh je však nativní a zpravidla rychlý, a je možno využít knihoven dané platformy (například API uživatelského rozhraní WinForms). Příkladem je C, C++, Pascal<br /> <br /> '''Interpretace:'''<br /> Program je interpretován přímo ze zdrojového kódu, příkazy jsou z kódu přečteny, interpretovány (&quot;tlumočeny&quot;) a okamžitě provedeny. Lze interpretofat příkazy jednotlivě, nebo interpretovat celý kód najednou při spuštění. Tento přístup vyžaduje interpreter, který je shopen pro danou platformu příkazy tlumočit. Příklady: PHP, BASIC, Perl, Python<br /> <br /> '''Hybridní vykonávání:'''<br /> Některé jazyky využívají kombinace předchozího přístupu, tedy kompilaci zdrojového kódu do univerzálního platormově nezávislého jazyka, který je poté interpretován. Příkladem je Java (překlad do byte-code (class) souborů, které jsou spouštěny na virtuálním stroji) nebo C# (překlad do nezávislého Common Intermediate Language, který je poté přeložen do nativní podoby a spuštěn, je li potřeba (JITerem))<br /> <br /> {{fav-kiv-bzinf}}<br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade https://www.512.cz/index.php?title=Probl%C3%A9m,_algoritmus,_program 2014-02-20T06:32:21Z

<p>Acolade: kategorizace</p> <hr /> <div>== Problém ==<br /> <br /> '''Problém:''' Otázka či stav, pro jejíž zodpovězení hledáme řešení, případně existenci řešení. Takovýto stav je nežádoucí a je tedy na nás jej změnit (problém vyřešit)<br /> <br /> '''Postup:''' Zjistíme, že problém nastal (nelze situaci zvládnout známými postupy), zadefinujeme problém (vstupy a výstupy), nalezneme způsob žešení, zjistíme, zda je způsob řešení efektivní a případně optimalizujeme způsob žešení. <br /> <br /> <br /> Rozhodovací problémy lze dělit do tříd složitosti<br /> * P (polynomiální) - problém je řešitelný pomocí (deterministického) [http://cs.wikipedia.org/wiki/Turing%C5%AFv_stroj Turingova stroje] v polynomiálním čase (např problém řazení), lze dokázat, že všechny problémy P jsou podmnožinou problémů skupiny NP (NP problém s jednou větví, NP problém bez hádání či nápovědy)<br /> * NP (nedeterministicky polynomiální) - Polynomiální čas, ale nedeterministický Turingův stroj (takový, který může rozvětvit program v libovolném kroku na více větví, ve kterých hledá řešení současně (zcela paralelně), případně lze mluvit o stroji, který &quot;uhodne&quot; kterou větví se vydat, případně mu něco &quot;napoví&quot; kudy se má vydat, aby řešení bylo správné. Také lze mluvit o problémech, jejichž řešení lze ověřit v polynomiálním čase (zpětný postup, zjištění, zda je nalezené řešení opdpovídající problému), níkoliv jej získat - pokud bychom všechny větve umístili řekněme do zásobníku (zásobníkový Touringův stroj), čas pro nalezení řešení by nutně nebyl polynomiální. Je otázkou, zda lze pro NP problémy najít P řešení.<br /> * NP-těžké - Problémy, na které lze v polynomiálním čase převést všechny problémy NP, nemusí však nutně v NP samy o sobě být (nemusí být ani rozhodovací)<br /> * NP-úplné - NP-těžké problémy, které jsou ve třídě NP, jde tedy o nejtěžší NP úlohy<br /> <br /> <br /> [[Soubor:Problemy.gif]]<br /> <br /> <br /> Vztah mezi P a NP je jedním ze sedmi problémů tisíciletí, které vypsal Clayův matematický ústav 24. května 2000, za rozhodnutí vztahu nabízí 1 000 000 dolarů.<br /> <br /> Pro zasmání: http://www.abclinuxu.cz/clanky/komiks-xkcd-287-np-uplnost<br /> <br /> <br /> == Algoritmus ==<br /> <br /> '''Algoritmus:''' Obecný postup pro nalezení řešení, ověřený že funguje. Jde o konečnou sekvenci známých operací (některé definice říkají, že tyto operace musí být elementýrní) které vedou k vyřešení problému.<br /> <br /> * Každý bod algoritmu musí být jednoznačně určen a musí být proveditelný (pochopitelný strojem)<br /> * Algoritmus musí mít konečný počet kroků, tedy musí skončit po konečném počtu operací (narozdíl od výpočetní metody)<br /> * Algoritmus má 0 - N vstupů<br /> * Algoritmus má 1 - N výstupů<br /> <br /> <br /> <br /> == Program ==<br /> <br /> <br /> '''Výpočetní metoda:''' &quot;Algoritmus&quot;, který není konečný (event-driven systémy jako třeba automat na kávu, snímače JIS karet, digitální hodinky...)<br /> <br /> '''Program:''' Výpočetní metoda (interaktivní aplikace) či algoritmus (dávkové aplikace) zapsaný v souladu s pravidly programovacího jazyka tak, aby bylo možné algoritmus přenést a použít na počítači či jiném stroji. Programovací jazyk je nástroj programátora pro snazší programování, převede se na strojový jazyk, kterému počítač rozumí. Součástí programu může být i popis použitých datových struktur, se kterými algoritmus či výpočetní metoda pracuje.<br /> <br /> {{fav-kiv-bzinf}}<br /> [[Kategorie:fav-kiv-bzinf]]</div>

Acolade