Kapitola 1
Státnice - Metody tvorby algoritmů

1.1 Popis složitosti algoritmů

Definice (Velikost dat, krok algoritmu)

Velikost dat je obvykle počet bitů, potřebných k jejich zapsání, např. data jako pro čísla je velikost dat .

Krok algoritmu je jedna operace daného abstraktního stroje (např. Turingův stroj, stroj RAM), zjednodušeně jde o nějakou operaci, proveditelnou v konstantním čase (např. aritmetické operace, porovnání hodnot, přiřazení – pro jednoduché číselné typy).

Definice (Časová složitost)

Časová složitost je funkce taková, že udává počet kroků daného algoritmu, pokud je spuštěn na datech .

Definice (Asymptotická složitost)

Řekneme, že funkce je asymptoticky menší nebo rovna než , značíme je , právě tehdy, když

Funkce je asymptoticky větší nebo rovna než , značíme je , právě tehdy, když

Funkce je asymptoticky stejná jako , značíme je , právě tehdy, když

Funkce je asymptoticky ostře menší než ( je , když

Funkce je asymptoticky ostře větší než ( je , když

Poznámka

Asymptotická složitost zkoumá chování algoritmů na velkých datech, zařazuje je podle toho do kategorií. Zanedbává multiplikativní a aditivní konstanty.

1.2 Rozděl a panuj

Definice (Metoda rozděl a panuj)

Rozděl a panuj je metoda návrhu algoritmů (ne strukturované programování), která má 3 kroky:

1. rozděl – rozdělí úlohu na několik podúloh stejného typu, ale menší velikosti

2. vyřeš – vyřeší podúlohy a to buď přímo pro dostatečně malé, nebo rekurzivně pro větší

3. sjednoť – sjednotí řešení podúloh do řešení původní úlohy

Aplikace

- QUICKSORT

- Hledání mediánu

Analýza složitosti algoritmů rozděl a panuj

Poznámka (Vytvoření rekurentní rovnice)

Pro časovou složitost algoritmů typu rozděl a panuj zpravidla dostávám nějakou rekurentní rovnici.

- budiž doba zpracování úlohy velikosti , za předpokladu, že pro .

- budiž doba na rozdělení úlohy velikosti na podúloh stejné velikosti .

- budiž doba na sjednocení řešení podúloh velikosti na jednu úlohu velikosti . Dostávám rovnici

Poznámka

Při řešení rekurentních rovnic:

- Zanedbávám celočíselnost ( místo a )

- Nehledím na konkrétní hodnoty aditivních a multiplikativních konstant, asymptotické notace používám i v zadání rekurentních rovnic, i v jejich řešení.

Věta (Substituční metoda)

1. Uhodnu asymptoticky správné řešení

2. Indukcí ověřím správnost (zvláště horní a dolní odhad)

Věta (Metoda “kuchařka” (Master Theorem))

Nechť a nechť je neklesající funkce taková, že tvaru platí

Potom

1. Je-li , pak je

2. Je-li , pak je

Věta (Master Theorem, varianta 2)

Nechť , kde a jsou reálná čísla a nechť splňuje rekurenci

Nechť je číslo řešením rovnice . Potom

1. Je-li (tedy ), pak je

2. Je-li (tedy ), pak je

1.3 Dynamické programování

Dynamické programování je metoda řešení problemů, které v sobě obsahují překrývající se subproblémy.

Příklad

Typickým příkladem je výpočet fibonaciho čísla. Fib. posloupnost je definována jako:

Výpočet třeba 4. čísla by pak byl . Vidíme, že jsme počítali dvakrát, třikrát a dvakrát. Ve větším měřítku toto zbytečně počítání vede k exponenciální složitosti algoritmu. Lepší cestou je počítat “od spodu”, kdy pomoci a spočteme , pak s jeho pomoci nakonec s lineární složitosti.

V dynamickém programování se například vytvoří mapa Fibonacciho čísel a jejich hodnot. Před tím, než začnu počítat hodnotu nějakého Fibonacciho čísla, se podívám do mapy.

Nutné podmínky

V dynamickém programování využíváme:

1. Překrývání podproblému — problém lze rozdělit na podproblémy, jejichž řešení se využívá opakovaně.

2. Optimální podstruktury — optimální řešení lze zkonstruovat z optimálních řešení podproblémů.

Postupy

Obvykle se používá jeden ze dvou přístupů k dynamickému programování:

- Top-down — problém se rekurzivně dělí na podproblémy a po jejich vyřešení se zapamatují výsledky, které se použijí při případném opětovném řešení daného podproblému.

- Bottom-up — nejdříve se spočítají všechny možné podproblémy (viz příklad s Fibonacciho posloupnosti), které se potom skládají do řešení větších problémů. Tento přístup je výhodnější z hlediska počtu volání funkci a místa na zásobníků, ale ne vždy musí být zřejmě, které všechny subproblémy je třeba předem spočítat.

Použití

Problém batohu – máme věci různé váhy a batoh určité nosnosti. Které věci máme dát do batohu, abychom jej co nejlépe zaplnili (jednorozměrná varianta problému batohu)? Speciální případ je součet podmnožiny (SP). Algoritmus je popsán v sekci o NP-úplnosti.

Uzávorkování součinu matic tak, aby počet skalárních součinů byl co nejmenší. Dělá se pomocí 2 čtvercových matic ( a ) řádu rovného počtu násobených matic, kde pracujeme jen nad diagonálou. Hodnota na udává minimální počet skalárních součinů při nejlepším uzávorkování matic až , hodnota určuje matici, která rozděluje závorkování na dvě podmnožiny matic. Hodnotu lze zkonstruovat ze všech a pro .

1.4 Hladové algoritmy

Motivace

Problém 1

Dán souvislý neorientovaný graf a funkce , udávající délky hran. Najděte minimální kostru grafu , tj. kostru tak, že je minimální.

Problém 2

Je dána množina úkolů jednotkové délky. Ke každému úkolu je dána lhůta dokončení a pokud , kterou je úkol penalizován, není-li hotov do své lhůty. Najděte rozvrh (permutaci úkolů od času do času ), který minimalizuje celkovou pokutu.

Problém 3

Je dána množina úkolů. Ke každému úkolu je dán čas jeho zahájení ukončení , . Úkoly a jsou kompatibilní, pokud se intervaly a nepřekrývají. Najděte co největší množinu (po dvou) kompatibilních úkolů.

Matroid

Definice (Matroid)

Matroid je uspořádaná dvojice , splňující:

- je konečná neprázdná množina (prvky matroidu )

- je neprázdná množina podmnožin (nezávislé podmnožiny), která má

1. dědičnou vlastnost: ,

2. výměnnou vlastnost: .

Věta (O velikosti maximálních nezávislých podmnožin)

Všechny maximální (maximální vzhledem k inkluzi) nezávislé podmnožiny v matroidu mají stejnou velikost.

Důkaz

Z výměnné vlastnosti, nechť maximální, , pak , což je spor.

Definice (Vážený matroid)

Matroid je vážený, pokud je dána funkce a její rozšíření na podmnožiny množiny je definováno předpisem:

Problém 1 a 2 – zobecněný

Pro daný vážený matroid nalezněte nezávislou podmnožinu s co největší vahou (optimální množinu). Protože váhy jsou kladné, vždy se bude jednat o maximální nez. množinu.

Problém 1 je spec. případ tohoto, protože můžeme uvažovat grafový matroid (nad hranami) – , kde a pro platí , pokud hrany z netvoří cyklus (tj. indukovaný podgraf tvoří les).

Dědičná vlastnost této struktury je zřejmá, výměnnost se dá dokázat následovně: mějme . Pak lesy z mají stromů (vč. izolovaných vrcholů). V musí být strom, který se dotýká různých stromů z . Ten obsahuje hranu, která není v žádném stromě a netvoří cyklus a tak ji můžu k přidat.

Váhovou funkci převedu na hledání maxim: , kde je dost velká konstanta, aby všechny váhy byly kladné. Algoritmus pak najde max. množinu, kde hrany netvoří cyklus. Implicitně bude mít hran, takže půjde o kostru a její bude maximální, tedy původní váha minimální.

Pro problém 2 zavedeme pojem kanonického rozvrhu – takového rozvrhu, kde jsou všechny včasné úkoly rozvrženy před všemi zpožděnými a uspořádány podle neklesající lhůty dokončení (tohle na celkové pokutě nic nezmění a máme bijekci mezi množinou včasných úkolů a kanonickými rozvrhy).

Optimální množinu pak lze hledat jen nad kanonickými rozvrhy – nezávislou množinou úkolů nazvu takovou, pro kterou existuje kanonický rozvrh tak, že žádný úkol v ní obsažený není zpožděný. Potom hledání max. nezávislé množiny při ohodnocení pokutami je hledání nejmenší pokuty (odeberu co nejvíc z možné celkové pokuty).

Pak zbývá dokázat, že takto vytvořená struktura je matroid. Dědičná vlastnost je triviální – vyhodím-li něco z nezávislé množiny, nechám v rozvrhu mezery a bude platit stále. Pro výměnnou vlastnost zavedu pomocnou funkci , udávající počet úkolů z množiny se lhůtou do času . Pak množina je nezávislá, právě když .

Pak máme-li 2 nezávislé , , , označíme největší okamžik takový, že , tj. od dál platí . To skutečně nastane, protože . Pak určitě v je ostře víc úkolů s než v , tj. se lhůtou . je nezávislá, protože pro a pro .

Hladový algoritmus na váženém matroidu

Algoritmus (Greedy)

Mám zadaný matroid , kde a . Potom

1. , setřiď a přeznač sestupně podle vah

2. pro každé zkoušej: je-li , tak

3. vrať jako maximální nezávislou množinu

Pokud přidám nějaké , nikdy nezruším nezávislost množiny; s už přidanými prvky se nic nestane. Časová složitost je na setřídění podle vah, testování nezávislosti množiny závisí na typu matriodu (), takže celkem něco jako .

Důkaz

- Vyhození prvků, které samy o sobě nejsou nezávislé množiny, nic nezkazí (z dědičné vlastnosti).

- První vybrané je “legální” (nezablokuje mi cestu), protože mezi max. nez. množinami určitě existuje taková, která jím mohla vzniknout (z výměnné vlastnosti – vezmeme první prvek, který je sám o sobě nez. mn. a s pomocí nějaké max. nez. množiny ho doplníme, vzniklé musí být také maximální).

- Nalezení optimální množiny obsahující pevné (první vybrané) v je ekvivalentní nalezení optimální množiny v , kde a (je-li neprázdná, je to matroid, vlastnosti se přenesou z původního; pokud je prázdná, tak algoritmus končí) a tedy když vyberu , nezatarasím si cestu k optimu – stačí ukázat, že je optimální v právě když je optimální v .

- Takže když budu vybírat (indukcí opakovaně) podle váhy, dojdu k optimální množině.

Algoritmus (Hladový algoritmus na problém 3)

Máme množinu úkolů s časy startů a konců . Provedeme:

1. ,

2. setřiď úkoly podle vzestupně a přeznač

3. pro každé zkoušej: je-li , pak a

4. vrať jako max. množinu nekryjících se úkolů

Složitost je na setřídění, zbytek už lineární. Sice to funguje, ale tahle struktura NENÍ matroid – nesplňuje výměnnou vlastnost. Algoritmus má ale stejný důkaz jako předchozí na matroidech (legálnost hladového výběru – existuje max. množina obsahující prvek – a existenci optimální množiny – převod na “menší” zadání).