Tietorakenteet ja algoritmit 2
TiteWiki
Sisällysluettelo |
Kurssin perustiedot
- Nimi: Tietorakenteet ja algoritmit 2
- Koodi: KTE1330
- Aika: 07.01.2008 - 02.05.2008
- Suoritus: pakollinen
- Luokittelu: suuntautumisvaihtoehdon ammattiopinnot, ohjelmistotekniikan suuntautumisvaihtoehto
- Laajuus: 3 op
- Oppitunteja/viikko: 4
- Arvostelu: 0-5
- Oma arvosana: 5
- Arvostelupvm: 02.05.2008
- Läsnäolopakko: ei
- Opettaja: Martti Ylä-Jussila
Virallinen kuvaus (scp.fi, opinto-opas 2005-2006)
Tavoite
Kurssin jälkeen oppilaalla on kyky hyödyntää tehokkaasti ja ohjelmoida yleisesti tunnettuja algoritmeja: peruskäsitteiden tuntemus, taito arvioida algoritmin tehoa ja soveltuvuutta sekä perusalgoritmien tuntemus. Kyky suunnitella tehtävään sopiva algoritmi yhdistelemällä ja soveltamalla tunnettuja tietorakenteita ja algoritmeja. Käsitys algoritmien osoittamisesta oikein toimiviksi.
Sisältö
Algoritmien suorituskyky ja valinta, järjestämisalgoritmit, lista-, taulukko- ja puurakenteet, graafialgoritmeja, muistin hallinnan algoritmeja sekä algoritmien suunnitteluperiaatteita.
Opetusjärjestelyt
Luentoja ja harjoituksia.
Oppimateriaali
Luentomonisteet. Kurssilla ei ole käytössä varsinaista oppikirjaa, mutta tukimateriaalina käytetään teoksia Martti Penttonen: Johdatus algoritmien suunnitteluun ja anlysointiin 1997, Ilkka Kokkarinen - Kirsti Ala-Mutka: Tietorakenteet ja Algoritmit, Suomen ATK-Kustannus, Cormen, Leiserson, Rivest & Stein: Introduction to algorithms, McGraw-Hill. Robert Sedgewick: Algorithms in C, Addisson-Wesley.
Hyväksymisvaatimukset
Harjoitustyöt ja välikokeet tai tentti.
Oma kuvaus
Opetusjärjestelyt
Tämä kurssi oli suoraa jatkoa Tietorakenteet ja algoritmit 1 -kurssille. Itse asiassa tämän kurssin asioita jo aloiteltiin tuon edellisen puolella, kun oppitunteja meinasi jäädä käyttämättä.
Opetusjärjestelyiltään kurssi jatkoi pitkälti edeltäjänsä linjoilla. Teoriaa katseltiin ja kuunneltiin kalvoilta ja oppilaille luennot olivat jaossa pääasiassa PDF-dokumentteina. Oppikirjaa ei ollut, tosin yhden välikokeen asiat muodostuivat Päivi Hietasen C++- ja olio-ohjelmointi -kirjan yksittäisen kappaleen sisällöstä. Tämä kirjahan hankittiin jo toisen opintovuoden alussa Ohjelmoinnin jatko -kurssia varten.
Teorian kuuntelun ohella oppitunneilla tehtiin harjoituksia opettajan johdolla Microsoft Visual C++ 6.0:aa hyödyntäen. Lisäksi tehtiin muutamia harjoituksia kynällä ja paperilla.
Sisältö
Tämän kurssin kurssisuunnitelmasta (opettajan laatimasta ja oppilailleen jakamasta) löytyi todella paljon asiaa, mutta loppujen lopuksi aivan kaikkea ei ehditty käydä läpi. Seuraavassa kuitenkin ne, mitä ehdittiin:
1. välikoe
- hajautus
- verkkoteoria (peruskäsitteet, painotettu verkko, Dijkstran algoritmi)
2. välikoe
- STL (tietovarastoluokat ja geneeriset algoritmit - opiskelu suoraan Hietasen kirjasta)
3. välikoe
- algoritmin käsitteestä (tutkimusongelmia, Carry-yhteenlaskin, kompleksisuus, automaatit, Turingin kone...)
- NP-täydellisyys (NP, P, ongelmakategoriat, väritettävyys, tarkka peite, solmupeite, reppuongelma...)
- algoritmien analysointimenetelmät (pahimman ja parhaan tapauksen kompleksisuus, keskimääräinen kompleksisuus, kompleksisuuden määrittäminen)
- algoritmien suunnitteluperiaatteita (hajota ja hallitse, dynaaminen ohjelmointi, ahne menetelmä, tehtävän muuntaminen, hakumenetelmät, seulontamenetelmät)
- merkkijonon haku (triviaalimenetelmä, Knuth-Morris-Pratt-algoritmi, Boyer-Moore-Horspool-algoritmi, Boyer-Moore-algoritmi)
- joukot (perusoperaatiot, prioriteettijonot, keko, kekolajittelu, vasemmistolaiset keot...)
- sanakirjat (binääriset hakupuut, 2-3-4-puut, punamustat puut, AVL-puut, tasapainottaminen, kierrot)
4. välikoe
- graafit (minimi virittävä puu, Primin algoritmi, Kruskalin algoritmi)
- likimääräis-, satunnais- ja rinnakkaisalgoritmit (0,5-approksimaatio...)
- neuroverkot (mahdollisuudet, neuroni, neuroverkon opettaminen, Perceptron, Adaline, SOM)
- geneettiset algoritmit (termejä, toimintaperiaate, sovellusalueet)
- sumeat järjestelmät (sumea logiikka, sovellusalueet, sumea säätö, perinteinen säätö - käsitelty hyvin pintapuolisesti)
Kurssiin kuului neljä jaksotehtävää, jotka olivat seuraavat:
- Kuljetusongelma (tavaroiden kuljettaminen tieverkolla yhdistetyistä kaupungeista toiseen, ts. lyhimmän reitin etsiminen Dijkstran algoritmin avulla)
- Junan lastaaminen (lastaamisen optimointi eli kaikki vaunut mahdollisimman täyteen - vaati optimointiajattelua, mutta oli käytännössä tietorakenteen käytön harjoittelua)
- Merkkijonon hakeminen (merkkijonojen hakeminen tekstitiedostosta erilaisilla algoritmeilla ja käytetyn ajan tutkiminen - strstr-funktio, triviaalimenetelmä ja Knuth-Morris-Pratt-algoritmi)
- Kohtaaminen (kolmiulotteisessa avaruudessa olevan satelliitin sijainnin laskeminen geneettisellä algoritmilla - jätin tämän viimeisen jaksotehtävän tekemättä)
Koe/muu arvostelu
Arvostelu perustui neljään välikokeeseen ja neljään jaksotehtävään. Pari viimeistä koetta olivat pituudeltaan melko järjettömiä yhdentoista sivun kysymyslistoja - kaikkiin kysymyksiin ei edes ehtinyt vastata, tosin ei tarvinnutkaan, kun korkeimman arvosanan pystyi saavuttamaan vastaamalla oikein vain osaan kokeen kysymyksistä. Ensimmäiseen ja toiseen välikokeeseen sisältyi kynäilyosuuden lisäksi myös pieni ohjelmointitehtävä.
Välikokeet oli pakko suorittaa hyväksytysti läpi, mutta jaksotehtäviä ei välttämättä tarvinnut tehdä. Jaksotehtävissä oli kuitenkin sellainen "kikka", että jos niitä jätti tekemättä, laskivat ne kokonaisarvosanaa. Itse jätin viimeisen jaksotehtävän tekemättä, sillä muut saavutukseni kokeista ja aiemmista jaksotehtävistä riittivät arvosanaan 5.
Todellinen hyöty oppimisen kannalta
Paljon asiaa tällä kurssilla, hyvää sellaista. Harmittavasti jotkut aihepiirit jouduttiin käymään läpi hyvin pintapuolisesti, sillä aika ei olisi muuten riittänyt. Omasta mielestä mielenkiintoisia asioita olivat Dijkstran algoritmi, tietovarastoluokat, merkkijonoon hakuun käytettävät algoritmit ja puut. Kokonaisuutena hyvin paljon sellaisia asioita, joiden tietämisestä on hyötyä yleisesti minkä tahansa ohjelmointikielen kohdalla.
Arvosanat kurssille (0-5)
- Toteutus: 4
- Opetus: 5
- Hyödyllisyys: 5
- Oma suoritus: 5
