1. Signatura datového typu a) b) c) d)
popisuje vlastnosti operací datového typu popisuje sémantiku datového typu popisuje jména druh a operací a druhy argument a výsledku je grafickým vyjád ením implementace datového typu
tvrtá možnost odpadá ihned, protože tím, že je datový typ abstraktní, existuje on sám i jeho signatura d íve než jakékoli implementace a v bec na nich nezavisí. Sémantika operací je zachycena axiomy, nikoli signaturou, druhá možnost odpadá. První varianta íká prakticky totéž co druhá, takže zbývá jen t etí správná možnost. 2. Signatura datového typu a) b) c) d)
popisuje vlastnosti operací datového typu lze ji popsat graficky pomocí ovál , malých kroužk a spojovacích ar a písmen vyjad uje se pomocí axiom popisuje universum hodnot
T etí možnost nedává smysl, nebo axiomy se k signatu e p idávají práv proto, aby bylo možno ADT kompletn popsat. Signatura nepopisuje ani vlastnosti operací, nebo práv ony se vyjad ují pomocí axiom . První a t etí možnost tedy nedává smysl. Ješt mén smyslu dává poslední tvrtá možnost, universum hodnot p edstavuje pouze všechny v bec možné hodnoty se kterými ADT m že pracovat, vlastnosti této množiny ovšem ADT v bec nezachycuje. Nap íklad ADT fronta ned celými ísly nijak blíže celá ísla nespecifikuje. Zbývá jen možnost b), jakkoli p itom vypadá primitivn . 3. Signatura datového typu a) b) c) d)
je zájmová skupina naturist popisuje syntaxi datového typu sestává z druh , jmen operací a axiom popisuje sémantiku datového typu
Popis sémantiky, tj. „jaký má význam a co se strane když...“ zajiš ují axiomy datového typu. varianta d) odpadá. Stejn tak odpadá varianta c) nebo axiomy práv sou ástí signatury nejsou. Protože naturisté jsou osoby programov holdující návratu k p írod , kde se s abstraktními datovými typy nesetkáváme (nanejvýš s jejich implementacemi), platí varianta b). 4. Datová struktura a) je konkrétní realizací datového typu b) je základním stavebním kamenem datových typ c) slouží k ukládání polí v po íta i
d) vznikne ze signatury dopln ním axiom P idáním axiom k signatu e vzniká abstraktní datový typ, varianta d) neplatí. Pole v po íta i je sice p íkladem datové struktury, nikoli však jediným, varianta c) je p inejmenším podez elá. U variant a) a b) je nutno rozhodnout, zda se ADT odvozuje od datové struktury i naopak. V tšinou se konkrétní odvozuje od abstraktního, takže p ednost dostane varianta a). 5. Datová struktura a) b) c) d)
popisuje jména druh , jména operací a druhy parametr popisuje syntaxi datového typu je pln popsána soustavou axiom vznikne z datového typu volbou nosi druh a implementací operací
Datová struktura je realizací ur itého ADT. Všechny její podstatné vlastnosti jsou tedy v odpovídajícím ADT popsány, takže ona sama nemusí nic poposovat, varianty a) a b) odpadají. Naopak, soustava axiom k popisu nesta í, axiomy ne íkají, nad jakým druhem dat se oparace provád jí, varianta c) také odpadá. Zbývá poslední varianta d). 6. Datový typ a) b) c) d)
je pln popsán soustavou axiom je ur en druhy dat a typickými operacemi je ur en typickými operacemi je ur en druhy dat
To je otázka pamatování si definice. Pro datový typ musí být známo, s jakými v bec hodnotami m že pracovat (= druhy dat) a také musí být známo, jaké operace nad t mito hodnotami lze v rámci datového typu provád t (= typické operace). Platí b). 7. Druh dat a) b) c) d)
popisuje syntaxi datového typu popisuje sémantiku datového typu je povolená množina hodnot lze popsat graficky pomocí ovál , malých kroužk a spojovacích ar a písmen
Toto je také otázka sm rem do definic – druh dat je to, co se zmi uje ve variant c).
8. Soustava axiom op(x, true) = true op(x,false) = x op(x,y) = op(y,x) a) b) c) d)
popisuje operaci and popisuje operaci xor popisuje operaci or popisuje operaci not
Operace op je binární, operace not je unární, tvrtá možnost odpadá. Po dosazení false za x v prvním axiomu vidíme, že op nem že být operací and. Po dosazení false za x ve druhém axiomu vidíme, že se nem že jednat o operaci xor. Zbývá tudíž jen or – t etí možnost. 9. Soustava axiom op(x, true) = x op(x,false) = false op(x,y) = op(y,x) a) b) c) d)
Popisuje operaci or Popisuje operaci and Popisuje operaci xor Popisuje operaci not
Operace op je binární, operace not je unární, tvrtá možnost odpadá. Po dosazení false za x v prvním axiomu vidíme, že op nem že být operací or. Po dosazení false za x ve druhém axiomu vidíme, že se nem že jednat o operaci xor. Zbývá tudíž jen and – druhá možnost. 10. Je dán datový typ množina bez opakování prvk . Kterým výrazem je nutno nahradit písmena xxx v následujících axiomech, popisujících mazání prvku z množiny?
a) b) c) d)
del(x,[ ])=[ ] del(x,ins(y,s))= if eq(x,y) then xxx else ins(y,del(x,s)) ins(x,s) del(x,s) s x
Jsme tázáni, co se stane, když do množiny vložíme prvek x vzáp tí jej op t smažeme. Pokud na za átku prvek x již v množin byl, pokus o vložení množinu s nezm ní (množina je bez opakování!) a další operace mazání jej skute n z množiny odstraní,
takže celou událost lze popsat výrazem del(x,s). Žádný z dalších t í nabízených výraz a), c), d) se nehodí. Nyní pozor. Pokud na za átku prvek x v množin nebyl, z ejm vložení a následné smazání zanechá množinu s beze zm ny. Našt stí v takovém p ípad formáln platí s = del(x,s). A již tedy prvek x v množin s byl nebo nebyl, platí del(x, ins(x,s)) = del(x,s). Jediná možná varianta odpov di je b). 11. Je dán datový typ množina bez opakování prvk . Kterým výrazem je nutno nahradit písmena xxx v následujících axiomech, popisujících velikost množiny? card([ ])=0 card(ins(y,s))= if in(y, s) then xxx else succ(card(s)) a) b) c) d)
succ(card(ins(y,s))) card(s) s card(y)
Jsme tázáni, jak velká bude množina poté, co se do ní pokusíme vložit prvek, který už je v ní obsažen. Protože množina je bez opakování, prvek se nevloží a velikost množiny se nezm ní. To znamená, že pravdivá je varianta b). 12. Popište abstraktní datový typ „množina s opakováním prvk “ s operacemi: [] „prázdná množina“ ins „vložení prvku do množiny“ isIn „test p íslušnosti prvku k množin “ del „smazání prvku z množiny“ eq „rovnost dvou množin“ card „mohutnost množiny“ Signatura (1 bod), axiomy (0+1+1+1+1+1): ešení typ: MNOŽINA( ELEMENT ) parametr: typ prvk ELEMENT požadavky na parametr: druhy: Elem operace: eq(_,_): Elem, Elem -> Bool použité typy: ELEMENT, p irozená ísla, logické hodnoty druhy: Elem, Bool, Set, Nat operace: [ ]: Set (prázdná množina) ins(_,_): Elem,Set ->Set (vložení prvku) del(_,_): Elem,Set ->Set (zrušení -“- ) in(_,_) : Elem,Set ->Bool(test p ísluš.)
prom nné: axiomy:
card(_) : Set->Nat
(po et prvk )
s: Set, x,y: Elem // nic imezujícího pro ins del(x,[ ])=[ ] del(x, ins(y,s))= if eq(x,y)
// mazání jednoho insu then s // maže se jeden výskyt x v s else ins(y, del(x,s))
in(x,[ ]) = false in(x,ins(y,s))= if eq(x,y)then true else in(x,s) card([ ]) = 0 card(ins(x,s)) = succ(card(s)) // po ítá se pokaždé eq(s,t) = eq(t,s) eq(s,[ ]) = if eq(s,[ ]) then true else false eq(ins(x,s),t) = if in(x,t) //jednodušší then eq(s,del(x,t)) else false 13. Popište abstraktní datový typ „množina bez opakování prvk “ s operacemi: [] „prázdná množina“ ins „vložení prvku do množiny“ isIn „test p íslušnosti prvku k množin “ del „smazání prvku z množiny“ eq „rovnost dvou množin“ card „mohutnost množiny“ Signatura (1 bod), axiomy (0+1+1+1+1+1): pozor na zamezení vícenásobného vkládání u operace ins a mazáni duplicit p i operaci del. ešení: typ: MNOŽINA( ELEMENT ) parametr: typ prvk ELEMENT požadavky na parametr: druhy: Elem operace: eq(_,_): Elem, Elem -> Bool použité typy: ELEMENT, p irozená ísla, logické hodnoty druhy: Elem, Bool, Set, Nat operace: [ ]: Set (prázdná množina) ins(_,_): Elem,Set ->Set (vložení prvku)
prom nné: axiomy:
del(_,_): Elem,Set ->Set (zrušení -“- ) in(_,_) : Elem,Set ->Bool(test p ísluš.) card(_) : Set->Nat (po et prvk ) s: Set, x,y: Elem ins(x,s) = if in(x,s) then s del(x,[ ])=[ ] del(x, ins(y,s))= if eq(x,y)
// druhé vložení bez významu // mazání všech ins then del(x,s) else ins(y, del(x,s))
in(x,[]) = false in(x,ins(y,s))= if eq(x,y)then true else in(x,s) card([]) = 0 card(ins(x,s)) = if(in(x,s)) then card(s) else succ(card(s)) // po ítá se jen 1x eq(s,t) = eq(t,s) eq(s,[]) = if eq(s,[])
then true else false
eq(ins(x,s),t) = if in(x,s)
then eq(s,t) else if in(x,t) then eq(s,del(x,t)) else false
