PA1 Flashcards
(32 cards)
Proměnná
pojmenovaný datový objekt obsahující nějakou hodnotu. Jsou jednoznačně identifikovány jmény.
Datový typ
definuje význam hodnot, kterých smí nabývat proměnná nebo konstanta a specifikuje:
• Množinu hodnot.
• Množinu operací, které lze s hodnotami provádět.
Rozdělení datových typů - Jednoduché
jejich hodnoty jsou z hlediska operací nedělitelné (atomické)
• Celočíselné - (signed/unsigned): int, short, long
o Hodnoty bez znaménka jsou uloženy v binárním kódu
o Záporné hodnoty nejčastěji reprezentovány doplňkovým kódem
o Pokud je datový typ delší než 1B, řeší se endianita
o Little-endian (intel) – little end first
▪ Nejnižší adresa obsahuje LSB (nejméně významný byte)
LSb (bit) určuje lichost/sudost)
o Big-endian (motorola) – nejnižší adresa obsahuje MSB
• Znakové (char)
o Znaky jsou kódovány jako čísla
o Různé standardy pro kódování znaků
▪ ASCII - 7 bitů, ASCII extended – 8 bitů, UNICODE - UTF-8, UTF-16, UTF-32, UCS2, UCS4
o V C/C++ a Javě platí: znak = ‘c’ , řetězec = “string“
• Racionální (float – jednoduchá přesnost, double – dvojitá přesnost)
o V paměti jsou racionální čísla zobrazena v pohyblivé řádové čárce
o Aproximují reálná čísla, ale mají omezený rozsah a přesnost
o Přesně vlastnosti dány implementací
o Semilogaritmický reprezentace
▪ Mantisa – udává přesnost
▪ Exponent – udává rozsah pohyblivé čárky
Rozdělení datových typů - Strukturované
▪ pole - jedno- i vícerozměrné, složky které jsou stejného typu, přístup ke složce je pomocí indexovaní
proměnné (p[i]) nebo pomocí ukazatele na prvek pole
▪ řetězce
▪ struktury - složena z různých typů, má definovanou strukturu. Přístup ke složce je pomocí selekce položky
(s.x, ps->x)
▪ union, file, třídy (C++)
Rozdělení datových typů - Ukazatele
Obsah premennej typu ukazatel je adresa, na ktorej sa nachádza daná hodnota
Využitie pre:
- predávanie výstupných parametrov
- pole ako parameter funkcie
- dynamická alokácia
Staticky alokované premenné
▪ Proměnná je vytvořená v době překladu.
▪ Musíme dopředu vědět, kolik paměti potřebuju - velikost zná překladeč předem.
▪ Výhoda takového přístupu je jeho rychlost a bezobslužnost – při definování proměnné
se vyhradí data a při opuštění příslušného bloku kódu se paměť automaticky uvolní.
▪ Jednodušší používání.
▪ Alokace statických proměnných
o Lokální proměnné → stack
o Globální a statické neinicializované hodnoty → .BSS (defaultně na 0)
o Inicializované proměnné (static int x = 6) → .DATA
Dynamicky alokované premenné
- Miesto v pamäti je vyhradené až pri behu programu
- veľká flexibilita
- prístup cez ukazatele
- alokácie - malloc, dealokácia - free, zmena veľkosti - realloc
- na halde
Spojové seznamy – datová struktura
▪ Lineární soubor dat, kde pořadí není určeno pozicí v pamětí,
místo toho každý prvek (uzel) odkazuje na další uzel.
▪ Tzn. množina objektů propojených pomocí ukazatelů.
▪ Spojový seznam slouží k ukládání dat předem neznámé délky.
▪ Druhy spojových seznamů: jednosměrný, obousměrný, cyklický.
▪ Umožňuje efektivní vkládání nebo odebírání prvků z jakékoliv pozice
Modulární programování
Zloitejšie programy sú rozdelené do niekoľkých súborov. Modulom sa v programovaní rozumie časť programu, ktorá poskytuje prostriedky inej časti programu. Zlepšuje udržateľnosť programu. Modul sa skladá z dvoch častí:
- Specifikační část - deklarácia funkcí, tried, dátových typov - Implementační - poskytnuté prostriedky sú implementované
C/C++ - hlavičkové a implementačné súbory
+ zrychlení kompilace
Procedury, funkce
Funkce a procedury jsou posloupnosti instrukcí sloužící pro zápis dílčího algoritmu (=podprogramy). Skládají se z:
- Definice
▪ Hlavička funkce/metody která specifikuje návratový typ, jméno a počet parametrů.
int sum (int a, int b); – funkce
void sumPrint (int a, int b); – metoda
- Deklarace
▪ Obsahuje tělo funkce (konkrétní implementace v programu)
Funkce – vrací návratovou hodnotu (výsledek) pomocí return.
Procedura – nevrací žádnou hodnotu – místo návratového typu je void.
Vstupní a výstupní parametry
▪ Vstupním parametrem jsou hodnoty sloužící jako vstup dílčího algoritmu, který je funkcí/metodou realizován.
▪ Výstupní parametr - umožňuje, aby funkce (procedura) přiřadila hodnotu do proměnné, která je dána
skutečným parametrem. Výstupní parametr je zadáván adresou místo returnem.
Překladač - kompilátor
● Slouží k překladu vyššího jazyka do jazyka nižšího.
● Nejčastěji překládá zdrojový kód do strojového kódu.
● Vzniká strojový kód s neřešenými referencemi mezi moduly – objektový soubor.
2 části
● Front-end – parsuje zdrojový kód do vnitřní reprezentace (IR) kompilátoru.
○ Závisí na jazyce.
● Back-end – překládá vnitřní reprezentace (IR) do strojového kódu cílové platformy.
○ Závisí na cílové architektuře (Intel, AVR,..)
IR – Intermediate Representations
Reprezentuje formu programu mezi zdrojovým kódem a výsledným jazykem konkrétní platformy. Pomáhá rozdělit komplikovaný proces překladu do více jednodušších částí a tím zajistit přenositelnost.
Linker
● Řeší reference mezi objektovými soubory a knihovnami.
● Slouží k propojení zkompilovaných modulů
○ Sestavuje z modulů a knihoven jeden funkční celek.
● jeho výstupem je spustitelný soubor.
Preprocessing
include header, expandovanie makier
Debugger
● Nástroj pro ladění kódu a hledání chyb v programu.
● Bývá součástí IDE, ale lze ho použít i samostatně.
● Může usnadnit pochopení, jak program funguje.
Časová a paměťová složitost algoritmů
Vyjadřuje závislost času/paměti potřebného pro provedení výpočtu dle rozsahu vstupních dat. Většinou se uvádí pouze analýza nejhoršího případu pomocí asymptotické O-notace.
O(1) – konstantní – je čídlo sudé / liché
O(log n) – logaritmická - binární vyhledávání
O(sqrt(n)) – házení vajíčka z paneláku (two egg problem)
O(n) – lineární – najdi největší číslo v neseřazeném poli
O(n log n) – qsort
O(n^2 ) – kvadratická - bubble sort
O(n^k) – polynomiální
O(2^n ) – exponenciální - faktorizace celých čísel ( 864 = 2^5 + 3^3 )
O(n!) – faktoriálová - brute force search
Algoritmy vyhledávaní - sekvenční, púlení intervalu
Sekvenčné:
Hľadáme postupne od začiatku dokonca, ak prvok nájdeme môžeme skončiť. O(n)
Púlení intervalu:
Predpokladom je zoradené pole. Opakovane zmenšujeme interval prohledávaných dat na polovinu, pokiaľ nenájdem hľadaný prvok alebo pokiaľ je možné zmenšovať - O(log n)
Algoritmy slučování a řazení - Bubble sort
Stabilní, in-place a datově citlivý
Problém zajace a želvy pri prebublávaní
O(n^2)
Algoritmy slučování a řazení - Select sort
Vybírá – selectuje nejmenší prvky v nesetříděné části a třídí (prohazuje je) na konec setříděné části pole.
Nestabilní, in-place, datově necitlivý
O(n^2)
Algoritmy slučování a řazení - Insert sort
Vezme první prvek v nesetříděné části a vloží ho
na správné místo v setříděné části
Stabilní, in-place, datově citlivý
O(n^2)
Algoritmy slučování a řazení - Merge sort
Rekurzivní algoritmus založen na operaci slučování.
- Řazený úsek rozděl na 2 části.
- Následně se seřadí levý a pravý úsek – zavoláním merge sort na sebe sama.
- Sloučení obou seřazených úseků
Nevýhody MergeSort
▪ poměrně vysoká multiplikativní konstanta
▪ Potřeba další paměťový prostor (není in-place)
• QuickSort tato omezení nemá
O(n * log n)
Algoritmy slučování a řazení - Quick sort
Vyber pivot (na něm závisí efektivita) a následně dej všechny menší prvky doleva a větší doprava. Na takto rozdělené části znovu zavolej QuickSort
O(n * log n) – průměr , O(n2 ) – worst case
Dolní mez složitosti řazení v porovnávacím modelu
Tzn. je možné řadit pomocí operace porovnávání v čase rychlejším než Theta(n log n) ?
NE , pokud je algoritmus
• Deterministický – každý krok je jednoznačně určen dle výsledků předchozích kroků.
• Pracuje v porovnávacím modelu – smí tedy prvky pouze vzájemně porovnávat a přesouvat.
