Sanastoa (glossary in Finnish)
Termien tarkemmat määrittelyt, sekä esimerkkejä, on annettu englanninkielisten termien viittaamissa kohdissa lukemistossa.
A | B | D | E | F | G | H | I | J | K | L | M | N | O | P | R | S | T | V | Y
- ahne algoritmi
en: greedy algorithm
Algoritmi, joka tekee jossain mielessä paikallisesti optimaalisen valinnan jokaisella askeleella. Ei välttämättä tuota globaalisti optimaalista ratkaisua.
- aikaleima
en: timestamp
Tieto, joka kertoo tietyn tapahtuman ajankohdan, joko absoluuttisesti tai suhteessa toisiin tapahtumiin.
- aliverkko
en: subgraph
Verkko \(G' = (V',E')\) on verkon \(G = (V,E)\) aliverkko jos \(V' \subseteq V\) ja \(E' \subseteq E\).
- aste
en: degree
Suuntaamattoman verkon solmun naapureiden lukumäärä.
- asteluku
Katso: aste
- AVL-puu
en: AVL tree
Eräs tasapainottettujen binäärihakupuiden luokka. Tasapainotusehto vaatii, että puun jokaisen solmun vasemman ja oikean lapsen alipuiden korkeudet eroavat korkeintaan yhdellä. Nimen “AVL” tulee tietorakenteen keksijöiden, Georgy Adelson-Velsky ja Evgenii Landis, sukunimistä.
- avoin osoittaminen
en: open addressing
Yhteentörmäysten käsittelymenetelmä hajautustauluissa.
- B-puu
en: B-tree
Itsestään tasapainottuva puutietorakenne. Käytetään esimerkiksi tietokantojen indeksoinnissa.
- Bellman-Fordin algoritmi
-
Suunnattujen kaaripainotettujen verkkojen algoritmi, joka laskee annetusta lähtösolmusta lyhimmät pulut kaikkiin lähtösolmusta saavutettaviin solmuihin. Kaaripainot voivat olla negatiivisia, ja algoritmi pystyy tunnistamaan onko verkossa lähtösolmusta saavutettava negatiivisen painon sykli.
- BFS
Katso: leveyshaku
- binäärihakupuu
-
Binääripuu, jonka solmuihin on liitetty alkioita. Lisäehtona tulee jokaiselle solmulle päteä, että solmun vasemman alipuun solmujen alkiot ovat korkeintaan yhtä suuria kuin solmun alkio, ja oikean alipuun solmujen alkiot ovat vähintään yhtä suuria kuin solmun alkio.
- binäärinen keko
en: binary heap
Binääripuu tietyillä lisäominaisuuksilla. Käytetään prioriteettijonojen ja kekojärjestämisen toteuttamiseen.
- binääripuu
en: binary tree
Juurellinen puu, jonka jokaisella solmulla voi olla vain vasen lapsisolmu ja oikea lapsisolmu, ja molemmat näistä voivat puuttua.
- bittivektori
en: bit set
Joukkotietorakenne avaimille, jotka ovat pienehköjä kokonaislukuja (tai voidaan helposti muuntaa sellaisiksi).
- DAG
Katso: suunnattu syklitön verkko
- DFS
Katso: syvyyshaku
- Dijkstran algoritmi
-
Ahne algoritmi, joka laskee suunnatun kaaripainotetun verkon annetusta lähtösolmusta lyhimmät polut kaikkiin lähtösolmusta saavutettaviin solmuihin. Kaaripainot eivät saa olla negatiivisia.
- dynaaminen ohjelmointi
-
Algoritmien suunnittelumenetelmä.
- edustaja-alkio
-
Alkio, joka toimii mahdollisesti suuremman alkiokokoelman edustajana. Esimerkiksi erillisten joukkojen tietorakenteessa kullakin joukolla yksi sen alkioista on sen edustaja.
- Fibonaccin luvut
-
Kokonaislukusarja \(0,1,1,2,3,5,8,...\), joka on määritelty rekursiivisesti siten että \(F_0 = 0\), \(F_1 = 1\) ja \(F_n = F_{n-1}+F_{n-2}\) kaikille \(n \ge 2\).
- funktio-ongelma
en: function problem
- geneerinen ohjelmointi
en: generics
- GPU
Katso: grafiikkasuoritin
- grafiikkasuoritin
-
Alunperin tietokonegrafiikan vaatimien laskutoimitusten suorittamiseen erikoistunut prosessorityyppi. Käytetään nykyään myös monenlaiseen muuhun laskentaan.
- hajautusarvo
en: hash value
Hajautusfunktion tuottama arvo.
- hajautusfunktio
en: hash function
Funktio, joka laskee annetulle syötteelle hajautusarvon.
- hajautustaulu
en: hash table
Tietorakenne joukkojen ja kuvausten toteuttamiseksi hajautusfunktioden avulla.
- hajota ja hallitse
-
Algoritmien suunnittelumenetelmä.
- invariantti
en: invariant
Matemaattisen olion ominaisuus, joka pysyy voimassa vaikka olioon tehdään muutoksia.
- jakoalkio
en: pivot element
Alkio, jonka suhteen pikajärjestämisalgoritmin ositusalgoritmi jakaa osataulukon.
- jono
en: queue
Kokoelmatietotyyppi. Sallii alkioiden lisäämisen (engl. “enqueue”) jonon loppuun ja poistamisen (engl. “dequeue”) jonon alusta. Samankaltainen kuin pino mutta FIFO-jonokurilla (engl. “first in, first out”).
- juurellinen puu
en: rooted tree
Puu, jonka yksi solmuista on valittu sen juureksi.
- järjestetty joukko
en: ordered set
Joukkotietorakenne, joka ylläpitää alkioiden järjestystä. Mahdollistaa pienimmän, suurimman, seuraaja- ja edeltäjäalkioiden tehokkaan etsimisen.
- järjestetty kuvaus
en: ordered map
Kuvaustietorakenne, joka ylläpitää tallennettujen avainten järjestystä. Mahdollistaa pienimmän, suurimman, seuraaja- ja edeltäjäavainten tehokkaan etsimisen.
- järjestetty puu
en: ordered tree
Juurellinen puu, jossa solujen lapsisolmut ovat järjestetty.
- kantalukujärjestäminen
en: radix sort
Järjestämisalgoritmi taulukoille, joiden alkiot ovat sekvenssejä pieniä kokonaislukuja (tai helposti nähtävinä sellaisina).
- kasautuminen
en: clustering
Avointa osoittamista ja (lineaarista tai neliöllistä) kokeilua käyttävissä hajautustaluissa esiintyvä ilmiö.
- kattava hakeminen
-
Hakualgoritmi, joka käy kaikki ratkaisuvaihtoehdot jollain tavalla läpi, ja löytää jonkin ratkaisun tai pystyy kertomaan ettei ratkaisuja ole.
- kekojärjestäminen
en: heapsort
Järjestämisalgoritmi, joka ensin muodostaa kekotietorakenteen alkiosta ja tämän jälkeen poistaa alkiot keosta suuruusjärjestyksessä.
- ketjutus
en: chaining
Yhteentörmäysten käsittelymenetelmä hajautustauluissa.
- kierto
en: rotation
Binäärihakupuiden paikallinen muokkausoperaatio, joka säilyttää binäärihakupuuominaisuuden.
- kokeilujono
en: probe sequence
Järjestys, jossa hajautustaulukon paikkoja tarkastellaan avoimessa osittamisessa.
- Kosarajun algoritmi
-
Lineaarisen ajan algoritmi suunnatun verkon vahvasti yhtenäisten komponenttien laskemiseksi.
- Kruskalin algoritmi
-
Ahne algoritmi pienimpien virittävien puiden laskemiseksi.
- kryptografinen hajautusfunktio
en: cryptographic hash function
Hajaustusfunktio, jolla on tiettyjä lisäominaisuuksia, joiden takia sitä voidaan käyttää tiedon salauksessa ja suojauksessa.
- käänteinen puolalainen notaatio
-
Matemaattisten kaavojen merkintätapa, jossa operaattori kirjoitetaan operandien jälkeen. Esimerkiksi lauseke \(1 + (2 * 3)\) kirjoitetaan muodossa “\(1\) \(2\) \(3\) \(*\) \(+\)”.
- laskentajärjestäminen
en: counting sort
Järjestämisalgoritmi taulukoille, joiden alkiot ovat pieniä kokonaislukuja tai helposti nähtävinä sellaisina.
- lauselogiikka
en: propositional logic
- leikkaussolmu
en: cut vertex
Suuntaamattoman verkon solmu, jonka poistaminen lisää verkon yhtenäisten komponenttien määrää.
- leveyshaku
-
Verkkojen läpikäyntialgoritmi.
- leveyssuuntainen läpikäynti
Katso: leveyshaku
- linkitetty lista
en: linked list
Kokoelmatietotyyppi. Jokainen alkio on tallennettu solmuun, ja solmu linkitetty viittauksella seuraajasolmuun (“null” listan lopussa).
- lisäysjärjestäminen
en: insertion sort
Järjestämisalgoritmi.
- lomitusjärjestäminen
en: mergesort
Järjestämisalgoritmi.
- lomitusoperaatio
en: merge operation
Operaatio, joka yhdistää kaksi järjestettyä osataulukkoa yhdeksi järjestetyksi osataulukoksi.
- lähtöaste
en: out-degree
Suunnatun verkon solmusta lähtevien kaarten lukumäärä.
- läpikäynti esijärjestyksessä
-
Juurellisten puiden solmujen läpikäyntimenetelmä. Tarkasteltu solmu käsitellään ensin ja sen jälkeen solmun lapsien alipuut rekursiivisesti yksi kerrallaan.
- läpikäynti jälkijärjestyksessä
-
Juurellisten puiden solmujen läpikäyntimenetelmä. Tarkastellun solmun lapsien alipuut käsitellään ensin rekursiivisesti yksi kerrallaan, ja tämän jälkeen lopuksi solmu itse.
- läpikäynti sisäjärjestyksessä
-
Juurellisten puiden, erityisesti binääripuiden, solmujen läpikäyntimenetelmä. Ensin käsitellään rekursiivisesti tarkastellun solmun vasemman lapsen alipuu, sitten solmu itse, ja lopuksi rekursiivisesti solmun oikean lapsen alipuu.
- läpikäynti tasojärjestyksessä
-
Juurellisten puiden solmujen läpikäyntimenetelmä. Solmut käsitellään tasoittain, eli ensi juuri, sen jälkeen juuren lapset, sitten juuren lapsien lapset jne.
- metsä
en: forest
Joukko erillisiä puita.
- muuttuvamittainen taulukko
en: resizable array
Taulukon kaltainen kokoelmatietotyyppi, joka mahdollistaa alkioiden indeksoidun hakemisen ja kirjoittamisen vakioajassa, sekä alkioiden lisäämisen taulukon loppuun kuoletetussa vakioajassa.
- NP
en: NP
Niiden päätösongelmien luokka, jotka voidaan ratkaista polynomisessa ajassa käyttämällä jotain epädeterminististä Turingin konetta.
- optimointiongelma
-
Laskennallinen ongelma, jossa on tavoitteena löytää paras mahdollinen, eli optimaalinen, ratkaisu.
- ositusalgoritmi
-
Pikajärjestämisalgoritmin apualgoritmi, joka osittaa annetun osataulukon kolmeen osaan annetun jakoalkion suhteen.
- paikallaan järjestäminen
en: in place sorting algorithm
Järjestäminen, eli järjestämisalgoritmin toiminta, jossa vain korkeintaan jokin vakiomäärä järjestettävistä alkioista on kulloisena ajanhetkenä tallennettuna järjestettävän taulukon ulkopuolelle. Määritelmästä on muitakin muunnoksia, ks. lukemisto.
- pakka
-
Kokoelmatietotyyppi. Samankaltainen kuin jono mutta sallii myös alkioiden lisäämisen alkuun ja poistamisen lopusta.
- peräytyvä hakeminen
-
Kattava hakualgoritmi, joka pyrkii löytämään ratkaisun laajentamalla kulloista osittaisratkaisua rekursiivisesti. Peräytyy edelliseen osittaisratkaisuun mikäli mikään laajennuksista ei johtanut ratkaisuun.
- pikajärjestäminen
en: quicksort
Järjestämisalgoritmi.
- pino
en: stack
Kokoelmatietotyyppi, joka sallii alkioiden lisäämisen (engl. “push”) ja poistamisen (engl. “pop”) pinon päältä. Samankaltainen kuin jono mutta käyttää LIFO-jonokuria (engl. “last in, first out”).
- polku
en: path
Sarja verkon solmuja siten että jokainen peräkkäinen solmupari on yhdistetty kaarella.
- postfix-notaatio
- Primin algoritmi
en: Prim’s algorithm
Ahne algoritmi pienimpien virittävien puiden laskemiseksi.
- prioriteettijono
en: priority queue
Kokoelmatietotyyppi, jossa alkioihin on liitetty prioriteetti. Mahdollistaa kulloisen suurimman prioriteetin alkion tehokkaan etsimisen ja poistamisen.
- pseudokoodi
en: pseudocode
Ihmisten luettavaksi tarkoitettu korkeamman abstraktiotason algoritmien kuvaustapa.
- punamusta puu
en: red-black tree
Eräs tasapainottettujen binäärihakupuiden luokka. Puun solmut on värjätty joko punaisiksi tai mustiksi tietyn tasapainotusehdon mukaisesti.
- puu
en: tree
Matemaattinen rakenne, tai tietorakenne, joka koostuu solmuista ja kaarista niiden välillä. Yhtenäinen syklitön verkko.
- päätösongelma
en: decision problem
- riippumaton joukko
en: independent set
Verkon joukko solmuja, joiden yhdenkään välillä ei ole kaarta.
- sanakirjajärjestys
en: lexicographical order
- SCC
- solmuattribuutti
en: vertex attribute
- suorahakutaulu
-
Kuvaustietorakenne avaimille, jotka ovat pienehköjä kokonaislukuja (tai voidaan helposti muuntaa sellaisiksi).
- suunnattu syklitön verkko
-
Suunnattu verkko, joka ei sisällä syklejä.
- suunnattu verkko
en: directed graph
Verkko, jonka kaaret ovat suunnattuja eli jokaisella on lähtö- ja maalisolmu.
- sykli
en: cycle
Verkon polku, joka alkaa ja päättyy samaan solmuun.
- syvyyshaku
-
Verkkojen läpikäyntialgoritmi.
- syvyyssuuntainen läpikäynti
Katso: syvyyshaku
- särmä
Katso: kaari
- taulukko
en: array
Perustietorakenne. Kiinteän mittainen sekvenssi alkioita, jotka on tallennettu peräkkäisiin muistiosoitteisiin.
- tiiviste
Katso: hajautusarvo
- topologinen järjestys
en: topological sort
Suunnatun syklittömän verkon solmujen lineaarinen järjestys, jossa verkon jokaiselle kaarelle pätee että lähtösolmu on järjestyksessä ennen maalisolmua.
- totuusjakelu
en: truth assignment
Kuvaus lauselogiikan kaavan muuttujilta Boolean arvoille “epätosi” ja “tosi”.
- tuloaste
en: in-degree
Suunnatun verkon solmuun tulevien kaarten lukumäärä.
- täyttösuhde
en: load factor, sv: belastningsfaktor
Muuttuvamittaisissa taulukoissa suhde \(\frac{s}{c}\), missä \(s\) on taulukkoon tallennettujen alkioiden määrä ja \(c\) on taulukon kapasiteetti. Hajautustauluissa suhde \(\frac{n}{m}\), missä \(n\) on hajautustauluun tallennettujen alkioden lukumäärä ja \(m\) hajaustustaulun taulukon koko.
- vahvasti yhtenäinen komponentti
en: strongly connected component
Suunnatun verkon maksimaalinen solmujen osajoukko, jonka kaikista solmuista on polku kaikkiin muihin sen solmuihin.
- vakaa järjestämisalgoritmi
-
Järjestämisalgoritmi, joka ei muuta yhtäsuurten alkioden keskinäistä järjestystä.
- valintajärjestäminen
en: selection sort
Järjestämisalgoritmi.
- verkko
en: graph
Matemaattinen rakenne, tai tietorakenne, joka koostuu solmuista ja niitä yhdistävistä kaarista.
- vieruslista
en: adjacency list
Tietorakenne verkon esittämiseksi. Siinä jokaiseen solmuun on liitetty lista sen naapureista.
- vierusmatriisi
en: adjacency matrix
Tietorakenne verkon esittämiseksi. Siinä solmujen vierekkäisyystieto on kuvattu matriisilla.
- virittävä puu
en: spanning tree
Verkon aliverkko, joka on puu ja sisältää kaikki verkon solmut.
- yhdistä ja etsi
en: union-find
- yhteentörmäys
en: collision
Kahden alkion kuvautuminen samalle hajautusarvolle.
- yhtenäinen komponentti
-
Suuntaamattoman verkon maksimaalinen solmujen osajoukko, jonka kaikista solmuista on polku kaikkiin muihin sen solmuihin.