PA1 Flashcards
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.
Řazení v lineárním čase
Speciální algoritmy, které nepracují v porovnávacím modelu.
CountingSort
Algoritmus pro řazení n prvků, jejichž klíče jsou celá čísla z množiny {0, . . . , r}.
• Řazení a paměťová náročnost (n+r).
• Není in-place ani datově citlivý.
Postupně prochází vstup a počítá pro každé číslo z množiny – kolikrát se číslo objevilo na vstupu.
Díky tomu vypočítá budoucí pořadí daného prvku a pouze přesune prvky ze vstupu na spočítané pozice.
Rozděl a panuj
Označuje algoritmy, které řeší problém rozdělením úlohy na dílčí části – podproblémy.
Jsou to většinou problémy, které lze řešit rekurzivně
Při vhodném použití může tato technika vést k překvapivě efektivnímu algoritmu.
Typický problém řešený metodou rozděl a panuj – Hanojské věže, MergeSort.
Rozděl a panuj - Rekurze
Rekurze je způsob programování, kde funkce k vyřešení problému volá sama sebe. Pro použití rekurze musí být splněny 2 obecné podmínky:
• Rekurzivní volání řeší menší (jednodušší) instanci původního problému.
• Existuje nějaké triviální instance problému, kde rekurze končí.
Výhody:
• Kratší zápis kódu
• Jednoduchost
Nevýhody:
• Možná časová náročnost(zbytečné opakování)
• Použití systémového zásobníku při „vnořování“
Každou rekurzi lze převést na Iteraci
Základní typy rekurze
• Koncová (tail)
o Rekurzivní volání je posledním příkazem algoritmu, po kterém se už neprovádějí žádné další operace.
o Lze snadno převést na iterační algoritmus.
o Např bubbleUp při vkládání do binární minimové haldy
• Lineární
o Rekurzivní volání se vyskytují v disjunktních větvích podmíněných příkazů a provede se z nich vždy jen 1.
• Stromová/kaskádní
o V těle algoritmu jsou za sebou aspoň dvě rekurzivní volání, která se za určitých okolností obě provedou.
Strom rekurzivnéch volání je tedy více-ární.
o Obvykle synonymum pro algoritmy Rozděl a panuj.
o Např Fibonacciho posloupnost
Rozděl a panuj - Iterace
Umožňuje posloupnosti instrukcí, aby se prováděly opakovaně dokud se nesplní nějaká podmínka. Zápis kódu je většinu delší, ale nedochází u něj k použití zásobníku.
Většinou se skládá z:
• Inicializace a stanovení podmínky
• Provádění příkazů ve smyčce
• Aktualizace kontrolní proměnné
Dynamické programování
Je technika návrhu algoritmů, která je založena na rekurzivním rozkladu problému na podproblémy. Na rozdíl od klasické metody Rozděl a panuj, metoda DP využívá toho, že podproblémy se během rekurzivního
rozkladu opakují. Podmínkou DP je opakovaný výskyt stejných podproblému při tomto rozkladu.
• Potom DP vede na mnohem rychlejší algoritmy než přímočarý rekurzivní rozklad.
Časová složitost rekurzivního výpočtu Fibonacciho čísla je Theta(1,61^n+1)
Vylepšení výpočtu pomocí memoizace
• Použijeme tabulku T do které zapíšeme každé nově vypočítané (narazíme na něj poprvé) Fibonacciho číslo.
• Při každém volání rekurzivní funkce se nejdřív díváme do příslušného políčka zda výsledek již neznáme.
=> O(n)
Princip Dynamického programování
Začneme s rekurzivním algoritmem, který má exponenciální složitost.
- Odhalíme opakované výpočty stejných podproblémů.
- Vytvoříme si tabulku do které budeme zapisovat výsledky již vyřešených podproblémů.
- Tím prořežeme strom rekurze a vznikne rychlejší algoritmus.
- Uvědomíme si, že tabulku lze vyplňovat bez rekurze, zvolíme-li vhodné pořadí podproblémů.
a. Tím získáme stejně rychlý (řádově), ale ještě jednodušší algoritmus.
Problém – nejdelší rostoucí posloupnost NRP
Na vstupu je posloupnost celých čísel. Úkolem je vyškrtnout co nejméně prvků tak, aby zbývající čísla tvořila rostoucí
posloupnost. → Najít nejdelší rostoucí podposloupnost.
1) Najdeme vzdálenost nejdelší rostoucí podposloupnosti.
Při rekurzivním volání a zkoušení všech možností je časová složitost exponenciální – O(2n).
Při použití tabulky – memoizace se dostaneme na čas O(n^2).
Rekurze se lze zbavit – začneme vyplňovat v opačném směru (od konce)
2) Najdeme vzdálenost i samotnou posloupnost – P[] – pole předchůdců.
