UL/FRI/UNI-RI/APS2/Povzetek osnovnih pojmov

Povzetek osnovnih pojmov je povzet po knjigi Boštjan Vilfan: Osnovni algoritmi, ki je avtorsko delo, ki mi ga ne jemljemo. Samo pojme smo prepisali in jih razožili.

Aja, pa te stvari ima v rad prof. Vilfan na izpitu.

Algoritmi

Razlika med programom in algoritmom

• Od algorima zahtevamo, da pri vhodnih podatkih vrne (izhod) rezultat, ki mora biti natančno določen.

Pojem RAM stroja

• Tu mislimo računalnike(stroje), ki imajo za pomnilnik RAM

Sled algoritma

• Sled algoritma je zapis vrstic, ki jih obhodi algoritem, ker opis spremenjljivk t tek vrsticah algoritma

Drevo sledi

• Narišem drevesno shemo, obiska vrstic algoritma, pri različnih vhosnih podatkih

Osnovne metoda za preverjanje pravilnosti algoritmov

• Pravilnost lahko preverjamo s poskusi, ta metoda ni ravno najboljša, ker se pri dolžih algoritmih zaplete
• Druga možnost je da preverimo algoritem z dokazovanjem pravilnosti, to počnemo s predikatnim računom prvega reda:
  • možnost dokazovanja pravilnosti z diagramom poteka algoritma
  • možnost preverjanja s pravili, ki so določena za preverjanje programov, ki so že zapisani v programskem jeziku

Preverjanje pravilnosti s poskusi

Ideja: pri nekaterih izbranih vhodih sestavi sled programa in preveri, če program deluje pravilno. Če vrednost ene izmed spremenljivk v sledi ni pravilna, potem je algoritem nepravilen. V kolikor so vse sledi v redu, je algoritem pravilen.

Preverjanje s preiskušanjem je nerodno, ker moramo preveriti vse sledi. V praksi ni zelo uporabno.

Preverjanje z logično analizo

Ta del članka je potrebno dopolniti oz. popraviti. Urednik strani te snovi ni razumel oz. je ne zna pravilno. Iščejo se prostovoljci, ki bodo to popravili.

Diagram poteka

Diagram poteka je usmerjen graf z enim vhodom in z enim oz več izhodi.

Za risanje grafa uporabljamo vozlišča treh vrst:

• stekališče za prirejanje (x:=f(...))
• pogojni stavek (IF x > 0 THEN)
• stekališče (združitev)

Dokazovanje pravilnosti

Pravilnost algoritma dokažemo na naslednji načim:

• izhajamo iz znanih lastnostih vhoda ter izhoda
• vsakemu vozlišču S pripišemo množico trditev in sicer:
  • po eno trditev vsaki vhodni povezavi v S
  • po eno trditev vsaki izhodni povezavi iz S

Primer:

A... antecedens
C... konsekvens
S... vozlišče

A --> S --> C

Če pred izvedbo S na vhodu velja A, potem bo na izhodu po izvedbi S veljal C.

Antecedens, konsekvens

Antecedens je vhod v neko spremembo v algoritmu, konsekvens pa je izhod spremembe.

AKSIOMI

• stekališče:

v stekališču poti mora imeti vsak antecedens za posledico konsekvens - torej če pred stekališčem velja neka trditev mora veljati tudi po stekališču

• pogojni stavek:

če je antecedens pogojnega stavka trditev P, potem je konsekvens izpolnjenega pogoja B enak P Λ B, konsekvens neizpolnjenega pogoja pa je P Λ !B

• prirejanje:

če je konsekvens prirejanja trditev P, ter za x = f(...) vsebuje prosto spremenljivko x, potem antecedens pridobimo iz konsekvensa tako, da zamenjamo vse proste primnerke spremenljivke x z desno stranjo prirejanja

Preverjanje pravilnosti zank

Ta del članka je potrebno dopolniti oz. popraviti. Urednik strani te snovi ni razumel oz. je ne zna pravilno. Iščejo se prostovoljci, ki bodo to popravili.

Zančna invarianta

Ideja je, da najdemo neko invatianto (množico matematičnih trditev), ki se mora skozi izvajanje zanke ohraniti in nas na koncu pripeljati do željenega stanja. To je osnovna stvar pri dokazu pravilnosti zanke. Je neka trditev, postavljena na začetek zanke, ki velja vedno, ne glede na to kolikokrat izvedemo jedro zanke. Bistvena je pri dokazovanju pravilnosti programa.

Urejanje