Tietojenkäsittelyopin laboratorio Tentti

Tik-76.147 Tietämystekniikan peruskurssi

Merkitse jokaiseen vastauspaperiisi

-Tik-76.147 tietämystekniikan peruskurssi

-04.04.1995

- sukunimi, etunimet

- osasto

- opintokirjan numero

1 a)Vertaile semanttisia verkkoja ja kehyksiä tietämyksen esittämistapoina.

b) Miten semanttista verkkoja ja kehyksiä voidaan toteuttaa PROLOG-kielellä. Esitä myös periytymisen toteutus.

(arvostelu: a-kohta max. 2 pistettä, b-kohta max. 4 pistettä)

2. a) Miksi unifikaatiota tarvitaan predikaattilogiikassa, esim. resoluutiossa?

b) Esitä unifikaatioalgoritmi pääpiireittäin

(arvostelu: a-kohta max. 2 pistettä, b-kohta max. 4 pistettä)

3. Ratkaise resoluutiolla:

Jouko, Maija ja Tauno opiskelevat teatterikorkeakoulussa.

Siellä jokainen opiskelija, joka ei harrasta performansseja, harrastaa bodausta. Bodausta harrastavat eivät pidä yleisöstä ja jokainen, joka ei pidä julkisuudesta, ei harrasta performansseja.

Maija inhoaa sitä, mistä Tauno pitää, ja pitää siitä, mitä Tauno inhoaa.

Tauno pitää yleisöstä ja julkisuudesta.

Onko teatterikorkeakoulussa opiskelijaa, joka harrastaa bodausta, mutta ei performansseja?

Käytä esim. predikaatteja:

teatterikorkeakoulussa( <henkilö>)

pitää( <henkilö>, <asia> )

harrastaa-performansseja( <henkilö>)

harrastaa-bodausta (<henkilö> )

4. a) Selosta A* -hakuproseduurin toimintaperiaate.

b) Sovella A* -hakuproseduuria ongelmaan, jossa seuraavat tilasiirtymät ovat

mahdollisia:

Siirtymä Sen kustannus

S ->A 2

S -> B 1

S ->C 2

A -> D 2

B ->E 1

C -> F 1

D->H 2

E -> H 8

E -> I 7

F -> I 2

H -> G 1

I -> G 2

Ongelmana on löytää polku tilasta S tilaan G, kun funktion h* arvot eri solmuissa ovat seuraavat: h*(A)=3, h*(B)=3, h*(C)=3, h*(D)=2, h*(E)=2, h*(F)=2, h*(H)=1 ja h*(I)=1. Kumman kahdesta minimikustannuspolusta algoritmisi löytää ja miksi?

(arvostelu: a-kohta max. 3 pistettä, b-kohta max. 3 pistettä)

5. Tarkastelemme rajoitteiden tyydyttämisongelmaa, missä

1) Solmujen joukko on A, B, C, D, E, F ja G

2) Kunkin solmun arvoalue on {a, b, c}

3) Seuraavien solmuparien välillä vallitsee binäärirajoite erisuuri kuin(ts. esim. A-n arvon

tulee olla erisuuri kuin B:n arvo):

(A, B), (B, C), (C, D), (D, E), (E, F), (F, G), (G, B), (A, F), (A, D)

a) Mikä on rajoiteverkon leveys?

b) Etsi ko. leveyttä vastaava instantiointijärjestys.

C) Muuta verkkoa siten, että siinä vallitsee em. leveyttä vastaava konsistenssi (so.

jos leveys on k, niin konsistenssin on oltava k+l). Sinun ei tarvitse käyttää, saati sitten formaalisti muotoilla, mitään k-konsistenssialgoritmia, mutta tuloksen on oltava oikein. Halutessasi voit rajoittua suunnattuun konsistenssiin (kohdan b järjestyksen mukaan).

d) Ratkaise ko. ongelma ilman peruutusta.

Arvostelu: kohdat a ja b 2 pistettä, kohdat c ja d 1 piste.