Úvod Teorie čísel a kombinatorika Řetězce Geometrie Různé algoritmické problémy Úvod Teorie čísel a kombinatorika Řetězce Geometrie Obsah 1 Úvod 2 Teorie čísel a kombinatorika Největší společný dělitel Prvočísla Náhodná čísla Další problémy 3 Řetězce Podřetězce Komprese textu 4 Geometrie Základy Konvexní obal Triangulace Voroného diagram Úvod Teorie čísel a kombinatorika Řetězce Geometrie O přednášce směsice algoritmických problémů z různých oblastí klasické problémy (,,co by měl informatik znát ) mnoho aplikací zajímavé algoritmy, pěkné myšlenky Úvod Teorie čísel a kombinatorika Řetězce Geometrie Teorie čísel a kombinatorika problémy ,,nad čísly vstupem, výstup: většinou čísla jen několik zato mohou být ,,dlouhá Úvod Teorie čísel a kombinatorika Řetězce Geometrie Největší společný dělitel Největší společný dělitel vstup: přirozená čísla a, b výstup: největší společný dělitel a, b příklad: 180, 252 Jak na to? Úvod Teorie čísel a kombinatorika Řetězce Geometrie Největší společný dělitel Naivní algoritmus I projít všechny čísla od 1 do min(a, b) pro každé vyzkoušet, zda dělí a i b vzít největší Úvod Teorie čísel a kombinatorika Řetězce Geometrie Největší společný dělitel Naivní algoritmus II ,,školní algoritmus najít všechny dělitele čísel a, b projít dělitele, vybrat společné, vynásobit příklad: 180 = 22 32 5 504 = 23 32 7 NSD = 22 32 = 36 Úvod Teorie čísel a kombinatorika Řetězce Geometrie Největší společný dělitel Euclidův algoritmus: základ základní myšlenka: pokud a > b, pak: NSD(a, b) = NSD(a - b, b) příklad: krok a b 1 504 180 2 324 180 3 180 144 4 144 36 5 108 36 6 72 36 7 36 36 8 36 0 Úvod Teorie čísel a kombinatorika Řetězce Geometrie Největší společný dělitel Operace modulo modulo = zbytek po dělení příklady: 13 mod 5 = 3 28 mod 4 = 0 14 mod 3 = 2 18 mod 7 = ?? 29 mod 13 = ?? Úvod Teorie čísel a kombinatorika Řetězce Geometrie Největší společný dělitel Euclidův algoritmus: vylepšení vylepšená základní myšlenka: pokud a > b, pak: NSD(a, b) = NSD(a mod b, b) krok a b 1 504 180 2 180 144 3 144 36 5 36 36 6 36 0 Úvod Teorie čísel a kombinatorika Řetězce Geometrie Největší společný dělitel Euclidův algoritmus: pseudokód odčítací varianta, bez rekurze function gcd(a, b) if a = 0 return b while b != 0 if a > b a := a - b else b := b - a return a Úvod Teorie čísel a kombinatorika Řetězce Geometrie Největší společný dělitel Euclidův algoritmus: pseudokód modulo varianta, rekurzivně function gcd(a, b) if b = 0 return a else return gcd(b, a mod b) Úvod Teorie čísel a kombinatorika Řetězce Geometrie Největší společný dělitel Příklady 160, 75 57, 33 Úvod Teorie čísel a kombinatorika Řetězce Geometrie Prvočísla Prvočísla dělitelné jen 1 a sebou samým předmět zájmu matematiků od pradávna, cca od 70. let (moderní kryptologie) i důležité aplikace problémy s prvočísly: výpis (počet) prvočísel v intervalu test prvočíselnosti rozklad na prvočísla (hledání dělitelů) Úvod Teorie čísel a kombinatorika Řetězce Geometrie Prvočísla Eratosthenovo síto problém: výpis prvočísel od 2 do n algoritmus: opakuj: označ další neškrknuté číslo na seznamu jako prvočíslo všechny násobky tohoto čísla vyškrkni Úvod Teorie čísel a kombinatorika Řetězce Geometrie Prvočísla Test prvočíselnosti Problém Vstup: číslo n Výstup: ANO/NE (je/není prvočíslo) Úvod Teorie čísel a kombinatorika Řetězce Geometrie Prvočísla Test prvočíselnosti: naivní algoritmus zkoušíme všechny možné dělitele od 2 do n - 1 vylepšení: dělíme pouze lichými čísly dělíme pouze čísly tvaru 6k 1 dělíme pouze do n Úvod Teorie čísel a kombinatorika Řetězce Geometrie Prvočísla Test prvočíselnosti: chytřejší algoritmy náhodnostní algoritmy polynomiální deterministický algoritmus (objeven 2002) (vysoce) nad rámec tohoto kurzu umíme to dělat rychle Úvod Teorie čísel a kombinatorika Řetězce Geometrie Prvočísla Rozklad na prvočísla rozklad na prvočísla = faktorizace naivní algoritmy: průchod všech možných dělitelů zlepšení podobně jako u testů prvočíslenosti chytřejší algoritmy: složitá matematika aktivní výzkumná oblast přesto to neumíme dělat rychle max cca 200 ciferná čísla Úvod Teorie čísel a kombinatorika Řetězce Geometrie Prvočísla Aplikace: asymetrická kryptologie Úvod Teorie čísel a kombinatorika Řetězce Geometrie Prvočísla Asymetrická kryptologie: realizace jednosměrné funkce jednoduché vypočítat jedním směrem obtížné druhým (inverze) ilustrace: míchání barev RSA (Rivest, Shamir, Adleman) algoritmus jednosměrná funkce: násobení prvočísel (inverze = faktorizace) veřejný klíč: součin velkých prvočísel bezpečnost nikdo neumí provádět efektivně faktorizaci využití modulární aritmetiky, Eulerovy věty, ... Úvod Teorie čísel a kombinatorika Řetězce Geometrie Náhodná čísla Náhodná čísla vstup: ,,semínko výstup: posloupnost ,,náhodných čísel ,,pseudo-náhodná čísla ­ snaha, aby posloupnost měla charakteristiky co nejpodobnější reálným náhodným číslům hlavní žádoucí vlastnosti: uniformní distribuce, vzájemná nezávislost aplikace: numerické výpočty, simulace, kryptologie, ... Úvod Teorie čísel a kombinatorika Řetězce Geometrie Náhodná čísla Generování pseudo-náhodných čísel základní přístup: lineární kongruentní rovnice iterování rovnice typu: Xn+1 = (aXn + b) mod m Úvod Teorie čísel a kombinatorika Řetězce Geometrie Náhodná čísla Opravdu náhodná čísla random.org ­ atmosférický šum http://gamesbyemail.com/News/DiceOMatic Úvod Teorie čísel a kombinatorika Řetězce Geometrie Další problémy Matice násobení matic výpočet determinantu řešení lineárních rovnic (Gaussova eliminační metoda) Úvod Teorie čísel a kombinatorika Řetězce Geometrie Další problémy Lineární programování hledání přiřazení proměnným: splňujících systém lineárních nerovnic maximalizující lineární optimalizační funkci obecný problém, má mnoho konkrétních aplikací (grafy, optimalizace, ...) základní řešení: simplexový algoritmus Úvod Teorie čísel a kombinatorika Řetězce Geometrie Další problémy Kombinatorika generování (např. pro množinu {A, B, C, D}: permutací (ABCD, ABDC, ACBD, ...) kombinací, podmnožin (, A, B, C, D, AB, AC, ..) rozdělení (partitions) ((ABCD), (A, BCD), (A, B, CD), ..) Úvod Teorie čísel a kombinatorika Řetězce Geometrie Řetězce vstup: textový řetězec výstup: určitá informace o textu, zpracovaný text příklady aplikací: vyhledávání v ,,běžných textech (editory, prohlížeče) komprese souborů bioinformatika Úvod Teorie čísel a kombinatorika Řetězce Geometrie Podřetězce Nejdelší rostoucí úsek, podposloupnost Pozn. nikoliv text, ale posloupnost čísel, typem algoritmu se sem ale hodí Nejdelší rostoucí úsek vstup: posloupnost čísel výstup: nejdelší rostoucí úsek (po sobě jdoucí čísla) Nejdelší rostoucí podposloupnost vstup: posloupnost čísel výstup: nejdelší rostoucí podposloupnost (čísla nemusí jít po sobě) Úvod Teorie čísel a kombinatorika Řetězce Geometrie Podřetězce Nejdelší rostoucí úsek, podposloupnost příklad: 4, 1, 8, 6, 5, 11, 2, 4, 9, 12, 5, 13, 7, 8, 12, 10, 11 Úvod Teorie čísel a kombinatorika Řetězce Geometrie Podřetězce Nejdelší rostoucí úsek, podposloupnost příklad: 4, 1, 8, 6, 5, 11, 2, 4, 9, 12, 5, 13, 7, 8, 12, 10, 11 nejdelší rostoucí úsek: 2, 4, 9, 12 nejdelší rostoucí podposloupnost: 1, 2, 4, 5, 7, 8, 10, 11 Úvod Teorie čísel a kombinatorika Řetězce Geometrie Podřetězce Algoritmy nejdelší rostoucí úsek: jeden průchod pole, lineární složitost O(n) pamatuji si aktuální délku rostoucí podposloupnosti + dosavadní maximum nejdelší rostoucí podposloupnost: ,,dynamické programování pro každou pozici si pamatuji délku nejdelší podposloupnosti končící v tom místě přímočaře: kvadratická složitost O(n2) efektivní implementace O(n log n) Úvod Teorie čísel a kombinatorika Řetězce Geometrie Podřetězce Nejdelší společný podřetězec, podposloupnost vstup: dva řetězce s1, s2 výstup: nejdelší společný úsek/podposloupnost (rozdíl podobně jako u předchozího) příklad: BDCABA ABCBDAB Úvod Teorie čísel a kombinatorika Řetězce Geometrie Podřetězce Nejdelší společná podposloupnost Úvod Teorie čísel a kombinatorika Řetězce Geometrie Podřetězce Nejdelší společná podposloupnost ,,dynamické programování Úvod Teorie čísel a kombinatorika Řetězce Geometrie Komprese textu Komprese textu vstup: text výstup: bezeztrátová komprese (text lze rekonstruovat) aplikace: šetření místa (viz např. zip) příklad: dlouhý textový dokument, bitmapový obrázek jak byste komprimovali? Úvod Teorie čísel a kombinatorika Řetězce Geometrie Komprese textu Komprese textu: přístupy ,,Run-length encoding (RLE): nahrazení opakovaných výskytů stejného znaku např. bitmapový obrázek (statické) slovníkové metody statistické metody ­ kódování podle textu Úvod Teorie čísel a kombinatorika Řetězce Geometrie Komprese textu Kódování: příklad proměnlivá délka ­ kód musí být ,,bez-prefixový Úvod Teorie čísel a kombinatorika Řetězce Geometrie Komprese textu Huffmanovo kódování Úvod Teorie čísel a kombinatorika Řetězce Geometrie Komprese textu Huffmanovo kódování Úvod Teorie čísel a kombinatorika Řetězce Geometrie Geometrické algoritmy typicky problémy v rovině (případně 3D prostoru) vstupem množina bodů, složitějších objektů výstup body, objekty, splňující zadané požadavky kromě algoritmického nápadu často nutný i ,,geometrický vhled Úvod Teorie čísel a kombinatorika Řetězce Geometrie Základy Základní operace průsečík dvou úseček obsah trojúhelníku nad/pod test: bod vzhledem k přímce uvnitř test: bod vzhledem ke kruhu Úvod Teorie čísel a kombinatorika Řetězce Geometrie Základy Obsah polygonu vstup: polygon (ne nutně konvexní) výstup: obsah Úvod Teorie čísel a kombinatorika Řetězce Geometrie Základy Obsah polygonu vstup: polygon (ne nutně konvexní) výstup: obsah algoritmus: ,,diskrétní integrování Úvod Teorie čísel a kombinatorika Řetězce Geometrie Konvexní obal Konvexní obal vstup: množina bodů v rovině (souřadnice xi , yi ) výstup: uspořádaný seznam bodů tvořících konvexní obal Úvod Teorie čísel a kombinatorika Řetězce Geometrie Konvexní obal Graham scan: ilustrace Úvod Teorie čísel a kombinatorika Řetězce Geometrie Konvexní obal Graham scan: ilustrace Úvod Teorie čísel a kombinatorika Řetězce Geometrie Konvexní obal Jarvis march: ilustrace Úvod Teorie čísel a kombinatorika Řetězce Geometrie Triangulace Triangulace Úvod Teorie čísel a kombinatorika Řetězce Geometrie Triangulace Triangulace vstup: množina bodů, příp. polygon výstup: triangulace Úvod Teorie čísel a kombinatorika Řetězce Geometrie Triangulace Triangulace variace: Delaunay: ,,pěkné úhly (minimalizace maximálního úhlu) minimalizace vzdáleností 3D: trojúhelníky čtyřstěny aplikace: počítačová grafika algoritmy: konvexní polygon: přímočaré další variace postupně komplikovanější Úvod Teorie čísel a kombinatorika Řetězce Geometrie Voroného diagram Voroného diagram vstup: množina bodů výstup: rozdělení roviny na oblasti ,,ke kterému bodu je odsud nejblíž aplikace: vyhledávání umisťování nových bodů (např. restaurace) plánování cest (např. roboti) triangulace Úvod Teorie čísel a kombinatorika Řetězce Geometrie Voroného diagram Voroného diagram animace algoritmu: http://www.diku.dk/hjemmesider/studerende/duff/ Fortune/ Úvod Teorie čísel a kombinatorika Řetězce Geometrie Voroného diagram Shrnutí algoritmické problémy z různých oblastí teorie čísel, řetězce, geometrické algoritmy přehled: o co v problémech jde myšlenky základních algoritmů