Teorija 2: povzetek prosojnic

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):

Nat:

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:

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} }