Algoritmizace a programování

Úvod

Algoritmus je postup k řešení nějakého problému. Vzniká procesem algoritmizace, který problém zformuluje, analyzuje, navrhne řešení a implementuje ho. Program je konkrétní implementace algoritmu pomocí programovacího jazyka.

Programátorské konstrukce

Proměnná

Proměnná je pojmenované místo v paměti, ve kterém jsou uložena nějaká data. Je to základní stavební kámen každého programu – umožňuje uchovávat a později číst hodnoty, se kterými program pracuje.

final double PI = 3.14159;
final int MAX_POCET = 100;

Větvení programu

Větvení umožňuje programu rozhodovat se – vykonat různé bloky kódu podle toho, zda je splněna určitá podmínka.

Podmíněné větvení (if-else)

Základní mechanismus – program vyhodnotí podmínku (výraz typu boolean) a podle výsledku se vydá jednou ze dvou (nebo více) větví. V Javě jsou k tomu vyhrazena klíčová slova if, else if a else.

// Jednoduché větvení
if (vek >= 18) {
    System.out.println("Jsi plnoletý.");
}

// Úplné větvení s více cestami
if (teplota > 30) {
    System.out.println("Vedro.");
} else if (teplota > 20) {
    System.out.println("Příjemně.");
} else if (teplota > 0) {
    System.out.println("Chladno.");
} else {
    System.out.println("Mráz.");
}

Switch

Konstrukce switch slouží k větvení podle hodnoty jedné proměnné (typy int, char, String, enum). Je přehlednější než řetězec if-else if při porovnávání proti mnoha konkrétním hodnotám.

switch (denVTydnu) {
    case 1:
        System.out.println("Pondělí");
        break;
    case 2:
        System.out.println("Úterý");
        break;
    case 6:
    case 7:
        System.out.println("Víkend!");
        break;
    default:
        System.out.println("Neplatný den");
}

Ternární operátor

Ternární operátor ? : je zkrácený zápis pro jednoduché if-else, který vrací hodnotu. Hodí se pro přiřazení nebo vložení podmínky dovnitř výrazu.

// Místo:
String status;
if (vek >= 18) {
    status = "plnoletý";
} else {
    status = "neplnoletý";
}

// Lze napsat:
String status = (vek >= 18) ? "plnoletý" : "neplnoletý";

Cykly

Cykly umožňují opakované vykonávání bloku kódu, dokud platí určitá podmínka. Jsou základním nástrojem pro zpracování kolekcí, iterativní výpočty a řízení toku programu.

For-loop

Cyklus s pevným počtem iterací. Skládá se ze tří částí: inicializace, podmínka pokračování a krok po každé iteraci.

// for (inicializace; podmínka; krok)
for (int i = 0; i < 10; i++) {
    System.out.println("Iterace č. " + i);
}

While-loop

Cyklus, který se opakuje, dokud je podmínka pravdivá. Podmínka se testuje před každou iterací – pokud není splněna hned na začátku, tělo se neprovede ani jednou.

int i = 0;
while (i < 10) {
    System.out.println("Iterace č. " + i);
    i++;
}

Do-while-loop

Obdoba while, ale podmínka se testuje až po provedení těla. Tělo se tedy provede vždy alespoň jednou.

int i = 0;
do {
    System.out.println("Iterace č. " + i);
    i++;
} while (i < 10);

Členění programu

S rostoucí složitostí programu je nutné kód organizovat do logických celků – funkcí, tříd, balíků. To zlepšuje čitelnost, znovupoužitelnost a udržovatelnost.

Funkce

Funkce je pojmenovaný blok kódu, který přijímá parametry, provádí výpočet a vrací výsledek. Základní jednotka dekompozice v procedurálním programování.

// Funkce, která sečte dvě čísla a vrátí výsledek
static int secti(int a, int b) {
    return a + b;
}

Procedury

Procedura je speciální případ funkce, která nevrací žádnou hodnotu (v Javě void). Používá se, když potřebujeme vykonat akci, ale neočekáváme výsledek – např. vypsání do konzole, zápis do souboru.

// Procedura – nic nevrací, jen provede akci
static void pozdrav(String jmeno) {
    System.out.println("Ahoj, " + jmeno + "!");
}

Metody

Metoda je označení pro funkci nebo proceduru, která patří k nějaké třídě nebo objektu. V objektovém programování jsou všechny funkce a procedury metodami.

public class Kalkulacka {
    // Metoda – funkce uvnitř třídy
    public int secti(int a, int b) {
        return a + b;
    }
}

Třída

Třída je struktura, která definuje, jaké budou mít její instance data (atributy) a chování (metody). Je to šablona, podle které se vytvářejí objekty.

V Javě je na třídy vyhrazené klíčové slovo class. Každá veřejná třída je definována v odděleném souboru, jehož název se shoduje s názvem třídy. Každý program musí mít alespoň jednu třídu, a alespoň jedna musí mít definovaný vstupní bod programu – metodu main:

public class MojeTrida {
    // Vstupní bod programu
    public static void main(String[] args) {
        System.out.println("Program spuštěn!");
    }
}

Objekt

Objekt (instance třídy) je konkrétní exemplář vytvořený podle šablony (třídy). Každý objekt má vlastní kopii atributů definovaných třídou.

Kalkulacka k = new Kalkulacka();  // vytvoření objektu (instance)
int vysledek = k.secti(5, 3);      // volání metody na objektu

Balíky

Balíky (packages) slouží k organizaci většího množství tříd do logických skupin – podobně jako složky v souborovém systému. Zabranují kolizím jmen a pomáhají s modularitou.

package cz.example.aplikace.util;

public class PomocnaTrida {
    // ...
}

import java.util.ArrayList;
import java.util.List;

Programovací paradigmata

Strukturované programování

Strukturované programování je paradigma, které odmítá nekontrolované skoky (goto) a staví na třech základních řídících strukturách:

• Sekvence – příkazy se vykonávají jeden po druhém.
• Větvení – if, else, switch – rozhodování na základě podmínek.
• Cykly – for, while, do-while – opakování bloků kódu.

Program se rozkládá na funkce a procedury, které volají jedna druhou. Hlavní myšlenkou je, že každý blok kódu má jeden vstupní a jeden výstupní bod – to usnadňuje analýzu, ladění a testování.

Objektové programování

Objektově orientované paradigma je způsob nahlížení na softwarový systém jako na kolekci autonomních, vzájemně komunikujících entit (objektů), namísto sekvence příkazů nebo procedur. Tento přístup vychází z přirozeného lidského vnímání reality, kdy složité systémy dekomponujeme na menší, uchopitelné části s jasně definovanou zodpovědností.

Funkcionální programování

Funkcionální programování je deklarativní programovací paradigma, které staví na matematické teorii funkcí (konkrétně na \(\lambda\)-kalkulu). Na rozdíl od imperativního programování, kde program popisuje jak se má výpočet provést pomocí změn stavů a sekvencí příkazů, funkcionální programování popisuje co je výsledkem výpočtu pomocí skládání výrazů a funkcí.

Složitost algoritmu

Složitost je charakteristika algoritmu, která měří časové nebo paměťové nároky algoritmu v závislosti na velikosti vstupních dat. Jedná se o způsob kvantifikace, jak efektivně algoritmus pracuje s různě velkými vstupy.

Asymptotická složitost

Asymptotická složitost je charakteristika algoritmu vyjádřená jako rostoucí funkce. Říká nám, jak rychle se zvyšuje počet potřebných operací se zvětšujícím se množstvím vstupních dat.

Amortizovaná složitost

Amortizovaná složitost je časová složitost, která je průměrem nejhorších případů v řadě. Amortizace je proces, kdy nejhorší případ asymptotické složitosti ztrácí na důležitosti, protože nastává zřídka v sadě dalších případů.

Vyhledávání

Vyhledávací algoritmy slouží k nalezení prvku s daným klíčem v prohledávaném prostoru (pole, seznam, strom). Efektivita vyhledávání zásadně závisí na tom, zda je prostor seřazený.

Lineární vyhledávání

Lineární vyhledávání je nejjednodušší vyhledávací algoritmus – prochází prohledávaný prostor prvek po prvku, dokud nenalezne hledaný klíč nebo nedojde na konec.

• Složitost: \(O(n)\) v nejhorším i průměrném případě.
• Výhody: Funguje na neseřazených datech, triviální implementace.
• Nevýhody: Pomalé pro velká data.

Binární vyhledávání

Binární vyhledávání používá metodu půlení intervalu k nalezení hledaného klíče. V každém kroku porovná hledanou hodnotu s prostředním prvkem a podle výsledku zahodí polovinu prohledávaného prostoru.

• Složitost: \(O(\log n)\).
• Princip: Porovnej prostřední prvek, pokud je menší než hledaný → hledej v pravé polovině, pokud větší → hledej v levé polovině, pokud rovný → nalezeno.

Interpolační vyhledávání

Interpolační vyhledávání je varianta binárního vyhledávání, která se snaží simulovat lidské chování – místo půlení intervalu odhaduje pozici hledaného prvku na základě hodnot. Když hledáme "K" ve slovníku, neotevřeme ho uprostřed, ale někde ke konci.

Odhad pozice se počítá podle vzorce:

• Složitost: \(O(\log \log n)\) pro rovnoměrně rozložená data, \(O(n)\) v nejhorším případě (např. exponenciálně rostoucí data).
• Výhody: Rychlejší než binární vyhledávání na rovnoměrně rozložených datech.

Binární vyhledávací strom

Binární vyhledávací strom (BST) je datová struktura, ve které pro každý uzel platí:

• Všechny uzly v levém podstromu mají hodnotu menší než kořen.
• Všechny uzly v pravém podstromu mají hodnotu větší než kořen.

• Složitost: \(O(h)\), kde \(h\) je výška stromu. V nejhorším případě (degenerovaný strom) \(O(n)\).

AVL Stromy

AVL strom je výškově vyvážený binární vyhledávací strom, který každému uzlu přiřazuje faktor vyváženosti:

kde \(h_L\) je výška levého podstromu a \(h_R\) výška pravého podstromu. Pro všechny uzly vyváženého AVL stromu platí, že \(\text{bal}(u) \in \{-1, 0, 1\}\).

• Složitost: Garantovaná výška \(O(\log n)\), operace vkládání, mazání i hledání v \(O(\log n)\).

Hledání do hloubky (DFS)

Depth-First Search (DFS) prochází graf nebo strom tak, že jde co nejhlouběji, dokud nenarazí na konec větve, a pak se vrací (backtrackuje) a zkouší další cesty.

• Implementace: Rekurzivně (přirozené) nebo iterativně pomocí zásobníku.
• Složitost: \(O(V + E)\) kde \(V\) je počet vrcholů a \(E\) počet hran.
• Použití: Detekce cyklů, topologické řazení, řešení bludišť, generování permutací.

Hledání do šířky (BFS)

Breadth-First Search (BFS) prochází graf po vrstvách – nejdříve navštíví všechny uzly ve vzdálenosti 1 od startu, pak vzdálenost 2, a tak dál. Používá frontu (FIFO).

• Implementace: Iterativně pomocí fronty.
• Složitost: \(O(V + E)\).
• Použití: Hledání nejkratší cesty v neohodnoceném grafu, procházení sociálních sítí podle stupně vzdálenosti, web crawling.

Prohledávání řetězců

Prohledávání řetězců je úloha najít všechny výskyty hledaného vzoru v delším textu. Naivní přístup testuje každou pozici – chytřejší algoritmy využívají předzpracování vzoru nebo textu k přeskočení zbytečných porovnání.

Přirozené prohledávání

Nejjednodušší algoritmus – pro každou pozici v textu testuje, zda na ní nezačíná hledaný vzor. Porovnává znak po znaku, dokud nenarazí na neshodu nebo nedojde na konec vzoru.

• Složitost: \(O(n \cdot m)\) v nejhorším případě, kde \(n\) je délka textu a \(m\) délka vzoru.
• Výhody: Triviální implementace, žádné předzpracování.
• Nevýhody: Pomalé pro velké texty a vzory s opakujícími se prefixy.

Knuth-Morris-Pratt (KMP)

KMP algoritmus staví na přirozeném prohledávání, ale přidává chytré řízení posunu. Když dojde k neshodě, KMP neposune vzor jen o 1, ale o tolik pozic, kolik umožňuje struktura samotného vzoru – využívá toho, že část vzoru již byla porovnána úspěšně.

Klíčem je chybová funkce (failure function) \(F(k)\), která pro každou pozici \(k\) ve vzoru udává délku nejdelšího prefixu vzoru \(P[0:k]\), který je zároveň jeho suffixem. Tato funkce se spočítá předem (preprocessing).

• Složitost: \(O(n + m)\) – lineární v délce textu i vzoru.
• Výhody: Žádné couvání v textu, lineární složitost.

Boyer-Moore

Boyer-Moore je algoritmus, který stojí na myšlence zrcadlového hledání – porovnává vzor od konce, nikoliv od začátku. Díky tomu může při neshodě poskočit o více pozic najednou.

Posuny se určují předem pomocí mapy abecedy – pro každý znak si zapamatujeme index jeho posledního výskytu ve vzoru (nebo \(-1\), pokud se nevyskytuje).

• Složitost: \(O(n \cdot m)\) v nejhorším, \(O(n/m)\) v nejlepším případě. V praxi typicky sublineární – rychlejší než KMP.
• Výhody: Na dlouhých vzorech a velkých abecedách extrémně rychlý.

Rabin-Karp

Rabin-Karp algoritmus porovnává hash vzoru a jednotlivých podřetězců textu. Místo porovnávání znak po znaku porovná čísla (hashe). Pokud se hashe shodují, teprve pak se ověří znak po znaku (kvůli možným kolizím hashovací funkce).

Klíčem je rolling hash – hashovací funkce, která umožňuje z hashe jednoho podřetězce rychle spočítat hash následujícího posunutého podřetězce (odečtením prvního znaku a přičtením nového), typicky v \(O(1)\).

• Složitost: \(O(n + m)\) v průměru, \(O(n \cdot m)\) v nejhorším (samé kolize).
• Výhody: Snadné rozšíření na hledání více vzorů najednou, detekce plagiátů.

Třídění

Třídící algoritmy uspořádávají prvky posloupnosti podle zvoleného klíče. Liší se rychlostí, paměťovou náročností, stabilitou a chováním na různých typech vstupních dat.

Vlastnosti třídících algoritmů

Stabilita

Stabilita třídícího algoritmu popisuje, jak se zachová při řazení prvků se stejnou hodnotou či klíčem.

Přirozenost

Přirozenost třídícího algoritmu nám říká, jak se algoritmus chová na již (alespoň částečně) uspořádaných datech.

Bubblesort

Bubblesort je vnitřní, stabilní a přirozený algoritmus, který probublává větší prvky na konec posloupnosti.

• Složitost: \(O(n^2)\) v nejhorším i průměrném, \(O(n)\) na seřazených datech (díky přirozenosti).
• Výhody: Jednoduchý, detekuje už seřazená data.
• Nevýhody: Pomalý – nepoužitelný pro větší data.

Shakersort

Shakersort (též Cocktail sort) je vylepšená varianta Bubblesortu, která řadí posloupnost v obou směrech. Nejdříve probublá největší prvky na konec (dopředný průchod), a následně probublá nejmenší prvky na začátek (zpětný průchod).

Tímto se dá předejít problému želv a zajíců – malé prvky na konci pole (želvy) se v klasickém Bubblesortu posouvají jen o jednu pozici za průchod, zatímco Shakersort je posune rychleji při zpětném průchodu.

Combsort

Combsort je vylepšená varianta Bubblesortu, která používá snižující se rozestup (gap) mezi porovnávanými prvky. Začíná s velkým rozestupem (typicky délka pole), který se postupně zmenšuje, až dosáhne \(1\) (poslední průchod je klasický Bubblesort).

• Složitost: \(O(n^2)\) v nejhorším, \(O(n \log n)\) v průměru.

Selectsort

Selectsort je vnitřní, nestabilní a nepřirozený algoritmus, který pracuje na bázi hledání nejmenšího prvku.

• Složitost: \(O(n^2)\) vždy (i na seřazených datech – nepřirozený).
• Výhody: Jednoduchý, minimální počet prohození (\(n-1\)).
• Nevýhody: Pomalý, nestabilní.

Insertsort

Insertsort je vnitřní, stabilní a přirozený algoritmus, který imituje přirozené řazení karet člověkem.

• Složitost: \(O(n^2)\) v nejhorším, \(O(n)\) na seřazených datech.
• Výhody: Rychlý na malých a téměř seřazených datech, stabilní, online (může třídit data, jak přicházejí).
• Použití: Součást hybridních algoritmů (např. Timsort – v Javě a Pythonu), kde se používá pro malé podposloupnosti.

Mergesort

Mergesort je třídící algoritmus typu Divide and Conquer (rozděl a panuj). Je vnitřní, stabilní a přirozený.

• Složitost: \(O(n \log n)\) vždy (nejhorší, průměrný i nejlepší případ).
• Výhody: Garantovaná složitost \(O(n \log n)\), stabilní, vhodný pro spojové seznamy.
• Nevýhody: Vyžaduje pomocnou paměť \(O(n)\) (není in-place).

Quicksort

Quicksort je třídící algoritmus typu Divide and Conquer. Je vnitřní, nestabilní a nepřirozený, ovšem v praxi je nejrychlejší ze všech obecných třídících algoritmů.

• Složitost: \(O(n \log n)\) v průměru, \(O(n^2)\) v nejhorším (při špatné volbě pivotu – např. vždy nejmenší/největší prvek).
• Výhody: Extrémně rychlý v praxi, in-place (nepotřebuje pomocnou paměť).
• Nevýhody: Nestabilní, \(O(n^2)\) při nevhodné volbě pivotu (řeší se randomizací nebo median-of-three).

Heapsort

Heapsort je třídící algoritmus, který používá datovou strukturu halda (heap).

• Složitost: \(O(n \log n)\) vždy – garantovaná.
• Výhody: In-place, garantovaná složitost, nepotřebuje rekurzi.
• Nevýhody: Nestabilní, v praxi pomalejší než Quicksort (horší lokalita cache).

Bogosort

Bogosort je třídící algoritmus, který ke setřízení dat spoléhá na opakování náhodného rozmístění prvků, dokud se netrefí do seřazené permutace.

function bogosort(array) {
    while (!isOrdered(array)) {
        shuffle(array);
    }
}

• Složitost: \(O(\infty)\) v nejhorším, \(O(n \cdot n!)\) v průměru (počet permutací krát kontrola seřazenosti).

Rekurze

Rekurze je princip, který umožňuje funkci volat samu sebe. Tento přístup je často elegantní a intuitivní, zejména pokud je problém definován rekurzivně. Funkce může volat sebe buď přímo (přímá rekurze), nebo nepřímo přes jinou funkci (nepřímá rekurze).

static int faktorial(int n) {
    if (n <= 1) return 1;              // báze rekurze
    return n * faktorial(n - 1);       // rekurzivní krok
}

Rekurze může být náročná na paměť, protože každé volání funkce se ukládá na zásobník. Pokud není správně implementována podmínka ukončení, může rekurze pokračovat nekonečně, což vede k vyčerpání zásobníku (stack overflow).

Backtracking

Backtracking je metoda pro vytváření algoritmů, která hrubou silou prohledává prostor všech možných řešení, ale inteligentně se vrací (backtrackuje) ve chvíli, kdy narazí na slepou větev – tedy na částečné řešení, které už nemůže vést k platnému výsledku.

Pomocí rekurze vytváří strom, kde každá větev reprezentuje rozhodnutí o jedné proměnné a každá úroveň reprezentuje částečné řešení. Backtracking lze použít pro nalezení:

• Libovolného řešení – stačí nám cokoliv, co splňuje podmínky.
• Nejlepšího řešení – hledáme optimum podle nějakého kritéria.
• Všech možných řešení – potřebujeme kompletní výčet.