Algoritmien laatiminen,
oikeellisuus ja vaativuus |
-
joukko-opin ja logiikan alkeet; todistamisen perustekniikat (Johdatus yliopistomatematiikkaan)
-
logaritmi- ja eksponenttifunktion perusominaisuudet; aritmeettisten ja geometristen sarjojen summa (koulumatematiikka)
|
-
ohjelmoi yksinkertaisia algoritmeja muualla matriisissa esitettyjen tietorakenteiden ja ratkaisumallien mukaan
-
määrittää yksinkertaisen algoritmin asymptoottisen aika- ja tilavaativuuden
-
tuntee O-notaation (funktioiden suuruusluokat)
|
-
tunnistaa esimerkkejä hieman vaativammista eri suunnittelumetodeja edustavista algoritmeista
-
perustelee yksinkertaisen algoritmin toiminnan invarianttien avulla
|
-
käyttää invariantteja normaalina osana ohjelmointia
-
analysoi algoritmin resurssivaatimuksia palautuskaavoilla (Algoritmien suunnittelu ja analyysi)
|
Perustietorakenteet ja
ohjelmointitaidon syventäminen |
-
käyttää taulukkoa osana normaalia ohjelmointia (Ohjelmoinnin perusteet)
-
sujuva ohjelmointitaito (Ohjelmoinnin jatkokurssi)
|
-
ohjelmoi linkitetyn listan ja sen yksinkertaisia muunnelmia Javalla
-
kirjoittaa Javalla yksinkertaisia rekursiivisia ohjelmia
-
toteuttaa prioriteettijonon kekorakenteena
|
-
käyttää pinoa, jonoa, listaa ja puurakenteita osana normaalia ohjelmointia
-
käyttää ohjelmoinnissa rekursiota tarpeen mukaan
-
tuntee Javan tarjoamia työkaluja ja ratkaisuja kurssilla esiintyvien tietorakenteiden ja algoritmien toteuttamiseen
|
-
tekee Javalla epätriviaaleja tietorakenteita sisältävän ohjelman (Tietorakenteiden harjoitustyö)
-
soveltaa tietorakenteita tehokkaasti nykyaikaisissa ohjelmointiympäristöissä mm. rinnakkaistamalla
|
|
Hakemistorakenteet |
-
tuntee taulukosta etsimisen idean ja osaa ohjelmoida binäärihaun (Ohjelmoinnin perusteet)
|
-
ohjelmoi (tasapainottoman) binäärihakupuun perus-operaatiot
-
ymmärtää hajautuksen käsitteen ja toteuttaa jonkin perusversion hajautustaulusta
|
-
ymmärtää hakupuun tasapainoisuuden käsitteen ja seuraukset ja tuntee tasapainotustapoja
-
käyttää hakemistorakenteiden aikavaativuustuloksia sopivan rakenteen valitsemiseen
-
soveltaa hajautusta ja muita hakemistorakenteita yksinkertaisten algoritmisten ongelmien ratkaisemiseen
|
-
tuntee levymuistiin soveltuvia hakemistorakenteita
-
analysoi hakemistorakenteiden tasoitettua aikavaativuutta (Algoritmien suunnittelu ja analyysi)
|
|
Järjestäminen |
-
vertailuihin perustuvan järjestämisen aikavaativuusalaraja Ω(n log n) (Johdatus yliopistomatematiikkaan)
-
toteuttaa Javalla jonkin neliöllisen järjestämisalgoritmin (Ohjelmoinnin jatkokurssi)
|
-
tuntee muutaman järjestämisalgoritmin ja ohjelmoi ainakin yhden järjestämisalgoritmin, jonka aikavaativuus on O(n log n)
|
-
tuntee keskeisten järjestämisalgoritmien aikavaativuudet ja rajoitukset
|
-
analysoi järjestämisalgoritmien aikavaativuutta myös keski-määräisessä tapauksessa (Algoritmien suunnittelu ja analyysi)
|
|
Verkot |
-
tuntee verkkojen perusmääritelmät (Johdatus yliopistomatematiikkaan)
|
-
ohjelmoi verkon leveyssuuntaisen ja syvyyssuuntaisen läpikäynnin
-
selittää (kuvin, sanoin, esimerkein) lyhimpien polkujen ja pienimpien virittävien puiden perusalgoritmien toiminnan
|
-
soveltaa verkon läpikäyntejä, polunetsintää ja virittäviä puita erilaisten verkko-ongelmien ratkaisemiseksi
-
perustelee lyhimpien polkujen ja pienimpien virittävien puiden perusalgoritmien oikeellisuuden ja aikavaativuuden
|
-
ratkaisee optimointiongelmia verkkovuoalgoritmeja soveltaen (Diskreetti optimointi)
-
tunnistaa useita NP-täydellisiä verkko-ongelmia ja osaa selittää NP-täydellisyyden merkityksen (Algoritmien suunnittelu ja analyysi)
|
Tulostettava sivu