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

KEE

2012-02-14T16:19:49Z

81.201.60.162:

[[KEE/ZBP - Základy bezpečnosti práce]]

KEE

2012-02-14T09:14:45Z

81.201.60.162:

[[KEE/ZBP - Základy bezpečnosti práce]]
ll
u

KEE

2012-02-14T09:13:15Z

81.201.60.162:

[[KEE/ZBP - Základy bezpečnosti práce]]
ll

Vyjmenujte a stručně popište alespoň dva mechanizmy porušení kompozitních materiálů

2011-09-16T15:39:48Z

81.201.60.162: Založena nová stránka: Typy porušení * delaminace - roztržení dvou vrstev kompozitu od sebe * porušení vláken ** vláknové přemostění ** ztráta adheze - praskne jedno vlákno, ale...

Typy porušení
* delaminace - roztržení dvou vrstev kompozitu od sebe
* porušení vláken
** vláknové přemostění
** ztráta adheze - praskne jedno vlákno, ale ostatní drží. Může dojít k lokální ztrátě adheze - v místě se poruší několik vláken.
* porušení matrice - dutiny v pojivu
* tahem - prasknutí pojiva mezi vlákny ve směru kolmém na osu vlákna

{{fav-kme-umm}}

Rekurze

2011-08-25T22:26:57Z

81.201.60.162: /* 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:

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

{{fav-kiv-bzinf}}

Analýza programů

2011-08-25T13:12:58Z

81.201.60.162:

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.

== Časová náročnost ==

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<sub>operace</sub> a jejich skádáním počítáme celkový čas potřebný pro provedení algoritmu.

Příklad: Naplnění již alokovaného pole náhodnými čísly (c#)

for (int i = 0, i < pole.Length; i++)
{
pole[i] = rand.Next();
}

máme pole délky n = pole.Length
alokace proměnné trvá caloc
operace přiřazení trvá cpřiřazení
operace porovnání trvá cporovnání
operaci inkrementace lze definovat jako Cinkrement = cpřiřazení + csoučet
řekněme, že generování náhodného čísla trvá konstantní čas Crand

Inicializace cyklu for: alokace + přiřazení = caloc + cpřiřazení
Běh cyklu: porovnání (i<length) + přiřazení (do pole) + náh.číslo + inkrementace (i++) = cporovnání + cpřiřazení + Crand + Cinkrement
Cyklus for proběkne n-krát, tedy: n * ( cporovnání + cpřiřazení + Crand + Cinkrement )

Celkem: caloc + cpřiřazení + n * ( cporovnání + cpřiřazení + Crand + Cinkrement )

Asymptotická složitost:
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 + nb, kde a a b jsou doby, které mají určitou délku, která nás však přísliš nezajímá.

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é.
Rozlišujeme také složitost algoritmu a složitost problému (ta by měla patřit do otázky PPA1).

Theta notace Θ(f(x)) vyjadřuje A.S., omezenou složitostní funkcí c1,2 * f(x) shora, resp zdola, hledáme tedy 2 konstatnty, pro které je analyzovaná složitost omezena.

Tato notace říká, že algoritmus nebude asymptoticky složitější než c1 * f(x), a nebude rychlejší než c2 * f(x).
Tato notace říká, že problém lze řešit algoritmem, který nebude asymptoticky složitější než c1 * f(x), a neexistuje řešení lepší než c2 * f(x).

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.

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, respektive že problém nelze řešit jednodušeji, než algoritmem složitosti f(x). Druhá podmínka theta notace.

Pokud platí omikron a omega notace pro stejnou f(x), mluvíme o theta notaci.

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ř n2 + n2 = 2n2 => n2, 200 operací je asymptoticky stejné jako 100, ale n2 + n3 => n3 , 100 * 100 operací je vzhledem k 100 * 100 * 100 zanedbatelné)

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

Očekávaná složitost:
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í.

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)

Klasifikace složitosí:
Polynomiální - složitost O(nc) kde c je konstanta. Polynomiální algoritmy jsou použitelné. Ideální jsou algoritmy rychlejší (lineární, logaritmické,...), ne vždy j však možné takový algoritmus vymyslet

Exponenciální - složitost O(cn). 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.

Postupy výše lze aplikovat i na složitosti paměťové, šířky pásma, ...

KIV/BZINF - Státnice pro informatiky

2011-08-24T05:07:06Z

81.201.60.162:

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.

== PPA2 ==

# [[Problém, algoritmus, program]]
# [[Vykonání programu]]
# [[Objekt, třída]]
# [[Spojové datové struktury]]
# [[Správnost programů]]
# [[Analýza programů]]
# [[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 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. 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}}

Komprese dat, rozdělení kompresních metod, princip kompresních metod (Huffmann, aritmetické kódování, LZW, JPG, fraktálová komprese)

2011-08-23T21:45:44Z

81.201.60.162: /* Aritmetické kódování */

Algoritmy pro kompresi dat používáme pro snížení velikosti přenášených dat
* z paměťových důvodů
* ušetření šířky pásma
* urychlení přenosu a zkrácení doby odezvy
* archivace dat, zálohy
* obrana proti virům
* distribuce software
* ...

'''Kvalita komprese''' - úrověň zmenšení, poměr komprese = před/po. Symetrické metody potřebují stejný čas ke komprimaci jako k dekomprimaci

== Rozdělení kompresních metod ==

* '''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
* '''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.

== Metody komprese ==

* '''Jednoduché''' - založené na kódování opakujících se posloupností znaků (Run-Length Encoding - RLE)
* '''Statistické''' - založené na četnosti výskytu znaků v komprimovaném souboru (Huffmanovo kódování, Aritmetické kódování)
* '''Slovníkové''' - založené na kodování všech vyskytujících se posloupností (Lempel-Ziv-Welch - LZW)
* '''Transformační''' - založené na ortogonálních popř. jiných transformacích (JPEG, waveletová komprese, fraktálová komprese)

== RLE ==

RLE (Run Length Encoding) – kódování délkou běhu

Nejjednodušší komprimační algoritmus, nahrazuje opakující se znaky jedním znakem a číslem vyjadřujícím počet okpakování (AAAAABBBBBCCD -> 5A5B2C1D)
Pro text k ničemu, pro obraz celkem dobrá komprese (zvláště obrazy používající malou paletu barev)
Problém: pokud se znak neopakuje, dochází k expanzi (ABC -> 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.

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

== Huffmanovo kódování ==

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

Kódy vytvoříme Huffmannovým stromem:

* Jednotlivé znaky označíme jako listy stromu
* Tyto listy uložíme do seznamu S (S obsahuje uzly stromu, na začátku tedy pouze listy)
* Seznam S seřadíme podle četnosti
* Vybereme z S dva prvky M,N s nejnižšími četnostmi m, n, m < n
* Vytvoříme uzel p, kde vlevo je M a vpravo je N, a jeho četnost bude m+n
* Vložíme p do S a zpět na bod 3 dokud v S není jen jeden uzel

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)

Při dekompresi procházíme strom a rekonstruujeme zprávu.

[[Soubor:Huffman.png]]

== Aritmetické kódování ==

Také statistická metoda.
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 <0,1).

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 <0,1). Při kódování je pak celý interval <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).

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.

Příklad: kódujeme zprávu 'abaabcda'

[[Soubor:Aritmeticke-kodovani.jpg]]

Co z toho číst?
* První řádka ukazuje pravděpodovnosti písmen (ty vypočteme jako četnost písmene / písmen celkem)
* Dále vidíme, jak bude interval (a podintervaly) rozdělený. 'a' jako nejpravděpodobnější písmeno dostane největší část intervalu atd...
* 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.
* Zvýrazněná část intervalu se na obrázku vždy zazoomuje ;) (jsou tam šipky).
* 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)

== LZW ==

Z přednášek, doplněno:
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.
Princip:
Jednoprůchodová metoda (nevyžaduje předběžnou analýzu souboru. Ve výsledku se jen posunujeme po souboru jedním ukazatelem.)
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.
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.)
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ů).
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.

Aby to celé fungovalo, musíme slovník na dekomprimační straně "naučit" 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)

Pro obrázky viz přednášky z PT, jsou celkem snadno pochopitlené, i když místo "kód" občas autor používá "znak" či "nový znak", což je trochu matoucí.

== JPG ==

V současné době patří mezi nejvíce používané komprese u obrázků
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))

Princip:
části obrazu se transformují do frekvenční oblasti (výsledkem je matice „frekvenčních“ koeficientů, bezztrátový převod)
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)
zbývající koeficienty se vhodným způsobem zkomprimují (huffman, aritmeticky)

[[Soubor:Jpg-1.jpg]]
[[Soubor:Jpg-2.jpg]]

== Fraktálová komprese ==

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)

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é

[[Soubor:Fraktalova-komprese.jpg]]

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.

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.

Halda

2011-08-09T17:28:43Z

81.201.60.162:

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

Grafy a jejich implementace

2011-08-08T16:09:58Z

81.201.60.162:

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)

* '''Neorientovaný graf''': Hrany grafu nejsou orientované, tedy pokud vede hrana z uzli 1 do uzlu 5, vede i z uzlu 5 do uzlu 1 a platí tedy (u1, u2) = (u2, u1)
* '''Orientovaný graf''': Hrany grafu jsou orientované (jednosměrné), tedy pokud vede hrana z uzli 1 do uzlu 5, nevede z uzlu 5 do uzlu 1 a platí tedy (u1, u2) != (u2, u1)
* '''Ohodnocený graf''': Vednotlivé vrcholy či hrany mohou být ohodnoceny, graf tedy poté lze převést na množinu reálných čísel G(V, H) -> R

== Implementace grafu pomocí spojového seznamu (seznam sousednosti) ==

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)

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

== Implementace grafu pomocí matice sousednosti ==

Stejný graf jako v předchozím případě

Vytvoříme matici v*v prvků, kde v je počet vrcholů a hrany reprezentujeme jedničkami, zbytek matice jsou nuly.

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.

Ohodnocení lze provést uložením hodnoty místo jedniček, na diagonále lze ohodnotit vrcholy.

Problém, algoritmus, program

2011-08-03T19:32:48Z

81.201.60.162: /* Algoritmus */

== Problém ==

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

'''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í.

== Dělění problémů ==

Rozhodovací problémy lze dělit do tříd složitosti
* 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)
* 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ý "uhodne" kterou větví se vydat, případně mu něco "napoví" 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í.
* 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í)
* NP-úplné - NP-těžké problémy, které jsou ve třídě NP, jde tedy o nejtěžší NP úlohy

Pro zasmání: http://www.abclinuxu.cz/clanky/komiks-xkcd-287-np-uplnost

== Algoritmus ==

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

* Každý bod algoritmu musí být jednoznačně určen a musí být proveditelný (pochopitelný strojem)
* Algoritmus musí mít konečný počet kroků, tedy musí skončit po konečném počtu operací (x Výpočetní metoda)
* Algoritmus má 0 - N vstupů
* Algoritmus má 1 - N výstupů

== Výpočetní metoda ==

'''Výpočetní metoda:''' "Algoritmus", který není konečný (event-driven systémy jako třeba automat na kávu, snímače JIS karet, digitální hodinky...)

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

Problém, algoritmus, program

2011-08-03T19:31:59Z

81.201.60.162:

== Problém ==

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

'''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í.

== Dělění problémů ==

Rozhodovací problémy lze dělit do tříd složitosti
* 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)
* 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ý "uhodne" kterou větví se vydat, případně mu něco "napoví" 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í.
* 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í)
* NP-úplné - NP-těžké problémy, které jsou ve třídě NP, jde tedy o nejtěžší NP úlohy

Pro zasmání: http://www.abclinuxu.cz/clanky/komiks-xkcd-287-np-uplnost

== Algoritmus ==

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

Každý bod algoritmu musí být jednoznačně určen a musí být proveditelný (pochopitelný strojem)
Algoritmus musí mít konečný počet kroků, tedy musí skončit po konečném počtu operací (x Výpočetní metoda)
Algoritmus má 0 - N vstupů
Algoritmus má 1 - N výstupů

== Výpočetní metoda ==

'''Výpočetní metoda:''' "Algoritmus", který není konečný (event-driven systémy jako třeba automat na kávu, snímače JIS karet, digitální hodinky...)

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

Problém, algoritmus, program

2011-08-03T19:21:09Z

81.201.60.162:

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

'''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í.

== Dělění problémů ==

Rozhodovací problémy lze dělit do tříd složitosti
* 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)
* 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ý "uhodne" kterou větví se vydat, případně mu něco "napoví" 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í.
* 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í)
* NP-úplné - NP-těžké problémy, které jsou ve třídě NP, jde tedy o nejtěžší NP úlohy

// <http://www.abclinuxu.cz/clanky/komiks-xkcd-287-np-uplnost> :D

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.

Každý bod algoritmu musí být jednoznačně určen a musí být proveditelný (pochopitelný strojem)
Algoritmus musí mít konečný počet kroků, tedy musí skončit po konečném počtu operací (x Výpočetní metoda)
Algoritmus má 0 - N vstupů
Algoritmus má 1 - N výstupů

Výpočetní metoda: "Algoritmus", který není konečný (event-driven systémy jako třeba automat na kávu, snímače JIS karet, digitální hodinky...)

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.

KIV/BZINF - Státnice pro informatiky

2011-08-03T15:12:22Z

81.201.60.162: /* PT */

Hlavní strana

2011-07-31T20:07:07Z

81.201.60.162:

Wiki pro všechny studenty FAV

== Jednotlivé předměty roztříděné podle fakult ==

[[KFY]]

[[KIV]]

[[KMA]]

Hlavní strana

2011-07-31T20:06:31Z

81.201.60.162:

Wiki pro všechny studenty FAV
ff
test
== Jednotlivé předměty roztříděné podle fakult ==

[[KFY]]

[[KIV]]

[[KMA]]

Hlavní strana

2011-07-31T19:42:47Z

81.201.60.162:

Wiki pro všechny studenty FAV

test
== Jednotlivé předměty roztříděné podle fakult ==

[[KFY]]

[[KIV]]

[[KMA]]