UPP - teorie

Kódová vzdálenost

Teorie

Kód

Definice

Kód je způsob reprezentace dat pomocí znaků podle určitého pravidla. Např. binární kód (0 a 1) slouží k ukládání a přenosu dat.

Typy

prostý $\geq 1$ | zabezpečující $\geq 2$ | samoopravný $\geq 3$

Princip konstrukce

Zabezpečující: Přidáváme paritní bity, které označují sudou nebo lichou paritu (podle zvolené metody)

Samoopravný: Na pozice mocnin dvou (např. 1, 2, 4, 8, …) přidáváme paritní bity, které kontrolují různé kombinace ostatních bitů.

Nadbytečnost

Proč nadbytečnost (redundance)?

Jsou to nadbytečné informace, které můžou zvýšit h-vzdálenost a zabezpečit tím data před chybami.

nadbytečnost v %,

( $\geq 2$ ): 8+1 (parita) = 1/9 = 11.11 %.

( $\geq 3$ ): 8+4 (1,2,4,8) = 4/12 = 33.33 %.

Vzdálenost

Hamingeova - Počet bitů, ve kterých se liší dvě kódová slova.

Minimální - Hammingova vzdálenost mezi všemi dvojicemi kódových slov v daném kódu.

Udává schopnost kódu detekovat nebo opravovat chyby.

H-Váha - počet bitů, které mají hodnotu 1 v binárním řetězci

Link to original

Data a Uložení

Informace a Data
- Definice + VS
  - Data: kodová zpráva (přenos v bin)
  - Informace: data + jejich iterpretace (čitelný pro člověka)
  - VS: Máme data po decodovaní asci tebulkou přečteme “text”
    - Data(101...10) -> interpretace dat -> Informace(Hello World)
- Jednotky
  - (b)it (1/0) | (B)ajt (1B=8b) | půl-byte | kB,MB,GB,TB
- Typy a uložení
  - Celé čísla - doplňkový kod
  - Desetiná číslá - kod s plovoucí čárkou (IEEE754)
  - Znaky - unicode / asci tabulka
Uložení dat
- Krátkodobé: RAM
- Dlouhodobé: HDD, SDD, Optické média(CD,DVD)
? Vnitřní paměti
- Rozdělení
  - RAM: Dočasná paměť pro běžící procesy
  - Cache: Rychlá paměť mezi procesorem a RAM pro často používaná data.
  - Registry: Velmi rychlá paměť přímo v procesoru pro okamžitá data.
  - ROM: Trvalá paměť, obsahuje firmware. (bios)
- Architektura
  - Hierarchie: Registry → Cache → RAM → ROM → Sekundární úložiště.
  - Adresace: Paměť je organizována do adresovaných bloků, které umožňují rychlé vyhledávání dat.
- Paměťové buňky:
  - Nejmenší jednotka paměti, uchovává 1 bit (hodnotu 0 nebo 1).
  - Seskupují se do bajtů (8 bitů) a větších celků.
- Virtuální paměť
  - virtuální paměť = technika, která umožňuje počítačovému systému rozšířit dostupnou paměť nad rámec fyzické RAM
  - přidělování = adresový prostor - každý proces dostane představovaný prostor paměti, který může používat, i když v reálné paměti (RAM) není celkově tolik místa
Typy Architektury a rozdíly
- Harvardská
  - oddělená paměť (data/program)
  - rychlejší, paralelní přístup
- Von Neumannovo
  - jednoduší, levnější ⇒ (běžné PC)
  - (sdílná, sekvenční-hrdlo)
- Životní cyklus (Von)
  - 1 INPUT --(program & data)-> operační pamět
  - 2 vlastní výpočet -> ALU (řízena řadičem PC)
    - mezivýsledky → registrů / OP
  - 3 RESULTS -> OUTPUT DEVICE

Algoritmy

Program
- Definice:
  - Program je soubor pokynů napsaných v nějakém programovacím jazyce, který je určen k tomu, aby řešil konkrétní problém.
- Interpretace vs Kompilace
  - Kompilace překládá celý program do strojového kódu před jeho spuštěním, zatímco interpretace vykonává kód řádek po řádku během běhu programu.
- +
  - Program je algoritmus popsaný tak, aby jeho popis mohl sloužit jako vstup pro počítač. (Skripta)
  - Interpretace je proces, při kterém se program vykonává přímo z původního kódu, bez jeho předchozího překladu do strojového kódu. (např. Python, JS)
  - Kompilace je proces, při kterém se celý program přeloží z vyššího programovacího jazyka (např. C, C++) do strojového kódu nebo do mezikódu (např. bytecode pro Java)
Algoritmus
- Definice: Algoritmus je konečná posloupnost kroků k vyřešení určitého problému.
- Vlastnosti:
  - Mechanický - při běhu se nemůže vracet k zadání
  - Deterministický - vždy se ví co bude další krok (neni to random AI)
  - Hromadný (zobecnitelnost) - je ready na jakýkoliv vstup, ne jenom čísla 123
  - Konečný+Resultativnost - musí někdy skončit a něco vrátit (UI/hodnota)
  - Správný - nespadne při špatným inputu
  - Other
    - Elementárnost: je tvořen z nedělitelných kroků
    - (Efektivnost)
  - ? Správnost algoritmu: splňuje všechny vlastnosti
- Jak se dá zobrazit?
  - Textově - krok za krokem (příkazy, podmínky).
  - Pseudo+Kodem - psedojazyk
  - Diagramem - Plošný, Vývojový, Stromečkový
Strukturogramy:
- Typy + +/-
  - Plošný: Vhodné pro hierarchická rozhodnutí.
  - Vývojový: Vhodné pro hierarchická rozhodnutí.
  - Stromečkový: Vhodné pro vizualizaci toků a podmínek.
    - lze zjemňovat, pojmenovat celky, úrovňové
  - (všechny nejsou dobré na komplexnější alg, užitečné pouze na jednoduché)
- Převod
  - Každý algoritmus má 3 typy prvků:
    - Sekvence: posloupnost příkazů za sebou
    - Iterace: Cyklus
    - Selekce: Podmínka
  - ? stačí?
Rekurze
- Definice: Podprogram který se sám volá
- Pravidla: musí obsahovat basecase aby někdy skončila (přerušení)
Podprogram
- Definice - je samostatná část kódu (funkce, procedura), která vykonává určitou úlohu.
- Why? - zjednodušení kódu a znuvupoužitelnost
- Správný návrat
  - Stack (zásobník): Uchovává návratovou adresu (kam se má vrátit).
  - Instrukce return: Provádí návrat z podprogramu.

Other

Semafor
- K čemu? Používá se k řízení přístupu více procesů ke sdíleným zdrojům, aby nedošlo ke konfliktům v kritické oblasti.
- Jakých hodnot může nabývat?
  - Binární semafor: 0=obsazeno, 1=volné (zámek)
  - Počítaný: Celé číslo (0 až N)
    - N=počet volných zdrojů | 0=všechny zdroje obsazeny → čekej
    - umí řídit více instancí stejného typu zdroje
      - např: thread pool, více tiskáren
- Funkce
  - Test (zkontrolovat): Je semafor volný?
  - Uzamknutí (zamknout): Zabrání přístupu ostatním.
  - Odemknutí (uvolnit): Umožní dalším procesům přístup.
- ostatní
  - Kritická oblast = Část kódu přistupující ke sdíleným prostředkům, kde hrozí konflikty při souběžném přístupu více procesů
  - Jak předejít zamrznutí? = Správná alokace zdrojů (např. pomocí semaforů) a dodržení pravidel synchronizace, aby žádný proces nehladověl
OS
- definice: software, který spravuje hardware počítače a poskytuje prostředí pro běh aplikací, zjišťuje komunikaci mezi uživatelem a hardwarem
- služby: Síťové, Bezpečnost, správa souborů a procesů, Správa paměti
Co je Boolengovská algebra, důsledek, ekvivalence, …
- Transclude of mix---Logika#^teorie
UI & API
- UI je rozhraní které umožnuje uživateli komunikovat s počítačem (terminál, plovoucí okna aplikací)
- API je rozhraní pro programy, např knihovny od OS poskytují API pro správu souborů nebo rest api pro čerpání dat z backend
Testovací tabulka
- Význam: Popsat jaky vyznam ma testovaci tabulka algoritmu a co obsahuje
- Obsahuje: vstupní data a očekávané výstupy, skutečné výstupy, poznámky

Datové struktury

Základní
- Stack
  - LIFO, jako talíře
    - poslední přidaný prvek je první odebrán
  - operace: Push, Pop, Peek
  - využití: paměti, iterativní rekurze
- Que
  - FIFO, fronta v obchodě
    - první přidaný prvek je první odebrán
  - operace: EnQue, DeQue, Peek
  - využití: tiskové, priority
- Strom
  - Hierarchická struktura, kde každý prvek může mít více podřízených (např. binární strom pro vyhledávání).
- Pole
  - soubor stejných objektů | fixní velikost | přístup prvků přes index
Soubor
- slouží k uchovávání a organizaci dat na pevném disku nebo jiném úložném médiu
- Pojmy
  - Integrita: Data musí být v souladu s reálnými objekty (např. kladný věk).
  - Redundance: Opakování dat, které není nutné (např. duplicita informací).
  - Konzistence: Uložené údaje musí zůstat stejné, pokud jsou opakovaně čteny.
Typy
- Statická
  - velikost a struktura jsou definovány při kompilaci a nemění se během běhu programu
  - např: Pole
- Dynamická
  - umožňuje dynamické přidávání a odebírání prvků během běhu programu
  - např: List, Strom
  - +Flexibilita -pamět,pomalejší

HW

Sběrnice
- Definice:
  - komunikační kanál, který propojuje různé části počítače a umožňuje přenos dat mezi nimi (např: mezi procesorem, pamětí a periferními zařízeními)
  - P(jakákoliv skupina vodičů, po které jsou data v systému přenášena z jedné součásti desky do druhé)
- Typy:
  - datová, adresová, řídící

fáze strojových instrukcí procesoru
- načtení instrukce, dekódování, provádění, zápis?
pevný disk HDD a SSD
- HDD = úložné zařízení, které používá magnetické disky k ukládání dat
- SSD = úložné zařízení, které používá flash paměť k ukládání dat, bez pohyblivých částí, díky tomu je rychlejší, tišší a odolnější než HDD
optický disk CD rom, DVD
- CD = optický disk, který umožňuje pouze čtení dat (ne zápis), je často používaný pro distribuci hudby
- DVD = optický disk, který je podobný CD-ROM, ale má větší kapacitu pro uchovávání dat, je použitelný pro video, software a další data
pixel, barevná hloubka, barevná mapa
- pixel = nejmenší jednotka obrázku na obrazovce nebo v grafice, která může mít určitou barvu
- barevná hloubka = určuje, kolik bitů je použito k reprezentaci barvy jednoho pixelu (čím větší barevná hloubka, tím více barev může být zobrazeno)
- barevná mapa = tabulka, která mapuje indexy nebo hodnoty pixelů na konkrétní barvy
alokační jednotka, stopa, sektor, cylindr
- alokační jednotka = nejmenší jednotka paměti, kterou operační systém přiděluje procesům
- stopa = jedna z kruhových drážek na povrchu rotačního disku (např. HDD), kde jsou uložena data
- sektor = nejmenší jednotka pro čtení nebo zápis dat na disku
- cylindr = všechny stopy na všech diskových plotnách, které jsou umístěny ve stejné poloze

Notes by Edems

Explorer

UPP - teorie

Kódová vzdálenost

Teorie

Data a Uložení

Algoritmy

Other

Datové struktury

HW