Algebraické štruktúry
Problém: Začlenenie hierarchie algebraických štruktúr (grupa, okruh, pole, ...) do Smalltalku. Možnosť využitia takýchto štruktúr. Ukázanie výhod pri implementácii v OOP.
Use cases:
Analýza problému:
Algebraické štruktúry sa skladajú z dvoch podstatných častí - základnej množiny a aspoň jednej operácie definovanej na tejto množine.
Operácie sú v zásade troch druhov - nulárne, unárne a binárne (viac-árne operácie sa v implementovaných štruktúrach nevyskytujú). Nulárne aj binárne operácie vo všetkých implementovaných štruktúrach úzko súvisia s binárnou operáciou (/ami) danej štruktúry. Preto je 'binárna operácia' (BinaryOperation) odčlenená ako samostatná abstraktná trieda, ktorej podtriedy budú reprezentovať konkrétne operácie.
Požadované vlastnosti binárnej operácie:
- binárna operácia je asociatívna (ab)c=a(bc)
- dokáže 'zoperovať' dva prvky
- vie určiť niektoré svoje vlastnosti, napr. komutatívnosť, uzavretosť na podmnožine, atď.
Binárna operácia ako taká reprezentuje 'predpis', ktorým sa z dvoch prvkov vytvorí tretí, a algoritmy, ktoré na základe tohto 'predpisu' určia popisované charakteristiky operácie. Teda nie je závislá na konkrétnej množine a je postačujúce, ak bude pracovať na nejakej abstraktnej reprezentácii všetkých prípustných množín (zvačša pôjde o určitý druh číselnej množiny), na ktorej sa daná operácia jednoducho realizuje. Konkrétne algebraické štruktúry však pracujú na konkrétnych množinách, a teda je potrebný určitý 'wrapper' pre každú množinu, ktorý ju dokáže pretransformovať do podobny vhodnej pre operáciu a naopak (MappingOfSet). Vzhľadom na svoj charakter je binárna operácia, podobne ako aj 'wrapper' abstraktnou triedou.
Implementované algebraické štruktúry:
SemiGroup [pologrupa]
Základná algebraická štruktúra, skladajúca sa len z množiny a jedinej binárnej operácie, na ktorú nie sú kladené žiadne ďalšie požiadavky. Pologrupa je teda základný objekt v hierarchii. Všetky pologrupy sú chápané ako aditívne, a to aj v prípade, že pologrupová operácia nie je komutatívna.
Group [grupa]
Pologrupa, v ktorej existuje neutrálny prvok a ku každému elementu existuje inverzný. Očividne, grupa je špecializáciou pologrupy a teda v triedovom diagrame je priamym potomkom pologrupy. V prípade, že základná množina je konečná, grupa si sama vie overiť, či je skutočne grupou (t.j., či jej operácia spĺňa podmienky). Ak nie je konečná, grupe nezostáva iné, len sa spoľahnúť na vhodnú definíciu operácie.
Kompletný Class Diagram:
Aktuálny stav projektu:
Príklady:
Modulárna aritmetika
Modulárna aritmetika na číslach
| GZ := (0 to: 5) asAdditiveGroupZn | Vytvorí (aditívnu) grupu Zn s prvkami 0..5 |
| GZ operateOn: 4 and: 1. | Zrealizuje grupovú operáciu na prvkoch 4 a 1 |
| GZ operateOn: 5 and: 4. | dtto |
| GZ invert: 3. | Nájde inverzný prvok k trojke |
Celý tento mechanizmus však funguje všeobecnejšie (na ľubovoľných konečných množinách).
| GZ := #('Žiadne jabĺčko' 'Jedno jabĺčko' 'Dve jabĺčka' 'Tri jabĺčka') asAdditiveGroupZn. | |
| GZ operateOn: 'Dve jabĺčka' and: 'Jedno jabĺčko'. | |
| GZ operateOn: 'Tri jabĺčka' and: 'Jedno jabĺčko'. |
Jednoducho ukážeme, ako sa správajú zvyšky po delení 3 pri sčítavaní
| Zvysky3 := #('zvysok0' 'zvysok1' 'zvysok2') asAdditiveGroupZn | zvyšky modulo 3 |
| Zvysky3 operateOn: 'zvysok1' and: 'zvysok1' | sčítaním dvoch čísel so zvyškom 1 |
| Zvysky3 operateOn: 'zvysok0' and: 'zvysok2' | zvyšok 0 nemení zvyšok súčtu |
| Zvysky3 neutral | a teda neutrálnym prvkom je ... |
Ďalší príklad:
| Znamienka := #('plus' 'minus') asAdditiveGroupZn | + a - |
| Znamienka invert: 'minus' | aké je prevrátené číslo k zápornému |
| Znamienka operateOn: 'minus' and: 'minus' | mínus a mínus dá plus |
| Znamienka basicset domain | všetko má svoje... :) |
Príklady iných typov grúp
Multiplikatívna grupa Zn*
| GZ := GroupZnStar new: 42 | Vytvorí grupu s číslami < 42, nesúdeliteľnými so 42 |
| GZ raiseElement: 23 toPower: 81 | nájde 81 mocninu prvku 23 |
| GZ neutral | neutrálny prvok |
Testovanie prvočíselnosti veľkých čísel
| 17 isFermatPRPInBase: 10 | je 17 Fermatovo PRP pri základe 10? |
| 341 isFermatPRPInBase: 2 | je 341 Fermatovo PRP pri základe 2? |
| 341 isFermatPRPInBase: 3 | je 341 Fermatovo PRP pri základe 3? |
| 561 isFermatPRPInBase: 7 | je 561 Fermatovo PRP pri základe 7? |
RSA - demonštrácia
| RS := GroupRSA p: 11 q: 17 | vytvorí RSA kódovaciu grupu |
| RS verifyKey: 3 | overí, či 3 je vhodný šifrovací exponent |
| RS makeDecryptionKey: 3 | nájde dešifrovací (privátny) kľúč |
| RS encrypt: 54 with: 3 | zašifruje správu 54 verejným kľúčom |
| RS decrypt: 10 with: 107 | rozšifruje správu privátnym kľúčom |
Download:
Finálny changeset:
⬇ as.cs