Algoritmi

Algoritmi on yksityiskohtainen kuvaus tai ohje siitä, miten tehtävä tai prosessi suoritetaan; jota seuraamalla voidaan ratkaista tietty ongelma.[1] J.G. Brookshearin määritelmän mukaan algoritmi koostuu järjestyksessä olevista, yksiselitteisistä toiminnoista jotka voidaan suorittaa ja jotka määrittelevät lopputulokseen johtavan prosessin.[2]

Vuokaavioita käytetään usein graafisten algoritmien suunnitteluun ja tekemiseen.

Algoritmin käsite ja historia

Laajalti tunnettu esimerkki algoritmista on Hanoin tornin ratkaiseminen.
Ada Lovelacen tekemä diagrammi Bernoullin lukujen laskemiseen.
Algoritmi elektroniikassa: NAND-portti npn-transistoreilla.
Vuokaavioesimerkkejä algoritmista.

Algoritmien tutkimus alkoi matematiikan aiheena ja algoritmit ovat tietojenkäsittelytieteessä keskeinen käsite. Epämuodollisesti algoritmi on joukko askeleita, joka määrittää miten tehtävä suoritetaan. Esimerkiksi on olemassa algoritmeja ruuanlaittoon (reseptejä), ohjeet paikan löytämiseen kaupungissa (suuntaohjeet), pesukoneen käyttöön (käyttöohjeet), musiikin soittamiseen (nuottikirjoitus) ja taikatemppujen suorittamiseen.[3]

Algoritmeja ovat jo nekin koulun alaluokilla opetetut menetelmät (allekkain kertomisesta ja jakokulmassa jakamisesta), joilla mitkä tahansa luvut voidaan kertoa tai jakaa keskenään, mutta toisinaan termillä on tarkoitettu nimenomaan Eukleideen algoritmia kahden kokonaisluvun suurimman yhteisen tekijän etsimiseksi. Nykyisin algoritmin käsite kuitenkin liittyy ennen kaikkea tietokoneiden ohjelmointiin ja tietojenkäsittelytieteeseen, joissa niillä on erityisen suuri merkitys etenkin tietorakenteiden yhteydessä.

Universaalia Turingin konetta on käytetty määrittelemään mitä on mahdollista ratkaista laskennallisesti: kun jokin ongelma ei ole ratkaistavissa universaalilla koneella se ei ole ratkaistavissa laskennallisesti lainkaan.[4] Churchin–Turingin teesi ehdottaa, että algoritmi on vastaava kuin Turingin kone.[5][6] On väitetty, että Churchin–Turingin teesi oli vain askel ymmärtämään algoritmeja, mutta että se ei ratkaissut ongelmaa mikä algoritmi on.[7]

Algoritmeissa sekä tietokoneilla että ilman tietokonetta informaation käsittelyyn liittyy abstraktio todellisesta maailmasta: tietokoneelle valittu data on ongelman ratkaisun kannalta olennainen osa, jotta voidaan saada haluttu lopputulos.[8]

Sana algoritmi tulee persialaisen matemaatikon ja tähtitieteilijän Muhammed ibn-Musa al-Khwarizmin nimestä. Al-Khwarizmi kirjoitti kirjan Kitab al jabr wa'l-muqābala, josta on peräisin sana "algebra". Sana "algoritmi" ilmestyi vuonna 1957 Webster's New World Dictionary -sanakirjassa.[9] Ada Lovelace julkaisi vuonna 1843 kuvauksen ("Note G") askeleittain tehtävästä toimintojen sarjasta matemaattisen ongelman ratkaisemiseen, jota on kutsuttu ensimmäiseksi julkaistuksi algoritmiksi tietokoneelle.[10][11]

Algoritminen periaate

Esimerkkinä algoritmista voidaan käyttää Eukleideen algoritmia suurimman yhteisen nimittäjän löytämiseen kahdelle luvulle.[9] Kahdelle positiiviselle kokonaisluvulle m ja n voidaan löytää suurin yhteinen nimittäjä seuraavasti:

  1. (etsi jakojäännös) Jaa m luvulla n ja aseta r jakojäännökseksi. (Tällöin 0 ≤ r < n).
  2. (onko jakojäännös nolla?) Jos r on yhtä kuin nolla (r = 0), algoritmi päättyy; n on vastaus.
  3. (vähennä) Aseta m arvoksi n (mn) ja n arvoksi r (nr) ja palaa ensimmäiseen askeleeseen.

Eukleides ei esittänyt algoritmiaan tässä muodossa, mutta tätä voidaan käyttää esimerkkinä algoritmien esitystavasta.[9]

Algoritmin käsitteen määrittelyyn liittyy viisi ominaisuutta:[9]

  • Äärellisyys: algoritmin on aina päätyttävä äärellisellä määrällä askeleita. Määrä voi olla suuri, mutta kuitenkin rajallinen.
  • Tarkkarajaisuus: algoritmin jokainen askel on oltava täsmällisesti määritelty. Toiminnot on kuvattava ilman monia tulkintoja jokaiselle tapaukselle.
  • Syötteet: algoritmilla on nolla tai useampia syötteitä eli alkuarvoja tai arvot päätellään dynaamisesti suorituksen aikana.
  • Tulosteet: algoritmilla on yksi tai useampi lopputuloste eli arvoja, jotka liittyvät syötteisiin.
  • Tehokkuus: algoritmin odotetaan olevan tehokas siten, että sen toiminnot ovat yksinkertaisia ja periaatteessa suoritettavissa rajallisella määrällä aikaa käyttäen kynää ja paperia.

Algoritmit riippuvat tietorakenteiden suunnittelusta ja tietyt algoritmit ja rakenteet ovat toisia tehokkaampia samaan tarkoitukseen. Kun algoritmin kuvauksen pitää olla riittävän tarkka ihmisen ymmärrettäväksi niin tietokoneohjelman pitää olla sopiva tietokoneen suoritettavaksi. Tietokone tarvitsee lisää informaatiota formaalilla kielellä, jolloin algoritmi toteutetaan jollakin ohjelmointikielellä.[12]

Algoritmien analyysi

Algoritmien analyysi koskee pääasiassa algoritmin muisti- (tila) ja aikavaatimuksia (kompleksisuus).[13] Muistivaatimuksien määrittelyyn käytettävät tekniikat ovat alijoukko aikavaatimuksen määrittelyyn käytettävistä.[13] Algoritmin aikavaatimus määritetään ratkottavan ongelmajoukon koon funktiona.[13]

Perinteisesti algoritmien analyysi koskee operaatioiden ja vaiheiden määrän laskemiseen, joka oli perusteltu tapa aikana, jolloin tietokone käytti enemmän aikaa operaation suorittamisee kuin muistihakuun.[13] Nykyään suorituksen kustannus on merkittävästi pienempi kuin tiedon muistista hakemisen kustannus ja tämän seurauksena monien algoritmien suoritusaikaa hallitsee muistiviittausten määrä sekä välimuistihutien määrä.[13] Tästä johtuen algoritmien suunnittelussa on otettava huomioon muistilatenssi.[13]

Analyysissa voi usein keskittyä heikoimpaan suoritusaikaan eli pisimpään suoritusaikaan millä tahansa syötteellä. Heikoin suoritusaika on antaa ylärajan suoritusajalle. Tietyille algoritmeille heikoin tapaus tapahtuu usein. "Keskivertotapaus" voi olla karkeasti ottaen yhtä huono kuin heikoin. Myös suoritusajan kasvutahti on merkittävä.[14]

Algoritmien suunnittelu

Algoritmi on menetelmä tietyn tehtävän suorittamiseen ja ollakseen hyödyllinen algoritmin on ratkaistava yleinen täsmällisesti määritelty ongelma. Algoritminen ongelma määritellään kuvaamalla tapaukset (instanssit), joissa sen on toimittava ja sen tuloste jonkin tapauksen suorittamisen jälkeen. Erottelu yleiseen ongelmaan ja ongelman tapaukseen on olennainen. Yleisen tapauksen tunnistaminen on ensimmäinen askel ratkaisemiseen.[15]

Hyvällä algoritmilla on kolme haluttavaa ominaisuutta: oikeellisuus, tehokkuus sekä toteutuksen helppous. Kaikki ominaisuudet eivät ole aina yhtä aikaa saavutettavia.[15] Tietorakenteen vaihtaminen ei vaikuta oikeellisuuteen, mutta se voi tarjota vaihtoehtoja ja vaikuttaa operaatioiden tehokkuuteen, jolloin suorituskyky voi parantua dramaattisesti.[15] Haastavimmat ongelmat algoritmeissa liittyvät optimointiin, jolloin etsitään ratkaisua, joka maksimoi tai minimoi funktion.[15]

Lakiasiat

Pääartikkeli: Patentti

Ohjelmistopatenttien käsittely on kiistanalaista, mutta patenttien laajentaminen algoritmeihin on tyrmätty.[16] "Matemaattisia algoritmeja" ei ole voinut patentoida, mutta eräät ihmiset sijoittavat tietokoneohjelman toteuttaman algoritmin eri kategoriaan pohtiessaan patentoivuutta.[16]

Muutamia algoritmeja

Myös äänen- ja kuvanpakkaukseen liittyvät koodekit käyttävät erilaisia algoritmeja.

Matemaattisia algoritmeja:

Katso myös

Lähteet

  1. Vähäkotamäki, Antti & Savolainen, Tapani & Kärki, Pekka: Ohjelmoinnin peruskurssi – verkkomateriaali – 5. Algoritmi. Helsingin yliopisto. 2004. Arkistoitu 17.3.2013. Viitattu 21.9.2020.
  2. J. G. Brookshear, D. Brylow, N. Harris: Computer Science: An Overview (PDF) w3.cs.jmu.edu. 2015. Viitattu 28.10.2017. (englanniksi)
  3. Brookshear, J. Glenn & Brylow, Dennis: Computer Science an overview, s. 14. 12th edition. Pearson Education, 2015. ISBN 978-1-292-06116-0. (englanniksi)
  4. Turing Machines plato.stanford.edu. Viitattu 7.2.2020. (englanniksi)
  5. The Definition of Algorithm (PDF) cs.utsa.edu. Viitattu 16.9.2022. (englanniksi)
  6. Definition of a Turing machine (PDF) cs.cornell.edu. 2018. Viitattu 16.9.2022. (englanniksi)
  7. Andreas Blass & Yuri Gurevich: Algorithms: A Quest for Absolute Definitions (PDF) microsoft.com. Viitattu 8.9.2022. (englanniksi)
  8. Wirth, Niklaus: Algorithms + Data structures = Programs, s. 1. Prentice-Hall, 1976. ISBN 0-13-022418-9. (englanniksi)
  9. Knuth, Donald: The art of computer programming : Fundamental algorithms, s. 16. Third Edition. Addison Wesley, 1997. ISBN 0-201-89683-4. (englanniksi)
  10. Ada Lovelace Computer History Museum. Viitattu 12.7.2018. (englanniksi)
  11. Ada Lovelace's Note G projectlovelace.net. Viitattu 18.9.2022. (englanniksi)
  12. John Bullinaria: Lecture Notes for Data Structures and Algorithms (PDF) (sivu 5) cs.bham.ac.uk. 27.3.2019. Viitattu 8.9.2022. (englanniksi)
  13. Mehta, Dinesh P. & Sahni, Sartaj: Handbook of Data Structures And Applications, s. 1-1, 1-6. Chapman & Hall/CRC, 2005. ISBN 1-58488-435-5. (englanniksi)
  14. Thomas H. Cormen & Charles E. Leiserson & Ronald L. Rivest & Clifford Stein: Introduction to Algorithms, s. 26. Second edition. MIT Press, 2003. ISBN 0-262-03293-7. Teoksen verkkoversio. (englanniksi)
  15. Skiena, Steven S.: The Algorithm Design Manual, s. 34,65,273. Second edition. Springer, 2008. ISBN 978-1-84800-070-4. doi:10.1007/978-1-84800-070-4. (englanniksi)
  16. Timothy B. Lee: Ctrl-Z: a return to the Supreme Court’s software patent ban? arstechnica.com. 28.1.2009. Viitattu 22.10.2021. (englanniksi)

    Aiheesta muualla

    • Algorithm Encyclopedia of Mathematics (englanniksi)

    Kirjallisuutta

    • Brookshear, J. Glenn (1989). Theory of Computation: Formal Languages, Automata, and Complexity. Redwood City, California: Benjamin/Cummings Publish Company, Inc. ISBN 0-8053-0143-7.
    • A. Aho, J. Hopcroft, J. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. ISBN 978-0201000290. (englanniksi)
    • Knuth, Donald E.: Fundamental Algorithms, The Art of Computer Programming. Addison-Wesley Publishing Company, 1976. (englanniksi)
    • Wirth, Niklaus: Algorithms + Data Structures = Programs. Prentice-Hall, 1976. ISBN 0-13-022418-9. (englanniksi)
    • Kaleva, Osmo: Numeerinen analyysi. Opintomoniste 163. Tampere: TTKK, 1993. ISBN 951-721-941-5.
    • Goodrich, Michael T. & Tamassia, Roberto: Algorithm Design and Applications. Wiley, 2014. ISBN 978-1-118-33591-8. (englanniksi)
    • Kleinberg, Jon & Tardos, Eva: Algorithm Design. Pearson, 2005. ISBN 978-0321295354. (englanniksi)
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.