Kihagyás

3. előadás

Órai prezentáció:

Analóg programozás

  • Cél: egy feladat megoldására program készítése
  • Minden egyes alkalommal újra és újra kitalálhatjuk a megoldást
  • Vagy egy korábbi, közeli megoldást vehetjük kiindulópontnak
  • Analóg programozás: a konkrét feladatot egy korábbi feladat megoldása alapján állítjuk elő

Feladatosztályok

  • A korábbi programok ad hoc módon is előállhatnak
  • De felismerhetjük, hogy vannak megoldások, amelyek többé-kevésbé ugyanazt a feladatot oldják meg csak más módokon
  • Feladatosztályok
  • Ezekhez készíthetünk/létezik bizonyítottan helyes megoldást
  • Analóg programozás során ezeket használjuk mintának.

A specifikáció minden részfeladathoz külön készül el, de vehetünk inspirációt a részfeladatok specifikációiból. Az algoritmusban vehetjük alapul az előző feladat függvényeit.(?)

Célja

Bizonyíthatóan helyes sablon, amire lehet építeni (Könnyebben és biztonságosan fejleszthető)

Szerkezete

  • Absztrakt feladat specifikáció
  • Absztrakt algoritmus

Megjegyzés: A bemenet legalább egy sorozat

Felhasználásának menete

  1. A konkrét feladat specifikálása
  2. A specifikációban a PrT-ek megsejtése
  3. A konkrét feladat és az absztrakt feladat paramétereinek egymáshoz rendelése
  4. A konkrét algoritmus „generálása” a megsejtett PrT-ek absztrakt algoritmusok alapján, 3.szerint átparaméterezve
  5. Hatékonyítás programtranszformációkkal

Programozási tételek

  1. Összegzés (sorozatszámítás)
  2. Megszámlálás
  3. Maximum (és minimum) kiválasztás
  4. Keresés
  5. Eldöntés
  6. Kiválasztás

Összegzés

N valamiből kell kiszámolni egy valamit

Pl. \(\(\sum\)\) - összegzés, \(\(\Pi\)\)

Specifikáció

\(\mathbb{H}\) : Tetszőleges halmaz

  • Bemenet:
    • \(N \in \mathbb{N}\)
    • \(X_{1..N} \in \mathbb{H}^N\)
  • Kimenet \(S \in \mathbb{H}\)
  • Előfeltétel: -
  • Utófeltétel: \(S = \sum_{i=1}^{N}X_i\)

Általános probléma

F: N paraméteres művelet, ahol az N változó.

Megoldás

Visszavezetjük 2 paraméteres műveletre (\(\sum\) helyett +) és egy neutrális elemre (+ esetén a 0)

\[ F(X_{1..N}) \]

TH: A halmaznak megfelelő típus

Visszavezetési táblázat

Megszámolás

N darab "valamire" kell megadni, hogy hány adott tulajdonságú van közöttük.

Specifikáció

Bemenet:

  • \(N \in \mathbb{N}\)

  • \(X_{1..N} \in \mathbb{H}^N\) - \(\mathbb{H}\): tetszőleges halmaz

  • T: \(H \rightarrow L\) - T: tetszőleges tulajdonság függvény

Kimenet: Db \(\(\in\)\) \(\(\mathbb{N}\)\)

Előfeltétel: - Utófeltétel: \(Db = \sum_{i=1}^{n} \begin{cases}1 \quad ha \space T(x[i]) \\ 0 \quad különben \end{cases} = \sum_{\substack{i=1 \\ T(X_i)}}^{N}1\)

Maximum/Minimum-kiválasztás

N darab "valami" közül kell megadni a legnagyobbat (vagy legkissebbet) A "valamik" között értelmezhető egy rendezési reláció.

Specifikáció

Bemenet:

  • \(N \in \mathbb{N}\)

  • \(X_{1..N} \in \mathbb{H}^N\)

Kimenet:

  • Max \(\(\in \mathbb{N}\)\), MaxÉrt \(\(\in \mathbb{H}\)\)

Előfeltétel:

  • \(N > 0\)

Utófeltétel:

  • \(1 \leq Max \leq N\) és

  • \(\forall i (1 \leq i \leq N): X_{Max} \geq X_i\) és

  • \(MaxÉrt = X_{Max}\)

Másképp: \(Max_{i=1}^{n}X_i\)

Keresés

N darab közül kell megadni egy adott tulajdonságút

Specifikáció

Bemenet

  • N \(\(\in \mathbb{N}\)\), \(\(X_{1..\mathbb{N}}\)\), Ért \(\(\in \mathbb{H}\)\)

Kimenet

  • \[Van \in \mathbb{L}$$, $$Ind \in \mathbb{N}$$, $$Ért \in \mathbb{H}\]

Előfeltétel: -

Utófeltétel:

  • \(Van = \exists i (i\leq i \leq N): T(X_i)\)

  • \[Van \rightarrow 1 \leq Ind \leq N$$ és $$T(X_{Ind})$$ és $$Ért=X_{Ind}\]

Másképp: \((Van,Ind,Ért)=Keres_{i=1}^N T(X_i)\)