Algebraične strukture

Struktura = (Množica vrednosti, operacija[, operacija])

Operacije: unarne, binarne preslikave

Lastnosti operacij: 

  • o: asociativnost, enota, inverz, komutativnost
  • +,o: distributivnost

Polgrupa (M, o): binarna preslikava o in asociativost   (N,+)

Monoid (M, o): polgrupa in enota  (R,*) 

Grupa (M, o): monoid in inverz  (R,+)

Vse strukture so lahko še komutativne.

Algebraična definicija struktur (podatkovnega tipa):

  • tipi (množice vrednosti)
  • operacije (preslikave)
  • ekvivalence (pravila - lastnosti)

Nat:

tipi:   Nat
operacije:
  0: → Nat
  succ: Nat → Nat
  add: Nat Nat → Nat
ekvivalence:
  n, m ∈ Nat
  add(n, 0) = n
  add(n, succ(m)) = succ(add(n, m))

Int:

tipi:   Int
operacije:
  0: → Int 
  succ: Int → Int
  pred: Int → Int
  add: Int Int → Int
ekvivalence:
  n, m ∈ Int
  succ(pred(n)) = n
  pred(succ(n)) = n
  add(n, 0) = n
  add(n, succ(m)) = succ(add(n, m))
  add(n, pred(m)) = pred(add(n, m))

Stack:

tipi:   Item = Int ∪ {error},  Stack
operacije:
  empty: → Stack
  push: Item Stack → Stack
  pop: Stack → Stack
  top: Stack → Item
ekvivalence:
  pop(push(x, s)) = s
  top(push(x, s)) = x
  pop(empty) = empty
  top(empty) = error

1. Več kratkih nalog z algebraično definicijo tipov Nat, Int in Stack.

2.  Prikaži delovanje metode obrni(Stack s), ki obrne vsebino sklada s!

s: [A, B, C, D, E, F, G]                 obrni(s): [G, F, E, D, C, B, A]

3. Prikaži delovanje metode obrni(Stack s, int n, int m), ki obrne m elementov sklada s od mesta n dalje!

s: [A, B, C, D, E, F, G]                 obrni(s,2,3): [A, B, E, D, C, F, G]

4. Prikaži delovanje metode pogrezni(Stack s, int n, int m), ki pogrezne prvih n elementov sklada s za m mest!

s: [A, B, C, D, E, F, G]                  pogrezni(s,2,3): [C, D, E, A, B, F, G]

5. Prikaži delovanje metode izloci(Stack s, Object o), ki iz sklada izloči vse objekte, ki so enaki objektu o. Metoda naj vrne število izločenih elementov.

s: [A, A, B, C, A, D, E, A]             izloci(s,A): [B, C, D, E]   in vrne 4

6. Prikaži delovanje metode preuredi(Stack s), ki na podlagi sklada elementov različnih tipov vrne tabelo tabel objektov, kjer vsaka tabela vsebuje elemente enega (istega) tipa.

s: [A, 1, B, C, true, D, 3.14, 2]     preuredi(s):  { {A, B, C, D}, {1, 2}, {true}, {3.14} }



Последна промена: петок, 28 октомври 2022, 15:53