Taxonomie problémů, případ NP není P

Všechny rozhodovací problémy

Nepřečíslitelné problémy

Přečíslitelné, ale nerozhodnutelnéproblémy

Doplňkově Nepřečíslitelné problémy

Doplňkově přečíslitelné problémy

Rozhodnutelné problémy

Nikoli NPproblémy

NP problémy

NP, ale neP problémy

P problémy

NP, ale ne NP úplné

NP úplnéproblémy

Taxonomie problémů, případ NP je P

Všechny rozhodovací problémy

Nepřečíslitelné problémy

Přečíslitelné, ale nerozhodnutelnéproblémy

Doplňkově Nepřečíslitelné problémy

Doplňkově přečíslitelné problémy

Rozhodnutelné problémy

Nikoli NPproblémy

NP problémy

NP, ale neP problémy

P problémy

NP, ale ne NP úplné

NP úplnéproblémy

Toto vše je to samé, jako NP

Jak obejít nepřijatelnou časovou složitost

• 1. Nahradit daný problém jiným problémem, který v polynomiálním čase řešit umíme a jehož řešení „není příliš odlišné“ od řešení původního problému, které nás zajímá, nebo se od něj příliš neliší „v převážné většině případů“.

• 2. Užít algoritmus pro řešení původního problému, jehož pesimistická časová složitost sice není polynomiální, nalézt však takovou jeho modifikaci, při které k časově neúnosně dlouhému výpočtu dochází spíše výjimečně a ve „většině“ případů je potřebná doba přijatelná.

• 3. Zpochybnit Churchovu tezi, tedy pokusit se o nalezení takového technického prostředku pro výpočet, který bude „umět více“, než Turingův stroj. To ovšem určitě nemůže být současný počítač založený na von Neumannově architektuře.

Algoritmy prořezávání stromu• Princip spočívá v tom, že v každé situaci, kdy musíme vyšetřit více

možností se věnujeme pouze těm, které jsou z nějakého důvodu perspektivní. Ty, které se jeví jako málo nadějné pro nalezení řešení vynecháme (prořežeme některé větve stromu možných postupů).

• Typická aplikace metody větví a hranic prvého typu (kdy si nemůžeme být jisti zda výsledek získaný v přijatelném čase je blízko hledanému, je tomu však tak „obvykle“) bývá užit v programech pro hru šachy. Zde program nezkoumá všechny možnosti vývoje pozic na šachovnici mnoho tahů dopředu, ale každou pozici hodnotí. Pokud se zdá neperspektivní (například proto, že došlo k velkým ztrátám materiálu), dále ji nerozvíjí a zvažuje jen pozice „nadějné“.

• Tato strategie je úspěšná většinou. Ne však vždy. Šachisté vědí, že některé „oběti materiálu“ mohou být výhodné a vést třeba k matu soupeře o několik tahů později. Tak se může stát že optimální cesta bude odříznuta předčasně.

Gradientní algoritmyV řadě optimalizačních algoritmů je vhodné volit metodu

postupného přibližování k optimu tak, že přiblížení volíme „tím směrem“, kde se sledovaná hodnota zlepšuje nejrychleji. Je to jako když horolezec chce dosáhnout vrcholu hory tak, že leze tím směrem, kterým je svah nejpříkřejší. V řadě případů to k cíli vede. Ne však vždy. Může se snadno stát, že horolezec, který si dal za cíl zdolat nejvyšší vrchol pohoří vyleze do sedla mezi dvěma vrcholy a na základě zvoleného principu vyleze na ten nižší z obou.

Hladové (greedy) algoritmy

• Během řešení úlohy volím vždy tu variantu, která se v daném lokálním okolí jeví jako nejvýhodnější. Ne vždy je ovšem zaručeno, že takto naleznu optimální řešení

• U některých úloh je to zaručeno (lineární programování a simplexová metoda)

• Existují i obecnější principy založené na hladovém postupu– Bellmanův princip optimality

Genetické algoritmy

• Genetické algoritmy jsou založeny na Darwinově evolučním principu vývoje populace živých organizmů přirozeným výběrem. V něm se genetická informace nové generace vytváří kombinováním (křížením) genetické informace úspěšných jedinců generace předchozí s připuštěním určitých samovolně vznikajících mutací.

Neuronové sítě

• Modelují naše představy o funkci mozku u vyšších živočichů a člověka.

Soma

Synapse

Dendrity

Axon

x1

x2

xn

σ(ξ)

w1

w2

wn

y

1

x0 = -h

Paraelní systémy

Tradiční paralelizmus (výpočetní systémy na principu SIMD, MIMD, multicube, … ) pro řešení úloh, kde není znám polynomiálně složitý algoritmus příliš nepomohou.

Je-li K procesorů, zvýší se propustnost systému nejvýše K- krát. Třídu složitosti to neovlivní.

Kvantové počítače

• Foton se může nacházet „současně na více místech“ (s různou pravděpodobností). Nemá deterministicky určenou polohu. To dává šanci elementární částice užít přímo pro modelování nedeterministického Turingova stroje či jiného modelu nedeterministického výpočtu.

• Ve stádiu předběžných úvah a neurčitých záměrů

Chemické počítače

• Data jsou reprezentována různými koncentracemi chemikálií na vstupu. Výpočet je modelován průběhem chemické reakce.

• Ve stádiu předběžných úvah a neurčitých záměrů

DNA počítače

• Myšlenka založena se schopnosti řetězců aminokyselin DNA vytvářet masivně vlastní kopie paralelně. Výpočet by byl realizován jako biologický experiment. Pokud se aminokyseliny spojí do vhodného řetězce, lze jej považovat za řešení úlohy.

• Lepší perspektivu skýtají možná peptidy (12 bází místo 4 bází u DNA).

• Ve stádiu předběžných experimretnů

Analogové počítače• Jsou starší než číslicové. • Ke škodě věci se na ně poněkud pozapomenulo. • Vytvoří se fyzikální, obvykle spojitě pracující

model děje (mechanický, hydraulický, elektromagnetický, …), který se řídí stejnými nebo podobnými zákony jako řešený problém.

• Nechá se proběhnout vývoj na tomto modelu. • Výsledek poskytne informaci o řešení původního

problému. • Dávno známé, dnes možná neprávem poněkud

opomíjené

Toky v sítích

Síť• Síť je orientovaný graf, jehož hrany jsou ohodnoceny

nezápornými reálnými čísly a ve kterém vyznačíme dva uzly– zdroj – obvykle značíme z– spotřebič – obvykle značíme p

• Formálně: Síť je čtveřice (G, z, p, c), kde– G je orientovaný graf– z je uzel grafu G, do nějž nevchází žádné hrany– p je uzel grafu G, z nějž nevychází žádné hrany– c: HR+

0 je funkce přiřazující hranám ohodnocení (kapacitu, maximální průtok)

Tok• Je dána síť N = (G, z, p, c). Tokem v síti nazveme takové

ohodnocení hran f: HR+0, které splňuje

– kapacitní omezení: 0≤f(h)≤c(h) pro každé hH– zachování toku (Kirhofův zákon): pro každý uzel kromě

zdroje a spotřebiče je součet toků ve vstupních hranách roven součtu toků ve výstupních hranách

• Velikost toku |f| je součet toků výstupních hran zdroje (= vstupních hran spotřebiče)

strana 16

)()(

)()(:},{vHhvHh

hfhftsUv

Řez• Řez v síti je taková množina hran, po jejichž odstranění by v

síti nezbyla žádná cesta ze zdroje do stoku– velikost řezu je rovna součtu kapacit hran v řezu

• Analogická definice řezu je rozklad množiny uzlů na dvě disjunktní podmnožiny, z nichž jedna obsahuje zdroj a druhá spotřebič– velikost řezu je rovna součtu kapacit hran spojujících uzly v

různých třídách rozkladu• Velikost řezu značíme

– c(H), je-li H množina hran tvořící řez– c(A,B) jsou-li A, B třídy rozkladu tvořící řez

• Počet všech možných řezů je 2|V|-2

strana 17

Velikost toku a velikost řezu

• Věta: Je-li f tok a (V,W) řez, pak platí|f| ≤ c(V,W)– Tedy: Pro každý tok a každý řez platí, že

velikost toku není větší než velikost řezu

strana 18

Další síťové pojmy• Maximální tok v síti je takový tok, který má největší

možnou velikost.• Rezervní kapacita hrany

cf(h) = c(h) – f(h)– je-li cf(h) = 0, hovoříme o nasycení hrany h

• Rezervní kapacita cesty je minimum rezervních kapacit hran na této cestě

• Nasycená cesta je cesta s nulovou rezervní kapacitou– tj. některé hrana je nasycená

• Rezervní síť je podgraf tvořený pouze hranami s kladnou rezervní kapacitou

strana 19

Rozšiřující cesta a polocesta• Rozšiřující (též zlepšující) cesta je cesta ze z do p taková, že pro

každou hranu platí, že cf(h)>0• Rozšiřující (též zlepšující) polocesta je cesta z z do p v

symetrizaci sítě taková, že– pro každou hranu ve směru cesty platí, že f(h) < c(h)– pro každou hranu proti směru cesty platí, že f(h) > 0

• Tok po hraně ve směru cesty lze snížit, tok po hraně proti směru cesty lze zvýšit.

• Rezerva hrany je rovna– rezervní kapacitě hrany, tj. c(h) – f(h) pro hrany ve směru

cesty– toku přiřazenému hraně, tj. f(h) pro hrany proti směru cesty

strana 20

Proč je třeba uvažovat i o „zpětných“ hranách

Maximální tok a rozšiřující polocesta

• Věta: Velikost toku v síti je maximální právě tehdy, když v rezervní síti neexistuje rozšiřující polocesta

• Důkaz : Kdyby existovala rozšiřující cesta, bylo by možné navýšit tok o rezervní kapacitu této cesty, tudíž by tok nebyl maximální

• Důkaz : Pokud by tok nebyl maximální, bylo by možné nalézt tok větší. Označme rozdíl velikosti toků d. Je-li však možné tok zvýšit o d, musí existovat rozšiřující polocesta s rezervní kapacitou d.

strana 22

Věta o maximálním toku a minimálním řezu

• Věta: Maximální velikost toku v síti je rovna minimální velikosti řezu

• Zobecnění: Následující tvrzení jsou ekvivalentní– f je maximální tok– v síti neexistuje zlepšující cesta– existuje řez (S,T) takový, že |f| = c(S,T)

strana 23

Hledání maximálního toku v síti

• Fordův-Fulkersonův algoritmus• U každé hrany udržujeme dvojici (tok, kapacita)• Nalezneme rezervní polocestu ze zdroje do

spotřebiče• Identifikujeme nejmenší rezervu hrany na této

cestě – to je rezerva polocesty• Na hranách ve směru cesty zvýšíme tok o • Na hranách proti směru cesty snížíme tok o • Opakujeme tak dlouho, dokud existuje rezervní cesta

strana 24

Edmonds-Karpův algoritmus I.

• Zefektivnění Fordova-Fulkersonova algoritmu• Nejnižšího počtu iterací dosáhneme, hledáme-li

rezervní tok na nejkratší možné polocestě (vzhledem k počtu hran)

• Edmonds-Karpův algoritmus k nalezení nejkratší rezervní cesty využívá prohledávání grafu do šířky

strana 25