Tietokoneen käytön ja ohjelmoinnin alkeet

Kurssin kotisivulle

Algoritmi

Tietokone sellaisenaan ei tee mitään. Se pystyy kuitenkin suorittamaan erilaisia ohjelmia.

Algoritmi on yksityiskohtainen toimintaohje.

Luonnollinen kieli on usein epämääräistä. Algoritmi on kuvattava jollakin formaalilla kielellä, jonka rakenteilla on yksityiskohtainen tulkinta. Ohjelmointikielet ovat tällaisia.

Tehtävän ratkaisu esitetään aluksi mahdollisimman täsmällisenä algoritmina, joka sitten kirjoitetaan ohjelmointikielellä.

Tietokoneella oleva kääntäjä (sekin on ohjelma) muuttaa ohjelman koneen ymmärtämälle konekielelle.

Konekielinen ohjelma voidaan suorittaa.

Esimerkki 1: Etsitään lukujoukon suurin luku.

Riittävä ohje ihmiselle, mutta ei kerro lainkaan, miten tehtävä suoritetaan:

Matemaattinen esitys:

x = max { a1, a2, ... , an }

Tämäkään ei kerro, miten suurin luku etsitään.

Algoritminen esitys: 

  x = a1,
  jos a2 > x, x = a2,
  jos a3 > x, x = a3,
  ...
  jos an > x, x = an.

Tämän voisi jo ohjelmoida tietokoneelle, jos n tunnetaan.

Entäpä jos n voi eri suorituskerroilla saada eri arvoja?

Parempi algoritmi: 

  n = 100
  x = a1
  i = 2, 3, ... n:
     jos ai > x, x = ai

Esimerkissä esiintyy kolme algoritmien perusrakennetta:

1 Peräkkäisyys:
Ensin asetetaan alkioiden lukumääräksi 100, sitten muuttujan $x$ arvoksi lukujoukon ensimmäinen alkio ja lopuksi suoritetaan varsinainen suurimman alkion etsintä.

2 Valinta:
Jos lukujoukon alkio on suurempi kuin tähän mennessä löydetty suurin luku, suurimman arvoksi vaihdetaan uusi luku.

3 Toisto:
Suoritetaan sama vertailu lukujoukon kaikille alkioille.

Tämä voitaisiin kirjoittaa suoraan C-kieliseksi ohjelmaksi: 

  n = 100 ;
  x = a[1] ;
  for (i=2; i <= n, i++)
    if (a[i] > x) x = a[i] ;

Tämä ei ole vielä täydellinen ohjelma (luvut ai eli ohjelmassa taulukon a alkiot on saatava jostakin ja lopputulos tulostettava tai sitä on käytettävä jotenkin muuten). Se sisältää kuitenkin algoritmin vastineen toteutettuna ohjelmointikielellä.

Esimerkki 2: Eratostheneen seula

Tämä on hyvin yksinkertainen antiikin aikainen menetelmä alkulukujen etsimiseksi.

  1. Kirjoitetaan luonnolliset luvut 2, 3, 4, ... , n.
  2. Poistetaan luvun 2 monikerrat (4, 6, 8 jne.).
  3. Listan seuraava jäljellä oleva luku on alkuluku.
  4. Poistetaan luvut, jotka ovat edellisessä vaiheessa löydetyn alkuluvun monikertoja.
  5. Jos seuraava jäljellä oleva luku < sqrt(n), palataan kohtaan 3.
  6. Jäljellä on vain alkulukuja.

Ohje on jo hyvin täsmällinen, mutta esimerkiksi askel 2 sisältää toiston, joten algoritmi vaatii vielä pientä tarkennusta ennen lopullista ohjelmointia.