Algoritmien laatiminen,
oikeellisuus ja vaativuus |
- joukko-opin ja logiikan alkeet; todistamisen perustekniikat (Johdatus diskreettiin matematiikkaan)
- 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 |
- kuvailee linkitetyn rakenteen toteutuksen koneen muistissa (Java-ohjelmointi)
|
- 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 toteuttamiseen
|
- tekee Javalla epätriviaaleja tietorakenteita sisältävän ohjelman (Tietorakenteiden harjoitustyö)
|
| Hakemistorakenteet |
- kuvailee linkitetyn rakenteen toteutuksen koneen muistissa (Ohjelmoinnin jatkokurssi)
|
- 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 (Tietokantasovellusu)
- analysoi hakemistorakenteiden tasoitettua aikavaativuutta (Algoritmien suunnittelu ja analyysi)
|
| Järjestäminen |
- vertailuihin perustuvan järjestämisen aikavaativuusalaraja Ω(n log n) (Johdatus diskreettiin matematiikkaan)
- 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 diskreettiin matematiikkaan)
|
- 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