Algoritmid (0)

1.       Algoritm . Algoritmi  omadused. Keerukus . Ajalise keerukuse asümptoodiline hinnang. Erinevad keerukusklassid. 
Algoritm on mingi meetod probleemi lahendamiseks, mida saab realiseerida arvutiprogrammi abil. Algoritm peab olema 
määratud  nii  täpselt,  et  seda  suudaks  täita  isegi  arvuti.  Täidetavaid   samme   ei  tohi  olla  liiga  palju.  Algoritm  peab 
lahendama ülesande õigesti erinevate sisendandmete korral. 
Algoritmi 5 olulist omadust: 
1.    Lõplikkus. Algoritmi töö peab lõppema peale lõpliku arvu sammude läbimist. 
2.     Määratletus . Algoritmi iga samm peab olema rangelt  ja ühemõtteliselt  määratud iga juhu  jaoks. 
3.     Sisend . Algoritmil on sisendandmed, mille hulk võib olla null. 
4.    Väljund. Algoritmil on vastus(ed), millel on täpselt määratud seos sisendandmetega. 
5.    Efektiivsus  (tulemuslikkus).  Algoritm  peab  olema  nii  lihtne,  et  on  lõpliku  ajavahemiku  jooksul   pliiatsi   ja 
paberi abil täidetav. 
Algoritmi  keerukus  on  hinnang  sellele,  kuidas  algoritmi  poolt  esitatavad  nõudmised  ajale  muutuvad  näiteks  siis,  kui 
probleemi  mõõt  kasvab.  Keerukus  mõjutab  jõudlust,  kuid  mitte  vastupidi.  Ajaline  keerukus  –  hinnatakse  programmi 
tööaega.  Mahuline keerukus – hinnatakse programmi tööks kasutatava mälu mahtu. 
Ajalise keerukuse asümptoodiline hinnang (asümptoodiline hinnang efektiivsusele). Funktsiooni kasvukiiruse hinnang, 
kui  palju  kasvab  algoritmi   tööaeg   andmemahu  suurenemisel.  Reeglina  antakse  hinnang  halvima  juhu  jaoks  ja  tegelik 
tööaeg peaks olema parem.  Hinnangud  hakkavad kehtima alles andmehulga (N-i) suurte väärtuste korral. Algoritmi tööaja 
hindamiseks peab pöörama tähelepanu struktuurile. 
Keerukusklassid: 
1.    O(1) –  konstantne  keerukus (andmehulgast ei sõltu tööaeg, programmi  lauseid  täidetakse üks kord, tavaliselt 
lahendamiseks valem). 
2.    O(log n) – logaritmiline keerukus (tööaeg kasvab väga aeglaselt andmete kasvuga, lahendamine järkjärgulisel 
vähendamisel, tavaliselt logaritmi aluseks 2, kahendotsimine – otsitav piirkond aheneb igal  sammul  2x). 
3.    O(N) – lineaarne keerukus (elementide töötlemine, andmehulga kasvades 2x kasvab ka tööaeg 2x, lineaarne 
otsimine). 
4.    O(n*log n) – linearitmiline keerukus (kui õnnestub saavutada O(N2) asemel, siis on hästi. Kiirsorteerimine & 
mestimine, kiirem kui ruutkeerukus). 
5.    O(N2)  –  ruutkeerukus  (andmehulga  kasvamisel  10x  suureneb  tööaeg  102  x,  enamasti  2  tsüklit  üksteise  sees, 
sõltuvad algandmete hulgast, sobilik väikeste probleemide lahendamisex). 
6.    O(N3)  –  kuupkeerukus  (3  tsüklit  üksteise  sees,  sõltuvad  algandmete  hulgast,  sobilik  väikeste  andmehulkade 
korral, maatriksite korrutamine). 
7.    O(2n) –  eksponentsiaalne  keerukus (N=10, aeg on 1000; N=200, aeg on 1 000 000, ebapraktiline, sellised on 
tihti jõumeetodil lahendused) 
2.        Algoritmimise strateegiate lühike iseloomustus ja kasutamise näide ( Brute - force  algoritmid,  ahned  algoritmid, 
dünaamiline programmeerimine ). 
Algoritmimise  strateegiad  on  üldised  põhimõtted  sellest,  kuidas   konstrueerida   tulemuslikke  algoritme 
probleemide lahendamisex. 
Erinevad  strateegiad:  Jõumeetod  (Brute-force),  jaga  &  valitse  ( Divide   &  Conquer),  dünaamiline 
programmeerimine ( Dynamic Programming), ahne algoritm (Greedy Method), tagurdusmeetod (Backtracking). 
Brute-force  –  väga  ebaefektiivne,  vaadatakse  läbi  kõik  teed  &  võimalused,  palju  samme,  kergesti  arusaadav  & 
väljamõeldav,  sõltub  lähteandmete  iseloomust,  hulgast  &  sellest,  mida  otsitakse.  Keerukusklass  võib  kerkida 
O(N!)-ni.  Eelisteks  probleemist  paremini  arusaamine,  mõtlemise  strateegia,  väikese  andmehulga  korral  saab 
paberil   läbi  mängida.  Jõumeetodil  töötavad  algoritmid  on  lihtsad,  arusaadavad,  kergemini  realiseeritavad  ja 
veakindlamad. 
Dünaamiline  programmeerimine  –  kasutatakse  siis,  kui  otsitav  vastus  koosneb  osadest,  mis  omakorda  on 
lahendusteks  alamprobleemile.  Sobilik  siis,  kui  ette  tuleb  sama  alamülesande  lahendamine,  leitud  lahendused 
peetakse meeles, juhuks kui uuesti vaja läheb. Võimalikke lahendusi palju, saab valida  parima . Kasutatakse: kui 
probleemi saab jagada järkudeks ning igas  järgus  nõutakse otsuse tegemist; igas järgus on mitu olekut (näiteks 
punkt, kuhu selleks hetkeks jõutud); iga otsus viib järgmisesse olekusse; otsus määrab edasise tee; antud olekus 
tehtud otsus ei sõltu eelmistest otsustest; viimane järk peab lahenduma iseenesest. Kõige raskem on õigete järkude 
&   seisundite   üles  leidmine.  Halvimal  juhul  ruutkeerukus,  parimal  juhul  keerukus.  DP  on  alt  üles  tehnika,  kus 
kõige väiksemad alamprobleemid lahendatakse  kõigepealt  ning liigutakse samm-sammul ülespoole. 
Ahne  algoritm  –  sobilik  optimeerimisülesanneteks,  kergem  koostada  &  kiirem  kui  DP  algoritm,  ei  anna  alati 
tulemuseks optimaalset vastust, vastuse optimaalsust raske tõestada. Sobib kui kõige optimaalsemat vastust polegi 
vaja & kindlasti siis, kui alamülesannete optimaalsed lahendused annavad tulemuseks kogu probleemi optimaalse 
lahenduse. 
 
Kudos who wrote it!(+1)+1 
3.      Andmestruktuur. Loogiline tase. Realisatsiooni tase. 
Andmestruktuur näitab, kuidas paiknevad programmi töö ajal mälus  hoitavad  andmed. Lihtsaim viis –  massiiv  ehk tabel 
(füüsiline struktuur). Loogiline struktuur on andmete jada, elemendid on järjestatud. Keerulisemad  struktuurid  on kahe- ja 
mitmemõõtmelised massiivid, kirjed  jne. 
Loogiline  tase  –  kirjeldab  struktuuri  loogilist  ülesehitust.   Esitamiseks   sobivad   kastid   &  nooled.  Operatsiooni 
selgitamiseks pseudokood. 
Realisatsiooni tase  – näitab,  kuidas  vastav  struktuur tegelikult  arvutis  realiseeritakse ja  kuidas  toimuvad   operatsioonid . 
Realiseerida saab tavaliselt mitmel erineval moel ning otstarbeka variandi valimine sõltub keelest ja olukorrast. 
4.            Ühe  ja  kahe  viidaga  lineaarnimistud.  Peamised  tegevused:  elemendi  lisamine,  elemendi  kustutamine,  nimistu 
läbimine. 
Ühe viidaga  loend  koosneb  peast  & selle külge aheldatud & omavahel soetud elementidest. Viimase elemendi viidaväljas 
tühi  viit  NIL. Tühja loendi puhul on pea väärtus NIL. Loendi läbimine – alusta algusest, lõpeta lõpus. 
Kahe viidaga loend koosneb peast, selle külge aheldatud & omavahel seotud elementidest & sabast, elemendid on seotud 
kahe viidaga. Igas sõlmes on 2 aadressivälja (järgmise sõlme aadress Next [ Node ] ja eelmise sõlme aadress Prior [Node]). 
Eelised – saab teha kiiremini operatsioone loendi mõlema otsaga, teinekord mugavam keskmiste elementide töötlemiseks. 
Puudused – võtab rohkem mälu, keerukam  hallata, sest alati vaja ühendada & lahti võtta 2 viita . 
5.       Pinu . Omadused. Operatsioonid. Näited kasutamisest. Realiseerimine arvutis. 
Pinu on lineaarloend, kuhu elemente lisatakse ning kustutatakse  samast  otsast – pinu tipust. Andmete kättesaamine toimub 
elemendi eemaldamisel pinust. 
Pinu  omadused  –  keskele  elemendi  lisamine,  kustutamine  &  vaatamine  on  keelatud;  elemente  saab  lisada,   kustutada   & 
vaadata ainult pinu tipust; ei ole ette nähtud pinu läbimist. 
Operatsioonid  –  elemendi  lisamine;  elemendi  eemaldamine;  uue  pinu  loomine;  kontroll,  kas  pinu  on  tühi;  kontroll,  kas 
pinu on täis. 
Kasutamisnäited – Pinu kasutamine sõna KUI tagurpidipööramiseks, aga pigem kalkulaatorite mälu salvestamiseks.  
Realiseerimine  arvutis  –  kasutatakse  erinevates rakendustes,  näiteks  pannakse  poolelijäänud  alamprogramm(ap)  pinusse 
koos  muutujate  komplektiga,  kõik  poolelijäänud  ap-d  pannakse  üksteise  otsa  ning  kui  ühe  ap-i  täitmine  lõpeb,  siis 
võetakse tema asemel pinust  eelmine ap. Vajadusel võib lisada pinusse uusi ap-e. 
6.      Poola kuju ja pööratud Poola kuju. 
Poola kuju – loogikaavaldiste kirjapanek sulgusid kasutamata. Idee seisneb selles, et kui panna tehtemärgid väärtuste ette 
või  järele  ja  kui  tehtemärgi  poolt  töödeldavate  väärtuste  hulk  on  üheselt  määratud,  siis  saab  hakkama  ilma  sulgudeta. 
Tehtemärgid väärtuste ees on Poola kuju. Prefiks (+ab). 
Pööratud poola kuju – ilma sulgudeta kirjapanek, tehtemärgid väärtuste järgi. Postfiks (ab+). Tavaliselt infiks (a+b). 
Näide – infiks notatsioon on (a*b)+c, sama avaldis postfiks notatsioonis oleks ab*c+ 
 
Pööratud Poola kuju näide 
N:(5*3)+(1+(3-2)) Normaalkujult -> Postfixkujule 
Reeglid 1.Arv kirjuta väljundisse 
 
2.Vasakut sulgu ignoreeri 
 
3. Operaator (tehtemärk) pinusse 
 
4.Parempoolse sulu puhul võta operaator pinust ja pane väljundisse. 
1. 5*3)+(1+(3-2)) vasak  sulg  nahui 
2. *3)+(1+(3-2)) nr väljundisse V:5 P:tühi 
3. 3)+(1+(3-2)) operaator pinusse V5 P:* 
4. )+(1+(3-2)) nr väljundisse V:5 3 P:* 
5. +(1+(3-2)) parem sulg võtab pinust operaatori ja paneb väljundisse V:5 3* P:tühi 
6. (1+(3-2)) operaator pinusse  V:5 3* P:+ 
7. 1+(3-2))  fuck  vasak sulg- nobody  likes  him 
8. +(3-2)) nr väljundisse  V:5 3*1 P:+ 
9. (3-2)) operaator pinusse V:5 3*1 P:++ 
10. 3-2)) vasak sulg ei eruta meid 
11. -2)) nr väljundisse V:5 3*1 3 P:++ 
12. 2)) operaator pinusse V:5 3*1 3 P:-++ ( - on esimene kuna ta on kõige pealmine ) 
13. )) nr väljundisse V:5 3*1 3 2 P:-++ ( - on esimene kuna ta on kõige pealmine) 
14. ) operaator pinust välja ja väljundisse V:5 3*1 3 2 - P:++ 
15. operaator pinust välja ja väljundisse V:5 3*1 3 2 -+ P:+ 
16. Pinu tühjaks õiges järjekorras. operaator pinust välja ja väljundisse V:5 3*1 3 2 -++ P:Tühi 
 
N: 53*132-++ Postfix kujult ->  Normaalkujule   
1. Pistad kõik pinusse alustades paremalt, ehk pinu kõige alla jääb + ja kõige peale 5. 
2. Võtad  numbrid välja kuni operandini e. väljas on 5 3 ja pinus  on  *132-++ 
3. Operant  Läheb nüüd kahe arvu vahele e. väljas on 5*3 ja piinus on 132-++ 
4. Numbrid välja 5*3 1 3 2 pinus on -++ 
5.Operant paika (5*3) 1 (3-2) pinus on ++ 
6.Operant paika (5*3) 1+(3-2) pinus on + 
7.Operant paika (5*3)+(1+(3-2)) pinu on tühi 
 
7.       Järjekord . Omadused. Operatsioonid. Näited kasutamisest. Realiseerimine arvutis. 
Järjekord ehk saba – lineaarloend, kus elemente lisatakse ühes otsas ning eemaldatakse teises. Reeglina pääseb andmetele 
ligi vaid seal otsas, kus toimub eemaldamine. 
-Operatsioonid  –  elemendi  lisamine  jk  lõppu;  elemendi  eemaldamine  jk  algusest;  tühja  jk  loomine;  kontroll,  kas  jk  on 
tühi; kontroll, kas jk on täis. 
Kasutatakse siis, kui andmed saabuvad kindlas jk-s ning töötlemise jk on oluline. Näiteks lennukile  piletite  broneerimise 
süsteem. Kes tahtis varem kohta, see saab ka selle. 
Erilised jk-d – mitme teenindajaga , prioriteetidega, piiratud pikkusega. 
Realiseerimine arvutis – sõltub progemiskeelest. 2 võimalust – massiiv (kaks indeksit – algus & lõpp;  algusesse  lisatakse, 
lõpust  eemaldatakse;  kui  lõpp