Implementácia abstraktných údajových typov

Už sme sa venovali abstraktný údajový typ postupnosť, ktorý patrí k základným v aplikatívnom programovaní. Na programovanie zložitých úloh však treba aj iné údajové typy ako napr. množinu, graf, tabuľku. Na ilustráciu v tejto kapitole opíšeme imlementáciu abstraktného údajového typu konečná množina. Na konštrukciu prototypovej implementácie konečných množín použijeme postupnosť.

Abstraktný údajový typ sa zvyčajne opisuje signatúrou a axiomatickou špecifikáciou. Tento opis nezávisí od konkrétneho prostriedku, ktorý sa použije na implementáciu údajového typu. Prototyp predstavuje skutočne vytvorený model údajového typu. Často sa nazýva aj prvou implementáciou. Prototyp vlastne preukazuje, že sa špecifikáciou nepožadovalo niečo nemožné. Keďže prototyp by mal iba ukázať vhodnosť implementácia špecifikácie nemusí byť efektívna a výkonná. Dôležitejšie je, aby prototyp bol jednoduchý, aby nám umožnil ukázať, že všetky navrhnuté operácie sú implementované správne.

Abstraktný údajový typ množina

V tejto časti uvedieme špecifikáciu údajového typu konečná množina, ktorá bude slúžiť ako východisko pri jej implementácii. Aký je rozdiel medzi konečnými množinami a postupnosťami? Pri množinách poradie a viacnásobný výskyt prvkov nie je dôležitý. Napr. tieto množiny považujeme za rovnaké:

     {7,2,14} {2,14,7} {2,2,14,7} {14,2,2,7,7,2}.

     [7,2,14] [2,14,7] [2,2,14,7] [14,2,2,7,7,2].

Konštruktory

Množiny sa 'podobajú' na postupnosti v tom zmysle, že ich môžeme skonštruovať induktívne - n+1 prvkovú množinu môžeme vytvoriť pridaním jedného prvku k n-prvkovej množine. Táto operácia spolu s operáciou vytvorenia prázdnej množiny dovoľuje konštrukciu ľubovoľnej konečnej množiny. Potrebujeme dva konštruktory:

• jeden pre vytvorenie prázdnej množiny (empty) a
• jeden pre pridanie prvku k ľubovoľnej konečnej množine (insert).

Rozlišovače

Ako rozlišovač spojený s prázdnou množinou budeme uvažovať operáciu isempty, takú, že

   isempty(S)  = true práve  vtedy, ak S je prázdna  množina.

     isempty(empty) = true
     isempty(insert(x,S)) = false

     isempty(empty) => true
     isempty(insert(x,S)) => false

Selektory

Keďže prázdna množina nemá žiadne prvky, nemá ani žiadne selektory. Preto sa budeme zaoberať selektormi pre neprázdne množiny. Vzhľadom na to, že pri množinách nezáleží na poradí prvkov nemôžeme uvažovať o operácii insert(x,S) ako o operácii, ktorá vloží prvok x na prvé miesto v množine S. Musíme uvažovať, že táto operácia môže vložiť x na ľubovoľné miesto v množine S:

     insert(7, {2,14}) = {7,2,14} = {14,2,7} = {2,14,7} = ...

     insert(7, {2,14}) = insert(2, {7,14}) = insert(14, {7,2})

Máme nepríjemnú situáciu: údajovú štruktúru, do ktorej môžeme vložiť objekty (pomocou konštruktora), ale z ktorej nemôžeme dostať nič (keďže nemáme žiadne selektory). Z tejto situácie nám môže pomôcť operátor isin (test, či sa prvok nachádza v množine), ktorý sa správa určitým spôsobom ako selektor. Dovoľuje zistiť štruktúru množiny. Tento operátor nazývame interogátor, lebo odpovedá na otázky o komponentoch štruktúry.

o------------------o----------------------o--------------------o
|  druh množiny    |      prázdna         |   neprázdna        |
o------------------+----------------------+--------------------o
|  rozlišovač      |      isempty         |   not(isempty)     |
|  konštruktor     |      empty           |   insert           |
|  interogátor     |        -             |   isin             |
o------------------o----------------------o--------------------o

     isin(x, empty) = false
     isin(x, insert(y,S)) = (x = y \/ isin(x,S))

Keďže každá konečná množina sa dá vyjadriť ako konečný počet aplikácií operácií insert, tieto rovnosti definujú funkciu isin pre všetky konečné množiny. Na pravej strane vyššie uvedených rovností sa používa operácia '=' definovaná pre údajový typ tau, ktorý je bázou množiny. Operáciu isin možno špecifikovať iba na základe predpokladu, že typ tau má definovanú operáciu rovnosti. Bez toho by sme neboli schopní určiť, či daný objekt je alebo nie je prvkom množiny.

Konečnosť množín

    card: finset tau -> N (N množina konečných prirodzených čísel)
    card je totálna funkcia na finset tau

    card(empty) = 0
    card(insert(x,S)) = card(S),       ak isin(x,S)
    card(insert(x,S)) = 1 + card(S)    ak not(isin(x,S))

Axióma extenzionality

Zdá sa, že okrem mien nie je veľa rozdielov medzi funkciami cons a insert. Ako môžeme vyjadriť fakt, že insert vytvára množiny, zakiaľ čo cons postupnosti? Základným rozdielom je, že postupnosti závisia od poradia a viacnásobného výskytu prvkov a množiny nie:

     cons(x,cons(y,S)) <> cons(y,cons(x,S)),   pre x<>y
     cons(x,S)   <> cons(x,cons(x,S))
     insert(x, insert(y, S)) = insert(y, insert(x, S))
     insert(x, S) = insert(x, insert(x, S))

Túto axiómu extenzionality možno jednoducho vyjadriť takto:

  S = R práve vtedy ak pre všetky x platí: isin(x,S) = isin(x,R)

Axióma extenzionality nám umožňuje dokázať vyššie uvádzané rovnosti.

Špecifikácia

Do špecifikácie ďalej zaradíme operácie pre prácu s množinami ako sú prienik, zjednotenie, rozdiel, podmnožina. Výhoda vývoja špecifikácie pred prototypom je v tom, že tento postup umožňuje dôkaz vlastností údajového typu predtým ako sa implementuje.

SIGNATÚRA údajového typu množina:
druhy: tau, finset tau, bool, N
operácie:
    empty:                              -> finset tau
    insert:     tau x finset tau        -> finset tau
    isempty:    finset tau              -> bool
    isin:       tau x finset tau        -> bool
    card:       finset tau              -> N
    intersect:  finset tau x finset tau -> finset tau
    union:      finset tau x finset tau -> finset tau
    difference: finset tau x finset tau -> finset tau
    issubset:   finset tau x finset tau -> bool
    =:          finset tau x finset tau -> bool

SÉMANTIKA
EXISTENČNÁ AXIÓMA:
    empty patri finset tau
    insert(x, S) patri finset tau,  ak x patri tau, S patri finset tau
    nejake z nepatri finset tau, inak

MNOŽINA ROVNOSTÍ:
    isempty(empty) = true
    isempty(insert(x,S)) = false

    isin(x,empty) = false
    isin(x,insert(y,S)) = (x = y \/ isin(x,S))

    card(empty) = 0
    card(insert(x,S)) = card S,     ak isin(x,S)
    card(insert(x,S)) = 1 + card S, ak not(isin(x,S))
          card je totálna funkcia na finset tau

    S = R <=> pre všetky x: isin(x, S) = isin(x, R)

    isin(x, prienik(S,R)) = isin(x,S) /\ isin(x,R)
    isin(x, union(S,R)) = isin(x,S) \/ isin(x,R)
    isin(x, difference(S,R)) = isin(x,S) /\ not(isin(x,R))
    issubset(empty,S) = true
    issubset(insert(x,S),R) = isin(x,R) /\ issubset(S,R)

Prototyp pre konečné množiny

Ako môžeme implementovať konečné množiny? Najskôr treba zvoliť implementujúci údajový typ, a potom naprogramovať operácie. Máme viacero možností: tabuľka, bitový vektor, usporiadané pole, B-strom, postupnosť. Účelom prototypu je, aby jeho implementácia bola jednoduchá. Najlepší výber v tomto prípade je reprezentácia konečnej množiny pomocou postupnosti obsahujúcej jej prvky. Keďže v postupnostiach je poradie a viacnásobný výskyt prvkov významné, a v množinách nie, bude existovať veľa postupností reprezentujúcich tú istú množinu. Napr. množinu {7,2,14} možno reprezentovať postupnosťami:

     [7,2,14], [2,14,7], [14,7,2], [7,14,2], [2,7,14,2],....

V skutočnosti však to, že údajový typ má viacnásobné abstraktné reprezentácie je úplne nezávislé od toho, či sa implementuje s viacnásobnými konkrétnymi reprezentáciami. Napr. hoci množiny majú viacnásobné abstraktné reprezentácie, mohli by sme ich implementovať spôsobom, ktorý priraďuje jedinečnú konkrétnu reprezentáciu každej množine (povedzme, napr. usporiadaním prvkov a vylúčením duplikátov). Vzťah medzi viacnásobnými reprezentáciami na abstraktnej a konkrétnej úrovni je znázornený na obrázku nižšie.

insert(7, {2,14})    insert(2, {7,14})   insert(14, {2,7}) ...
               \             |            /
viacnásobné     \            |           /
abstraktné       \           |          /
reprezentácie     \          |         /
                   \         |        /
                    abstraktná hodnota {7,2,14}
                    /        |       \
viacnásobné        /         |        \
konkrétne         /          |         \
reprezentácie    /           |          \
                /            |           \
          [7,2,14]       [14,2,7]      [7,2,14,2] .....

     S = R --> equal(S,R)

Používateľovi abstraktného údajového typu množina treba skryť podrobnosti implementácie (ako nejednoznačnú konkrétnu reprezentáciu). Potom možno vykonať zmeny implementácie údajového typu množina bez ovplyvnenia programov, ktoré tento abstraktný typ údajov používajú. Poznamenajme, že insert a union môžu zaviesť do množiny duplikáty, čo je zvolenou reprezentáciou povolené.

Väčšina prototypových implementácií operácií sa vytvára podľa takéhoto vzoru: buď sú to jednoduché rekurzívne definície alebo definície v pojmoch už definovaných operácií.

PROTOTYP pre údajový typ konečná množina:
  empty --> nil

  insert(x, S) --> cons(x, S)

  isempty(S) --> null(S)

  isin(x, S) --> member(x, S)

  card(S) --> 0,                    ak isempty(S)
  card(S) --> card(rest(S)),        ak not(isempty(S)) /\ isin(first(S),rest(S))
  card(S) --> card(rest(S)) + 1     inak

  intersect(S,R) --> nil,                                     ak isempty(S)
  intersect(S,R) --> insert(first(S), intersect(rest(S),R))), ak isin(first(S),R)
  intersect(S,R) --> intersect(rest(S),R)),                   inak

  union(S,R) --> append(S,R)

  difference(S,R) --> nil,                                     ak isempty(S)
  difference(S,R) --> insert(first(S), difference(rest(S),R)), ak not(isin(first(S),R))
  difference(S,R) --> difference(rest(S),R),                   inak

  issubset(S,R) --> isempty(difference(S,R))

  S = R --> issubset(S,R) /\ issubset(R,S)

to Homepage

to Teaching

to FLP

to the Top