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

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

Principi reševanja problemov

Osnovni principi so:

• razumevanje
  • zahteve
  • nedvoumna definicija problema
  • dejstva, pravila, cilji pri reševanju tega problema
  • implicitni podatki -> eksplicitno zapišemo
  • odvečni podatki (nas ovirajo pri reševanju problema)
• abstrakcija
  • objekti (jih poimenujemo)
  • relacije med objekti
  • definiramo operacije na voljo v teh objektih
  • Z zgornjimi tremi alinejami smo definirali problemski prostor
  • včasih je koristno tudi, da si narišemo graf (lahko spremenimo v drevo, s tem pridobimo na koristnosti prikaza)

Primer problema: Teta je Jožefina in sedaj trikrat toliko stara kot je bil star nečak Rožle pred 10-imi leti. Rožle je sedaj pol toliko star kot (Ni dokončano)

Odvečni podatki so teta, imena Jožefina in Rožle, itn.

Objekti sta starost Jožefine (J) in starost Rožleta (R).

Relacija je dejstvo, da je Jožefina trikrat starejša kot je bil Rožle pred 10-imi leti.

J = 3 \cdot (R-10)

R = \frac{1}{2} \cdot

• notacija

  • je ključna!

  • definicija: Notacija je simbolična predstavitev, ki modelira skupne značilnosti razreda objektov ali situacije in možne operacije na simbolu.
  • simbolična
  • razredi objektov
  • operacije
  • ločimo:
    • slikovno notacijo(primer: prometni znak)
      • okrajšave
      • koncepti

1. objekti, veličine: imena (v našem primeru J in R) 2. operacije, relacije: +,-,=,<,>

• • • besedno notacijo

Ko si izberemo notacijo, je slej kot prej potreben formalni sistem:

• • • • programski jezik)
      • algebra
      • teorija množic
      • izjavni račun
      • predikatni ? račun

Iz realnega sistema moramo prenesti zapis v formalni sistem.

Reševanje poteka na sintaktičnem nivoju

Dobimo neko rešitev in je potrebno najti povezavo nazaj v realni sistem

Tone vrže žogo z 8m/s navzgor. Strop je visok 3m. Kako dolgo bo žoga letela navzgor?

s=v_0+\frac{1}{2}gt^2

t_1 = 1s

t_2 = \frac{3}{5}s

Naša enačba predpostavlja, da ni stropa, zato uporabimo manjšo vrednost, saj strop dejansko je.

• razbitje problema na podprobleme
  • od zgoraj navzdol
  • od spodaj navzgor

dinamično programiranje

faktoriela (zadnjič smo jo reševali od zgoraj navzdol), lahko rešimo z uporabo iteracije in dinamičnega programiranja

• podobnost med problemi

pri iskanju rešitve našega problema (razvoju algoritma, razumevanja problema). Transformiramo probleme v druge

• • poenostavitev problema
  • posplošitev: konstanto spremenimo v spremenljivko
  • reformuliramo
  • izomorfizem: preslikava je enolična

Primer problema: narisati pismo z eno potezo brez da bi dvigal pisalo od papirja

domine

3 v vrsto(križci in krožci) se poenostavi, če igramo igro z 9-imi kartami, v kateri zmaga tisti, ki ima 3 karte z vsoto 15 (karte so od 1 do 9 in jih lahko porazdelimo kot pri igri križci in krožci)

• • matematična indukcija

1. robni primer n=1,0 2. predpostavimo: n-1 in potem izpeljemo, da dobimo n algoritem(izrek) za poljubni n

Domača naloga

5 profesorjev, ki spijo (vsi v isti sobi)

V sobi pride zlobni študent in jim pobarva obraze z zeleno barvo

Profesorji se zbudijo, se pogledajo in se začnejo smejati.

Najpametnejši med njimi ugotovi, da je tudi sam pobarvan in se neha smejati.

Kako je ugotovil, da je tudi sam pobarvan?

Nima ogledala, nima očal, noben ne pove drugemu, da je pobarvan.

• strategija preiskovanja

Reševanje problemov z algoritmi

Kaj -> Kako

Definicija: Algoritem je končno zaporedje natančno določenih ukazov, ki opravijo neko nalogo v končnem številu korakov

Algoritem ima vhodne podatke, ki vrnejo rezultat

Algoritmi so končni. Preslikava vhoda v izhod (funkcija).

Program je algoritem zapisan v programskemu jeziku

Razvoj algoritma:

• kako izraziti algoritem (kakšno notacijo)
  • diagrami poteka (vizualno predstavljajo algoritem)
  • pseudo koda (strukturiran naravni jezik, kjer poskušamo razdeliti problem, tako da imamo dobro osnovo za napisati algoritem)
    • naravni jezik
    • kontrolne konstrukte in ukaze iz prog.jezika
    • izrazi iz formulnih sistemov
    • skice, diagrami poteka, ...

Naravni jezik, se sprva prevede v grobi opis (pseudo koda). Kasneje dobimo fini opis (pseudokoda) in za tem dobimo programski jezik.

• • programski jezik
• kako zasnovati algoritem
  • uporabimo principe reševanja algoritmov
• kako analizirati algoritem (ugotoviti kako se bo ta algoritem obnašal)
  • algoritem analiziramo preden ga napišemo, saj če vanj vložimo veliko truda, bo ta trud zaman, če algoritem analiziramo po temu ko ga napišemo. Analizo moramo narediti bolj zgodaj
  • analiza časa
    • asimptotična velikost podatkov
    • dejanski čas
  • analiza prostora
• kako preveriti algoritem
  • branje in razumevanje algoritma (problematično, če smo zapisali napačno, ga bomo tudi prebrali napačno)
    • pisanje čitljivih algoritmov
    • izbira ustreznih imen (mnemonična imena, ki že sama povejo, za kaj se uporabljajo)
    • komentarji (niso potrebni, če je že koda lepo napisana)
  • testiranje (pomembno je biti "zloben", potrebno dati programu najhujše podatke), ekstremni primer, veliko različnih vrednosti, ničla, ...

dokaz nepravilnosti: s testiranjem tega ne dosežemo. Potrebujemo sklop podatkov, na katerih algoritem ne deluje pravilno

• • dokaz pravilnosti:
    • daljši od programa. Če ste se zmotili pri programu, ste se zmotili tudi pri dokazu
    • formalno zahtevna
    • se ga ne da popolnoma avtomatizirati
    • pogoji?

Pregled strategij preiskovanja

• strategije, ki iščejo optimalne rešitve
  • izčrpno iskanje
    • iskanje na širino (preiskovanje po nivojih) prostor! zapomniti si moramo celotni prejšnji nivo
    • iskanje na globino ciklanje! (neskončna veja)
    • iterativno poglabljanje čas!
  • omejeno izčrpno (razveji in omeji - branch and bound) pove, da so nekatere veje neobetavne včasih s tem tudi zavržemo optimalno rešitev in se moramo zadovoljiti z približno rešitvijo
  • !(obetavna strategija)najprej najboljši (prostor!)
  • dinamično programiranje (od spodaj navzgor)
• strategije, ki iščejo približne rešitve
  • požrešni(greedy) (odločimo se samo za eno vejo, ostale zavržemo)
  • v snopu (beam search) - glede na k, izberemo k poti ostalo zavržemo; k=1 je v bistvu enak požrešnemu algoritmu
  • zvezni: gradientno (hill climbing)
  • !(obetavna strategija)lokalna optimizacija (v prostoru naključno izberem začetek in z uporabo požrešnega algoritma pridemo do rešitve, to večkrat ponovimo toliko časa, kolikor ga imamo na voljo
• stohastični algoritmi