Algebraicke struktury
Problem:
Zaclenenie hierarchie algebraickych struktur (grupa, okruh, pole, ...) do Smalltalku.Moznost vyuzitia takychto struktur. Ukazanie vyhod pri implementacii v OOP.
Use cases:
- Didakticka pomocka pri studiu vyssej algebry - hotove- Propedeutika pomocou nazornych objektov - vysvetlenie delitelnosti (modularna aritmetika) hotove
- Testovanie prvociselnosti velkych cisel hotove
- Metody sifrovania dat pomocou grup (sifrovanie RSA apod. ) hotove
Problem Analysis:
Algebraicke struktury sa skladaju z dvoch podstatnych casti - zakladnej mnoziny a aspon jednej operacie definovanej na tejto mnozine.Operacie su v zasade troch druhov - nularne, unarne a binarne (viac-arne operacie sa v implementovanych strukturach nevyskytuju). Nularne aj binarne operacie vo vsetkych implementovanych strukturach uzko suvisia s binarnou operaciou (/ami) danej struktury. Preto je 'binarna operacia' (BinaryOperation) odclenena ako samostatna abstraktna trieda, ktorej podtriedy budu reprezentovat konkretne operacie.
Pozadovane vlastnosti binarnej operacie:
- binarna operacie je asociativna (ab)c=a(bc)
- dokaze 'zoperovat' dva prvky
- vie urcit niektore svoje vlastnosti, napr. komutativnost, uzavretost na podmnozine, atd.
Binarna operacia ako taka reprezentuje 'predpis', ktorym sa z dvoch prvkov vytvori treti, a algoritmy, ktore na zaklade tohto 'predpisu' urcia popisane charakteristiky operacie. Teda nie je zavisla na konkretnej mnozine a je postacujuce, ak bude pracovat na nejakej abstraktnej reprezentacii vsetkych pripustnych mnozin (zvacsa pojde o urcity druh ciselnej mnoziny), na ktorej sa dana operacia jednoducho realizuje. Konkretne algebraicke struktury vsak pracuju na konkretnych mnozinach, a teda je potrebny urcity 'wrapper' pre kazdu mnozinu, ktory ju dokaze pretransformovat do podobny vhodnej pre operaciu a naopak (MappingOfSet). Vzhladom na svoj charakter je binarna operacia, podobne ako aj 'wrapper' abstraktnou triedou.
Implementovane algebraicke struktury (neabstraktne triedy):
SemiGroup [pologrupa] - zakladna algebraicka struktura, skladajuca as len z mnoziny a jedinej binarnej operacie, na ktoru nie su kladene ziadne dalsie poziadavky. Pologrupa je teda zakladny objekt v hierarchii. Vsetky pologrupy su chapane ako aditivne, a to aj v pripade, ze pologrupova operacia nie je komutativna.Group [grupa] - pologrupa, v ktorej existuje neutralny prvok a ku kazdemu elementu existuje inverzny. Ocividne, grupa je specializaciou pologrupy a teda v triedovom diagrame je priamym potomkom pologrupy. V pripade, ze zakladna mnozina je konecna, grupa si sama vie overit, ci je skutocne grupou (t.j., ci jej operacia splna podmienky). Ak nie je konecna, grupe nezostava ine, len sa spolahnut na vhodnu definiciu operacie.
Kompletny Class Diagram:
Aktualny stav projektu:
| Analyza | kompletna |
| Implementacia internej funkcionality | kompletna |
| Priklady | kompletne |
| e-modularna aritmetika | pripravene |
| e-ukazka sifrovania | pripravene |
Priklady:
Modularna aritmetika
Modularna aritmetika na cislach
| GZ := (0 to: 5) asAdditiveGroupZn | "Vytvori (aditivnu) grupu Zn s prvkami 0..5" |
| GZ operateOn: 4 and: 1. | "Zrealizuje grupovu operaciu na prvkoch 4 a 1" |
| GZ operateOn: 5 and: 4. | " dtto " |
| GZ invert: 3. | "Najde inverzny prvok k trojke" |
Cely tento mechanizmus vsak funguje vseobecnejsie (na lubovolnych konecnych mnozinach).
| GZ := #('Ziadne jablcko' 'Jedno jablcko' 'Dve jablcka' 'Tri jablcka') asAdditiveGroupZn. |
| GZ operateOn: 'Dve jablcka' and: 'Jedno jablcko'. |
| GZ operateOn: 'Tri jablcka' and: 'Jedno jablcko'. |
Jednoducho ukazeme, ako sa spravaju zvysky po deleni 3 pri scitavani
| Zvysky3 := #('zvysok0' 'zvysok1' 'zvysok2') asAdditiveGroupZn | "zvysky modulo 3" |
| Zvysky3 operateOn: 'zvysok1' and: 'zvysok1' | "scitanim dvoch cisel so zvyskom 1" |
| Zvysky3 operateOn: 'zvysok0' and: 'zvysok2' | "zvysok 0 nemeni zvysok suctu" |
| Zvysky3 neutral | " a teda neutralnym prvkom je ..." |
Dalsi priklad:
| Znamienka := #('plus' 'minus') asAdditiveGroupZn | "+ a -" |
| Znamienka invert: 'minus' | "ake je prevratene cislo k zapornemu" |
| Znamienka operateOn: 'minus' and: 'minus' | "minus a minus da plus " |
| Znamienka basicset domain | "vsetko ma svoje... :) " |
Priklady inych typov grup
Multiplikativna grupa Zn*
| GZ := GroupZnStar new: 42 | Vytvori grupu s cislami < 42, nesudelitelnymi so 42 |
| GZ raiseElement: 23 toPower: 81 | najde 81 mocninu prvku 23 |
| GZ neutral | neutralny prvok |
Testovanie prvociselnosti velkych cisel
| 17 isFermatPRPInBase: 10 | "je 17 Fermatovo PRP pri zaklade 10?" |
| 341 isFermatPRPInBase: 2 | "je 341 Fermatovo PRP pri zaklade 2?" |
| 341 isFermatPRPInBase: 3 | "je 341 Fermatovo PRP pri zaklade 3?" |
| 561 isFermatPRPInBase: 7 | "je 561 Fermatovo PRP pri zaklade 7?" |
RSA - demonstracia
| RS := GroupRSA p: 11 q: 17 | "vytvori RSA kodovaciu grupu " |
| RS verifyKey: 3 | "overi, ci 3 je vhodny sifrovaci exponent" |
| RS makeDecryptionKey: 3 | "najde desifrovaci (privatny) kluc " |
| RS encrypt: 54 with: 3 | "zasifruje spravu 54 verejnym klucom" |
| RS decrypt: 10 with: 107 | "rozsifruje spravu privatnym klucom" |
Download: finalny changeset - as.cs
1-Sep-2011