Ha az egér-kurzor ilyen:, akkor a szövegrész „kinyitható”; az aláhúzott szövegre kattintva annak leírását megjelenítheti!
Szó-magyarázkodás
Kumulatív összegzés
Kumulatív gondolat …
Otthonra
„Kumulációk” – gyakorlat

„Kumulatív algoritmusok” paradigma

Kumulatáció

Egy kis „szó-magyarázkodás”

A kumuláció (latin szó magyarul: összegyűjtődés, felhalmozódás) fogalmával találkoztunk a sorozatszámítás tételnél.
Jelentése ez volt: valamilyen N-áris operáció (például: ∑⋅, ∏⋅, ∪⋅, ∩⋅, &⋅, …) kiszámításához a rokon bináris operációt (például: ⋅+⋅, ⋅*⋅, ⋅∪⋅, ⋅∩⋅, ⋅&⋅, …) kellett „sorozatosan” végezni az argumentum-sorozat elemein végig haladva, figyelembe véve az adott bináris művelethez tartozó neutrális értéket (a ∅∈H az ⊕:H×H→H operátorra nézve neutrális, ha teljesül ez a két azonosság: ∀e∈H: e⊕∅=e, ∅⊕e=e).

A fentiek után mit jelenthet a főcímben és különösen kiindulóul szolgáló példafeladat címében („kumulatív összegzés”) a kumulatív jelző, hiszen az összegzés szó maga is egyfajta kumulációt jelent? Nézzük a feladatot!

 

 

Kumulatív összegzés

Az 1. megoldandó feladat

Adott egy N×M-es egészekből álló mátrix. Keressük azt a részmátrixát, amely elemeinek összege maximális.

A megoldás

Hasonlatos az előadás 2-6. diáin szerepelt feladathoz. Annak 2-dimenziós „általánosítása”.

Ugye világos az „absztrakt” gondolat:

  1. Összegek szélsőértékéről lévén szó, előre kiszámítjuk a „sorozat-kezdethez” képesti összegét „minden egyes rész-sorozatnak”.
  2. Majd a rész-sorozatok mindkét végét szisztematikusan mozgatva elvégezzük a szélsőérték-keresést.
    • Két vég szisztematikus mozgatása → kettős ciklus.
    • Szélsőérték-keresés → maximum-kiválasztás tétel kettős ciklushoz igazított változata.

Algoritmizálás

Az előadás algoritmusát ismerve fogalmazza újra erre a mátrixos feladatra!

Segítségképpen:

  1. A sorozatot most rész-mátrixok alkotják.
  2. A fenti 1. lépésbeli sorozat-kezdet ebben az esetben a mátrix (1,1) eleme (Mat1,1).
  3. Hogyan számolhatja ki az összeg-mátrixot (kumMat)? Rajzoljon!
    kumMati,j:= ???
    Egy rekurzív definícióra gondoljon!
    Alighanem jó, ha 0. sorral és 0. oszloppal is rendelkezik: kumMat0,0..M:=0 , kumMat0..N,0:=0 .
    Végül is: kumMati,j:=kumMati,j-1+kumMati-1,j-kumMati-1,j-1+Mati,j .
  4. Hogyan számolhatja ki egy (i,j)..(k,l) rész-mátrix elemeinek az összegét a kumMat mátrixra építve? Rajzoljon!

Az ábrázolás valami efféle: 

  Konstans
    MaxN:Egész(???)
    MaxM:Egész(???)
  Típus
    [a 0. sor és oszlop a feldolgozás rekurzív formulája miatt célszerű:]
    TMátrix=Tömb(0..MaxN,0..MaxM:Egész)
    TRészMátrix=Rekord(bfi,bfj,jai,jaj:Egész)
  Változó
   [bemenet:]
   N,M:Egész         [mátrix-méretek]
   Mat:TMátrix       [mátrix-elemek]
   [kimenet:]
   MaxRM:TRészMátrix [a max. részmátrix sarok elemeinek indexei]
   MaxÉrt:Egész      [a max. részmártix elemösszege]

Találja ki a feldolgozás eljárásának az algoritmusát!

  Eljárás Feldolgoz(Konstans N,M:Egész, Mat:TMátrix)
Nem megy?

    A rekurzív definíciót a mátrix (1,1) indexű eleme felöl kezdve iterációval implementáljuk. 
  Eljárás Feldolgoz(Konstans N,M:Egész, Mat:TMátrix):
    Változó
      kumMat:TMátrix
      i,j,k,l:Egész

    [0. sor és 0. oszlop nullázása:]
    kumMat(0..N,0):=0; kumMat(0,1..M):=0
    [(1,1)..(i,j) i=1..N,j=1..M részmátrix-összeg számítása:]
    Ciklus i=1-től N-ig
      Ciklus j=1-től M-ig
        kumMat(i,j):=kumMat(i,j-1) 
                    +(kumMat(i-1,j)-kumMat(i-1,j-1))
                    +Mat(i,j)
      Ciklus vége
    Ciklus vége
    [max-keresés:]
    MaxÉrt:=kumMat(1,1)
    MaxRM:=TRészMátrix(1,1,1,1)
    Ciklus i=1-től N-ig
      Ciklus j=1-től M-ig
        Ciklus k=i-től N-ig
          Ciklus l=j-től M-ig
            Ha kumMat(k,l)-kumMat(k,j-1)-kumMat(i-1,l)+kumMat(i-1,j-1)>MaxÉrt akkor
              MaxÉrt:=kumMat(k,l)-kumMat(k,j-1)-kumMat(i-1,l)+kumMat(i-1,j-1)
              MaxRM:=TRészMátrix(i,j,k,l)
            Elágazás vége
          Ciklus vége
        Ciklus vége
      Ciklus vége
    Ciklus vége
  Eljárás vége.


Tehát mit jelent a kumuláció a címben?

Utalás az algoritmus első lépésében létrejövő és a „lényegi” lépésben központi szerepet játszó sorozat generálásának módjára:
a „mozgó” összegzésre, vagy valami sorozatszámításra hajazó algoritmusra.

Kódolás

Kódolja a fenti probléma megoldását Pascalban! Feltesszük, hogy a mátrix elemeit egy karakteres fájl tartalmazza a szokásos formátumban.
(1. sor:  N M ; i+1. sor:  Mati,1 Mati,2 ... Mati,M i=1..N)

Valami ilyesmire gondoltam: exe. Találhat hozzá egy bemeneti fájlt is, csak minta gyanánt: dat. Hogy elegendő legyen a lényegre szorítkoznia, letölthet egy keretprogramot is, amelyhez két inklúdállomány szükséges a Hasznos programtöredékek könyvtárból.

 

 

Kumulatív „gondolat” továbbvitele

A 2. megoldandó feladat

Adott egy táglalap alakú terület, amelyen különféle „tereptárgyak” vannak elhelyezve. Határozzuk meg a benne lévő legnagyobb üres téglalap alakú területet!

Segítségképpen:

Visszavezethető az előbbi feladatra.

Hogyan?

Többféleképpen is:
  1. Rendeljen egy 0-kat, ill. alkalmasan választott (X) egész értékeket tartalmazó mátrixot a kezdetben megadott téglalap alakú területhez!
    Az X-nek nyilván olyannak kell lennie, hogy ne legyen „érdemes” olyan részmátrixot választani, amelyben bent van.
    Mivel 0-k összege nem függ a 0-k számától, ezért a szélsőérték-kiválasztás feltételében figyelni kell a „jelölt” téglalap méretére is.
    (Az én bináris megoldásom.)
  2. Összegzés helyett számolja meg az üres helyeket a mátrix-szerűen ábrázolt téglalapban, és keressen maximum értékű területet!
  3. Összegzés helyett számolja meg a nem üres helyeket a mátrix-szerűen ábrázolt téglalapban, és keressen minimum (=0) jellemzőjű, maximális méretű területet!
    (Az én bináris megoldásom.)
A megoldhatóság feltétele, hogy legyen egyáltalán üres elem.

 

 

Házi feladatok
  1. 'Az 1. megoldandó feladat' következő szigorítását oldja meg! Adott egy N×M-es egészekből álló mátrix. Keressük a maximális elemösszegű részmátrixok legnagyobbikát (azaz a legnagyobb méretűt).
    Például erre az elsőként írt program az (1,1)..(1,1) részmártixot adná, a most írandó pedig az (1,1)..(3,4) részmátrixot.


Szlávi Péter