Perustiedot opintojaksosta Algoritmit ja tietorakenteet, päivitetty 9.9.2008 (Hannu Laine)

Algoritmit ja tietorakenteet T0197  (Iltaopiskelu)

Kurssi on peruutettu vähäisen osanottajamäärän takia.

Opintojakson tärkein tavoite on oppia ymmärtämään abstraktion, yleisyyden ja ohjelmistokomponenttien merkitys ohjelmoinnissa ja oppia käyttämään niitä hyväksi. Opintojaksolla opitaan käyttämään ja rakentamaan ohjelmistokomponentteja. Opintojaksolla tutustutaan yleisten uudelleenkäytettävien ohjelmistokomponenttien problematiikkaan. Komponentteja rakennetaan sekä C-kielellä, jolloin käytetään ns. abstraktien tietotyyppien mallia ja C++ -kielellä, jolloin käytetään luokkamallia. Tarkoituksena on nähdä, miten C-kielellä voidaan toteuttaa yleisiä uudelleen käytettäviä komponentteja.  Näiden välineiden puutteet havaitaan kokreettisesti ja omakohtaisesti. Näin opitaan perusteellisesti ymmärtämään mitä etuja olioperustainen lähestymistapa antaa perinteiseen ohjelmointikieleen nähden. C ja  C++ kieliä siis verrataan toisiinsa niiden abstraktioon ja yleisyyteen tarjoamien välineiden osalta. Opintojaksolla käsitellään myös yleiseen käyttöön tarkoitetut  ohjelmistokomponentit  kuten listat, pinot, jonot ja puut. Algoritmien osalta käsitellään rekursio perusteellisesti. Opitaan, miten rekursiota käytetään määrittelyissä, ongelman ratkaisussa ja ohjelmointitekniikkana. Tutustutaan myös siihen, millä tavalla prosessori suorittaa rekursiivista aliohjelmaa. Opintojaksolla tutustutaan erilaisiin järjestämis- ja etsintämenetelmiin käyttäen lähestymistapana algoritmien analyysia. Myös näiden kohdalla on yhtenä tarkastelukulmana algoritmien yleisyys. Yllämainittuihin asioihin liittyen esiin tulevat lisäksi mm: template luokat, säiliöluokat, iteraattorit yms.

 

[ Yleistiedot  |   Pääkohdat   |   Toteutumat  |   Kurssimateriasaali  | Harjoitukset  |  Ryhmätyö  | Tentti]

o Yleistiedot

oSisällön pääkohdat

Seuraavassa on alustavasti sisällön pääkohdat. Lista tarkentuu opintojakson aikana.
 

oKäsitellyt asiat

Klikkaamalla seuraavaa linkkiä, saat näkyviin tarkemman listan, mitä tähän mennessä on tunneilla käsitelty:

Lista käsitellyistä asioista

 oKurssimateriaali

(tai 2) Mark Allen Weiss : Data structures and algorithm analysis in C )

Moniste 1 ( Algoritmi ja abstraktio )

( Esimerkki 1 , Esimerkki 2 , Esimerkki 3 ,  Esimerkki 4 ,  Esimerkki 5 )

Moniste 2 ( Tietueen ominaisuudet )

Moniste 3 ( Lista)

(Esimerkki 1 : "Järjestämätön lista",  Esimerkki 2 : "Järjestetty lista".

       

Moniste 4 ( Pino ja jono )

Esimerkki 1 (pinon toteutus taulukolla ja pinon käyttöesimerkki),
Esimerkki 2 : (edellisen jakaminen erillisiin tiedostoihin : pinoa käyttävä sovellus , pinon header,
pinon toteutus )
Esimerkki 3 (pinon toteutus toisella tavalla, sovellus ei muutu)
Esimerkki 4 (jonon toteutus taulukolla ja jonon käyttöesimerkki)
Esimerkki 5 : (ADT pinon käyttö työkaluna ADT listan linkatussa taulukkototeutuksessa :  Lista linkattuna taulukkona ,  kokonaislukupinon header ,  kokonaislukupinon toteutus )
Esimerkki 6  (ADT jonon käyttö ADT prioriteettijonon toteutuksessa)

Moniste 5 ( Dynaamiset tietorakenteet )

Esimerkki 1 (Tilan varaaminen taulukoille dynaamisesti),
Esimerkki 2 (Pinon toteutus dynaamisesti varatulla taulukolla),
Esimerkki 3 (Dynaamisesti varatun linkatun listan periaate vaiheittain: Case 1 , Case 2 , Case 3 , Case 4 )
Esimerkki 4 (Pinon toteutus dynaamisesti varattuna linkattuna rakenteena),
Esimerkki 5  (Jonon toteutus dynaamisesti varattuna linkattuna rakenteena)
Esimerkki 6  (Pinon toteutus dynaamisesti varattuna linkattuna rakenteena C++:n luokkana)

Moniste 6 ( Muita linkattuja rakenteita)

 

o Harjoitukset

Harjoitustehtäviä on kaikkiaan noin 10 kpl, joista noin 7 on pakollista. Vapaaehtoiset tehtävät on merkitty numeron perässä olevalla L-kirjaimella (, jossa L tulee sanan Lisätehtävä alkukirjaimesta)

 

Harjoitus 1


Harjoitus 2

 oRyhmätyöharjoitus

Opintojaksoon ei kuulu ryhmätyöharjoitusta.

 o Tentti 

Tentissä tutkitaan kurssilla käsiteltyjen aiheiden ymmärtäminen ja kyky niiden soveltamiseen. Opintojakson arvosana määräytyy pääsiassa kokeen perusteella (80%). Aktiivisuus labratehtävien tekemisessä vaikuttaa max 20% ( yksi askel numeroskaalassa). Tehtävien luonne noudattaa pitkälle labraharjoituksissa olleita tehtäviä, mutta labratehtävät eivät suinkaan anna suoria vastauksia kysymyksiin.

Seuraavassa muutamia tyypillisiä kysymystyyppejä. Kysymystyyppi 1) Tiettyjä reaalimaailman objekteja kuvataan seuraavilla ominaisuuksilla: ... ja niille on määritelty seuraavat operaatiot. Toteuta abstrakti tietotyyppi näille objekteille (s.o. kirjoita tietotyyppimäärittelyt ja operaatiofunktiot). Kysymystyyppi 2) Käytössäsi on abstrakti tietotyyppi xxx. Sen operaatiofunktiot ovat.... Interfacen kuvaus on tiedostossa  xxx.h ja käännetty objektitiedosto on tiedostossa xxx.obj. Kirjoita ohjelma, joka tekee seuraavan tehtävän... käyttäen annettua abstraktia tietotyyppiä xxx. Kysymystyyppi 3) Käytössäsi on abstrakti tietotyyppi xxx. Sen operaatiofunktiot ovat.... Interfacen kuvaus on tiedostossa  xxx.h ja käännetty objektitiedosto on tiedostossa xxx.obj. Toteuta abstrakti tietotyyppi yyy, jolla on seuraavat operaatiot... käyttäen abstraktia tietotyyppiä xxx (ADT xxx tulee siis olemaan ADT yyy:n alakomponentti). Kysymystyyppi 4) Kirjoita ohjelma, joka ratkaisee annetun probleeman rekursiivisesti. Kysymystyyppi 5) Alla on valmis ohjelma (todennäköisesti rekursiivinen). Minkä probleeman ohjelma ratkaisee tai minkä tehtävän se suorittaa. Mikä on maksimitila, joka on varattuna pinosta kerraallaan fucktiolle f.  Kysymystyyppi 6) Alla on funktio, joka järjestää kokonaislukutaulukon.  Mitkä muutokset funktioon tarvitaan tekemään siitä yleinen järjestämisfunktio. Yleisellä järjestämisfunktiolla tarkoitetaan funktiota, jonka lähdekoodia ei tarvitse muuttaa, kun taulukon alkion tyyppiä muutetaan vaikkapa kokonaisluvusta varaosatietueeksi tai kun järjestämiskriteeri vaihdetaan vaikka varaosan hinnan ja painon suhteeksi.

Muutamia mallikysymyksiä ja niiden vastaukset löydät näistä linkeistä.