Algoritmisuunnittelua

Algoritmisuunnittelua on tietojenkäsittelytieteen ala, joka keskittyy ongelmien ratkaisemiseen mahdollisimman tehokkaasti ja luotettavasti. Tavoitteena on kehittää ratkaisu, joka on sekä oikea että käytännöllisesti toteutettavissa suuremmissakin ongelmissa, ja jonka aikavaativuutta ja muistinkäyttöä voidaan analysoida. Suunnittelussa painotetaan oikeellisuutta, suorituskykyä sekä resurssien hallintaa.

Keskeisiä suunnittelumenetelmiä ovat erilaiset paradigmat kuten greedy-, divide-and-conquer-, dynamic programming sekä backtracking ja branch-and-bound. Lisäksi käytetään satunnaisia algoritmeja sekä approksimaatio- ja parametrisointitekniikoita silloin, kun tarkka ratkaisu olisi liian kallis. Ongelman muotoilu ja kyseessä olevan mallin oletukset ohjaavat valittavien menetelmien valintaa. Oikeellisuuden todistaminen sekä ajallinen ja muistinen analyysi ovat keskeisiä osia suunnitteluprosessia.

Esimerkkejä sovelluksista ovat lyhimmän polun ratkaisut kuten Dijkstra ja Bellman-Ford; järjestelyalgoritmit kuten quicksort ja mergesort; dynaamisen ohjelmoinnin klassiset ongelmat kuten knapsack ja pisin yhteinen alijono; Huffman-koodaus pakkaustehtävissä. Toisaalta monet verkko- ja optimointi-ongelmat ovat NP-kovia, jolloin ratkaisutyyppiä lähestytään heuristiikkain tai approksimaatioin.

Algoritmisuunnittelua sovelletaan laajasti ohjelmistokehityksessä, tietorakenteissa, verkko- ja optimointisovelluksissa sekä tieteellisessä tutkimuksessa, jossa keskeistä on saada ratkaisut sekä tehokkaasti että osoitettavasti oikein.