Keskustelu: Yleinen keskustelu: Opasprojekti: Algoritmit

Alan kirjoittaa keväällä algoritmiaiheista opassarjaa, joka korvaa nykyiset kaksi opasta aiheesta "Algoritmien aakkoset". Oppaiden tarkoituksena on kertoa algoritmien suunnittelusta sekä teoreettisesta että käytännöllisestä näkökulmasta. Lukijalta vaaditaan ohjelmoinnin perusteiden osaaminen sekä yläasteen matematiikan tiedot.

Tässä on opassarjan hyvin alustava aiheluettelo:

Osa 1: Johdanto
- peräkkäishaku ja binäärihaku
- aikavaativuus ja tilavaativuus

Osa 2: Lajittelu
- kuplalajittelu
- pikalajittelu
- laskentalajittelu

Osa 3: Verkot
- yleistä verkoista
- leveyshaku ja syvyyshaku
- samalla: jono ja pino

Osa 4: Reitinhaku
- A*-algoritmi
- samalla: keko

Osa 5: Ahneet algoritmit
- edustavia esimerkkejä

Osa 6: Dynaaminen ohjelmointi
- edustavia esimerkkejä

Osa 7: Merkkijonot
- merkkijonon etsintä
- Boyer-Moore-algoritmi

Osa 8: Tekoäly
- minimax-algoritmi

Osa 9: NP-ongelmat
- P ja NP
- NP-täydellisyys
- esimerkkejä

Liite: Vaativuusluokat
- lineaarinen, neliöllinen, ...

Miltä tämä suunnitelma vaikuttaa? Mitä pitäisi vielä käsitellä?

Lisäksi: Pitäisikö oppaissa käyttää pseudokoodia vai jotain ohjelmointikieltä? Jälkimmäisessä tapauksessa mitä ohjelmointikieltä?

Muita opassarjaan liittyviä ajatuksia?

Vaativuusluokilla meinaat varmaan Landau-notaatiota ja kumppaneita? Häirittee välillä, kun ei ymmärrä suomenkielistä termistöä. :D

Itse käsittelisin kunnolla algoritmien toimintaperiaatteen ja teorian sen takana ja pitäisin toteutuksen takasijalla, jokaisesta yksinkertainen pseudokooditoteutus lopussa. Jos opassarjan tarkoituksena on päinvastainen, toteutus etusijalla ja teorialla ei niin suurta merkitystä, on joku curly bracket -kieli aika hyvä valinta. Jos osaa yhden, ymmärtää aika hyvin muita, ja vastaavan version kirjoittaminen itselle tutulla kielellä toisen toteutuksen pohjalta ei ole hankalaa.

Lajitteluun voisi ottaa mukaan radix ja merge sortit, jotka ovat tehokkaita ja yleisesti käytettyjä. Radixin ainakin saattaa joutua itse koodaamaan, jos haluaa lisää tehokkuutta järjestämiseen.

Reitinhaun voisi aloittaa dijkstralla ja edetä vasta sitten A*:iin. Voisi myös mainita A*:n yhteydessä IDA* algoritmin, joka on paremmin käytettävissä suuressa hakuavaruudessa. Reitinhaun yhteydessa kannattaa painottaa, että näillä algoritmeillä ei etsitä vain 'reittejä' vaan ne on yleisluontoisia algoritmejä ongelmiin, joissa pitää löytää toimintasarja, jolla pääsee tilasta A tilaan B. Monet ongelmat voidaan palauttaa reitinhakuongelmaksi.

Vaativuusluokkien yhteydessä pitää muistaa erotella aika ja tila vaatimukset. Tietysti on myös hyvä mainita keskimääräiset ja pahimman tapauksen vaatimukset.

Yhtenä uutena osana voisi puhua algoritmista rinnakkaisohjelmoinnissa tai miten esitellyt algoritmit toimivat useammalla prosessorilla.

Noiden vaikeiden ongelmien yhteydessa voisi esitellä joitain optimointitekniikoita (siis ratkaisun optimointi, ei koodin optimointi). Näillä siis pyritään mahdollisimman hyvään ratkaisuun vaikeassa ongelmassa, johon ei välttämättä voida laskea optimaalista ratkaisua. Esimerkkinä simuloitu jäähdytys, jota olen tullut käyttäneeksi muutaman putkapostin ratkaisussa.

Algoritmien toimintaperiaatteen voi esittää pseudokoodilla, mutta itse yleensä jään kaipaamaan toimivaa testiohjelmaa, jota voi hiukan muutella ja tutkia.

Jes, tällaista opasta olen kaivannutkin. Ei ole ikinä oikein tullut opeteltua noita reitinhakualgoritmeja. Kaikki kirjat ja englanninkieliset artikkelit aiheesta ovat olleet melko luotaantyöntäviä.

Minusta olisi parempi, jos esimerkit olisi tehty jollakin ohjelmointikielellä, niin niitä voisi sitten itse kukin tutkia ja muutella helposti, kuten FooBat jo edellä sanoi. Runsaasti kommentoituna se olisi varmaan yhtä selkeää kuin pseudokoodi. Ehkäpä kaikkein mukavin kieli tähän olisi mielestäni C++, sillä sen osaavat suunnilleen kaikki.

:)vihdoinkin, ilmestyykö tuo ennen 2011 datatähteä?

Vaikuttaa hyvältä oppaalta. Olen FooBatin kanssa eri mieltä noista lajitteluista. Ei kannata keskittyä liikaa yhteen osa-alueeseen. Lajittelualgoritmeista löytää varmasti itse tarvittaessa lisää tietoa.

Algoritmit on minustakin yleensä selkeintä esittää pseudokoodina, mutta valmiit koodiesimerkit olisivat hyvä lisä. Näitä voisi olla peräti useilla kielillä. Jos kuitenkin pitäisi valita, niin voisin kallistua Javan puolelle. C++(98) on vähän sotkuista.

VB6: Sorting algorithms löytyy lajittelusta hieman lisää syvyyttä ajatteluun. Tuolla nousee esille se asia, että joskus alkuperäinen järjestys halutaan säilyttää samanarvoisten arvojen osalta, jolla on väliä kun taulukossa on muutakin tietoa kuin itse järjesteltävä tieto. Toinen olennainen asia on lajittelualgoritmin kyky toimia vajaan tiedon kanssa, eli järjesteleminen silloin kun tietoa tulee vaikkapa paketeissa Internetin ylitse, läheskään kaikki algoritmit eivät pysty tähän.

Siten ainakin Merge Sort olisi olennainen lisäys. Myös Insertion Sort taitaa olla harkinnan arvoinen. Molemmat ovat suht lyhyitä koodattavia. Radixin voi mainita, mutta sen koodaaminen taitaa vaatia aikamoisen paljon enemmän päänvaivaa kuin nämä muut, ja lisäksi sehän taitaa erikoistua pelkästään merkkijonoihin. Kuplalajittelun voinee esitellä, mutta sen ongelma on järkyttävä hitaus heti kun lajiteltavaa on enemmän kuin vähän.

Kiitos hyvistä kommenteista. Ehkä paras ratkaisu olisi, että algoritmit olisivat oppaissa pseudokoodina, mutta lisäksi olisi saatavilla toimivat toteutukset esimerkiksi C++:lla.

Lajittelu on vähän ongelmallinen aihe, koska yleensä voi käyttää ohjelmointikielten valmiita tehokkaita algoritmeja. Toisaalta aihe kuuluu ohjelmoijan yleissivistykseen ja vastaavia tekniikoita voi soveltaa muissa algoritmeissa.

Yleensäkin haluaisin oppaiden opettavan enemmän algoritmien suunnittelua kuin esittelevän suuren joukon valmiita algoritmeja.

Antti Laaksonen kirjoitti:

Yleensäkin haluaisin oppaiden opettavan enemmän algoritmien suunnittelua kuin esittelevän suuren joukon valmiita algoritmeja.

Tämä on minustakin oikea tavoite. Lajittelussa olennaisempaa olisi perustella, miksi lajittelu vaatii tietyn määrän operaatioita ja miksi erilaiset menetelmät ovat vaativuudeltaan erilaisia. Valmiiden algoritmien pintapuolinen esittely ei ole kovin antoisaa: esimerkiksi merge sort usein esitellään ilman selityksiä siitä, miten kaksi järjestettyä taulukkoa yhdistetään tehokkaasti yhdeksi, vaikkei tämä suinkaan ole kaikille selvää.

Pseudokoodi on minusta hyvä ratkaisu. Esimerkkien kirjoittamisesta eri kielillä voidaan järjestää vaikka talkoot.

Minimaxin lisäksi voisi käsitellä alpha-beta pruning -algoritmin (mitä lie suomeksi). Se on hyvä esimerkki algoritmin optimoimisesta välttämällä turhia laskuja.

Suunnitelma todellakin näyttää hyvältä, etenkin siltä osin, ettei oteta liian montaa algoritmia per osa, koska muuten algoritmistä voi tulla turhan nopeaan käsitelty.

Nyt kun kaikki on opetelleen pythonin monen oppaan voimin, olisi se minun kielen elegattiuden takia paras kieli esittää esimerkin.

Itsestä tosin ei oppaan kirjoittajaksi ole, koska ei itselläkään ole tullut algoritmejä sen syvellisemmin opiskeltua. Huomattavaa on lisäksi että Ohjelmointiputkassa on jo opassarja algoritmeistä, jotta esim. aika- ja tila-vaatimuksia ei kirjoiteta uudestaan (ts. tule päällekkäisyyksia).

ZcMander kirjoitti:

Huomattavaa on lisäksi että Ohjelmointiputkassa on jo opassarja algoritmeistä, jotta esim. aika- ja tila-vaatimuksia ei kirjoiteta uudestaan (ts. tule päällekkäisyyksia).

Antti Laaksonen kirjoitti:

..., joka korvaa nykyiset kaksi opasta aiheesta "Algoritmien aakkoset".