Számítógép és programozás 2

Számítógép és programozás 2

8. Előadás Megoldhatóság, hatékonyság

http://digitus.itk.ppke.hu/~flugi/

Elméleti áttekintés a SzámProg 1 tárgyból ●

Algoritmikus eldönthetőség kérdése

●

Bizonyíthatóság kérdése, Gödel

●

Terminálási probléma (Turing)

●

Chomsky nyelvosztályok

●

Eldönthetőségi probléma a nyelvosztályokban

●

Rekurzívan és parciálisan rekurzívan eldönhető problémák

Eldönthetőség, kiszámíthatóság ●

●

●

Létezik-e algoritmus (egyszer leírt végleges megoldás minden esetre) egy adott specifikációhoz? Eldönthető: –

Döntsd el egy egész számról, hogy páros-e!

–

Add meg egy véges sorozat legnagyobb elemét!

Vannak nem eldönthető kérdések!

Terminálási probléma ●

●

●

Nem készíthető program, amely bármely programot elemezve eldönti, hogy végtelen ciklusba kerül-e. Az állítás bizonyítása meglehetősen hasonlít Gödel tételére, illetve Cantor bizonyítására Indirekt bizonyítás: tegyük fel, hogy a terminálási probléma kiszámítható, és van is egy függvényünk, TERM(P,A), ami P függvényről eldönti, hogy A adattal terminál-e.

Terminálási probléma ● ●

●

Tehát TERM(P,A) = {igaz, hamis} Ahogy Gödelnél, a programok és az adatok egyaránt megszámozhatóak, így használhatjuk azt az esetet, hogy TERM(x,x) Legyen G(A) { if(TERM(A,A)) while(1); else return hamis; }

●

..és legyen az A paraméter G számértéke!

●

Ez ellentmondás.

Chomsky nyelvosztályok ●

●

Példa nyelvtanra: S → aSb | ab generálja az {ab, aabb, aaabbb, ..} nyelvet, mert –

Minden ilyen szó generálható: n-1-szer az első, és egyszer a második szabály alkalmazásával

–

Csak ilyen szó generálható, mert minden szabály garantálja, hogy ugyanannyi a és b karakter kerül a szóba, és az a-k mindig a közepe elé, a b-k a közepe mögé

A kérdés: eldönthető-e tetszőleges szóról, hogy generálja-e a nyelvtan?

„big O notation”, Ordo ●

●

O(f(n)) jelölés: egy algoritmust jellemez, hogy a futásidejét hogyan lehet becsülni az adat egy paramétere alapján –

maximumkeresés: O(n)

–

maximumkiválasztásos rendezés: O(n2)

–

quicksort: O(log2 n)

Most futásidő mellett memóriaigényre is használni fogjuk

Chomsky nyelvosztályok ●

●

A szóprobléma eldönthetősége és hatékonysága a szabálykészlettől függ: –

L3: A → a | aB

–

L2: A → u

–

L1: uAv → uwv

–

L0: u → v ahol A ∈ N, a ∈ T, u,v,w ∈ {N ∪ T}*

L3 lineárisan eldönthető, L2 köbösen, L1 exponenciálisan, L0 sehogy.

Eldönthető, felsorolható ●

●

●

L0 felsorolható: A szabályok szisztematikus felhasználásával kapott szavak kötött sorrendben keletkeznek, idővel bármely szó megjelenik így L0 nem eldönthető: ha arra várunk, hogy egy szó kijön-e a szisztematikus szabályalkalmazásból, nem terminálunk, ha a válasz nemleges. L1 eldönthető: a szó csak egyre hosszabb lehet, ami terminálási feltételre ad lehetőséget

Nyelvosztályok összefoglalva ●

Chomsky nyelvosztályok –

L3, reguláris: lineáris időben eldönthető a szóprobléma

–

L2, környezetfüggetlen: köbös időben eldönthető a szóprobléma

–

L1, hosszúságot nem csökkentő szabályok: exponenciális időben eldönthető a szóprobléma

–

L0, tetszőleges szabályok: parciálisan rekurzív, csak akkor ad választ az algoritmus, ha a szóprobléma megoldása az „igaz”

Rekurzívan felsorolható, rekurzívan eldönthető ●

●

Church, Turing, Kleene, Gödel tételei alapvetően rekurzív függvényekre épültek Miért fontos a rekurzív függvény a számítástudományban? –

Mert könnyű kiértékelni algoritmikusan

–

Az így készült program helyessége könnyebben bizonyítható

Rekurzív függvény kiértékelése ●

●

●

maxn(S) = S[n], ha S[n] > maxn-1(S) maxn-1(S) különben A ciklusmag a tételben: if (S[n] > max) {max = S[n];} else {max=max;} Nyilvánvaló az egyezés, látható, hogy mechanikusan építhető ciklus olyan rekurzív függvényre, amely csak az előző értékre hivatkozik

Kiszámíthatóság összefoglalás ●

●

●

Rekurzív függvényekkel felírt problémákat könnyen algoritmizáljuk Church-Turing Tézis: –

Amit ki lehet számolni valahogy, azt rekurzív függvénnyel is ki lehet számolni

–

Azaz: amit ki lehet számolni valahogy, azt algoritmussal is ki lehet számolni

Van, amit nem lehet kiszámolni egyáltalán, pl. terminálási probléma.

Döntési probléma ●

●

●

Minden feladat, aminek a kimenete egyetlen logikai érték Példák: –

szóprobléma

–

prímszám-e

–

terminálási probléma

Sok feladat átfogalmazható döntési feladatra, de van, ami nem, pl. optimalizálási feladatok

Keresési/optimalizálási feladatok ● ●

●

Az algoritmus bemenete egy halmaz (leírása) Kimenete egy elem a halmazból, amire teljesül a feltétel (optimalizálásnál egy szélsőértéke a célfüggvénynek) Példák: –

rendezések: melyik az a permutáció, amelyikre igaz a rendezettség

–

Rubik kocka kirakásához szükséges lépéssorozat ●

minimális?

P vs NP ●

●

A döntés folyamata szerint a megoldó algoritmus –

P, ha determinisztikus és polinomiális időben végez

–

NP, ha nemdeterminisztikus, és polinomiális időben választ adhat

Kitérő: nemdeterminisztikus algoritmus –

előre nem megadott lépések, véletlenszerű választások, a lehetőségek között ha van kedvező, akkor a lehetőség miatt a megoldás útjának ez tekinthető ●

pl. nemdeterminisztikus automata és a szóprobléma

P vs NP ●

P részhalmaza NP-nek

●

Az, hogy P =?= NP, jelenleg nyitott kérdés –

●

Sokak szerint a válasz „nem”, de nincs bizonyítva

NP-teljes problémák: olyan problémák, amikre létezik ismert NP megoldás, és egymásra levezethetőek O(n) időben –

vagyis, ha egyikről kiderül, hogy P, akkor a többi is.

Híres NP-teljes problémák ●

Hamilton kör léte –

●

Utazó ügynök probléma

Pakolási probléma –

Részösszeg probléma

●

Izomorfizmus gráfokban

●

Gráf színezés

● ●

… (több mint 3000 másik) Sudoku, aknakereső, stb

NP-teljes problémák ●

Pozitív: megoldhatóak

●

Negatív: lassan, általános esetben

●

Sok esetben felismerhető egy-egy speciális eset, amivel könnyen választható egyszerűbb megoldás –

tipikusan gyakran a rejtvényújság Sudoku rejtvényei lineáris időben megfejthetőek

–

pakolási probléma és a váltópénz minimális darabszáma is jó példa: a váltópénz címleteit szándékosan úgy választják meg, hogy a lineáris idejű megoldás optimális legyen

NP-teljes problémák ●

Máskor a megoldás minőségével szembeni követelményeket enyhítik –

Pakolási probléma operációs rendszer munkafolyamatain a memóriában ●

●

●

mindig az igényelt memóriánál legkevésbé nagyobb helyet adni: O(n) nem optimális, de nem sokkal rosszabb

Heurisztika: gyakorlati tapasztalatból adódó, feltételezésekre építő elem az algoritmusban

A keresési feladat megoldása ● ●

Legyen a lehetséges megoldások halmaza M ciklus { X legyen egy tetszőleges eleme M-nek } amíg X nem megoldás

●

Kicsit lassú

●

Viszont minden keresési feladat őse –

A keresési feladatok csak abban különböznek, hogy milyen stratégia szerint vizsgálnak meg egy elemet előbb, vagy később

Ingyen leves tétel ●

●

● ●

Nincs ingyen leves: nincs mindenre jó keresési stratégia Tetszőleges, egyébként egy részterületen kiváló keresési stratégiához létezik olyan másik részterület, ahol nem jó P(A talál n lépésben) = P(B talál n lépésben) Más szavakkal: az adott részterület sajátságainak kihasználása nélkül pont olyan hatékony minden algoritmus (pl. az előző is)

Az ingyen leves tétel következménye ●

Egy használható keresési-optimalizálási megoldásnak rendelkeznie kell ismerettel a problémáról –

Heurisztika

–

Tanulás reprezentáció

–

…

Genetikus algoritmus ●

● ●

●

Van egy fit(X) függvényünk, ami a feladat célfüggvénye legyen P egy részhalmaz M-ből ciklus amíg nem vagyunk elégedettek P legjobbjával –

P elemei közül a nagyobb fit() értékűekhez hasonlókat szaporítunk, az alacsonyabbakat töröljük

–

néhány elemet P-ben véletlenszerűen megváltoztatunk

ciklus vége

Genetikus algoritmus ●

Mit használunk ki? –

A fit függvény adott

–

A „hasonló szaporítása” reprezentációját már heurisztikusan választhatjuk

–

A mutációt is heurisztikusan választhatjuk

–

A múltbeli ismereteinket használjuk, körről körre az eddigi jó megoldásokat megtartjuk ●

feltételezzük, hogy a legjobb megoldáshoz vezető úton jobb és jobb megoldásokon keresztül megyünk a választott heurisztikákkal

Genetikus algoritmus példa ●

●

Hegymászás: adott egy hegy, aminek nem tudjuk hol a csúcsa, de azt tudjuk, hogy nincs másik lokális maximumpont –

szaporításnál a szülő(k) környékén véletlenszerűen választhatunk

–

így garantálva van, hogy a mindenkori legmagasabban levő példány van legközelebb az optimumhoz

Nagyon ritkán ilyen könnyű a feladat –

erre más megoldások, kiegészítések: maximális meredekség (gradiens), szimulált hűtés

Összefoglalás ●

●

A keresési és döntési feladatokat három osztályba sorolhatjuk: –

megoldhatatlan

–

lassan megoldható (pl. NP-teljes)

–

polinomiális időben megoldható

Az NP-teljes problémák kezelése a brute force mellett –

heurisztikus megközelítések

–

enyhített feltételek

Utazó ügynök probléma