Tietorakenteet ja algoritmit -kirja

Kirjoittaja: Antti Laaksonen

Tietorakenteet ja algoritmit on avoin oppikirja, joka käsittelee tehokkaiden algoritmien suunnittelua ja toteutusta. Kirja on tarkoitettu erityisesti oppimateriaaliksi samannimiselle kurssille Helsingin yliopiston tietojenkäsittelytieteen osastossa.

Kirja lähestyy aihepiiriä sekä teorian että käytännön kautta. Kirja pyrkii näyttämään, mikä yhteys teoreettisilla tuloksilla on siihen, miten hyvin algoritmit toimivat käytännössä. Kirja esittelee myös Java- ja Python-kielten tietorakenteita ja ominaisuuksia.

Lataa kirja (PDF)

Kirjan lisenssi on Creative Commons BY-NC-SA 4.0.

Yhteenveto sisällöstä

  1. Johdanto
    Mitä algoritmit ovat • Pseudokoodi • Ohjelmoinnin peruspalikat • Rekursio
  2. Tehokkuus
    Aikavaativuus • Merkinnät Ο, Ω ja Θ • Tilavaativuus
  3. Järjestäminen
    Lisäysjärjestäminen • Lomitusjärjestäminen • Pikajärjestäminen • Järjestämisen alaraja • Laskemisjärjestäminen • Binäärihaku
  4. Lista
    Taulukkolista • Linkitetty lista • Pino ja jono
  5. Hajautustaulu
    Hajautusfunktio • Hajautuksen tehokkuus • Joukon ja hakemiston toteutukset
  6. Binäärihakupuu
    Taustaa binääripuista • Binäärihakupuun operaatiot • AVL-puu
  7. Keko
    Binäärikeko • Prioriteettijono • Taulukon muuttaminen keoksi • Kekojärjestäminen
  8. Peruuttava haku
    Osajoukot • Permutaatiot • Kuningatarongelma • Branch and bound -tekniikka • Minimax-algoritmi
  9. Dynaaminen ohjelmointi
    Perustekniikat • Pisin nouseva alijono • Reitti ruudukossa • Repunpakkaus • Binomikertoimet
  10. Verkkojen perusteet
    Verkkojen käsitteitä • Verkon esitystavat ohjelmoinnissa • Syvyyshaku • Leveyshaku
  11. Lyhimmät polut
    Bellman–Fordin algoritmi • Dijkstran algoritmi • Floyd–Warshallin algoritmi
  12. Suunnatut syklittömät verkot
    Topologinen järjestys • Dynaaminen ohjelmointi verkoissa • Vahvasti yhtenäiset komponentit
  13. Komponentit ja virittävät puut
    Union-find-rakenne • Kruskalin algoritmi • Primin algoritmi
  14. Maksimivirtaus
    Ford–Fulkersonin algoritmi • Yhteys minimileikkaukseen • Edmonds–Karpin algoritmi • Erilliset polut • Maksimiparitus • Polkupeitteet
  15. NP-ongelmat
    Vaativuusluokat • P ja NP • NP-täydellisyys • SAT-ongelma • Ongelmien palautukset • Optimointiongelmat