Program

Iz izkušenj že vemo, da je program postopek za reševanje problema, zapisan v nekem programskem jeziku. Tako kot problem ima tudi program svoj vhod in izhod: vhod sestavljajo vsi podatki, ki jih program pridobi iz zunanjega sveta (npr. z uporabnikovim vnosom), izhod pa tvorijo podatki, ki jih program zunanjemu svetu sporoči kot svoj rezultat (npr. tako, da jih izpiše na zaslon).

Kdaj lahko rečemo, da program rešuje določen problem? Takrat, ko se program za vsak veljaven vhod problema ustavi in ustvari pričakovani izhod. Pogoj, da se mora program prej ali slej ustaviti (končati svoje izvajanje), se morda zdi samoumeven, vendar bomo pozneje videli, da ni čisto tako. Napišimo program za problem MIN3. Možnosti je kar precej, ena od njih pa je ta:

Izvedi Počisti



					

Naš program prejme vhod tako, da ga uporabnik vnese s pomočjo tipkovnice, dobljeni izhod pa izpiše na zaslon. Seveda pa to ni edina možnost: lahko bi denimo brali iz datoteke in vanjo tudi pisali.

Ali naš program dejansko rešuje obravnavani problem? Ali se za vsako trojico celih števil ustavi in izpiše pravilen (torej pričakovani) rezultat? Ustavljivost ni vprašljiva: ker program vsebuje samo branje, izpis in pogojne stavke, se bo tako ali drugače vedno ustavil. Kako pa bi preverili pravilnost? Lahko bi na primer tvorili tisoč različnih trojic celih števil in za vsako preverili izhod. Vendar pa to ne bi zadoščalo, saj bi morali pravilnost preveriti za vsako možno trojico, teh pa je seveda neskončno. Kako lahko kljub temu pokažemo pravilnost programa, bomo videli nekoliko pozneje.

Vaja

Vaja