7. Programozás

Elérhető forrás: GT egy pék

Felsoroló fogalma

A gyűjtemény/tároló/kollekció/iterált egy olyan objektum, ami elemek tárolására alkalmas, valamint az elemek tárolására és visszakeresésére biztosít műveletet. Az iterált lehet valódi elemek valamilyen halmaza (zsák, tömb, sorozat, verem, sor, stb), vagy lehet virtuális gyűjtemény is (egyész számok egy intervalluma, egy szám prím osztói, stb.)

A bejárásra az alábbi 4 függvénnyel kell egy felsorolónak rendelkeznie (\(A^*\)):

• first() : \(\top\) - az iterátort az első elemre állítja
• next() : \(\top\) - tovább lépteti a felsorolót a következő elemre
• end(): \(\mathbb{B}\) - megmondja hogy a felsoroló végigért-e (nincs következő elem)
• current() : \(A\) - megadja a jelenlegi elemet

GT drop: "Célszerű a felsorolást olyan algoritmusba beágyazni, amely garantálja, hogy csak olyan állapotban hajtja végre a felsoroló egyik műveletét, amikor az értelmes."

GT megengedi a következő shorthand-et egy felsorolóra:

Nevezetes gyűjtemények felsorolói

A felsoroló típusát leíró osztályt az jellemzi, hogy megvalósítja a felsoroló műveleteket. A megvalósításakor a reprezentáció tartalmazza

‒ a felsorolni kívánt gyűjtemény hivatkozását ‒ a felsoroló műveletek implementációjához szükséges segéd adatokat.

Példa kódok kotlin-ban (mert a pszeudokód uncsi :P)

interface Enumerator<out T>{
    fun first(): Unit
    fun next(): Unit
    fun end(): Bool
    fun current(): T
}

Intervallum felsoroló

class IntervalEnumerator(val m: Int, val n: Int, var i: Int) : Enumerator<Int>{
    override fun first() { i = m }
    override fun next() { i += 1 }
    override fun end() = i > n
    override fun current() = i
}

Tömb felsoroló

class ArrayEnumerator<T>(
    val m: Int, val n: Int, val v: Array<T>, var i: Int
) : Enumerator<T>{
    override fun first() { i = m }
    override fun next() { i += 1 }
    override fun end() = i >= n
    override fun current() = v[i]
}

Mátrix felsoroló

class ArrayEnumerator<T>(
    val k: Int, val l: Int, val v: Matrix<T>, var i: Int, var j: Int
) : Enumerator<T>{
    override fun first() { i = m }
    override fun next() { if(j < m) { j += 1 } else { j = 1; i += 1 } }
    override fun end() = i >= n
    override fun current() = v[i, j]
}

Sekvenciális inputfájl felsoroló

class SeqInFileEnumerator<T>(
    var x: InFile<T>,var dx: T,var sx: Status
) : Enumerator<T>{
    override fun first() { (sx, dx, x) = x.read() }
    override fun next() { (sx, dx, x) = x.read() }
    override fun end() = st is ABNORM
    override fun current() = dx
}

enum class Status{ NORM, ABNORM }

fun interface InFile<T>{
    fun read(): Triple<Status, T, InFile<T>>
}

Yes, itt hagytam a szükséges InFile interfészt, hogy legyen a kódnak értelme (nyugi, magyarázat nélkül a forrásnak sincs értelme)

Felsorolóra megfogalmazott programozási tételek

Összegzés

Feladat:

Adott egy \(E\)-beli elemeket felsoroló t objektum és egy \(f:E\to H\) függvény. A \(H\) halmaz elemein értelmezett egy baloldali nulla elemmel rendelkező művelet (nevezzük ezt összeadásnak és jelölje a +). Határozzuk meg a függvénynek a t elemeihez rendelt értékeinek összegét! (Üres felsorolás esetén az összeg értéke definíció szerint a nullelem: 0).

Specifikáció:

\(\begin{array}{l} A = \left(t: enor(E), s: H\right) \\ \\ Ef=\left(t=t'\right) \\ \\ Uf=\left(s=\underset{e\in t'}{\large\sum} f(e)\right)\end{array}\)

Számlálás

Feladat: Adott egy \(E\)-beli elemeket felsoroló t objektum és egy \(f:E\to\mathbb{L}\) feltétel. A felsoroló objektum hány elemére teljesül a feltétel?

Specifikáció:

\(A = \left(t: enor(E), c: \N\right)\)

\(Ef=\left(t=t'\right)\)

\(Uf=\left(s=\underset{f(e)}{\underset{e\in t'}{\large\sum}} 1\right)\)

Maximum kiválasztás

Specifikáció:

\(A = \left(t: enor(E), max: H, elem: E\right)\)

\(Ef=\left(t=t'\land |t|>0\right)\)

\(Uf=\left(\left(max, elem\right) = \large\underset{e\in t'}{\bold{MAX}}, f(e)\right)\)

Feltételes maximumkeresés

Specifikáció:

\(A = \left(t: enor(E), l: \mathbb{L}, elem: E\right)\)

\(Ef=\left(t=t'\right)\)

\(Uf=\left(\left(l, max, elem\right) = \large\underset{felt(e)}{\underset{e\in t'}{\bold{MAX}}}, f(e)\right)\)

Lineáris keresés

Specifikáció:

\(A = \left(t: enor(E), l: \mathbb{L}, elem: E\right)\)

\(Ef=\left(t=t'\right)\)

\(Uf=\left(\left(l, elem, t\right) = \large\underset{felt(e)}{\underset{e\in t'}{\bold{SEARCH}}}, f(e)\right)\)

Kiválasztás

Specifikáció:

\(A = \left(t: enor(E), elem: E\right)\)

\(Ef=\left(t=t'\land \exists i\in[1..|t|]: felt(t_i) \right)\)

\(Uf=\left(\left(elem, t\right) = \large\underset{felt(e)}{\underset{e\in t'}{\bold{SELECT}}}, f(e)\right)\)

A visszavezetés módszere

A visszavezetés során egy konkrét feladatot megoldó programot egy programozási tétel segítségével állítunk elő:

1. Megsejtjük a feladatot (részfeladatot) megoldó programozási tételt.
2. Specifikáljuk a feladatot a programozási tételre utaló végrehajtható utófeltétellel.
3. Megadjuk a feladat és a programozási tétel közötti eltéréseket:
   • felsoroló típusát a felsorolt elemek típusával együtt
   • függvények \((f : E\to H, felt : E\to \mathbb{L})\) konkrét megfelelőit
   • a H halmaz műveletét, ha kell. Például:
     • \((H, >)\) helyett például \((\mathbb{Z}, >)\) vagy \((\mathbb{Z}, <)\)
     • \((H, +)\) helyett például \((\mathbb{Z}, +)\) vagy \((\mathbb{R}, *)\) vagy \((\mathbb{L}, \land)\)
   • változók átnevezéseit
4. Átalakítjuk a programozási tétel algoritmusát a fenti különbségek alapján, hogy megkapjuk a

kitűzött feladatot megoldó algoritmust.c

Programozási tételekkel készült programok tesztelése

A programozási tételek segítségével előállított programok tesztelését a hagyományos fekete- és fehér dobozos tesztelések mellett a felhasznált programozási tételek algoritmusára jellemző tesztesetek mentén is végezhetjük. Mivel az alkalmazandó programozási tételre már a specifikáció is rámutat, ez egyszerre számít fehér- és fekete, azaz szürke dobozos tesztelésnek. Tesztelési szempontok:

• Felsoroló szerint (mindegyik programozási tétel esetén)
  • eltérő hosszúságú felsorolások: nulla, egy illetve hosszabb felsorolásokra is kipróbájuk az algoritmust
  • kezdet és a vég: feldolgozza-e az algoritmus a felsorolás első ill. utolsó elemét
• Funkció szerint (programozási tételenként eltérő)
  • összegzés: felsorolás hosszának skálázása
  • keresés, számlálás: van vagy nincs keresett tulajdonságú elem
  • maximum kiválasztás: egyetlen vs. több azonos maximális érték
  • feltételes maximumkeresés:
    • van vagy nincs keresett tulajdonságú elem
    • feltételt kielégítő egy vs. több azonos maximális érték
    • a legnagyobb értékű elem nem elégíti ki a feltételt
• A felt(i) és f(i) kifejezések kiszámolásánál használt műveletek sajátosságai.