BME Villamosmérnöki és Informatikai Kar
Mérnök-informatikus alapszak
Nappali tagozat
2016/2017-es tanév, őszi félév

Deklaratív programozás

1. kis házi feladat: Mátrix feldarabolása

1.0 változat
Utolsó módosítás: 2016-09-16
Kiadás: 2016-09-16
Beadási határidők a fõoldalon.

A feladat

A feladat egy mátrix kisebb mátrixokra való feldarabolása, és a kis mátrixok elemeit tartalmazó listák előállítása.

A feladat paramétere egy (R,C) számpár, ahol R, ill. C a kis mátrixok sorainak, ill. oszlopainak a számát adja meg.

Egy M mátrix (R,C) paraméterű feldarabolását a következőképpen végezzük el:

  1. Az első R sor után húzunk egy vízszintes elválasztó vonalat, majd minden további R sor után is.
  2. Az első C oszlop után húzunk egy függőleges elválasztó vonalat, majd minden további C oszlop után is.
  3. Az elválasztó vonalak által határolt minden egyes, nem üres kis mátrix elemeiből sorfolytonosan egy-egy listát képezünk.
  4. A kis mátrixok elemeiből az előző pont szerint képzett listákat egyetlen listába gyűjtjük össze, tetszőleges sorrendben.

Az így előállított listák listáját nevezzük az M mátrix (R,C) paraméterű feldarabolásának.

Írjon olyan Prolog-eljárást, illetve Erlang-függvényt, amely előállítja egy M mátrix (R,C) paraméterű feldarabolását!

A mátrixot – mindkét nyelven – sorok listájaként adjuk meg; az első listaelem felel meg a mátrix első sorának s.í.t. A mátrix minden egyes sorát az adott sorban levő mátrixelemek listájaként ábrázoljuk; a lista első eleme tartalmazza az adott sor első elemét s.í.t.

Feltételezheti (tehát nem kell ellenőriznie), hogy a mátrix minden sora azonos számú elemből áll; ezt a számot nevezzük a mátrix oszlopszámának. Feltételezheti, hogy a mátrix sorainak és oszlopainak a száma legalább 1. Végül feltételezheti, hogy a feldarabolás paraméterében megadott R és C mennyiségek pozitív egész számok (azaz R,C≥1).

A feldarabolás eredménye egy olyan lista, amelynek elemei a bemenetként megadott mátrix elemeiből képzett, nem üres listák. Az utóbbi listák hossza nem feltétlenül egyezik meg.

Prolog-specifikációk

Írjon Prolog-eljárást feldarabolasa/3 néven egy tetszőleges mátrix adott paraméterű feldarabolására! A mátrix elemei tetszőleges Prolog-kifejezések lehetnek.

A feldarabolás paraméterét a `-´ operátorral képzett R-C Prolog-kifejezéssel adjuk meg.

A feldarabolasa/3 első, bemenő argumentuma a mátrix, második, bemenő argumentuma a feldarabolás paramétere, míg harmadik, kimenő argumentuma a feldarabolás eredménye.

A feldarabolasa/3 eljárás argumentumaival kapcsolatos elvárásokat az alábbi típuskommentekben formálisan is leírjuk (a Mercury típusleíró nyelvének segítségével), majd megadjuk az eljárás fejkommentjét.

% :- type matrix == list(row).
% :- type row == list(any).
% :- type parameter ---> subRows-subCols.
% :- type subRows == int.
% :- type subCols == int.
% :- pred feldarabolasa(+matrix, +parameter, ?list(list(any))).
% feldarabolasa(Mx, P, LL): Az LL lista az Mx mátrix P paraméterű feldarabolása.

Erlang-specifikációk

Írjon Erlang-függvényt khf1:feldarabolasa/2 néven egy tetszőleges mátrix adott paraméterű feldarabolására!
%% @type matrix() = [row()].
%% @type row() = [any()].
%% @type parameter() = {subRows(), subCols()}.
%% @type subRows() = integer().
%% @type subCols() = integer().
%% @spec khf1:feldarabolasa(Mx::matrix(), P::parameter()) -> LL::[[any()]].
%%   Az LL lista az Mx mátrix P paraméterű feldarabolása.
A programot tartalmazó modul attribútumai ezek legyenek:
-module(khf1).
-author('email@unit.org.hu').
-vsn('year-mm-dd').
-export([feldarabolasa/2]).
%-compile(export_all).

Példák

Prolog

| ?- feldarabolasa([[a,b,  c,d],
                    [e,f,  g,h]], 2-2, LL).
LL = [[a,b,e,f],
      [c,d,g,h]] ? ;
no
| ?- feldarabolasa([[a,b,  c,d],
                    [e,f,  g,h],

		    [i,j,  k,l],
                    [m,n,  o,p]], 2-2, LL).
LL = [[a,b,e,f],
      [c,d,g,h],
      [i,j,m,n],
      [k,l,o,p]] ? ;
no
| ?- feldarabolasa([[a,b,c,  d],
                    [e,f,g,  h],
                    [i,j,k,  l],

                    [m,n,o,  p]], 3-3, LL).
LL = [[a,b,c,e,f,g,i,j,k],
      [d,h,l],
      [m,n,o],
      [p]] ? ;
no
| ?- feldarabolasa([[a,b,  c,d],
                    [e,f,  g,h],
		    [i,j,  k,l],

		    [m,n,  o,p]], 3-2, LL).
LL = [[a,b,e,f,i,j],
      [c,d,g,h,k,l],
      [m,n],
      [o,p]] ? ;
no
| ?- feldarabolasa([[a,b,c,  d],
		    [e,f,g,  h],

		    [i,j,k,  l],
		    [m,n,o,  p]], 2-3, LL).
LL = [[a,b,c,e,f,g],
      [d,h],
      [i,j,k,m,n,o],
      [l,p]] ? ;
no
| ?- feldarabolasa([[a,b,  c,d],

                    [e,f,  g,h],

		    [i,j,  k,l],

		    [m,n,  o,p]], 1-2, LL).
LL = [[a,b],
      [c,d],
      [e,f],
      [g,h],
      [i,j],
      [k,l],
      [m,n],
      [o,p]] ? ;
no
| ?-

Erlang

1> c(khf1).
{ok,khf1}
2> khf1:feldarabolasa([[a,b,c,d],
2>                     [e,f,g,h]], {2, 2}).
[[a,b,e,f],[c,d,g,h]]
3> khf1:feldarabolasa([[a,b,c,d],
3>                     [e,f,g,h],
3>                     [i,j,k,l],
3>                     [m,n,o,p]], {2, 2}).
[[a,b,e,f],
 [c,d,g,h],
 [i,j,m,n],
 [k,l,o,p]]
4> khf1:feldarabolasa([[a,b,c,d],
4>                     [e,f,g,h],
4>                     [i,j,k,l],
4>                     [m,n,o,p]], {3, 3}).
[[a,b,c,e,f,g,i,j,k],
 [d,h,l],
 [m,n,o],
 [p]]
5> khf1:feldarabolasa([[a,b,c,d],
5>                     [e,f,g,h],
5>                     [i,j,k,l],
5>                     [m,n,o,p]], {3, 2}).
[[a,b,e,f,i,j],
 [c,d,g,h,k,l],
 [m,n],
 [o,p]]
6> khf1:feldarabolasa([[a,b,c,d],
6>                     [e,f,g,h],
6>                     [i,j,k,l],
6>                     [m,n,o,p]], {2, 3}).
[[a,b,c,e,f,g],
 [d,h],
 [i,j,k,m,n,o],
 [l,p]]
7> khf1:feldarabolasa([[a,b,c,d],
7>                     [e,f,g,h],
7>                     [i,j,k,l],
7>                     [m,n,o,p]], {1, 2}).
[[a,b],
 [c,d],
 [e,f],
 [g,h],
 [i,j],
 [k,l],
 [m,n],
 [o,p]]

A kiírásnak megfelelően mindkét nyelven jók azok a programok is, amelyek a külső lista elemeit a fentiekhez képest más sorrendben adják vissza. A belső listák elemeinek a sorrendjét azonban előírtuk: minden egyes ilyen elemnek egy-egy kis mátrix elemeit sorfolytonosan kell felsorolnia.

Tudnivalók a beadásról

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 4.3.x, ill. az Erlang/OTP R16B rendszerekkel teszteljük.

Ennek a kis házi feladatnak a beadása ugyan nem kötelező, azonban a félévközi követelmények teljesítéséhez a félév során legalább három kisházifeladat-megoldást – közülük legalább egyet Prolog és legalább egyet Erlang nyelven – sikeresen be kell adni. Sikeres az a megoldás, amelyik az összes tesztesetre helyes választ ad. Ha ezt a kis házi feladatot mindkét nyelven sikeresen beadja, az természetesen két megoldásnak számit.

A programot az Elektronikus Tanársegéd (ETS) segítségével weben keresztül lehet beadni, a HF beadás menüpont alatt. Ez az egyes számú kis házi feladat, ennek megfelelően az ETS a beküldött megoldást khf1.pl, ill. khf1.erl néven tárolja el és hivatkozik rá. (A feltöltendő állomány neve tetszőleges lehet, az ETS átnevezi.)

Az osztályzat megállapításakor a határidőre beadott, minden tesztesetre helyesen működő feladatmegoldásért plusz 1-1 pont jár.

Gyakorló feladatok

A házi feladat megoldásának előkészítésére a következő kisebb gyakorló feladatok megoldását javasoljuk.
  1. Lista szeletének (i. és j. sorszámú elemek közötti részének) előállítása.
  2. Sorfolytonosan, illetve oszlopfolytonosan tárolt mátrix i. sorának előallítása.
  3. Sorfolytonosan, illetve oszlopfolytonosan tárolt mátrix j. oszlopának előállítása.
  4. Sorok listájaként tárolt mátrix sorfolytonosan, illetve oszlopfolytonosan tárolt változatának előállítása.
  5. Sorfolytonosan, illetve oszlopfolytonosan tárolt mátrix sorok listájaként tárolt változatának előállítása.