| BME Villamosmérnöki és Informatikai Kar
Műszaki informatika szak |
Nappali tagozat
2005/2006-os tanév, tavaszi félév
|
A programok módosított beadási határideje 2006. május 15., hétfő, 24h. az elektronikus dokumentációé 2006. május 17., szerda, 24h.
Ez a leírás a Deklaratív programozás c. tárgyból kiadott féléves házi feladatot ismerteti.
Nevezzünk térképnek egy n*m mezőből álló, téglalap alakú
táblát, amelynek mezői az alábbi "tereptárgyak" egyikéhez tartoznak, azaz
az alábbi típusúak lehetnek:
A forrás, a tó és a tetszőleges számú kikötő mindegyike csak egyetlen mezőből állhat. A folyót egymással összefüggő mezők alkotják. A többi mező a réthez tartozik. Forrásból, tóból és folyóból csak egy, kikötőből és rétből több is lehet. A feladat az, hogy egy részlegesen kitöltött térképen (azaz amelyen nincs minden mező típusa megadva) meghatározzuk a vizes, azaz a forrás, folyó és tó típusú mezőket úgy, hogy az alábbi feltételek teljesüljenek:
A feladványban az összes kikötő típusú mező helyét előre megadjuk, a többi mező típusát pedig vagy megadjuk, vagy nem. A feltételekből következik, hogy a megoldásban legalább három vizes mezőnek kell lennie: a forrás és a tó mellett legalább egy mezőnek a folyóhoz kell tartoznia. Minden feladványnak természetesen több megoldása is lehet.
Az 1. ábra egy feladványt ábrázol, a 2. ábra ennek (egyetlen) megoldását mutatja. Jelölések: F = forrás, T = tó, @ = folyó, számjegy = adott befogadóképességű kikötő, R = rét, üres négyzet = ismeretlen mező a feladványban, réthez tartozó mező a megoldásban.
+---+---+---+---+---+ | | 3 | | | | +---+---+---+---+---+ | T | | | R | | +---+---+---+---+---+ | | | | | @ | +---+---+---+---+---+ | F | | 6 | | | +---+---+---+---+---+ | | | | | | +---+---+---+---+---+ |
+---+---+---+---+---+ | | 3 | | | | +---+---+---+---+---+ | T | @ | @ | R | | +---+---+---+---+---+ | | | @ | @ | @ | +---+---+---+---+---+ | F | @ | 6 | | @ | +---+---+---+---+---+ | | @ | @ | @ | @ | +---+---+---+---+---+ |
|
1. ábra. Egy feladvány (n=5, m=5)
|
2. ábra. A feladvány egyetlen megoldása |
Írjon folyo 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(S-O,MezoL)
felépítésű struktúra, ahol
S és O a tábla mérete, azaz
sorainak és oszlopainak a száma (a tábla bal felső mezője az első sor
első oszlopában van).MezoL az ismert típusú mezők listája, ahol a lista
m(Sor,Oszlop,Tipus) alakú elemekből áll. Ezek
határozzák meg a mezők pozícióját és típusát. A lista
lexikografikusan rendezett, Tipus lehetséges
értékei pedig:
folyoforrastoretkikoto(N), ahol N egy 1 és 7 közötti
egész számAz 1. ábrán bemutatott feladvány esetén például a Prolog-eljárás bemenő paramétere:
f(5-5, [m(1,2,kikoto(3)),m(2,1,to),m(2,4,ret),m(3,5,folyo),m(4,1,forras),m(4,3,kikoto(6))])
A Prolog-eljárás kimenő paramétere a forrástól a tóig vezető vizes mezők koordinátáinak a listája (a forrást és a tavat is beleértve).
A 2. ábrán látható megoldást írja le az alábbi lista:
[4-1,4-2,5-2,5-3,5-4,5-5,4-5,3-5,3-4,3-3,2-3,2-2,2-1]
Az SML-függvény paramétere egy ((S,O), MezoL)
pár, ahol S és O jelentése azonos a
Prolog-eljárásnál leírtakkal, MezoL pedig egy
(Sor,Oszlop,Tipus) hármasokból álló lista, ahol
Sor, Oszlop és Tipus jelentése
szintén azonos a Prolog-eljárásnál leírtakkal.
A Tipus paraméter mtipus típusú értéke ötféle
lehet az alábbi deklaráció szerint:
datatype mtipus = Folyo | Forras | To | Ret | Kikoto of int
Az 1. ábrán bemutatott feladvány esetén például az SML-függvény paramétere:
((5,5), [(1,2,Kikoto 3),(2,1,To),(2,4,Ret),(3,5,Folyo),(4,1,Forras),(4,3,Kikoto 6)])
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 feladványnak nincs megoldása, az eredmény az üres lista. Egy megoldást a koordinátapárok (kettesek) listájaként kell megadni, a Prolog-megoldáshoz hasonlóan.
A 2. ábrán látható megoldást írja le az alábbi (egyelemű) megoldás-lista:
[[(4,1),(4,2),(5,2),(5,3),(5,4),(5,5),(4,5),(3,5),(3,4),(3,3),(2,3),(2,2),(2,1)]]
A folyo/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 folyoterkep ---> f(meret, list(mezo)).
% :- type mezo ---> m(sor, oszlop, mezo_tipus).
% :- type mezo_tipus ---> folyo ; forras ; to ; ret ; kikoto(dokkszam).
% :- type sor == integer.
% :- type oszlop == integer.
% :- type dokkszam == integer.
% :- type pont ---> sor-oszlop.
% :- type meret ---> sor-oszlop.
% :- type folyovonal == list(pont).
% :- pred folyo(folyoterkep::in, folyovonal::out).
A folyo/2 eljárás első, folyoterkep típusú
paramétere mindenképpen kielégíti az alábbi feltételt:
helyes_feladvany(f(Meret,MezoL)) :- % a tábla méretezése helyes: helyes_pont(Meret,inf-inf), % nincs nem helyes eleme a MezoL listának: \+ ( member(Mezo, MezoL), \+ helyes_mezo(Mezo, Meret) ), % a forrás és a tó (ha meg vannak adva) nem lehetnek élszomszédosak, % azaz távolságuk nagyobb 1-nél: ( member(m(SF,OF,forras),MezoL), member(m(ST,OT,to),MezoL) -> tavolsaga(SF-OF, ST-OT, Tav), Tav > 1 ; true ), % nincs két forrás a listában: ( select(m(_,_,forras),MezoL,MezoLF) -> \+ member(m(_,_,forras),MezoLF) ; true ), % nincs két tó a listában: ( select(m(_,_,to),MezoL,MezoLT) -> \+ member(m(_,_,to),MezoLT) ; true ), % a MezoL lista lexikografikusan rendezett: sort(MezoL, MezoL), % a MezoL lista minden eleme különböző (Sor,Oszlop) % koordinátára vonatkozik (a rendezettség miatt elegendő ezt a % szomszédos elemekre kikötni): \+ append(_, [p(S,O,_),p(S,O,_)|_], MezoL). helyes_pont(S-O, MaxS-MaxO) :- integer(S), S >=1, S =< MaxS, integer(O), O >=1, O =< MaxO. tavolsaga(S1-O1, S2-O2, T) :- T is sqrt( (S1-S2)**2 + (O1-O2)**2 ). helyes_mezo(m(S,O,Tipus),Meret) :- helyes_pont(S-O,Meret), helyes_tipus(Tipus). helyes_tipus(folyo). helyes_tipus(forras). helyes_tipus(to). helyes_tipus(ret). helyes_tipus(kikoto(N)) :- integer(N), N >= 1, N =< 7.
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 folyo - teljes nevén Folyo.folyo - 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 TFolyo = struct type sor = int (* 0 < sor *) type oszlop = int (* 0 < oszlop *) type dokkszam = int (* 1 <= dokkszam <= 7 *) datatype mtipus = Folyo | Forras | To | Ret | Kikoto of dokkszam type pont = sor * oszlop type meret = sor * oszlop type mezo = sor * oszlop * mtipus type folyoterkep = meret * mezo list type folyovonal = pont list end signature Folyo = sig val folyo : TFolyo.folyoterkep -> TFolyo.folyovonal list end
A Folyo.folyo függvény Tfolyo.folyoterkep típusú
paramétere mindenképpen kielégíti az alábbi feltételt:
app load ["Listsort", "Math", "TFolyo"]; open TFolyo; (* helyes feladvany : folyoterkep -> bool *) fun helyes_feladvany (Meret, MezoL) = let val (MaxS, MaxO) = Meret fun helyes_pont (Sor, Oszlop) = 1 <= Sor andalso 1 <= Oszlop andalso Sor <= MaxS andalso Oszlop <= MaxO fun helyes_tipus (Kikoto n) = 1 <= n andalso n <= 7 | helyes_tipus _ = true fun helyes_mezo (Sor, Oszlop, Tipus) = helyes_pont (Sor, Oszlop) andalso helyes_tipus Tipus fun tavolsag (SOME (S1, O1), SOME (S2, O2)) = Math.sqrt(Math.pow(real(S1)-real(S2),2.0)+ Math.pow(real(O1)-real(O2),2.0)) | tavolsag _ = 10e6 fun lexikografikusan_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 szomszedok_kulonbozok (rp1::(rps as rp2::_)) = lexikografikusan_hasonlit (rp1, rp2) <> EQUAL andalso szomszedok_kulonbozok rps | szomszedok_kulonbozok _ = true fun forras (_, _, Forras) = true | forras _ = false fun to (_, _, To) = true | to _ = false fun coords (SOME (S, O, _)) = SOME (S, O) | coords NONE = NONE in (* a tábla méretezése helyes: *) 1 <= MaxS andalso 1 <= MaxO andalso (* a MezoL lista minden eleme helyes: *) (List.all (fn x => x) (map helyes_mezo MezoL)) andalso (* a forrás és a tó csak a sarkukkal érintkezhet: *) tavolsag(coords (List.find forras MezoL), coords (List.find to MezoL)) > 1.0 andalso (* nincs két forrás a listában: *) List.length (List.filter forras MezoL) < 2 andalso (* nincs két tó a listában: *) List.length (List.filter to MezoL) < 2 andalso (* a MezoL lista lexikografikusan rendezett: *) Listsort.sorted lexikografikusan_hasonlit MezoL andalso (* a MezoL lista minden eleme különböző (Sor,Oszlop) koordinátára vonatkozik (a rendezettség miatt elegendő ezt a szomszédos elemekre kikötni): *) szomszedok_kulonbozok MezoL end
Az SML megoldásában tehát feltételezheti, hogy a bemenő argumentumra a
helyes_feladvany predikátum 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 hamarosan 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 tábla sorainak és oszlopainak száma szerepel, az ezt követő sorok
mindegyike pedig két számmal kezdődik, amelyek az adott mező sor- és
oszlopszámát adják meg. Ezután a mező típusa következik, amely a
folyo, forras, to, ret
vagy kikoto szavak egyike lehet. Kikötő esetében a sor végén
egy további szám is áll: a kikötő befogadóképessége. A mezőkre 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 kikötők befogadóképessége 1 és 7 közé esik, és a
sorok lexikografikusan rendezve vannak (ld. 3. ábra, vö. 1. ábra).
5 5 1 2 kikoto 3 2 1 to 2 4 ret 3 5 folyo 4 1 forras 4 3 kikoto 6 |
| 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 a következő öt eljárást exportálja:
helyes_feladvany(folyoterkep::in)folyo_be(file::in, folyoterkep::out)folyo_ki(file::in, folyoterkep::in, folyovonal::in)megold(file::in, file::in)folyo/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
folyo.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. Példa:
SICStus 3.12.2 (x86-linux-glibc2.3): Sun May 29 11:59:09 CEST 2005 Licensed to BUTE-DP-course | ?- [kfolyo]. % consulting d:/dokumentumok/bme/deklapo/06s/kfolyo.pl... % module folyo_keret imported into user % loading e:/programozas/sicstus/library/lists.po... % module lists imported into folyo_keret % loaded e:/programozas/sicstus/library/lists.po in module lists, 15 msec 11688 bytes % consulted d:/dokumentumok/bme/deklapo/06s/kfolyo.pl in module folyo_keret, 15 msec 29792 bytes yes | ?- stopper(..., ...).
A stopper/2, ill. megold/2 eljárások meghívása a
folyo.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 a következő négy függvényt exportálja:
signature KFolyo = sig val helyes_feladvany : TFolyo.folyoterkep -> bool val folyo_be : string -> TFolyo.folyoterkep val folyo_ki : string * TFolyo.folyoterkep * TFolyo.folyovonal list -> unit val megold : string * string -> string end
helyes_feladvany ftft folyótérkép helyességét vizsgáló, fent ismertetett
feladványellenőrző függvény.folyo_be ff szöveges állományból beolvasott adatokból képzett
folyótérkép.folyo_ki(m, ft, fvk)ft folyótérkép fvk 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ását az m szöveges
állományba. Ehhez természetesen szüksége van a
Folyo.folyo függvényre. Eredménye az f nevet, 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/Windows
alatt mindkét esetben a con állománynév megadásával.
Használat: először fordítsa le az összes modult, belértve
a folyo függvényt megvalósító
Folyo.sml nevű saját programját is az alábbi
paranccsal:
mosmlc -c TFolyo.sml Folyo.sig Folyo.sml KFolyo.sig KFolyo.sml
Ezután töltse be az interpreterbe és nyissa meg a KFolyo
modult:
Moscow ML version 2.01 (January 2004) Enter `quit();' to quit. - load "KFolyo"; > val it = () : unit - open KFolyo; > val helyes_feladvany = fn : (int * int) * (int * int * mtipus) list -> bool val folyo_be = fn : string -> (int * int) * (int * int * mtipus) list val megold = fn : string * string -> string val folyo_ki = fn : string * ((int * int) * (int * int * mtipus) list) * (int * int) list list -> unit - megold (..., ...);
A saját programja módosításakor elegendő a Folyo.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. az 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, PDF, esetleg ASCII formátumban.
A programok készülhetnek MS Windows alatt is, de Linux alatt is működniük kell. A beadott programokat Linux környezetben a SICStus Prolog 3.12.x, ill. az MOSML 2.01 rendszerekkel teszteljük.
A programokat és az elektronikus dokumentációt webes felületen lehet majd külön-külön feltölteni az Elektronikus Tanársegéd HF beadás menüpontjában. Programját egy tízelemű tesztsorozattal automatikusan futtatjuk, és erről válaszlevélben értesítjük. A beadást többször is megismételheti, az utoljára beadott megoldást tekintjük érvényesnek.
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 teszteseteket úgy választottuk meg, 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 módosított beadási határideje 2006. május 15., hétfő, 24h. az elektronikus dokumentációé 2006. május 17., szerda, 24h.
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étraversenyben 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.