Glossary

Week01 - Glossary

English

algorithm

A sequence of unambiguous instructions for obtaining, in a finite amount of time, a required output when given any legitimate input. (Suomeksi: algoritmi)

pseudocode (suom pseudokoodi)

A written description of a sequence of steps presented using ordinary language and mathematical notation, but including many of the features of normal programming languages. For example pseudocode typically includes for-loops, if-then-else blocks, variables and procedures/functions. Pseudocode is meant to be read by a human.

input (suom syöte)

The information or data that is provided to an algorithm before the algorithm is executed. In C++ an input to an algorithm or function is usually called a parameter.

decrease and conquer (suom pala kerrallaan)

An algorithm design strategy typically comprised of multiple iterations. In each iteration the algorithm processes one part of the entire problem completely, after which the algorithm proceeds to process the remaining unhandled part. (Sometimes the decrease and conquer strategy is called the incremental strategy.)

insertion sort (suom lisäysjärjestäminen)

A decrease and conquer algorithm typically used to sort an array of elements according to some well-defined ordering rule. For example, for numbers one such rule is that a number x precedes a number y, when x is less than or equal to y.

Viikko01 - Sanasto

Suomeksi

algoritmi (engl algorithm)

Sarja yksiselitteisiä ohjeita vaaditun tuloksen saamiseksi rajallisessa ajassa, kun annetut lähtötiedot ovat kelvollisia.

pseudokoodi (engl pseudocode)

Kirjallinen kuvaus ohjeiden sarjasta, joka on esitetty käyttäen tavallista kieltä ja matemaattista merkintätapaa, mutta joka sisältää monia normaalien ohjelmointikielien ominaisuuksia. Esimerkiksi pseudokoodi voi sisältää for-silmukkoita, if-then-else lohkoja, muuttujia ja proseduureja. Pseudokoodi on tarkoitettu ihmisen luettavaksi.

syöte (engl input)

Tiedot, jotka toimitetaan algoritmille ennen algoritmin suorittamista. Ohjelmointikielen C++:n algoritmin tai funktion syötettä kutsutaan yleensä parametriksi.

pala kerrallaan (engl decrease and conquer )

Algoritmin suunnittelustrategia, joka koostuu tyypillisesti useista iteraatioista. Jokaisessa iteraatiossa algoritmi käsittelee kokonaan yhden osan koko ongelmasta, minkä jälkeen algoritmi jatkaa jäljellä olevan käsittelemättömän osan käsittelyä.

lisäysjärjestäminen (engl insertion sort)

Pala kerrallaan strategialla toimiva järjestämisalgoritmi, jota käytetään tyypillisesti taulukon alkioiden lajitteluun jonkin hyvin määritellyn järjestyssäännön mukaan. Esimerkiksi luvuille yksi tällainen sääntö on, että luku x edeltää lukua y, kun x on pienempi tai yhtä suuri kuin y.

Week02 - Glossary

English

algorithm efficiency (suom algoritmin tehokkuus)

Informally, an algoritm’s efficiency is the amount of time an algorithm takes to complete its computations for a given input. More formally, an algorithm’s efficiency is the depedence of the number of operations an algorithm must perform on the size of the input to the algorithm.

asymptotic efficiency (suom asymptoottinen tehokkuus)

The behavior of a function when its independent variable becomes very large (or very small) is the function’s asymptotic behavior. For an algorithm, its asymptotic efficiency is how the number of operations behaves as the size of input becomes very large.

simple operation (suom askel tai yksikertainen operaatio)

A computation in an algorithm whose execution does not depend on the input size.

value semantics and reference semantics (suom arvosemantiikka ja viitesemantiikka)

In a computer language which uses value semantics, an ordinary variable is equivalent to the data in some particular memory location. In a computer language which uses reference semantics, an ordinary variable points to a memory location, which holds some data.

iterator (suom iteraattori)

An object that points to some particular location in a container. An iterator is typically used to traverse through some or all of the locations in a container.

recursive algorithm or procedure (suom rekursiivinen algoritmi tai funktio)

A procedure or algorithm which calls itself. A recursive procedure must contain at least one base (or trivial) case and at least one recursion case.

base case (suom triviaali tapaus)

A case in a recursive algorithm, where the algorithm does not call itself. It is sometimes called a trivial case.

recursive case (suom rekursiivinen tapaus)

A case in a recursive algorithm where the algorithm calls itself.

call stack (suom kutsupino)

In a recursive algorithm the stack of calls to the algorithm that are not yet completed. The most recent call is on the top of the stack. Usually there is no explicit variable containing the call stack.

Viikko02 - Sanasto

Suomeksi

algoritmin tehokkuus (engl algorithm efficiency)

Puhekielessä algoritmin tehokkuus on aika, joka algoritmilla kestää tietyn syötteen laskelmien suorittamiseen. Tarkemmin sanottuna algoritmin tehokkuus on miten algorithmin suoritettavien operaatioiden lukumäärä riippuu syötteen koosta.

asymptoottinen tehokkuus (engl asymptotic efficiency)

Funktion käyttäytyminen, kun sen itsenäinen muuttuja muuttuu hyvin suureksi (tai hyvin pieneksi), on funktion asymptoottinen käyttäytyminen. Algoritmin asymptoottinen tehokkuus on se, miten operaatioiden määrä käyttäytyy, kun syötteen koko kasvaa hyvin suureksi.

askel tai yksikertainen operaatio (engl simple operation)

Lasku algoritmissa, jonka suoritus ei riipu syötteen koosta.

arvosemantiikka ja viitesemantiikka (engl value semantics and reference semantics)

Tietokoneen kielellä, joka käyttää arvosemantiikkaa, tavallinen muuttuja vastaa jonkin tietyn muistisijainnin tietoja. Tietokoneen kielellä, joka käyttää viitesemantiikkaa, tavallinen muuttuja osoittaa muistin sijaintiin, jossa on joitain dataa.

iteraattori (engl iterator)

Olio, joka osoittaa johonkin tiettyyn paikkaan säilössä. Iteraattoria käytetään tyypillisesti kulkemaan joidenkin tai kaikkien säiliön paikkojen läpi.

rekursiivinen algoritmi tai funktio (engl recursive algorithm or procedure)

Algoritmi tai funktio, joka kutsuu itseään. Rekursiivisen algoritmin on sisällettävä vähintään yksi triviaalitapaus ja vähintään yksi rekursiotapaus.

triviaali tapaus (engl base case)

Tapaus rekursiivisessa algoritmissa, jossa algoritmi ei kutsu itseään.

rekursiivinen tapaus (engl recursive case)

Tapaus rekursiivisessa algoritmissa, jossa algoritmi kutsuu itseään.

kutsupino (suom call stack)

Rekursiivisessa algoritmissa pino kutsuja algoritmiin, jotka eivät ole vielä valmiita. Viimeisin kutsu on pinon päällimäisin. Yleensä ei ole olemassa muuttujaa, joka sisältää kutsupinon.

Week03 - Glossary

English

divide and conquer (suom hajoita ja hallitse)

Divide and conquer is an algorithm design strategy. In an algorithm using this strategy a problem is broken up into subproblems. This division into subproblems continues until the subproblems are simple enough to solve without having to divide them further. The solutions to subproblems are combined to obtain the solution to the original problem.

merge sort (suom lomitusjärjestäminen)

Merge sort is an algorithm for sorting elements in a list (or array) using a divide and conquer strategy. The list containing the elements is divided into sublists, each containing one element. These one element sublists are merged into larger sorted sublists, which are in turn merged into still larger sublists. The merging operations terminate when the last two sublists merged form the entire sorted list.

merging (suom lomittaminen)

Merging is the process in which two (or more) sorted lists (or arrays) are combined into one sorted list (or array).

quick sort (suom pikajärjestäminen)

Quick sort is an algorithm for sorting elements in an array using a divide and conquer strategy. The array containing the elements is partitioned into two subarrays using a pivot selected from the original array. One subarray contains elements that are less than (or equal to) the pivot, the other subarray contains elements that are greater than (or equal to) the pivot. These two subarray are then recursively handled.

partitioning (suom osittaminen)

The process of dividing a list (or array or set) into two or more sublists.

Viikko03 - Sanasto

Suomeksi

hajoita ja hallitse (engl divide and conquer)

Hajota ja hallitse on suunnittelustrategia algoritmille. Algoritmissa, joka käyttää tätä strategiaa ongelma jaetaan osaongelmiin. Jakaminen osaongelmiin jatkuu kunnes osaongelmat ovat riittävän yksinkertaisia ratkaistaviksi ilman, että niitä tarvitsee jakaa pienempiin osaongelmiin. Yhdistämällä osaongelmien ratkaisut saadaan alkuperäisen ongelman ratkaisu.

lomitusjärjestäminen(engl merge sort)

Lomitusjärjestäminen on algoritmi listan (tai taulukon) alkioiden lajitteluun, joka toimii hajoita ja hallitse -strategian avulla. Alkuperäinen lista jaetaan pieniin osalistoihin, jotka sisältää yhden alkion. Nämä yhden alkioiden osalistat lomitetaan suurempiin lajiteltuihin osalistoihin, jotka puolestaan lomitetaan vielä suuremmiksi osalistoiksi. Lomittamistoiminnot päättyvät, kun kaksi viimeistä osalistaa lomitetaan koko lajitelluun listaan.

lomittaminen (engl merging)

Lomittaminen on operaatio, jossa kaksi (tai useampia) lajiteltuja listoja (tai taulukoita) yhdistetään yhdeksi lajitelluksi listaksi (tai taulukoksi).

pikajärjestäminen (engl quick sort)

Pikajärjestäminen on algoritmi taulukon alkioiden lajitteluun, joka käyttää hajoita ja hallitse -strategiaa. Taulukko ositetaan kahteen osataulukkoon käyttämällä alkuperäisestä taulukosta yhtä alkiota vertailualkioksi ns pivotiksi. Yksi osataulukko sisältää alkiot, jotka ovat pienempiä (tai yhtä suuria kuin) pivot, toinen osataulukko sisältää alkiot, jotka ovat suurempia (tai yhtä suuria) kuin pivot. Näitä kahta osataulukkoa käsitellään sitten rekursiivisesti.

osittaminen (engl partitioning)

Prosessi, jossa taulukko (tai lista tai joukko) jaetaan kahteen tai useampaan osataulukkoon.

Week04 - Glossary

English

big-O notation (suom iso-O-notaatio)

When we say that a function \(f(n)\) belongs to \(O(g(n))\), we mean that for sufficiently large \(n\), \(f(n)\) will always be less than the product \(cg(n)\), where \(c\) is some constant. We can say that the product \(cg(n)\) is an asymptotic upper bound for \(f(n)\).

big-Omega notation (suom iso-Omega-notaatio)

When we say that a function \(f(n)\) belongs to \(Omega(g(n))\), we mean that for sufficiently large \(n\), \(f(n)\) will always be greater than the product \(dg(n)\), where \(d\) is some constant. We can say that the product \(dg(n)\) is an asymptotic lower bound for \(f(n)\).

big-Theta notation (suom iso-Theta-notaatio)

When we say that a function \(f(n)\) belongs to \(\Theta(g(n))\), we mean that \(f(n)\) belongs to \(O(g(n))\) and \(f(n)\) belongs to \(\Omega(g(n))\). We can say that some product \(cg(n)\) is an asymptotic upper bound for \(f(n)\) and some other product \(dg(n)\) is an asymptotic lower bound for \(f(n)\).

best case input (suom parhaan tapauksen syöte)

For some algorithm a best case input is one for which the algorithm’s efficiency attains the slowest growth it can possibly attain as the input size increases.

worst case input (suom pahimman tapauksen syöte)

For some algorithm a worst case input is one for which the algorithm’s efficiency attains the fastest growth it can possibly attain as the input size increases.

Viikko04 - Sanasto

Suomeksi

iso-O-notaatio (engl big-O notation)

Sanomalla, että funktio \(f(n)\) kuuluu luokkaan \(O(g(n))\), tarkoitetaan että, kun \(n\) kasvaa riittävän suureksi funktio \(f(n)\) on aina pienempi kuin tulo \(cg(n)\), jossa \(c\) on jokin vakio. Voidaan sanoa, että tulo \(cg(n)\) on asymptoottinen yläraja funktiolle \(f(n)\).

iso-Omega-notaatio (engl big-Omega notation)

Sanomalla, että funktio \(f(n)\) kuuluu luokkaan \(\Omega(g(n))\), tarkoitetaan että, kun \(n\) kasvaa riittävän suureksi funktio \(f(n)\) on aina suurempi kuin tulo \(dg(n)\), jossa \(d\) on jokin vakio. Voidaan sanoa, että tulo \(dg(n)\) on asymptoottinen alaraja funktiolle \(f(n)\).

iso-Theta-notaatio (engl big-Theta notation)

Sanomalla, että funktio \(f(n)\) kuuluu luokkaan \(\Theta(g(n))\), tarkoitetaan, että \(f(n)\) kuuluu luokkaan \(O(g(n))\) ja \(f(n)\) kuuluu luokkaan \(\Omega(g(n))\). Voidaan sanoa, että jokin tulo \(cg(n)\) on asymptoottinen yläraja funktiolle \(f(n)\) ja jokin toinen tulo \(dg(n)\) on asymptoottinen alaraja funktiolle \(f(n)\).

parhaan tapauksen syöte (suom best case input)

Joillekin algoritmeille parhaan tapauksen syöte on sellainen, jolle algoritmin tehokkuus saavuttaa hitaimman mahdollisen kasvun syötekoon kasvaessa.

pahimman tapauksen syöte(suom worst case input)

Joillekin algoritmeille pahimman tapauksen syöte on sellainen, jolle algoritmin tehokkuus saavuttaa nopeimman mahdollisen kasvun syötekoon kasvaessa.

Week05 - Glossary

English

STL (suom STL)

The Standard Template Library (STL) is a collection of data structures and associated algorithms for C++.

STL containers (suom STL:n säiliöt)

The Standard Template Library (STL) includes many different data structures that collectively are referred to as containers.

STL sequences (suom STL:n sarjat)

The STL sequences are containers whose element order can be set by the programmer. The names of the sequence containers are as follows: array, vector, deque, forward_list and list.

STL associative containers (suom STL:n assosiatiiviset säiliöt)

The STL includes a number of containers whose elements can be accessed using keys. The associative containers can be divided into two groups: ordered and unordered. The names of the ordered associative containers are as follows: set, map, multiset and multimap. The names of the unordered associative containers are as follows: unordered_set, unordered_map, unordered_multiset and unordered_multimap.

STL container adaptors (suom STL:n säiliösovittimet)

The STL includes data structures that are collectively called adaptors. The names of the adaptors are as follows: stack, queue and priority_queue.

iterator categories (suom iteraattorikategoriat)

The STL includes several different categories (or types) of iterators. What distinguishes one category from another are the operations that can be done on an iterator. The most often used categories, in order starting from the most restrictive, are as follows: forward, bidirectional and random access. There are two other categories that are rarely used: input and output.

STL generic algorithm (suom geneeriset algoritmit)

The STL contains includes many functions for performing typical operations on data structures: searching, sorting, counting and so on. Collectively these functions are called algorithms.

Viikko05 - Sanasto

Suomeksi

STL (engl STL)

STL on kokoelma tietorakenteita ja niihin liittyviä algoritmeja C++:lle.

STL:n säiliöt (engl STL containers)

STL sisältää monia erilaisia tietorakenteita, joita kutsutaan yhdessä säiliöiksi.

STL:n sarjat (engl STL sequences)

STL-sarjat ovat säiliöitä, joiden alkioiden järjestyksen ohjelmoija voi itse päättää. Sarjasäilöiden nimet ovat seuraavat: array, vector, deque, forward_list and list.

STL:n assosiatiiviset säiliöt (engl STL associative containers)

STL sisältää useita säiliöitä, joiden alkioihin pääsee käsiksi avaimilla. Assosiatiiviset säiliöt voidaan jakaa kahteen ryhmään: järjestetyt ja järjestämätömmät. Järjestetyjen assosiatiivisten säiliöden nimet ovat set, map, multiset ja multimap. Järjestämättömien assosiatiivisten säiliöden nimet ovat unordered_set, unordered_map, unordered_multiset ja unordered_multimap.

STL container adaptors (STL:n säiliösovittimet)

STL sisältää tietorakenteet, joita kutsutaan yhdessä säiliösovittimiksi. Sovittimien nimet ovat stack, queue ja priority_queue.

iteraattorikategoriat (engl iterator categories)

STL sisältää useita eri iteraattoreiden kategoriat (tai luokkia). Se, mikä erottaa yhden kategorian toisesta, ovat operaatiot, jotka voidaan tehdä iteraattorilla. Useimmin käytetyt kategoriat, järjestyksessä alkaen rajoittavimmasta, ovat seuraavat: forward, bidirectional ja random access. On olemassa kaksi muuta kategoriaa, joita käytetään harvoin: input ja output.

STL:n geneeriset algoritmit (engl STL generic algorithm)

STL sisältää monia funktioita tyypillisten toimintojen suorittamiseen tietorakenteilla: haku, lajittelu, laskenta ja niin edelleen. Yhdessä näitä funktioita kutsutaan algorithms:iksi.

Week06 - Glossary

English

lambda function (suom lambda-funktio)

An unnamed function typically passed as an parameter to another function.

capturing variables (suom muuttujien kaapaaminen)

A captured variable is one that is fed to a lambda function, but not as as a parameter. Typically the situation is the following: a lambda function X is passed a parameter to some other function Y which occurs inside a third function Z. Inside Z some variable V occurs which is needed inside the lambda function X. In such a situation we need to feed V as a captured variable to X.

Viikko06 - Sanasto

Suomeksi

lambda-funktio (engl lambda function)

Nimeämätön funktio, joka yleensä välitetään parametrina toiseen funktioon.

muuttujien kaapaaminen (engl capturing variables)

Kaapattu muuttuja on sellainen, joka syötetään lambda-funktioon, mutta ei parametrina. Tyypillisesti tilanne on seuraava: lambda-funktio X välitetään parametrina jollekin muulle funktiolle Y, joka esiintyy kolmannen funktion Z sisällä. Funktiossa Z esiintyy muuttuja V, joka halutaan välittää lambda-funktioon X. Tällaisessa tilanteessa meidän täytyy välittää V kaapatuna muuttujana lambda-funktioon X.

Week07 - Glossary

English

node or vertex (suom solmu tai piste)

A node is an element in a graph or tree to which one or mores edges may be attached.

edge or arc (suom kaari tai linkki)

In a graph or tree there is an edge between two nodes when there is some relationship or connection between the two nodes.

rooted tree (suom juurrellinen puu)

A rooted tree has one particular node called the root. A rooted tree has the following properties: (i) there is precisely one path from the root to any other node in the tree and (ii) there is no path from any node to the root. These two properties imply that all edges in a rooted tree are directed away from the root.

parent and child (engl vanhempi ja lapsi)

In a rooted tree when there is an edge from node \(x\) to node \(y\), then \(x\) is \(y\)’s parent and \(y\) is \(x\)’s child.

subtree (engl alipuu)

Let \(x\) be a node in a rooted tree and \(y\) be \(x\)’s child. The subtree of \(x\) rooted at \(y\) consists of all nodes to which there exists a path from \(y\) along with all the edges included in these paths.

leaf (suom lehti)

In a rooted tree, a node with no children is called a leaf.

tree height (suom puun korkeus)

In a rooted tree, the number of edges in the path from the root to the leaf that is farthest from the root is the tree height.

binary tree (engl binääripuu)

A rooted tree in which each node can have at most 2 children. These children are referred to as the left child and the right child.

preorder traversal (suom esijärjestyksen läpikäynti)

In a preorder traversal of a rooted tree we visit each node of the tree exactly once in the following order. Staring at the root, we first visit a node itself and then we recursively traverse each subtree of the node.

postorder traversal (suom jälkijärjestyksen läpikäynti)

In a postorder traversal of a rooted tree we visit each node of the tree exactly once in the following order. Staring at the root, we first recursively traverse all the subtrees of a node, before finally visiting the node itself.

inorder traversal (suom välijärjestyksen läpikäynti)

In an inorder traversal of a binary tree we visit each node of the binary tree exactly once in the following order. Staring at the root, we first recursively traverse the left subtree of the node, then we visit the node itself and finally we recursively traverse the right subtree of the node.

iterator invalidation (suom iteraattori mitätöityminen)

In C++ iterator invalidation occurs when an iterator to some location in a container no longer works properly. A simple example of this is when the location to which the iterator was refering has been erased or deleted. Pointer invalidation and index invalidation can be defined in a similar way.

Viikko07 - Sanasto

Suomeksi

solmu tai piste (engl node or vertex)

Solmu on graafin tai puun alkio, johon voidaan kiinnittää yksi tai useampi kaari.

kaari tai linkki (engl edge or arc)

Graafissa tai puussa on kaari kahden solmun välillä, kun näiden kahden solmun välillä on jonkinlainen suhde tai yhteys.

juurrellinen puu (engl rooted tree)

Juurrellisessa puussa on yksi tietty solmu, jota kutsutaan juureksi. Juurrellisella puulla on seuraavat ominaisuudet: (i) juuresta on täsmälleen yksi polku mihin tahansa muuhun puun solmuun ja (ii) mistään solmusta juureen ei ole polkua. Seurauas näistä kahdesta ominaisuudesta on, että kaikki juurrellinsen puun kaaret on suunnattu poispäin juuresta.

vanhempi ja lapsi (engl parent and child)

Kun juurrellisessa puussa on olemassa kaari solmusta \(x\) solmuun \(y\), niin \(x\) on \(y\): vanhempi ja \(y\) on \(x\):n lapsi.

alipuu (engl subtree)

Olkoon \(x\) solmu juurrellisessa puussa ja olkoon solmu \(y\) solmun \(x\) lapsi. Solmun \(x\) alipuu, jonka juuri on \(y\), koostuu kaikista solmuista, joihin pääsee solmusta \(y\) jollakin polulla ja myös kaikki näihin polkuihin sisältyvät kaaret.

lehti (engl leaf)

Juurellisen puun solmua, jolla ei ole lapsia, kutsutaan lehdeksi.

puun korkeus (engl tree height)

Juurrellisessa puussa polun kaarien lukumäärä juuresta lehteen, joka on kauimpana juuresta, on puun korkeus.

binääripuu (engl binary tree)

Juurrellista puuta, jossa jokaisella solmulla on korkeintaan kaksi lasta, kutsutaan binääripuuksi. Näitä lapsia kutsutaan vasemmaksi lapseksi ja oikeaksi lapseksi.

esijärjestyksen läpikäynti (engl preorder traversal)

Juurrellisen puun esijärjestyksessä läpikäynnissä käydään puun jokaisessa solmussa täsmälleen kerran seuraavassa järjestyksessä. Juuresta lähtien käydään ensin itse solmussa ja sitten läpikäydään rekursiivisesti solmun jokainen alipuu.

jälkijärjestyksen läpikäynti (engl postorder traversal)

Juurrellisen puun jälkijärjestyksessä läpikäynnissä käydään puun jokaisessa solmussa täsmälleen kerran seuraavassa järjestyksessä. Juuresta lähtien ensin läpikäydään ensin solmun jokainen alipuu ja sitten käydään itse solmussa.

välijärjestyksen läpikäynti (engl inorder traversal)

Binääripuun välijärjestyksessä läpikäynnissä käydään binääripuun jokaisessa solmussa täsmälleen kerran seuraavassa järjestyksessä. Juuresta lähtien läpikäydään ensin rekursiivisesti solmun vasen alipuu ja sitten käydään itse solmussa ja lopuksi läpikäydään rekursiivisesti solmun oikea alipuu.

iteraattori mitätöityminen (engl iterator invalidation)

C++-ohjelmointikielessä iteraattorin mitätöityminen tapahtuu, kun iteraattori johonkin säilön sijaintiin ei enää toimi oikein. Yksinkertainen esimerkki tästä on, kun sijainti, johon iteraattori viittasi, on poistettu. Osoittimen mitätöityminen ja indeksin mitätöityminen voidaan määrittää samalla tavalla.

Week08 - Glossary

English

amortized efficiency (suom amortisoitua tehokkuus)

An amortized efficiency is an average of runtime efficiencies for a given sequence of operations.

verifying asymptotic efficiency (suom asymptoottisen tehokkuuden testaaminen)

The methods that one can use to try to measure how the execution of an algorithm depends on the size of the input data. One common method is to measure how the actual time (say in seconds) of the algorithm changes as the size of the input data changes. Another common method is to count the number of machine operations of algorithm and record how this count changes as the size of the input data changes.

randomization (suom satunnaistaminen)

An algorithm strategy in which some part of the algorithm operates randomly. In such algorithms a random number generator is needed. Typically randomization is used to try to improve an algorithm’s average efficiency.

Viikko08 - Sanasto

Suomeksi

amortisoitua tehokkuus (engl amortized efficiency)

Amortisoitua tehokkuus on tietyn operaatiosarjan keskimääräinen tehokkuus.

asymptoottisen tehokkuuden testaaminen (suom verifying asymptotic efficiency)

Menetelmät, joilla voidaan yrittää mitata, miten algoritmin suorittaminen riippuu syötteen koosta. Yksi yleinen menetelmä on mitata, miten algoritmin todellinen laskenta-aika (esimerkiksi sekunteina) muuttuu syötteen koon muuttuessa. Toinen yleinen menetelmä on laskea algoritmin koneen operaatioden toimintojen lukumäärä ja tallentaa, miten tämä lukumäärä muuttuu syötteen koon muuttuessa.

satunnaistaminen (engl randomization)

Strategia, jossa jokin algoritmin osa toimii satunnaisesti. Tällaisissa algoritmeissa tarvitaan satunnaislukugeneraattori. Tyypillisesti satunnaistamista käytetään yrittämään parantaa algoritmin keskimääräistä tehokkuutta.

Week09 - Glossary

English

heap (suom keko)

A heap is a tree based data structure, in which the tree height is as small as possible. Typically a binary tree is used for implementing a heap. In a max-heap the key of a node is at least as large as the key of any of its children. In a min-heap the key of a node is at most as large as the key of any of its children.

priority queue (suom prioriteettijono)

A data structure in which each element has associated with it a priority, which is usually a number. Usually one requirement is that it should be possible to access the element with the largest priority (or smallest priority) quickly.

Viikko09 - Sanasto

Suomeksi

keko (engl heap)

Keko on tietorakenne, joka perustuu puuhun, jonka korkeus on mahdollisimman pieni. Tyypillisesti binääripuuta käytetään keon toteuttamiseen. Max-keossa (engl max-heap) solmun avain (tai arvo) on vähintään yhtä suuri kuin minkä tahansa sen lapsen avain (tai arvo). Min-keossa (engl min-heap) solmun avain on korkeintaan yhtä suuri kuin minkä tahansa sen lapsen avain.

prioriteettijono (engl priority queue)

Prioriteettijono on tietorakenne, jossa jokaiseen alkioon liittyy prioriteetti. Tavallisesti prioriteetti on luku. Yleensä yksi vaatimus on, että suurimman prioriteetin (tai pienimmän prioriteetin) alkioon pitäisi olla mahdollista päästä nopeasti.

Week10 - Glossary

English

graph (suom graafi)

An object defined by two sets: a set of nodes and a set of edges (or arcs). An edge is a defined by a pair of nodes \((x,y)\), where in fact \(x=y\) is allowed. If the graph is undirected, the order of the nodes in the pair \((x,y)\) is of no significance. If the graph is directed, then the order of the nodes in the pair \((x,y)\) is significant.

path (suom reitti, polku)

An ordered sequence of one or more edges in a graph. In a path, if edge \((a,b)\) comes immediately before edge \((c,d)\), then \(b=c\) is necessary.

connected graph (suom yhtenäinen graafi, kytetty graph)

In a connected graph a path exists between any two different nodes \(x\) and \(y\).

cycle (suom silmukka)

A cycle is a path where the first and last nodes are the same. Often in an undirected graph, a nontrivial cycle must have at least 3 different edges.

distance (suom etäisyys)

The distance between two nodes \(x\) and \(y\) is the number of edges in the path from \(x\) to \(y\) containing the smallest number of edges.

Viikko10 - Sanasto

Suomeksi

graafi (engl graph)

Graafi määritellään kahdella joukolla: solmujen joukko ja kaarien joukko. Kaari on solmupari \((x,y)\), jossa itse asiassa \(x=y\) on sallittu. Jos graafi on suuntamaton, parin \((x,y)\) solmujen järjestyksellä ei ole merkitystä. Jos graafi on suunnattu, parin \((x,y)\) solmujen järjestys on merkittävä.

reitti, polku (engl path)

Reitti on yhden tai useamman kaaren järjestetty sarja graafissa. Jos kaari \((a,b)\) tulee välittömästi ennen kaarta \((c,d)\), niin vaaditaan, että \(b=c\).

yhtenäinen (tai kytetty) graafi (engl connected graph)

Yhtenäisessä graafissa on olemassa reitti minkä tahansa kahden eri solmun välillä.

silmukka (engl cycle)

Silmukka on reitti, jossa ensimmäinen ja viimeinen solmu ovat samat. Usein suuntamattomassa graafissa ei-triviaalissa silmukalla on oltava vähintään 3 eri kaarta.

etäisyys (engl distance)

Kahden solmun \(x\) ja \(y\) välinen etäisyys on kaarien lukumäärä reitillä solmusta \(x\) solmuun \(y\), joka sisältää pienimmän määrän kaaria.

Week11 - Glossary

English

weighted graph (suom painotettu graafi)

A graph in which each edge has associated with it a number called a weight.

Viikko11 - Sanasto

Suomeksi

painotettu graafi (engl weighted graph)

Graafi, jossa jokaiseen kaareen liittyy luku, jota kutsutaan painoksi.

Week12 - Glossary

English

hash table (suom hajautustaulu)

A data structure in which records or elements are stored in buckets or slots. Each record has associated with it a unique key. When the key is input into the hash function, the hash function computes the location of the bucket in which the record should be stored.

bucket or slot (suom ämpäri)

One location in a hash table in which records can be stored.

open hashing or chained hashing (suom ketjutettu hajautus)

When the hash function maps two or more keys to the same bucket, a collision occurs. In open hashing a linked list is associated with each bucket. The records are not stored directly in the buckets, but rather in the elements of the linked list. When a collision occurs, a new element is added to the linked list and the new record is stored in the new element of the linked list.

closed hashing (suom suljettu hajautus)

When the hash function maps two or more keys to the same bucket, a collision occurs. In closed hashing, the records are stored directly in the buckets. When a collision occurs, in closed hashing a search is done to find an empty bucket in which to store the new record.

load factor (suom täyttöaste)

The total number of records stored in a hash table divided by the total number of buckets.

rehashing (suom uudelleenhajautus)

When the load factor exceeds some acceptable limit, a rehashing occurs. In a rehashing, the number of buckets is increased and all the records that are in the hash table are re-inserted.

Viikko12 - Sanasto

Suomeksi

hajautustaulu (engl hash table )

Tietorakenne, jossa tietueet tai alkiot tallennetaan ämpäriiin. Jokaiseen tietueeseen on liitetty yksikäsitteinen hakuavain. Kun hakuavain syötetään hajautusfunktioon, hajautusfunktio laskee sen ämpärin sijainnin, johon tietue tulisi tallentaa.

ämpäri (engl bucket or slot)

Yksi hajautustaulun paikka, johon tietueita voidaan tallentaa.

ketjutettu hajautus (engl open hashing or chained hashing)

Kun hajautusfunktio osoittaa kaksi tai useampia hakuavaimia samaan ämpäriin, tapahtuu törmäys. Ketjutetussa hajautuksessa linkitetty lista liitetään jokaiseen ämpäriiin. Tietueita ei tallenneta suoraan ämpäreihin, vaan linkitetyn listan alkioihin. Kun törmäys tapahtuu, uusi alkio lisätään linkitettyyn listaan ja uusi tietue tallennetaan linkitetyn listan uuteen alkioon.

suljettu hajautus (engl closed hashing)

Kun hajautusfunktio osoittaa kaksi tai useampia hakuavaimia samaan ämpäriin, tapahtuu törmäys. Suljetussa hajautuksessa tietueet tallennetaan suoraan ämpäreihin. Kun törmäys tapahtuu, suljetussa hajautuksessa, etsitään tyhjä ämpäri, johon uusi tietue tallennetaan.

täyttöaste (suom load factor)

Hajautustauluun tallennettujen tietueiden kokonaismäärä jaettuna ämpäreiden kokonaismäärä.

uudelleenhajautus (engl rehashing)

Kun täyttöaste ylittää jonkin hyväksyttävän rajan, tapahtuu uudelleenhajautus. Uudelleenhajautuksessa ämpäreiden määrää lisätään ja kaikki tietueet jotka ovat hajautustaulussa, lisätään siihen uudelleen.

Week13 - Glossary

English

binary search tree (suom binäärihakupuu)

In a binary search tree each node has associated with it a key (or value). Assuming all the keys are unique, then a binary search tree has the following two properties for any node \(x\): (i) all the keys in the left subtree of \(x\) are less than the key of \(x`and (ii) all the keys in the right subtree of :math:`x\) are greater than the key of \(x\).

balanced binary search tree (suom tasapainotettu binäärihakupuu)

Roughly speaking, a binary search tree is balanced when the heights of the left and right subtrees of any node are almost equal. More precisely a balanced binary search tree provides some upper bound on the following ratio: the height of the tree relative to the height of a binary search tree having minimal height.

AVL binary search tree (suom AVL-binäärihakupuu)

A balanced binary search tree which has the property that the heights of the two subtrees of any node differ by at most one.

red-black binary search tree (suom punamusta binäärihakupuu)

A balanced binary search tree in which each node is colored either red or black. A red-black tree remains balanced when nodes are added or deleted by maintaining certain properties pertaining to the colors of the nodes.

Viikko13 - Sanasto

Suomeksi

binäärihakupuu (engl binary search tree)

Binäärihakuussa jokaiseen solmuun liittyy hakuavain (tai arvo). Olettaen, että kaikki hakuavaimet ovat yksikäsitteisiä, binaarihakupuulla on seuraavat kaksi ominaisuutta mille tahansa solmulle \(x\): (i) jokainen solmun \(x\) vasemmassa alipuussa oleva hakuavain on pienempi kuin solmun \(x\) hakuavain ja (ii) jokainen solmun \(x\) oikeassa alipuussa oleva hakuavain on suurempi kuin solmun \(x\) hakuavain.

tasapainotettu binäärihakupuu (engl balanced binary search tree)

Karkeasti ottaen binäärihakupuu on tasapainotettu, kun minkä tahansa solmun vasemman ja oikean alipuun korkeudet ovat lähes yhtä suuret. Tarkemmin sanottuna tasapainotetulla binäärihakupuulla on yläraja seuraavalle suhteelle: binäärihakupuun korkeus suhteessa minimaaliseen korkeuteen.

AVL-binäärihakupuu (engl AVL binary search tree )

Tasapainotettu binäärihakupuu, jolle pätee seuraava ominaisuus mille tahansa solmulle: solmun vasemman alipuun ja oikean alipuun korkeudet eroavat toisistaan korkeintaan yhdellä.

punamusta binäärihakupuu (engl red-black binary search tree)

Tasapainotettu binäärihakupuu, jossa jokaiselle solmulle määritetään joko punainen tai musta väri. Punamusta puu pysyy tasapainossa, kun solmuja lisätään tai poistetaan ylläpitämällä tiettyjä solmujen väreihin liittyviä ominaisuuksia.

Palautusta lähetetään...