Deklaratív programozás pótzárthelyi, 2002. május 14. ==================================================== Javítási kulcsok ================ ------------------- A csoport ------------------- 1. Döntse el, mi lesz az alábbi Prolog kérdések eredménye (hiba, meghiúsulás, siker)! Siker esetén adja meg a keletkező valtozó-behelyettesítéseket! A kérdéseket egyenként és önmagukban adjuk át az értelmezőnek. 1a. | ?- [X|Y] = [a,b]. X = a, Y = [b] 1b. | ?- V is 3*U, U = 2+2. Instantiation error 1c. | ?- A is 2+2, B = A+2. A = 4, B = 4+2 1d. | ?- P/Q = 48/12/3. P = 48/12, Q = 3 1e. | ?- 1+4 = Z, Z = 5. no Pontozás: 1.a-1.e Helyes válasz 1 pont, helytelen 0 pont. 2. Írja fel az alábbi egyenlőségek bal- és jobboldalának alapstruktúra alakját, vagy rajzolja fel a fastruktúrájukat! Adja meg, milyen változó-behelyettesítéseket eredményeznek ezek az egyesítések! 2a. f(X, X, [1]) = f(X,X,.(1,[])) f(B+A, 4/2+C, C) = f(+(B,A),+(/(4,2),C),C) egyesítés eredménye: A = [1], B = 4/2, C = [1], X = 4/2+[1] 2b. [g(P,a*b),Q|R] = .(g(P,*(a,b)),.(Q,R)) [Q|.(g(6,S),[S])] = .(Q,.(g(6,S),.(S,[]))) egyesítés eredménye: P = 6, Q = g(6,a*b), R = [a*b], S = a*b Pontozás: Minden helyes alapstruktúra-alak 1 pont, helytelen 0 pont (összesen max. 4 pont). 2a. helyes egyesítés 2 pont 2b. helyes egyesítés 3 pont Mindösszesen max. 9 pont 3. Tegyük fel, hogy az alábbi programot betöltöttük a Prolog rendszerbe. q(a, b). q(b, a). p([_|L], Y) :- p(L, Y). p([X|_], Y) :- q(X, Y). Állapítsa meg, hogy a feltett kérdésekre válaszul a rendszer milyen behelyettesítést ad az X változónak! Írja fel az összes megoldást a rendszer által előállított sorrendben, pontosvesszővel elválasztva! Ha nincs megoldás, írjon {no}-t! 3a. p([], X). ---> {no} 3b. p([a], X). ---> b 3c. p([a,b,b], X). ---> a ; a ; b 3d. p([b,u,b,a], X). ---> b ; a ; a 3e. p([b,e,z,a,b,a,l], X). ---> b ; a ; b ; a 3f. Tegyük fel, hogy a fenti eljárás p(L, X) hívásában az L argumentum egy csak a és b atomokat tartalmazó lista. Írja le általánosan, hogy milyen X értékeket eredményez majd ez a hívás, és a megoldásokat milyen sorrendben adja ki a Prolog rendszer. Felsorolja a lista összes elemét, hátulról előrefelé, és minden 'a' esetén 'b'-t, minden 'b' esetén 'a'-t ad eredményül. Pontozás: 3a.-e. minden helyes válaszért 1 pont 3f. 2 pont 4. Egy hegyi utat egy L számlistával írunk le, amelynek elemei az út egyes pontjainak tengerszint feletti magasságát adják meg. Feltételezzük, hogy ezen pontok között az út vagy csak emelkedik vagy csak lejt. Az emelkedő szakaszok szintkülönbségének az összegét az út emelkedésének nevezzük. Írjon olyan Prolog eljárást, amely megfelel az alábbi fejkommentnek! Segédeljárást nem használhat! % emelkedes(+L, +E0, -E): Az L lista által leírt út emelkedése E-E0. % L és E0 bemenő, E kimenő paraméter. | ?- emelkedes([10,15,20], 0, E). ----> E = 10 ? ; no | ?- emelkedes([0,10,5,15], 0, E). ----> E = 20 ? ; no | ?- emelkedes([0,20,40,25,20,40,28,16], 0, E). ----> E = 60 ? ; no 4/1. megoldás: emelkedes([], E0, E0). emelkedes([_], E0, E0). emelkedes([X,Y|L], E0, E) :- ( Y > X -> E1 is E0+Y-X ; E1 is E0 ), emelkedes([Y|L], E1, E). 4/2. megoldás: emelkedes([], E0, E0). emelkedes([X,Y|L], E0, E) :- Y > X, !, E1 is E0+Y-X, emelkedes([Y|L], E1, E). emelkedes([_|L], E0, E) :- emelkedes(L, E0, E). Összpontszám: 9 pont Nem követelmény a hatékony program. 5. Mi az f típusa az alábbi (egymástól független) deklarációkban? 5a. fun f x y z = (x, y z) f : 'a -> ('b -> 'c) -> 'b -> 'a * 'c 5b. fun f (x, y, z) = x (y z) f : ('a -> 'b) * ('c -> 'a) * 'c -> 'b 5c. fun f x (y, z) = x (y, z) f : ('a * 'b -> 'c) -> 'a * 'b -> 'c Pontozás: Helyes válaszonként 3-3, összesen 9 pont. Kis hiba esetén nincs levonás, komolyabb hiba esetén 1-1, súlyos hiba esetén 2-2 pont levonás. 6. Mi az x értéke és típusa az alábbi (egymástól független) deklarációkban? 6a. val x = explode "csi" @ [#"p",#"a"] x = [#"c", #"s", #"i", #"p", #"a"] : char list 6b. val x = List.filter (fn true => true | _ => false) [1<2, 1.2=2.1, "a"<>"b"] x = [true, true] : bool list 6c. val x = map List.drop [([9,8,7,6,5],4), ([3,2],1)] x = [[5], [2]] : int list list Pontozás: Helyes válaszonként 2-2, összesen 6 pont. Kis hiba esetén nincs levonás, komoly hiba esetén 1-1 pont levonás. 7. Mit kap eredményül, ha az alábbi f függvényt a nyolc számjegyből álló, ÉÉÉÉHHNN alakban füzérként megadott saját születési dátumára alkalmazza (pl. f "19820431")? Válaszát indokolja! local fun g (x::y::zs) = chr (let val z = ord x + ord y - ord #"0" in if z <= ord #"9" then z else z-10 end) :: g zs | g _ = [] in fun f t = implode(g(explode t)) end A feladatban megnevezett példára: f "19820431" = "0044", egy "saját" születési dátumra: f "19831129" = "0121". Indoklás, magyarázat: explode argumentumát, a t füzért karakterlistává, implode a g függvény karakterlista-eredményét füzérré alakítja. A g függvény argumentuma a karakterlista: első két elemének ascii-kódját összeadja és levonja belőle a 0 ascii-kódját (vagyis a karaktereknek megfelelő két decimális számjegyet összeadja, és az eredményt karakterként ábrázolja); ez lesz z értéke. Ha a két számjegy összege 9-nél nagyobb, az eredményből levon 10-et, egyébként változatlanul hagyja. A kapott karakterkód lesz az eredménylista első, ill./ a rekurzív hívások során a következő jegye. A rekurzió véget ér, ha a karakterlista üressé válik. Nyolcjegyű születési dátum esetén az f függvény eredménye egy négy számjegyből álló füzér. Pontozás: Összesen 6 pont. Ha a válasz csak a saját születésnapra kapott eredményből áll, indoklás nélkül, akkor 2 pont adható, csak az indoklásért max. 4 pont jár. Kisebb hibáért 1 pontot, nagyobb hibáért 2 pontot vonunk le. 8. Egy nemnegatív egész számokból álló listát (n,m)-emelkedőnek hívunk, ha a 0 elemektől eltekintve kizárólag az n+1, n+2, ..., m (esetleg üres) számsorozatot tartalmazza, ebben a sorrendben. Speciálisan: egy üres vagy csak 0-kat tartalmazó listát (n,n)-emelkedőnek tekintünk, tetszőleges n esetén. Írjon olyan SML-függvényt, amely megfelel az alábbi fejkommentnek! Segédfüggvényt nem definiálhat! (* emelkedo : int list * int -> int emelkedo (ns, n) = m, ha ns (n,m)-emelkedő; ~1, ha nem az PRE: ns minden eleme >= 0, n >= 0 *) Példák: emelkedo([5,6], 4) = 6 emelkedo([6,5], 4) = ~1 emelkedo([0,1,2,0,3], 0) = 3 emelkedo([0,1,0,0,2,0,3,4,0], 0) = 4 emelkedo([0,0,0,0], 9) = 9 emelkedo([], 123) = 123 Megoldás: fun emelkedo ([], n) = n | emelkedo (0::ns, n) = emelkedo(ns, n) | emelkedo (m::ns, n) = if n+1=m then emelkedo(ns, n+1) else ~1 Pontozás: Összesen 9 pont. Levonások járnak az alábbiakért: - nem áll le a rekurzió, nincs [] ág -2 pont - a 0 esetet nem vagy rosszul kezeli -2 pont - nem ad vissza ~1-et hiba esetén -2 pont - az m=n+1 eset hibás vagy hiányzik -3 pont Egyéb lehetséges hibák: - n-et nem növeli, vagy mindig növeli -2 pont - apróbb szintaktikai hiba (pl. [a::as]) -1 pont - nagyobb szintaktikai hiba (pl. a@as) -2 pont - durva hiba (hiányzó else ág) -3 pont - felesleges eset -2 pont ------------------- B csoport ------------------- 1. Döntse el, mi lesz az alábbi Prolog kérdések eredménye (hiba, meghiúsulás, siker)! Siker esetén adja meg a keletkező valtozó-behelyettesítéseket! A kérdéseket egyenként és önmagukban adjuk át az értelmezőnek. 1a. | ?- [u,v,w] = [X,Y|Z]. X = u, Y = v, Z = [w] 1b. | ?- 4+2+3 = X+Y. X = 4+2, Y = 3 1c. | ?- X is X+1. Instantiation error 1d. | ?- X is 3+4, X = 3+4. no 1e. | ?- a+A = B+b. A = b, B = a Pontozás: 1.a-1.e Helyes válasz 1 pont, helytelen 0 pont. 2. Írja fel az alábbi egyenlőségek bal- és jobboldalának alapstruktúra alakját, vagy rajzolja fel a fastruktúrájukat! Adja meg, milyen változó-behelyettesítéseket eredményeznek ezek az egyesítések! 2a. [[X], Y, 2*X] = .(.(X,[]),.(Y,.(*(2,X),[]))) [.(1,E), F, F] = .(.(1,E),.(F,.(F,[]))) egyesítés eredménye: E = [], F = 2*1, X = 1, Y = 2*1 2b. f(U*V, [3*2+b|W]) = f(*(U,V),.(+(*(3,2),b),W)) f(S, [S+T, T]) = f(S,.(+(S,T),.(T,[]))) egyesítés eredménye: S = 3*2, T = b, U = 3, V = 2, W = [b] Pontozás: Minden helyes alapstruktúra-alak 1 pont, helytelen 0 pont (összesen max. 4 pont). 2a. helyes egyesítés 2 pont 2b. helyes egyesítés 3 pont Mindösszesen max. 9 pont 3. Tegyük fel, hogy az alábbi programot betöltöttük a Prolog rendszerbe. s([], 0). s([X|_], X) :- X > 5. s([_,_|L], X) :- s(L, X). Állapítsa meg, hogy a feltett kérdésekre válaszul a rendszer milyen behelyettesítést ad az X változónak! Írja fel az összes megoldást a rendszer által előállított sorrendben, pontosvesszővel elválasztva! Ha nincs megoldás, írjon {no}-t! 3a. | ?- s([8], X). ---> 8 3b. | ?- s([7,8], X). ---> 7 ; 0 3c. | ?- s([7,8,9], X). ---> 7 ; 9 3d. | ?- s([1,6,8,2,7,9,3], X). ---> 8 ; 7 3e. | ?- s([2,3,4,5,6,7,8,9], X). ---> 6 ; 8 ; 0 3f. Tegyük fel, hogy a fenti eljárás s(L, X) hívásában L egy páros elemszámú lista. Írja le általánosan, hogy ebben az esetben milyen X értékeket eredményez majd ez a hívás, és a megoldásokat milyen sorrendben adja ki a Prolog rendszer. Felsorolja a lista páratlan sorszámú elemei közül azokat, amelyek 5-nél nagyobbak, és a végén még egy 0-t. Pontozás: 3a.-e. minden helyes válaszért 1 pont 3f. 2 pont 4. Egy repülő útvonalát egy L számlistával írjuk le, amelynek elemei a repülő rendszeres időközökben mért tengerszint feletti magasságát adják meg, méterben. Zuhanásnak nevezzük azt, ha két egymás utáni adat közötti különbség legalább 10 méteres süllyedést mutat. Írjon olyan Prolog eljárást, amely megfelel az alábbi fejkommentnek! Segédeljárást nem használhat! % zuhanasok(+L, +Z0, -Z): Az L lista által leírt repülő-útvonalon Z-Z0 % számú esetben fordul elő zuhanás. L és Z0 bemenő, Z kimenő paraméter. | ?- zuhanasok([20,15,10], 0, Z). ----> Z = 0 ? ; no | ?- zuhanasok([20,10], 0, Z). ----> Z = 1 ? ; no | ?- zuhanasok([0,20,40,25,20,40,28,16], 0, Z). ----> Z = 3 ? ; no 4/1. megoldás: zuhanasok([], Z0, Z0). zuhanasok([_], Z0, Z0). zuhanasok([X,Y|L], Z0, Z) :- ( Y =< X-10 -> Z1 is Z0+1 ; Z1 = Z0 ), zuhanasok([Y|L], Z1, Z). 4/2. megoldás: zuhanasok([], Z0, Z0). zuhanasok([X,Y|L], Z0, Z) :- Y =< X-10, !, Z1 is Z0+1, zuhanasok([Y|L], Z1, Z). zuhanasok([_|L], Z0, Z) :- zuhanasok(L, Z0, Z). Összpontszám: 9 pont Nem követelmény a hatékony program. 5. Mi az f típusa az alábbi (egymástól független) deklarációkban? 5a. fun f x y z = (x y, z) f : ('a -> 'b) -> 'a -> 'c -> 'b * 'c 5b. fun f (x, y, z) = (x y) z f : ('a -> 'b -> 'c) * 'a * 'b -> 'c 5c. fun f (x, y) z = x (y, z) f : ('a * 'b -> 'c) * 'a -> 'b -> 'c Pontozás: Helyes válaszonként 3-3, összesen 9 pont. Kis hiba esetén nincs levonás, komolyabb hiba esetén 1-1, súlyos hiba esetén 2-2 pont levonás. 6. Mi az x értéke és típusa az alábbi (egymástól független) deklarációkban? 6a. val x = [#"p",#"a"] @ explode "csi" x = [#"p", #"a", #"c", #"s", #"i"] : char list 6b. val x = List.filter (fn true => false | _ => true) [3.0>4.0, 4.7>2.4, ~3.0<=0.4] x = [false] : bool list 6c. val x = map List.take [([9,8,7,6,5],4), ([3,2],1)] x = [[9, 8, 7, 6], [3]] : int list list Pontozás: Helyes válaszonként 2-2, összesen 6 pont. Kis hiba esetén nincs levonás, komoly hiba esetén 1-1 pont levonás. 7. Mit kap eredményül, ha az alábbi f függvényt a nyolc számjegyből álló, ÉÉÉÉHHNN alakban füzérként megadott saját születési dátumára alkalmazza (pl. f "19820431")? Válaszát indokolja! local fun h (u::v::ws) = chr (let val w = (ord u + ord v) div 2 in if w >= ord #"5" then w else 2*w - ord #"0" end) :: h ws | h _ = [] in fun f t = implode(h(explode t)) end A feladatban megnevezett példára: f "19820431" = "5544", egy "saját" születési dátumra: f "19831129" = "5525". Indoklás, magyarázat: explode argumentumát, a t füzért karakterlistává, implode a g függvény karakterlista-eredményét füzérré alakítja. A h függvény argumentuma a karakterlista: első két elemének ascii-kódjának veszi a lefelé kerekített átlagát, vagyis az átlaguk ascii-kódját; ez lesz w értéke. Ha a w nem kisebb, mint 5, akkor változatlanul hagyja, egyébként veszi a kétszeresének megfelelő karaktert. A kapott karakterkód lesz az eredménylista első, ill./ a rekurzív hívások során a következő jegye. A rekurzió véget ér, ha a karakterlista üressé válik. Nyolcjegyű születési dátum esetén az f függvény eredménye egy négy számjegyből álló füzér. Pontozás: Összesen 6 pont. Ha a válasz csak a saját születésnapra kapott eredményből áll, indoklás nélkül, akkor 2 pont adható, csak az indoklásért max. 4 pont jár. Kisebb hibáért 1 pontot, nagyobb hibáért 2 pontot vonunk le. 8. Egy nemnegatív egész számokból álló listát (n,m)-lejtőnek hívunk, ha a 0 elemektől eltekintve kizárólag az n, n-1, ..., m+1 (esetleg üres) számsorozatot tartalmazza, ebben a sorrendben. Speciálisan: egy üres vagy csak 0-kat tartalmazó listát (n,n)-lejtőnek tekintünk, tetszőleges n esetén. Írjon olyan SML-függvényt, amely megfelel az alábbi fejkommentnek! Segédfüggvényt nem definiálhat! (* lejto : int list * int -> int lejto (ns, n) = m, ha ns (n,m)-lejtő; ~1, ha nem az PRE: ns minden eleme >= 0, n > 0 *) Példák: lejto([6,5], 6) = 4 lejto([5,6], 5) = ~1 lejto([0,3,2,0,1], 3) = 0 lejto([0,5,4,0,0,3,0,2,0], 5) = 1 lejto([0,0,0,0], 9) = 9 lejto([], 123) = 123 Megoldás: fun lejto ([], n) = n | lejto (0::ns, n) = lejto(ns, n) | lejto (m::ns, n) = if n=m then lejto(ns, n-1) else ~1 Pontozás: Összesen 9 pont. Levonások járnak az alábbiakért: - nem áll le a rekurzió, nincs [] ág -2 pont - a 0 esetet nem vagy rosszul kezeli -2 pont - nem ad vissza ~1-et hiba esetén -2 pont - az m=n eset hibás vagy hiányzik -3 pont Egyéb lehetséges hibák: - n-et nem csökkenti, vagy mindig csökkenti -2 pont - apróbb szintaktikai hiba (pl. [a::as]) -1 pont - nagyobb szintaktikai hiba (pl. a@as) -2 pont - durva hiba (hiányzó else ág) -3 pont - felesleges eset -2 pont