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