Algoritmejä

Algoritmi on systemaattinen, rajallinen ja toistettava ohjeistus ongelman ratkaisemiseksi. Se kuvaa sarjan vaiheita, joita noudattamalla ohjelmisto tuottaa halutun tuloksen syötteestä. Hyvin suunniteltu algoritmi on selkeä, deterministinen ja päättäväinen; sen suoritus voidaan analysoida ja oikeellisuus todistaa.

Historiallisesti algoritmeja on käytetty jo antiikin ajoista; esimerkkinä Euclidoksen algoritmi, jolla lasketaan suurin yhteinen tekijä. 1900-luvulla computability- ja kompleksiteettiteorioiden kehittyessä algoritmeista muodostui tiukka tietojenkäsittelytieteen ala. Turingin koneet ja Big-O -analyysi ovat olleet keskeisiä työkaluja suoritusaikojen ja muistinkäytön arvioinnissa.

Algoritmeja voidaan luokitella monella tavalla. Ne ovat usein deterministisiä tai stokastiisia; suunnittelussa hyödynnetään paradigmoja kuten jakaminen ja valloittaminen (divide and conquer), dynaaminen ohjelmointi, ahneus (greedy) sekä backtracking. Lisäksi on heuristiikkoja ja approximaatioita, joita käytetään ongelmiin, joille ei löydy nopeaa optimaalista ratkaisua. Oikeellisuuden ja päättymisen varmuus sekä analysointi ovat keskeisiä osa-alueita.

Yleisimmät kategorit ovat lajittelu-, haku-, reititys- ja graafialgoritmit. Esimerkkejä: lajittelussa Merge Sort ja Quick Sort; hakuissa binäärihaku; reititys- ja graafialgoritmeissa Dijkstra, Bellman-Ford ja A*; lisäksi puu- ja verkkoanalyyseihin liittyvät menetelmät kuten Kruskal ja Prim.

Algoritmeja sovelletaan laajasti ohjelmistokehityksessä, tietokannoissa, tietoliikenteessä, bioinformatiikassa, logistiikassa, tekoälyssä ja muilla aloilla. Oikeellisuuden ja päättymisen varmistaminen sekä suorituksen tehokkuuden analysointi ovat keskeisiä osa-alueita.