BME Villamosmérnöki és Informatikai Kar
Műszaki informatika szak
Nappali tagozat
2006/2007. tanév, tavaszi félév

Deklaratív programozás

1. kis házi feladat: atfedok

1.3 változat
Utolsó módosítás: 2007-03-17

A feladat

Adott egy ts = [t0, t1, ..., tz-1] szólista, ahol 0 ≤ z. Válogassa ki ts-ből azokat a (ti,tj) szópárokat, amelyekre 0 ≤ i < z, 0 ≤ j < z, i ≠ j és 0 ≤ k mellett teljesül, hogy a ti utolsó k karaktere megegyezik a tj első k karakterével. (Az ilyen szópárokat a továbbiakban k helyen átfedőnek vagy röviden k-átfedőnek nevezzük.)

Precízebben: Jelöljük a ti karaktereit a ci0 ci1 ... cim-1, a tj karaktereit pedig a cj0 cj1 ... cjn-1 azonosítókkal. Elő kell állítani az összes olyan (ti,tj) párt, amelyekre 0 ≤ k és i ≠ j mellett a cim-k = cj0, cim-k+1 = cj1, ..., cim-1 = cjk-1 feltételek mind teljesülnek.

A k-nál rövidebb szavakat értelemszerűen ki kell hagyni a felsorolásból.

SML-specifikációk

Írjon SML-függvényt atfedok néven, amely egy füzérlista elemeinek párosításával előállítható összes k-átfedő füzérpár listáját adja eredményül (tetszőleges sorrendben). 
(* atfedok : int -> string list -> (string * string) list
   atfedok k ts = a ts lista k helyen átfedő elemeinek összes
                  lehetséges párosítását tartalmazó lista
*)

Prolog-specifikációk

Írjon Prolog-eljárást atfedok/3 néven, amely egy névkonstans-lista elemeinek párosításával előállítható összes k-átfedő névkonstans-pár listáját előállítja (tetszőleges sorrendben). 
% :- type szolista    == list(atom).
% :- type atfedes     == int.
% :- type szopar      ---> atom-atom.
% :- type szoparlista ---> list(szopar).
% :- pred atfedok(szolista::in, atfedes::in, szoparlista::out)

% atfedok(K,L1,L2), ahol L2 az L1 lista K helyen átfedő elemeinek
%                   összes lehetséges párosítását tartalmazó lista

Példák

atfedok 2 ["alma","omlik","mama","malom","ikra","atom","adat","ragad"] =
    [("alma", "malom"), ("alma", "mama"), ("atom", "omlik"), ("omlik", "ikra"),
     ("malom", "omlik"), ("mama", "malom"), ("ikra", "ragad"),
     ("adat", "atom"), ("ragad", "adat")]

atfedok 3 ["alma","omlik","mama","malom","ikra","atom","adat","ragad"] =
    []

atfedok 1 ["alma","omlik","mama","malom","ikra","atom","adat","ragad"] =
    [("alma", "adat"), ("alma", "atom"), ("ikra", "alma"), ("mama", "alma"),
     ("mama", "adat"), ("mama", "atom"), ("atom", "mama"), ("malom", "mama"),
     ("atom", "malom"), ("ikra", "adat"), ("ikra", "atom")]

atfedok 2 ["aa", "aa"] = [("aa", "aa"), ("aa", "aa")]

atfedok 3 ["aa", "aa"] = []


?- atfedok(2,[alma,omlik,mama,malom,ikra,atom,adat,ragad],L).
L = [alma-mama,alma-malom,malom-omlik,omlik-ikra,atom-omlik,mama-malom,ikra-ragad,adat-atom,ragad-adat] ;
no

?- atfedok(3,[alma,omlik,mama,malom,ikra,atom,adat,ragad],L).
L = [] ;
no

?- atfedok(1,[alma,omlik,mama,malom,ikra,atom,adat,ragad],L).
L =
[alma-atom,alma-adat,mama-alma,mama-atom,mama-adat,malom-mama,ikra-alma,
ikra-atom,ikra-adat,atom-mama,atom-malom] ;
no

?- atfedok(2,[aa,aa],L).
L = [aa-aa,aa-aa] ;
no

?- atfedok(3,[aa,aa],L).
L = [] ;
no

Tudnivalók a beadásról

A programot az Elektronikus Tanársegéddel kell beadni, a HF beadás menüpont alatt, atfedok.sml, illetve atfedok.plnéven. Az új beadási határidő (2007. március 31., szombat helyett) 2007. április 2., hétfő 24:00.

A vizsgaosztályzat megállapításakor a határidőre beadott, helyesen megoldott kis házi feladatokért plusz 1-1 pont jár.

Részfeladatok, további feladat

Részfeladatok

  1. Predikátum két (karakter)lista k-átfedő voltának vizsgálatára.
  2. Olyan Prolog-eljárás, amely kérésre visszalépéssel felsorolja a k-átfedő szópárokat.
  3. Olyan SML-függvény, amely egy adott szóból és egy szólista elemeiből képezhető összes k-átfedő párok listáját adja eredményül.

További feladat

  1. Függvény/eljárás a legalább 1, legfeljebb k helyen átfedő szópárok listájának előállítására. (Az ilyen szópárokat maxk helyen átfedőnek vagy röviden maxk-átfedőnek nevezhetjük.)
dp@inf.bme.hu