C2142 Návrh algoritmů pro přírodovědce Tomáš Racek Financováno Evropskou unií NextGenerationEU NÁRODNÍ PLÁN OBNOVY Wh 1. Od problému k algoritmu Problém, algoritmus Problém - nerozřešená, sporná otázka, kterou je třeba řešit. Příklady problémů: • Kolik je třetí odmocnina z 27? • Bude zítra pršet? • HW = EW • Co si vzít na sebe do divadla? Algoritmus je funkce mezi vstupem a výstupem reprezentována konečným způsobem v nějakém formalismu. Ne každý problém lze algoritmicky řešit. Potřeba formalismu Přirozený jazyk trpí často nejednoznačností - dvojsmysly. • Návrh putuje k Ústavnímu soudu v době, kdy je neúplný. • Máme jen velvyslance prezidenta. Formální jazyk má přesně danou syntaxi (strukturu) a sémantiku (význam). • matematický zápis (př. Vx e A : x < 0) • značkovací jazyky (př. HTML, XML,...) • programovací jazyky (př. C/++, Python, Java, C#,...) def fact(n): return n * fact(n -1) if n > 0 else 1 Hledání počátku replikace jednoduchých bakterií Biologický problém. Nalezněte část genomu, kde začíná replikace DNA (angl. origin of replication, oriC). Způsoby řešení • biolog - laboratoř • informatik - počítač Vstup: Genom (řetězec znaků A, C, G, T) Výstup: Pozice počátku replikace v genomu. Je toto informatický správně formulovaný problém? Problémy specifikace Vstup: Génom (řetězec znaků A, C, G, T) Výstup: Pozice počátku replikace v genomu. Počátek replikace (oriC) není užitečně definován —> potřeba dalších biologických informací. Další vlastnosti: • většinou několik stovek nukleotidů dlouhá oblast genomu • obsahuje netriviální množství tzv. DnaA box (= krátké oblasti, na které se naváže DnaA protein a spustí tak replikaci) • typicky např. 9 nukleotidů • liší se pro každý organismus Transformace problému Problém nalezení oriC převedeme na hledání DnaA boxes. Oblast s jejich největším výskytem bude pak ukazovat na oriC. (1) Zjednodušený problém. Nalezněte v textu řetězce délky ks nejvyšším počtem výskytů (DnaA box). (2) Upravený problém. Nalezněte v textu řetězce délky k (DnaA box) v oblasti délky n ( oriC) s minimálním počtem výskytů t. Je náš zvolený přístup perspektivní? Pravděpodobnost, že existuje řetězec délky 9, který se vyskytuje v oblasti dlouhé 500 nukleotidů alespoň 3krát je asi 1/1300. (1) Hledání nejčastějších slov v textu - řešení Užitečným nástrojem pro řešení problému je dekompozice - rozložení problému na menší, lépe zvládnutelné jednotky. pattern_count(text, pattern) • pomocná funkce • vrací počet výskytů řetězce pattern v řetězci text. frequent_words(text, k) 1. Pro každý podřetězec délky k řetězce text spočítej jeho výskyt pomocí funkce pattern_count 2. Urči nejvyšší nalezenou četnost 3. Vrať řetězce s touto nejvyšší četností (1) Hledání nejčastějších slov v textu def pattern_count(text, pattern): count = 0 for i in range(0,1 + len(text) - len(pattern)): if text[i: i + len(pattern)] == pattern: count += 1 return count def frequent_words(text, k): counts = dict() frequent_patterns = set() for i in range(0, len(text) - k + 1): pattern = text[i: i + k] counts[pattern] = pattern_count(text, pattern) max_count = max(counts.values()) for (pattern, count) in counts.items(): if count == max_count: frequent_patterns.add(pattern) return frequent_patterns Vybrané poznámky ze softwarového inženýrství "Always code as if the guy who ends up maintainingyour code will be a violent psychopath who knows where you live." John Woods Pro naše účely je forma uvedených algoritmů dostačující, v praxi je vhodné doplnit zejména: • komentáre objasňující zvolený postup, připadne myšlenkové obtížnější časti algoritmu • kontroly, zda jsou vstupní data v pořádku (1) Upravená verze hledání nejčastějších slov def frequent_words(text, k): """Find the most frequent words of the specified length""" counts = dict() frequent_patterns = set() if k < 1: raise Exception(The length of the pattern has to be at least 1') # Find the frequency for each pattern in the text for i in range(0, len(text) - k + 1): pattern = text[i: i + k] counts[pattern] = pattern_count(text, pattern) # Select the patterns with the highest occurrence max_count = max(counts.values()) for (pattern, count) in counts.items(): if count == max_count: frequent_patterns.add(pattern) return frequent_patterns (2) Hledání nejčastějších slov v podřetězci (2) Upravený problém. Nalezněte v textu řetězce délky k (DnaA box) v oblasti délky n ( oriC) s minimálním počtem výskytů t. def frequent_words_within_region(text, k, n, t): frequent_patterns = set() for i in range(0, len(text) - n + 1): text_region = text[i: i + n] counts = dict() for j in range(0, len(text_region) - k + 1): pattern = text_region[j: j + k] counts[pattern] = pattern_count(text_region, pattern) for (pattern, count) in counts.items(): if count >= t: frequent_patterns.add(pattern) return frequent_patterns Korektnost Korektnost algoritmu. Návrh/implementace odpovídá specifikaci (zadání). Metody: • testování* • matematický důkaz • ověření, že korektní vstupní data budou algoritmem transformována na správná výstupní • formální verifikace • ověření, zda model systému splňuje zadanou vlastnost • stejná míra jistoty jako u matematického důkazu • lze algoritmizovat • použitelná pouze pro velmi malé systémy Testování Testování. Levný a rychlý nástroj pro ověření základní funkcionality. Co testovat? • obvyklý běh • krajní hodnoty • zakázané hodnoty Motto: "Testing shows the presence, not the absence of bugs." Edsger W. Dijkstra Proč tomu tak je? Escherichia coli Genom E. coli - asi 4,6 milionu nukleotidů (níže prvních 0,00313 %): AG CTTTTC ATTCTG ACTG CAACG G G CAATATGTCTCTGTGTG GATTAA AAAAAG AGTGTCTG ATAG C AG CTTCTG AACTG GTTACCTG CCGTGAGT AAATTAAAATTTTATTGACTTAGGTCACTAAATACTTTAACCAATATA Praktický test (1) Zahřívací problém. Nalezněte nejčastější řetězce délky 9 v rámci prvních 5000 nukleotidů genomu E. coli. • použijeme funkci frequent_words • čas výpočtu asi 6 s ACCATTACC TGGCGATGA CACCATTAC AACTGAAAG TGATGAAGA (2) Kompletní genom E. coli Zopakujte (1) pro celýgenom E. coli. • téměř 10OOkrát větší problém než (1) • odhad času výpočtu 1000 • 6 s = 6000 s < 7200 s = 2 h • realita? Vylepšení o další biologické poznatky 1 Náš vstupní řetězec představuje pouze jedno ze dvou navzájem reverzně komplementárních vláken genomu. Komplementární báze: • A~T • C~ G Např. reverse_complement(ACCCTG) = CAGGGT. Závěr. Při hledání nejčastějších podřetězců je potřeba vzít do úvahy i druhý řetězec. Vylepšení o další biologické poznatky 2 V řetězci DNA může dojít k mutacím (např. záměně jednoho nukleotidu za jiný). Hammingova vzdálenost. Počet pozic, na kterých se dva řetězce stejné délky liší. Př. Seznam všech řetězců (ze znaků A, C, G, T), které mají Hammingovu vzdálenost od řetězce AAA rovnu nejvýše 1: GAA ACA CAA AAA AAC ATA AGA TAA AAG AAT Závěr. Při hledání nejčastějších podřetězců zohledníme i jejich blízké (co do Hammingovy vzdálenosti) sousedy. 2. Úvod do složitosti Hledání n ej častej š ich slov - frequent_words Zadání. Nalezněte v textu řetězce délky k s nejvyšším počtem výskytu. frequent_words(text, k) 1. Pro každý podřetězec délky k řetězce text spočítej jeho výskyt pomocí funkce pattern_count(text, pattern) 2. Urči nejvyšší nalezenou četnost 3. Vrať řetězce s touto nejvyšší četností Praktický test. • krátké řetězce - frequent_words uspokojivě funguje • dlouhé řetězce - nepoužitelné, čas výpočtu neodpovídá odhadu frequent_words - doba výpočtu Pozorování • doba výpočtu je úměrná velikosti vstupních dat • závislost není nutně lineární - výpočet na 10OOkrát větší úloze nemusí trvat 1000krát déle • na různých strojích/architekturách různé časy výpočtu • Thinkpad T480s: 6 s • Thinkpad T430s: 7 s • Thinkpad X200s: 14 s • Desktop (Ryzen 3600): 3 s Důsledek (1). Nutná hlubší analýza frequent_words. Důsledek (2). Porovnání náročnosti algoritmů podle času výpočtu není vhodné, potřebujeme aparát nezávislý na konkrétním stroji/architektuře/implementaci. Složitost Složitost algoritmu. Zaveďme složitost algoritmu jako funkci f{n), kde n je velikost vstupu. Návrh. f(n) určuje počet jednoduchých operací daného algoritmu pro vyřešení problému o velikosti n. • jednoduché operace « instrukce CPU (např. sečtení nebo porovnání dvou čísel, AND/OR,...) • řešení nezávislé na architektuře Důsledek. Porovnání efektivity algoritmů lze zjednodušeně převést na porovnání jejich složitostí. Asymptotická složitost - definice Formální definice 0(g) = {/ | 3c e ]R+, 3n0 e N : Vn > n0 : 0 < f(n) < c • g(n)} f e 0(g) čteme „f roste asymptoticky nejvýše tak rychle jako g". Význam konstant c rozdíl pouze v multiplikativní konstantě nepovažujeme za významný, tj. ztotožňujeme např. n2 a 4n2 no vztah nemusí platit pro prvních n0 čísel Poznámka. Analogicky lze definovat další množiny: • / e Q(g) - / roste asymptoticky alespoň tak rychle jako g • / e ®(g) " / roste asymptoticky právě tak rychle jako g Asymptotická složitost - příklady Rychlost růstu funkcí log n «: n «: n log n «: n2 «: 2n «: n! pro n —> oo Příklady Funkce Složitostní třída Pojmenování 2142 (9(1) konstantní 21ogn + 4 <9(logn) logaritmická 0.5n + logn <9(n) lineární n2 - Wn 0(n2) kvadratická 6n3 0(n3) kubická 2n-l 0(2n) exponenciální Poznámka. Ověření, zdali / e 0(g), lze provést výpočtem limity limn^oo f (n)/g(n). Složitost problému Cíl. Snaha o nalezení efektivních algoritmů pro daný problém. Otázka. Lze zrychlovat pořád, nebo existuje nějaký dolní limit? Složitost problému • minimální počet operací potřebný pro vyřešení libovolné instance problému • nutno odvodit teoreticky —> mnohdy netriviální • odpovídá složitosti optimálního algoritmu pro daný problém Jak ale poznám optimální algoritmus? Srovnejme odhady složitosti problému ¥{ a složitosti algoritmů řešící tento problém: Pi(n) < ... < Pk(n) < ^li(ft) < ... < J[m{n) 3\ je optimální algoritmus, pokud J[{n) = ^(n). Složitost problému - příklady Nalezení nejmenšího prvku pole • je nutné projít všechny prvky pole - Q(n) operací • algoritmus se složitostí 0(n) jistě existuje -> složitost problému (= složitost optimálního algoritmu) je lineární Násobení matic • potřeba Q(n2) operací • naivní algoritmus - 0(n3) • Strassenův algoritmus - 0(nlo&7) = 0(n2'81) • aktuálně nejlepší algoritmus (2014) - 0(n2'372-) • nalezení optimálního algoritmu je otevřený problém Prostorová složitost Prostorová složitost. Vedle časové náročnosti algoritmů lze určit i množství paměti, které algoritmus potřebuje pro svůj výpočet. • velikost vstupních (a výstupních) dat neuvažujeme • vyjadřujeme také (9-notací In situ algoritmus vyžaduje navíc pouze 0(1) paměti. • výpočet průměrné hodnoty prvků v poli • naivní násobení matic Otázka. Je lepší in situ algoritmus s časovou složitostí 0(n2) než algoritmus s časovou složitostí 0(n log n) a prostorovou složitostí 0(n)l Vztah mezi časem a prostorem Teze. Někdy lze snížit časovou složitost algoritmu zvýšením jeho prostorové složitosti (a naopak). t prostor i čas • softwarová cache • předpočítání (mezi)výsledků T čas i prostor • komprese • zvýšení abstrakce Složitost v praxi Tabulka časů výpočtu algoritmů o složitostech logn, n, n2, 2n a pro vstup velikosti 10, 20, 50 a 1000. Předpokládejme, že jedna iterace algoritmu trvá 1/ís. 10 20 50 1000 log n 0,000001 s 0,000001 s 0,000002 s 0,000003 s n 0,00001 s 0,00002 s 0,00005 s 0,001 s 2 0,0001 s 0,0004 s 0,0025 s 1 s 2^ 0,001024 s 1,048576 s 35,7 let 3,4-10287 let Poznámka. Stáří vesmíru je odhadováno na 13,8 • 109 let. pattern_count - analýza def pattern_count(text, pattern): count = 0 for i in range(0,1 + len(text) - len(pattern)): if text[i: i + len(pattern)] == pattern: count += 1 return count Pozorování • procházíme celkem \text\ - \pattern\ + 1 možných umístění • každé porovnání dvou řetězců obnáší nejvýše \pattern\ porovnání jednotlivých znaků Závěr. Počet kroků, které vykoná funkce pattern_count, lze vyjádřit jako 0(\pattern\ • (\text\ - \pattern\ + 1)). frequent_words - analýza I def frequent_words(text, k): counts = dict() frequent_patterns = set() for i in range(0, len(text) - k + 1): pattern = text[i: i + k] counts[pattern] = pattern_count(text, pattern) max_count = max(counts.values()) for (pattern, count) in counts.items(): if count == max_count: frequent_patterns.add(pattern) return frequent_patterns Pozorování • počet volání pattern_count je \text\ - k + l • další příkazy nejsou určující pro dobu běhu frequent_words - analýza II Složením předchozích informací dostáváme: frequent_words(text, k) • složitost funkce pattern_count je 0(\pattern\ • (\text\ - \pattern\ + 1)) • počet volání pattern_count je \text\ -k + 1 • platí k = \pattern\ • počet kroků celkem: k • (\text\ -k + l)- (\text\ -k+l) = k- (\text\ -k+l)2 V praxi platí k «: \text\, asymptotická složitost funkce frequent_words je tedy 0(k- \text\2). frequent_words - praxe Měření. Doba výpočtu funkce frequent_words(text, k) pro k = 9 a \text\ = {1000,..., 90001. 1000 2000 3000 4000 5000 6000 7000 8000 9000 Pozorování. Naměřená data lze úspěšně proložit parabolou, což odpovídá odhadnuté složitosti 0(k- \text\2). Hledání nejčastějších slov v textu Dosavadní řešení. Jsme schopni navrhnout a implementovat algoritmus se složitostí 0(k • \text\2). Zásadní otázka. Jde to i lépe? Alternativní návrh. Počítání četností podřetězců při průchodu textem 1. Procházej vstupní text postupně po podřetězcích délky k 1.1 Pokud se konkrétní podřetězec vyskytl poprvé, nastav jeho četnost na 1, jinak ji zvyš o 1 2. Urči nejvyšší nalezenou četnost 3. Vrať řetězce s touto nejvyšší četností faster_frequent_words Jak ukládat pro každý řetězec jeho četnost? • počet různých řetězců délky fc z písmen A, C, G, T je 4fc • každému tomuto řetězci lze přiřadit číslo od 0 do 4k - 1 Příklad pro k = 3: AAA -> 0, AAC -> 1,AAG -> 2,...,TTT -> 63 Příklad převodu řetězce na číslo. A -> 0, C -> 1, G -> 2, T -> 3. ACCTG -> A-^ + C-^ + C-ť + T-^ + G^0 ACCTG -> 0 + 64 + 16 + 12 + 2 ACCTG -> 94 Implementace. Vytvořím pole o velikosti 4k, kde budu ukládat četnosti jednotlivých ■v . -v O retezcu. Převod řetězce na číslo - implementace def pattern2number(pattern): characters = "ACGT" if pattern =="": return 0 else: return 4 * pattern2number(pattern[:-1]) \ + characters.index(pattern[-1:]) def number2pattern(number, k): characters = "ACGT" if k == 0: return"" else: divisor = 4** (k-1) return characters[number// divisor] \ + number2pattern(number % divisor, k -1) faster_frequent_words - implementace def computing_frequencies(text, k): frequency_array = [0] * (4 ** k) for i in range(len(text) - k + 1): pattern = text[i: i + k] frequency_array[pattern2number(pattern)] += 1 return frequency_array def faster_frequent_words(text, k): frequent_patterns = set() frequency_array = computing_frequencies(text, k) max_count = max(frequency_array) for i in range(0, 4 ** k): if frequency_array[i] == max_count: frequent_patterns.add(number2pattern(i, k)) return frequent_patterns Složitost faster_frequent_words Složitost jednotlivých fází algoritmu • inicializace pole četností 0(4k) • převod řetězce na číslo (a naopak) 0(k) • průchod vstupním textem, počítání četností 0(k • (\text\ - k + 1)) • nalezení nejvyšší četnosti 0(4k) • výběr řetězců s nejvyšší četností 0(k • 4fc) Celková složitost faster_frequent_words. Po úpravě dostáváme složitost 0(k • \text\ + k • 4fc), přičemž paměťová složitost je 0(4k). Závěr. Pro k «: \text\ je faster_frequent_words výrazně rychlejší než frequent_words. A jde to ještě lépe? ;-) 3. Základní datové struktury C2142 Návrh algoritmů pro přírodovědce Tomáš Racek Datové struktury Datová struktura popisuje uložení dat v paměti počítače. Výběr datové struktury ovlivňuje: • množství použité paměti (režie konkrétní struktury) • složitost operací nad touto strukturou, např.: • přidání/odebrání prvku • zpřístupnění prvku • sekvenční průchod přes všechny prvky • nalezení minimálního/maximálního prvku • • • • Aktuálně známe: • jednoduché proměnné (celá čísla, desetinná čísla, znaky,...) • pole Pole I Pole je soubor prvků stejného typu uložených v paměti za sebou. Vlastnosti: • zabírá souvislou oblast v paměti • zpřístupnění prvku přes jméno pole a index (př. A[i + 1]) Indexace v poli • výpočet adresy konkrétního prvku: adresa prvního prvku (A) + velikost typu (D) * počet předchozích prvků • 1D: adresa A[i] = A + D-i • 2D: adresa A[i][j] =A + D-(i-n + j) • 3D: adresa A[i][j][k] = A + D • (i • n2 +; • n + k) Pole II Výhody pole: • jednoduchá implementace • přímočaré použití • zpřístupnění prvku v konstantním čase • sekvenční přístup vede často v praxi k vysokému výkonu (díky využití vyrovnávací paměti) Nevýhody pole: • problematická změna velikosti - Jak přidám/odeberu prvek? Statické vs. dynamické datové struktury Statické datové struktury (např. pole) mají pevné danou velikost. • neflexibilní přístup • lze nadhodnotit velikost —> plýtvání paměti ve většině případů Dynamické datové struktury nabízí implicitní způsob změny velikosti. • složitější na implementaci • změna velikosti přináší jistou režii Dynamické pole I Nedostatky pole. Pole neumožňuje libovolně přidávat/odebírat prvky, změna jeho velikosti je složitá —> je potřeba znovu alokovat souvislý kus paměti a kopírovat prvky. Pozorování • přidávat prvky na začátek/doprostřed poleje obtížné • přidání nebo odebrání prvku na konci pole je snazší —> můžeme se vyhnout kopírování prvků • pro přidání prvku na konec pole musí být v paměti místo Dynamické pole. Rozšíření pole o možnost přidávat a odebírat prvky. Implementací jde o statické pole, které je logicky rozděleno na aktuálně zabranou a volnou oblast. Dynamické pole II • prvky lze na konec přidávat až do vyčerpání kapacity • poté je potřeba realokace celého pole, typicky např. na dvojnásobnou kapacitu • zjevně má přidání prvku na začátek/doprostřed/na konec pole lineární složitost 2 2 7 2 7 1 2 7 1 3 2 7 1 3 8 2 7 1 3 8 4 Logical size _i Capacity Jak je tomu ale v praxi? Amortizovaná složitost Pozorování. Při přidávání prvku na konec dynamického pole je většina těchto operací rychlá - mají konstantní složitost. Pokud je ale nutné pole realokovat, složitost je lineární. • lineární složitost nastává ale velmi zřídka • někdy může být užitečnější jiný aparát pro popis složitosti Amortizovaná složitost neuvažuje operace izolovaně, ale v rámci větší skupiny. • poskytuje reálnější odhad pro dlouhodobé chování datové struktury • nedává horní odhad —> některé operace mohou trvat „překvapivě" dlouho Dynamické pole - amortizovaná složitost Příklad. Uvažme dynamické pole o n prvcích, kapacitě 2n a operaci přidání prvku na konec pole. • prvních n operací přidání prvku na konec má složitost 0(1) • následující operace je ale v 0(n) —> způsobí zvětšení pole na dvojnásobek • dalších 2n těchto operací je opět rychlých • • • • Pozorování. Posloupnost n operací přidání prvku na konec pole má celkem složitost 0(n). Závěr. Přidání prvku na konec dynamického pole má konstantní amortizovanou složitost. (Analogicky pro odebrání posledního prvku.) Dynamické pole IV - praxe Praxe. Dynamické pole je implementováno například jako list v Pythonu nebo std::vector v C++. Měření. Změřte dobu běhu programu, který postupně přidává celkem 100 000 prvků do pole (a) na začátek, (b) doprostřed, (c) na konec. (a) 8,7 s (b) 4,5 s (c) 0,1 s Závěr. Měření potvrzuje amortizovaný odhad složitosti. Dynamické poleje efektivní při přidávání/odebírání posledního prvku. Spojový seznam I Nedostatkem dynamického poleje přidávání/odebírání prvku mimo jeho konec. Spojový seznam představuje datovou strukturu s konstantní složitostí přidání/odebrání prvku. • každý prvek obsahuje ukazatel na prvek následující - next • na rozdíl od pole nevyžaduje souvislou oblast paměti 2184 2003 2004 4 3225 2184 2185 5571 3225 3226 Nul) 5571 5572 Spojový seznam II Přístup ke spojovému seznamu je realizován přes ukazatel na jeho začátek - HEAD. Pro zvýšení efektivity přidávání prvků (-> 0(1)) na konec seznamu lze využít ukazatel na konec seznamu - TAIL. 12 • 99 • 37 • X Pozorování. Indexace (= zpřístupnění prvku) je v 0(n). Průchod seznamem: • sekvenční průchod v 0(n) - stejně jako u pole • v opačném pořadí ovšem 0(n2)\ Spojový seznam III - příklad Příklad operace nad spojovým seznamem 12 • y 99 • -> 37 • -> X Přidání prvku na začátek seznamu: 1. alokace paměti pro nový prvek N 2. kopie vlastních dat do N 3. nastavení N.next na aktuální HEAD 4. nastavení ukazatele HEAD na nový prvek Další typy spojových seznamů Oboustranně zřetězený spojový seznam. Je rozšířením spojového seznamu o ukazatel na předchozí prvek - prev. • průchod seznamem v opačném pořadí v 0(n) • zvyšuje paměťovou náročnost Cyklický spojový seznam propojuje poslední prvek s prvním. 99 12 •—>-99 •—>37 Srovnání datových struktur Složitosti operací nad základními datovými strukturami: Operace Pole Dynamické pole Spojový seznam Indexace 0(1) 0(1) 0{n) Vyhledávání 0(n) 0(n) 0(n) Přidání prvku — 0(n) 10(1)» 0(1) Odebrání prvku — 0(n) 10(1)» 0(1) Paměťová režie — 0(n) 0(n) * amortizovaná složitost pro poslední prvek Závěr. Univerzálně nejlepší datová struktura neexistuje. Fronta I Fronta je datová struktura typu FIFO (First In First Out). Implementuje tzv. FCFS (First Come First Served) přístup. Operace: • enqueue - přidá prvek na konec fronty • dequeue - odebere prvek ze začátku fronty • obě lze implementovat v 0(1) queue <- dequeue()-— front <- —- enqueue() back Fronta II Implementace fronty • (dynamické) pole • spojový seznam dequeueQ queue enqueueQ front back Prioritní fronta • každému prvku je přiřazeno číslo - priorita • priorita určuje, kam bude prvek do fronty zařazen • několik možných implementací Zásobník Zásobník je datová struktura typu LIF0 (Last In First Out). Všechny ostatní vlastnosti jsou shodné s frontou. stack Operace: • push - přidá prvek na vrchol zásobníku • pop - odebere prvek z vrcholu zásobníku • obě lze implementovat v 0(1) Abstraktní datový typ Abstraktní datový typ (ADT) je matematický model pro určité datové struktury definované svými operacemi a omezeními na nich. • teoretický koncept zjednodušující analýzu chování • někdy je součástí specifikace i složitost operací • konkrétní implementaci lze zvolit Příklady: seznam, fronta, zásobník, množina,... Ukázka pro zásobník • zásobník S, prvek k, proměnná X • S.push(k); X <- S.popO je ekvivalentní X <- k • operace pushQ a pop() mají konstantní složitost Zajímavé odkazy • Vizualizace operací nad polem: https://visualgo.net/en/array • Vizualizace operací nad spojovým seznamem: https://visualgo.net/en/list • Vizualizace datových struktur v Pythonu: https://pythontutor.com/visualize.html 4. Řazení Sekvenční vyhledávání Problém. Uvažme problém nalezení prvku v poli. Tento lze zřejmě řešit s lineární složitostí. def search(array, k): for i in range(len(array)): if arrayp] == k: return i return None Zamyšlení. Pokud by bylo pole seřazeno, vyhledávání v něm by mohlo být snazší. • Jak náročné je vyhledávání v seřazeném poli? • Jak náročné je seřadit pole? Binární vyhledávání I Myšlenka. Pole je seřazeno pro každý prvek pole platí, že hodnoty vlevo od něj jsou menší nebo rovny tomuto prvku a vpravo od něj větší nebo rovny. Příklad. Vyhledávání čísla 76. v 2 9 11 15 28 33 40 47 51 64 76 77 62 35 94 ■ 2 9 11 15 28 33 40 47 51 54 7tí 77 82 35 94 ■ i" 2 9 11 15 28 33 40 47 51 64 76 77 82 85 94 t 2 9 11 15 28 33 40 47 51 64 76 77 82 85 94 Binární vyhledávání II Rekurzivní implementace binárního vyhledávání: def binary_search(A, k, i_min, i_max): if i_max < i_min: return None mid = (i_min + i_max) // 2 if k== A[mid]: return mid elif k< A[mid]: return binary_search(A, k, i_min, mid -1) else: return binary_search(A, k, mid + 1, i_max) Složitost. V každé iteraci se velikost prohledávané oblasti zmenší na polovinu. Složitost binárního vyhledávání je tedy <9(logn). Problém řazení Neformální definice: Vstup: Posloupnost prvků a\,...,an délky n Výstup: Neklesající permutace vstupní posloupnosti, tj. Si e {1,..., n - 1} : ai < Poznámka k definici. Formální definice pracuje s prvky tvaru (a;,D;), kde a,- jsou klíče (podle kterých se řadí) a D; pak další data, která mají význam v praktických aplikacích. Při analýze algoritmů je většinou zanedbáme (Dř- = 0). Poznámka k terminologii. Někdy se nesprávně používá pro řazení výraz třídění, které značí ale spíše seskupování objektů podle daných vlastností. Selection sort Myšlenka. Najdi v poli nejmenší prvek a vyměň jej s prvkem na první pozici. Opakuj postup pro zbytek pole (bez prvního prvku). def selection_sort(A): for i in range(len(A)): minjdx = i for j in range(i, len(A)): if A[min_idx] > A[j]: minjdx = j A[min_idx], A[i] = A[i], A[min_idx] Složitost. Vnější for cyklus zjevně 0(n), vnitřní má však různé délky (n, n -1,..., 1). Celkem tedy 1 + 2 + ...+ n e 0(n2). Bubble sort Myšlenka. Porovnávám postupně prvky na sousedních pozicích. Pokud jsou vůči sobě dva v nesprávném pořadí, prohodím je. Důsledek. Po první iteraci „probublá" největší prvek na konec pole. def bubble_sort(A): for i in range(len(A)): for j in range(len(A) - i -1): if A[j] > A[j + 1]: A[j], A[j + 1] = A[j + 1], A[j] Složitost. 0(n2) podle stejné úvahy jako pro selection sort. Složitost lze vylepšit na příznivých datech. Jak? Insertion sort Myšlenka. Rozdělme (virtuálně) pole na dvě části: (1) už seřazenou a (2) dosud neseřazenou. Vždy první prvek z (2) zařazujeme korektně do (1). def insertion_sort(A): for i in range(len(A)): item = A[i] j = " while j > 0 and item < A[j -1 ]: A[j]=A[j-1] j-=1 A[j] = item Složitost. Pro nejhorší případ (pole seřazeno v opačném pořadí) je složitost 0(n2). Složitost problému řazení Idea důkazu. Uvažme posloupnosti složené pouze z čísel 1,...,n, kde se každé číslo vyskytuje nejvýše jednou (= permutace této množiny). Takových je zjevně n!. Asociativní řadicí algoritmy mohou provádět pouze porovnání dvojice prvků. Korektní řadicí algoritmus musí pro každou takovouto posloupnost provést jiný výpočet. Libovolný asociativní řadicí algoritmus musí tyto výpočty odlišit, tj. provést alespoň log2(n!) binárních testů. Důsledek. Dolní odhad složitosti řazení je Q(nlogn). Quick sort Myšlenka. Vyberu prvek pole. Vlevo od něj přesunu všechny menší prvky, vpravo od něj větší. Obě tyto části pak řadím dále rekurzivně stejným postupem. def quick_sort(array): if len(array) <= 1: return array else: pivot = array[0] smaller = [x for x in array[1:] if x < pivot] bigger = [x for x in array[1:] if x >= pivot] return quick_sort(smaller) + [pivot] + quick_sort(bigger) Složitost. V nejhorším případě (libovolně seřazené pole) bude hloubka rekurzivního volání 0(n), v každé úrovni je potřeba rozdělit prvky do dvou částí se složitostí 0(n). Celkem tedy 0(n2). Merge sort Idea. Uvažme dvě již seřazené posloupnosti. Jak z nich vytvořit jednu seřazenou? Funkce merge(A, B) • porovnává vždy první prvky obou posloupností, menší z nich přesune do výstupní posloupnosti Merge sort • seřazenou posloupnost délky n získám ze dvou seřazených posloupností délky n/2 aplikací funkce merge • analogicky posloupnosti velikosti n/2 „slévám" ze dvou seřazených posloupností o velikosti n/4 • posloupnosti délky 1 jsou implicitně seřazeny Merge sort - ukázka 38 38 27 / r 27 X ' f 27 38 38 27 43 38 27 43 3 / 43 3 43 L7 3 43 N k 3 27 38 43 82 10 9 82 10 32 82 9 82 10 \ 10 / 10 9 10 82 3 9 10 27 38 43 82 Merge sort - implementace def merge(A, b): if len(A) == 0: return b if len(b) == 0: return A if A[0] < b[0]: return [A[0]] + merge(A[1:], b) else: return [b[0]] + merge(A, b[1:]) def merge_sort(A): if len(A) <= 1: return A mid = len(A) 112 return merge(merge_sort(A[:mid]), merge_sort(A[mid:])) Merge sort - složitost Složitost merge sortu • funkce merge má složitost 0(n) • počet úrovní volání funkce funkce merge je <9(logn) • složitost merge sortu je 0(nlogn) Pozorování • dolní odhad složitosti problému řazení je Q(n log n) • složitost merge sortu je 0(nlogn) Závěr. Merge sort je optimální algoritmus pro problém řazení se složitostí 0(n logn). Stabilita řadicích algoritmů Definice. Řadicí algoritmus je stabilní, pokud neprohazuje prvky se stejným klíčem. Příklad. Uvažme seznam lidí seřazených podle jména. Pokud jej sežadíme dále stabilním algoritmem podle příjmení, získáme seznam seřazený podle příjmení a jména. L A Jméno B Příjmení 2 Marek Dostál 3 Petr Klíč 5 5 Petr Dostál Prokop Buben Tomáš Fuk Přirozenost řadicích algoritmů Definice. Řadicí algoritmus je přirozený, pokud dokáže využít předuspořádání vstupní posloupnosti. Důsledek. Přirozené řadicí algoritmy řadí částečně seřazené posloupnosti v lepším čase. Příklad. Modifikace algoritmu bubble sort: def bubble_sort(A): for i in range(len(A)): swapped = False for j in range(len(A) - i -1): if A[j] > A[j + 1]: A[j],A[j + 1]=A[j + 1],A[j] swapped = True if not swapped: return Součet čísel Experiment. Určete součet zadaného souboru reálných čísel. Řešení. V Pythonu například funkce sum nebo explicitně: total = 0 for item in array: total += item Pozorování. Uvažme stejnou sadu čísel, jen v jiném (zcela náhodně zvoleném) pořadí. array2 = sorted(array, key = lambda k : random.random()) Zřejmě platí: sum(array) == sum(array2) Nebo ne? Asociativita sčítání reálných čísel Příklad. Uvažme výpočet 1,11+ 0,001 s přesností na 3 platné číslice. Poznámka. Počet platných desítkových číslic pro typ float je průměrně 7, pro typ double pak 16. • 1,11 +0,001 = 1,11 • korektní výsledek v rámci zvolené přesnosti Srovnejme • 1,11 +0,001 + ...+ 0,001 • 1,11 +(0,001 + ...+ 0,001) Závěr. Sčítání reálných čísel není asociativní. Doporučení. Pokud je přesnost důležitá, sčítám čísla v pořadí podle jejich (absolutní) velikosti. xkcd.com/1185/ ineffective: sorts t?£Fi*£ HňLFHo«TEDMeRSESofir((.i&r): Dewne Fft5T1Jc«o5oKTC(-»5T): IFĽEWH(uST")<2: //AM OPtTrH?ED BOGOSORT RETURN uer // M OWUWN) W0T = MT(t£NeTH(LI5T) /I) FOR n FROM LTO (JDGCt£MGTri(U3T)): shuftle(LGr): IF isSoRiEofrjsr): // UrtMriMM REtLÍRM[ň,B] //HERE. SORIW return "keknel FflGE FAULT" (ERROR. CODE: 2)" DEFINE J&BIMIERflBJQUICKSO(ír(LI&r): DEFINE RflNIICSOKTCUSTl: CK50Y0U CHOOSE flFUOT IFf5S0RTED(DST): then divoc ide ľ&t in hwf Return list FW EřkX HftLF; for N frqh 1 TO 10000: CHQX Tb 5EE F ITS SORTED PlV0r=R/WlrW(O,LE*Nefl(LI5T)) NO, UftlT fTCOESNT ľlŕíITER UST = list [PM5T: ] + U5T [ :FW0Tj C&ľlFWRE E5"ŕH HEMEfÍT To we PWOT if tSSttfttEDfUST): THE BľJGQ? ONES Go IM ň MDJ LŮT REWRN UST the: EawLOhJEä go niô, uh lF|S&ORTED(UST): THE: SŕTOND U&T FROM tJOČftE FSURN (J6T: HAMS OH, Let* he NfvtCTHE USTS IT IsSoRTEDftlsT): //THIS GWt BE HAPPENING Trie 15 u&t ň rekrn uar the, new oc 15 list b FISS0RTO?{LlSTj: //COME ON a*T£ celkově až <9(logn) Heap sort Heap sort je řadicí algoritmus, který je postaven nad operacemi haldy. Má dvě fáze: 1. Přidání všech prvků do haldy. 2. Opakované odebírání minima. Složitost Heap sortu • první fáze má složitost <9(n), druhá pakO(nlogn) • celkově tedy 0(nlogn) • Heap sort je optimální algoritmus Zamyšlení. Ačkoliv asymptoticky optimální, navržená implementace vyžaduje stále lineární množství paměti pro vytvoření haldy. Jde to udělat lépe? Implementace haldy v poli Nápad. Každou binární haldu (obecně i každý zleva zarovnaný binární strom) lze reprezentovat v poli. Pro každý uzel platí: • je-li uzel uložen na indexu z, jeho levý potomekje na indexu li • analogicky pravý potomek pak na indexu 1 5 3 9 8 6 Heap sort pak spočívá ve vytvoření maximové haldy přeuspořádáním prvků v poli (1. fáze) a následně odebrání všech prvků (2. fáze), které budou tvořit od konce seřazenou posloupnost. Heap sort - implementace def sift_down(A, start, end): root = start while True: child = 2*root + 1 if child >= end: break if child + 1 < end and A[child] < A[child + 1]: child += 1 if A[root] < A[child]: A[root], A[child] = A[child], A[root] root = child else: break def heap_sort(A): for i in range(len(A)//2, -1, -1): sift_down(A, i, len(A)) for i in range(len(A)): A[0], A[len(A) - i -1] = A[len(A) - i -1], A[0] sift_down(A, 0, len(A) - i -1) Haldy v životě informatika (http://xkcd.com/835/) Not only is that terrible in general, but you just KNOW Billy's going to open the root present first, and then everyone will have to wait while the heap is rebuilt. Odbočka: Prioritní fronta Opakování. Aktuálně umíme implementovat jednoduchou frontu pomocí spojového seznamu nebo pole pevné délky. Zobecnění. Přiřaďme každému prvku prioritu, která bude určovat v jakém pořadí bude z fronty odstraněn. Pozorování. Stávající implementace v tomto případě neposkytují lepší než lineární složitost pro alespoň jednu z operací fronty, tedy přidání nebo odebrání prvku. Řešení. Přímočarou implemetací prioritní fronty je binární halda. • přidání prvku - <9(logn) • odebrání prvku (odpovídá odebrání minima) - <9(logn) • pokud je implentována v poli, k přidávání nebo odebírání prvků dochází jen na jeho konci —> lze využít dynamického pole Indexy Shrnutí. V současnosti umíme seřadit data podle zvoleného klíče. Vyhledávat v seřazeném poli lze efektivně pomocí binárního vyhledávání v logaritmickém čase. • není nutné řadit vlastní (často objemná) data, ale stačí seřadit klíče • takových uspořádání, tzv. indexů, je možné udržovat více najednou 1 3 5 6 8 9 C D F G L X k i F \ I V F \ VV F -SF F F I . F~SF F VV I • I . • • I o m V • i F F I Nevýhoda současného reseni spočíva v obtizne zmene velikosti indexu. Pridaní nebo odebrání prvku má lineární složitost. Nápad. Využijme místo pole jako základ indexu binární strom. Binární vyhledávací strom Binární vyhledávací strom (BST)je datová struktura založena na binárním stromě, kde pro každý uzel platí, že: • všechny uzly v jeho levém podstromu mají menší ohodnocení než on sám • analogicky všechny uzly v pravém ^ ^lo) podstromu mají ohodnocení větší Základní operace nad BST: • přidání prvku • odebrání prvku • vyhledání prvku Operace nad BST Vyhledání prvku. Analogie binárního vyhledávání-porovnáváme hledanou hodnotu s ohodnocením aktuálního prvku. Je-li menší, vyhledávání pokračuje v jeho levém podstromu, je-li větší, pak v pravém. Přidání/odebrání prvku. Nejprve je potřeba nalézt místo, kde k vlastnímu přidání/odebrání dojde. Na konci pak zajistit, že změněný strom je stále BST. Pozorování. Složitost těchto operací bude záviset na výšce stromu, v nejhorším případě bude tedy lineární (uvažme např. vytvoření BST ze seřazené posloupnosti klíčů). Závěr. Pro dosažení efektivity je potřeba implementovat operace přidání a odebrání prvku tak, aby udržovaly logaritmickou výšku BST. Zajímavé odkazy • Vizualizace operací nad binární haldou: https://visualgo.net/en/heap • Vizualizace operací nad binárním vyhledávacím stromem: https://visualgo.net/en/bst 6. Vyhledávací stromy, hashovací tabulky, trie. Nevýhody B ST Opakování. Binární vyhledávací strom představuje koncepčně jednoduchou formu indexu nad daty. Jeho hlavní nevýhoda je až lineární výška. Myšlenka. Modifikujme operace přidání a odebrání prvku tak, aby zbytečně nezvyšovaly výšku stromu. AVL stromy AVL strom je binární vyhledávací strom, který navíc splňuje následující podmínku: Pro každý uzel AVL stromu platí, že výška jeho levého a pravého podstromu se liší nejvýše o 1. Poznámka. Definiční podmínka zaručuje, že výška AVL stromu je nejvýše asi 1,5 -log(n), kde n je počet jeho prvků. Implementace. Každý uzel AVL stromu bude mít u sebe navíc i informaci o své výšce. V případě porušení definiční podmínky při některé z operací bude nutné strom upravit. AVL strom - ukázka Operace nad AVL stromy Vyhledání prvku. Úplně stejná operace jako v obyčejném BST. Díky zaručené výšce AVL stromu ovšem nyní nejvýše <9(logn). Přidání/odebrání prvku. Probíhá obdobně jako u BST. Pokud je narušena vyváženost AVL stromu (porušení definiční podmínky), probíhá vyvažování pomocí tzv. rotací. Operace nad AVL stromy II Rotace • pouze lokální změna datové struktury • konstantní složitost • při přidání prvku stačí nejvýše 1 • při odebrání prvku je jejich počet omezen výškou stromu Složitost přidání/odebrání prvku v AVL stromu je <9(logn). Logaritmická výška I Shrnutí. AVL stromy poskytují z pohledu asymptotické složitosti optimální rozšíření B ST. Poznámka. Na BST jsou také založeny např. červeno-černé stromy, které mají logaritmickou výšku (i když větší než AVL), nicméně poskytují v praxi rychlejší vyvažování. Příklad. Uvažme data o velikosti n = 22 000 000 (přibližný počet sloučenin v databázi PubChem). Vybudujeme nad těmito daty index na bázi binárního stromu. • výška úplného binárního stromu by byla 25 • v rámci teorie ideální, v praxi může být i to příliš Logaritmická výška II Nápad. Uvažme vyvážený strom (= s logaritmickou výškou), jehož arita fcje větší než 2. • zvolme např. k = 100 • pak výška tohoto stromu pro stejnou velikost dat bude 4 Realizace. Na této myšlence jsou založeny tzv. B stromy. • logaritmická složitost operací • typicky pro velké objemy dat • existují různé varianty (B/B+/B*) Využití B stromů • souborové systémy (NTFS, Ext4, btrfs) • indexy pro databáze Hashovací tabulka Shrnutí. Vyvážené vyhledávací stromy poskytují základní operace v logaritmickém čase. Jde dosáhnout i konstantní složitosti? Nápad. Uvažme pole o velikosti M a tzv. hashovací funkci, která každé hodnotě klíče přiřadí index i do tohoto pole, kde se daná položka bude nacházet. Hashovací funkce - příklad • uvažme klíče k jako přirozená čísla • pak např. i = H(k) = k mod M • konstantní složitost výpočtu indexu Hashovací funkce Ideální případ. Uvažme hashovací tabulku o velikosti M s následujícími vlastnostmi: • počet vkládaných prvků n < M • hashovací funkce má konstantní složitost • hashovací funkce je prostá, tj. Vklfk2 : H(fci) = H(k2) -^k1=k2 • pak složitost přidání, vyhledání a odebrání prvku je konstantní Kolize. V praxi ovšem tohoto není často možné dosáhnout, hashovací funkce nebývá prostá —> pro dva různé klíče získáme stejnou hodnotu hashovací funkce. Příklady řešení pro n < M • lineární hashování - je-li index i obsazen, zkusím i + 1 atd. • dvojité hashování - při kolizi volím jinou hashovací funkci Řešení kolizí I Řešení kolizí v obecném případě spočívá v možnosti vytvoření spojového seznamu pro každý index pole. Řešení kolizí II Vlastnosti • ideální hashovací funkce rozděluje klíče rovnoměrně • délka každého seznamu je pak průměrně n/M • přidání prvku v 0(1) • vyhledání/odebrání prvku ale v 0(n) - stejné jako u spojového seznamu V praxi je ale často výrazně lepší než obyčejný spojový seznam. Srovnejme několik příkladů s ideální hashovací funkcí a n = 5000: • M = 1000 • M = 5000 • M = 10000 Závěr. Hashovací tabulka je velmi efektivní, pokud známe rozložení prvků (-> hashovací funkce) a jejich počet (-> velikost tabulky). Hashovací tabulka - poznámky Rozšíření. V případě, kdy není počet prvků znám dopředu, lze měnit velikost i vlastní tabulky. • základem je dynamické pole • je potřeba sledovat zaplnění tabulky, tedy poměr n/M • vysoká zaplněnost přináší nižší výkon • změna velikosti nastává při dosažení zvolené hranice zaplněnosti (např. 2/3 nebo 3/4) Použití • implementuje ADT asociativní pole (slovník), které uchovává dvojice typu (klíč, hodnota) • v Pythonu typ diet, vjavě HashMap, v C++ std::unordered_map Trie Trie (prefixový strom) je stromová datová struktura zejména vhodná pro uložení klíčů, které jsou řetězci. Trie - příklad implementace Příklad. Uvažme řetězce složené ze znaků anglické abecedy • každý uzel trie obsahuje pole 26 ukazatelů na další prvky • v každém uzlu uložíme příznak, který říká, zdali je tento uzel validním klíčem (listy jsou implicitně) Složitost operací • nechťh je délka nejdelšího řetězce • pak trie má výšku h • operace přidání, vyhledání a odebrání prvku mají všechny složitost 0(h) • neúspěšné hledání může skončit v kterékoliv úrovni (srovnejme s BST) Zajímavé odkazy • Vizualizace operací nad AVL: https://visualgo.net/en/bst • Vizualizace operací nad hashovací tabulkou: https://visualgo.net/en/hashtable • Vizualizace operací nad trií: https://www.cs.usfca.edu/~galles/visualization/Trie.html 7. Grafy. Vyhledávání v databázích I Opakování. Umíme efektivně vyhledávat a řadit objekty podle různých klíčů v případě, zeje na těchto klíčích definováno uspořádání (<). Vyhledávání molekul. Mějme molekulu a chtějme zjistit, zdali se již vyskytuje v dané sadě sloučenin (= databázi). • Záznamy o molekulách často obsahují jednoznačné identifikátory (řetězce znaků) -> umíme. Problém. Tyto informace ale nemusí být dostupné. K dispozici máme však minimálně: • údaje o atomech (pozice, typy) • vazby mezi atomy Příklad molekuly - formát MOL 702 -OEChem-03301510303D 9 8 0 0 0 0 0 0 0999V2000 -1.1712 0.2997 0.0000 0 0 0 0 0 0 0 -0.0463 -0.5665 0.0000 C 0 0 0 0 0 0 1.2175 0.2668 0.0000 c 0 0 0 0 0 0 -0.0958 -1.2120 0.8819 H 0 0 0 0 0 0 -0.0952 -1.1938 -0.8946 H 0 0 0 0 0 0 2.1050 -0.3720 -0.0177 H 0 0 0 0 0 0 1.2426 0.9307 -0.8704 H 0 0 0 0 0 0 1.2616 0.9052 0.8886 H 0 0 0 0 0 0 -1.1291 0.8364 0.8099 H 0 0 0 0 0 0 12 10 0 0 0 19 10 0 0 0 2 3 10 0 0 0 2 4 10 0 0 0 2 5 10 0 0 0 3 6 10 0 0 0 3 7 10 0 0 0 3 8 10 0 0 0 Vyhledávání v databázích II Intuice. Porovnání na základě pozic jednotlivých atomů a vazeb představuje výpočetně netriviální problém. Současné databáze navíc obsahují stovky tisíc až miliony struktur. Návrh řešení. Proveďme vyhledávání v několika fázích, které budou postupně omezovat množinu přípustných struktur. Postupujme od nejjednodušších metod po ozitejsi. 1. jednoduché deskriptory (př. sumárnívzorec) 2. využití znalosti topologie, podstruktur 3. porovnání pozic atomů v prostoru Příklad. Porovnání molekul podle sumárních vzorců v rozumném čase výrazně redukuje množinu kandidátů. Nicméně samo o sobě nestačí. Vyhledávání v databázích III Omezení. Pomocí sumárního vzorce nelze rozlišit izoméry. H\/H H3C OH H3C XH3 Ethanol (Alcohol) Dimethylether Topologie. Je nutné přidat další informace o struktuře sloučenin - propojení vazbami, Problém. Potřebujeme nalézt vhodnou datovou strukturu pro reprezentaci molekuly. 3. fáze. Ani toto rozlišení obecně nestačí (stereoizomery), ale získané výsledky lze použít jako výchozí bod pro další algoritmy. Graf Definice. Graf G = {V,E), kde l/je množina uzlů (vrcholů) a E je množina hran. Typy grafů • orientovaný - hrany jsou uspořádané dvojice (u,v) • neorientovaný - hrany jsou dvouprvkové podmnožiny {u,v} Příklad orientovaného grafu • G = (V,E) • V={A,B,C,D,E,F} • E = {(A, B), (B, C), (C, E), (D, B), (E, D), (E, F)} Reprezentace grafu Minimální požadavky na datovou strukturu • dotaz na existenci hrany v grafu • sousedé daného vrcholu Triviální řešení představuje obyčejný seznam (pole) hran. Nicméně výše zmíněné operace pak nelze implementovat efektivně. • G = (V,E) • V={A,B,C,D,E,F] • E = {(A, B), (B, C), (C, E), (D, B), (E, D), (E, F)} Matice sousednosti Matice sousednosti. Vytvořme pro graf G = (V, E) matici A o rozměrech |V| x |V| s vlastností: Příklad Ay = l <->(/,;■) e E A = '0 1 1 0\ 0 0 0 0 0 10 1 0 0 10 Vlastnosti • dotaz na přítomnost hrany je konstatní operace • seznam následníků daného vrcholu v lineárním čase • potřeba \V\2 paměti -> vhodné pro husté grafy (|E| ~ \V\2) Seznam následníků Seznam následníků. Uvažme pole ukazatelů na seznamy následníků daných vrcholů. Příklad Vlastnosti • dotaz na přítomnost hrany je lineární operace • seznam následníků v lineárním čase • pouze \V\ + |E| paměti -> vhodné pro řídké grafy (|E| ~ \V\) Procházení grafu Cíl. Projít všechny vrcholy grafu dostupné ze zvoleného výchozího. Naivní řešení. Projít postupně seznam vrcholů od začátku do konce (podobně jako u obyčejného pole). • zjevně lineární operace • nerespektuje strukturu grafu • graf nemusí být souvislý —> projdeme i jeho nedosažitelné části Ideální řešení • zachová lineární složitost • každý vrchol projde právě jednou • odstraní výše uvedené nedostatky Procházení do šířky Breadth First Search (BFS) prochází graf po jednotlivých úrovních - než projde vrcholy vzdálené (co do počtu hran) n od výchozího, projde předtím všechny vrcholy vzdálené n -1. Breadth-First Search (BFS) Vlastnosti • procházíme nejdříve všechny přímé následníky vrcholů • pro uložení pořadí, ve kterém vrcholy prohledáváme, používáme frontu • lineární složitost vzhledem k velikosti grafu - 0(\V\ + |E|) Procházení do šířky - pseudokód 1: function BFS(G,w) is 2: NechťQ je prázdná fronta 3: Enqueue(Q,w) 4: Označ u jako navštívený 5: while Q není prázdná do 6: v <- Dequeue(Q) 7: for all (v,w) e E do 8: if w není navštívený then 9: Označ w jako navštívený 10: Enqueue(Q,w) 11: fi 12: done 13: done 14: end Procházení do hloubky Depth First Search (DFS) prochází graf „dokud to jde", pak se vrací do posledního místa, kde existuje neprozkoumaná cesta, kterou pak pokračuje dále (= obvyklé prohledávání bludiště). Vlastnosti • lineární algoritmus - 0(\V\ + |E|) • často v rekurzivní podobě, iterativní využívá zásobník 1: function DFS(G,w) is 2: Označ u jako navštívený 3: for all (u, v) e E do 4: if v není navštívený then 5: DFS(G,u) 6: fi 7: done 8: end Procházení do hloubky (iterativně) - pseudokód 1: function DFS(G,w) is 2: NechťSje prázdný zásobník 3: Push(S,w) 4: Označ u jako navštívený 5: while S není prázdný do 6: v <- Pop(S) 7: for all (v,w) e E do 8: if w není navštívený then 9: Označ w jako navštívený 10: Push(S,w) 11: fi 12: done 13: done 14: end Otázka. Čím se liší pseudokód pro BFS a DFS? Procházení binárního stromu BFS —> procházení po úrovních Varianty DFS • pre-order -> 1. uzel, 2. levý podstrom, 3. pravý podstrom • in-order -> 1. levý podstrom, 2. uzel, 3. pravý podstrom • post-order -> 1. levý podstrom, 2. pravý podstrom, 3. uzel Pořadí procházení vrcholů • BFS: 2, 7, 5,1,6, 9, 5,11,4 • DFS pre-order: 2, 7,1, 6, 5,11, 5, 9, 4 • DFS in-order: 1, 7, 5, 6,11, 2, 5, 4, 9 • DFS post-oder: 1, 5,11, 6, 7, 4, 9, 5, 2 Otázka. Co kdybychom použili DFS in-order na BST? Zajímavé odkazy • Vizualizace různých reprezentací grafů: https://visualgo.net/en/graphds • Vizualizace průchodů grafem (BFS/DFS) nad AVL: https://visualgo.net/en/dfsbfs • Zajímavé aplikace teorie grafů: https://www.fi.muni.cz/~xpelanek/ucitele/data/ Prezentace%20-%20zajimave%20aplikace%20teorie%20grafu.pdf 8. Nejkratší vzdálenosti. Nejkratší vzdálenosti v grafu Problém. Určete nejkratší vzdálenost mezi vrcholy u a z; v grafu. Pozorování. V tuto chvíli můžeme posuzovat vzdálenost pouze jako počet hran na cestě mezi uav. Takový výpočet realizuje prohledávání do šířky (BFS) v lineárním čase vůči velikosti grafu. Rozšíření. Uvažme případ, kdy bychom chtěli přiřadit hranám na cestě různou váhu. Graf G = {V,E,we) nazveme hranově ohodnocený, we\e funkce, která každé hraně přiřazuje její ohodnocení - reálné číslo. Nejkratší vzdálenost mezi dvěma vrcholy v grafu je minimální součet ohodnocení hran některé cesty mezi těmito vrcholy. Matice vzdáleností Poznámka. Na hranově neohodnocenýgraf se lze dívat jako na speciální případ ohodnoceného, kde V(u,v) e E : we{u,v) = 1. Matice vzdáleností W je rozšíření matice sousednosti: Příklad 0 we(i, j) oo proi = ; pro (i, j) e E pro (i, j) í E W = 0 2 OO oo 1 0 3 oo oo oo 0 oo oo 3 1 0 \ Záporný cyklus Příklad. Určete nejkratší vzdálenost mezi vrcholy s a ŕ v grafu: Pozorování. Graf obsahuje cyklus záporné délky (vrcholy e,f,g), nejkratší vzdálenost mezi s a t není definována. Poznámka. Uvažme graf bez cyklů záporné délky. Každá nejkratší cesta mezi dvěma vrcholy obsahuje libovolný vrchol nejvýše jednou. Bellman-Fordův algoritmus Pozorování. Z předchozí poznámky vyplývá, že nejkratší cesta mezi dvěma vrcholy v grafu obsahuje nejvýše \V\ - 1 hran. Relaxace hrany. Nechť (u,v) je hrana v grafu G s ohodnocením we(u,v) a hodnoty u.d a v.d jsou v daném okamžiku nejkratší nalezené vzdálenosti do u, resp. do v, z výchozího vrcholu. Zjevně pak platí, že: v.d = mm(v.df u.d + we(u, v)) Tato (případná) změna ohodnocení v.d se nazývá relaxací. Bellman-Fordův algoritmus je založen na těchto dvou principech. • počítá nejkratší vzdálenosti z výchozího vrcholu do všech ostatních (1:N) • (|Vl - l)krát relaxuje všechny hrany Bellman-Fordův algoritmus - poznámky Složitost Bellman-Fordova algoritmu je 0(\V\ • |E|), relaxace hrany má totiž zřejmě konstatní složitost. Pozorování • Pokud při některé z iterací nedojde ke změně hodnoty v A pro žádný vrchol v, pak je možné výpočet ukončit. • Provedením jedné iterace výpočtu navíc lze v grafu detekovat záporné cykly. • Pokud dojde k relaxaci hrany, lze u koncového vrcholu nastavit ukazatel na jeho předchůdce -> rekonstrukce cesty. Bellman-Fordüv algoritmus - pseudoköd 1: function Bellman-Ford(G = (V,E,we), s) is 2: Wv e V : ü.d <- oo; s.d <- 0 3: forz<- 1 to \V\-1 do 4: for all e E do 5: if ü.d > u.d + i?) then 6: ü.d <— u.d + I?) 7: fi 8: done 9: done 10: for all (u,v) e E do 11: \fv.d> u.d + we(u, v) then 12: Error : Negative cycle detected 13: fi 14: done 15: end Dijkstrův algoritmus Dijkstrův algoritmus představuje odlišný způsob řešení problému nejkratších vzdáleností v grafu. • Opět řeší problém typu 1:N. • Vyžaduje graf s nezáporným ohodnocením všech hran. Myšlenka. Pokud je posloupnost u,u\,...,un,v nejkratší cesta z u do v, pak posloupnost u, u\,... tik, kde k < n je nejkratší cesta z u do wfc. Výpočet algoritmu. V každé iteraci rozšiřujeme množinu vrcholů, do kterých již známe nejkratší vzdálenost z výchozího. Dijkstrův algoritmus Příklad 1. Pokud je Q množina vrcholů s dosud neurčenou nejkratší vzdáleností, tak z ní nejprve vybereme vrchol u, jehož ohodnocení u.d je nejnižší. 2. Poté přepočítáme všechny vzdálenosti do vrcholů z Q, do kterých vede z u hrana. Dijkstrův algoritmus - pseudokód 1: function Dijkstra(G = (V,E,we), s) is 2: Sv G V : v.d <— oo 3: s.d <- 0 4: Q^l/ 5: while Q není prázdná do 6: u <- í e Q s minimální í.d 7: Odstraň i/zQ 8: for all v : (u,v) e E do 9: if > w.d + v) then 10: i7.d <— u.d + ií7e(w, i?) 11: fi 12: done 13: done 14: end Dijkstra - volba datové struktury Složitost Dijkstrova algoritmu je dána volbou datové struktury pro Q. Zajímají nás dvě operace: • fát - extrakce prvku s minimálním klíčem {\V\ operací) • fdec - snížení klíče v.d (nejvýše |E| operací) Seznam vrcholů • snížení klíče - 0(1) • extrakce minimálního prvku -<9(|1/|) • celkem 0(\E\ + \V\2) = 0(\V\2) Binární halda • snížení klíče i extrakce minima -<9(log|V|) • celkem 0(log|V| • (|V1 + |E|)) Nejkratší vzdálenosti mezi všemi dvojicemi vrcholů Pozorování. Určit nejkratší vzdálenost mezi dvěma vrcholy (1:1) má stejnou složitost jako určit nejkratší vzdálenost z jednoho vrcholu do všech ostatních (1:N). Nejkratší mezi všemi dvojicemi vrcholů lze spočítat např. využitím \V\ volání Dijkstrova nebo Bellman-Fordova algoritmu, kdy v každém výpočtu volíme jiný výchozí vrchol. Jde to i lépe? Floyd-Warshallův algoritmus počítá nejkratší vzdálenosti mezi všemi dvojicemi vrcholů v čase <9(|1/|3). Navíc oproti Dijkstrovu algoritmu umí pracovat se zápornými hranami. Floyd-Warshallův algoritmus Myšlenka. Označme d^. délku nejkratší cesty mezi vrcholy i a j, kde na této cestě jsou vrcholy pouze z množiny {1,..,,fc}. Zjevně dfj = we{i,j) a požadovaný výsledek odpovídá d^\ Mohou nastat dvě možnosti pro d^: 1. k není součástí nejkratší cesty -> df® = d?. ^ 2. fc je součástí nejkratší cesty -> = + 4fc~1) J J J h] i,k k,j Odtud tedy: d?> = min(d^1)/d^1) + dř:1) Poznámka. Pokud < 0 pro nějaké i, pak graf obsahuje cyklus záporné délky. Z/Z Floyd-Warsha11 uv algoritmus - pseudokod 1: function Floyd-Warshall(G = (V,E,we)) is 2: V(m, v) e {1,..., |VI} x {1,..., \V\] : dist(u, v) <- oo 3: VveV: dist{v, v) <- 0 4: V(w,y)eE: dist(u,v) <— ztfg(w,i?) 5: forfc^ 1 to |V| do 6: for z <- 1 to |V| do 7: for y <- 1 to |V| do 8: if dist(i, j) > dist(i, k) + dist{k, j) then 9: dist(i, j) <— dzsf(i, k) + dist(k, j) 10: fi 11: done 12: done 13: done 14: end Zajímavé odkazy • Vizualizace algoritmů pro výpočet nejkratších vzdáleností: https://visualgo.net/en/sssp 9. Minimální kostry. Kostra grafu Kostra neorientovaného grafu G je podgraf, který obsahuje všechny vrcholy G a je stromem. Opakování. Každá kostra grafu má |V| vrcholu a |V| - 1 hran. Poznámka. Počet různých koster v úplném grafu je n Minimální kostra grafu Minimální kostra hranově ohodnoceného neorientovaného grafu G je taková kostra G, která má součet ohodnocení hran nejnižší. Poznámka. Minimální kostra nemusí být určena jednoznačně. Uvažme např. graf, pro který platí V{u,v} e E : we(u,v) = 1. Zajímavost. Motivací pro řešení problému minimální kostry byla elektrifikace jižní Moravy (Otakar Borůvka, 1925). Popsáno v článcích: • O jistém problému minimálním • Příspěvek k řešení otázky ekonomické stavby elektrovodných sítí Primův algoritmus Princip • budování kostry začíná v libovolném vrcholu grafu • v každém kroce algoritmu je do kostry přidána minimální hrana sousedící s některým již v kostře obsaženým vrcholem tak, aby nebyl utvořen cyklus Primův algoritmus - poznámky Zajímavost. Tento algoritmus nejprve popsal český matematik Vojtěch Jarník (1930), později (1957,1959) byl znovuobjeven nezávisle na sobě Robertem Primem a Edsgerem Dijkstrou. Implementace • potřeba udržovat seznam hran, které sousedí s aktuálně zpracovanými vrcholy kostry—> rozdělení vrcholů na dvě množiny • výběr minimální hrany - struktura podobná jako u Dijkstrova algoritmu Primuv algoritmus - pseudokod 1: function Prim(G = (V,E,we), s) is 2: Vv eV : v.key <— oo 3: s.key <- 0, s.p <- NULL 4: Q^V 5: while |Q| gfc 0 do 6: u <— £ e Q s minimalnim .fey 7: Q <- Q \ [u] 8: for all e E do 9: if v e Q A Wg(w, v) < v.key then 10: v.key <— we(u,v) 11: <— w 12: fi 13: done 14: done 15: end Primův algoritmus - volba datové struktury Pozorování. Složitost Primová algoritmu je dána volbou datové struktury pro Q. Seznam vrcholů • odstranění minima - 0(\V\) • snížení klíče - 0(1) • celkem <9(|V|2 + |E|) = <9(|V|2) Binární halda • odstranění minima - <9(log|l/|) • snížení klíče - <9(log|l/|) • celkem 0(\V\ log |V| + |E| log\V\) = 0(\E\ log |V|) Kruskalův algoritmus Princip • každý vrchol v grafu představuje jednu komponentu kostry • v každém kroku jsou dvě komponenty spojeny minimální hranou Kruskalův algoritmus - poznámky Myšlenka. Seřadím hrany podle jejich ohodnocení. V tomto pořadí je budu uvažovat pro zařazení do kostry. Pozorování. Algoritmus musí udržovat informaci o tom, v jaké komponentě se který vrchol nachází. Nelze totiž vybrat do kostry hranu, která spojuje vrcholy v rámci stejné komponenty. Implemetace využívá tří pomocných funkcí: • MakeSet(u) vytvoří jednoprvkovou množinu obsahující vrchol u • FindSet(u) vrátí identifikátor množiny obsahující vrchol u • Union(u, v) sloučí množiny obsahující vrcholy uav Kruskalův algoritmus - pseudokód 1: function Kruskal(G = (V,E,we)) is 2: m st <- 0 3: for all v e V do 4: MakeSet(v) 5: done 6: for all [u,v\ e E od nejmenší podle we do 7: if FindSet(u) ^ FindSet(v) then 8: mst <- mst U {{u,v}} 9: Union(u, v) 10: f i 11: done 12: Vrať mst 13: end Jednoduchá struktura Union-Find Myšlenka. Každá množina bude reprezentována spojovým seznamem. • MakeSet(u) vytvoří jednoprvkový spojový seznam obsahující vrchol u • FindSet(u) vrátí první prvek seznamu obsahující vrchol u • Union(u, v) sloučí dva seznamy obsahující vrcholy uav Pozorování. Operace FindSet má lineární složitost, ale je v rámci Kruskalova algoritmu volána nejčastěji. Vylepšení. U každého prvku seznamu přidáme navíc ukazatel na hlavu seznamu. FindSet bude nyní konstantní, Union bude muset přepisovat všechny tyto ukazatele. Optimální verze Union-Find Myšlenka. Každou množinu reprezentujeme jako strom. Složitosti operací budou závislé na jejich výšce. • MakeSet(u) vytvoří jednoprvkový strom s kořenem u • FindSet(u) vrátí kořen stromu obsahující vrchol u • Union(u, v) sloučí dva stromy obsahující vrcholy u a v Vylepšení snižující složitost operací • Union napojuje vždy strom s nižší výškou pod kořen druhého • FindSet navíc snižuje výšku prohledávaného stromu napojením vrcholů přímo pod kořen Složitost Kruskalova algoritmu při využití této struktury je určena nutností seřazení hran podle jejich ohodnocení, tedy 0(|E| log |E|) = 6>(|E| log |1/|). Zajímavé odkazy • O jistém problému minimálním: https: //dml.cz/bitstream/handle/10338.dmlcz/500114/Boruvka_01 -0000-6J .pdf • Příspěvek k otázce ekonomické stavby elektrovodných sítí: https: //dml.cz/bitstream/handle/10338.dmlcz/500188/Boruvka_02-0000-1_1.pdf • Vizualizace algoritmů pro výpočet minimální kostry: https://visualgo.net/en/mst • Vizualizace operací nad strukturou Union-Find: https://www.cs.usfca.edu/~galles/visualization/DisjointSets.html 10. Přístupy k řešení problémů I. Hrubá síla Hrubá síla (brute force) představuje přímočarý přístup založený na definici problému. Vlastnosti • obecně výpočetně nejnáročnější postup -> použitelné pouze pro velmi malé instance problémů • v případě optimalizačních úloh se jedná o zkoušení všech potenciálních řešení • pro některé typu problémů jediná možnost Příklady • Selection sort • naivní násobení matic • jednoduché hledání podřetězce v textu Rekurzivní algoritmy Myšlenka rekurzivních algoritmů spočívá v znovupoužití algoritmu na problém menší velikosti. Speciální (triviální) případy řešíme přímo. def fact_recursive(n): return n * fact_recursive(n -1) if n > 0 else 1 def factjterative(n): result = 1 for i in range(1, n + 1): result *= i return result Poznámka. Volání funkce je ve srovnání s iterací cyklu drahá operace. Vysoká úroveň rekurzivního zanoření navíc může narazit na limity velikosti zásobníku. Hanoiské věže Hanoiské věže jsou hlavolam, v rámci kterého je potřeba přemístit všechny disky z jednoho kolíku na jiný za dodržení dalších pravidel. Poznámka. Existuje velmi jednoduché rekurzivní řešení. Složitost řešení problému Hanoiských věží je exponenciální vůči počtu disků (přesně 2n -1 operací). Rozděl a panuj Rozděl a panuj (divide and conquer, D & C) je přístup vycházející z rekurzivních algoritmů založený na dělení problému na menší, snadněji zvládnutelné, podproblémy. Princip 1. Rozděl problém na menší podproblémy • stejného typu • nepřekrývající se 2. Rekurzivně vyřeš každý podproblém 3. Zkombinuj řešení podproblémů v řešení původního problému Příklady • Mergesort • Quicksort Master theorem Master theorem je nástroj pro určování složitosti algoritmů založených na přístupu rozděl a panuj. Pokud je velikost podproblémů shodná, lze využít následujícího vztahu: T(n) = aT(n/b) + 0(nd) • T(n) - počet kroků nutných pro vyřešení problému o velikosti n •a - počet podproblémů • b - faktor určující velikost podproblémů • nd - rozdělení na podproblémy | sloučení řešení jednotlivých podproblémů 0{nd) prod>logř7a T(n) = 10(nd logn) pro d = logb a 0(nlo^a) prod T(n) = 0(nd logn). T(n) = 2T(n/2) + 0(n) -> T(n) = O(nlogn) Násobení matic Úkol. Popište algoritmus pro násobení dvou matic (Z = XY) o rozměrech nxn. Naivní násobení matic představuje učebnicový způsob řešení se složitostí 0(n3). n V(i,/) e {l..n} x {l..n} : Zifj = £ Xi/kYKj k=l Blokové násobení matic je přístup, kdy každou z matic rozdělíme na menšia násobíme dle následujícího schématu: x = (c d) y = (g L Z = XY = fa b\ e f\_ ae + bg af + bh c d I' G h)~\ce + dg cf + dhi Násobení matic Složitost blokového násobení matic je však zřejmě stále shodná s naivním přístupem, tedy 0(n3). Poznámka. V reálném běhu je dekompozice na bloky výrazně rychlejší řešení díky lepšímu využití vyrovnávací paměti. Rekurzivní algoritmus násobení matic Z = XV = fA B\ E F\_ AE + BG AF + BH C D I' G H)~\CE + DG CF + DHi aplikujme stejný (D & C) přístup pro výpočet součinů AE,BG, aplikací MT získáváme T(n) = 8T(n/2) + 0(n2) -> T(n) = 0(n3) Strassenův algoritmus Myšlenka. Využijeme rekurzivní algoritmus pro násobení matic, avšak pomocí algebraických transformací snížíme počet nutných násobení. Počet sčítání není příliš významný. p1 = A(F -H) P5 = (A + D)(E + H) P2 = (A + B)H Pe = (B- D)(G + H) P3 = (C + D)E P? = (A- C)(E + F) P4 = D(G - E) Z = XV = p5 + p4 - Pl + Pó Pl + p2 P3 + P4 ?! + P5 - P3 - P7i Složitost Strassenova algoritmu T(n) = 7T(n/2) + 0(n2) -> T(n) = 0(nlo&7) ~ 0(n2>81) Hladové algoritmy Hladový algoritmus (greedy algorithm) v každém kroce výpočtu vybírá aktuálně nejlepší možnost, přičemž spoléhá, že tato posloupnost voleb vede ke globálně nejlepšímu řešení. Vlastnosti • ne vždy lze s úspěchem použít - pouze některé problémy mají tuto strukturu • časově efektivní Příklady • Kruskalův a Primův algoritmus • Dijkstrův algoritmus Minimální počet mincí Problém. Vyplaťte zadanou částku pomocí minimálního počtu mincí. Příklad. Částka 79, hodnoty mincí 1, 2, 5,10,... • hladový přístup - volím vždy minci nejvyšší hodnoty menší než zbývající částka • 79 = 50 + 20 + 5 + 2 + 2 Příklad. Částka 6, hodnoty mincí 1, 3 a 4. • hladový přístup -6 = 4 + 1 +1 • optimální řešení-6 = 3 + 3 Příklad. Částka 14, hodnoty mincí 3, 7 a 10. • optimální řešení-14 = 7 + 7 • hladový přístup - 14 = 10 + ? Zajímavé odkazy • Hanoiské věže: https://www.mathsisfun.com/games/towerofhanoi.html 11. Přístupy k řešení problémů II. Sudoku Úkol. Vyřešte následující zadání Sudoku. 5 3 7 6 1 9 5 9 8 6 8 6 3 4 8 3 1 7 2 6 6 2 8 4 1 9 5 8 7 9 Zamyšlení. Řešení je poměrně snadné pro člověka, ale jak jej algoritmizovat? Backtracking Backtracking je rekurzivní přístup, v rámci něhož hledám řešení následujícím způsobem: 1. Zkontroluji, zdali jsem nalezl řešení. 2. Pokud ne, zkusím pokračovat v hledání některou z možností, kterou v danou chvíli mám a ještě jsem nevyzkoušel. 3. Pokud žádné možnosti nezbývají, vracím se do posledního místa, kde jsem měl ještě na výběr. Vlastnosti: • garance nalezení nejlepšího/všech řešení • potenciálně vysoká složitost Známé příklady: • DFS • minimální počet mincí Sudoku - jednoduché řešení 1. Pokud jsou obsazena všechna pole, vracím TRUE. 2. Najdu první prázdné pole. 3. Pro všechny přípustné číslice pro toto pole: 3.1 Zapíšu zvolenou číslici. 3.2 Celý algoritmus rekurzivně opakuji. 3.3 Pokud je výsledkem rekurzivního voláníTRUE, vracím jej, v opačném případě zkouším další číslici. 4. Všechny možnosti pro dané pole jsou neúspěšně vyčerpány, vracím FALŠE. Zamyšlení. Uvedený postup lze vylepšit, pokud budou volná pole vybírána v pořadí podle počtu možných číslic (od nejmenšího). Branch and bound Branch and bound je jednoduché vylepšení backtrackingu pro optimalizační problémy, kdy si během výpočtu pamatuju aktuálně nejlepší nalezené řešení (resp. jeho cenu). • eliminuji cesty, které už nemohou vést k lepšímu řešení (= jejich ohodnocení je větší než ohodnocení aktuálně nejlepšího nalezeného řešení) Vlastnosti: • vede k omezení větvení —> „prořezávání větví" • nezaručuje, že se vyhneme exponenciální složitosti • užitečné, pokud brzy najdeme dobré řešení Branch and bound - příklad Ukázka. Po nalezení řešení s ohodnocením 4 neprohledávám dále neperspektivní cesty. Dynamické programování Dynamické programování je metoda podobná rozdej a panuj použitelná pro optimalizační úlohy. Princip 1. Rozděl problém na menší podproblémy. • stejného typu • musíse překrývat (optimální řešení problému v sobě zahrnuje optimální řešení podproblému) 2. Vyřeš jednotlivé podproblémy v pořadí od nejmenších. 3. Zkombinuj řešení podproblémů na řešení původního problému. Příklady • Dijkstrův algoritmus • Floyd-Warshallův algoritmus Minimální počet mincí Opakování. Pro správně zvolené hodnoty mincí je hladový přístup optimální. V některých případech však nenalezne (nejlepší) řešení. Optimální řešení lze nalézt pomocí dynamického programování. • označme C[j] minimální počet mincí na zaplacení částky j • pokud známe optimální řešení pro C[j] a použili jsme minci hodnoty hif pak máme: C[j] = l + C[j-hi] Příklad. Pokud je C[46] optimální a použili jsme minci hodnoty 20, pak C[46] = 1 + C[26], Minimální počet mincí Zobecnění. Mějme k různých mincí hodnot hu kde 1 < i < k. Pak optimální řešení pro částku /je dáno: C[j] = CO 0 1 + min [C[j - hi]} l 1 Příklad pro částku 6 a hodnoty mincí 1, 3 a 4. • postupujeme od nejnižších částek až po výslednou dle předchozího výrazu • zjevně C[0] = 0 Minimální počet mincí 1 + C[1 -4] = oo 1 + C[4 -4] = 1 cm = min < 1 + C[1 -3] = oo C[4] = min < 1 + C[4 -3] = 2 1 + C[l -1] = 1 1 + C[4 -1] = 2 \ + C[2 -4] = oo 1 + C[5 -4] = 2 C[2] = min < 1 + C[2 -3] = oo C[5] = min < 1 + C[5 -3] = 3 ,1 + C[2 -1] = 2 1 + C[5 -1] = 2 1 + C[3 -4] = oo \ + C[6 -4] = 3 C[3] = min < 1 + C[3 -3] = 1 C[6] = min < 1 + C[6 -3] = 2 ,1 + Q3 -1] = 3 ,1 + C[6 -1] = 3 Optimální pořadí násobení matic Problém. Chceme vynásobit A1 • • -An s nejmenším počtem operací. Pozorování • násobení matic je asociativní, tj. A(BC) = (AB)C • vhodným uzávorkováním lze snížit množství nutných operací Příklad s maticemi A10X3o, B30x5, C5x6°: • 04-10x30 • #30x5) ' ^5x60 = ^10x5 • C5X6O • 10 • 30 • 5 + 10 • 5 • 60 = 4500 operací • ^10x30 ' (#30x5 ' C5X60) ~ ^10x30 * ^30x60 • 30 • 5 • 60 + 10 • 30 • 60 = 27000 operací Závěr. Složitost řešení pomocí přístupu rozděl a panuj je 0(3n), užitím dynamického programování pak 0(n3). Heuristiky Pozorování. Některé instance problémů mohou být z hlediska složitosti exaktně velmi těžko řešitelné. Myšlenka • suboptimální řešení lze nalézt často výrazně rychleji • často není potřeba určit všechna řešení • heuristika - forma odhadu jak vypadá/co obsahuje řešení (př. v 95 % případů platí...) Příklad. Určete nejkratšívzdálenost mezi vrcholys a ř vgrafu G. • pro výpočet uvažujeme pouze hrany s ohodnocením < k • zřejmě nemusí vést k (nejlepšímu) řešení Redukce Redukce je metoda převodu jednoho problému na jiný. Využívá se zejména v rámci teoretického porovnávání složitosti algoritmů. Princip 1. Zadání problému A transformuji na zadání pro problém B. 2. Vyřeším zadání problému B. 3. Řešení problému B převedu zpátky na řešení původního problému A. Příklad. Nejkratší vzdálenost v neohodnoceném grafu. • lze převést na nejkratší vzdálenost v ohodnoceném grafu • V{u, v) e E : we{u, v) = 1 • nejkratší cesta je v novém i původním grafu stejná Zajímavé odkazy • Řešitel sudoku: https://www.sudoku-solutions.com/ • Backtracking a průchod bludištěm: https://www.youtube.com/watch?v=hOaXgiL-lws 12. Těžké problémy. Typy problémů V rámci teoretické analýzy nejčastěji rozlišujeme dva typy problémů: Rozhodovací problém • ověření, zdali něco platí, nebo ne • př. Existuje v grafu G cesta mezi vrcholy s a t délky nejvýše 10? • odpověď: ANO x NE Optimalizační problém • cílem je nalezení nejlepšího řešení z množiny přípustných řešení • př. Jaká je nejkratší cesta v grafu G mezi vrcholy s a ŕ? • odpověd: konkrétní nejkratší cesta x cesta neexistuje Poznámka. Pokud existuje polynomiální algoritmus pro rozhodovací problém, existuje i pro jeho optimalizační variantu (a naopak). Problém obchodního cestujícího (TSP) Problém. Nalezněte nejkratší cestu, která prochází všemi zadanými městy a začíná a končí ve stejném městě. Alternativní definice. Nalezněte v hranově ohodnoceném grafu Hamiltonovskou kružnici (= obsahující všechny vrcholy) minimální délky. TSP - možnosti řešení Hrubá síla. Vygeneruji a ověřím délky všech možných cest. • složitost přístupu 0(nl) • v praxi nepoužitelné Dynamické programování • výrazně netriviální • složitost 0(n22n) Aktuální stav řešení TSP. • nevíme, zdali existuje algoritmus se složitostí nižší než 0(2n) • v roce 2006 se podařilo najít řešení pro instanci problému o velikosti 85 900 měst -> 136 CPU let výpočtů xkcd.com/399 BRUTE-FORCE SOLUTION: 0(ni) Dynamic PROGRAMMING ALGORITHMS- 0 (n*2°) SELLING C*J ESW: o(0 STILL WORKING ON YOUR ROUTE? \ SHIT THE HEU CP Třídy problémů Pozorování. Velká část dosud prezentovaných problémů byla bez větších problémů prakticky řešitelná. Opakem je například TSP. V rámci teorie pak můžeme přemýšlet, zdali lze problémy dělit do kategorií podle složitosti jejich řešení. Nejčastěji rozlišujeme dvě třídy problémů: P třída problémů řešitelných v polynomiálním čase NP třída problémů, pro které lze ověřit řešení v polynomiálním čase Poznámka. V rámci zařazování problémů do těchto tříd vždy uvažujeme jejich rozhodovací varianty. Příklad. TSP je ve třídě NP, nejkratší vzdálenost v grafu je v P i v NP. P vs. NP Zamyšlení. Zjevně platí, že každý problém ve třídě P patří i do třídy NP, tedy P c NP. Otázka. Platí to ale i naopak (NP c P)? Pokud ano, pak P = NP. P vs. NP • otevřený problém, jeden z největších v matematice a informatice • jeden ze sedmi problémů milénia (Millennium Prize Problém —> odměna 1 milion dolarů) P = NP If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in 'creative leaps/ no fundamental gap between solving a problem and recognizing the solution once it's found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss... Scott Aaronson, MIT NP-úplné problémy Pozorování. I v rámci třídy NP jsou problémy, které jsou různě těžké. NP-úplné problémy jsou nejtěžší problémy ve třídě NP. • každý problém v NP lze převést na NP-úplný problém v polynomiálním čase (existuje polynomiální redukce) • rozhodovací varianta TSP je NP-úplný problém • pro žádný NP-úplný problém není znám polynomiální algoritmus Možnosti řešení P vs. NP 1. Ukázat, že pro některý NP-úplný problém nelze zkonstruovat polynomiální algoritmus. Pak P ^ NP. 2. Nalézt polynomiální algoritmus pro libovolný NP-úplný problém. Pak P = NP. Problémy v NP - příklady Zamyšlení. Předpokládejme P ^ NP. Existují problémy, které jsou v NP, ale nejsou NP-úplné? Pravděpodobně následující: • prvočíselný rozklad • izomorfismus grafů Prvočíselný rozklad Úkol. Rozložte následující číslo na prvočísla: 135066410865995223349603216278805969938881475605 667027524485143851526510604859533833940287150571 909441798207282164471551373680419703964191743046 496589274256239341020864383202110372958725762358 509643110564073501508187510676594629205563685529 475213500852879416377328533906109750544334999811 150056977236890927563 • ekvivalentní rozluštění RSA-1024 • odměna 100000 dolarů • soutěž skončila v roce 2007 Travelling salesman (2012) Í3ppiffijM|p Travelling Salesman Pllllll =£?ĚÍĚWfÍ' Drama / Mysteriózní / Thriller / Sci-Fi WM^^M^Wr^.^^. USA, 2012, 80 min Hrají: Steve Wes-t TRAVELLING SALESMAN Obsah Čtveřice geniálních matematiků objeví v průběhu úspěšného výzkumu problému P versus NP algoritmus rapidně zrychlující výpočetní operace. Jejich objev může mít obrovské důsledky. Jak pozitivní, v podobě mohutné akcelerace biologického a medicínského vývoje, tak negativní, neboť nový algoritmus mj, umožňuje překonat moderní šifrování během několika vteřin. Poté, co vláda Spojených států nabídne každému z nich 10 milion dolarů za exkluzivní přístup k jejich části algoritmu, musí se čtveřice vypořádat s morálními i praktickými problémy, které jejich rozhodnutí přináší. (Slaboproud) Vybrané příklady NP-úplných problémů I Problém splnitelnosti výrokových formulí • formule výrokové logiky s proměnnými A\,.. .,An • Existuje přiřazení proměnných takové, že se zadaná formule vyhodnotí na TRUE? • Příklad: v A2) aA3a ^A± je splnitelná např. pro A± = 0, A2 = 0, A3 = 1, Klika • Existuje v grafu klika (= podgraf, který je úplným grafem) o k vrcholech? K3 K4 K5 Vybrané příklady NP-úplných problémů II Problém dvou loupežníků • Lze rozdělit multimnožinu nezáporných čísel na dvě tak, že v obou bude součet obsažených čísel stejný? Izomorfismus podgrafu • Je graf H izomorfní nějakému podgrafu grafu G? Problém batohu • mějme batoh o nosnosti Wan předmětů, každý o hmotnosti wi a hodnotě ví • Lze do batohu umístit předměty o celkové hodnotě alespoň VI Součet podmnožiny • Lze najít podmnožinu zadané množiny celých čísel takovou, že součet jejích prvků je nula? xkcd.com/287 MY HOBBY: Embedding np-odmpletc toblems in restaww orceks CHOTCKM^ej, Kin* ft*£D FRUIT French fries Side Salad Hot Wings Mozzareua Sticks swler plate ^ Sandwiches WE'D LIKE EXACTLY J 15t 05 ...EXACTLY? UKK. HERE, THESE ^PERSON THE KNtf5/*X PFOeUN rilGHT KELP YW OUT. \ LISTEN, 1 HAVE Six OTHER TABLES TP GET TO - -A& FAST AS POSSIBLE, Of CWR5f- WWT SOMETHING ON TRAVELING SflLESMfo? General solutions get you a 50% tip. P vs. NP - poznámky Možné výsledky • P = NP, ale nejlepší algoritmus pro TSP se složitostí Q(n100) • P ^ NP, ale algoritmus pro TSP se složitostí 0(2°'oa"ol7í) Možnosti řešení 1. přijmout exponenciální algoritmus 2. omezit se na speciální případy (př. izomorfismus stromů je v P) 3. přijmout suboptimální řešení (užitím hladových algoritmů, heuristik) Zajímavé odkazy • Netypická varianta TSP: https://www.math.uwaterloo.ca/tsp/pubs/index.html • Přehled důkazů P vs. NP: https://www.win.tue.nl/~wscor/woeginger/P-versus-NP.htm • Redukce mezi NP-úplnými problémy: https://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf