Otázky statnice_mgr_nav_apl_vseobecna_12_otazek

smičková.
Převody mezi číselnými soustavami
Jednoduše lze převádět mezi soustavami, kde základ jedné soustavy tvoří základ mocniny druhé. Např. mezi dvojkovou, osmičkovou a šestnáctkovou soustavou.
2 → 8
Např pro číslo 111010110.
Vytvoří se pomocná tabulka:
0
1
10
11
100
101
110
111
A s ní se číslo převede 111 ~ 7 | 010 ~ 2 | 110 ~ 6 == 726

2 → 16
Např pro číslo 111001011101.
Vytvoří se pomocná tabulka:
0
1
10
11
100
101
110
111
1000
1001
A 1010
B 1011
C 1100
D 1101
E 1110
F 1111
1110 0101 1101
A s ní se číslo převede 1110 ~ E | 0101 ~ 5 | 1101 ~ D == E5D
8 → 2
Číslo se jednoduše převede podle zmíněných tabulek.
16 → 2
Číslo se jednoduše převede podle zmíněných tabulek po jednotlivých pozicích.
2 → 10
Tady je to o něco složitější. Číslo lze převést jako součet mocnin dvojek např.
100110 se převede jako 0.20 + 1.21 + 1.22 + 0.23 + 0.24 + 0.25 = 2 + 4 + 32 = 38
10 → 2
Obrácený převod se provede jako dělení se zbytkem:
38:2=190
19:2=91
9:2=41
4:2=20
2:2=10
1:2=01
Výsledek se čte odspoda:1001102
Zobrazení čísel v počítači
Čísla se mohou v paměti počítače v binárním tvaru zobrazovat buď jako:
Little endian – LSB je na nejnižší adrese.
Big endian – MSB je nejnižší adrese.
Zobrazení kladných čísel
U kladných čísel buď může nebo nemusí být přítomen tzv. znaménkový bit.
Rozsah pro zobrazení celých kladných čísel je
Pro 16-bitový integer je to (-32768, 32767)
n – počet bitů.
Zobrazení záporných čísel
U záporných
Přímý kód – jen přidání znaménkového bitu, nevýhodou je záporná nula
Inverzní kód – obrácení jedniček a nul
Dvojkový doplňkový kód – obrácení jedniček a nul + přičtení jedničky
Zobrazení reálných čísel
Zobrazení reálných čísel v počítači se řídí v architektuře PC vesměs normou IEEE 754. Standard pracuje s různými úrovněmi přesnosti např. 32 bitů, 64 bitů, 80 bitů. Např. na 32 bitech má 32 bitové slovo následující hodnotu:
3130...23220
znaménko (1b)exponent (8b)mantisa (22b)
Popis struktury:
Znaménko je znaménkový bit.
Exponent je vyjádřen jako celé osmitové číslo v rozsahu 0 – 255. Je to posunutá hodnota skutečného exponentu o hodnotu (2e-1 – 1) . Dostáváme tak rozsah exponentu 126 – 127.
Mantisa může být buď normalizovaná nebo denormalizovaná. Denormalizovaná mantisa znamená, že první (nevyjádřený) bit je roven nule. Týká se jen velmi malých čísel.
Příklad převodu čísla -118.625
Nejprve vezmeme znaménko, tj. první bit bude "1"
Zapíšeme číslo v binární podobě. 1110110.101.
Posuneme desetinnou čárku. 1.110110101 x 26
Mantisa je část za desetinnou čárkou a vyplní se nulami až se dostane celých 23 bitů
Exponent je 6. Nejdřív se přičte 127 a zkonverujte na binární formu: 6 + 127 = 133 10000101
Vznikne číslo: 1 1000 0101 1101 1010 1000 0000 0000 000

4. Procesy a paralelismus, koordinace běhu procesů, synchronizace procesů
a synchronizace procesů pomocí komunikace mezi nimi.
Procesy a paralelismus
Proces
Proces je instance provádění programu
Proces je identifikovatelný
Proces vlastní nějaké prostředky (např. otevřené soubory, prostor v paměti)
Stav procesu je v každém jeho okamžiku definovatelný pomocí:
obsahu registrů
zasobníku
datové sekce
programu, který jej řídí
Procesů zpravidla na jednom počítači běží více najednou. OS se stará aby počítač (resp. procesor) byl maximálně využit a stará se aby:
Procesor byl maximálně využit a prokládá běh procesů
Doba odpovědi procesu na podnět byla malá, proto prokládá běh procesů.
Spravuje zdroje přidělované procesům (vzájemné vyloučení, priorita)
Stará se o tvorbu procesů a komunikaci mezi procesy.
Stavy procesu
Nový – právě vytvořený proces
Běžící – program se interpretuje procesorem
Čekající – např. na I/O operaci
Připravený – čeká na přidělení procesoru
Ukončený – ukončil své provádění
OS si udržuje tabulku se seznamem procesů, s množstvím různých údajů (id, otevřené soubory, stav procesoru, ...)
Procesy a vlákna
Proces je jednotka provádění programu, charakterizovaná přiděleným kontextem a paměťovým prostorem.
Vlákno je systémový objekt viditelný uvnitř procesu, typicky se vlákna přidělují procesorům.
Vlákno může být buď běžící nebo připravené a může přistupovat ke zdrojům vlastněným procesem.
Pokud vlákno přistoupí k nějakému zdroji, např. si otevře soubor, vidí jej všechna ostatní vlákna.
Vlakna si muze spravovat bud aplikace sama nebo se o ne muze starat kernel.
Synchronizace procesů
Problémy
Klasické problémy při synchronizaci mezi procesy jsou:
Komunikace mezi procesy:
uváznutí – každý proces v systému čeká na zprávu od nějakého jiného procesu
stárnutí – dva procesy si donekonečna posílají zprávy a třetí proces donekonečna čeká na zprávu od některého z prvních dvou.
Sdílení prostedků (problém soupeření, race condition)
Problém při čtení a modifikaci sdílených dat. Operace čtení mohou být souběžné. Operace zápisu musí být výlučné vzájemně a výlučné s operacemi čtení.
Pro zabezpečení dat se používají kritické sekce.
Uváznutí
Pro vznik uváznutí jsou potřeba 4 podmínky:
Výlučný přístup
Postupné přidělování prostředků
Nepreemptivní přidělování prostředků – jednou přidělené prostředky nelze odebrat.
Cyklické čekání
Předchází se mu zrušením jedné z podmínek, nebo detekcí z zotavením nebo přidělování prostředků pouze tehdy, je-li to bezpečné.
Kritická sekce
V obecném případě se předpokládá n procesů, ve kterých se mohou vyskytovat úseky, kde je potřeba zajistit výlučný přístup ke sdíleným prostředkům. Takové úseky se nazývají kritické sekce a je třeba, aby se v nich v jeden okamžik nacházel vždy jen jeden proces.
Pro správné řešení problému kritické sekce je třeba zajistit:
Podmínku bezpečnosti – když proces provádí kritickou sekci, nemůže žádný jiný proces začít provádět kritickou sekci sdruženou se stejným zdrojem.
Podmínku živosti – jestliže žádný proces neprovádí kritickou sekci sdruženou s nějakým zdrojem, nesmí trvat výběr procesu, který chce vstoupit do kritické sekce sdružené s nějakým zdrojem nekonečně dlouho.
Podmínka spravedlivosti – musí existovat horní mez, kolikrát je povolen vstup do kritické sekce sdružené s nějakým sdíleným prostředkem jiným procesům, než procesu, který vydal žádost o vstup.
Nejjednodušší implementací kritické sekce na jednoprocesorových strojích je zamaskování přerušení pro zamezení přepnutí procesu nebo zpracování přerušení. Po dokončení kritické sekce je přerušení odmaskováno. Takto řeší krátké kritické sekce linux.
Předchozí řešení je poměrně brutální, existují samozřejmě elegantnější řešení např. pomocí semaforů. Proces, který vstoupí do kritické sekce zvedne semafor a ostatní procesy mohou provádět své kritické sekce s jinými semafory. Proces pak po ukončení kritické sekce zas semafor shodí. Takto řeší linux delší kritické sekce.
Synchronizační úlohy
Producent – Konzument – předávání zpráv mezi procesy
Je třeba jeden semafor pro vzájemné vyloučení na bufferu a semafory pro indikaci prázdných a plných míst.
Zajistí se tím vlastnosti vzájemného vyloučení, dále vyloučení možnosti plnění již plného bufferu nebo čtení z prázdného bufferu.
Čtenáři a Písaři – souběh čtení a modifikace dat
Operace zápisu musí být exkluzivní. Operace čtení mohou čtený zdroj sdílet. Operace čtení musí být výlučná s operací zápisu.
Implementace pomocí binárního semaforu wrt, integer semaforu readcount a integer semaforu.
Příklad implementace s prioritou čtenářů: První čtenář zablokuje všechny písaře. Poslední čtenář přistup písařů uvolní. Písaři mohou stárnout.
Večeřící filozofové – řešení uváznutí
N filozofů jí špagety dvěma vidličkami přičemž je k dispozici jen N/2 vidliček.
Možné řešení zrušení symetrie, filozof smí uchopit vidličky jen když má volné ruce a musí je uchopit v kritické sekci.
Semafory
Datový typ semafor obsahuje čítač a frontu čekajících procesů.
Dalším primitivem jsou semafory. Semafor má celočíselný čítač, a funkce Up(), Down(). Pokud je čítač větší než nula, pak zavolání Down() sníží jeho hodnotu o 1. Pokud je roven nule, pak se proces ve volání funkce down zařadí do fronty čekajících procesů na semaforu a uspí se. Pokud je čítač větší než nula, pak při volání Up() se zvýší o jedna. Pokud je čítač roven nule a fronta čekající procesů je neprázdná, pak při volání Up() se vybere jeden čekající proces z fronty a ten se pustí (opět přesněji přepne do stavu připraven). Pokud je fronta prázdná a čítač roven 0, pak volání Up zvýší hodnotu o jedna.
Binární semafor
Je často nazýván mutex (mutual exclusion).
Čítač semaforu je na začátku nastaven na jedničku.
Umožňuje jednoduše synchronizovat přístup do kritické sekce.
Monitory
Problém se semafory = Pokud například zapomenete použít operaci up() na konci kritické sekce, potom procesy čekající ve frontě budou čekat navždy (uváznutí).
Proto byl vymyšlen monitor, který zavádí invariant, který musí být splněn v případě, že proces končí kritickou sekci. Dále obsahuje semafor pro výlučný přístup a sadu procedur, kterými lze manipulovat se sdílenou proměnnou.
Monitory jsou bezpečnější než semafory, neboť jejich použití může řešit kompilátor a ne programátor, který může na správné zamykání zapomenout.
Synchronizace procesů pomocí komunikace mezi nimi
Máme k dispozici schránku o kapacitě n zpráv a funkce pro zaslání zprávy (send) a pro příjem zprávy (recieve). Pokud je schránka prázdná a proces volá recieve(), pak se proces uspí. Pokud je schránka přeplněná, a proces volá send(), pak se také uspí. Pokud je schránka prázdná a proces volá send(), pak probudí jeden z čekajících procesů, který zavolal recieve() na prázdnou schránku a analogicky naopak.

5. Schémata organizace souborů.
Soubor
Soubor je logická paměťová jednotka, která představuje kolekci vzájemně souvisejících informací.
Zpravidla je umístěn na vnějším paměťovém médiu, kde se zobrazují do alokačních bloků (což mohou být fyzické stránky, sektory atd.). Přístup k celým souborům řeší operační systém, vlastní organizace souborů může být buď standardní nebo proprietární.
Struktura souboru
Soubor se skládá ze záznamů, což jsou kolekce atributů charakterizujících nějaký objekt.
Na fyzickém médiu se pak člení do stránek (fyzických bloků).
Kolekce záznamů, která je spolu v nějaké relaci pak tvoří soubor.
Pro efektnivní řešení dotazů nad soubory a modifikaci souborů se soubory opatřují indexy.
Hlavní problém optimální struktury souboru
Hlavním cílem je minimalizace přístupů na typicky pomalé zařízení, na kterém je soubor umístěn.
Statické vs. Dynamické soubory
Soubory mohou být buď statické, nebo dynamické, tj. záznamy se mohou přidávat/měnit/mazat. V druhém případě je návrh optimální souborové struktury složitější.
Přístup k záznamům v souboru
Čistě sekvenční – zejména historicky v době páskových zařízení, doba přístupu závisela lineárně na velikosti souboru.
Přímý – souvisí s objevem disků. Přístup k záznamům mohl být realizován např.
Hašováním – adresa záznamu na disku = F(klíčová položka).
Indexy – Tabulka se záznamy {index : adresa na disku}. Indexy se posléze začaly ukládat do stromů. Dnes jsou hojně používané tzv. B-stromy s logaritmickou složitostí vyhledávání.
Schéma organizace souborů
Schéma organizace se dá rozdělit na tři úrovně.
Logické schéma
Logická paměť se strukturou optimalizovanou tak, aby umožňovala efektnivní operace nad soubory. Logická paměť se dělí na logické stránky, které obsahují vlastní data + pomocné struktury jako indexy atd.
Cílem návrhu optimálního logického schéma je vymyslet strukturu, která při přidávání, modifikaci nebo ubírání záznamů v souboru minimalizovala operace se stránkami.
Návrh zahrnuje operace jako přidávání stránek, vztahy mezi stránkami, plnění stránek atd.
V linuxu např. vrstva VFS (Virtual File System).
Fyzické schéma
Je už jen zobrazením logických stránek do použitého fyzické zařízení.
V linuxu např. ext2 filesystem.
Implementační schéma
Rozmístění fyzických stránek v použitém zařízení. Řeší se už většinou v režii operačního systému.
V linuxu např. IDE disk.
Složitost schéma organizace souborů
Prostorová – kolik fyzických stránek zabere zobrazení našich souborů
Časová – jak budou časově náročné operace nad těmito soubory.
Standardní organizace souborů
Hromada
Nehomogenní soubor se záznamy o proměnných délkách. Složitost vyhledávání roste lineárně s počtem záznamů. Může být i efektivní co do zabraného místa.
Neuspořádaný sekvenční soubor
Homogenní soubor podobný hromadě. Složitost vyhledávání je stejná, složitost přidávání záznamů je konstatní – záznam se prostě přidá na konec.
Uspořádaný sekvenční soubor
Homogenní soubor uspořádaný podle nějakého klíče. Data mohou ukládat přímo do souboru a online reorganizovat, nebo ukládají do neorganizovaného souboru a občas se pak vyvolá setřizovací operace.
Složitost vyhledávání je logaritmická – půlí se interval.
Indexované soubory
Obvyklá struktura indexu je
{vyhledávací klíč ; ukazatel záznamu}
Druhy indexů mohou být:
Husté indexy – v indexu je záznam pro každou hodnotu vyhledávacího klíče.
Řídký index – v indexu jsou záznamy pouze pro vybrané klíčové hodnoty. Používá se v případě, že záznamy v souboru jsou setříděné. Případně lze použít kombinaci obou indexů.
Struktura indexů může být:
Uspořádaná tabulka
Hašovaný index
Stromový index
Index-sekvenční soubory
Jejich struktura se skládá z:
Primárního souboru dat
Hiearchie indexů
Oblasti pro řešení anomálií při vkládání, občas je nutná reorganizace.
Typickým příklade je struktura MyISA – databáze MySQL, která se skládá ze souborů MYD – data a MYI – index.
Hašovací tabulka
Hašovací tabulka ke datová struktura, která spojuje klíče s hodnotami.
Dobrá hašovací funkce by měla být prostá funkce bez kolizí.

6. Rysy imperativně orientovaných jazyků, jazyků funkcionálního programování
a logického programování.Rysy objektově orientovaných jazyků.
Rysy imperativně orientovaných jazyků
V tomto případě je program tvořen posloupností příkazů (odtud imperativní).V každém kroku je určeno co se má vykonat v kroku následujícím a v každém kroku se změní stav progarmu. Programátor tak musí analyzovat všechny situace, do kterých se může program dostat a podle toho tvořit program.
Z toho vyplývá, že program napsaný v imperativním programovacím jazyce předpisuje jak něco spočítat.
Imperativní jazyky mají svou podstatou blízko k samotným počítačům, které provádějí strojový kód, který je sekvence nějakých příkazů. Např. imperativní programovací jazyky běžně používají explicitní přiřazení do proměnné a její uložení na nějaké paměťové místo. Vyšší programovací jazyky pak mohou používat cykly, podmínky cyklů, funkce a procedury.
Mezi první imperativní programovací jazyky patřil např. FORTRAN, dále ALGOL a COBOL. Mezi v současnosti rozšířené imperativní programovací jazyky patři C, Pascal případně PHP.
Rysy jazyků funkcionálního programování
Funcionální programování je paradigma postavené na evaluaci funkcí. Nepoužívá stavy ani neprovádí přiřazení do proměnných.
Určitý základ funkcionálních programovacích jazyků lze nalézt v lamda kalkulu (i když se jednalo spíše o matematickou abstrakci) a dále v tzv. logice kombinátorů, kterou lze nahlížet jako lambda kalkul bez proměnných.
Vlastnosti
Referenční transparentnost – znamená, že v daném kontextu představuje proměnná vždy jednu a tutéž hodnotu nebo také, že volání funkce na stejných parametrech vrátí vždy stejnou hodnotu (chybí totiž globální proměnné, vedlejší efekty a přiřazení do proměnné).
Příklad:
y = f(x) * f(x);
může kompilátor transformovat na
z = f(x);
y = z * z;
a ušetří jednu evaluaci funkce.
Striktní a líné vyhodnocování – funkcionální jazyky se mohou dělit podle toho zda používají striktní, nebo líné vyhodnocování. Striktní vyhodnocování vyžaduje předávání funkce hodnotou, kdežto líné vyhodnocování může za parametry funkce předávat i nevyhodnocený výraz.
Funkce vracející funkce – které berou za vstup opět funkce
Rekurze - často se používá místo iterace
Mezi funkcionální jazyky patří např. LISP, ML a mezi čistě funkcionální jazyky pak např. Haskell, Miranda.
Rysy jazyků logického programování
Logické programování vychází z použití matematické logiky v programování. Patří mezi deklarativní paradigma – obdobně jako funkcionální programování je jeho úkolem zadat co je třeba spočítat nikoliv jak to spočítat.
Logické programování je založeno na ohraničené části logicky prvního řádu. Pro logiku prvního řádu platí, že dovoluje užívání predikátů "Pro každé něco" nebo "Existuje něco", ale něco musí být individuum, ne predikát. Dále je založeno na logice Hornových klauzulí, což jsou konečné množiny literálů spojených disjunkcí, a které se pro potřeby logického programování přepisují do tvaru:
(P1 & P2 & P3 ... ) → Q
Literály jsou výrokové proměnné nebo jejich negace.
Program v jazyce Prolog je pak konečná množina Hornových klauzulí a skládá se z tzv. faktů, pravidel a dotazů.
Ilustrace z čeho se skládá:
otec(Jan, Pavel) – Fakt
otec(Pavel, Jana) – Fakt
děda(X,Y) :- otec(X,Z), (X,Y) – Pravidlo
A dotaz:
?-otec(jan,pavel)yes
Zástupcem logického programování je programovací jazyk Prolog, jehož vznik se datuje do roku 1972.
Rysy objektově orientovaných jazyků
Základním princip objektového programování je jednoduchý – vše jsou objekty. Objekty jsou nějaké entity, které mají nějaké vlastnosti – atributy a mají nějaké metody – procedury, tj mohou něco provádět. Dále se pak uplatňují následující vlastnosti.
Třídy
Jsou vyjádřením abstrakce skupiny stejných objektů (stejné atributy a vlastnosti). Např. třída člověk. Každý objekt ze třídy je pak instance třidy a dědí z ní všechny atributy a metody.
Dědičnost
Dědičnost se může uplatňovat u podtříd, které dědí všechny metody a atributy od nadtřídy a mohou si přidávat své vlastní.
Zapouzdření
Je stav, kdy objekt z nějaké třídy skrývá provádění některé své metody před okolím a navenek místo toho vystupuje jinou metodou např. pevně daným interface. Např. objekt třídy pes má metodu štěkat, ale uvnitř má další metody nadechnout a vydechnout.
Abstrakce
Je princip při modelování reálného světa, kdy si reálných tříd objektů všímáme jen vlastností pro nás podstatných a ty pak modelujeme.
Polymorfismus
Je vlastnost metod, kdy metody mohou mít stejné jmého, ale jejich chování závisí na tom, ke které třídě patří.
Předávání zpráv
Je komunikace mezi objekty jednoduše realizovaná tím, že objekt vyvolává metodu u jiného objektu.
Zástupcem objektových programovacích jazyků je např. SmallTalk, C++ či Java.

7. Architektura počítačových sítí, OSI model, IP, transportní protokoly
(TCP, UDP a další), základní služby počítačových sítí. Bezpečnost, základy
kryptografie, soukromé a veřejné klíče, autentizační protokoly,
digitální podpis. Správa sítí, směrování, směrovací protokoly. Firewalls,
řízení přístupu. Kvalita služeb.
Architektura počítačových sítí
Architektura počítačové sítě určuje strukturu sítě – z jakých stavebních a funkčních celků se skládá a jak tyto celky spolupracují. Většina sítí je organizována ve vrstvách (s tím pak souvisí ISO/OSI model) a počet vrstev a jejich vlastnosti se liší síť od sítě.
Pro dva síťové uzly platí, že pokud je komunikace mezi nimi pomocí sítě možná, pak vrstva n
prvního uzlu komunikuje vždy s vrstvou n druhého uzlu. Pravidla takové komunikace se nazývají protokol. Např. 10baseT ethernet se na fyzické vrstvě domlouvá protokolem Manchester.
Součástí protokolu je:
syntax – formátování dat, tvar signálových prvků (Manchester)
sémantika – řídící informace pro koordinaci, reakce na chyby (např. CDMA)
časování – rychlost přenosu signálů po médiu (např. 10baseT – 10Mhz)
OSI model
OSI je abstraktní model počítačové sítě založený na 7 vrstvách:
fyzická – signály na přenosovém médiu, např. Manchester na ethernetu.
rámcová – přenos rámců na ethernetu mezi fyzickými adresmi