A vizsgán tudni kell a jegyzet alábbi fejezeteit:
Az alábbi beépített eljárások pontos működését fejből ismerni kell.
Az alábbi eljárások definícióját fejből ismerni kell.
A jegyzet fent említett részeiben szereplő egyéb eljárásokkal
kapcsolatban is csak lexikális segítséget adunk (milyen sorrendben sorolja
fel a megoldásokat, milyen sorrendben kapja a paramétereit stb.).
A vizsga első részében, min. 60 perces felkészülési idő alatt, néhány kisebb programozási feladatot kell megoldani Prolog-, ill. SML-nyelven, írásban.
Példák a feladható programozási feladatokra:
* Írjon egy olyan Prolog eljárást, amely egy tetszőleges Prolog kifejezés
esetén felsorolja a benne lévő olyan legbővebb összetett részkifejezéseket,
amelyek egész számokból a + és * kétargumentumú operátorokkal épülnek fel! A
`legbővebb' jelző azt jelenti, hogy egy ilyen részkifejezés részeit ne sorolja
fel, az `összetett' jelző pedig azt, hogy az egyetlen számból álló részkifejezé-
seket se sorolja fel. Vigyázat: a kifejezésben változók is előfordulhatnak!
% ari_resz(Kif, R): A Kif kifejezés része R, R összetett, egész számokból
% a + és * operátorokkal épül fel, és az ilyenek között a legbővebb.
% :- pred ari_resz(univ::in, univ::out).
| ?- ari_resz(f(1+2, 8, 4+3*X, g(5+4*2)), R). R = 1+2 ; R = 5+4*2 ; no
| ?- ari_resz(a+(1+2*3)*X+4*5+6, R). R = 1+2*3 ; R = 4*5 ; no
% Megjegyzés: a `...+4*5+6' zárójelezése `(...+4*5)+6', ezért a 4*5+6 ennek
% nem részkifejezése. Természetesen a zárojelezéssel nem kell foglalkoznia a
% megoldásban, hiszen azt a Prolog beolvasója megteszi!
Könnyített feladat: Felteheti, hogy a kifejezésben csak a + és * kétargumentumú
struktúranevek szerepelnek, mint a második példában.
* Írjon Prologban egy olyan eljárást, amely egy tetszőleges Prolog struktúra-
kifejezés összes olyan valódi részstruktúráját felsorolja, amelynek neve
megegyezik az egész kifejezés nevével. Nem számít valódi részstruktúrának
maga az egész kifejezés, és a benne előforduló atomok. Vigyázat, a
kifejezésben változók is előfordulhatnak!
% nevu_resze(Kif, Resz): Resz a Kif-nek olyan valódi részstruktúrája,
% amelynek neve megegyezik Kif nevével.
% :- pred nevu_resze(any::in, any::out).
Példa:
| ?- nevu_resze(f(1,f(2), f(f(X)), g(f)), R).
R = f(2); R = f(f(X)); R = f(X)
* írjon egy olyan Prolog eljárást, amely visszaadja egy atom formájában
megadott szövegben a szavak számát. Szónak számít minden 32-nél nagyobb
ASCII kódú karakterekből álló összefüggő jelsorozat. A szavakat egy vagy
több láthatatlan (32-nél kisebb-egyenlő kódú) karakter választja el. A
szöveg elején és végén előfordulhatnak láthatatlan karakterek. Törekedjék
hatékony (jobbrekurzív) megoldásra.
% szoszam(Atom, Szam): Szam az Atomban előforduló szavak száma.
% :- pred szoszam(atom::in, int::out).
Példa:
| ?- szoszam(' Ali baba és a 40 rabló', N). N = 6
* Egy számlistában kaptatónak hívunk egy olyan legalább kételemű folyamatos
részlistát, amely szigorúan monoton növő, és egyik irányba sem terjeszthető ki
szigorúan monoton módon. Írjon olyan Prolog eljárást, amely felsorolja egészek
egy adott listájában található kaptatókat.
% kaptato(L, K): K az L számlistában előforduló kaptató, azaz maximális
% szigorúan monoton növő, legalább kételemű folytonos részlista.
% :- pred kaptato(list(int)::in, list(int)::out).
| ?- kaptato([1,2,3,3,1,3,5,4,3,2,4], L). L = [1,2,3]; L = [1,3,5]; L = [2,4]
* Írjon egy olyan Prolog eljárást, amely egy tetszőleges Prolog kifejezésből
listába gyűjti a benne előforduló egész számokat! Az előfordulások sorrendjét
őrizze meg! Vigyázat, a kifejezésben változók is előfordulhatnak!
% szamai(Kif, EL): EL a Kif-ben előforduló egész számok listája.
% :- pred szamai(any::in, list(int)::out).
| ?- szamai(f(5,2+5,g(0)), L). L = [5,2,5,0]
* Írjon olyan Prolog eljárást, amely egy egyváltozós kifejezés adott helyen
vett behelyettesítési értékét számítja. A kifejezést egy olyan Prolog
adatstruktúrával adjuk meg, amely az `x' névkonstansból és számokból a `+',
`-' és `*' kétargumentumú operátorokkal épül fel.
% erteke(Kif, X, Ert): A Kif kifejezés értéke az x=X helyen Ert.
% :- pred erteke(univ::in, int::in, int::out).
Pluszfeladat: Oldja meg a fenti feladatot úgy, hogy megenged minden, az `is'
beépített eljárás által kezelt egy- ill. kétargumentumú műveletet.
| ?- erteke((x+1)*(x+1)-2*(x+1)+1, 4, E). E = 16
* Írjon egy olyan Prolog eljárást, amely egy tetszőleges Prolog névkonstans
(atom) esetén felsorolja a benne előforduló egész számokat. Pontosabban: az
eljárás megkeresi a névkonstanst alkotó karakterlista egy olyan folytonos
részét, amely csupa számjegyből áll és egyik irányba sem terjeszthető ki
számjeggyel. Visszaadja a számjegysorozat decimális számként vett értékét,
visszalépéskor felsorolva az összes ilyen számot.
% nevszam(Atom, E): E az Atom-ban előforduló egész szám.
% :- pred nevszam(atom::in, int::out).
| ?- nevszam('123 abc345-6', Sz). Sz = 123; Sz = 345; Sz = 6; no
* Írjon Prologban egy eljárást, amely egy tetszőleges Prolog kifejezésben
minden számot eggyel nagyobbra cserél. Vigyázat: a kifejezésben változók
is előfordulhatnak!
% novel(+Kif, ?Kif1): Kif1 ugyanolyan Prolog kifejezés mint Kif, csak
% minden szám helyett az eggyel nagyobb szám szerepel benne.
Példa: ?- novel(f(1, X, 2, [3,4]), Kif1).
válasz: Kif1 = f(2, X, 3, [4,5])
* A G irányítatlan gráfot az élek listájával adjuk meg, egy élet a
két végpontnak a '-' operátorjellel való összekapcsolásával
jelölünk (a két végpont sorrendje tetszőleges). A végpontokat Prolog
konstansok jelölik. Pl az [a-b,b-c,c-a] lista az abc háromszöget
jelöli.
Írjon egy olyan Prolog eljárást, amely megállapítja egy ily módon adott
gráf pontjainak fokszámát. (A gráf egy pontjának fokszáma a belőle kiinduló
élek száma.) Használjon jobbrekurziót.
% fokszamai(+G, ?FL): A G gráf pontjainak fokszámát az FL lista írja le,
% amelynek elemei Pont-Fokszám alakú párok. A gráf minden pontja pontosan
% egyszer szerepel FL-ben. Az FL lista elemeinek sorrendja érdektelen.
Példa: ?- fokszamai([a-b,b-d,c-b], FL). válasz: FL = [a-1,b-3,d-1,c-1].
* Írjon olyan Prolog eljárást, amely egy adott atomban keres egy abban
előforduló legalább kétkarakteres olyan folytonos részt, amely csupa
kisbetűből áll, és maximális, azaz egyik irányban sem terjeszthető ki
kisbetűvel! Az eljárás adja ki a megtalált részatom kezdő
indexpozicióját is (1-től számozva)! Visszalépéskor legyen hajlandó az
összes ilyen részatomot felsorolni!
% szava(Atom, Szo, Index): Az Atom atomban az Index kezdőpozición a Szo
% áll, amely csupa kisbetűből álló maximális, legalább kétbetűs atom.
% :- pred palindex(atom::in, atom::out, int::out).
| ?- szava('a gyogy* 6ott', S, I).
I = 3, S = gyogy; I = 11, S = ott; no
Könnyített feladat: eltekinthet a maximalitási feltételtől.
* Írjon Prologban egy eljárást, amely két, nem feltétlenül egyforma
hosszú lista elemeit összefésüli. Vigyázzon, hogy többszörös
megoldások ne fordulhassanak elő!
% kever(+L1, +L2, ?L): L1 és L2 listákelemeinek osszefésülése L.
Példák:
?- kever([a,b,c],[x,y,z], KL). válasz: KL = [a,x,b,y,c,z]
?- kever([a,b,c],[z], KL). válasz: KL = [a,z,b,c]
?- kever([a,b],[x,y,z], KL). válasz: KL = [a,x,b,y,z]
A második részben (felkészülési idő nélkül, legfeljebb rövid gondolkodás után) kiskérdésekre kell válaszolni (adott programrészlet működését elmagyarázni, típusegyenletet megoldani, Prolog-kifejezés gráfját felrajzolni, egy-egy beépített függvény, ill. eljárás működését ismertetni, egy-egy témakörről kiselőadást tartani stb.).
A Prolog vizsgán második feladatként kétféle azonnal megoldható feladatot adunk. Az első egy Mit nyomtat? feladat, a második egy Mi az eredménye? feladat.
Példák a ,,Mit nyomtat?'' feladatokra:
A. Mit ír ki az alábbi p eljárás, ha hívásakor paraméterként az Ön hatjegyű
(EEHHNN alaku) születési dátumát (pl ?-p(770321))? Indokolja meg miért
(írja le általánosan mit csinál az eljárás)!
Az eljárás típus-specifikációja mindegyik esetben:
% :- pred p(int::in).
Az alábbiakhoz feltételezzük, hogy a `lists' könyvtár be van töltve:
:- use_module(library(lists)).
továbbá, hogy a `between/3' eljárás definiálva van.
1.
p(N) :-
write(N), nl,
number_codes(N, NL),
findall(A, (member(A, NL), A > 0'4), AL),
reverse(AL, [U,V|_]), !,
put_code(V), put_code(U), nl.
p(_N) :-
write('nem megy'), nl.
2.
p(N) :-
write(N), nl,
number_chars(N, NL),
reverse(NL, [_,DC|_]),
number_chars(D, [DC]),
length(L, D), append(L, [E|_], NL),
put_char(E), nl.
3.
p(N) :-
write(N), nl,
number_codes(N, NL),
append(_, [A|BL], NL),
put_ccode(A),
BL = [B|_], B > A, !, nl.
p(_) :-
write(' vege'), nl.
4.
p(N) :-
write(N), nl,
number_codes(N, [E|NL]),
member(H, NL),
H < E, !,
put_code(E), nl.
p(_) :-
write('nem megy'), nl.
5.
p(N):-
write(N), nl,
number_codes(N, NL),
append(_, [A,B|L], NL),
( A mod 2 =:= B mod 2 -> true
; L = []
),
put_code(A), put_code(B), nl, !.
6.
p(N):-
write(N), nl,
number_chars(N, [_,A|NL]),
append(L, [B|_], NL),
number_chars(AB, [A,B]),
( L = []
; AB mod 3 =:= 0
),
write(AB), nl, fail.
p(_).
7.
p(N) :-
write(N), nl,
number_chars(N, [_,_,_|NL]),
append(L, [_], NL),
number_chars(M, L),
between(M, 100, I),
I mod 3 =:= 0, !,
write(I), nl.
p(_) :-
write('nem megy'), nl.
8.
p(N) :-
write(N), nl,
number_codes(N, NL),
reverse(NL, [_,A|_]),
member(X, [A|NL]), X < 0'3,
put_code(X), fail.
p(_N) :-
nl.
9.
p(N) :-
write(N), nl,
number_codes(N, [_|L]),
L1=[_|_],
append(L1, [C,_|_], L),
number_codes(N1, L1),
D is C-0'0,
write(N1-D), nl, fail.
p(_).
10.
p(N) :-
write(N), nl,
number_codes(N, [_|L]),
append(_, [C1,C2|L1], L),
C1 < C2, !, number_codes(N1, L1),
write(N1), nl.
p(_) :-
write('nem megy'), nl.
Példák a ,,Mi az eredménye?'' feladatokra:
B. Írja mindegyik Prolog cél mellé annak futási eredményét (siker,
meghiúsulás, vagy hiba). Sikeres futás esetén adja meg az X változó
értékét. Mindegyik célt a Prolog interpreternek önmagában adjuk oda,
azaz futásának kezdetén a célban előforduló változóknak nincs
értéke. Feltételezzük, hogy a `lists' könyvtár be van töltve.
?- 4*3 is X, X is 3*4.
?- append([], L, X), var(X).
?- X is 5//4, X == 5//4.
?- U is 21/5, (U < 4 -> X is 4-U ; X is U-4).
?- a+b+c =.. X.
?- atom_chars(abc, [U|V]), atom_chars(X, V).
?- X is +(1,2), X =:= 10//3.
?- member(X, [1,2,3]), !, X > 2.
?- atom_codes(X, [0'7,0'0]).
?- arg(2, [1], X).
?- X =.. [1,2,3].
?- X = 8//3.
?- number_chars(1+2, X).
?- functor([1], F, X).
?- append([1], U, X), f(1) =.. U.
?- findall(V, (member(V,[9,7,0,1,2,4]), V>3), X).
?- X = [1,2,3], arg(2, X, 2).
?- X =:= 7//3.
?- X is 2*3, X == 3*2.
?- atom_chars(haho, [A|U]), reverse(U, R), atom_chars(X, [A|R]).
?- append(X, [1|U], [3,2,1]).
?- length(X, 1), arg(1, X, 2).
?- 1+2*3 =.. [F|X].
A harmadik részben a felkészülési idő alatt megírt programokhoz kell magyarázatot, kiegészítést fűzni, ill. a vizsgáztatónak a programokra vonatkozó kérdéseire válaszolni.
A vizsga első három részben max. 70 pont szerezhető.
Végül a negyedik részben a hallgatónak a zh-ra, ill. az nhf-re vonatkozó kérdésekre kell válaszolnia, ha írt zh-t, ill. adott be nhf-et. Ha a válaszok nem kielégítőek, a zh-ra, ill. az nhf-re kapott pontszámot nem vesszük figyelembe az osztályzatban.