FAV wiki - Příspěvky uživatele [cs]

Dolní omezení pro porovnávací řazení

2017-06-07T10:29:18Z

Tomiksed:

Zkoumejme dolni omezeni počtu porovnani T(n) pro porovnávaci algoritmy řazení.

[[Soubor:Dolni-omezeni.jpg]]

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.

Přiklad rozhodovaciho stromu pro řazeni vkladanim tři prvků:
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.

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 .

Nyní musíme najít dolní omezení všech rozhodovacích stromů. Nechť rozhodovaci strom o výšce h má l listů, potom l = 2^h (binární strom má maximálně 2^h listů). Současně listů musi byt alespoň tolik, kolik je permutaci, tedy n! <= l.
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)

log2 (n!) <= log_2(2^h) | h*log_2(2) -> h * 1 = h = počet porovnání, kterým se dostneme k permutaci

Použitim levé části aproximace e*(n/e)^2 <= n! <= e*((n+1)/e)^(n+1) se dostáváme na:

log_2(n!) ~ n * log_2 (e*(n/e)) = n*(log_2(e) + log_2(n) - log_2(e))

čim dostavame dolni omezeni pro nejhorši připad Ω(n*log_2(n)).

Protože pro řazeni haldou a slučovanim jsou shora omezeny časem vypočtu Ω(n*log2 n), jsou tato řazeni asymptoticky optimalni.

[[Kategorie:fav-kiv-bzinf]]

Dolní omezení pro porovnávací řazení

2017-06-07T10:29:01Z

Tomiksed:

Zkoumejme dolni omezeni počtu porovnani T(n) pro porovnávaci algoritmy řazení.

[[Soubor:Dolni-omezeni.jpg]]

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.

Přiklad rozhodovaciho stromu pro řazeni vkladanim tři prvků:
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.

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 .

Nyní musíme najít dolní omezení všech rozhodovacích stromů. Nechť rozhodovaci strom o výšce h má l listů, potom l = 2^h (binární strom má maximálně 2^h listů). Současně listů musi byt alespoň tolik, kolik je permutaci, tedy n! <= l.
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)

log2 (n!) <= log_2(2^h) | h*log_2(2) -> h * 1 = h = počet porovnání, kterým se dostneme k permutaci

Použitim levé části aproximace e*(n/e)^2 <= n! <= e*((n+1)/e)^(n+1) se dostáváme na:

log_2(n!) ~ n * log_2 (e*(n/e)) = n*(log_2(e) + log_2(n) - log_2(e))

čim dostavame dolni omezeni pro nejhorši připad Ω(n*log2 n).

Protože pro řazeni haldou a slučovanim jsou shora omezeny časem vypočtu Ω(n*log2 n), jsou tato řazeni asymptoticky optimalni.

[[Kategorie:fav-kiv-bzinf]]

Dolní omezení pro porovnávací řazení

2017-06-07T10:28:32Z

Tomiksed:

Zkoumejme dolni omezeni počtu porovnani T(n) pro porovnávaci algoritmy řazení.

[[Soubor:Dolni-omezeni.jpg]]

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.

Přiklad rozhodovaciho stromu pro řazeni vkladanim tři prvků:
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.

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 .

Nyní musíme najít dolní omezení všech rozhodovacích stromů. Nechť rozhodovaci strom o výšce h má l listů, potom l = 2^h (binární strom má maximálně 2^h listů). Současně listů musi byt alespoň tolik, kolik je permutaci, tedy n! <= l.
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)

log2 (n!) <= log_2(2^h) | h*log_2(2) -> h * 1 = h = počet porovnání, kterým se dostneme k permutaci

Použitim levé části aproximace e*(n/e)^2 <= n! <= e*((n+1)/e)^(n+1) se dostáváme na:

log_2(n!) = n * log_2 (e*(n/e)) = n*(log_2(e) + log_2(n) - log_2(e))

čim dostavame dolni omezeni pro nejhorši připad Ω(n*log2 n).

Protože pro řazeni haldou a slučovanim jsou shora omezeny časem vypočtu Ω(n*log2 n), jsou tato řazeni asymptoticky optimalni.

[[Kategorie:fav-kiv-bzinf]]

Dolní omezení pro porovnávací řazení

2017-06-07T10:28:09Z

Tomiksed:

Zkoumejme dolni omezeni počtu porovnani T(n) pro porovnávaci algoritmy řazení.

[[Soubor:Dolni-omezeni.jpg]]

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.

Přiklad rozhodovaciho stromu pro řazeni vkladanim tři prvků:
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.

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 .

Nyní musíme najít dolní omezení všech rozhodovacích stromů. Nechť rozhodovaci strom o výšce h má l listů, potom l = 2^h (binární strom má maximálně 2^h listů). Současně listů musi byt alespoň tolik, kolik je permutaci, tedy n! <= l.
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)

log2 (n!) <= log_2(2^h) | h*log_2(2) -> h * 1 = h = počet porovnání, kterým se dostneme k permutaci

Použitim levé části aproximace e*(n/e)^2 <= n! <= e*((n+1)/e)^(n+1) se dostáváme na:

log_2(n!) = n * log_2 (e*(n/e)) = n*(log_2(e) + log_2(n) - log_2(e))

čim dostavame dolni omezeni pro nejhorši připad Ω(n*log2 n).

Protože pro řazeni haldou a slučovanim jsou shora omezeny časem vypočtu Ω(n*log2 n), jsou tato řazeni asymptoticky optimalni.

'''JE TO ŠPATNĚ !!!!!!!!!!!!!!! V TEXTU NEJSOU VIDĚT INDEX h^2 viz.: [http://www.kiv.zcu.cz/~netrvalo/vyuka/ppa2-11/ekniha/online/HTML/54/default.htm]'''

[[Kategorie:fav-kiv-bzinf]]

KIV/BZINF - Státnice pro informatiky

2017-06-07T08:46:37Z

Tomiksed:

Okruhy pro státní závěrečnou zkoušku. Zpravidla ale neplatí, že jeden okruh je jedna otázka. Někdy třeba spojí více okruhů do jednoho, jindy se zase zeptají jen na jednu jeho část.

Důležitá poznámka: '''používejte mozek'''! Wiki je plná kravin, přemýšlejte nad tím, co čtete, protože říct u státnic naprostou volovinu je to nejhorší, co se vám může stát. I odpověď "nevím" je lepší...

== PPA2 ==

# [[Problém, algoritmus, program]]
# [[Vykonání programu]]
# [[Objekt, třída]]
# [[Spojové datové struktury]]
# [[Správnost programů]]
# [[Analýza programů]]
# [http://www.512.cz/index.php?title=Analýza_programů#Asymptotick.C3.A1_slo.C5.BEitost Asymptotická složitost]
# [[Rekurze]]
# [[Abstraktní datové typy]]
# [[Zásobník, fronta, seznam]]
# [[Strom, průchody stromem, binární vyhledávací stromy]]
# [[Grafy a jejich implementace]]
# [[Prohledávání grafů]]
# [[Topologické řazení]]
# [[Tabulka s přímým adresováním]]
# [[Rozptylové tabulky s vnějším řetězením]]
# [[Prioritní fronta]]
# [[Halda]]
# [[Algoritmy řazení O(N logN)]]
# [[Dolní omezení pro porovnávací řazení]]
# [[Generičnost]]
# [[Dědičnost]]
# [[Rozhraní]]
# [[Algoritmická řešitelnost problémů]]
# [[Klasifikace problémů]]

== PT ==

# [[Úvod do technologie programování a programovacích stylů, objektově orientovaný návrh, základní UML diagramy, psaní programů v Javě]]
# [[Abstraktní datové typy zásobník fronta, seznamy, řady, vektory a jejich implementace]]
# [[Stromové struktury (Avl, BVS, B, Red-Black) a jejich implementace]]
# [[Skip-list - použití a implementace]]
# [[Tabulky s rozptýlenými položkami, vyhledávání v tabulkách]]
# [[Algoritmy zpracování textů – operace s řetězci, porovnání se vzorem (KMP, Boyer-Moore algoritmus), nejdelší společný podřetězec (LCS algoritmus), vzdálenost mezi řetězci, datová struktura Trie a použití]]
# [[Komprese dat, rozdělení kompresních metod, princip kompresních metod (Huffmann, aritmetické kódování, LZW, JPG, fraktálová komprese)]]
# [[Grafové algoritmy (cesta – Dijkstra, Floyd-Warshal, kostra – Prim-Jarnik), reprezentace grafu (matice, seznam sousednosti), základy kryptografie (symetrické, asymetrické šifrování)]]

== ZOS ==

# [[Rozdělení OS, architektura a komponenty OS]]
# [http://www.512.cz/index.php?title=Rozdělení_OS,_architektura_a_komponenty_OS#Komponenty_OS Základní funkce OS]
# [[Vyvolání služeb OS, zpracování přerušení]]
# [[Proces, implementace procesu, konstrukce pro vytváření procesů]]
# [[Paralelní procesy, prostředky pro popis paralelních procesů, vlákna]]
# [[Problém kritické sekce]]
# [[Prostředky pro synchronizaci procesů]]
# [[Semafory, jejich použití a implementace]]
# [[Monitory]]
# [[Problém uvíznutí procesů, graf alokace zdrojů]]
# [[Klasické problémy meziprocesové komunikace – producent-konzument aj.]]
# [[Plánování úloh a procesů v dávkových systémech]]
# [[Plánování procesů v interaktivních systémech]]
# [[Správa hlavní paměti, metody přidělování paměti, virtuální paměť]]
# [[Algoritmy nahrazování stránek paměti]]
# [[Ovládání periferních zařízení, RAID]]
# [[Systémy souborů]]
# [[Kontrola konzistence souborového systému, mechanismy ochrany před neoprávněným přístupem]]

{{fav-kiv}}
[[Kategorie:fav-kiv-bzinf]]
[[Kategorie:KIV]]

Rekurze

2017-06-07T08:32:04Z

Tomiksed: /* Příklady */

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).

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).

Rekurze musí mít následující podmínky:
* 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
* 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)

== Typy rekurze ==

* '''Přímá''' - metoda volá sama sebe
* '''Nepřímá''' - metoda volá metodu, která volá zpětně ji

* '''Lineární''' - metoda volá pouze jednu svoji kopii (faktorial)
* '''Stromová''' - metoda volá více svých kopií (Fibonacci, průchod adresářovou strukturou, často Divide & Conquer algoritmy)

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.

Příklad: Procházení adresářové struktury.
Vytvoříme metodu ProjdiAdresář(string cesta);

Iteračně (nesmysl?):

# Vytvoříme ukazatel na položku adresářové struktury ukazující "před?" výchozí adresář a uložíme tuto hodnotu do vedlejší proměnné
# Posuneme ukazatel na další položku adresáře
# 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 "před?"
# Je-li pod ukazatelem adresář, označíme jej jako zpracovaný (i když je otázka jak) a posuneme ukazatel na jeho první položku
# Je-li pod ukazatelem soubor, [otevře, vypíše název, zpracuje, přidá do vlastní datové struktury,...], a označíme soubor jako zpracovaný
# Zpět na bod 2

Zásobníkem:

# Načte obsah adresáře 'cesta' do zásobníku
# Prochází položky zásobníku:
## Je - li položka soubor, [otevře, vypíše název, zpracuje, přidá do vlastní datové struktury,...]
## Je - li položka adresář, načte jeho obsah do zásobníku
# Opakuje body 2 a 3 dokud není zásobník prázdný

Rekurzivně:

# Načíst obsah adresáře 'cesta' a prochází jednotlivé položky
# Narazí - li na soubor, [otevře, vypíše název, zpracuje, přidá do vlastní datové struktury,...]
# Narazí - li na adresář, volá sama sebe na jeho cestu

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)

Pár slov k implementaci rekurze:
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.

// http://www.abclinuxu.cz/clanky/ruzne/komiks-xkcd-244-stolni-rpg pro ty, to ví co je Dungeons & Dragons

== Příklady ==

Výpočet faktoriálu:

int faktorial(int f) {
if (f <= 1)
return 1;
else
return f * faktorial(f - 1);
}

Fibonacciho posloupnost:

Pozor na tento příklad. Fibonacciho posloupnost je jeden z nejhorších příkladů rekurze. Použitím rekurze u fibonacciho posloupnosti se dostáváte na velmi vysokou exponenciální složitost algoritmu, vedoucí k miliardám volání pro počáteční prvky posloupnosti. 50. prvek posloupnosti, skoro 16 miliard volání funkce fibonacci. Tento příklad nepatří do materiálů, natož ke státnicím!!! (pokud tedy není uváděn jako špatný příklad pro použití rekurze)

int fibonacci(int n) {
if (n <= 2)
return 1;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}

{{fav-kiv-bzinf}}
[[Kategorie:fav-kiv-bzinf]]

Halda

2017-05-28T16:39:01Z

Tomiksed: /* Vlastnosti */

Halda je datová struktura, která má následující vlastnosti:

* Jde o strom
* Pokud C je potomkem P, potom hodnota h(C) <= h(P)

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ě.

== Implementace ==

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á ...)

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.

== Vlastnosti ==

Vyhledání nejvyššího prvku v haldě je triviální (jde o kořen haldy, tedy O(1))

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.

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.

Implementace na poli:
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

Implementace objektově
Jako spojová struktura, je však nutné udržovat pointer na rodiče nejnižší úrovně (to může být problematické a pomalé)

{{fav-kiv-bzinf}}
[[Kategorie:fav-kiv-bzinf]]

Halda

2017-05-28T16:38:11Z

Tomiksed: /* Vlastnosti */

Halda je datová struktura, která má následující vlastnosti:

* Jde o strom
* Pokud C je potomkem P, potom hodnota h(C) <= h(P)

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ě.

== Implementace ==

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á ...)

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.

== Vlastnosti ==

Vyhledání nejvyššího prvku v haldě je triviální (jde o kořen haldy, tedy O(1))

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.

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.

Implementace na poli:
Má-li prvek na indexu k v poli potomky, jsou na indexech 2k a 2k+1. 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

Implementace objektově
Jako spojová struktura, je však nutné udržovat pointer na rodiče nejnižší úrovně (to může být problematické a pomalé)

{{fav-kiv-bzinf}}
[[Kategorie:fav-kiv-bzinf]]

Problém uvíznutí procesů, graf alokace zdrojů

2017-05-26T17:43:07Z

Tomiksed: /* Řešení zablokování */

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.

== Podmínky vzniku uvíznutí ==
(musejí být splněny všechny 4, 1-3 jsou předpoklad pro 4):
# Vzájemné vyloučení: každý zdroj je buď dostupný, nebo je výhradně přiřazen právě jednomu procesu
# „hold and wait“: proces držící výhradně přiřazené zdroje může požadovat další zdroje
# Nemožnost odejmutí: jednomu přiřazené zdroje nemohou být procesu násilně odejmuty
# 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

Tyto 4 podmínky mohou být modelovány pomocí orientovaných grafů = ''graf alokace zdrojů''.

Graf má 2 typy uzlů:
* proces - zobrazujeme jako kruh
* zdroj - zobrazujeme jako čtverec
Význam hran:
* od zdroje k procesu: zdroj držen procesem
* od procesu ke zdroji: proces je blokován čekáním na zdroj
Cyklus v grafu je nutnou a postačující podmínkou pro vznik uvíznutí

[[Soubor:Alokace-zdroju.jpg]]

== Řešení zablokování ==

# '''Pštrosí algoritmus''' - Zablokování se ani nedetekuje, ani se mu nezabraňuje, ani se neodstraňuje, Uživatel sám rozhodne o řešení (kill). Nespotřebovává prostředky OS - nemá režii ani neomezuje podmínky provozu. (Nejčastější řešení - Unix, Windows)
# '''Detekce a zotavení''' - Hledá kružnici v orientovaném grafu (hrany vedou od procesu, který čeká, k procesu, který prostředek vlastní), pokud tam je kružnice, nastalo zablokování a je třeba ho řešit:
#* Odebrání prostředku - dohled operátora, pouze na přechodnou dobu
#* Zabíjení procesů z cyklu (resp. mimo cyklus vlastnící identický prostředek)
#* Rollback (OS ukládá stav procesů, při zablokování se některé procesy vrátí do předchozího stavu => ztracena práce... obdoba u DB)
# '''Vyhýbání se''' - Bezpečný stav (procesy/prostředky nejsou zablokovány, existuje cesta, jak uspokojit všechny požadavky na prostředky spouštěním procesů v jistém pořadí); Viz bankéřův algoritmus. Nutné je předem znát všechny prostředky, které budou programy potřebovat; OS pak dává prostředky tomu, který je nejblíž svému maximu potřeby a navíc pro který je prostředků dost na dokončení. Dnes se moc nepoužívá.
# P'''ředcházení (prevence)''' - napadení jedné z Coffmanových podmínek
# '''Vzájemné vyloučení''' - spooling (prostriedky spravuje jeden systemový proces, ktory dohliada na to, aby jeho stav bol konzistentny (tiskarna) - pozor na místo na disku)
# '''Drž a čekej''' - žádat o všechny prostředky před startem procesu. Nejprve všechno uvolnit a pak znovu žádat o všechny najednou
# '''Neodnímatelnost''' - vede k chaosu
# '''Čekání do kruhu''' - nejvýše jeden prostředek - všechny prostředky jednoznačně očíslovány, procesy mohou žádat o prostředky jen ve vzestupném pořadí
# '''Dvojfázové zamykání''' - nejprve postupně všechno zamykám (první fáze). Potom se může pracovat se zamčenými prostředky - a na závěr se už jen odemyká (druhá fáze) - viď transakční spracování u databází ((striktní/konzervativní) dvoufázové zpracování)

''Bankéřův algoritmus'': Bankéř má klienty a těm slíbil jistou výšku úvěru. Bankéř ví, že ne všichni klienti potřebují plnou výši úvěru najednou. Klienti občas navštíví banku a žádají postupně o prostředky do maximální výšky úvěru. Až klient skončí s obchodem, vrátí bance vypůjčené peníze. Bankéř peníze půjčí pouze tehdy, zůstane-li banka v bezpečném stavu.

{{fav-kiv-bzinf}}

[[Kategorie:fav-kiv-bzinf]]