30 Flashcards
reprezentace čísel
dvojková soustava, náboj na vodičích, high low, 1 0
bit (zkratka)
binary digit
Fixed point obecně + rozsah zobrazení
pevná řádová čárka (pevný počet číslic před a po); dnes hlavně celá čísla (čárka není) - <0, 2^n - 1> (minus jedno cislo protoze od nuly)
Přímý kód
se znaménkem, 2x nula, MSB udává znaménko
graf (kladný /; záporný )
Doplňkový kód
o jedno záporné číslo víc
graf (kladný /; záporný /)
Kód transformované nuly
MSB znaménkový bit (0 záporné, 1 kladné); samé nuly reprezentují nejnižší číslo -2^(n-1)
Sečítání, odečítání
if C == P then OK else overflow (O = C xor P)
Násobení
výsledek do 2x většíno prostoru; if záporné číslo, tak ho převedeme na kladné, spočítáme a výsledek na záporné
Floating point
repre pomocí znaménkového bitu, exponentu a mantisy;
X = (-1)^s * 2^(exp-bias) * 1.mantisa
IEEE754
standard definující aritmetiku s FP a pravidla konverze; single float 32bit (1znamenko, 8exp, 23 mantisa) (bias 127);
infinity (IEEE754)
exp 1111 mantisa 0000
NaN (IEEE754)
exp 1111 mantisa 0001
denormalizované číslo (IEEE754)
exp 0000 mantisa 0001
FP sčítání
není asociativní
FP násobení
X*Y = (mantisa X * mantisa Y) * 2^(expX + expY)
BCD
každá dekadická číslice na 4 bitech
VHDL defice
jazyk navržen a optimalizován pro popis struktury a chování elektronických systémů (popis a simulace);
vhdl struktura kódu
číslicové zařízení pomocí komponent (ta se zkládá z entity a architektury)
vhdl entita
definuje rozhraní, skládá se ze signálů a generických parametrů
vhdl architektura
popisuje strukturu nebo chování, svázaná s entitou; 3 úrovně popisu: strukturální, behaviorální, dataflow; věci uvnitře prováděny paralelně
vhdl procesy
blok sekvenčních příkazů uvnitř behaviorální architektury, má sensitivity list (seznam sig. kterými je spuštěn if změna)
VHDL proč vnikl?
před implementací na desku ozkoušíme
Komunikační kanály (definice)
způsob komunikace založená na lidských smyslech
Kom. kanály stroj->člověk
obraz (nejvíce info), sluch (umí upozornit), hmat (forcetouch), čich chuť (VR)
Kom. kanály člověk->stroj
hmat (myš, tastatur), sluch/zvuk (řeč, Siri macOS), gesta, neuralink
Metody komunikace
aktivní: uživatel řídí činnost počítače (klik menu, dávka v terminálu)
pasivní: uživatel odpovídá na dotazy počítače (gui modální okna, terminál Y/N)
Modální okna
uživatel na ně musí odpovědět, než může pokračovat
implementace mod. oken
zabránění průchodu zpráv do níže položených oken
Sys. řízený událostmi
základní princip práce s GUI, tok programu je řízen událostmi, listener čeká na příjem události (win ~ zprávy - typ zp., target okno, params)
implementace sys. řízeného událostmi
místem v programu: program čeká ve smyčce
stavovou proměnnou: na základě změny proměnné je volána fce
Prvky rozhraní
dialog boxy, buttony, radio, checkbox, slider, progressbar, seznam, file chooser
Jaké jsou dialog boxy
modal, non-modal (notifications,…), system-modal (priorita nad apps)
Značkovací jazyky
programovací jazyky sloužící pro popis dokumentů; převládá obecný text, značky ho uvozujů
dělení značkovacích jazyků
procedurální (TeX): značka definuje konkrétní akci, která se má s uvozeným prvkem provést.
deskriptivní (HTML): popis dat (-> informace), nemají přesně definovanou sémantiku
Rodina SGML
vznikl metajazyk SGML pro definici dalších značk. jaz. jako své podmnožiny (HTML); později vznikl XML -> XHTML
HTML
značk. jaz. pro hypertext (= text s odkazy provazující dokumenty), umožňuje tvorbu obsahu webu;
množina značek a atributů, kt. určují význam textu uvnitř
DTD
popisuje jak mohou být značky navzájem vnořeny a uspořádány; deklarace DTD uvedena direktivou
DOM
Document Object Model, objektově orientovaná reprezentace HTML, vytváří si ho prohlížeče
Druhy HTML značek
strukturální: <div> <p> </p><h1>
popisné: povaha obsahu <address>
stylistické: <b> <i></i></b></address></h1></div>
JavaScript
interpretovaný, objektový (prototyp), (asynchronní), jádro + knihovny
klientský JS
jádro + klient. vrstva; integrovaný do prohlížeče + DOM, global obj. window (DOM v window.document), prohlížeč generuje události
nevýhody JS
uživatel může JS zakázat, různé verze v prohlížečích, není přístup k souborům a systému (bezpečnost) - jen cookies
vložení JS
tag, src=file, přímo do html jako atributy onclick=””
Ajax (Veliký − hrdina Trojských válek)
asynchronní JS a HTML, umožňuje komunikai se serverem bez nutnosti načíst znovu stránku
CSS
kaskádové styly, prioritní strom, pravidla se na sebe nabalují a podle priorit se aplikují (embedded > id > class > tag)
Parametry hodnocení algoritmů
čas a paměťový prostor potřebný pro provedení (=> závisí na velikosti zpracovávaných dat)
Složitost algoritmu
funkce velikosti dat; čas (množství elem. kroků); pamět…
Způsoby určování složitosti
analýza algoritmu; aplikací na různý počet položek a vyhodnocení
Asymptotická časová složitost
vyjadřuje se porovnáním alg. s jistou fcí pro N blížící se nekonečnu; O Omikrot (horní hranice chodávní), Omega, Theta
přesné určování složitosti
pomocí turing. stroje, matematicky, testováním
f(n) = O(g(n))
f roste řádově nejvýš tak rychle jako g
Datové struktury
způsob uložení a organizace dat, aby je bylo možné pooužít efektivně
dělení dat. struktur
homogenní x hetero; statické x dynamické; lineární, ortogonální, …
homogenní dat. struktura
všechny komponenty téhož typu - pole; (x hetero. - záznam)
ADT abstraktní datový typ (definice)
je difinován množinou hodnot, kterých mohou nabývat prvky tohoto typu a množinou operací nad tímto typem
Datový typ (definice)
množina hodnot a množina operací nad těmito hodnotami
výraz
předpis na získávání hodnoty (je nositelem této hodnoty)
příkaz
pokyn, který se odehraje při běhu programu
Pole
homogenní, ortogonální datová struktura; prvky zpřístupněny indexem; statická strukt.
Seznam
homogenní lineární dynamická struktura; každý prvek (kromě head a tail) má předchůdce a následníka; sekvenčí přístup; varianty dvousměrný, kruhový
Zásobník
homogenní lineární dynamická struktura; LIFO; operace: push, pop, top, init, empty; využité: nerekurzivní průchod bin. stromem
Fronta
homogenní lineární dynamická struktura; FIFO; QueUp, Front, Remove, init, empty
Binární strom
Binární strom je buď prázdný, nebo sestává z jednoho uzlu (kořen) a dvou bin. podstromů - levého a pravého (oba vlastntosti stomu)
Váhově (výškově) vyvážený bin. strom
pro všechny uzly platí, že počet uzlů (výška) levého a pravého podstromu se rovná nebo libí právě o jeden
Řídicí struktury
strukturované příkazy -> sekvence, selekce, iterace
jednoduchý příkaz
přiřazení; proměnná := výraz
sekvence
složený příkaz; blok příkazů
selekce
podmíněný příkaz if {}; alternativní příkaz - if {} else {}; vícečetný alter. příkaz case/switch
iterace
příkaz cyklu; počítané (explicitní), nepočítane (implicitní), nekonečné
procedura
nástroj zvyšování abstrakce (nemá návratovou hodnotu -> jinak funkce); příkaz procedury: na místě volání se generuje skos do podprogramu, pak se řízení vrací
Důležitý parametr u Vyhledávání (kritérium hodnocení)
přístupová doba - doba potřebná pro nalezení; min, min, avg
způsoby vyhledávání
sekvenční v poli, + se zarážkou (odpadá kontrola na konec pole), v seřazeném poli (neúspěch dříve); binární, hash
Sekvenční vyhledávání v poli
O(n)
Binární vyhledávání
O(logn); musí být seřazené pole; Dijkstrova varianta (nalezene poslední ze synonym)
BVS
bin. strom, vlevo menší, vpravo větší, výška log2(n); vkládáním a mazaním může strom degenerovat -> vyvážit -> AVL; průchody pre, in, post -order, inorder dá seřazenou posloupnost (musí použít stack)
AVL
výškově vyvážený BVS (výška dvou podstromů se liší max o jedna), nutné znovuvyvážení LL rotace; O(logn) + jeho výška je vždy stejná (hledání v jedné větvi nebude delší než v druhé)
BVS + zpětné ukazatele
inOrder nemusí používat stack
Hash tabulka (TRP)
mapovací fce (ke klíči nalezne index); kolize, synonyma, indexsekvenční přístup, max doba dána nejdelším seznamem synonym; řazení implicitní (adresa následníka je funkcí adresy předchůdce)
Knuth-morris-prat
Používá KA, z každého uzlu vychází tolik hran, kolik je znaků abcd; lineární
Řazení (x třídění, setřídění)
třídí se odpad (do skupin), řadí se položky podle atributu; setřiďují se skupiny (vzniklé tříděním)
Smysl řazení
urychlení neúspěšného vyhledávání
Vlastnosti algoritmů třídění
stabilita − zachovává relativní pořadí prvků se stejným klíčem;
přirozenost − upořádané položky řadí kratší dobu než opačně uspořádné;
řazení bez přesunu položek
MacLarenův algoritmus
Principy řazení
selection (výběr) − vybírá min/max a přesouvá do seř. posl.
insertion (vkládání) − bere nějaký prvek a vkládá do seřazené posloupnosti
rozdělování (partition) − rozdělí na 2 podle mediánu a rekurze
slučování (merging) − sloučí dva prvky -> ty pak dají 4 -> ty 8 -> až hotovo
Selection sort
(výběr), nestabilní přirozená, O(n^2), G(n^2)
Bubble sort
(zaměňování), stabilní přirozená, O(n^2), G(n)!!; pro pro řazení s více klíči
Heap sort
nestabilní nepřirozená, O(n*logn); hromada - strom, otec vždy větší/menší než všichni syni; při porušení sift-down (O(logn))
Insert sort
(vkládání), stabilní přirozený, O(n^2), G(n)
Quick sort
(partition), nestabilní nepřirozený, O(n^2)-velice špatný pivot; G(n*logn); medián->pseudomedián
Merge sort
(slučování), nestabilní, nepřirozená, O(n*logn); potřebuje 2x větší pole (ne insitu); třípásková metoda
Životní cyklus SW
definuje etapy vývoje sw jako nutné činnosti se vstupy a výstupy;
proces vývoje sw
transformace potřeb uživatele na požadavky na sw, na jejichž základě je vytvořen návrh systému, podle nějž je sw implementován, otestován a předán zákazníkovi
učástníci na procesu vývoje
zákazník, dodavatel, uživatel
SW inženýrství
systematický přístup k vývoji, nasazení a údržbě sw; vzniklo jako odpověď na sw krizi
Etapy vývoje sw
- analýza a specifikace požadavků, 2. architektonický a podrobný návrh, 3. implementace, 4. integrace a testování, 5. provoz a údržba
- analýza a specifikace požadavků (co?, problémy?, výstup?)
transformace neformálních požadavků na strukturované; problémy: vyřazení, zkreslení, zobecnění;
Výstup: stukt. požadavky, plán akcept. test., prohlášení o cílech, studie vhodnosti
- architektonický a podrobný návrh
dekompozice na podsystémy + vymezení jejich funkcionality + definice vztahů; plánuje se testování a nasazení do provozu; požadavky na lidské zdroje;
výstup: návrhové třídy, rozhraní
- implementace
programová realizace + dokumentace + testování jednotliv částí; shora-dolů, zdola-nahoru, výstup: jednotlivé části sw
- integrace a testování
spojení částí do celku + test celého systému; akcept. testování a instalace - otestování uživatelem
- provoz a údržba
řešení chyb vznikajících z běhu, rozšiřování, přizpůsobování měnícím se požadavkům
Model živ. cyklu (co definuje?)
definuje etapy + čas návaznost
vodopádový model
nemožnost měnit požadavky po zahájení dalších etap
iterativní model
po každé iteraci je spustitelná verze s neúplnou funkcionalitou, možné upřesnění požadavků, nutnost rozdělení do iterací
spirálový model
jako iterativní + zavádí prototypování a analýzu rizik; prototyp se zahazuje
inkrementální
odevzdáváno po částech
V-Model
zaměřuje se na testování
RUP
rational unified process; iterační, důraz na vizualizaci UML, kontrolu kvality a dokumentaci; paralelní etapy; vývoj rozsáhlých sw
Agilní metodiky
ostatní spíše prodražují a zpomalují vývoj, důraz na člověka jako určující faktor kvality; menší sw projekty; scrum (sprint), extr. prog., TDD
jazyk UML
jednotný grafický jazyk pro specifikaci, vizualizaci, konstrukci a dokumentaci při oběkt. orient. analýze a návrhu i pro modelování organizaci; pohledy
pohled v uml
projekce systému na jeden z jeho klíč. aspektů; obsahuje prvky a vztahy (diagram)
statické diagramy UML
popisují strukturu; diagram tříd, komponent
dynamické diagramy UML
popisují chování; use-case (případy užití), sekvenční diagram, diagram spolupráce
základní stavební bloky UML
prvky - strukt., chování, seskupování, doplnkové (komentáře, poznámky);
vztahy − asociace – závislost, agregace, generalizace, realizace
diagram tříd UML
statický model, znázorňuje typy objektů a vztahy mezi nimi; vztah má název a násobnost
vztah kompozice a agregace UML
kompozice − silnější vztah seskupení (celek bez částí nemůže být), komponentní obj. může být součástí jen jedné kompozice; agregace − slabší, opak
vztah generalizace (zobecnění) UML
zachycuje dědičnost, vícenásobná může být, šipka s prázdným trojúhelníkem
vztah realizace UML
vztah mezi rozhraním a implementační třídou
diagram případů užití UML
aktéři, případy užití (ovál, kdo a co může vykonat), relace include (povinně zahrnuje), extends (volitelně rozšiřuje); detail případů užití − spec. tabulka (vstup, činnost, výstup)
sekvenční diagram UML
repre. časově orientovanou posloupnost předávání zpráv mezi obj.
diagram aktivit UML
modelování procesů
Stavový diagram uml
stavy do kt. mohou instance konkr. třídy vstupovat; KA
návrhové vzory
adapter (převádí nekomp. rozhraní), factory, singleton, observer
