PA1

Question 1

Proměnná

Answer 1

pojmenovaný datový objekt obsahující nějakou hodnotu. Jsou jednoznačně identifikovány jmény.

Question 2

Datový typ

Answer 2

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.

Question 3

Rozdělení datových typů - Jednoduché

Answer 3

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

Question 4

Rozdělení datových typů - Strukturované

Answer 4

▪ 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++)

Question 5

Rozdělení datových typů - Ukazatele

Answer 5

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

Question 6

Staticky alokované premenné

Answer 6

▪ 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

Question 7

Dynamicky alokované premenné

Answer 7

• 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

Question 8

Spojové seznamy – datová struktura

Answer 8

▪ 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

Question 9

Modulární programování

Answer 9

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

Question 10

Procedury, funkce

Answer 10

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.

Question 11

Vstupní a výstupní parametry

Answer 11

▪ 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.

Question 12

Překladač - kompilátor

Answer 12

● 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,..)

Question 13

IR – Intermediate Representations

Answer 13

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.

Question 14

Linker

Answer 14

● Ř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.

Question 15

Preprocessing

Answer 15

include header, expandovanie makier

Question 16

Debugger

Answer 16

● 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.

Question 17

Časová a paměťová složitost algoritmů

Answer 17

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

Question 18

Algoritmy vyhledávaní - sekvenční, púlení intervalu

Answer 18

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)

Question 19

Algoritmy slučování a řazení - Bubble sort

Answer 19

Stabilní, in-place a datově citlivý
Problém zajace a želvy pri prebublávaní
O(n^2)

Question 20

Algoritmy slučování a řazení - Select sort

Answer 20

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)

Question 21

Algoritmy slučování a řazení - Insert sort

Answer 21

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)

Question 22

Algoritmy slučování a řazení - Merge sort

Answer 22

Rekurzivní algoritmus založen na operaci slučování.

1. Řazený úsek rozděl na 2 části.
2. Následně se seřadí levý a pravý úsek – zavoláním merge sort na sebe sama.
3. 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)

Question 23

Algoritmy slučování a řazení - Quick sort

Answer 23

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

Question 24

Dolní mez složitosti řazení v porovnávacím modelu

Answer 24

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.

Question 25

Řazení v lineárním čase

Answer 25

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.

Question 26

Rozděl a panuj

Answer 26

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.

Question 27

Rozděl a panuj - Rekurze

Answer 27

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

Question 28

Základní typy rekurze

Answer 28

• 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

Question 29

Rozděl a panuj - Iterace

Answer 29

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é

Question 30

Dynamické programování

Answer 30

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)

Question 31

Princip Dynamického programování

Answer 31

Začneme s rekurzivním algoritmem, který má exponenciální složitost.

1. Odhalíme opakované výpočty stejných podproblémů.
2. Vytvoříme si tabulku do které budeme zapisovat výsledky již vyřešených podproblémů.
3. Tím prořežeme strom rekurze a vznikne rychlejší algoritmus.
4. 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.

Question 32

Problém – nejdelší rostoucí posloupnost NRP

Answer 32

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ů.