Tietotekniikan perusteet
Loppukoe ke 17.6.1998 8-12

Teht. 1
(a) (5 pistettä)

 
Figure:   Tehtävän 1. automaatti.

Täydennä kuvan 1 automaatti (sijoita muistipaikkoihin 0 tai 1) niin, että syötteen ollessa automaatti tulostaa vasteenaan seuraavaa päättymätöntä sekvenssiä ( ):

ja syötteen ollessa automaatti tulostaa vasteenaan päättymätöntä sekvenssiä:

(b) (5 pistettä)

Mikä on edellisen kohdan automaatin tilakaavio (esitettynä joko taulukkona tai graafisesti) ?

(c) (5 pistettä)

Kuinka toteutat vastaavan automaatin vain kahdella tilalla, käyttäen bitin muistin sijaan bitin muistia.

Teht. 2

(a) (5 pistettä)

Esitä lyhyesti ja ytimekkäästi Von Neumann (EDVAC) arkkitehtuurin käskynhakusekevenssi.

(b) (5 pistettä)

Selvitä lyhyesti seuraavat käsitteet: muistiavaruus, sananpituus, aritmeettislooginen yksikkö, väylä, ohjelmalaskuri (PC-rekisteri).

(c) (5 pistettä)

Esitä lyhyesti mikä ero on spesifikaatiolla, algoritmilla ja implementaatiolla.

Teht. 3

Mitkä seuraavista väitteistä ovat tosia (T), mitkä epätosia (E) (kukin kohta 1 piste):

1. Useimmat nykyisin käytössä olevat ohjelmointikielet polveutuvat vuonna 1958 kehitetystä Algol-kielestä.
2. Tulkkiohjelman tehtävänä on kääntää konekielinen ohjelma ihmisen luettavaan muotoon.
3. Windows NT on ensimmäinen oikeaksi todistettu käyttöjärjestelmä.
4. Yksiprosessorikoneessa voi vain yksi prosessi kerrallaan olla valmiustilassa.
5. Ohjelman sijainti tietokoneen muistissa voi muuttua ohjelman suorituksen aikana.
6. John von Neumannin EDVAC-raportti vakiinnutti rinnakkaistietokoneiden arkkitehtuurin.
7. Algoritmien aikavaativuutta voidaan arvioida käytetystä ohjelmointikielestä riippumatta.
8. ``Käyttökelpoisina'' pidetään yleensä algoritmeja, joiden aikavaativuus on enintään polynominen syötejonon pituuden suhteen.
9. Tällä hetkellä ei tiedetä, onko funktio n! arvon n suhteen polynomisesti rajoitettu.
10. Tällä hetkellä ei tiedetä, onko P = NP.
11. Tiedonhallinnan verkkomalli on vähitellen syrjäyttämässä relaatiomallin.
12. Relaatiotaululla voi olla useita avaimia.
13. Tekoälytutkimus on tietotekniikan uusin kehityssuunta.
14. Tekoälytutkijoiden tavoitteena on löytää älyllisen toiminnan yleiset lait ja toteuttaa ne tietokoneella.
15. ``Tiedonjalostus'' (engl. data mining) on yksi tietokonelingvistiikan tärkeimpiä sovellusalueita.

Teht. 4 (15 pistettä)

Toinen seuraavista:

1. Virtuaalimuistin toimintaperiaate.
2. Korkean tason ohjelman kääntäminen konekielelle. (Valaise esitystäsi esimerkillä. Tarvitsemasi konekielen käskyt saat halutessasi keksiä itse; selitä kuitenkin käyttämiesi käskyjen toiminta.)