2.1 Ohjelmointiympäristön asennus
2.2 TDD-testit
3.1 Taulukko (array)
3.2 Hajautustaulu (hash table, map)
3.3 Joukko (set)
3.4 Jono (queue)
3.5 Pino (stack)
3.6 Linkitetty lista (linked list)
3.7 Verkko (graph)
3.8 Binääripuu (BST ja b-tree)
4.1 Algoritmien tehokkuus
4.1.1 Big O -notaatio
4.1.2 Ahne algoritmi
4.1.3 Kuinka teet tehokkaampia algoritmeja
4.2 Lajittelualgoritmit
4.2.1 Lisäyslajittelu (InsertionSort)
4.2.2 Valintalajittelu (SelectionSort)
4.2.3 Pikalajittelu (QuickSort)
4.3 Haku- ja reitinetsintäalgoritmit
4.3.1 Binäärihaku (BinarySearch)
4.3.2 Leveyshaku (BreadthFirstSearch)
4.3.3 Dijkstran algoritmi (Dijkstras)
4.3.4 Joukkopeitto (SetCover)
4.4 Regressio- ja luokittelualgoritmit
4.4.1 Lineaarinen regressio (LinearRegression)
4.4.2 Logistinen regressio (LogisticRegression)
4.4.3 K-NN -algoritmi (K-Nearest Neighbours)
4.4.4 K-means -algoritmi (K-means clustering)
Tehtävät1 - Tietorakenteet
Tehtävät2 - Algoritmit
Tietorakenteet ja Algoritmit (3op) kuuluu Jyväskylän Ammattikorkeakoulun (JAMK) Tietojenkäsittelyn koulutusohjelman (Tiko) vapaavalintaisiin ammattiopintoihin.
Opettaja Tommi Tuikka, tuito(at)jamk.fi
Muut perustiedot ovat opintojakson Moodle-työtilassa.
Kurssilla käytetään ohjelmointikielenä Javascriptiä Nodejs-alustalla. Javascript on hieman epätyypillinen Tietorakenteet ja Algoritmit -kurssin kieleksi, sillä yleensä tämän aihealueen kurssilla ohjelmointikielenä on Python, C tai Java. Mutta koska koulutusohjelmassa koulutetaan web-kehittäjiä, ja web-kehittäjä tarvitsee tietorakenteita ja algoritmeja esim. frontend-sovelluskehityksessä (React, Angular, Vue, Svelte), backend-sovelluskehityksessä (Node.js), tekoälykehityksessä (Tensorflow.js), ja datan visualisoinnissa (d3.js), niin JS:n valinta kurssin kieleksi on perusteltua. Ohjelmointiympäristönä käytetään normaalia JS-ekosysteemiä ja kehitysvälineenä Visual Studio Code -editoria.
Debuggaus on algoritmeja tutkittaessa ja
kehitettäessä usein välttämätöntä. Koodissa esiintyvien muuttujien
arvojen muutoksen seuraaminen helpottaa algoritmien ymmärtämistä.
VSCodessa on sisäänrakennettu JS-debuggeri. Oletuksena debuggaus
onnistuu vain Nodejs-moottorissa (ei selaimessa) suoritettavalle
koodille. Debuggaus suoritetaan tavallisesti vain omalle koodille
ja ulkopuoliset kirjastot olisi hyvä "skipata". Tämä onnistuu
laittamalla skipFiles-määritys VSCode-projektin
launch.json-tiedostoon.
➤Video JS-koodin debuggauksen alkeista VSCodella. Videossa debugattava koodi - debug_example.zip - suoritetaan Nodejs-moottorissa.
Useimmissa kurssin tehtävissä tarjotaan test-kansiossa olevat testit jotka ajamalla voi varmistaa, että tehtävä on tehty oikein. Kyseessä on TDD eli Test Driven Development joka on JS-ohjelmoinnissa varsin yleinen menetelmä. TDD eli testivetoinen kehitys tarkoittaa koodausta jossa muusta koodista eristetty koodinpätkä, esim. funktio, testataan koodausvaiheessa siten että ensin kirjoitetaan testi ja sitten kirjoitetaan testin läpäisevä koodi. Työskentely tapahtuu siis yksikkötestauksen "vetämänä" eli "test driven". Kyseessä ei ole varsinaisesti testausmenetelmä vaan kehitysmenetelmä, joskin samalla tulee testaus hoidettua. Lisäksi testit toimivat koodin dokumentaationa.
Tämän kurssin testeissä käytetyt testikirjastot:
-Mocha -
testien suorituskirjasto (testing framework)
-Chai -
väitekirjasto (assertion library), jolla asetetaan ja tarkistetaan
testin väitteet.
Mochalla ja Chailla totetettu yksinkertainen testauskoodi kun testataan laskeMerkit-funktiota. Kyseessä on vain esimerkki, eikä se ole riittävä varmistamaan että laskeMerkit on toteutettu oikein:
const expect = require('chai').expect;
const laskeMerkit = require('../app/laskeMerkit');
describe('Testataan laskeMerkit-funktiota', ()=> {
it('laskee merkkijonon merkkien lukumäärän', ()=> {
const tulos = laskeMerkit('mjono');
expect(tulos).to.equal(5); //expect on Chai-kirjaston väite
});
});
Kun testi ajetaan, se ei mene läpi. Sitten toteutetaan laskeMerkit-funktio ja testin pitäisi mennä läpi. Describe on "test suite" eli kokoelma tietyn yksikön testejä. Sen callbackin sisällä olevat it-funktiot ovat varsinaisia testejä.
Oikeaoppinen TDD:n käyttö edellyttäisi tietenkin sitä, että opiskelija tekisi itse testit ennen tehtävien ratkaisua, mitä tällä kurssilla ei kuitenkaan vaadita. Testien suunnittelu pakottaa ohjelmoijan pohtimaan tarkemmin sitä miten koodin pitäisi toimia, joten ohjelmoijan looginen ajattelukyky paranee. TDD myös pakottaa suunnittelemaan koodin siten, että se koostuu helposti testattavista yhtenäisistä osista, jotka eivät ole liian tiiviisti sidottu toisiinsa (loose coupling). Koodi jota on helppo testata testeillä, jotka eivät ole liian pitkiä, on yleensä laadukasta koodia.
Jos tietokoneen muistissa voisi olla vain muuttujia, jotka sisältävät ainoastaan yhden arvon (primitiivinen tietorakenne ja tietotyyppi), olisi tietojenkäsittely hyvin hankalaa. Siksi on kehitetty ei-primitiivisiä tietorakenteita, jotka voivat sisältää useita arvoja eri tavoin muistiin järjestettynä. Käsitteellä tietorakenne tarkoitetaankin käytännössä aina ei-primitiivisiä tietorakenteita eli muistiin eri tavoin järjestettyjä tietokokoelmia. Tietorakenteeseen kuuluvat lisäksi myös tietojen väliset suhteet sekä metodit ja operaatiot joita tietoihin voi kohdistaa. Tietorakenne on siis tietojen järjestämis-, hallinta- ja varastomuoto, joka mahdollistaa tehokkaan tietojen hakemisen ja muokkauksen. Tietorakenteet ovat yleensä välttämättömiä algoritmien kehityksessä. Siksi tietorakenteet ja algoritmit käsitellään tietojenkäsittelyn oppilaitoksissa yleensä samalla kurssilla, jonka nimi on perinteisesti Tietorakenteet ja Algoritmit.
Kurssilla käydään läpi vain muutamia yleisimpiä tietorakenteita. Erilaisia tietorakenteita ja niiden muunnoksia on olemassa useita kymmeniä.
Taulukko on
tietorakenteista tutuin, sillä siihen tutustutaan aina jo
ohjelmoinnin peruskurssilla. Taulukko on yksinkertainen tapa
säilyttää tietokokoelmaa ohjelmassa. Siinä on n alkiota
joiden sijainteja kuvataan indekseillä 0,1,...,n-1.
Taulukko on sisäänrakennettuna JS:n Api:ssa. JS:ssä taulukko on myös olio, joten sillä on myös olion ominaisuudet. JS:ssä taulukko on hieman erilainen kuin monissa muissa ohjelmointikielissä. JS-taulukossa voi olla alkioita, joiden tietotyypit ovat erilaisia. Taulukon koko ei ole etukäteen määrätty, vaan sen muuttaminen on helppoa. JS-taulukolla on paljon metodeja tietojen hakemiseen ja muokkaukseen esim. forEach(), push() tai slice(). Taulukolla on length -property jota käytetään kun tarvitsee hakea taulukon pituus.
Hajautustaulu (hash table, map) on tietorakenne joka sisältää tietoja avain-arvo -pareina. Sitä voidaan kutsua myös assosiatiiviseksi taulukoksi, sillä avain voi kuvata arvoa, eli tarjota assosiaation (mielleyhtymän) arvoon, esim. Map{'nimi'=>'Tommi', 'tulos'=>25}. Avaimet voivat olla tyypiltään mitä tahansa. Hajautustaulua käytetään algoritmeissa tiedon välivarastointiin. Sen avulla voidaan esimerkiksi nopeuttaa algoritmeja dynaamisen ohjelmoinnin keinoin.
Hajautustaulun nimi johtuu siitä että hajautusfunktio arpoo
tauluun lisättävien tietojen muistipaikat, jotka pyritään
asettamaan optimaalisesti, jotta tietojen haku olisi
mahdollisimman nopeaa. JS:ssä käytetään avain-arvo -parien
säilyttämiseen usein myös tavallisia olioita, koska ne ovat
yksinkertaisia ja soveltuvat moniin tarkoituksiin yhtä hyvin kuin
hajautustaulu. Hajautustaulua ei kuitenkaan aina voi korvata
oliolla, sillä erojakin on.
Hajautustaulu eli Map-tietorakenneluokka on sisäänrakennettuna JS:n Api:ssa. Hajautustaulu syntyy muistiin, kun luokasta luodaan olio. Map-olion metodeja ovat mm. get() ja set(), ja hajautustaulun koko saadaan size -propertystä.
Joukko on taulukkoa muistuttava tietorakenne
jonka kaikki arvot ovat uniikkeja eli kahta samaa arvoa ei voi
esiintyä. Joukko eroaa taulukosta myös siten, että sen alkioita ei
voi asettaa mihinkään määrättyyn järjestykseen. Joukkoa käytetään
ohjelmistokehityksessä esim. varmistamaan että tietoalkiot ovat
uniikkeja. Sitä käytetään myös nopeisiin hakuihin joissa tutkitaan
onko tietty alkio joukossa joka koostuu hyvin suuresta määrästä
alkioita. Joukon unioni ja leikkaus ovat hyödyllisiä joissakin
tietojenkäsittelytehtävissä. Joukko (Set) on JS:n Api:ssa
sisäänrakennettuna, ja siihen voidaan lisätä alkiot helposti
taulukosta, joka annetaan argumenttina Set()-luokan
konstruktoriin.
Jono on taulukkoa muistuttava tietorakenne joka eroaa taulukosta
lähinnä alkioiden lisäyksen ja poiston osalta. Vain jonon loppuun
voi lisätä alkioita ja vain sen alusta voi ottaa niitä pois. Jono
on ns. FIFO -tietorakenne (First In First Out). Jonoa voidaan
käyttää esimerkiksi keräämään jatkuvana virtana sovellukseen
saapuvaa dataa (stream), jolloin voidaan päästää läpi
merkityksetön data ja ottaa tarkempaan käsittelyyn merkittävä
data. Jonoa ei ole sisäänrakennettuna JS:n Api:ssa, mutta sen
toteutukseen on ulkopuolisia kirjastoja kuten queue-fifo.
Pino on muuten samanlainen kuin jono, mutta vain pinon päälle voi lisätä alkioita ja vain sen päältä voi ottaa niitä pois. Pino on ns. LIFO -tietorakenne (Last In First Out). Käytännön esimerkki pinosta on ohjelmistokehityseditorien debug -tilassa näkyvä Call stack eli kutsupino. Pino on kätevä apuväline esim. algoritmeissa joissa tietojen järjestys pitää kääntää päinvastaiseksi. Pinoa ei ole sisäänrakennettuna JS:n Api:ssa, mutta sen toteutukseen on ulkopuolisia kirjastoja kuten stack-lifo.
Linkitetty lista on yksinkertaisin osoittimiin perustuva tietorakenne. Se muistuttaa jossain määrin taulukkoa, mutta lista muodostuu ns. solmuista joissa on viittaus (osoitin) seuraavaan solmuun (singly-linked-list) tai edelliseen ja seuraavaan solmuun (doubly-linked-list). Solmussa on osoittimien lisäksi tietoalkio. Linkitetyn listan solmut eivät ole koneen muistissa peräkkäin kuten taulukon alkiot, vaan viereiset solmut löydetään osoittimien avulla. Linkitettyä listaa käytetään harvoin sellaisenaan, mutta sitä käytetään usein muiden tietorakenteiden kehittämiseen. Käytännön esimerkki tilanteesta jossa linkitetty lista on tehokas tietorakenne voisi olla vaikkapa musiikkisoittimen kappalelista, jossa soitetaan kappaleita tietyssä järjestyksessä ja listasta poistetaan ja sinne lisätään kappaleita. Listan solmujen lisäys ja poisto on paljon nopeampi operaatio, kuin vastaavat toimenpiteet taulukossa. Linkitettyä listaa ei ole sisäänrakennettuna JS:n Api:ssa, mutta sen toteutukseen on ulkopuolisia kirjastoja kuten simple-double-linked-list.
Verkko on tietorakenne joka muodostuu solmuista (vertice) ja
niiden välisistä kaarista (edge).
Verkossa oleva polku (path) on kaarta pitkin kulkeva reitti
lähtösolmusta kohdesolmuun. Suunnatussa (directed ) verkossa
jokaisella kaarella on tietty suunta johon täytyy kulkea kaarta
pitkin. Solmun naapureita (neighbors) ovat kaikki solmut, joihin
se on yhteydessä kaarella, ja solmun aste (degree) on sen
naapureiden määrä. Verkko on puu (tree), jos se on yhtenäinen eli
kaikki verkon solmut ovat polkujen kautta yhteydessä toisiinsa, ja
lisäksi syklitön eli kaaret eivät muodosta rengasrakennetta.
Verkkoa käytetään algoritmeissa joissa esim. optimoidaan
reitinhakua tai tehdään hakuja sosiaalista verkostoista.
Neuroverkkoa käytetään koneoppimissovelluksissa. On olemassa myös
verkkotietokantoja, kuten Neo4J. Verkkoa ei ole
sisäänrakennettuna JS:n Api:ssa, mutta sen toteutukseen on
ulkopuolisia kirjastoja kuten graph-data-structure.
Binääripuu on verkon erikoistapaus ja esim. tiedostojärjestelmissä ja tietokannoissa yleisimmin esiintyvä tietorakenne. Binääripuu muistuttaa ylösalaisin käännettyä puuta ja se muodostuu solmuista. Puussa ylimpänä on solmu, jota kutsutaan juureksi (root). Jokaisella solmulla voi olla yksi tai kaksi lasta(child ), ja erikoistapauksissa (b-tree) useampikin lapsi. Kaikilla solmuilla juurta lukuun ottamatta on yksikäsitteinen vanhempi (parent). Puun lehtiä (leaf ) ovat solmut, joilla ei ole lapsia. Binääripuun rakenne on hierarkinen ja rekursiivinen: jokainen solmu toimii juurena alipuulle (subtree), joka on myös binääripuu. Binääripuun yleisimmin käytetyt tyypit ovat binäärihakupuu (BST) ja b-tree. Binääripuun avulla voidaan ratkaista sellaisia tietojenkäsittelyn ongelmia jotka edellyttävät tietojen järjestämistä hierarkiseen rakenteeseen. BST ja b-tree ovat tehokkaita hakualgoritmeissa. Binääripuuta ei ole sisäänrakennettuna JS:n Api:ssa, mutta sen toteutukseen on ulkopuolisia kirjastoja kuten bst-js joka on binäärihakupuu.
Algoritmi on toimintaohje jota seuraamalla voimme ratkaista jonkin tietojenkäsittelyn ongelman. Algoritmille annetaan syöte (input) eli tiedot jotka tarvitaan ongelman ratkaisuun. Algoritmi tuottaa tulosteen (output) joka on ongelman ratkaisu. Periaatteessa kaikki ohjelmonti on toimintaohjeiden antamista koneelle, eli tavallaan algoritmien kehittämistä, mutta algoritmilla tarkoitetaan yleensä hieman vaativampaa ja monimutkaisempaa toimintaohjetta. Sovelluskehittäjän ei yleensä tarvitse itse kehittää monimutkaisimpia algoritmeja, mutta hänen pitäisi osata löytää sopiva valmis algoritmi, ja osata käyttää sitä ongelman ratkaisuun.
Algoritmit tehdään yleensä uudelleenkäytettäviksi sovelluksen
rakenneosiksi, esim. funktioiden tai luokkien sisään. Algoritmien
toteutuksessa käytetään yleensä tarkoitukseen sopivia
tietorakenteita.
Algoritmit voidaan luokitella monilla eri tavoilla. Esimerkiksi
käyttökonteksti, toimintaperiaate ja käyttötarkoitus voivat toimia
luokitteluperusteina. Kurssin esimerkeissä on käytetty
yksinkertaista käyttötarkoitukseen perustuvaa luokittelua.
Esimerkit edustavat vain muutamia tunnettuja ja
sovelluskehityksessä paljon hyödynnettyjä algoritmeja.
Algoritmien tehokkuutta kuvataan ns. Big O -notaatiolla. Samalla notaatiolla
kuvataan myös tietorakenteiden operaatioiden (lisäys, poisto
jne... ) tehokkuutta. Tehokkuus voi liittyä aikavaativuuteen (time
complexity) tai muistivaativuuteen (space/memory complexity).
Aikavaativuus tarkoittaa algoritmin suoritusaikaa eli nopeutta
(riippuu myös koneen tehokkuudesta) ja muistivaativuus vaadittavan
muistin määrää.
Big O -notaatio alkaa isolla O-kirjaimella ja sen perässä olevien sulkujen sisällä on tehokkuutta kuvaava kerroin. Esimerkiksi O(n*n) tarkoittaa sitä, että jos tapauksia on n kappaletta, algoritmi pitää suorittaa enintään n*n kertaa ennen kuin se tuottaa oikean tuloksen. Jos kyse on ajankäytöstä, tämä tarkoittaa sitä että tapausten lisääntyessä (esim. taulukon alkiot), lisääntyy algoritmin(esim. taulukon järjestäminen) ajankäyttö neliöllisesti.
Big O -notaatio kertoo suurimman mahdollisen ajankulutuksen tai muistinkulutuksen. Pienintä mahdollista ajan/muistinkulutusta voidaan kuvata Omega -notaatiolla ja keskimääräistä ajan/muistinkulutusta Theta -notaatiolla, mutta niitä käytetään harvemmin.
Taulukossa on esitetty ajankäytön kasvu n -arvon kasvaessa:
| Notaatio | Nimi | n=10 | n=20 | n=100 | n=1000 | n=10^6 |
|---|---|---|---|---|---|---|
| O(1) | Vakio | 1 | 1 | 1 | 1 | 1 |
| O(log n) | Logaritminen | 3.32 |
4.32 |
6.64 |
9.96 |
19.93 |
| O(n) | Lineaarinen | 10 | 20 | 100 | 1000 | 10^6 |
| O(n log n) | Kvasilineaarinen | 33.22 | 86.44 | 664.39 | 9965.78 | 19.9*10^6 |
| O(n*n) | Neliöllinen | 100 | 400 | 10^4 | 10^6 | 10^12 |
| O(n*n*n) | Kuutiollinen | 1000 | 8000 | 10^6 | 10^9 | 10^18 |
| O(2^n) | Eksponentiaalinen | 1024 | 10.5*10^5 | 1.3*10^30 | --- | --- |
| O(n!) | Faktoriaalinen | 3.6*10^6 | 2.4*10^18 | --- | --- | --- |
Huomaa että log n -merkinnällä tarkoitetaan 2-kantaista logaritmia.
Ahne algoritmi (greedy algorithm) on algoritmi joka perustuu
siihen että pyritään saavuttamaan jokaisella algoritmin tapauksen
suorituskerralla mahdollisimman hyvä tulos (eli ollaan ahneita).
Näin tehdään vaikka lopputulos ei olisi välttämättä paras
mahdollinen, sillä parhaan mahdollisen lopputuloksen
saavuttamiseksi vaadittava aika on liian pitkä. Parhaan
mahdollisen eli täydellisen ratkaisun aikavaativuus on tällaisissa
tapauksissa yleensä O(n!). Ongelma joka on nopeillekin koneille
liian hidas ratkaistavaksi kun kaikki kombinaatiot on käytävä
läpi, on ns. "NP-complete" (NP === Nondeterministic Polynomial
time). Ehkäpä kuuluisin NP-täydellinen ongelma on ns. Kauppamatkustajan ongelma. NP-täydellinen
ongelma kannattaa siis ratkaista approksimaatiolla kuten ahneella
algoritmilla. Yksinkertaisella ahneella algoritmilla lopputulos
voi olla hyvin lähellä parasta mahdollista ja suoritus on nopea.
Myös Joukkopeitto eli SetCover on hyvä
esimerkki ahneen algoritmin hyödyntämisestä.
Ensimmäinen mieleen tuleva algoritmin ratkaisu ei useinkaan ole
tehokkain mahdollinen. Helpoin ratkaisu perustuu usein kaikkien
mahdollisten ratkaisuvaihtoehtojen läpikäymiseen hyödyntämällä
tietokoneen raakaa laskentatehoa eli "brute forcea". Tällöin
ratkaisu sisältää yleensä paljon samojen toimenpiteiden toistoa,
kuten samojen tietorakenteen alkioiden läpikäyntiä useita kertoja.
Järkevintä olisi kuitenkin etsiä ratkaisu jonka aikavaativuus ja
muistivaativuus ovat mahdollisimman pienet. Kannattaa muistaa,
että jos algoritmin suunnittelussa painotetaan nopeutta, yleensä
muistivaativuus kasvaa, ja sama pätee toisinpäin.
Suoritusympäristöstä riippuu, kuinka paljon kannattaa panostaa
nopeuteen, ja kuinka paljon vähäisempään muistin käyttöön.
Neljä yleisintä tehokkuutta parantavaa menetelmää ovat:
Lajittelualgoritmeilla lajitellaan tietorakenteen alkiot järjestykseen jonkin niiden ominaisuuden perusteella. Tyypillisin tapaus on taulukon sisältämien numeroiden järjestäminen suuruusjärjestykseen. Lajittelualgoritmien avulla on helppo havainnollistaa algoritmien toiminnan eroja, tehokkuutta ja Big O -notaatiota.
Lisäyslajittelu on lajittelualgoritmi jonka nopeus on 0(n*n). Eli
jos taulukossa on 8 alkiota, tarvitsee algoritmi suorittaa
enintään 64 kertaa, kunnes lajittelu on varmasti valmis.
Lisäyslajittelu perustuu alkioiden vertailuun ja sopivimman alkion
lisäämiseen oikealle paikalleen. Algoritmi on hidas, mutta sen
muistin käyttö on pienempi kuin esim. selvästi nopeammalla
pikalajittelulla.
Valintalajittelu on lajittelualgoritmi jonka teoreettinen nopeus on 0(n*n), mutta käytännössä se on nopeampi eli 0((n*n)/2), koska n:n lukumäärä vähenee yhdellä joka kierroksella. Valintalajittelu perustuu siihen että taulukosta valitaan esim. pienin alkio joka sijoitetaan uuden taulukon alkuun ja loput alkiot yhdistetään taulukoksi josta taas valitaan pienin jne. kunnes kaikki alkiot ovat järjestyksessä uudessa taulukossa.
Pikalajittelu on edellisiä algoritmeja nopeampi lajittelualgoritmi. Algoritmin nopeus on O(n*log n) eli jos taulukossa on 8 alkiota, tarvitsee algoritmi suorittaa enintään 8*3 = 24 kertaa. Pikalajittelu käyttää rekursiota joka on yleinen periaate algoritmeissa. Rekursiossa funktio kutsuu itseään. Ensin katsotaan toteutuuko mahdollisimman yksinkertainen 'base case' johon suoritus voi myös päättyä, ja jos se ei toteudu, toistetaan 'recursive casea'. Pikalajittelu on esimerkki "Divide and conquer" -periaatteella toteuteusta algoritmista.
Haku- ja reitinetsintäalgoritmeilla haetaan tietorakenteesta alkio/alkiot jonkin kriteerin perusteella tai etsitään verkosta lyhin/nopein reitti alkioiden välillä. Hakualgoritmit ovat lajittelualgoritmien ohella yleisimpiä "tavallisessa" sovelluskehityksessä käytettyjä algoritmeja.
Binäärihaulla haetaan lajitellusta taulukosta alkion arvon
perusteella sen indeksi. Haku tehdään nopeudella O(log n) eli jos
taulukossa on 8 alkiota, tarvitsee algoritmi suorittaa enintään 3
kertaa. Binäärihakua kutsutaan myös puolitushauksi koska se
perustuu haettavan alueen puolittamiseen jokaisella
hakukierroksella.
Leveyshaku on verkkoalgoritmi eli graph-algoritmi jolla haetaan verkosta lyhintä reittiä solmusta toiseen läpikäytävien solmujen lukumäärällä mitattuna. Algoritmin nopeus on O(solmujen lkm + kaarien lkm) eli O(V+E). V = vertices ja E = edges.
Dijkstran algoritmi on verkkoalgoritmi eli graph-algoritmi jolla haetaan verkosta solmuja ja nopeinta reittiä solmusta toiseen. Se eroaa leveyshausta siten että verkko on painotettu. Solmujen väliset kaaret eivät ole samanarvoisia vaan algoritmi ottaa kaarien väliset erot (esim. reitin vaatima matka-aika) huomioon.
Joukkopeitto on ahne algoritmi jonka tarkoituksena on hakea pienin mahdollinen määrä olemassa olevia joukkoja (set) jotka kattavat kaikki tunnetut alkiot. Joukkopeitto voidaan määritellä hakualgoritmiksi, mutta myös optimointialgoritmiksi. Joukkopeiton idea on erittäin yksinkertainen: valitse joukko joka kattaa mahdollisimman monta alkiota joita ei ole vielä peitetty. Ei haittaa vaikka mukana on alkioita jotka on jo peitetty. Tätä toistetaan kunnes kaikki alkiot on peitetty. Joukkopeiton nopeus on O(n*n), joten se on approksimaation ansiosta huomattavasti nopeampi kuin täydellinen ratkaisu jonka nopeus olisi O(n!).
Regressio- ja luokittelualgoritmit poikkeavat edellisistä algoritmeista siinä että ne pohjautuvat tilastotieteen menetelmiin. Niitä käytetetään erityisesti koneoppimis- ja tekoälysovelluksissa. Tarkoituksena on löytää tietorakenteiden alkioista johdonmukaisuuksia tai yhteisiä piirteitä, joiden perusteella voidaan tehdä johtopäätöksiä ja ennusteita tai luokittelua. Valmiita regressio- ja luokittelualgoritmeja on tarjolla useimmilla pilvialustoilla kuten esim. AWS Sagemakerissa tai Microsoft Azuressa.
Regression avulla kuvataan kahden tai useamman muuttujan välistä vuorovaikutussuhdetta, eli sitä, kuinka selitettävä muuttuja muuttuu, kun selittävät muuttujat muuttuvat. Regressio voidaan esittää koordinaatistoon piirretyn kuvaajan avulla. Lineaarinen regressio on yksinkertaisin regressioalgoritmi jonka toiminta perustuu lineaarisen suoran kaavaan y = ax + b, jossa y on selitettävä muuttuja ja x selittävä muuttuja. Lineaariseksi regressioksi kutsutaan joskus myös suorasta poikkeavaan käyrään perustuvia regressioita. Esim. exponentiaalinen regressio tai logaritminen regressio voidaan luokitella lineaarisen regression alalajeiksi, mutta myös omiksi regressiotyypeikseen.
Logistinen regressio eroaa lineaarisesta regressiosta siten että selitettävät muuttujat ovat todennäköisyyksiä välillä 0-1, jolloin 0 tarkoittaa että tapahtuma ei tapahdu ja 1 tarkoittaa että se tapahtuu. Logistisen regression kuvaaja on s-kirjainta hieman muistuttava sigmoidikäyrä ja sen kaava on hieman monimutkaisempi kuin lineaarisen regression yksinkertainen suoran kaava. Logistinen regressio on oikeastaan enemmänkin luokittelua kuin regressioanalyysia, vaikka sen nimessä esiintyy sana regressio.
K-NN -algoritmi on yksinkertainen luokittelualgoritmi jota käytetään paljon koneoppimisessa. K-NN -luokittelun ideana on luokitella koordinaatistoon asetettu datapiste siihen luokkaan johon kuuluvat useimmat sitä lähinnä olevat k kappaletta datapisteitä. Tyypillisiä k:n arvoja ovat esim. 3 ja 5. Algoritmia pitää harjoittaa harjoitusdatalla ennen sen käyttöä. K-NN toistaa määriteltyä laskentaprosessia, eikä algoritmissa ole mitään mallia tai painokertoimia jotka muuttuisivat uuden harjoitusdatan vaikutuksesta. Kuitenkin se tavallaan "oppii", koska sen tuottamat tulokset voivat parantua, kun harjoitusdataa tulee lisää.
K-means -algoritmi on myös luokittelualgoritmi, mutta menetelmä on hieman erilainen verrattuna K-NN:ään. Harjoitusdataa ei käytetä. Datapisteet luokitellaan k kappaleeseen klustereita eli luokkia. Aluksi luodaan oletetut klusterien keskipisteet eri puolille koordinaatistossa olevaa dataa. Sitten sijoitetaan alkiot siihen klusteriin jonka keskipiste on lähinnä. Sitten muutetaan keskipisteeksi klusterin alkioiden keskiarvovektori. Tätä toistetaan kunnes klusterien keskipisteet eivät enää muutu, eli klusterointia tarkennetaan iteroiden. K-means -algoritmin avulla on siis mahdollista löytää klustereita, eli uusia ryhmiä tai piirteitä, ennalta tuntemattomasta datasta.
***