Mikä on WikiWiki?
nettipäiväkirja
koko wiki (etsi)
viime muutokset
Algoritmi on hyvin vaikea käsite selittää. Itse asiassa se on helpompi ymmärtää, jos osaa ohjelmointia: kun algoritmin käsitteelle etsittiin muodollista selitystä, Alan Turing määritteli eräänlaisen kuvitteellisen koneen (nykyaikaisen tietokoneen esiaste) ja sanoi: algoritmi on toiminta, joka voidaan toteuttaa tällä koneella.
Okei, tuosta määritelmästä ei ole paljon hyötyä, jos ei tunne Turingin koneen toimintaa... algoritmin jonkinlainen intuitiivinen määritelmä on "yksiselitteinen, tarkasti määritettyyn suuntaan etenevä kuvaus siitä, miten jotain tehdään".
Esimerkiksi tämä ei ole algoritmi:
"Löytääksesi jonkun ihmisen puhelinnumeron, katso oikeasta kohdasta puhelinluetteloa, mikä hänen numeronsa on."
Se ei ole algoritmi, koska "oikea kohta" ei ole hyvin määritelty: ei voi oikeasti tietää, mitä algoritmin kirjoittaja tarkkaan ottaen käskee.
Entä tämä:
"Löytääksesi jonkun ihmisen puhelinnumeron, käy läpi kaikki nimet puhelinluettelosta: jos jokin nimi on etsimäsi, sen kohdalla oleva numero on haluamasi."
Tämäkään ei ole algoritmi, sillä se ei määritä järjestystä ja tapaa, jolla kaikki nimet käydään läpi. Sen sijaan seuraavaa voisi jo ehkä pitää algoritmina:
"Löytääksesi jonkun ihmisen puhelinnumeron, katso puhelinluettelon ensimmäisestä nimestä, onko se etsimäsi. Jos on, sen kohdalla oleva puhelinnumero on haluamasi, ja voit lopettaa. Jos ei, etene seuraavaan nimeen ja toista." (Tämä on muuten hirvittävän typerä algoritmi.)
Luonnollisissa kielissä raja algoritmin ja ei-algoritmin välillä ei ole oikein selvä, sillä joskus on vaikea sanoa, kuinka paljon tulkitsija voi olettaa. Jos esimerkiksi sanoisin "käy nimet järjestyksessä alusta loppuun läpi", fiksu ihminen ymmärtäisi kyllä, mitä tarkoitan, ja kyseessä olisi algoritmi. Toisaalta yllä olevassakin on annettu periaatteessa epämääräinen käsky "toista"; tietokoneelle pitää kertoa tarkasti sekin, mistä alkaen toistetaan. Ylläoleva algoritmi olisi Python-kielellä jotain tällaista:
def etsi_nimi(puh_luett, nimi):
nyk_kohta = puh_luett.alku()
while puh_luett[nyk_kohta].nimi != nimi:
nyk_kohta = puh_luett.seur_kohta(nyk_kohta)
return puh_luett[nyk_kohta].numero
Ohjeita algoritmien (ja funktioiden) suunnitteluun: http://sange.fi/~atehwa/scheme-kurssi/algoritmisuunnittelu.html
On vielä yksi syy, miksi tarkasti määritelty toiminnan kuvaus (siis ohjelma) ei välttämättä ole algoritmi: jos se ei tuota tulosta äärellisessä ajassa. Esimerkiksi tämä ei ole algoritmi:
"Löytääksesi jonkun ihmisen puhelinnumeron, katso puhelinluettelon ensimmäisestä nimestä, onko se etsimäsi. Jos on, sen kohdalla oleva puhelinnumero on haluamasi, ja voit lopettaa. Jos ei, aloita alusta (siis katso ensimmäinen nimi uudestaan)."
Ohjelmat, jotka eivät tuota tulosta äärellisessä ajassa, ovat epäalgoritmisia riippumatta siitä, tekevätkö ne jotain "fiksua" vai "älytöntä" ikuisesti. Jos ohjelma tuottaa tuloksia tietyillä syötteillä mutta toisilla ei, sitä voi sanoa osittaisalgoritmiksi.
(takaisin ohjelmoinnin käsitteet-sivulle)