💻 BI-PA1 + BI-AG1 – Programování a Algoritmizace

📦 Datové typy v jazyce C

Primitivní (základní) typy

Modifikátory signed / unsigned mění interpretaci bitového vzoru. Typ unsigned int má rozsah 0 … 4 294 967 295 (2³² − 1).

Složené typy

• Pole (array) – posloupnost prvků stejného typu uložená v paměti za sebou. Indexování od 0, bez kontroly mezí za běhu.
• Struktura (struct) – složený typ sdružující různé položky (např. jméno + průměr studenta). Přístup přes . nebo -> (přes ukazatel). Typedef umožňuje kratší jméno.
• Ukazatel (pointer) – obsahuje adresu v paměti. Deklarace: int *p;, reference: p = &x;, dereference: *p = 10;. Hodnota nullptr (nebo NULL) označuje „neukazuje nikam".
• Výčtový typ (enum) – pojmenované celočíselné konstanty.

🧠 Statická vs. dynamická alokace paměti

Segmenty paměti programu

• Kód (.text) – instrukce programu, read-only.
• Globální a statická data (.data / .bss) – globální proměnné, static lokální proměnné. Existují po celou dobu běhu programu. Inicializované hodnoty → .data, neinicializované → .bss.
• Zásobník (stack) – lokální proměnné funkcí, parametry, návratové adresy. Automaticky se alokuje při volání funkce a uvolňuje při návratu. Velikost omezená (jednotky MiB); přetečení = pád programu.
• Halda (heap) – dynamicky alokovaná paměť (malloc). Programátor zodpovídá za uvolnění (free). V C není garbage collector.

Pravidla práce s dynamickou pamětí

• Každý blok alokovat právě jednou a uvolnit právě jednou (free).
• Dvojité uvolnění (double-free) → pád programu.
• Neutěsnění (memory leak) – blok se stane nedostupným bez uvolnění → program postupně vyčerpá paměť.
• Správný vzor pro malloc: int *a = (int*) malloc(n * sizeof(*a));

🔗 Ukazatele – principy

Ukazatel je proměnná, která uchovává adresu v paměti. Umožňuje nepřímý přístup k datům.

• Deklarace: int *p; – p je ukazatel na int.
• Reference (&): p = &x; – p dostane adresu proměnné x.
• Dereference (*): *p = 10; – přistoupí k hodnotě na adrese p.
• Ukazatelová aritmetika: p + n posune adresu o n * sizeof(T) bajtů. Platné jen uvnitř pole.
• Ukazatel na strukturu: p->pole je zkratka pro (*p).pole.

Výstupní parametry (out-parametry)

Jazyk C předává parametry hodnotou (call by value). Funkce tedy nemůže přímo měnit proměnné volajícího. Řešení: předat ukazatel na proměnnou.

Příklad: Funkce void minMax(int a, int b, int *min, int *max) — volající předá &min, &max a funkce zapíše výsledky přes dereferenci. Bez ukazatele by se změny ztratily (kopírování).

🔄 Spojové seznamy (linked lists)

Jednosměrný seznam

• Každý uzel: hodnota + ukazatel next na následující uzel.
• Poslední uzel: next = nullptr.
• Přidání na začátek: O(1). Přidání na konec: O(n) bez pomocného ukazatele na konec, O(1) s ním.
• Přístup k i-tému prvku: O(n) — musíme projít od hlavy.

Proč ne pole?

Pole má pevnou velikost (nebo nákladné nafukování) a vkládání prvků do středu je O(n) (přesun). Spojový seznam umožňuje vkládání/mazání kamkoli v O(1) (pokud máme ukazatel na místo), ale nemá náhodný přístup.

typedef struct TNode {
  int value;
  struct TNode *next;
} TNODE;

Dvousměrný seznam

Přidává ukazatel prev na předchozí uzel. Umožňuje procházení oběma směry a efektivní mazání libovolného uzlu (bez hledání předchůdce).

⚙️ Procedury a funkce – parametry

Funkce je podprogram, který řeší dílčí problém. Hlavička: typ jméno(seznam parametrů). Tělo: blok příkazů. Funkce s návratovým typem void nic nevrací.

Vstupní parametry

V C jsou parametry vždy předávány hodnotou (kopírování). Změna formálního parametru neovlivní skutečný parametr volajícího. Pro velké struktury je efektivnější předat ukazatel.

Výstupní parametry

Simulujeme pomocí ukazatelů (viz výše). Funkce zapíše výsledek přes dereferencovaný ukazatel.

Rekurzivní funkce

Funkce, která volá sebe sama. Musí mít: (1) base case – triviální případ, který se řeší přímo; (2) rekurzivní volání na menší instanci problému. Zásobník si pamatuje kontext každého volání – při příliš hluboké rekurzi hrozí stack overflow.

Deklarace vs. definice

• Deklarace (prototyp): jen hlavička + středník; říká překladači, že funkce existuje a jaké má typy.
• Definice: hlavička + tělo; implementace funkce.

🧩 Modulární programování

Struktura modulu v C

• Hlavičkový soubor (.h) – popisuje rozhraní modulu: prototypy funkcí, typy, deklarace extern proměnných. Slouží překladači i programátorovi.
• Implementační soubor (.cpp/.c) – obsahuje definice (těla) funkcí. Vkládá vlastní .h soubor.

Proč modularita?

• Změna implementace bez přepsání ostatních modulů (stačí zachovat rozhraní).
• Opakované použití (znovupoužitelnost kódu).
• Paralelní vývoj v týmu.
• Přehlednost a udržovatelnost.

🔧 Překladač, linker, debugger

Fáze překladu zdrojového kódu

1. Preprocesor – zpracovává direktivy začínající #:
   • #include <soubor> – textové vložení souboru.
   • #define X hodnota – textová substituce (makra).
   • #ifdef / #ifndef / #endif – podmíněný překlad (různé platformy, ladicí kód).
2. Kompilátor (překladač) – překládá zdrojový kód do objektového souboru (.o / .obj), který obsahuje strojový kód s neřešenými referencemi (volání funkcí z jiných modulů, knihoven).
3. Linker (sestavovací program) – spojuje objektové soubory a knihovny (.a / .lib / .so / .dll) do výsledného spustitelného souboru. Řeší reference mezi moduly – přiřazuje adresám symbolů konkrétní hodnoty.

Debugger

Nástroj pro ladění programů. Umožňuje: krokování (krok po kroku), breakpointy (zastavení na určitém řádku), inspekci hodnot proměnných za běhu, sledování zásobníku volání (call stack), detekci paměťových chyb (např. Valgrind). Principem je pozastavení procesu a čtení/zápis jeho stavu.

Ochranné hlavičky (include guards)

Aby se hlavičkový soubor nevložil vícekrát, používáme vzor:

#ifndef __MUJMODUL_H__
#define __MUJMODUL_H__
// obsah hlavičky
#endif

📋 Shrnutí okruhu 1

• Primitivní datové typy (int, char, float…) mají pevnou velikost a rozsah; pozor na přetečení.
• Statická alokace (zásobník, globals) vs. dynamická (halda – malloc/free); každý alokovaný blok uvolnit právě jednou.
• Ukazatel = adresa; výstupní parametry simulujeme předáním ukazatele.
• Spojový seznam = uzly propojené ukazateli; dynamická velikost, ale sekvenční přístup.
• Překlad: preprocesor → kompilátor → linker; objektové soubory propojí linker do spustitelného souboru.

Kontrolní otázky a odpovědi

📊 Časová a paměťová složitost

Asymptotická notace

• O(f(n)) – horní mez (worst case nebo průměr): existují c > 0 a n₀ takové, že pro všechna n ≥ n₀ platí T(n) ≤ c·f(n). „Algoritmus roste nejvýše jako f(n)."
• Ω(f(n)) – dolní mez: T(n) ≥ c·f(n). „Algoritmus roste alespoň jako f(n)."
• Θ(f(n)) – těsný odhad (platí O i Ω): algoritmus roste přesně jako f(n).

V praxi nejčastěji pracujeme s nejhorším případem (worst case) a O notací. Multiplikativní konstanty a nižší členy zanedbáváme – zajímá nás pouze trend pro velká n.

Paměťová složitost

Počet paměťových buněk použitých algoritmem v závislosti na n. Algoritmus in-place potřebuje O(1) extra paměti (jen vstupní pole + pár proměnných). Out-of-place vyžaduje pomocnou paměť (např. MergeSort vyžaduje O(n)).

🔍 Vyhledávání v poli

Sekvenční (lineární) vyhledávání

Procházíme pole od začátku a porovnáváme každý prvek s hledanou hodnotou. Funguje pro neseřazené i seřazené pole.

• Nejlepší případ: hledaný prvek je první → O(1).
• Nejhorší případ: prvek není nebo je poslední → O(n).
• Průměrný případ: O(n/2) = O(n).

Binární vyhledávání (půlení intervalu)

• Každé porovnání eliminuje polovinu zbývajícího prostoru.
• Složitost: O(log n) – po log₂ n krocích je interval prázdný.

Dolní mez vyhledávání

Věta: Každý deterministický algoritmus v porovnávacím modelu RAM pro vyhledávání v n-prvkové seřazené posloupnosti musí v nejhorším případě provést Ω(log n) porovnání. Binární vyhledávání je tedy asymptoticky optimální.

Důkaz idea: Algoritmus prochází stromem rozhodnutí. Ten musí mít alespoň n listů (odpovídají n různým pozicím + „nenalezeno"). Strom s k listy má výšku ≥ log₂ k. Tedy min. log₂ n porovnání.

🔃 Kvadratické řadící algoritmy

BubbleSort (řazení zaměňováním)

Princip: Opakovaně procházíme pole a zaměňujeme sousední prvky ve špatném pořadí. Po každém průchodu se „probublá" největší prvek na konec. Zastavíme se, pokud v průchodu nedošlo k žádné záměně (optimalizace).

• Složitost: O(n²) v nejhorším i průměrném případě.
• Nejlepší případ (seřazené pole): O(n) – jeden průchod bez záměny.
• In-place, stabilní, datově citlivý.

SelectSort (řazení výběrem)

Princip: Opakovaně hledáme minimum ve zbytku pole a přesuneme ho na správnou pozici zaměnou s prvním prvkem zbytku. Po i průchodech je prvních i prvků seřazeno.

• Složitost: vždy O(n²) – počet porovnání je vždy n(n-1)/2.
• Provádí méně záměn než BubbleSort (max. n-1 záměn).
• In-place, nestabilní, datově necitlivý.

InsertSort (řazení vkládáním)

Princip: Udržujeme seřazenou část pole (zpočátku jen první prvek). Vždy vezmeme první prvek z neseřazené části a vložíme ho na správnou pozici do seřazené části (posunutím větších prvků doprava).

• Složitost: O(n²) nejhorší, O(n) nejlepší (téměř seřazené pole).
• In-place, stabilní, datově citlivý.
• Efektivní pro malé nebo téměř seřazené vstupy.

⚡ Efektivní řadící algoritmy – O(n log n)

MergeSort (řazení slučováním)

Princip (Rozděl a panuj):

1. Rozdělíme pole na dvě poloviny.
2. Rekurzivně seřadíme každou polovinu.
3. Obě seřazené poloviny slijeme (merge) do jednoho seřazeného pole.

Slučování (merge): Prochází obě seřazené posloupnosti a vybírá vždy menší prvek. Složitost: O(m+n).

Rekurentní rovnice: T(n) = 2·T(n/2) + cn. Po rozvinutí: T(n) = Θ(n log n).

• Složitost: Θ(n log n) v každém případě.
• Paměťová složitost: O(n) – potřebuje pomocné pole.
• Stabilní. Vhodný pro sekvenční přístup (external sorting).

QuickSort (rychlé řazení)

Princip:

1. Vybereme pivot (ideálně medián).
2. Rozdělíme pole na část s prvky ≤ pivot a část s prvky > pivot.
3. Rekurzivně seřadíme obě části.

Výběr pivotu: Kritický krok. Špatný pivot (min/max) degraduje na O(n²). Randomizovaný výběr nebo medián ze 3 prvků dává O(n log n) průměrně.

• Složitost: O(n log n) průměrně, O(n²) nejhorší případ.
• Empiricky nejrychlejší – malá multiplikativní konstanta.
• In-place (bez pomocného pole), nestabilní.
• Střední hodnota počtu porovnání pro náhodný pivot: 2n ln n ≈ 1,39·n·log₂ n.

HeapSort (řazení haldou)

Princip:

1. Z pole vytvoříme binární haldu (HeapBuild) v čase O(n).
2. n-krát odstraníme minimum (HeapExtractMin) a zapíšeme do výstupního pole, každé v O(log n).

• Složitost: Θ(n log n) vždy.
• In-place (při vhodné implementaci), nestabilní.

📉 Dolní mez složitosti řazení

Důkaz idea: Existuje n! permutací vstupní posloupnosti. Každá permutace musí být seřazena jinak. Algoritmus si lze představit jako strom rozhodnutí s n! listy. Výška takového stromu je ≥ log₂(n!) ≈ n·log₂ n − n/ln 2 (Stirlingova formule). Tedy počet porovnání ≥ log₂(n!) = Ω(n log n).

Důsledky

• Žádný porovnávací algoritmus nemůže seřadit n čísel rychleji než Ω(n log n) v nejhorším případě.
• Každá implementace operace ExtractMin z haldy musí trvat Ω(log n) – jinak bychom mohli seřadit v o(n log n).

📈 Řazení v lineárním čase

Překonáváme dolní mez tím, že nevyužíváme porovnávací model – tyto algoritmy využívají konkrétní vlastnosti vstupních hodnot.

CountingSort (řazení počítáním)

Předpoklad: n celých čísel z množiny {1, …, r}.

1. Vytvoříme histogram – pole četností délky r.
2. Prefixovým součtem zjistíme, kde má každá hodnota začít v seřazeném poli.
3. Projdeme vstup a každý prvek umístíme na správnou pozici.

Složitost: Θ(n + r). Pro r = O(n) je to lineární. Algoritmus je stabilní, out-of-place, datově necitlivý.

RadixSort (řazení podle číslic)

Předpoklad: k-ciferná čísla v soustavě r (tj. z {0, …, r-1}).

Řadíme podle číslic od nejméně významné k nejvýznamnější, vždy pomocí stabilního CountingSort.

Složitost: Θ(k · (n + r)). Pro pevné k a r jde o lineární složitost.

Proč to funguje? Stabilita CountingSort zaručuje, že prvky se stejnou číslicí na aktuální pozici zachovají pořadí z předchozích průchodů (správnost lexikografického řazení).

📋 Shrnutí okruhu 2

• Složitost algoritmu = trend počtu operací v závislosti na velikosti vstupu; O, Ω, Θ notace.
• Binární vyhledávání: O(log n), optimální pro seřazené pole.
• Kvadratické algoritmy: BubbleSort, SelectSort, InsertSort – všechny O(n²) nejhorší případ.
• Efektivní algoritmy: MergeSort (Θ(n log n), stab.), QuickSort (O(n log n) průměr, nestab.), HeapSort (Θ(n log n), nestab.).
• Dolní mez porovnávacího řazení: Ω(n log n) – nedá se překonat v porovnávacím modelu.
• Lineární řazení (CountingSort, RadixSort) – pracuje s konkrétními hodnotami, ne porovnáváním.

Kontrolní otázky a odpovědi

🔁 Rekurze – principy

Podmínky správné rekurze

1. Base case (triviální případ): Existuje nejmenší instance problému, která se řeší přímo (bez dalšího rekurzivního volání). Rekurze zde končí.
2. Rekurzivní krok: Každé rekurzivní volání řeší menší (jednodušší) instanci původního problému.

Jak funguje rekurze v paměti?

Každé volání funkce vytvoří nový rámec (frame) na zásobníku: lokální proměnné, hodnoty parametrů, návratová adresa. Po návratu funkce se rámec odstraní. Příliš hluboká rekurze = přetečení zásobníku (stack overflow).

Klasické příklady

• Faktoriál: n! = n · (n-1)!, base case: 0! = 1. Rekurze i iterace jsou přirozené.
• Fibonacci: F(n) = F(n-1) + F(n-2), base: F(1) = F(2) = 1. Naivní rekurze je exponenciální – stejné podproblémy se řeší mnohokrát.
• Hanojské věže: Přesun n disků z kolíku A na B přes C = přesun n-1 disků A→C, pak disk A→B, pak n-1 disků C→B. T(n) = 2T(n-1) + 1 → T(n) = 2ⁿ − 1 pohybů.
• GCD (Eukleidův algoritmus): gcd(x, y) = gcd(y, x mod y), base: gcd(x, 0) = x. Logaritmická složitost.

🔄 Rekurze vs. iterace

Rekurze – výhody a nevýhody

• ✅ Kód odpovídá matematické definici – krátký, srozumitelný.
• ✅ Přirozená pro rekurzivní datové struktury (stromy, grafy).
• ❌ Overhead: každé volání vytvoří rámec na zásobníku (čas i paměť).
• ❌ Naivní rekurze může řešit stejný podproblém exponenciálně mnohokrát (Fibonacci).
• ❌ Nebezpečí stack overflow při velké hloubce.

Iterace – výhody a nevýhody

• ✅ Bez overhead zásobníku – rychlejší pro jednoduché případy.
• ✅ Žádné nebezpečí stack overflow.
• ❌ Složitější zápis pro přirozeně rekurzivní problémy.
• ❌ Musíme explicitně udržovat stav (iterativní DFS potřebuje vlastní zásobník).

Fibonacci: rekurze vs. iterace

Naivní rekurzivní Fibonacci má exponenciální složitost Θ(Φⁿ) ≈ Θ(1,618ⁿ), protože F(n-2) se počítá znovu pro každé F(n). Iterativní verze počítá „zdola nahoru" (F(2), F(3), …) v O(n).

// Iterativní – O(n)
int fibonacci(int n) {
  int a = 1, b = 1;
  for (int i = 2; i < n; i++) {
    int tmp = a + b; a = b; b = tmp;
  }
  return b;
}

⚔️ Metoda Rozděl a panuj (Divide and Conquer)

Struktura a analýza složitosti

Typická rekurentní rovnice: T(n) = a · T(n/b) + f(n), kde a je počet podproblémů, n/b je jejich velikost, f(n) je cena dělení a kombinování.

Příklady algoritmů Rozděl a panuj

MergeSort: T(n) = 2·T(n/2) + cn → Θ(n log n). Rozdělení: O(1), slévání: O(n).

QuickSort: T(n) = T(k) + T(n-k-1) + O(n), kde k závisí na pivotu. Pro balanced pivot: T(n) = Θ(n log n). Pro vždy nejhorší pivot: T(n) = Θ(n²).

Karacubovo násobení čísel: Naivní násobení n-ciferných čísel vyžaduje 4 násobení čísel poloviční délky → T(n) = 4T(n/2) + O(n) → O(n²). Karacuba: místo 4 jen 3 násobení díky algebraickému triku: (xU + xL)(yU + yL) − xU·yU − xL·yL. T(n) = 3T(n/2) + O(n) → Θ(n^{log₂3}) ≈ Θ(n^{1,59}).

QuickSelect (výběr k-tého nejmenšího prvku): Rozdělíme jako v QuickSort, ale rekurzivně jdeme jen do jedné části. S náhodným pivotem: střední hodnota O(n). Vhodným výběrem „skoromediánu" lze dosáhnout deterministicky O(n).

🗃️ Dynamické programování (DP)

Podmínky pro aplikaci DP

1. Optimální podstruktura: Optimální řešení problému se skládá z optimálních řešení podproblémů.
2. Překrývající se podproblémy: Rekurzivní rozklad vede na opakované řešení stejných podproblémů (např. Fibonacci: F(n-2) se počítá pro F(n) i F(n-1)).

Dva přístupy DP

• Top-down s memoizací: Rekurzivní algoritmus + tabulka výsledků. Před výpočtem zkontrolujeme, zda výsledek není v tabulce. Pokud ano, vrátíme ho přímo.
• Bottom-up (iterativní): Vyplňujeme tabulku od nejmenších podproblémů k největším. Nevyžaduje rekurzi, rychlejší v praxi.

Příklad 1: Fibonacciho čísla

Naivní rekurze: Θ(Φⁿ). S memoizací nebo iterativně: O(n) – každé F(i) se počítá jen jednou.

// Bottom-up DP
T[1] = 1; T[2] = 1;
for k = 3 to n:
    T[k] = T[k-1] + T[k-2]
return T[n]

Příklad 2: Nejdelší rostoucí podposloupnost (NRP)

Hledáme nejdelší rostoucí podposloupnost v posloupnosti a₁, …, aₙ.

DP definice: T[i] = délka nejdelší rostoucí podposloupnosti začínající prvkem aᵢ.

T[i] = 1 + max{T[j] : j > i, aⱼ > aᵢ} nebo 1 pokud takové j neexistuje.

Vyplňujeme od konce (bottom-up). Složitost: O(n²).

Příklad 3: Editační vzdálenost řetězců

Minimální počet operací (záměna, vložení, smazání znaku), který transformuje řetězec x na y.

DP stav: M[i,j] = editační vzdálenost suffixu x[i…m] a y[j…n].

Rekurence: M[i,j] = min(záměna, smazání xᵢ, vložení yⱼ). Složitost: O(m·n) čas i paměť.

Praktické využití: spell-checking, diff, bioinformatika (porovnání DNA sekvencí).

Obecný postup při použití DP

1. Formulujeme řešení rekurzivně (popíšeme podproblémy).
2. Identifikujeme opakované podproblémy.
3. Vytvoříme tabulku (pole) pro ukládání výsledků.
4. Vyplníme triviální případy (base cases).
5. Vyplníme tabulku bottom-up nebo přidáme memoizaci k top-down.
6. Načteme výsledek z tabulky.

🧱 Dekompozice problémů a návrh algoritmů

Při návrhu komplexního algoritmu decomponujeme problém na podproblémy, nejdříve na abstraktní úrovni (pseudokód), pak implementujeme pomocí funkcí.

Schéma návrhu (top-down design)

1. Definujeme hlavní problém slovně nebo pseudokódem.
2. Identifikujeme dílčí podproblémy (abstraktní příkazy).
3. Pro každý podproblém navrhneme funkci.
4. Iterujeme, dokud vše není implementovatelné přímočaře.

Kdy použít jakou techniku?

📋 Shrnutí okruhu 3

• Rekurze = funkce volá sebe sama; nutný base case a menší podproblém v rekurzivním kroku.
• Každá rekurze jde přepsat na iteraci; iterace je efektivnější (méně overhead zásobníku), ale méně přirozená pro rekurzivní struktury.
• Rozděl a panuj: disjunktní podproblémy → MergeSort Θ(n log n), QuickSort O(n log n) průměr, Karacuba Θ(n^{1.59}).
• Dynamické programování: překrývající se podproblémy + optimální podstruktura → ukládáme výsledky v tabulce → polynomiální složitost.
• Fibonacci naivně = Θ(Φⁿ), s DP = O(n). NRP = O(n²). Editační vzdálenost = O(m·n).

Kontrolní otázky a odpovědi