Informatika

1.1Bit a množství informace

Bit je nejmenší jednotka informace: odpověď na jednu otázku typu ano/ne, kde jsou obě odpovědi stejně pravděpodobné. Slovo vzniklo zkrácením binary digit, dvojková číslice; v tisku ho poprvé použil Claude Shannon v roce 1948 a připsal ho kolegovi Johnu Tukeymu.bit, binary digit

Řada \(n\) bitů může nabýt \(2^{n}\) různých hodnot. Obráceně: abychom rozlišili \(N\) stejně pravděpodobných možností, potřebujeme \(\log_2 N\) bitů, v praxi zaokrouhleno nahoru.

Entropie (rozšíření)

Když možnosti nejsou stejně pravděpodobné, nese zpráva v průměru méně informace. Shannon (1948) ji měří entropií: \(H = -\sum_i p_i \log_2 p_i\) bitů na zprávu. Mince, která padá v 90 % případů na líc, má entropii \(H = -(0{,}9\log_2 0{,}9 + 0{,}1\log_2 0{,}1) = 0{,}469\) bitu. Proto jde dobře komprimovat text: písmena v něm nejsou stejně častá a dají se kódovat úsporněji. Entropie je dolní mez průměrné délky bezeztrátového kódu.entropy, source coding

1.2Poziční číselné soustavy

V desítkové soustavě znamená zápis 2026 součet \(2\cdot10^{3} + 0\cdot10^{2} + 2\cdot10^{1} + 6\cdot10^{0}\). Hodnota číslice závisí na její pozici. Stejně funguje každá poziční soustava se základem \(z\): číslice \(c_k\) na \(k\)-té pozici zprava (počítáno od nuly) má váhu \(z^{k}\).positional numeral system, radix

Dvojková (binární) soustava má základ 2 a číslice 0 a 1. Šestnáctková (hexadecimální) má základ 16 a číslice 0–9 a A–F. Šestnáctková soustava je zkratka pro dvojkovou: jedna šestnáctková číslice odpovídá přesně čtyřem bitům, protože \(16 = 2^{4}\). Bajt se tak zapíše dvěma znaky.binary, hexadecimal

Převod z desítkové soustavy

Číslo opakovaně dělíme základem a zapisujeme zbytky. Zbytky čtené odspodu (od posledního k prvnímu) dávají zápis v nové soustavě. Funguje to proto, že zbytek po dělení dvěma je právě nejnižší bit a podíl je číslo posunuté o jedno místo doprava.

1.3Bajty a předpony

Bajt (B) je skupina 8 bitů a nejmenší jednotka, kterou běžné počítače adresují v paměti. Pro větší množství se používají předpony. Desítkové předpony soustavy SI znamenají mocniny tisíce: 1 kB = 1 000 B, 1 MB = \(10^{6}\) B, 1 GB = \(10^{9}\) B, 1 TB = \(10^{12}\) B. Protože paměti rostou po mocninách dvojky, zavedla norma IEC dvojkové předpony: 1 KiB (kibibajt) = 1 024 B, 1 MiB = \(2^{20}\) B, 1 GiB = \(2^{30}\) B.byte, binary prefixes (KiB, MiB, GiB)

1.4Celá čísla se znaménkem a desetinná čísla

Záporná čísla ukládají počítače ve dvojkovém doplňku: nejvyšší bit má zápornou váhu. U bajtu je to \(-128\) místo \(+128\), takže 8 bitů pokryje čísla od \(-128\) do \(127\). Opačné číslo se získá převrácením všech bitů a přičtením jedničky. Výhoda: sčítání funguje stejně pro kladná i záporná čísla, procesor nepotřebuje zvláštní obvod na odčítání.two's complement

Když výsledek nevejde do daného počtu bitů, nastane přetečení: v bajtu se znaménkem dá \(127 + 1\) výsledek \(-128\). Programovací jazyky se k tomu chovají různě – některé tiše „přetočí“ hodnotu, jiné ohlásí chybu, Python má celá čísla libovolné délky.integer overflow

Desetinná čísla se ukládají v plovoucí řádové čárce podle normy IEEE 754: znaménko, exponent a mantisa, podobně jako vědecký zápis \(6{,}022\cdot10^{23}\), jen se základem 2. Nejběžnější formát má 64 bitů (1 znaménko, 11 exponent, 52 mantisa) a přesnost zhruba 15–17 platných desítkových číslic.floating point, IEEE 754 double precision

1.5Text: ASCII, Unicode a UTF-8

Text je posloupnost znaků a každý znak má domluvené číslo. ASCII (americká norma z roku 1963) používá 7 bitů, tedy 128 kódů: 33 řídicích (konec řádku, tabulátor…) a 95 tisknutelných znaků včetně mezery. Písmeno A má kód 65, a má 97, číslice 0 kód 48. Velké a malé písmeno se liší jediným bitem s hodnotou 32.ASCII, character encoding

Pro češtinu ASCII nestačilo, a tak vznikla desítka vzájemně nekompatibilních osmibitových tabulek; text napsaný v jedné se v druhé zobrazil jako „rozsypaný čaj“. Řešením je Unicode: jediný katalog znaků všech písem. Každý znak má kódový bod zapisovaný U+ a šestnáctkovým číslem, například Č je U+010C, € je U+20AC. Prostor má \(17 \cdot 65\,536 = 1\,114\,112\) kódových bodů (U+0000 až U+10FFFF). Verze 18.0 z 16. 9. 2026 jich obsazuje 172 808.Unicode, code point

Unicode říká, jaké číslo znak má, ne jak ho zapsat do bajtů. To dělá kódování. Na webu převládá UTF-8 (RFC 3629): znaky ASCII zapíše jedním bajtem beze změny, ostatní dvěma až čtyřmi bajty. První bajt vícebajtové sekvence začíná tolika jedničkami, kolik bajtů sekvence má; každý následující bajt začíná 10.UTF-8, variable-length encoding

1.6Obrázek a zvuk

Rastrový obrázek je mřížka bodů (pixelů). Barva každého pixelu se obvykle skládá ze tří složek: červené, zelené a modré (RGB), každá 0–255, tedy 1 bajt. Tři bajty dají \(2^{24} = 16\,777\,216\) barev. Ve webových stránkách se barva píše šestnáctkově: oranžová tohoto průvodce je #EB6834, tedy R = 235, G = 104, B = 52.raster image, pixel, RGB

Zvuk je kmitání tlaku vzduchu. Mikrofon ho převede na spojitý elektrický signál a převodník ho vzorkuje: v pravidelných intervalech změří okamžitou hodnotu a kvantuje ji na nejbližší z konečně mnoha úrovní. Vzorkovací věta (Nyquist, Shannon) říká, že signál obsahující frekvence do \(f_{\max}\) lze z ideálně změřených vzorků přesně obnovit, je-li vzorkovací frekvence větší než \(2f_{\max}\).sampling, quantization, Nyquist–Shannon theorem

1.7Procvičení

2.1Co je algoritmus

Algoritmus je konečný a jednoznačný postup, který ze vstupních údajů v konečném počtu kroků vytvoří výsledek. Slovo pochází ze jména perského matematika al-Chvárizmího (9. století), jehož spis o počítání s indickými číslicemi se v latinském překladu šířil Evropou. Nejstarší algoritmus, který se dodnes běžně používá, popsal Eukleidés v Základech kolem roku 300 př. n. l.algorithm

Česká školní tradice vyjmenovává tyto vlastnosti:

• Elementárnost: skládá se z kroků, které vykonavatel umí provést.
• Determinovanost (jednoznačnost): po každém kroku je jasné, co následuje.
• Konečnost: pro každý přípustný vstup skončí po konečném počtu kroků.
• Rezultativnost: dává výsledek (výstup).
• Hromadnost (obecnost): řeší celou třídu úloh, ne jeden konkrétní případ. Postup „sečti 3 a 5“ není algoritmus sčítání; „sečti čísla \(a\) a \(b\)“ ano.

Knuth v The Art of Computer Programming uvádí pět podobných rysů: konečnost, určitost, vstup, výstup a efektivitu (kroky jsou tak jednoduché, že by je člověk zvládl s tužkou a papírem). Formální definici „postupu“ dal až Turing v roce 1936; k ní se vrátíme v kapitole 11.

2.2Jak algoritmus zapsat

Algoritmus lze popsat slovy, ale přirozený jazyk bývá dvojznačný. Proto se používá pseudokód: strukturovaný zápis podobný programu, který se nedrží syntaxe žádného jazyka a nechává stranou podrobnosti. V tomto průvodci píšeme přiřazení šipkou \(\leftarrow\), bloky odsazením a operaci zbytku po dělení jako mod.pseudocode

funkce NSD(a, b):
    dokud b ≠ 0:
        r ← a mod b          # zbytek po dělení
        a ← b
        b ← r
    vrať a

Druhou možností je vývojový diagram: grafický zápis, ve kterém tvar značky říká, o jaký krok jde. Symboly popisuje norma ISO 5807. Ovál je začátek a konec, obdélník zpracování, kosodélník vstup a výstup, kosočtverec rozhodnutí se dvěma východy.flowchart

2.3Posloupnost, větvení, cyklus

Každý algoritmus lze sestavit ze tří stavebních kamenů: posloupnosti (kroky jdou za sebou), větvení (podle podmínky se pokračuje jednou, nebo druhou cestou) a cyklu (část se opakuje, dokud platí podmínka). Že nic dalšího není potřeba, dokázali Böhm a Jacopini (1966). Na jejich výsledek navázal Dijkstra (1968) výzvou psát programy bez skoků goto; tak vzniklo strukturované programování.sequence, selection, iteration; structured programming

Cykly mají dvě podoby. Cyklus s pevným počtem opakování (opakuj 4, v Pythonu for i in range(4)) zná počet průchodů předem. Cyklus s podmínkou (dokud volno, while) se opakuje, dokud podmínka platí, a počet průchodů závisí na datech. Právě proto úroveň 3 laboratoře nejde vyřešit počítáním kroků: chodby jsou různě dlouhé a program musí reagovat na to, co robot „vidí“.

m ← x[1]
pro i od 2 do n:
    když x[i] > m:
        m ← x[i]
vrať m

2.4Euklidův algoritmus

Největší společný dělitel (NSD) dvou přirozených čísel je největší číslo, které dělí obě. Euklidův algoritmus stojí na pozorování, že \(\mathrm{NSD}(a, b) = \mathrm{NSD}(b, a \bmod b)\): každé číslo, které dělí \(a\) i \(b\), dělí i zbytek \(a - q\,b\), a naopak. Čísla se tak zmenšují, ale jejich NSD zůstává stejný. Když zbytek vyjde 0, je NSD poslední nenulové číslo.greatest common divisor (GCD), Euclidean algorithm

Jak rychlý? Nejhůř se algoritmu daří s dvojicemi po sobě jdoucích Fibonacciho čísel (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…), kde každý podíl vyjde 1 a čísla klesají nejpomaleji. \(\mathrm{NSD}(89, 55)\) potřebuje 9 dělení. Lamé (1844) dokázal, že počet dělení nepřesáhne pětinásobek počtu desítkových číslic menšího čísla; jde o jeden z prvních odhadů složitosti algoritmu v dějinách. Počet kroků tedy roste s počtem číslic, ne s velikostí čísel – to je v řeči kapitoly 6 logaritmická složitost.Lamé's theorem

2.5Správnost a konečnost

Že algoritmus funguje na několika příkladech, nic nedokazuje. Správnost se dokazuje dvěma nástroji. Invariant je tvrzení, které platí před každým průchodem cyklem; z něj a z podmínky ukončení plyne správnost výsledku. Variant (také konvergentní funkce) je nezáporné celé číslo, které se každým průchodem zmenší; protože nemůže klesat donekonečna, cyklus skončí.loop invariant, loop variant, termination

2.6Procvičení

3.1Z čeho se skládá počítač

Téměř všechny dnešní počítače vycházejí z von Neumannovy architektury, popsané v roce 1945 ve zprávě o počítači EDVAC. Jejím jádrem je myšlenka uloženého programu: instrukce programu leží ve stejné paměti jako data a dají se načíst, změnit i vytvořit jiným programem.von Neumann architecture, stored program

Procesor pracuje v cyklu načti – dekóduj – proveď: z adresy v čítači instrukcí načte instrukci, zjistí, co znamená (sečti, porovnej, skoč jinam, ulož do paměti…), provede ji a posune čítač na další. Rytmus udávají takty. Při frekvenci 3 GHz trvá takt \(1/(3\cdot10^{9})\ \text{s} = 0{,}33\) ns; světlo za tu dobu urazí jen 10 cm. Moderní procesor zvládne v jednom taktu i několik instrukcí najednou a má víc jader, z nichž každé je samostatný procesor.fetch–decode–execute cycle, clock, core

Procesor se skládá z miliard tranzistorů zapojených do logických hradel (AND, OR, NOT). Jak se z hradel postaví sčítačka a paměťová buňka, vysvětluje průvodce Elektrotechnika; logiku, na které hradla stojí, průvodce Logika a kritické myšlení.

3.2Paměťová hierarchie

Rychlá paměť je drahá a malá, levná paměť velká a pomalá. Počítač proto skládá několik úrovní: registry, vyrovnávací paměti procesoru (cache L1, L2, L3), operační paměť RAM a trvalé úložiště (SSD, pevný disk). Co program právě potřebuje, se drží co nejblíž procesoru. Funguje to díky lokalitě: programy často sahají na stejná data znovu (časová lokalita) a na data uložená vedle sebe (prostorová lokalita).memory hierarchy, cache, locality of reference

3.3Operační systém

Operační systém je program, který spravuje hardware a nabízí ostatním programům jednotné služby. Jeho jádro běží ve zvláštním privilegovaném režimu procesoru; aplikace o jeho služby žádají systémovým voláním. Hlavní úlohy:operating system, kernel, system call

• Procesy a plánování: každý spuštěný program je proces. Plánovač je střídá po milisekundách, takže se zdá, že běží současně, i když jader je méně než procesů.
• Správa paměti: každý proces vidí vlastní virtuální paměť; systém ji mapuje na fyzickou RAM a odděluje procesy od sebe, takže chyba jednoho programu nepřepíše data druhého.
• Souborový systém: uspořádá bajty na disku do souborů a složek (stromová struktura, kapitola 7).
• Ovladače a vstup/výstup: skryjí rozdíly mezi tisíci typy zařízení.
• Oprávnění a bezpečnost: kdo smí číst které soubory, která aplikace smí k mikrofonu nebo poloze.

3.4Sítě a internet

Data se po síti posílají v paketech, kousky o velikosti zhruba do 1 500 bajtů. Každý paket nese adresu odesílatele i příjemce a směrovače ho předávají dál, každý podle své tabulky „kterým směrem je to blíž“. Pakety jedné zprávy mohou jet různými cestami a dorazit v jiném pořadí. Této metodě se říká přepojování paketů; díky ní síť přežije výpadek části linek.packet switching, router

Komunikaci řídí vrstvy protokolů; každá řeší jednu starost a spoléhá na vrstvu pod sebou. Model TCP/IP má čtyři vrstvy:

1. Linková (Ethernet, Wi-Fi): přenos rámce k sousednímu zařízení.
2. Síťová (IP): doručení paketu přes mnoho sítí na cílovou IP adresu. IPv4 (RFC 791) má 32bitové adresy, tedy \(2^{32} = 4\,294\,967\,296\) adres, což je dnes málo. IPv6 (RFC 8200) má 128 bitů, \(2^{128} \approx 3{,}4\cdot10^{38}\) adres.
3. Transportní (TCP, UDP): TCP (RFC 9293) z nespolehlivých paketů skládá spolehlivý proud bajtů: čísluje je, potvrzuje, ztracené posílá znovu a řadí. UDP (RFC 768) posílá samostatné zprávy bez záruk; hodí se tam, kde je pozdní data lepší zahodit (hovor, hra).
4. Aplikační (HTTP, DNS, e-mail…): pravidla konkrétní služby.

3.5DNS: telefonní seznam internetu

Lidé si pamatují jména (skola.example), počítače potřebují IP adresy. Převod zajišťuje systém doménových jmen (DNS), popsaný v RFC 1034 a 1035 (1987). Jména jsou hierarchická a čtou se zprava: kořen, doména nejvyšší úrovně (.cz, .org), doména druhé úrovně (název organizace), případně další úrovně. Váš počítač se zeptá rekurzivního resolveru (obvykle u poskytovatele připojení) a ten postupně obejde servery kořene, nejvyšší úrovně a dané domény. Odpovědi se ukládají do mezipaměti na dobu, kterou určí správce domény (TTL).Domain Name System, resolver, time to live

3.6HTTP a HTTPS

HTTP je protokol webu: prohlížeč pošle požadavek (metoda GET pro čtení, POST pro odeslání formuláře, cesta, hlavičky) a server vrátí odpověď se stavovým kódem a obsahem. Kódy 2xx znamenají úspěch (200 OK), 3xx přesměrování (301), 4xx chybu klienta (404 Nenalezeno, 403 Zakázáno), 5xx chybu serveru (500). Význam protokolu popisuje RFC 9110 (2022), verze HTTP/1.1, HTTP/2 a HTTP/3 se liší jen způsobem přenosu.HTTP request, response, status code

HTTPS je HTTP přenášené přes šifrovaný kanál TLS (aktuální verze 1.3, RFC 8446, 2018). TLS zajišťuje tři věci: důvěrnost (obsah nikdo po cestě nepřečte), integritu (nikdo ho nezmění bez odhalení) a ověření serveru: server předloží certifikát podepsaný certifikační autoritou, které váš prohlížeč důvěřuje, a dokáže, že vlastní k němu patřící soukromý klíč. Jak to funguje matematicky, ukáže kapitola 9.HTTPS, TLS, certificate authority

3.7Bezpečnost a soukromí uživatele

Většina útoků na běžné uživatele nevyužívá chyby v šifrování, ale lidskou důvěřivost a slabá nebo opakovaná hesla. Obrana je proto hlavně v návycích.

Hesla

Síla náhodného hesla se měří entropií: \(L\) znaků vybraných náhodně z \(N\) možností dává \(L\log_2 N\) bitů. Každý bit navíc zdvojnásobí počet pokusů. Délka pomáhá víc než složitost: 15 náhodných malých písmen má 70,5 bitu, 8 náhodných znaků ze všech 94 tisknutelných jen 52,4 bitu. Americký standard NIST SP 800-63B-4 (2025) proto žádá u hesla, které je jediným ověřovacím faktorem, aspoň 15 znaků, u hesla doplněného druhým faktorem aspoň 8; služby mají přijímat aspoň 64 znaků, nemají vynucovat pravidla typu „velké písmeno a číslice“ ani pravidelnou změnu hesla, ale mají odmítat hesla ze seznamů uniklých a běžných hesel.password entropy, passphrase

• Každá služba jiné heslo. Když uniknou hesla z jedné služby, útočníci je zkoušejí jinde. Správce hesel vygeneruje a zapamatuje náhodná hesla; vy si pamatujete jedno silné hlavní heslo.
• Dvoufázové ověření (2FA) kombinuje dva různé faktory: něco, co znáte (heslo), něco, co máte (telefon, bezpečnostní klíč), nebo něco, čím jste (otisk prstu). Ukradené heslo samo nestačí.two-factor authentication
• Přístupové klíče (passkeys, standard WebAuthn) nahrazují heslo dvojicí kryptografických klíčů vázanou na doménu služby. Na podvodné doméně nefungují, takže odolávají phishingu.

Phishing a sociální inženýrství

Varovné znaky: nátlak a spěch („do 24 hodin“), žádost o heslo, kód nebo údaje karty, odkaz na nečekanou doménu, příliš výhodná nabídka, zpráva od „banky“ nebo „kurýra“, kterou jste nečekali. Banka ani úřad po vás nikdy nebude chtít heslo nebo kód z SMS. Obrana: odkaz neotvírat, do služby se přihlásit sami (záložka, aplikace), při telefonátu zavěsit a zavolat zpět na oficiální číslo. Kód z SMS, který přišel, aniž jste o něj žádali, nikomu nesdělujte – znamená, že někdo zkouší vaše heslo.phishing, social engineering

Další návyky

• Aktualizace opravují známé bezpečnostní chyby; instalujte je z nastavení systému nebo oficiálního obchodu s aplikacemi.
• Zálohy podle pravidla 3-2-1: tři kopie, na dvou různých médiích, jedna mimo domov (a odpojená, aby ji nezašifroval vyděračský program).
• Soukromí: aplikacím povolujte jen oprávnění, která potřebují; v nastavení cookies volte odmítnutí nepotřebných. Práva vůči firmám, které o vás zpracovávají údaje (přístup, oprava, výmaz), upravuje obecné nařízení EU o ochraně osobních údajů (GDPR).
• Při podezření na podvod volejte banku na číslo z jejích oficiálních stránek nebo z platební karty a věc oznamte Policii ČR (158). Doporučení pro uživatele vydává Národní úřad pro kybernetickou a informační bezpečnost (NÚKIB).

3.8Procvičení

4.1Proměnné a typy

Proměnná je pojmenované místo pro hodnotu. Přiřazení x = 5 (v pseudokódu \(x \leftarrow 5\)) neznamená rovnost jako v matematice, ale příkaz „ulož do \(x\) hodnotu 5“. Proto dává smysl x = x + 1: vezmi starou hodnotu, přičti 1 a výsledek ulož zpět.variable, assignment

Každá hodnota má typ, který určuje, jaké operace s ní lze dělat: celé číslo (int), desetinné číslo (float), logická hodnota (True/False), text neboli řetězec (str), seznam či pole. Jazyky se liší tím, kdy typy kontrolují. Při statickém typování (C, Java) zná typ každé proměnné už překladač a chybu ohlásí před spuštěním. Při dynamickém typování (Python, JavaScript) se typ zjišťuje až za běhu.data type, static and dynamic typing

Jazyky se liší i tím, jak ochotně typy samy převádějí. Python je přísný: "5" + 3 skončí chybou TypeError. JavaScript převádí potichu, a výsledky pak překvapí:

4.2Řízení běhu

Tři struktury z kapitoly 2 mají v každém jazyce svou podobu. Větvení if … elif … else, cyklus s pevným počtem opakování for, cyklus s podmínkou while. Příkaz break cyklus ukončí předčasně, continue přeskočí zbytek aktuálního průchodu. Tentýž program ve dvou jazycích:

# Python: součet sudých čísel
s = 0
for x in [3, 8, 5, 12, 7]:
    if x % 2 == 0:
        s = s + x
print(s)   # 20

// JavaScript: totéž
let s = 0;
for (const x of [3, 8, 5, 12, 7]) {
  if (x % 2 === 0) s = s + x;
}
console.log(s);  // 20

Python vyznačuje bloky odsazením, JavaScript složenými závorkami. JavaScript má dvě porovnání: == s převodem typů a === bez něj; používejte to druhé.

4.3Funkce

Funkce je pojmenovaný kus programu s parametry (vstupy) a návratovou hodnotou (výstupem). Funkce zkracují program, protože se kód nepíše dvakrát, a hlavně ho zpřehledňují: kdo volá prumer(znamky), nemusí vědět, jak se průměr počítá. Proměnné vytvořené uvnitř funkce jsou lokální: existují jen během jejího běhu a nejsou vidět zvenku. Oblasti, ve které je jméno platné, se říká rozsah platnosti.function, parameter, return value, local variable, scope

Funkce, která jen z argumentů spočítá výsledek a nic jiného nemění, se nazývá čistá. Funkce, která navíc něco vypíše, zapíše do souboru nebo změní globální proměnnou, má vedlejší efekt. Čisté funkce se snáz testují: pro stejné vstupy vždy vrátí totéž.pure function, side effect

Při každém volání si počítač na zásobník volání uloží rámec: hodnoty parametrů, lokální proměnné a místo, kam se má vrátit. Po návratu rámec odebere. Zásobník funguje jako stoh talířů: poslední přidaný se bere první (kapitola 7).call stack, stack frame

4.4Rekurze

Rekurzivní funkce volá sama sebe na menší verzi téže úlohy. Musí mít základní případ, který se vyřeší přímo, a rekurzivní krok, který úlohu zmenší směrem k základnímu případu. Bez základního případu se funkce volá, dokud nedojde paměť na zásobníku; Python v tom případě ve výchozím nastavení skončí po 1 000 úrovních chybou RecursionError.recursion, base case

def fakt(n):
    if n <= 1:          # základní případ
        return 1
    return n * fakt(n - 1)

def fib(n, pamet={}):
    if n < 2: return n
    if n not in pamet:
        pamet[n] = fib(n-1) + fib(n-2)
    return pamet[n]

Rekurze se hodí na úlohy, které se přirozeně rozpadají na menší kopie sebe sama: procházení stromu složek, řazení slučováním (kapitola 5), hledání v bludišti. Každou rekurzi lze přepsat na cyklus se zásobníkem a naopak.

Hanojské věže

Na první tyči leží \(n\) kotoučů od největšího po nejmenší. Úkol: přenést je na třetí tyč, vždy jen jeden kotouč a nikdy větší na menší. Rekurzivní řešení: přeneste \(n-1\) horních kotoučů na pomocnou tyč, největší kotouč na cílovou a pak \(n-1\) kotoučů z pomocné na cílovou. Počet tahů splňuje \(T(n) = 2T(n-1) + 1\), \(T(1) = 1\), tedy \(T(n) = 2^{n} - 1\).Tower of Hanoi, recurrence

Paměť místo opakování

Naivní rekurzivní Fibonacci počítá \(F(n-2)\) jednou přímo a jednou uvnitř \(F(n-1)\); počet volání roste zhruba jako \(1{,}618^{n}\). Pro \(n = 30\) je to 2 692 537 volání, pro \(n = 40\) už 331 160 281. Verze s pamětí (memoizací) spočítá každou hodnotu jednou: pro \(n = 40\) jen 79 volání. Obecný postup – rozložit úlohu na podúlohy, každou vyřešit jednou a výsledky skládat – se nazývá dynamické programování.memoization, dynamic programming

4.5Ladění a testování

Chyby jsou trojího druhu. Syntaktické (chybějící závorka) odhalí překladač nebo interpret ještě před spuštěním. Běhové (dělení nulou, index mimo rozsah) program za běhu shodí. Nejzrádnější jsou logické: program běží, ale počítá něco jiného.syntax error, runtime error, logic error

1. Zopakujte chybu spolehlivě a najděte co nejmenší vstup, na kterém nastane.
2. Vyslovte hypotézu, kde je problém, a ověřte ji: ladicím výpisem hodnot, nebo v debuggeru, kde program zastavíte na zarážce (breakpoint) a krokujete.
3. Opravte příčinu, ne projev, a napište test, který chybu zachytí, kdyby se vrátila.

def prumer(cisla):
    return sum(cisla) / len(cisla)

# jednoduché testy: když neplatí, program ohlásí AssertionError
assert prumer([1, 2, 3]) == 2
assert prumer([5]) == 5
# prumer([]) skončí ZeroDivisionError: co má funkce vrátit pro prázdný seznam?

4.6Paradigmata programování

Jazyky podporují různé styly myšlení. Imperativní program je posloupnost příkazů měnících stav (proměnné). Objektově orientovaný styl seskupuje data a funkce, které s nimi pracují, do objektů (student má jméno a umí spočítat průměr známek). Funkcionální styl skládá čisté funkce a vyhýbá se změnám stavu. Deklarativní styl popisuje, co chceme, ne jak to získat: typický příklad je SQL v kapitole 10. Python i JavaScript umožňují všechny tři první styly.imperative, object-oriented, functional, declarative programming

4.7Procvičení

5.1Úloha řazení

Řazení uspořádá posloupnost \(a_1, \dots, a_n\) tak, aby \(a_1 \le a_2 \le \dots \le a_n\). Algoritmy porovnáváme podle počtu porovnání a přesunů v nejlepším, průměrném a nejhorším případě a podle dalších vlastností. Stabilní řazení zachová pořadí prvků se stejným klíčem (seřadíte-li žáky podle známky stabilně, zůstanou se stejnou známkou v abecedním pořadí). Řazení na místě potřebuje jen konstantní paměť navíc.sorting, stable sort, in-place

5.2Bublinkové řazení

Procházíme pole a prohazujeme sousedy ve špatném pořadí. Po prvním průchodu „vybublá“ největší prvek na konec, po druhém druhý největší a tak dál. Počet porovnání je \((n-1) + (n-2) + \dots + 1 = n(n-1)/2\); pro 10 prvků 45. Algoritmus je stabilní a na místě, ale pomalý; hodí se jako první příklad, ne do praxe.bubble sort

pro k od n−1 dolů do 1:
    pro i od 1 do k:
        když a[i] > a[i+1]: prohoď a[i], a[i+1]

5.3Řazení vkládáním

Levá část pole je seřazená. Vezmeme další prvek a posouváme ho doleva, dokud nenarazíme na menší. V nejhorším případě (obrácené pole) to stojí \(n(n-1)/2\) porovnání, v nejlepším (seřazené pole) jen \(n-1\). Počet posunů se přesně rovná počtu inverzí, tedy dvojic prvků ve špatném pořadí. Na téměř seřazených datech je proto řazení vkládáním velmi rychlé.insertion sort, inversion

5.4Řazení slučováním

Metoda rozděl a panuj: pole rozdělíme na dvě poloviny, každou seřadíme (rekurzivně) a obě seřazené poloviny sloučíme: opakovaně bereme menší z dvou čel. Sloučení dvou úseků o celkové délce \(m\) stojí nejvýš \(m-1\) porovnání. Algoritmus popsal John von Neumann v roce 1945.merge sort, divide and conquer

Hloubka rekurze je \(\lceil\log_2 n\rceil\) a na každé úrovni se sloučí dohromady \(n\) prvků. Odtud rekurence a výsledek:

Přesně je to v nejhorším případě \(n\lceil\log_2 n\rceil - 2^{\lceil\log_2 n\rceil} + 1\) porovnání: pro \(n = 8\) jde o 17, pro \(n = 1\,000\) o 8 977. Algoritmus je stabilní a jeho čas nezávisí na datech, potřebuje ale pomocné pole velikosti \(n\).

5.5Rychlé řazení

Hoare (1962) zvolil jiný postup: vybrat pivot, přeskupit pole tak, aby menší prvky byly vlevo a větší vpravo (rozdělení), a obě části seřadit rekurzivně. Sloučení odpadá, pivot už stojí na svém místě.quicksort, pivot, partition

Při dobrém pivotu (blízko mediánu) se pole dělí napůl a čas je \(n\log n\). Průměrný počet porovnání přes všechna pořadí vstupu je \(2(n+1)H_n - 4n\), kde \(H_n = 1 + \tfrac12 + \dots + \tfrac1n\); asymptoticky \(2n\ln n \approx 1{,}39\,n\log_2 n\). Pro \(n = 1\,000\) vychází průměrně 10 986 porovnání. V nejhorším případě, když pivot je vždy nejmenší nebo největší prvek, je to \(n(n-1)/2\). Při volbě posledního prvku jako pivotu nastane nejhorší případ právě na seřazeném poli. Obrana: náhodný pivot nebo medián ze tří prvků.

5.6Rychleji to nejde: dolní mez

Každé řazení, které o prvcích zjišťuje informace jen porovnáváním, lze znázornit rozhodovacím stromem: v uzlech porovnání, v listech výsledná pořadí. Strom musí mít aspoň \(n!\) listů (každé pořadí vstupu vyžaduje jinou přestavbu) a binární strom s \(n!\) listy má hloubku aspoň \(\log_2 n!\). Nejhorší případ tedy potřebuje aspoň \(\lceil\log_2 n!\rceil\) porovnání.decision tree, lower bound

Pro 10 prvků je \(\log_2 10! = 21{,}8\), takže aspoň 22 porovnání; bublinkové řazení jich spotřebuje 45. Pro 1 000 prvků je mez 8 530 a řazení slučováním s 8 977 porovnáními v nejhorším případě je jí velmi blízko. Řazení slučováním je tedy asymptoticky optimální. Rychleji než \(n\log n\) umějí řadit jen algoritmy, které o klíčích vědí víc (například řazení počítáním pro malá celá čísla).

5.7Binární vyhledávání

V seřazeném poli hledáme hodnotu \(x\). Porovnáme ji s prostředním prvkem: je-li menší, hledáme dál jen v levé polovině, je-li větší, v pravé. Invariant: pokud \(x\) v poli je, leží v aktuálním úseku. Každý krok úsek aspoň způlí, takže stačí \(\lfloor\log_2 n\rfloor + 1\) porovnání: pro 1 000 prvků 10, pro milion 20, pro miliardu 30.binary search

def hledej(a, x):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        m = (lo + hi) // 2
        if a[m] == x: return m
        if a[m] < x: lo = m + 1
        else:        hi = m - 1
    return -1     # není v poli

5.8Procvičení

6.1Jak měřit rychlost algoritmu

Místo sekund počítáme elementární operace: přiřazení, porovnání, aritmetiku, přístup do pole. Předpokládáme, že každá trvá konstantní dobu (model počítače RAM). Časová složitost je funkce \(T(n)\), která velikosti vstupu \(n\) přiřadí počet operací. Protože pro stejně velké vstupy se počet liší (seřazené a obrácené pole), rozlišujeme nejhorší, průměrný a nejlepší případ. Nejčastěji se uvádí nejhorší: je to záruka.time complexity, worst case, average case

6.2O-notace

Zajímá nás chování pro velká \(n\), proto zanedbáváme konstanty a menší členy. Formálně:Big O, Big Omega, Big Theta

\(O\) je horní odhad („roste nejvýš tak rychle jako“), \(\Omega\) dolní, \(\Theta\) přesný řád. Rovnítko se tu čte „patří do třídy“, není to symetrická rovnost.

6.3Hierarchie růstu

Pro velká \(n\) platí \(1 \prec \log n \prec \sqrt{n} \prec n \prec n\log n \prec n^{2} \prec n^{3} \prec 2^{n} \prec n! \prec n^{n}\), kde \(f \prec g\) znamená, že podíl \(f/g\) jde k nule. Algoritmy s polynomiální složitostí (\(n^{k}\)) považujeme za prakticky použitelné, exponenciální za použitelné jen pro malá \(n\). Tabulka ukazuje proč.

6.4Algoritmus, nebo hardware?

Gordon Moore v roce 1965 předpověděl, že počet tranzistorů na čipu se bude pravidelně zdvojnásobovat (od roku 1975 uváděl zhruba každé dva roky). Výkon počítačů tak po desetiletí rostl exponenciálně. Přesto lepší algoritmus obvykle přinese víc než lepší počítač: tisíckrát rychlejší stroj zvětší zvládnutelný vstup u algoritmu \(n^{2}\) jen \(\sqrt{1\,000} \approx 31{,}6\)krát, u \(n^{3}\) desetkrát a u \(2^{n}\) jen o 10 (\(\log_2 1\,000 \approx 9{,}97\)).Moore's law

6.5Jak složitost určit

• Posloupnost kroků: složitosti se sčítají a vítězí největší, \(O(n) + O(n^{2}) = O(n^{2})\).
• Cyklus: počet průchodů krát cena těla. Vnořené cykly přes \(n\) dávají \(n\cdot n\); vnitřní cyklus „do \(i\)“ dává \(0 + 1 + \dots + (n-1) = n(n-1)/2\), tedy také \(\Theta(n^{2})\).
• Půlení: cyklus, který \(n\) pokaždé vydělí dvěma, proběhne \(\lfloor\log_2 n\rfloor + 1\)krát; pro \(n = 1\,000\) desetkrát.
• Rekurze vede na rekurenci, rovnici, ve které je \(T(n)\) vyjádřeno přes \(T\) menších vstupů.

Mistrovská věta (rozšíření)

Pro algoritmy „rozděl a panuj“, které úlohu velikosti \(n\) rozdělí na \(a\) podúloh velikosti \(n/b\) a rozdělení a složení stojí \(\Theta(n^{d})\), platí:master theorem

Řazení slučováním: \(a = 2\), \(b = 2\), \(d = 1 = \log_2 2\), tedy \(\Theta(n\log n)\). Binární vyhledávání: \(a = 1\), \(b = 2\), \(d = 0 = \log_2 1\), tedy \(\Theta(\log n)\). Karacubovo násobení velkých čísel (1960) převádí násobení dvou \(n\)-ciferných čísel na tři násobení polovičních: \(a = 3\), \(b = 2\), \(d = 1 \lt \log_2 3\), tedy \(\Theta(n^{\log_2 3}) = \Theta(n^{1{,}585})\) místo školních \(n^{2}\).

6.6Paměť a amortizace

Paměťová složitost měří spotřebu paměti navíc ke vstupu: řazení slučováním potřebuje \(\Theta(n)\), rychlé řazení \(\Theta(\log n)\) na zásobník rekurze. Často se dá čas vyměnit za paměť, jako u memoizace v kapitole 4.space complexity, amortized analysis

Amortizovaná složitost je průměrná cena operace v nejhorší posloupnosti operací. Typický příklad je dynamické pole (seznam v Pythonu): když se zaplní, alokuje se pole dvojnásobné velikosti a prvky se zkopírují. Jednotlivé přidání tak občas stojí \(\Theta(n)\), ale při \(n\) přidáních se kopíruje nejvýš \(1 + 2 + 4 + \dots \lt 2n\) prvků. Průměrně tedy přidání stojí \(O(1)\).

6.7Procvičení

7.1Abstraktní datový typ a jeho implementace

Abstraktní datový typ říká, jaké operace s daty lze dělat (vlož, odeber, najdi), a ne, jak jsou data uložena. Datová struktura je konkrétní uspořádání v paměti, které operace implementuje. Tentýž abstraktní typ „množina“ lze implementovat polem, stromem i hašovací tabulkou, s velmi rozdílnou cenou operací.abstract data type (ADT), data structure

7.2Pole a spojový seznam

Pole ukládá prvky v paměti těsně za sebou. Adresu \(i\)-tého prvku spočítá procesor jedním násobením, proto je přístup podle indexu \(O(1)\). Vložení doprostřed ale vyžaduje posunout všechny následující prvky, \(O(n)\). Spojový seznam ukládá každý prvek zvlášť spolu s ukazatelem (adresou) na další prvek. Vložení za známý prvek je \(O(1)\) – stačí přepojit ukazatele –, ale k \(i\)-tému prvku se musíme „dokrokovat“, \(O(n)\).array, linked list, pointer

Pole pevné velikosti se v praxi nahrazuje dynamickým polem (seznam v Pythonu, pole v JavaScriptu), které se při zaplnění zdvojnásobí. Přidání na konec stojí amortizovaně \(O(1)\) (oddíl 6.6). Díky souvislému uložení je pole navíc přátelské k vyrovnávací paměti procesoru (oddíl 3.2) a v praxi bývá rychlejší, než by napovídala O-notace.

7.3Zásobník a fronta

Zásobník má operace vlož na vrchol (push) a odeber z vrcholu (pop); poslední vložený prvek odchází první (LIFO). Používá se pro zásobník volání funkcí (oddíl 4.3), tlačítko Zpět, vyhodnocování výrazů a párování závorek. Fronta vkládá na konec a odebírá z čela; první vložený odchází první (FIFO). Používá se pro tiskové úlohy, zpracování požadavků na serveru a prohledávání do šířky (kapitola 8). Obě operace mají v obou strukturách složitost \(O(1)\); fronta se v poli realizuje jako kruhový buffer, kde se čelo i konec posouvají dokola.stack (LIFO), queue (FIFO), circular buffer

7.4Stromy

Strom je hierarchická struktura: má kořen, každý uzel kromě kořene má právě jednoho rodiče a uzly bez potomků jsou listy. Hloubka uzlu je počet hran od kořene, výška stromu je největší hloubka. Stromy jsou složky na disku, struktura webové stránky (DOM), rozbor věty i rodokmen. Binární strom má u každého uzlu nejvýš dva potomky: levého a pravého.tree, root, leaf, depth, height, binary tree

Binární vyhledávací strom (BVS) splňuje invariant: všechny hodnoty v levém podstromu uzlu jsou menší než hodnota uzlu, všechny v pravém větší. Hledání, vkládání i mazání sledují jedinou cestu od kořene, stojí tedy \(O(h)\), kde \(h\) je výška. Ta je mezi \(\lceil\log_2(n+1)\rceil - 1\) (vyvážený strom; pro milion uzlů 19) a \(n - 1\) (strom zdegenerovaný v řetěz, například při vkládání seřazených hodnot). Při vkládání v náhodném pořadí je průměrná hloubka uzlu asi \(2\ln n \approx 1{,}39\log_2 n\).binary search tree (BST)

Vyvážené stromy po každém vložení nebo smazání strom lokálně přestaví (rotace), aby výška zůstala \(O(\log n)\). Nejstarší jsou AVL stromy (Adelson-Velskij a Landis, 1962), v knihovnách jsou běžné červeno-černé stromy. Databáze používají B-stromy s mnoha potomky v uzlu (kapitola 10).balanced tree, AVL tree, red-black tree

7.5Halda a prioritní fronta

Prioritní fronta vrací vždy prvek s nejvyšší prioritou (nejmenším klíčem): pohotovost ošetřuje nejvážnější případy, plánovač procesů nejdůležitější úlohy, Dijkstrův algoritmus nejbližší vrchol. Implementuje se binární haldou: téměř úplným binárním stromem, ve kterém je každý rodič menší nebo roven svým potomkům. Minimum je v kořeni; vložení i odebrání minima opraví haldu výměnami po jedné cestě, \(O(\log n)\). Halda se ukládá do pole bez ukazatelů: potomci prvku na indexu \(i\) jsou na indexech \(2i+1\) a \(2i+2\).priority queue, binary heap

7.6Hašovací tabulka

Hašovací tabulka ukládá dvojice klíč–hodnota do pole \(m\) přihrádek. Hašovací funkce \(h\) spočítá z klíče číslo přihrádky; dobrá funkce rozhází klíče rovnoměrně. Když dva klíče padnou do stejné přihrádky, nastane kolize. Řeší se řetězením (přihrádka drží seznam) nebo otevřeným adresováním (hledá se jiná volná přihrádka). Poměr \(\alpha = n/m\) se nazývá faktor naplnění. Při rovnoměrném hašování je průměrná délka řetězce \(\alpha\) a hledání trvá v průměru \(O(1 + \alpha)\). Když \(\alpha\) překročí mez (typicky kolem 0,75), tabulka se zvětší a klíče se přehašují.hash table, hash function, collision, chaining, load factor

Narozeninový paradox

Kolize přicházejí dřív, než by se zdálo. Pravděpodobnost, že mezi \(k\) lidmi mají aspoň dva narozeniny ve stejný den (365 dní, rovnoměrně), je

Pro 23 lidí vychází 50,7 %, pro 50 lidí 97,0 %, pro 70 lidí 99,9 %. Obecně se první kolize v tabulce s \(m\) přihrádkami čeká už kolem \(\sqrt{m}\) klíčů. Stejná úvaha určuje, jak dlouhý musí být kryptografický haš (kapitola 9).birthday paradox

7.7Grafy

Graf \(G = (V, E)\) je množina vrcholů \(V\) a hran \(E\) mezi nimi. Hrany mohou být orientované (jednosměrky, odkazy mezi stránkami) nebo neorientované (přátelství), a ohodnocené (délka silnice). Stromy jsou zvláštní případ grafu: souvislý graf bez cyklů. Ukládá se dvojím způsobem:graph, vertex, edge, adjacency matrix, adjacency list

7.8Procvičení

8.1Cesty a souvislost

Cesta v grafu je posloupnost vrcholů spojených hranami, cyklus je cesta, která se vrací do výchozího vrcholu. Graf je souvislý, když mezi každými dvěma vrcholy vede cesta. Stupeň vrcholu je počet hran, které z něj vycházejí; součet stupňů všech vrcholů je \(2m\), protože každá hrana se počítá u obou konců. Teorie grafů začala Eulerovou úvahou o sedmi mostech v Královci (1736): projít každý most právě jednou nejde, protože všechny čtyři části města měly lichý počet mostů, a takový tah existuje, jen když lichý stupeň mají nejvýš dva vrcholy.path, cycle, connected graph, degree

8.2Prohledávání do šířky (BFS)

BFS začne ve výchozím vrcholu a navštěvuje vrcholy po vrstvách: nejdřív všechny ve vzdálenosti 1, pak 2 a tak dál. Pomocí fronty: z čela vezmeme vrchol, jeho dosud nenavštívené sousedy označíme a zařadíme na konec. Protože vrstvy přicházejí v pořadí vzdálenosti, první návštěva každého vrcholu proběhne po nejkratší cestě (v počtu hran). Každý vrchol i hrana se zpracují jednou, složitost je \(O(n + m)\).breadth-first search (BFS)

BFS(G, s):
    vzd[s] ← 0;  fronta ← [s]
    dokud fronta není prázdná:
        u ← odeber z čela fronty
        pro každého souseda v vrcholu u:
            když v ještě nemá vzdálenost:
                vzd[v] ← vzd[u] + 1;  před[v] ← u
                vlož v na konec fronty

8.3Prohledávání do hloubky (DFS)

DFS jde co nejdál jedním směrem a teprve ve slepé uličce se vrací k poslední odbočce. Používá zásobník, nejčastěji skrytě v podobě rekurze. Najde nějakou cestu, ne nutně nejkratší. Hodí se ale na mnoho jiných úloh: zjistit, zda je graf souvislý a zda obsahuje cyklus, najít komponenty souvislosti, generovat bludiště nebo topologicky uspořádat úkoly, které na sobě závisejí (co se musí udělat dřív). Složitost je také \(O(n + m)\).depth-first search (DFS), topological sort

8.4Dijkstrův algoritmus

Když mají hrany různou délku (nezápornou), nejkratší cestu najde algoritmus, který Edsger Dijkstra publikoval v roce 1959. Udržuje odhad vzdálenosti \(d(v)\) každého vrcholu; na začátku \(d(s) = 0\) a ostatní \(\infty\). Opakovaně vybere nezpracovaný vrchol s nejmenším odhadem, prohlásí ho za hotový a relaxuje jeho hrany: když \(d(u) + w(u, v) \lt d(v)\), sníží \(d(v)\). Výběr nejbližšího vrcholu zajišťuje prioritní fronta (halda, oddíl 7.5); složitost je pak \(O((n + m)\log n)\).Dijkstra's algorithm, relaxation

Proč je to správně: když vybereme vrchol \(u\) s nejmenším odhadem, žádná jiná cesta do \(u\) nemůže být kratší, protože by musela vést přes nějaký jiný nezpracovaný vrchol s odhadem aspoň \(d(u)\) a hrany nemají zápornou délku.

8.5A*: Dijkstra s kompasem

Algoritmus A* (Hart, Nilsson, Raphael, 1968) vybírá vrchol podle součtu \(f(v) = g(v) + h(v)\), kde \(g\) je známá cena cesty ze startu a \(h\) heuristika, odhad zbývající ceny do cíle. Je-li heuristika přípustná (nikdy nepřecení skutečnou cenu), najde A* nejkratší cestu a obvykle prozkoumá mnohem méně vrcholů než Dijkstra, protože se „táhne“ k cíli. Na mřížce se používá manhattanská vzdálenost, na mapě vzdušná čára. Při \(h = 0\) je A* totéž co Dijkstra.A* search, admissible heuristic

8.6Minimální kostra

Kostra souvislého grafu je podmnožina hran, která propojí všechny vrcholy a neobsahuje cyklus; má vždy \(n - 1\) hran. Minimální kostra má nejmenší součet ohodnocení. Úlohu poprvé formuloval a vyřešil brněnský matematik Otakar Borůvka (1926) při návrhu elektrické sítě na Moravě; Vojtěch Jarník (1930) v dopise Borůvkovi popsal jiný postup, který později znovu objevil Prim (1957). Kruskal (1956) přidal třetí. Všechny jsou hladové a správné díky jedné vlastnosti:minimum spanning tree (MST), Borůvka's, Jarník's (Prim's), Kruskal's algorithm

• Kruskal: hrany seřadí od nejlehčí a postupně přidává každou, která nevytvoří cyklus. Cykly hlídá struktura union-find. Složitost \(O(m\log m)\), hlavně řazení.
• Jarník (Prim): strom roste z jednoho vrcholu; vždy přidá nejlehčí hranu, která vede ze stromu ven. S haldou \(O(m\log n)\).
• Borůvka: každá komponenta najednou přidá svou nejlehčí odchozí hranu; počet komponent se v každém kole aspoň způlí, kol je nejvýš \(\log_2 n\). Dobře se paralelizuje.

8.7Procvičení

9.1Co kryptografie chrání

Kryptografie zajišťuje čtyři vlastnosti: důvěrnost (zprávu přečte jen oprávněný), integritu (změna zprávy se pozná), autenticitu (víme, kdo zprávu poslal) a nepopiratelnost (odesílatel nemůže zapřít, že zprávu podepsal). Otevřený text se pomocí klíče převádí na šifrový text. Auguste Kerckhoffs v roce 1883 formuloval zásadu, která platí dodnes: systém má zůstat bezpečný, i když nepřítel zná vše kromě klíče. Utajený algoritmus není ochrana, jen odklad.confidentiality, integrity, authenticity, non-repudiation, Kerckhoffs's principle

9.2Klasické šifry a jejich pád

Caesarova šifra posune každé písmeno o \(k\) míst: \(c = (m + k) \bmod 26\). Klíčů je jen 25, takže se dá vyzkoušet všechny. Obecná záměna (každé písmeno nahradí jiné podle tabulky) má \(26! \approx 4{,}03\cdot10^{26}\) klíčů, přesto padne frekvenční analýzou, kterou v 9. století popsal arabský učenec al-Kindí: v každém jazyce jsou některá písmena častější (v textu tohoto průvodce E 9,7 %, A 9,1 %, O 8,7 %), a záměna písmen rozložení četností nezmění, jen ho přejmenuje.Caesar cipher, substitution cipher, frequency analysis

Vigenèrova šifra (16. století) střídá několik posunů podle klíčového slova a jednoduchou frekvenční analýzu odolá; v 19. století ji prolomil Kasiski hledáním opakování. Šifrovací stroj Enigma z druhé světové války měl astronomický počet nastavení, přesto ho prolomili polští matematici v čele s Marianem Rejewskim (1932) a pak tým v Bletchley Parku včetně Alana Turinga – díky chybám v provozu a matematice permutací.

Jedinou dokazatelně nerozluštitelnou šifrou je jednorázová tabulka (one-time pad): klíč je stejně dlouhý jako zpráva, zcela náhodný a použije se jen jednou; šifruje se operací XOR. Shannon (1949) dokázal, že šifrový text pak o zprávě neprozradí nic. Nevýhoda je zřejmá: předat tak dlouhý klíč bezpečně je stejně těžké jako předat samotnou zprávu.one-time pad, perfect secrecy

9.3Symetrické šifry: AES

V symetrické kryptografii mají odesílatel i příjemce stejný tajný klíč. Dnešním standardem je AES (norma FIPS 197 z roku 2001, algoritmus Rijndael belgických autorů Daemena a Rijmena). Šifruje bloky po 128 bitech klíčem o délce 128, 192 nebo 256 bitů; v mnoha kolech střídá záměnu bajtů, přeskupení a míchání s klíčem. AES je rychlý (procesory na něj mají instrukce) a šifruje disky, Wi-Fi i obsah spojení TLS.symmetric encryption, AES, block cipher

Blokovou šifru je třeba použít ve vhodném režimu. Nejjednodušší režim, šifrovat každý blok zvlášť (ECB), prozradí opakující se vzory. Dnes se používá autentizované šifrování (například AES-GCM), které současně zajistí důvěrnost i integritu.

9.4Hašovací funkce

Kryptografická hašovací funkce převede libovolně dlouhá data na otisk pevné délky (SHA-256: 256 bitů). Musí být jednosměrná (z otisku nejde najít vstup), odolná vůči kolizím (nejde najít dva vstupy se stejným otiskem) a mít lavinový efekt: změna jediného bitu vstupu změní zhruba polovinu bitů otisku.cryptographic hash function, preimage resistance, collision resistance, avalanche effect

Kvůli narozeninovému paradoxu (oddíl 7.6) stačí na nalezení kolize u \(n\)-bitového haše zhruba \(2^{n/2}\) pokusů; proto se používají haše aspoň 256bitové. Starší funkce MD5 a SHA-1 jsou prolomené: pro SHA-1 byla v roce 2017 veřejně předvedena kolize dvou různých dokumentů PDF. Platnými standardy jsou SHA-2 (FIPS 180-4) a SHA-3 (FIPS 202).

Jak bezpečně ukládat hesla

Služba nemá znát vaše heslo; ukládá jen jeho otisk a při přihlášení porovná otisk zadaného hesla. Ke každému heslu přidá náhodnou sůl, aby stejná hesla měla různé otisky, a použije záměrně pomalou funkci (Argon2 podle RFC 9106, bcrypt, PBKDF2), která i po úniku databáze zpomalí hádání na tisíce pokusů za sekundu místo miliard. To je rozdíl, se kterým počítala laboratoř v kapitole 3.salt, password hashing, key stretching

9.5Asymetrická kryptografie

Symetrická šifra má jeden zásadní problém: jak si klíč předat, když zatím nemáme bezpečný kanál? Řešení publikovali Whitfield Diffie a Martin Hellman v roce 1976: dvě strany se mohou na tajném čísle dohodnout veřejně, protože některé matematické operace jdou snadno jedním směrem a prakticky ne zpět. Umocnit číslo modulo prvočíslo je snadné; z výsledku zjistit exponent (diskrétní logaritmus) pro velká čísla neumíme.public-key cryptography, Diffie–Hellman key exchange, discrete logarithm

RSA

Rivest, Shamir a Adleman popsali v roce 1977 (publikováno 1978) systém, ve kterém má každý pár klíčů. Bezpečnost stojí na tom, že vynásobit dvě velká prvočísla je snadné, ale rozložit jejich součin zpět na činitele neumíme.RSA, integer factorization

1. Zvolíme dvě různá prvočísla \(p, q\) a spočítáme \(n = pq\) a \(\varphi(n) = (p-1)(q-1)\).
2. Zvolíme \(e\) nesoudělné s \(\varphi(n)\) a najdeme \(d\) tak, aby \(e\cdot d \equiv 1 \pmod{\varphi(n)}\) (rozšířeným Euklidovým algoritmem, kapitola 2).
3. Veřejný klíč je \((n, e)\), soukromý \(d\). Šifrování \(c = m^{e} \bmod n\), dešifrování \(m = c^{d} \bmod n\).

Poslední krok plyne z Eulerovy věty \(m^{\varphi(n)} \equiv 1 \pmod n\) pro \(m\) nesoudělné s \(n\) (platí i pro ostatní \(m \lt n\), jak se ověří přes čínskou větu o zbytcích). Kdo zná \(p\) a \(q\), spočítá \(\varphi(n)\) a z \(e\) snadno \(d\). Kdo zná jen \(n\), musí \(n\) nejdřív rozložit.

9.6Digitální podpis a certifikáty

Digitální podpis obrací role klíčů: podepisuje se soukromým klíčem, ověřuje veřejným. Podepisuje se otisk dokumentu: \(s = h(M)^{d} \bmod n\). Ověřovatel spočítá \(s^{e} \bmod n\) a porovná s otiskem \(h(M)\), který si sám vypočte z dokumentu. Shoda dokazuje, že dokument podepsal držitel soukromého klíče (autenticita, nepopiratelnost) a že se od podpisu nezměnil (integrita).digital signature

Zbývá otázka, komu veřejný klíč patří. Odpovídá na ni certifikát: dokument „tento veřejný klíč patří doméně skola.example“ podepsaný certifikační autoritou, jejíž veřejný klíč má prohlížeč předinstalovaný. Řetěz podpisů od kořenové autority k serveru tvoří infrastrukturu veřejných klíčů (PKI). Na stejném principu stojí zaručený elektronický podpis, který v EU upravuje nařízení eIDAS (č. 910/2014).certificate, certificate authority, public key infrastructure (PKI)

9.7Kvantové počítače a postkvantová kryptografie

Peter Shor (1994) ukázal, že dostatečně velký kvantový počítač by rozložil čísla na prvočinitele i spočítal diskrétní logaritmus v polynomiálním čase. RSA i Diffie–Hellman (včetně variant na eliptických křivkách) by pak padly. Symetrické šifry ohrožuje Groverův algoritmus jen tak, že efektivně půlí délku klíče; AES-256 zůstává bezpečný. Takový kvantový počítač zatím neexistuje, ale data zachycená dnes by mohla být rozšifrována později. Americký úřad NIST proto v srpnu 2024 vydal první normy postkvantové kryptografie (FIPS 203, 204 a 205), založené na úlohách, pro které kvantový algoritmus neznáme, například na mřížkách.Shor's algorithm, post-quantum cryptography

9.8Procvičení

10.1Proč databáze

Databázový systém (DBMS) spravuje data trvale, umožní k nim přístup mnoha uživatelům najednou, hlídá pravidla (každá známka patří existujícímu žákovi) a odpovídá na dotazy. Aplikace neřeší, jak jsou data uložena na disku; to je datová nezávislost. Změny se provádějí v transakcích s vlastnostmi ACID (Härder a Reuter, 1983): atomičnost (provede se celá, nebo vůbec), konzistence (zachová pravidla), izolovanost (souběžné transakce se navzájem neruší) a trvanlivost (potvrzená změna přežije i výpadek proudu).database management system, transaction, ACID

10.2Relační model

Edgar F. Codd (1970) navrhl ukládat data jako relace: tabulky, jejichž řádky (n-tice) jsou množinou a sloupce (atributy) mají doménu přípustných hodnot. Primární klíč jednoznačně určuje řádek (studenti.id). Cizí klíč odkazuje na primární klíč jiné tabulky (znamky.student_id → studenti.id); databáze hlídá, aby odkaz vedl na existující řádek (referenční integrita).relation, tuple, attribute, primary key, foreign key, referential integrity

10.3Relační algebra

Dotazy nad relacemi lze skládat z několika operací, jejichž výsledkem je opět relace. Selekce \(\sigma_{p}(R)\) vybere řádky splňující podmínku \(p\); projekce \(\pi_{A}(R)\) ponechá sloupce \(A\); kartézský součin \(R \times S\) spojí každý řádek \(R\) s každým řádkem \(S\); spojení \(R \bowtie_{p} S = \sigma_{p}(R \times S)\); dále sjednocení, rozdíl a přejmenování. SQL je nad touto algebrou uživatelsky přívětivý jazyk a databáze dotaz do algebry přeloží a přestaví do co nejlevnější podoby (optimalizace dotazu).relational algebra, selection, projection, join, query optimization

10.4SQL

SQL (norma ISO/IEC 9075, poslední verze SQL:2023) je deklarativní: popisuje, jaký výsledek chceme, ne jak ho spočítat. Má část pro definici dat (CREATE TABLE), pro změny dat (INSERT, UPDATE, DELETE) a dotaz SELECT. Klauzule dotazu se píší v jiném pořadí, než v jakém se logicky vyhodnocují:SQL, declarative language

SELECT p.nazev, AVG(z.znamka) AS prumer, COUNT(*)
FROM predmety p JOIN znamky z ON p.id = z.predmet_id
GROUP BY p.nazev
ORDER BY prumer;

Spojení a NULL

Vnitřní spojení (JOIN) vrátí jen dvojice řádků, které splní podmínku ON. Levé vnější spojení (LEFT JOIN) vrátí navíc každý řádek levé tabulky, který žádný protějšek nemá, a chybějící hodnoty doplní hodnotou NULL („neznámá / chybí“). NULL se chová zvláštně: jakékoli porovnání s ní dá výsledek neznámo, ne pravda ani nepravda (tříhodnotová logika). Proto WHERE x = NULL nevrátí nic a správně se píše WHERE x IS NULL.inner join, left outer join, NULL, three-valued logic

10.5Normalizace

Tabulka, která ukládá stejný fakt vícekrát, trpí anomáliemi. Představte si jedinou tabulku vysvedceni(jmeno, trida, tridni_ucitel, predmet, znamka): změna třídního učitele 3.A se musí provést v mnoha řádcích (aktualizační anomálie, stačí jeden přehlédnout a data si odporují); smazáním poslední známky žáka zmizí i informace, do které třídy chodí (mazací anomálie); novou třídu nejde zapsat, dokud v ní není žák se známkou (vkládací anomálie).normalization, update/delete/insert anomaly

Příčinou je funkční závislost \(X \to Y\) („hodnota \(X\) určuje hodnotu \(Y\)“), jejíž levá strana není klíčem: trida → tridni_ucitel. Normální formy takové závislosti postupně odstraňují:

• 1NF: hodnoty jsou atomické (žádné seznamy známek v jedné buňce).
• 2NF: 1NF a žádný neklíčový atribut nezávisí jen na části složeného klíče.
• 3NF: 2NF a žádný neklíčový atribut nezávisí na jiném neklíčovém atributu (tranzitivně).
• BCNF: levá strana každé netriviální funkční závislosti je nadklíč.

Rozklad vysvedceni na studenti(id, jmeno, trida), tridy(trida, tridni_ucitel), predmety(id, nazev) a znamky(student_id, predmet_id, znamka) je v BCNF: každý fakt je uložen jednou a původní tabulku vrátí spojení. V analytických databázích se naopak někdy záměrně denormalizuje, aby čtení nemuselo spojovat tabulky.

10.6Indexy

Bez indexu musí databáze najít řádky s jmeno = 'Dana' průchodem celé tabulky. Index je pomocná struktura, nejčastěji B-strom (Bayer a McCreight, 1972): vyvážený strom, jehož uzel zabírá celou stránku disku a má stovky potomků. Při větvení 200 má strom pro \(10^{8}\) řádků hloubku \(\lceil\log_{200}10^{8}\rceil = 4\), binární strom by měl 27 úrovní. Index zrychlí hledání, spojování a řazení podle indexovaného sloupce, ale zpomalí zápisy (každý INSERT a UPDATE musí upravit i index) a zabere místo.index, B-tree

10.7Bezpečnost a další modely dat

Hodnoty zadané uživatelem se nikdy nesmějí vkládat do textu dotazu skládáním řetězců: kdo by do formuláře napsal kus SQL, mohl by změnit význam dotazu (SQL injection, jedna z nejčastějších zranitelností webů). Obranou jsou parametrizované dotazy, kde se dotaz a data posílají databázi odděleně, a oprávnění, která aplikaci dovolí jen to, co nutně potřebuje.SQL injection, parameterized query

# správně: hodnota jde odděleně jako parametr, nikdy ne vlepená do textu dotazu
cur.execute("SELECT jmeno FROM studenti WHERE trida = ?", (trida,))

Pro data, která se do tabulek nehodí, vznikly databáze NoSQL: dokumentové (záznamy jako stromy JSON), klíč–hodnota (obří hašovací tabulky), grafové (vztahy jako hrany) a sloupcové pro analytiku. Distribuované databáze naráží na větu CAP (Brewer 2000, důkaz Gilbert a Lynch 2002): při výpadku spojení mezi servery musí systém volit mezi konzistencí a dostupností. Statistické zpracování velkých dat rozebírá průvodce Statistika a modely.NoSQL, CAP theorem

10.8Procvičení

11.1Turingův stroj

David Hilbert v roce 1928 položil otázku (Entscheidungsproblem), zda existuje mechanický postup, který o každém matematickém tvrzení rozhodne, zda je dokazatelné. Aby na ni šlo odpovědět, bylo třeba přesně definovat „mechanický postup“. Alan Turing (1936) navrhl abstraktní stroj, který napodobuje počtáře s tužkou: nekonečnou pásku rozdělenou na políčka, hlavu, která čte a píše po jednom políčku, a konečnou množinu stavů „mysli“.Turing machine, Entscheidungsproblem

Formálně (Sipser) je Turingův stroj sedmice \((Q, \Sigma, \Gamma, \delta, q_0, q_{\text{acc}}, q_{\text{rej}})\): konečná množina stavů \(Q\), vstupní abeceda \(\Sigma\), pásková abeceda \(\Gamma \supseteq \Sigma \cup \{\_\}\), přechodová funkce \(\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}\), počáteční stav a přijímající a zamítající stav. Stroj přijme vstup, když dojde do \(q_{\text{acc}}\), zamítne ho v \(q_{\text{rej}}\) – nebo může běžet donekonečna. Jazyk je rozhodnutelný, když ho rozpoznává stroj, který se na každém vstupu zastaví.decidable language, configuration

11.2Church–Turingova teze

Ve stejném roce popsal Alonzo Church jiný model výpočtu, λ-kalkul, a brzy se ukázalo, že oba modely – i všechny později navržené (stroje RAM, rekurzivní funkce, běžné programovací jazyky) – spočítají přesně tytéž funkce. Church–Turingova teze tvrdí, že vše, co lze spočítat jakýmkoli mechanickým postupem, spočítá Turingův stroj. Je to teze, ne věta: „mechanický postup“ je intuitivní pojem. Jazyk nebo systém, který umí simulovat Turingův stroj, se nazývá Turingovsky úplný.Church–Turing thesis, Turing complete

Turing také sestrojil univerzální stroj, který na vstupu dostane popis jiného stroje a jeho vstup a odsimuluje ho. To je teoretický předobraz počítače s uloženým programem z kapitoly 3: jeden stroj, mnoho programů.universal Turing machine

11.3Problém zastavení

Problém zastavení: dostaneme program \(P\) a vstup \(x\); zastaví se \(P\) na \(x\)? Turing dokázal, že žádný algoritmus tuto otázku nerozhoduje pro všechny dvojice \((P, x)\).halting problem, undecidability

1. Předpokládejme, že existuje program H(P, x), který vždy skončí a vrátí ano, právě když \(P\) se na \(x\) zastaví.
2. Sestrojíme program D(P): zavolá H(P, P); vyjde-li ano, zacyklí se; vyjde-li ne, skončí.
3. Co udělá D(D)? Zastaví-li se, pak H(D, D) vrátilo ano a D se zacyklilo – spor. Nezastaví-li se, vrátilo H ne a D skončilo – spor.
4. Předpoklad byl chybný: program H neexistuje.

Je to diagonální argument, stejný trik, kterým Cantor dokázal, že reálných čísel je víc než přirozených. Z problému zastavení plyne mnoho dalších nerozhodnutelných otázek. Riceova věta (1953) říká, že každá netriviální vlastnost chování programů je nerozhodnutelná: zda program někdy vypíše „ahoj“, zda počítá stejnou funkci jako jiný program, zda obsahuje nekonečný cyklus.diagonal argument, Rice's theorem

11.4Třídy P a NP

Složitost (kapitola 6) třídí rozhodnutelné úlohy podle času. Uvažujeme rozhodovací úlohy s odpovědí ano/ne. Třída P obsahuje úlohy řešitelné deterministickým algoritmem v polynomiálním čase \(O(n^{k})\): řazení, nejkratší cesta, test prvočíselnosti (algoritmus AKS, 2002). Třída NP obsahuje úlohy, u kterých lze kladnou odpověď ověřit v polynomiálním čase, dostaneme-li vhodný certifikát: u sudoku vyplněnou mřížku, u obchodního cestujícího okruh kratší než zadaná mez. Každá úloha z P je v NP (certifikát ani nepotřebujeme), tedy \(\mathrm{P} \subseteq \mathrm{NP}\).decision problem, class P, class NP, certificate, verifier

Zda \(\mathrm{P} = \mathrm{NP}\), tedy zda je hledání řešení vždy jen polynomiálně těžší než jeho kontrola, je nejslavnější otevřená otázka informatiky. Clayův matematický institut ji v roce 2000 zařadil mezi sedm problémů tisíciletí s odměnou milion dolarů. Většina odborníků se domnívá, že \(\mathrm{P} \ne \mathrm{NP}\).

11.5Redukce a NP-úplnost

Úloha \(A\) se polynomiálně redukuje na úlohu \(B\) (\(A \le_p B\)), když každou instanci \(A\) umíme v polynomiálním čase přeložit na instanci \(B\) se stejnou odpovědí. Pak je \(B\) aspoň tak těžká jako \(A\): kdo umí rychle \(B\), umí rychle i \(A\). Úloha je NP-těžká, když se na ni redukuje každá úloha z NP, a NP-úplná, když je navíc sama v NP.polynomial-time reduction, NP-hard, NP-complete

Stephen Cook (1971) a nezávisle Leonid Levin (1973) dokázali, že NP-úplná je splnitelnost logických formulí (SAT): dá se proměnným přiřadit pravda/nepravda tak, aby formule platila? Richard Karp (1972) pak redukcemi ukázal NP-úplnost 21 dalších úloh, mezi nimi kliky, pokrytí vrcholů, Hamiltonovy kružnice a barvení grafu. Dnes jich známe tisíce. Kdyby jediná z nich měla polynomiální algoritmus, platilo by \(\mathrm{P} = \mathrm{NP}\).Cook–Levin theorem, SAT

11.6Co dělat s těžkými úlohami

• Malé instance řešit přesně. Prohledávání s ořezáváním (branch and bound) zvládne i stovky prvků, i když v nejhorším případě exponenciálně.
• Aproximace se zárukou. Pokrytí vrcholů jde v polynomiálním čase najít nejvýš dvakrát větší než optimum; pro obchodního cestujícího s trojúhelníkovou nerovností dává Christofidesův algoritmus (1976) okruh nejvýš o polovinu delší.
• Heuristiky bez záruky, ale prakticky dobré: hladové volby, lokální vylepšování, simulované žíhání.
• Speciální případy bývají snadné: barvení dvěma barvami je v P, třemi NP-úplné; SAT s klauzulemi o dvou proměnných je v P.
• Řešiče SAT zvládají průmyslové formule s miliony proměnných, protože skutečné instance mají strukturu, kterou nejhorší případ nemá.

Těžkost je někdy výhoda: kryptografie (kapitola 9) stojí na úlohách, které považujeme za těžké. Rozklad na prvočinitele ale není známý jako NP-úplný a kvantový počítač by ho zvládl (Shor); proto se pro postkvantové šifry hledají úlohy jiného typu.

11.7Procvičení

12.1Co je umělá inteligence

Alan Turing (1950) navrhl místo otázky „umí stroj myslet?“ zkoušku: pozná tazatel v písemném rozhovoru, zda odpovídá člověk, nebo stroj? Obor dostal jméno na letní dílně v Dartmouthu (1956). Učebnice Russella a Norviga definuje umělou inteligenci jako studium agentů, kteří vnímají prostředí a jednají tak, aby co nejlépe splnili svůj cíl. Obor prošel vlnami: symbolické uvažování a prohledávání, expertní systémy s ručně psanými pravidly, strojové učení z dat a od 2010. let hluboké neuronové sítě. Otázky vědomí a porozumění strojů rozebírá průvodce Filozofie.artificial intelligence, Turing test, rational agent

12.2Prohledávání a hry

Mnoho úloh lze formulovat jako hledání cesty ve stavovém prostoru: stavy jsou vrcholy grafu, tahy hrany (kapitola 8). U her pro dva hráče se prohledává herní strom. Minimax: hráč MAX volí tah s nejvyšší hodnotou, protivník MIN s nejnižší, hodnoty se počítají od listů (výhra +1, remíza 0, prohra −1) nahoru.state space, game tree, minimax

Alfa-beta ořezávání přeskakuje větve, které výsledek nemohou ovlivnit; výsledek je stejný jako u úplného minimaxu. Při dobrém pořadí tahů zmenší počet prohledaných pozic zhruba na odmocninu (Knuth a Moore, 1975). Celý strom piškvorek 3 × 3 má 549 946 uzlů a 255 168 různých partií; s alfa-beta ořezáváním (tahy zkoumané v pořadí políček) stačí k vyhodnocení prázdné desky 18 297 uzlů. Výsledek: při bezchybné hře obou stran remíza.alpha-beta pruning

U šachů Shannon (1950) odhadl strom zhruba na \(10^{120}\) partií, takže úplné prohledání nepřichází v úvahu. Programy prohledávají do omezené hloubky a pozice hodnotí hodnoticí funkcí. V roce 1997 porazil šachový počítač mistra světa Garriho Kasparova; v roce 2016 porazil program pro hru go Lee Se-dola, tentokrát díky kombinaci prohledávání s neuronovými sítěmi naučenými na milionech partií.evaluation function

12.3Strojové učení stručně

Strojové učení hledá pravidla z dat místo z ručně psaného kódu. Při učení s učitelem má každý příklad správnou odpověď (obrázek a popisek), při učení bez učitele hledá model strukturu sám (shluky), při zpětnovazebním učení se agent učí z odměn. Úspěšnost se měří na testovacích datech, která model při učení neviděl; model, který si zapamatoval trénovací data a na nových selhává, je přeučený.machine learning, supervised, unsupervised, reinforcement learning, overfitting

Perceptron se učí jednoduchým pravidlem: když se splete, přičte k vahám \(\eta\,(y - \hat y)\,x\). Novikoff (1962) dokázal, že na lineárně oddělitelných datech pravidlo po konečném počtu chyb najde oddělující přímku. Minsky a Papert (1969) upozornili, že funkci XOR jediný perceptron nespočítá, protože body (0, 1), (1, 0) nejde oddělit od (0, 0), (1, 1) přímkou. Řešením jsou vícevrstvé sítě s nelineárními funkcemi, které se učí zpětným šířením chyby (Rumelhart, Hinton a Williams, 1986).perceptron, perceptron convergence theorem, backpropagation

12.4Velké jazykové modely v principu

Jazykový model přiřazuje pravděpodobnost pokračování textu. Text se rozdělí na tokeny (slova nebo jejich části) a model se učí odhadovat rozdělení pravděpodobnosti dalšího tokenu podle předchozích. Generuje se opakovaně: vybere se token (podle pravděpodobností a teploty), připojí se k textu a postup se opakuje. Dnešní velké jazykové modely používají architekturu transformer (Vaswani a kol., 2017), jejíž mechanismus pozornosti umí při odhadu vážit vztahy mezi vzdálenými částmi textu. Mají miliardy parametrů a učí se nejdřív na obrovském množství textu (předtrénování), pak se dolaďují na příkladech a podle hodnocení lidí.language model, token, transformer, attention, pretraining, fine-tuning

12.5Jak se dělá software

Software se nevytváří jen psaním kódu. Životní cyklus zahrnuje sběr požadavků (co má systém dělat), návrh (z jakých částí se skládá), implementaci, testování, nasazení a dlouhou údržbu. Starší vodopádový model procházel fázemi postupně jednou; dnes převládají agilní přístupy (manifest agilního vývoje, 2001), které dodávají funkční software v krátkých iteracích a průběžně ho upravují podle zpětné vazby.software engineering, requirements, agile

Správa verzí uchovává celou historii změn: každá uložená změna (commit) má autora, čas a popis, k jakékoli starší verzi se lze vrátit. Nejrozšířenější je svobodný systém Git (2005). Nová funkce se vyvíjí ve větvi, po kontrole kódu kolegou (code review) se sloučí do hlavní větve.version control, commit, branch, merge, code review

Testování má úrovně: jednotkové testy ověřují jednotlivé funkce (jako assert v kapitole 4), integrační jejich spolupráci, systémové celek a akceptační splnění požadavků zákazníka. Testy se spouštějí automaticky při každé změně (průběžná integrace). Dijkstra připomínal, že testy mohou dokázat přítomnost chyb, nikdy jejich nepřítomnost; kde jde o životy, doplňují se formálními důkazy správnosti.unit, integration, system, acceptance testing; continuous integration

12.6Etika a odpovědnost

Software rozhoduje o úvěrech, přijetí na školu, lékařské péči i o tom, co lidé vidí na sociálních sítích. Proto se od něj očekává:

• Ochrana soukromí: sbírat jen nezbytné údaje a chránit je; v EU to vyžaduje obecné nařízení o ochraně osobních údajů (GDPR, nařízení (EU) 2016/679).
• Férovost: model naučený na zkreslených datech zkreslení zopakuje (například horší rozpoznávání skupin, které byly v datech málo zastoupené). Je třeba to měřit a opravovat.
• Průhlednost a dohledatelnost: člověk má vědět, že jedná se strojem, a rozhodnutí má jít vysvětlit a napadnout.
• Odpovědnost a bezpečnost: za systém odpovídají lidé, kteří ho navrhli a nasadili; profesní zásady shrnuje například etický kodex ACM (2018).

Evropská unie upravuje umělou inteligenci nařízením (EU) 2024/1689 (AI Act), které třídí systémy podle rizika. Zákazy nepřijatelných praktik platí od 2. 2. 2025, pravidla pro modely pro obecné účely od 2. 8. 2025; povinnosti pro vysoce rizikové systémy byly změnou z roku 2026 odloženy na 2. 12. 2027, respektive 2. 8. 2028 (stav k 13. 10. 2026, podrobnosti v příloze C). Ekonomické dopady digitálních platforem rozebírá průvodce Ekonomie, filozofické otázky odpovědnosti průvodce Filozofie.GDPR, AI Act, algorithmic fairness, accountability

12.7Procvičení