Programozási paradigmák, nagyzárthelyi, 1999. november 26. 15.30--17.00 Prolog, "A" csoport (30 pont) A Prolog-eljárás megírását kérő feladatokban a jegyzetben szereplő összes Prolog-eljárás (akár beépített, akár a jegyzetben definiált) szabadon használható. Ha segédeljárást definiál, feltétlenül adjon meg hozzá (deklaratív) fejkommentet, azaz specifikálja az eljárás típusát és írja le az eljárás paraméterei közötti kapcsolatot; enélkül a megoldás nem értékelhető, vagy csak csökkentett pontszámot kaphat. Törekedjék egyszerű, tömör és hatékony programozásra; használjon jobbrekurziót, kerülje a felesleges hívásokat. 1. Írja fel az alábbi kifejezések alapstruktúra-alakját (azaz szintaktikus édesítőszerek nélküli formáját) vagy rajzolja fel a hozzájuk tartozó fastruktúrákat! Állapítsa meg, hogy a két kifejezés egyesíthető-e, és ha igen, milyen behelyettesítéssel! (3 pont) .(A+C*A,[C]) [w+B,3] 2. Egy célsorozat keresési fája egy olyan irányított gráf, amelynek csúcsaiban célsorozatok vannak, és két csúcs között akkor megy él, ha a kiinduló csúcs célsorozatából egyetlen (Prolog) redukciós lépéssel eljuthatunk a cél-csúcs célsorozatába. Az élek a redukció során alkalmazott klóz sorszámával vannak címkézve. A fa gyökerében a teljes kiindulási célsorozat van, az üres célsorozatot egy négyzettel jelöljük. Rajzolja fel az alábbi célsorozat keresési fáját! A fa nem üres célsorozatot tartalmazó leveleinél jelezze a visszalépést! A select és a write szavakat rövidítheti (s, ill. w). (7 pont) | ?- select(A, [1,4,2,3], [1,B,3]), write(A-B). A select/3 eljárás definíciója: (1) select(E, [E|L], L). (2) select(E, [X|T], [X|L]) :- select(E, T, L). 3. Írjon olyan Prolog-eljárást, amely előfordulási (preorder) sorrendben felsorolja egy alább specifikált szerkezetű bináris fa páros elemeit! (7 pont) % :- type bfa ---> levél(int) ; ág(bfa, int, bfa). % :- pred páros(bfa::in, int::out). % páros(BFa, Elem): Elem a BFa bináris fa egy páros eleme. Példa: | ?- páros(ág(levél(8), 13, ág(levél(15), 18, levél(31))), E). E = 8 ? ; E = 18 ? ; no 4. Írjon olyan Prolog-eljárást, amely egy listába összegyűjti egy UNIX fájl tartalmát ábrázoló karakterkódlistában előforduló sorok hosszát! Egy sornak tekintjük az egymás melletti, 10-es (újsor) karakterkódtól különböző karakterek lehető leghosszabb (de esetleg üres) sorozatát. Így egy UNIX fájl sorainak száma 1-gyel több, mint a benne előforduló 10-es kódú karakterek száma (pl. egy üres fájlban 1 db 0 hosszú sor van). (13 pont) % :- pred sorhosszak(list(int)::in, list(int)::out). % sorhosszak(Karakterek, SorHosszak): SorHosszak a Karakterek % karakterkódlistában előforduló sorok hosszát tartalmazó lista. Példák: | ?- sorhosszak([97,10], Hk). Hk = [1,0] ? ; no | ?- L = "ab\n\na", sorhosszak(L, Hk). L = [97,98,10,10,97], Hk = [2,0,1] ? ; no Programozási paradigmák, nagyzárthelyi, 1999. november 26. 15.30--17.00 Standard ML, "A" csoport (30 pont) Az SML-függvény megírását kérő feladatokban a jegyzetben szereplő összes SML-függvény (akár beépített, akár a jegyzetben definiált) szabadon használható. Ha segédfüggvényt definiál, feltétlenül adjon meg hozzá (deklaratív) fejkommentet, azaz specifikálja a függvény típusát és írja le a függvény argumentumai és az eredménye közötti kapcsolatot; enélkül a megoldás nem értékelhető, vagy csak csökkentett pontszámot kaphat. Törekedjék egyszerű, tömör és hatékony programozásra; használjon jobbrekurziót, kerülje a felesleges hívásokat. 5. Deklaráljon SML-jelöléssel egy olyan bináris fát, amelynek a csomópontjaiban nincsenek értékek, a levelei pedig egész értéket tartalmaznak! Rajzoljon fel egy tetszőleges olyan bináris fát, amely az alábbi értékeket tartalmazza a megadott sorrendben balról jobbra haladva, majd írja le a fát a most deklarált új adattípus adatkonstruktoraival! (4 pont) Az ábrázolandó értékek sorozata: 4, 6, 8, 3, 11, 2 6. Írjon olyan SML-függvényt, amely egy egészlista első eleméből és a szomszédos elemeinek szorzatából álló listát ad eredményül (az eredeti sorrendet követve)! Használjon jobbrekurziót! (6 pont) (* szomszor zs = olyan lista, amelynek első eleme a zs egészlista első eleme, többi eleme pedig zs szomszédos elemeinek a szorzata az eredetivel egyező sorrendben szomszor : int list -> int list *) Példák: szomszor [4, 2, 3, 5, 7, 2, 9, 8] = [4, 8, 6, 15, 35, 14, 18, 72] szomszor [5] = [5] szomszor [] = [] 7. Mi a típusa az alábbi v1, v2, v3 SML-értékeknek? Az a)--c) deklarációk egymástól függetlenek, és a Real könyvtár be van töltve. (7 pont) a) val v1 = (("123.0", (~123.0-123.0)), (ord #"\123", real 123)) b) val v2 = fn (g, x, y) => (x g, y g) c) fun v3 ls = map (fn r => Real.toString r) ls 8. Írjon olyan SML-függvényt, amely egy listába összegyűjti egy UNIX fájl tartalmát ábrázoló karakterlistában előforduló sorok hosszát! Egy sornak tekintjük az egymás melletti, a #"\n" (újsor) karaktertől különböző karakterek lehető leghosszabb (de esetleg üres) sorozatát. Így egy UNIX fájl sorainak száma 1-gyel több, mint a benne előforduló #"\n" karakterek száma (pl. egy üres fájlban 1 db 0 hosszú sor van). (13 pont) (* sorhosszak cs = a cs karakterlistában előforduló sorok hosszát tartalmazó lista sorhosszak : char list -> int list *) Példák: sorhosszak [#"a", #"\n"] = [1, 0] sorhosszak(explode "ab\n\na") = [2, 0, 1] Programozási paradigmák, nagyzárthelyi, 1999. november 26. 15.30--17.00 Prolog, "B" csoport (30 pont) A Prolog-eljárás megírását kérő feladatokban a jegyzetben szereplő összes Prolog-eljárás (akár beépített, akár a jegyzetben definiált) szabadon használható. Ha segédeljárást definiál, feltétlenül adjon meg hozzá (deklaratív) fejkommentet, azaz specifikálja az eljárás típusát és írja le az eljárás paraméterei közötti kapcsolatot; enélkül a megoldás nem értékelhető, vagy csak csökkentett pontszámot kaphat. Törekedjék egyszerű, tömör és hatékony programozásra; használjon jobbrekurziót, kerülje a felesleges hívásokat. 1. Írja fel az alábbi kifejezések alapstruktúra-alakját (azaz szintaktikus édesítőszerek nélküli formáját) vagy rajzolja fel a hozzájuk tartozó fastruktúrákat! Állapítsa meg, hogy a két kifejezés egyesíthető-e, és ha igen, milyen behelyettesítéssel! (3 pont) f(2*A+B, [C], B*C) f(U+V, .(V,_), U) 2. Egy célsorozat keresési fája egy olyan irányított gráf, amelynek csúcsaiban célsorozatok vannak, és két csúcs között akkor megy él, ha a kiinduló csúcs célsorozatából egyetlen (Prolog) redukciós lépéssel eljuthatunk a cél-csúcs célsorozatába. Az élek a redukció során alkalmazott klóz sorszámával vannak címkézve. A fa gyökerében a teljes kiindulási célsorozat van, az üres célsorozatot egy négyzettel jelöljük. Rajzolja fel az alábbi célsorozat keresési fáját! A fa nem üres célsorozatot tartalmazó leveleinél jelezze a visszalépést! A select és a write szavakat rövidítheti (s ill. w). (7 pont) | ?- select(U, [b,c], V]), write(U-V). A select/3 eljárás definíciója: (1) select(E, [E|L], L). (2) select(E, [X|T], [X|L]) :- select(E, T, L). 3. Írjon olyan Prolog-eljárást, amely fordított előfordulási (postorder) sorrendben felsorolja egy alább specifikált szerkezetű bináris fa pozitív elemeit! (7 pont) % :- type bfa ---> levél(number) ; ág(bfa, number, bfa). % :- pred pozitív(bfa::in, number::out). % pozitív(BFa, Elem): Elem a BFa bináris fa egy pozitív eleme. Példa: | ?- pozitív(ág(levél(-8), 13, ág(levél(15), 0, levél(-31))), E). E = 15 ? ; E = 13 ? ; no 4. Írjon olyan Prolog-eljárást, amely egy listába összegyűjti egy negatív számokat nem tartalmozó egészlista szárazföldjeinek hosszát. Szárazföldnek a csupa pozitív számból álló, legalább 1 hosszú, maximális hosszúságú (semelyik irányba ki nem terjeszthető), folytonos részlistát nevezzük. (13 pont) % :- pred foldhosszak(list(int)::in, list(int)::out). % foldhosszak(Szamokk, FoldHosszak): FoldHosszak a Szamok % egészlistában előforduló szárazföldek hosszát tartalmazó lista. Példa: | ?- foldhosszak([0,1,0,3,4,0,0,1], H). H = [1,2,1] ? ; no Programozási paradigmák, nagyzárthelyi, 1999. november 26. 15.30--17.00 Standard ML, "B" csoport (30 pont) Az SML-függvény megírását kérő feladatokban a jegyzetben szereplő összes SML-függvény (akár beépített, akár a jegyzetben definiált) szabadon használható. Ha segédfüggvényt definiál, feltétlenül adjon meg hozzá (deklaratív) fejkommentet, azaz specifikálja a függvény típusát és írja le a függvény argumentumai és az eredménye közötti kapcsolatot; enélkül a megoldás nem értékelhető, vagy csak csökkentett pontszámot kaphat. Törekedjék egyszerű, tömör és hatékony programozásra; használjon jobbrekurziót, kerülje a felesleges hívásokat. 5. Deklaráljon SML-jelöléssel egy olyan bináris fát, amelynek csak a csomópontjaiban vannak egész értékek, a levelei pedig üresek! Rajzoljon fel egy olyan tetszőleges bináris fát, amely az alábbi értékeket tartalmazza a megadott sorrendben balról jobbra haladva, majd írja le a fát a most deklarált új adattípus adatkonstruktoraival! (4 pont) Az ábrázolandó értékek sorozata: 7, 3, 8, 13, 5, 15, 51 6. Írjon olyan SML-függvényt, amely egy egészlista utolsó eleméből és a szomszédos elemeinek szorzatából álló listát ad eredményül (az eredetivel ellenkező sorrendet követve)! Használjon jobbrekurziót! (6 pont) (* szomszor zs = olyan lista, amelynek első eleme zs utolsó eleme, többi eleme pedig a zs egészlista szomszédos elemeinek szorzata az eredetivel ellenkező sorrendben szomszor : int list -> int list *) Példák: szomszor [6, 2, 3, 5, 7, 2, 9, 8] = [8, 72, 18, 14, 35, 15, 6, 12] szomszor [5] = [5] szomszor [] = [] 7. Mi a típusa az alábbi v1, v2, v3 SML-értékeknek? Az a)--c) deklarációk egymástól függetlenek, és az Int könyvtár be van töltve. (7 pont) a) val v1 = ("123.0", ((~123.0-123.0), (ord #"\123"), floor 123.0)) b) val v2 = fn (g, x, y) => g y x c) fun v3 ls = map (fn r => explode(Int.toString r)) ls 8. Írjon olyan SML-függvényt, amely egy listába összegyűjti egy negatív számokat nem tartalmazó egészlista szárazföldjeinek hosszát. Szárazföldnek a csupa pozitív számból álló, legalább 1 hosszú, maximális hosszúságú (semelyik irányba ki nem terjeszthető), folytonos részlistát nevezzük. (13 pont) (* foldhosszak zs = a negatív számokat nem tartalmazó zs egészlistában előforduló szárazföldek hosszát tartalmazó lista foldhosszak : int list -> int list *) Példák: foldhosszak [0, 1, 0, 3, 4, 0, 0, 1] = [1, 2, 1] foldhosszak [0, 31, 5, 0, 30, 4, 10, 0, 0, 100] = [2, 3, 1]