rozne Flashcards
(21 cards)
Pouzitia ADT
Zasobnik:
- rekurzia
- vyhodnocovanie výrazov (infix-postfix)
- spatné sledovanie (labyrint, sudoku)
- prechádzanie stromov a grafom (DFS)
- undo-redo mechanizmy: Historia v prehliadaci
Fronta:
- planovanie procesov v OS
- fronty zariadeni (tlaciaren)
- simulacie frontov (zakaznici, letiska, banky)
- algoritmy prehľadávania do šírky (grafy BFS)
- sync v sieti - fronty paketov
Linked list:
- ostatne ADT zasobink, front
- dynamicke datove struktury - ked nepozname velkost udajov
- sprava pamate
typy instrukcii
🔄 Presun údajov:
* MOV – presun dát
* LOAD – z pamäte do CPU
* STORE – z CPU do pamäte
LEA - efektivnu adresu pamatoveho operandu do registra
➕ Aritmetické:
* ADD, SUB - odcitanie, INC, DEC, CMP, NEG, (DIV, MUL, )
🔣 Logické - 2 operandy. Výsledok uložia do ľavého operandu:
* AND, OR, XOR (exclusive OR), NOT
🔁 Posuny a rotácie - 2 operandy, register/pamäťové miesto akonštanta/register CL:
* SHL/SAL (do lava + carry bit), SHR/SAR, ( ROL, ROR, ARL (aritmetic), ARR)
🧭 Riadenie toku (skoky) - prepisuje sa IP register:
* JMP - nepodmieney skok ( JNZ (not zero), JC (carry), JNC (not carry), JGE (great eq))
📦 Zásobník:
* PUSH, POP
📞 Podprogramy a prerušenia:
* CALL (volanie podporgramu, adresa sa zapise do zasobnika, potom prepise IP), RET, INT, RTI
🔧 I/O operácie:
* IN, OUT
⚙️ Manipulácia príznakoveho registra:
* HALT, WAIT, ESC, LOCK (SEC (set carry), CLC (clear carry), STI (set interpupt), CLI)
sedemtaktovy
Fáza Skratka Popis Inkrementacia IP
1. FI Fetch Instruction – Načítanie inštrukcie z pamäte podľa IP 1 MC
2. DI Decode Instruction – Dekódovanie inštrukcie pomocou logickych obvodov 1 MC
3. FD Fetch Data (adresa) – Vypočíta sa adresa operandu ≥1 MC
4. FD Fetch Data (údaj) – Výber operandu inštrukcie z pamäte ≥1 MC
5. EI Execute Instruction – Vykonanie inštrukcie ALU ≥1 MC
6. WD Write Data – Zápis výsledku do cieľového miesta ≥1 MC
7. - Inkrementácia IP – Posun IP na ďalšiu inštrukciu 1 MC
3 suborove systemy
Súbor: jednosmerná sekvencia bajtov, dlhodobejší ako program; sú prístupne i po skončení programu
Char: spôsob ukladania prístupu a org súborov/priečinkov na diskoch. Umožňuje OS mapovanie logického umiestnenia súborov na fyzické (cez metadata)
Klasifikácia súb sys:
- Sekvenčný
- Priamy
- Pamatove mapovanie
Podpa sposobu pouzitia:
- lokalny
- sietovy (NFS, SMB)
- virtualny
Procesy a vlákna.
Program - zápis algoritmu v prog. jazyku
Proces - bežiaci program, tvorený nemenným kódom programu
- umiestnený vo vlastnom pamäťovom priestore v pdoboe postupností inštrukcií vykonavaných procesorom
- môže byť v roznych stavoch počas existenice
- Kontext procesu:
- textový a datový region (segment)
- zásobník
- registre, sys tabulky a záznamy v nich
Vlákno (thread) = “ľahký” proces, zdieľa pamäť procesu s ostatnými vláknami.
Správa procesov:
- pokiaľ je v PC menej procesorov ako bežiacich procesov - striedaju sa = zmena kontextu
- info každého procesu uložené v PCB (Process control block) na začiatku zásobníka jadra OS (chranené miesto pred ost použivatel a proces)
19 Digitalizácia obrazu
- získanie obrazu na monitore ==> prevod spojitej funkcie f(x, y) na diskrétnu funkciu l(i, j)
- spojitá fncia sa nahradí konečným počtom bodov (px) s konečným množstvom farieb
- rastr. obrázky = sieť myslených štvočekov + farebná hĺbka
Procesy:
* Vzorkovanie (sampling)
* odoberanie vzoriek v rovnakých intervaloch, kde obraz sa rozdelá na N riadkov a M stĺpcov
prienik riadka a stĺpca tvorí obrazový bod
* vzor. frekvencia - počet vzoriek za jednotku času (Hz) alebo vzdialenosť (DPI)
* interval vzorkovania - Nyquist-Shannonova veta:
* 2x väčšia ako najvyššia frekvencia vo vzorkovanom signáli, alebo
* interval vzorkovania musí byť tak veľký, aby bol menší alebo rovný ½ rozmeru najmenších detailov
* spôsoby:
* bodové - hodnota vzorky v jednom bode
* plošné - meraním zo vš hodnôt - priemerovaním
* Kvantovanie
Kvantovanie = koľko rôznych hodnôt intenzity môže mať každý pixel.
* čiselné vyjadrenie odobratej vzorky, výber hodnoty pomocou priemeru celého intervalu
* može dochádzať ku kvantizačnej chybe:
* šum (vo vysokých frekv)
* alias (v nízkych frekv)
HSV
- Intuitívny model – bližší ľudskému vnímaniu farieb
- Zložky:
- H – farebný tón (0–360°) – určuje farbu (červená, modrá, atď.)
- S – sýtosť (0–100%)
- V – jas (0–100%)
- Vizuálne znázornený ako ihlan
- Čisté farby po obvode podstavy, biela v strede, jas stúpa smerom nahor
- Nedostatok: neplynulý prechod medzi čiernou a bielou
HLS
(Hue, Lightness, Saturation)
* Ešte bližšie ľudskému vnímaniu ako HSV
* Zložky:
* H – farebný tón (0–360°)
* L – svetlosť (0–100%)
* S – sýtosť (0–100%)
* Lepšie zachytáva správanie farieb pri silnom stmavení alebo presvetlení
* vizuálne šestuholník
* Jas stúpa medzi čiernym a bielym vrcholom
Gamut
farebný rozsah zariadenia
* Predstavuje všetky farby, ktoré zariadenie (monitor, tlačiareň) dokáže zaznamenať alebo zobraziť.
* Zobrazuje sa ako trojuholník v CIE farebnom diagrame (pre RGB zariadenia).
* Farby mimo trojuholníka = “out of gamut” – zariadenie ich nedokáže zobraziť.
* Tlačiarne (CMYK) majú menší a zložitejší gamut, mení sa podľa jasu.
* ICC profily (.icc/.icm) ukladajú informácie o gamute zariadenia a slúžia na prevod farieb medzi zariadeniami.
* Color Matching Module zabezpečuje preklad farieb medzi zariadeniami s rôznymi gamutmi.
Vlastnosti farieb
🔢Farebná hĺbka
* Počet farieb, ktoré zariadenie dokáže zobraziť.
* 24-bitová grafika = štandard (8 bitov pre každú z R, G, B → 16,78 mil. farieb).
* Indexované farby = namiesto RGB hodnôt sa ukladá index z farebnej palety → úspora dát.
🌈Typy svetla
* Achromatické svetlo = biele svetlo (napr. slnko), obsahuje všetky farby.
* Monochromatické svetlo = svetlo len jednej farby (napr. červené).
* nechromatické - čierna, biela a odtiene šedej
📌Atribúty farieb
* Farba telesa - schopnosť pohlcovať a odražať žiarenie
* Farebný tón (Hue) – závisí od dominantnej vlnovej dĺžky.
* Odtieň – rozlíšenie medzi podobnými farbami (prechody, miešanie).
* Komplementárne farby – dve farby, ktoré spolu vytvoria bielu.
* Jas (luminancia) – intenzita svetla (od čiernej po bielu, rozsah 0–255).
* Svetlosť – podiel achromatickej (bielo-šedej) zložky vo farbe.
* Sýtosť – čistota farby, určuje, ako veľmi sa odlišuje od šedej.
Farebne schemy
- Monochromatická – odtiene jednej farby
- Analogická – susedné na farebnom kruhu
- Doplnková (Komplementárna) – opačné farby (napr. modrá – oranžová)
- Triadická – 3 farby, 120stupňov vzdialené
- Tetradická/štvorcová(radené do obdĺžnika/štvorca)
- Rozdelená komplementárna/doplnková(1 farba doplnená o 2 oproti),
CIDR skratka
classless inter-domain routing
DFA formal zapis
- Formálne: pätica M = (K, Σ, δ, q0, F)
- K je neprázdna konečná množina stavov,
- Σ je konečná vstupná abeceda,
- δ: K × Σ → K je prechodová funkcia,
- q0 ∈ K je počiatočný stav,
- F⊆K je množina akceptačných (koncových) stavov
PDA
paska + zasobnik
* sedmica A=(K, Σ, Γ, δ, q0, Z0, F)
* K: konečná množina stavov,
* Σ: vstupná abeceda,
* Γ (gama): zásobníková abeceda (symboly, ktoré sa ukladajú do zásobníka),
* δ: prechodová funkcia, ktorá môže byť nedeterministická,
* q0: počiatočný stav,
* Z0 : počiatočný symbol zásobníka,
* F: množina koncových (akceptujúcich) stavov .
* Rozpoznávanie slov zásobníkovým automatom:
* Akceptácia prázdnou pamäťou (prázdnym zásobníkom)
* Akceptácia koncovým stavom
neuzavreta na PRIENIK a DOPLNOK
Turingov stroj
- Teoretický/abstraktný výpočtový model - “definicia” algoritmickej riešiteľnosti
- šestica T = (Σ, Γ, K, q0, δ, F), kde platí:
- Σ(sigma) - vstupná abeceda ( B ∉ Σ B je blank symbol – prázdna bunka pásky).
- Γ(gama) - pracovná abeceda (obsahuje aj symboly vstupnej abecedy Σ ⊆ Γ, ako aj symbol B).
- K – konečná neprázdna množina stavov.
- q0 ∈ K – počiatočný stav.
- δ(delta) – prechodová funkcia
- F ⊆ K – množina akceptujúcich stavov .
- Obsahuje:
- Páska (nekonečná pamäť) - symboly prac. abecedy (inak vyplnene Blankom)
- Hlava (číta/zapisuje) - pohyb vľavo/vpravo/na mieste
- Stavový riadiaci mechanizmus
- Môže vykonávať: čítať, zapísať, posunúť hlavu, zmeniť stav
- Výpočet stroja môže skončiť (zastaviť sa) alebo pokračovať donekonečna (stroj sa nezastaví) .
- univerzálny - schopný realizovať akýkoľvek algo, aj keď obohatenie o ďalšie pásky, hlavy
- TS dokáže riešiť ÁNO/NIE problémy
- Akceptácia - ak sa zastaví v koncovom stave, Zamienutie - zastaví v ne-koncovom alebo zacyklí
Univerzálny Turingov stroj (UTM)
- dokáže simulovať ľubovoľný iný TS
- Vstup: popis iného TS + vstup pre ten stroj
- Základ pre koncept univerzálneho počítača
3 pasky:
- popis stroja - program
- obsah pasky stroja - data
- stavy stroja
kodovanie symbolov, tiez stavov, tiez posunu hlavy
1 -> a, 11 -> b…
oddelovac - 0 v prechod funkcii
delta(q1, a) = (q2, b, L)
00 oddeluje funkcie
Triedy zlozitosti problemov
- Rozdelenie problémov podľa výpočtových nákladov (čas/pamäť)
- Zohľadňuje sa veľkosť vstupu (n) a rast náročnosti algoritmu
- Časovou (a priestorovou) náročnosťou sa zaoberá teória zložitosti.
Časová zložitosť
* určuje počet krokov, ktoré algoritmus (resp. Turingov stroj) vykoná v závislosti od veľkosti vstupu.
* Nejde nám o presný počet operácií, ale o všeobecné vyjadrenie trendu rastu počtu operácií stroja v závislosti na veľkosti vstupných dát.
* Nechceme počítať presný čas výpočtu pre dáta určitej dĺžky, ale skôr poznať odpoveď na otázku, koľkokrát dlhšie bude trvať výpočet, ak vstupné dáta budú napr. desať krát vačšie.
* Bežne sa uvažuje zložitosť v najhoršom prípade („pesimistická zložitosť“), teda maximálny počet krokov, ktorý algoritmus potrebuje.
* Často sa používa asymptotická zložitosť, ktorá zanedbáva konštanty a menej významné členy výrazu (napr. n2 + 4n ≈ n2) .
- Zjednodušenie pohľadu na problematiku: zanedbáme rozdiely medzi stupńami polynomiálnej zložitosti a uvažujeme o dvoch triedach problémov: trieda so zložitosťou polynomiálnou a s exponenciálnou (hrubej sily- riešenie úplým prehľadávaním celého stavového priestory- vyskúšaním všetkých možností)
TCP
- TCP (Transmission Control Protocol)
* Vrstva: Transportná vrstva TCP/IP.
* Úloha: spoľahlivá, spojovaná služba pre prenos dát medzi aplikáciami. Vytvára virtuálny okruh medzi odosielateľom apríjemcom
* je spoľahlivý protokol, pretože deteguje chybu a opätovne prenáša poškodené segmenty.
* Vlastnosti:- Spoľahlivosť: potvrdenie prijatia dát, riadenie toku, ochrana pred zahltením siete.
- Každý segment TCP je označený sekvenčným číslom.
- Komunikácia prebieha cez TCP spojenie: vytvorenie spojenia (three-way handshake: SYN, SYN+ACK, ACK), prenos dát a ukončenie spojenia (FIN, FIN+ACK).
§ Komponent: Prístupové metódy
ako viaceré zariadenia zdieľajú prenosové médium (napr. kábel, vzduch pri Wi-Fi) a kedy môže ktoré zariadenie vysielať dáta.
* CSMA (Carrier-sense multiple access)
* detekcia obsadenosti média pred vysielanim
Aktívne sieťové prvky
Hub / opakovac (OSI L1) - bity na jednom porte odosiela na ostatne, 1 kolizna domena
Switch (OSI L2) - ramce cez MAC adresy, rozdeluje na mensie kolizne domeny
Bridge (OSI L2) - spája segmenty siete, MAC adresy, STP (Spanning tree protocol) - zamedzny zacykleniu
Router(Smerovač ) (OSI L3) - pakety podľa IP, smerovacie tabulky, ACL filtrovanie
Smerovanie
§ Smerovanie
Smerovanie je proces zabezpečenia prenosu IP paketov zo zdroja do cieľa cez počítačovú sieť pomocou smerovačov (routerov).
🔹Základné prvky smerovania:
* Koncové systémy: zariadenia ako počítače, mobily, tlačiarne – generujú a prijímajú dáta.
* Autonómne systémy (AS): skupiny sietí a smerovačov pod jednou administráciou, používajú spoločné smerovacie politiky.
* Medziľahlé systémy (smerovače): zaisťujú prenos dát medzi koncovými zariadeniami.
🔹Typy smerovania podľa rozsahu:
Intra
Inter
🔹Smerovače a smerovacia tabuľka
* Každý smerovač má smerovaciu tabuľku, kde sú:
* IP adresy cieľových sietí
* Najlepšia cesta k nim
* Smerovač vyberá cestu podľa najvhodnejšej metriky.
