Skoči na: navigacija, iskanje

• principi reševanja problemov
• algoritmi
• pregled strategij preiskovanja

Vsebina 1 Principi reševanja problemov 1.1 Razumevanje 1.1.1 Primer 1.2 Notacija 1.2.1 Primer 1.3 Razbitje problema na podprobleme 1.4 Podobnost med problemi 2 Reševanje problema z algoritmi 2.1 Izražanje 2.2 Zasnova 2.3 Analiza algoritma 2.4 Preverjanje 3 Strategije preiskovanja

Principi reševanja problemov

Osnovni principi pri reševanju problemov so:

• razumevanje
• abstrakcija
• notacija
• razbitje problema na podprobleme
• podobnost med problemi
• izbira ustrezne strategije preiskovanja

Razumevanje

• zahteve
• nedvoumnost

nedvoumna definicija problema

• dejstva

kakšna dejstva so podana

• pravila

pravila za reševanje problema

• cilji

kaj želimo doseči

• implicitni podatki

tisti, ki pri samem opisu niso podani

dobimo jih iz konteksta

zapišemo jih eksplicitno da olajšamo razumevanje

• odvečni podatki

so tisti ki zamegljujejo celotni problem

nas ovirajo pri reševanju

Primer

Teta jožefina je sedaj 3x toliko stara kot rožle pred 10 leti. Rožle je sedaj pol toliko star kot jožefina. Koliko je jožefina starejša od rožleta?

Zanima nas razlika v starosti.

Dejstva

jožefina je trikrat starejša kot rožle pred 10 leti

Pravila

starost merimo v letih

z leti lahko računamo kot z naravnimi števili

Cilj

razlika v letih

Odvečni podatki

imena (Jožefina, Rožle)

sorodstveno razmerje (teta, nečak)

sedaj se osredotočimo samo na pomembne podatke in ignoriramo odvečne: ugotovimo kaj so pomembni objekti v naši definiciji problema in jih poimenujemo. Določimo relacije med temi odbjekti in definiramo operacije, ki so dovoljene nad temi objekti.

Ko definiramo te 3 stvari definiramo problemski prostor. Ko je problemski prostor definiran iščemo znotraj tega prostora rešitev.

Abstrakcija

• objekti (zanimajo nas samo starosti objektov, ostalo nas ne zanima)

J (starost jožefine)

R (starost rožleta)

• relacije (sestaviti je treba enačbo da odraža opis prostora)

(jožefina je 3x starejša kot rožle pred 10 leti)

• operacije

običajne operacije ki veljajo za cela števila z omejitvami

starost je izražena v letih, ne more biti negativna, ni večja od 150

Pri abstrakciji si je pogosto uporabno narisati graf, ki nam predstavlja problemski prostor.

Notacija

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

Od izbire notacije je ključno razumevanje reševanja problema.

Pri notacijah ločimo:

• slikovno notacijo

prometni znaki (prevladujoče v Evropi)

miselni vzorci

diagrami poteka

• besedno notacijo

prometni znaki (prevladujoče v Ameriki)

Besedni simboli so okrajšave za koncepte, ki so v pomoč spominu pri reševanju problemov.

Tisto kar označimo s simboli so:

• objekti (veličine)

uporabljamo imena iz alfanumeričnih simbolov

• operacije (relacije)

uporabljamo posebne simbole (+,-,=,<,>)

Formalni sistem znotraj katerega rešujemo naš problem:

• programski jezik
• algebra
• geometrija
• teorija množic
• izjavni račun
• predikatni račun prvega reda

Izbira pravega formalnega sistema nam omogoča, da problem pravilno rešimo.

Opis realnega sveta moramo prenesti v opis formalnega sistema.

Potem iščemo rešitev na sintaktičnem nivoju (pozabimo na realni svet, rešitev iščemo znotraj formalnega sistema).

Rešitev

Rešitev moramo interpretirati (najti povezavo rešitve z realnim svetom).

Primer

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

ko enačbo rešimo dobimo:

t₁ = 1s

Sedaj moramo zadevo prevesti v realni svet.

Ker se žoga v resnici odbije od stropa in ne gre skozenj, prva rešitev nima smisla. 2 rešitvi smo dobili ker smo dejstvo, da strop obstaja ignorirali. Torej žoga leti do stropa 3/5 s.

Razbitje problema na podprobleme

Tipično so problemi preveč kompleksni, da bi se jih lotili neposredno. Zato jih moramo razbiti na enostavnejše podprobleme.

Razbitje lahko poteka:

• od zgoraj navzdol

imamo cel problem, potem ga poizkušamo transformirati tako, da ga opišemo s podproblemi

to nadaljujemo dokler niso podproblemi dovolj majhni da se jih znamo lotiti

v programskem jeziku so to posamezni moduli, procedure ipd...

primer so hanoiski stolpiči katerega rekurzivno razbijemo na manjše (premik največjega diska, premikanje manjših skladov diskov)

primer faktoriele z rekurzijo

• od spodaj navzgor

se uporablja redkeje

uporabljamo ko ne vemo kako bi se lotili razbitja od zgoraj navzdol

poizkušamo najti nekaj podproblemov, ki bi eventuelno lahko pomagali pri rešitvi celotnega problema

to idejo uporablja dinamično programiranje

večina realnih problemov ni tako lepih

primer faktoriele z iteracijo (dinamično programiranje)

Podobnost med problemi

Podobnost predstavlja zmožnost da z različnimi transformacijami spremenimo probleme iz podobnega v tega.

Pri iskanju rešitve (razvoju algoritma) si pogosto lahko pomagamo s podobnostjo med problemi.

Transformacije

• poenostavitev

pri računanju meta žoge v strop poenostavimo kot da stropa ni

• posplošitev

pogledamo na zadevo bolj globalno

konstante definiramo s spremenljivko

• reformulacija

spremenjeni problem rešujemo (ker nam je bolj domač) glede na rešitev podobnega problema

• izomorfizem

transformacija problema v drug problem je taka, da spremenimo samo notacijo, preslikava pa ostane enolična

rešitev enolično določa problem v originalnem prostoru

• matematična indukcija

problem posplošimo na nek parameter

tipično je ta parameter naravno število

z indukcijo poizkusimo rešiti problem za vsa naravna števila

1. robni primer - n=1
2. splošni primer - predpostavimo da zadeva velja za n=1, iz tega poizkušamo izpeljati da zadeva velja tudi za n

---

   E
  / \
 C - D
 | × |
 A - B

Problem izomorfizma:

• Nariši pismo z 1 potezo brez da bi dvignil svinčnik s papirja.

oglišča poimenujemo s črkami

• Sestavi vse domine v vrsto (ploskve se morajo ujemati).

imajo oštevilčene ploskve - ploskve lahko označimo s črkami

Če najdemo algoritem za reševanje risanja pisma imamo algoritem za reševanje domin.

---

Izomorfni problem;

• Imamo problem igre 3 v vrsto - naloga algoritma je da zmaga v igri.
• Imamo 9 kart, vsaka ima število od 1-9, to so odprte karte. Izmenično izbirata karte nasprotna igralca, zmaga tisti, ki ima prvi tri karte z vsoto 15.

Če imamo algoritem, ki optimalno igra 1. igro, imamo algoritem, ki optimalno igra 2. igro zato, ker lahko 9 kart uredimo enako, kot igro 3 v vrsto tako, da so vse možne petnajstice v vseh možnih zmagah igre "3 v vrsto".

Reševanje problema z algoritmi

Poizkušamo transformirati opis problema kaj je potrebno narediti v opis postopka kako to narediti.

Algoritem je končno zaporedje natančno določenih ukazov, ki opravijo neko nalogo v končnem številu korakov. Algoritem dobi vhodne podatke in vrne rezultat, zato na algoritem lahko gledamo kot funkcijo.

Program je algoritem, ki je zapisan v programskem jeziku.

Problemi, katere moramo rešiti pri razvoju algoritmov:

• kako izraziti algoritem

kakšno notacijo izbrati

• kako zasnovati algoritem

uporabimo principe reševanja problemov

• kako analizirati algoritem

kako ugotoviti kako se bo ta algoritem obnašal

zanima nas čas ki je potreben da se algoritem zaključi in prostor, ki ga potrebuje za izvajanje

• kako preveriti algoritem

je to res to kar smo želeli?

ali deluje pravilno?

Izražanje

Gremo skozi več stopenj. Začnemo z naravnim jezikom, potem gremo v grobi opis (psevdokoda), stopnjujemo proti vedno bolj finem opisu (psevdokoda) in končamo s programskim jezikom.

• diagram poteka

vizualno predstavi algoritem

• psevdokoda

uporabljamo naravni jezik (kontrolne konstrukte iz programskega jezika in druge ukaze)

je strukturiran naravni jezik, kjer poizkušamo strukturirati problem do te mere, da imamo dobro osnovo za algoritem napisan v programskem jeziku

izrazi iz drugih formalnih sistemov (formule, enačbe ipd)

skice

• programski jezik

Zasnova

Uporabimo vse naštete principe razumevanja v osnovnih principih.

Analiza algoritma

Algoritem ni pametno analizirati, ko je že napisan. Analizo moramo narediti bolj zgodaj, da vidimo da zadeva ustreza časovnim in prostorskim zahtevam izvajanja.

Analiza časa:

• asimptotična analiza

govori o velikostnem redu časovne zahtevnosti

da nam občutek kako hitro raste čas v odvisnosti od velikosti problema

ne dela razlike med milisekundo in 1 letom - časovna enota tu ni pomembna - govori samo o hitrosti rasti zahteve po času

• dejanski čas

koliko časa zadeva zares potrebuje ko se izvaja na obstoječem hardware-u

Preverjanje

• branje

razumevanje algoritma

problematično - če se zmotimo pri pisanju se lahko zmotimo tudi pri razumevanju

pisanje čitljivih programov

ustrezno strukturirana koda

mnemonična imena spremenljivk

jasnost

komentiranost

če je koda dovolj razumljiva je komentar odveč

komentarji morajo opisovati dejansko stanje - morajo biti pravilni

• testiranje

pomembno je biti zloben

lotimo se programa tako, da ga želimo sesuti

pri tem pomagajo ekstremni primeri

• ekstremna števila
• brez vhodnih podatkov
• ogromno vhodnih podatkov
• null
• deljenje z ničlo
• itd...

testiranje lahko dokaže nepravilnost, ne more dokazati pravilnosti

nepravilnost dokažemo tako, da najdemo nabor podatkov, ki vrne napačen rezultat

dlje kot testiramo, manjša je verjetnost napak

ta verjetnost ni nikoli 0

• dokaz pravilnosti

ta dokaz enkrat za vselej dokaže da je program pravilen

problem dokaza je da je dokaz daljši od programa

temu se lahko izognemo s programsko opremo, ki podpira dokazovanje pravilnosti

formalno je zapleten

se redkeje uporablja

problem dokazovanja je, da se ga ne da popolnoma avtomatizirati

definirati moramo pravilne pogoje

Strategije preiskovanja

Imamo prostor, ki ga je potrebno preiskati. V tem prostoru iščemo rešitev našega problema. Najbolj optimalno rešitev najdemo, če preiščemo celoten prostor.

Strategije, ki:

• iščejo optimalne rešitve

• izčrpno preiskovanje

• v širino

drevo preiskujemo po nivojih (začetno stanje, naslednjike, naslednjike naslednjikov itd...)

pri tem imamo lahko probleme s prostorom ker si moramo zapomniti celotni prejšnji nivo ki raste eksponentno

• v globino

vedno gremo samo po eni veji (npr. najbolj levi)

ko pridemo do konca, če ne najdemo rešitve, se vračamo nazaj in iščemo še druge možnosti rešitve (algoritem sestopanja)

problem je ciklanje, ker pri zaciklanem grafu lahko dobimo neskončno vejo drevesa

• z iterativnem poglabljanjem

izkorišča prednosti obeh prejšnjih preiskovalnih algoritmov

uporablja iskanje v globino s tem da omeji globino in iterativno povečuje

začnemo z globino 1 in pregledamo graf do globine 1, če ne uspe povečamo globino in zopet pregledamo graf

cena tega algoritma je čas ker moramo ob vsaki naslednji globini pregledati zopet isti prostor kot prej + 1 globino več

• omejeno izčrpno - razveji in omeji

najprej prostor razmejimo, potem pa omejimo

• najprej najboljši

uporabljamo princip omejenega izčrpnega iskanja s tem, da se vedno odločimo za tistega, ki je najbolj obetaven

princip uporabljamo zato da najdemo čimprej čimboljše rešitve, da čimbolje lahko režemo prostor

pri tem principu potrebujemo veliko prostora

ena najbolj obetavnih strategij

• dinamično programiranje

gradimo od spodaj navzgor

če ima problem ustrezne lastnosti lahko garantiramo optimalno rešitev

• zagotavljajo sub-optimalne (približne) rešitve

• požrešni algoritmi (greedy)

so algoritmi, ki se odločijo vedno samo za 1 naslednjika - vse ostalo vržemo stran

"požrešno golta" celoten prostor - v enem samem koraku vržemo stran velike dele verjetnostnega prostora

• iskanje po snopu (bean)

imamo k rešitev (več možnih kandidatov) - povečamo širino pogleda

• zvezni prostori

gradientno iskanje (hill climbing)

• lokalna optimizacija

izredno učinkovit algoritem

imam prostor in izberem naključno rešitev, potem uporabljamo požrešni algoritem in optimiziram požrešno dokler še lahko izboljšamo rezultat

optimalna rešitev je taka kjer v 1 koraku od nje ne dobimo boljše rešitve

• stohastični algoritmi