UL/FRI/VSP-RI/OAPS2/HitriZapiski/2006-03-02:frin

Osnovni principi reševanja problemov

Razumevanje

• zahteve
• nedvoumna
• dejstva, pravila, cilji
• implicitni podatki -> eksplicitni
• obvezni

Abstrakcija

• objekti: imena
• relacije

starost Jožefine = 3*(Rožle-10) // 3x kot R pred 10 leti

• operacije
• graf // nam predstavlja problemski prostor, graf -> drevo

Objekti, relacije in operacije: problemski prostor

Notacija, ključna!

Definicija: notacija je simbolična predstavitev, ki modelira skupne značilnosti razreda objektov ali situacije in možne operacije na simbolih.

• slikovna
• besedna
  • okrajšave za koncepte, ki so v pomoč spominu pri reševanju problemov, okrajšava je pomembna, da hitreje sprocesiramo podatek. Tisto kar označimo s simboli so:

1. objekti, veličine
2. operacije, relacije

Za imena objektov uporabljamo alfanumerične simbole.

Operacije in relacije se tako razlikujejo od objektov da za to uporabljamo drugačne simbole, ki niso sestavljeni iz alfanumeričnih simbolov ampak posebnih simbolov (+, -, =, >, <). Ti simboli povdarjajo da gre za operacijo oz. relacijo.

Prej ali slej moramo izbrati formalni sistem, znotraj katerega bomo reševali naš problem. Formalni sistem bo programski jezik. Poleg p.j. so:

• algebra
• geometrija
• teorija množic
• izjavni račun
• predikatni račun 1. reda
• ...

Na koncu bo naš formalni sistem programski jezik. Izbira formalnega sistema je tisto kar omogoča, da bomo učinkovito rešili naš problem. Iz realnega sveta moramo prevesti opis našega problema v formalni sistem. Ko imamo ta zapis iščemo rešitev na sintaktičnemu nivoju. Dobimo neko rešitev, ki jo moramo interpretirati (najti nazaj povezavo rešitev -> realni svet). S formalnim sistemom smo učinkovito, hitro našli našo rešitev, zdaj pa moramo rešitev preveriti, če ustreza realnemu svetu (starost 300 let ali -15 let za Jožefino ni primerna), interpretacija.

Tone vrže žogo navpično navzgor 8m/s, do stropa je 3 metre. Kako dolgo bo žoga letela do stropa?

Kvadratna enačba:

Naša enačba predvideva da bo šla žoga čez strop in čez čas padla nazaj, zato dobimo 2 rešitvi. Primerna je le rešitev t₂.

Razbitje problema na podprobleme

Realni problemi so kompleksni in je nujno razbiti problem na podproblem.

Najpogosteje je razbitje problema od zgoraj navzdol. Alternativa je od spodaj navzdol.

Zgoraj navzdol:

• imamo cel problem, ki ga želimo razbiti na podprobleme, razbijamo toliko časa, dokler niso problemi dovolj majhni, da se jih znamo lotiti. (predstava: drevo root -> listi). Primer: hanoiski stolpi

Spodaj navzgor:

• redkeje se uporablja, uporabljamo ko pri razbitju od zgoraj navzdol se nam zatakne. Poskušamo najti preproste podprobleme, ki bi eventuelno pomagali pri rešitvi celotnega problema. Potem poskušamo rešitve povezovat za rešitve bolj zapletenih problemov, in tako naprej navzgor. To idejo uporablja dinamično programiranje.

Realno poskušamo kombinirati oba pristopa.

Problem faktorele: z rekurzijo smo jo rešili od zgoraj navzdol (ni repna rekurzija in je ne moremo direktno spremeniti v iteracijo). Iterativno implementacijo smo dobili z dinamičnim programiranjem od spodaj navzgor (najprej robni primeri, s pomočjo teh preprostih rešitev gradimo faktorelo za večje argumente).

Podobnost med problemi

Pri iskanju rešitve našega probleme, pri razvoju algoritma si pogosto lahko pomagamo s podobnostjo med problemi. Uporabimo različne transformacije:

• problem lahko poenostavimo, pri metanju žoge smo zadevo poenostavili, kot da stropa ni, samo moramo paziti pri rešitvah
• problem lahko posplošimo, če je problem posplošen pogledamo na problem kot na globalno zadevo, konstanta -> spremenljivka, ta bolj globalen pogled na zadevo nam lahko omogoči da najdemo rešitev probleme
• lahko ga reformuliramo, in spremenjeni problem rešujemo ker nam je bolj domač ali smo podoben problem že rešili. Z rešitvijo tega problema lahko skušamo rešiti originalen problem
• izomorfizem, spremenimo samo notacijo v drug problemski prostor. Preslikava je enolična in rešitev v drugem problemskem prostoru določa rešitev v iskanem problemskem prostoru. Primer: narisati hišo/pismo z eno potezo, da ne dvignemo svinčnika s papirja in nobene črte ne potegnemo 2x. Drug primer: domine.

Drug problem:

• tic tac toe
• 9 kart (1..9), izbrati 3 karte da imamo vsoto 15

2 7 6
9 5 1
4 3 8

Matematična indukcija:

1. robni primer, n=1,0
2. predpostavimo: n-1 -> n

Domača naloga iz matematične indukcije:

Imamo 5 profesorjev, ki spijo. Zlobni študent pride v sobo in jim pobarva obraze z zeleno barvo. Potem se profesorji zbudijo se pogledajo in se začnejo smejati drug drugemu. Potem pa najpametnejši med njimi ugotovi da je tudi sam pobarvan in se neha smejati. Vprašanje je, kako je to ugotovil? Posplošitev zadevo za n profesorjev in rešimo z matematično indukcijo

Algoritmi

Ko rešujemo problem z algoritmi je da poskušamo transformirati opis problema, ki govori Kaj je v problemu treba narediti, opis prenesemo v Kako.

Definicija: Algoritem je končno zaporedje natančno določenih ukazov, ki opravijo neko nalogo v končnem številu korakov. To predpostavlja omejitev, kaj se sploh da izračunati. Od algoritma zahtevamo da se v končnem številu korakov zaključi. Tisti programi ki se zaciklajo, niso algoritmi.

Algoritem ima vhodne podatke -> vrne rezultat (funkcija).

Program je algoritem, ki ga lahko izvajamo na računalniku, zapisan je v programskem jeziku.

Probleme, ki jih moramo rešiti pri razvoju algoritmov:

• kako izraziti algoritem (kakšno notacijo izbrati)

• diagrami poteka, vizualno predstavljajo algoritem
• psevdo koda, strukturiran naravni jezik, kjer poskušamo razdelati problem do te mere, da imamo dobro osnovo za končni algoritem zapisan v programskem jeziku. Pomeni, da lahko notri uporabljamo naravni jezik, tipično uporabljamo kontrolne konstrukte iz programskega jezika in ukaze programskega jezika, lahko pa uporabljamo tudi izraze iz drugih formalnih sistemov (enačbe). Uporabimo lahko tudi skice, diagrame poteka, ...

Naravni jezik->grobi opis: psevdo koda->...->fini opis: psevdo koda->programski jezik

Lahko so tudi cikli. Če vsak korak dobro naredimo, potem iteracije niso potrebne.

• programski jezik

• kako zasnovati algoritem (uporabimo principe reševanja problemov)
• kako analizirati algoritem (kako ugotoviti, kako se bo ta algoritem obnašal, predvsem nas zanima čas, ki je potreben da se algoritem zaključi in pomnilniški prostor, ki ga potrebuje za svoje izvajanje)

Ne analiziramo ga šele, ko je že napisan ampak je treba začeti že v zgodnji fazi razvoja algoritma.

Zanimata nas:

• čas
• asimptotična analiza: velikostni red, da nam samo občutek, kako hitro raste ta čas od odvisnosti od problema, ne govori v časovnih enotah (ne dela razlike med milisekundo in enim letom)
• dejanski čas

• prostor

• kako preveriti algoritem (kako preverimo ali je to res tisto kar smo želeli, ali je to pravilen algoritem, ali bo rezultat res pravi)

• branje in razumevanje algoritma, ki je problematično, če smo se zmotili pri pisanju algoritma in se lahko zmotimo tudi ko ga beremo in ga narobe razumemo. Je zelo pomembno, ampak ne garantira pravilnost algoritma. Moramo pisati čitljive programe, odvisna je predvsem od programskega jezika, najbolj pa od samega programerja. Izbrati moramo ustrezna imena, izogibamo se spremenljivkam, kot so "x, y, z, i, j". Ime je namenjeno tistemu, ki program bere.

komentarji so tudi pomembni, v komentar ne zapišemo tisto kar je razumljivo že iz kode.

• testiranje, pomembno je biti zloben, ne čustveno navezan na svoj program, preiskušati program na najtežje možne načine. Ekstremni primeri, ekstremna števila vhodnih podatkov, veliko zelo različnih vrednosti, deljenje z ničlo.

Testiranje pomeni dokazanje nepravilnosti. Da bi testirali ali dela pravilno bi morali testirati vse možne vhodne podatke, kar pa ni možno ker jih je ponavadi neskončno mnogo.

• formalni dokaz pravilnosti, ki enkrat zavselej dokaže, da je program pravilen. Problem dokaza je to, da je dokaz daljši od programa. Če se zmotimo v programu se lahko zmotimo tudi v dokazu in je dokaz brez učinka. Obstajajo programi, ki podpirajo dokazovanje pravilnosti.

Ne da se ga popolnoma avtomatizirati. Rabimo določeno ustvarjalnost, kjer je treba definirati neke pogoje. Vprašanje je kakšne pogoje je treba definirati, da bo dokaz dovolj močen, da bo program formalno dokazan.

Strategija preiskovanja prostorov

Strategije, ki iščejo optimalne rešitve

• izčrpno preiskovanje, preiščemo ves prostor in najdemo optimalno rešitev

• izkanje v širino

Problem preiskovanje naslednikov: zapomniti si moramo vse prednike, trati prostor

• v globino

Vedno gremo samo po najbolj levi veji drevesa, in šele ko tu pridemo do konca in ni rešitve, se vračamo nazaj in poskušamo po desni oz. drugi poti. Prostor tu ni problem, problem je ciklanje

• iterativno poglabljanje

kombinacije, ki izkorišča prednosti obeh, v širino in globino, omeji globino in potem iterativno podaljšuje globino (najprej pregledamo graf z globino 1, nato z globino 2, …). Tu pa je problem čas. Prostorsko ni problematično, ker imamo v pomnilniku vedno samo eno vejo. Čas pa je problem, saj pregledujemo že pregledane podatke.

• omejeno izčrpno (razveji in omeji, branch and bound)

Pogledamo naslednike v drevesu, vemo da so nekateri nasledniki neobetavni (slabši kot rešitev, ki jo že imamo) in jih ne gremo pregledovati. Ostane nam samo en del naslednikov, ki jih obdržimo in nadaljujemo iskanje.

Kvaliteta tega rezanja je odvisna od tega kako dobro poznamo problem.

• najprej najboljši, uporabljamo princip omejenega izčrpnega iskanja s tem da se odločimo za tistega, ki je najbolj obetaven, trati prostor.

To je ena najboljših strategij

• princip dinamičnega programiranja, gradimo rešitev od spodaj navzgor. Če ima problem ustrezne lastnosti, potem imamo lahko garantirano optimalno rešitev.

Strategije, ki iščejo približne rešitve

• požrešni (greedy) algoritmi, so algoritmi, ki se odločijo vedno samo za enega naslednika, glede na trenutno znanje. Vse ostalo vržemo stran. Rešitev ni garantirano optimalna, razen če je problemski prostor tako definiran.
• iskanje v snopu (beam search), posplošen požrešni, namesto samo enega možnega kandidata jih imamo k-možnih. k izberemo glede na to koliko časa imamo na voljo. Če k=1 potem je to požrešni algoritem
• zvezni prostori:

• gradientno iskanje (hill climbing), požrešni algoritem, ki se glede na odvod (na funkciji) odloči, kam bomo šli
• lokalna optimizacija (posplošitev požrešnega algoritma), izredno obetaven algoritem, naključno izberemo algoritem, to je naše začetno stanje in požrešno nadaljujemo preiskovanje, dokler še lahko izboljšamo potezo

Stohastični algoritmi

• genetski algoritmi, izredno obetaven