|
BME Villamosmérnöki és Informatikai Kar
Műszaki informatika szak
|
Nappali tagozat
2003/2004-es tanév, tavaszi félév
|
Ez a leírás a Deklaratív programozás c. tárgyból kiadott féléves házi feladatot ismerteti.
Adott egy n*m mezőből álló téglalap, amely egy
radarernyőt ábrázol. A radarral felhőket figyelünk
meg, a radarernyő minden mezője vagy egy felhőhöz, vagy
a tiszta égbolthoz tartozik. Az alábbi feltételek mindig teljesülnek:
Az 1. ábra egy feladványt ábrázol, a 2. ábra ennek (egyetlen) megoldását mutatja. Az ábrán minden sorhoz és oszlophoz megadtunk egy számot. Ha ez a szám pozitív, akkor a felhős mezők számát adja meg, míg a -1 érték azt jelzi, hogy az adott sorról, ill. oszlopról nincs információ. Jelölések: # felhős mező; . felhőtlen mező.
+---+---+---+---+---+
| | | | | | 4
+---+---+---+---+---+
| | | | | . | 4
+---+---+---+---+---+
| | | | | | 0
+---+---+---+---+---+
| | # | | | | -1
+---+---+---+---+---+
| | | | | | 4
+---+---+---+---+---+
4 4 -1 4 2
|
+---+---+---+---+---+
| # | # | # | # | . | 4
+---+---+---+---+---+
| # | # | # | # | . | 4
+---+---+---+---+---+
| . | . | . | . | . | 0
+---+---+---+---+---+
| # | # | . | # | # | -1
+---+---+---+---+---+
| # | # | . | # | # | 4
+---+---+---+---+---+
4 4 -1 4 2
|
|
1. ábra. Egy feladvány (n=5, m=5) |
2. ábra. A feladvány megoldása |
Írjon felhok néven olyan Prolog-eljárást,
ill. SML-függvényt, amely egy feladvány összes megoldását előállítja!
A Prolog-eljárásnak két paramétere van. Első (bemenő) paramétere a feladványt, második (kimenő) paramétere a megoldást írja le. Az eljárásnak a visszalépések során minden megoldást pontosan egyszer kell kiadnia. Ha a feladványnak nincs megoldása, az eljárás hiúsuljon meg.
A Prolog-eljárás bemenő paramétere egy
f(SOL, OOL, RefPL)
felépítésű struktúra, ahol
SOL a sorösszeg-lista, azaz a tábla soraiban lévő
felhős mezők száma az első sortól kezdve (hossza egyben megadja a tábla magasságát);
OOL az oszlopösszeg-lista, azaz a tábla oszlopaiban lévő
felhős mezők száma az első oszloptól kezdve (hossza egyben megadja a tábla szélességét);
RefPL a referenciapontok (esetleg üres) listája, amelynek
elemei f(Sor,Oszlop)
vagy e(Sor, Oszlop) alakúak.
Az első jelentése az, hogy a (Sor,Oszlop) koordinátájú mező felhős, a másodiké pedig az,
hogy a mező felhőtlen (azaz ott az ég látszik, ezért használjuk a
e(...) jelölést). A lista a sor-oszlop párok szerint
lexikografikusan rendezve van.
Az 1. ábrán bemutatott feladvány esetén például a Prolog-eljárás bemenő paramétere:
f([4,4,0,-1,4], [4,4,-1,4,2], [e(2,5), f(4,2)])
A Prolog-eljárás kimenő paramétere az eredményt egy felhőlista formájában adja meg,
a lista elemei egy-egy felhőt írnak le f(KS, KO,
ZS, ZO) alakban,
ahol a felhő a KS..ZS sorok és a KO..ZO oszlopok metszete.
A 2. ábrán látható megoldást írja le az alábbi lista:
[f(1,1,2,4), f(4,1,5,2), f(4,4,5,5)]
Az SML-függvény paramétere egy (SOL, OOL,
RefPL) hármas, ahol SOL, OOL és RefPL
jelentése azonos a Prolog-eljárásnál leírtakkal.
Az 1. ábrán bemutatott feladvány esetén például az SML-függvény paramétere:
([4,4,0,~1,4], [4,4,~1,4,2], [e(2,5), f(4,2)])
Az SML-függvény eredménye egy olyan lista, amely a
feladvány összes megoldását tartalmazza, mégpedig minden
megoldást pontosan egyszer. Ha a feladatnak nincs megoldása, az eredmény az
üres lista. Egy-egy megoldást a felhők - (KS, KO,
ZS, ZO) négyesek - listájaként kell
megadni, a Prolog-megoldáshoz hasonlóan.
A 2. ábrán látható megoldást írja le például az alábbi (egyelemű) megoldás-lista:
[[(1,1,2,4), (4,1,5,2), (4,4,5,5)]]
A felhok/2 Prolog-eljárás paramétereinek típusát a
következő - megjegyzésként megadott -
Prolog-típusdefiníciók írják le.
% :- type radarkep ---> f(list(sorosszeg), list(oszloposszeg), list(ref_pont)).
% :- type sorosszeg == integer.
% :- type oszloposszeg == integer.
% :- type ref_pont ---> f(sor, oszlop) | e(sor, oszlop).
% :- type sor == integer.
% :- type oszlop == integer.
% :- type felhok == list(felho).
% :- type felho ---> f(kezdosor, kezdooszlop, zarosor, zarooszlop).
% :- type kezdosor == sor.
% :- type kezdooszlop == oszlop.
% :- type zarosor == sor.
% :- type zarooszlop == oszlop.
% :- pred felhok(radarkep::in, felhok::out).
A felhok/2 eljárás első, radarkep típusú
paramétere mindenképpen kielégíti az alábbi feltételt:
helyes_feladvany(f(SorOsszegek, OszlopOsszegek, RefPL)) :- length(SorOsszegek, N), length(OszlopOsszegek, M), % a referenciapontok koordinátáinak KoordL listája % az eredetivel azonos sorrendű, ahol minden % referenciapont eget vagy felhőt jelöl: koordinatak(RefPL, KoordL), % az összegek legkisebb értéke -1 lehet, % de nem haladhatják meg a tábla méretét: forall( member(S, SorOsszegek), (-1 =< S, S =< M) ), forall( member(O, OszlopOsszegek), (-1 =< O, O =< N) ), % a KoordL lista minden eleme helyes: forall( member(Koord, KoordL), helyes_koordinata(Koord, N-M) ), % a KoordL lista lexikografikusan rendezett; % ebből következően RefPL is: sort(KoordL, KoordL), % A KoordL lista bármely két eleme különböző; % ebből következően a RefPL listában szereplő % (Sor,Oszlop) koordináták is páronként különböznek % (a rendezettség miatt elegendő ezt a szomszédos elemekre kikötni): forall( append(_, [K1, K2|_], KoordL), K1 \= K2 ). koordinatak([], []). koordinatak([e(S,O)|RefPL], [S-O|KoordL]) :- koordinatak(RefPL, KoordL). koordinatak([f(S,O)|RefPL], [S-O|KoordL]) :- koordinatak(RefPL, KoordL). helyes_koordinata(S-O, MaxS-MaxO) :- integer(S), S > 0, S =< MaxS, integer(O), O > 0, O =< MaxO. % forall(Cél1, Cél2) : Cél1 minden megoldása teljesíti Cél2-t. forall(Goal1, Goal2) :- ( Goal1, \+ Goal2 -> fail ; true ).
A Prolog megoldásában tehát feltételezheti, hogy a bemenő argumentumra a
helyes_feladvany/1 eljárás sikeresen lefut (csak ilyen adattal
teszteljük majd a programot).
A felhok függvény paraméterének és eredményének
típusát a következő SML-típusdefiníciók írják le.
structure TFelhok = struct type sorosszeg = int type oszloposszeg = int type sor = int type oszlop = int datatype refpont = f of sor * oszlop | e of sor * oszlop type radarkep = sorosszeg list * oszloposszeg list * refpont list type kezdosor = int type kezdooszlop = int type zarosor = int type zarooszlop = int type felho = kezdosor * kezdooszlop * zarosor * zarooszlop type felhok = felho list end signature Felhok = sig val felhok : TFelhok.radarkep -> TFelhok.felhok list end
A Felhok.felhok függvény TFelhok.radarkep
típusú paramétere mindenképpen kielégíti az alábbi feltételt:
app load ["Listsort"]; fun helyes_feladvany ((SorOsszegek, OszlopOsszegek, RefPL) : TFelhok.radarkep) = let val n = length SorOsszegek val m = length OszlopOsszegek fun ref_pont_koord (TFelhok.f(Sor, Oszlop)) = (Sor, Oszlop) | ref_pont_koord (TFelhok.e(Sor, Oszlop)) = (Sor, Oszlop) fun helyes_koord (Sor, Oszlop) = Sor > 0 andalso Sor <= n andalso Oszlop > 0 andalso Oszlop <= m val helyes_ref_pont = helyes_koord o ref_pont_koord fun helyes_osszegek ((osszeg::osszegek), max) = osszeg > ~2 andalso osszeg <= max andalso helyes_osszegek (osszegek, max) | helyes_osszegek _ = true fun lexikogr_hasonlit ((x1,y1), (x2,y2)) = if x1 < x2 orelse x1 = x2 andalso y1 < y2 then LESS else if x1 > x2 orelse x1 = x2 andalso y1 > y2 then GREATER else EQUAL fun lexikografikusan_hasonlit (rp1, rp2) = lexikogr_hasonlit (ref_pont_koord rp1, ref_pont_koord rp2) fun szomszedok_kulonbozok (rp1::(rps as rp2::_)) = lexikografikusan_hasonlit (rp1, rp2) <> EQUAL andalso szomszedok_kulonbozok rps | szomszedok_kulonbozok _ = true in (* az összegek a megadott intervallumon belül vannak: *) helyes_osszegek (SorOsszegek, m) andalso helyes_osszegek (OszlopOsszegek, n) andalso (* a RefPL lista minden eleme helyes: *) (List.all (fn x => x) (map helyes_ref_pont RefPL)) andalso (* a RefPL lista lexikografikusan rendezett: *) Listsort.sorted lexikografikusan_hasonlit RefPL andalso (* a RefPL listában szereplő (Sor,Oszlop) koordináták páronként különböznek (a rendezettség miatt elegendő ezt a szomszédos elemekre kikötni): *) szomszedok_kulonbozok RefPL end
Az SML megoldásában tehát feltételezheti, hogy a bemenő argumentumra
a helyes_feladvany függvény igazat ad eredményül (csak ilyen
adattal teszteljük majd a programot).
Programjait keretprogramok segítségével próbálhatja ki. A keretprogramokat a specifikációs modulokkal és egy, a beadáskor használthoz hasonló tesztsorral együtt letöltheti innen. A házi feladatok teszteléséhez és értékeléséhez ezekkel kompatíbilis programokat fogunk használni.
A keretprogram bemenete egy olyan szöveges állomány, amelynek első
sorában a sorösszegek szerepelnek szóközzel elválasztva, második sorában
az oszlopösszegek hasonló módon. Az ezt követő sorok
mindegyikében egy betű és két szám áll, amelyek az adott referenciapont típusát,
valamint sor- és oszlopszámát határozzák meg. Ezekre a bejegyzésekre a már fent
említett korlátok vonatkoznak, tehát a sor- és oszlopszámok a táblán belüli
mezőt azonosítanak, a típust jelölő karakter pedig e vagy f
(ld. 3. ábra, vö. 1. ábra).
4 4 0 -1 4 4 4 -1 4 2 e 2 5 f 4 2 |
3. ábra. A bemenő állomány tartalma az 1. ábrán látható feladvány esetén
A keretprogram kimenete a 2. ábrán bemutatotthoz hasonló tartalmú szöveges állomány.
A Prolog-keretprogram öt eljárást exportál:
helyes_feladvany(radarkep::in)felhok_be(file::in, radarkep::out)felhok_ki(file::in, radarkep::in, felhok::in)megold(file::in, file::in)
felhok/2 eljárásra.
stopper(file::in, file::in) megold/2, de a futás végén kiírja a futási időt
is.
A keretprogram felhasználja a file típust:
% :- type file == atom.
A file típusú paraméterben a user atomot megadva
a terminálról vihetünk be, ill. a terminálra írathatunk ki adatokat.
Egyébként a megadott nevű állományba írunk, ill. állományból olvasunk.
Használat: a saját programját a felhok.pl
nevű állományba tegye, különben a keretprogram nem találja
meg. Ezután futtassa a SICStus interpretert, és töltse be a
keretprogramot:
SICStus 3.10.0 (x86-linux-glibc2.2): Thu Jun 27 22:46:49 CEST 2002 Licensed to BUTE DP course | ?- [kfelhok]. % consulting /home/david/uni/dp/04s/nhf/kfelhok.pl... % module felhok_keret imported into user % loading /usr/local/lib/sicstus-3.9.1/library/lists.po... % module lists imported into felhok_keret % loaded /usr/local/lib/sicstus-3.9.1/library/lists.po in module lists, 0 msec 11656 bytes % consulted /home/david/uni/dp/04s/nhf/kfelhok.pl in module felhok_keret, 20 msec 29168 bytes yes | ?- stopper(..., ...).
A stopper/2, ill. megold/2 eljárások meghívása
a felhok.pl programot automatikusan betölti (ha szükséges),
ezért ennek módosításakor nem kell sem a SICStus interpretert
újraindítania, sem a keretprogramot újra betöltenie.
Az SML-keretprogram négy függvényt exportál:
signature KFelhok = sig val helyes_feladvany : TFelhok.radarkep -> bool val felhok_be : string -> TFelhok.radarkep val felhok_ki : string * TFelhok.radarkep * TFelhok.felhok list -> unit val megold : string * string -> string end
helyes_feladvany rkfelhok_be f f szöveges állományból beolvasott adatokból képzett
radarkép.
felhok_ki(m, rk, fk) rk radarkép fk megoldáslistáját
olvasható formában kiírja az m szöveges állományba.
megold(f, m) f szöveges állományból és
kiírja az összes megoldást az m szöveges állományba.
Ehhez természetesen szüksége van a Felhok.felhok
függvényre. Eredménye az f nevét, a megoldások
számát és a futási időt mp-ben tartalmazó füzér.
A bemenetet, ill. a kimenetet a terminálra irányíthatjuk Unix alatt a
/dev/stdin, ill. a /dev/stdout, MS-DOS alatt
mindkét esetben a con állománynév megadásával.
Használat: először fordítsa le az összes modult,
beleértve a felhok függvényt megvalósító
Felhok.sml nevű saját programját is az alábbi paranccsal:
mosmlc -c TFelhok.sml Felhok.sig Felhok.sml KFelhok.sig KFelhok.sml
Ezután töltse be az interpreterbe és nyissa meg a KFelhok
modult:
Moscow ML version 2.00 (June 2000) Enter `quit();' to quit. - load "KFelhok"; > val it = () : unit - open KFelhok; > val helyes_feladvany = fn : TFelhok.radarkep -> bool val felhok_ki = fn : string * TFelhok.radarkep * TFelhok.felhok list -> unit val megold = fn : string * string -> string val felhok_be = fn : string -> TFelhok.radarkep - megold (..., ...);
A saját programja módosításakor elegendő a Felhok.sml
állományt újrafordítani, és célszerű az SML értelmezőt újraindítani.
Mindkét programot úgy írja meg (választása szerint vagy magyarul, vagy angolul), hogy a szövegük jól olvasható legyen: válasszon értelmes neveket, specifikálja a paraméterek és más azonosítók szerepét és értelmezési tartományát, magyarázza meg az egyes eljárások, ill. függvények feladatát és működését! Kövesse a Prolog, ill. SML jegyzetben látható szövegelrendezési szokásokat! Ne írjon 72 karakternél hosszabb sorokat! Minden eljáráshoz és függvényhez készítsen fejkommentet!
A két programhoz készítsen közös dokumentációt; vagy magyarul, vagy angolul. A dokumentáció tartalma legalább a következő legyen:
Fogalmazzon világosan és tömören, ügyeljen a helyes nyelvhasználatra és a helyesírási szabályok betartására! Az indokoltan elvárható formai követelmények be nem tartását, a gondatlan kivitelt szankcionáljuk.
A dokumentációt elektronikus alakban adja be, HTML, esetleg ASCII formátumban.
A programok készülhetnek MS DOS vagy MS Windows alatt is, de Unix (Linux) alatt is működniük kell. A beadott programokat Unix környezetben a SICStus Prolog 3.11.0, ill. az MOSML 2.00 rendszerekkel teszteljük.
A programokat és az elektronikus dokumentációt a webes felületen keresztül lehet külön-külön feltölteni az Elektronikus Tanársegéd HF beadás menüpontjában. Programját egy 10-elemű tesztsorozattal automatikusan futtatjuk, és erről válaszlevélben értesítjük. A beadást többször is megismételheti, a legutolsóként beadott megoldást értékeljük.
A házi feladat beadása nem kötelező, de a DP nyelvek magasszintű elsajátításához nagy segítséget ad. Ezért javasoljuk, hogy a házi feladatot mindkét nyelven készítsék el és adják be. Mindazonáltal elfogadunk csak SML, ill. csak Prolog nyelven készült megoldásokat, értelemszerűen felére csökkentett pontszámmal. A tesztesetek úgy vannak kialakítva, hogy 3-4 feladatot az egyszerű, algoritmikus ötletek nélküli programok is meg tudjanak oldani.
Figyelem! A jó jegyhez gyakorlatilag elengedhetetlen a házi feladat elkészítése.
A programok és az elektronikus dokumentáció végső beadási határideje 2004. május 3. hétfő, 24 óra.
Az értékeléshez a beadási tesztsorozathoz hasonló nehézségű teszteseteket fogunk használni. Az időkorláton belül helyes eredményt adó tesztesetek mindegyikére 0,5-0,5 pontot adunk. A 10 tesztesetre összesen tehát nyelvenként maximum 5 pontot kaphat. Ezen felül a dokumentációt, a programkód olvashatóságát, kommentezettségét is értékeljük, nyelvenként maximum 2,5 ponttal. Ha mindkét nyelvből beadja a házi feladatot, akkor tehát maximum 15 pontot kaphat (ez 15%-a a pluszpontok nélkül elérhető legfeljebb 100 alappontnak).
Azok a programok, amelyek az alapteszt minden feladatát helyesen és az előírt időkorláton belül megoldják, létraversenyen vesznek részt. A leggyorsabban futó SML-, ill. Prolog-programokra - helyezési számuktól függően - külön-külön 7,5 és 0,5 közötti pluszpont kapható. Ha valaki tehát mindkét nyelvből a leggyorsabb programot írja meg, akkor a 100 alapponton felül 15 pluszpontot kap.
A programot és dokumentációt mindenkinek saját magának kell elkészítenie. A beadott házi feladatokat gépi úton hasonlítjuk össze, másolás esetén a kódot adó és kapó hallgató sem kaphat pontot. Az algoritmusra vonatkozó ötletek cseréjét viszont nem tiltjuk.
Utolsó módosítás: 2004. 03. 17.