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 konkreettisesti 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. Opintojaksolla käsitellään myös puurakenteet. Yllämainittuihin asioihin liittyen esiin tulevat lisäksi mm: template luokat, säiliöluokat, iteraattorit yms.

 Yleistiedot

• Opintojakso sijoittuu periodeille 1 ja 2
• Opintojakson laajuus on  4,5 op
  
• Luentoja 2 h / viikko( 28 h yhteensä)
• Laboratorioharjoituksia 2 h / viikko (28 h yhteensä)
• Harjoitustyö (15 h)
• Itseopiskelua (49h)
• Tentti opintojakson lopussa ( 3h)

Sisällön pääkohdat

Seuraavassa on alustavasti sisällön pääkohdat. Lista tarkentuu opintojakson aikana.
 
• Johdanto, sisältö, algoritmi
• Toimintojen abstraktio / tietojen abstraktio
• Abstrakti tietotyyppi (ADT-komponentit)
• Sovelluksen "koonti" komponenteista
• Komponenttien toteutus (C ja C++)
• Monitasoiset komponentit
• Lista : Määrittely ja käyttö
• Lista : Erilaisia toteutustapoja
• Komponenttien yleisyys
• Pino : Määrittely, käyttö ja toteutukset
• Jono : Määrittely, käyttö ja toteutukset
• Taulukkototeutusten puutteet
• Dynaamisen muistin käyttö toteutuksissa
• ADT lista dyn. varattuna linkattuna rakenteena
• Pino ja jono dyn. varattuna linkattuna rakenteena
• Muita linkattuja rakenteita
• Renkaat, kaksoislinkatut listat, matriisit jne
• Lisää yleisyyden tarkastelua
• Luokat, operaattorien ylikuormitus ja template
• Muita eroja C:n ja C++:n välillä
• Säiliöluokat
• Iteraattorit
• Yhteenveto komponenteista
• Rekursion periaate, rekursiivisen funktion toiminta (call tree)
• Rekursio ongelman ratkaisuvälineenä
• Järjestämismenetelmät ja niiden vertailu
• Etsintämenetelmät ja niiden vertailu
• Sequential search, Binary search, Hashing method
• Binääripuu, binäärinen etsintäpuu
• Puualgoritmit (operaatiofunktiot)

Käsitellyt asiat

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

Lista käsitellyistä asioista

 Kurssimateriaali

• Allaolevat linkit sisältävät tukimateriaalia tunneilla käsiteltäviin asioihin
• Tunneilla tehtävät muistiinpanot
• Asiaa tukevia kirjoja 1)  Kruse, Leung, Tondo :  Data Structures and Program design in C
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 )

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)

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 7 (Rekursio )

Esimerkki 1  (Linkatun listan operaatiofunktioita rekursiivisesti toteutettuna )

Esimerkki 2  (Hakemistorakenteen läpikäynti)

 Harjoitukset

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

 Ryhmätyöharjoitus

  Tentti

Tentti on toisella tenttijaksolla torstaina 15.12.2005 klo 8.00 huoneessa 1.127.  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ä.


---