KOMPUTERALGEBRA RENDSZEREK ´ BEADANDOK 2010-2011.I Czirbusz S´andor 2010. november 6.
I. r´ esz
Felt´ etelek K´etfajta feladat van, mindenkinek mindk´et t´ıpusb´ol legal´abb egy-egy feladatot kell megoldani. Vagy matematikai modellt kell k´esz´ıteni, vagy programot a kit˝ uz¨ ott feladatra. A matematikai modelleket vagy Maple- vagy Sage-munkalapban kell megoldani, nem k¨otelez˝o programot ´ırni, ahol lehet k´esz´ıts¨ unk grafik´ at illetve anim´ aci´ot. Itt a v´alasztott komputeralgebra rendszer minden tud´ asa alkalmazhat´ o. A program´ır´ asn´ al a v´alasztott rendszer ,,magas szint˝ u” tud´ asa nem haszn´alhat´ o, azaz ha megoldhat´o egy utas´ıt´assal (p´eld´ aul LinSolve), azt tilos alkalmazni. A feladatok mellett tal´ alhat´ o bet˝ u utal´ as a modell vagy program sz´ ora, de nem k¨otelez˝ o ragszkodni hozz´ a. A sz´ am a feladat pont´ert´ek´e jel¨oli.
II. r´ esz
Feladatok 1. Kriptogr´ afia 1.1. ,,Pap´ıros–ceruz´ as” kriptogr´ afia Az itten elj´ar´ asokat ak´ar munkalaposan lehet szeml´eltetni, ak´ar programot lehet r´ a ´ırni. C´elszer˝ u t¨ obbet is feldolgozni ,,egy f¨ ust alatt”. 1.1.1. Transzpoz´ıci´ ok R´ acsos ker´ıt´ es : (20P) A sz¨ oveget t¨obb sorba cikk-cakkban ´ırjuk le, majd a sorokb´ ol ¨ ossze ´ all´ıtjuk az u ¨zenetet. P´eld´ aul az ,,informatikus vagyok” 1
sz¨ ovegre i o a k g k n r t u v y f m i s a o A ,,k´odolt” sz¨ oveg :,,ioak gnrtuvykfmisao” (A c´elszer˝ u karakterk´eszletet korl´ atozni) Forg´ o r´ acs : Adott egy n´egyzetr´acs, a r´ acsok negyede lyukas. A r´ acsot r´ ateszik egy pap´ırra, majd a lyukaba ´ırj´ak az u ¨zenet els˝ o r´esz´et. Ezut´an a r´ acsot 90 fokkal elforgatj´ ak a n´egyzet k¨oz´eppontja ker¨ ul, a sz¨ oveg m´ asodik r´esze az ´ıgy keletkezett lyukakba ker¨ ul. Ugyanezen ir´ anyba u ´jra elforgatj´ ak, u ´jra be´ırj´ak a sz¨ oveget a lyukakba, majd m´egegyszer. Egyszer˝ u oszlopcsere : Kital´ alunk egy olyan kulcsz´ot, ami csupa k¨ ul¨ onb¨ oz˝o bet˝ ub˝ ol ´ all. Fel´ırjuk egy t´ abl´ azat tetej´ere, a sz¨ oveget sorokra t¨ordelve bet˝ ur˝ ol bet˝ ure ´ırjuk a t´ abl´ azatban kulcs bet˝ ui al´a. Ezut´an a kulcs bet˝ uit rendezz¨ uk, a rendez´essel mozgatjuk a sz¨ oveg oszlopait is. (Kulcscsere ,) Luigi Sacco oszlopcser´ eje : Ugyan´ ugy, mint az egyszer˝ u oszlocser´en´el, fel´ırunk egy kulcsz´ ot, majd a kulcsz´o bet˝ ui al´a oda´ırjuk, a rendez´esebn hanyadikok. A sz¨ oveget sorfolytonosan ´ırjuk, az els˝ o sorban az 1-et tartalmaz´ o oszlopig, a m´ asodik sorban a 2-t tartalmz´ o oszlopig, s´ıt. A ,,tiktos sz¨ oveg” az oszlopokban van. Nihilista transzpoz´ıci´ o : Most a kulcsz´ot nemcsak az oszlopfejl´ecekbe, hanaem a sork elej´ere is be´ırjuk. Az sozloponk´enti rendez´es ut´ an rendezz¨ uk a sorokat is, a titkos´ıtott sz¨ oveg a sorokban van. Cadenus : Most is egy kulcs al´a ´ırjuk a sz¨ oveget, de a sz¨ ovegt˝ol balra egy oszlopba fel´ırjuk a haszn´alt ´a´ec´e bet˝ uinek egy permut´ aci´oj´at. Rendezz¨ uk a kulcs szerint az oszlopokat, majd minden oszlopot felfel´e rot´ alunk a k¨ovetkez˝ ok´epp : megn´ezz¨ uk, a k´od bet˝ uje hol van a permut´ alt ´ab´ec´eben, megfelel˝o oszlopot adig toljuk felfel´e, amig a sor–sozlop metsz´espontban l´ev˝o bet˝ u az les˝ o poz´ıci´ ora ker¨ ul. 1.1.2. Egy´ ab´ ec´ es helyettes´ıt´ es KamaSutra k´ odol´ as : Az ´ab´ec´e bet˝ uit t´abl´ azat alapj´an p´ aros´ıtjuk, a megfeleltet´est v´eletlengener´al´assal v´egezz¨ uk. ´ Caesar k´ odol´ as : A k´odol´ ast u ´gy v´egezz¨ uk, hogy az ABC bet˝ uit adott sz´ ammal k¨orbe shiftelj¨ uk. 2
Affin cipher :
KamaSutra ut´ ana Caesar
Nihilista helyettes´ıt´ es(angol ´ ab´ ec´ evel) : A ,,j”–t azonosnak vessz¨ uk az ,,i”–vel. Az ´ ab´ec´et v´eletlesnzer´ uen be´ırjuk egy 5 × 5-¨os t´abl´ azatba, a sor- ´es oszlopsorsz´ amokb´ ol kapunk egy k´etejgy´ u k´odot a bet˝ ukh¨oz. Elrendezz¨ uk a kulcsz´ o al´ a megint a sz¨ oveget. A sz¨ oveget u ´gy k´odoljuk, hogy a bet˝ u k´odj´ahoz hozz´ aadjuk a felette l´ev˝o kulcsbet˝ u k´odj´at. Ha az eredm´eny nagyobb 100–n´ al, levonunk bel˝ole 100–at. ´ ep˝ Atl´ os t´ abla K´esz´ıt¨ unk egy 3 × 10–es t´abl´ azatot, indexelj¨ uk a sorokat– oszlopokat 0–val kezdve. A k´odjaink 1 ´es k´etjegy˝ u sz´ amok lesznek. Az ´ab´ec´et be´ırjuk a t´ abl´ azatba sorfolytonosan u ´gy, hogy a kulcsz´oval kezd¨ unk, ut´ ana a megmaradt bet˝ uk.
0 1 2
0 C A N
1 D O
2 E P
3 Z F Q
4 I G T
5 R H V
6 B J W
7 U K Y
8 S L .
9 Z M /
A k´et kih´ uzott hely az´ert van, mert nem haszn´alhat´ o az 1 ´es 2 egyjegy˝ uk´ent. (Ennek vari´ ans´ at haszn´alt´ ak az orosz k´emek a II. vil´agh´ abor´ uban) Bacon titkos´ır´ asa Az ´ ab´ec´e minden bet˝ uje kapjon egy 5 jegy˝ u bin´ aris k´odot, a speci´ alis karakterek hatjegy˝ uek. K´ odoljuk ´at az u ¨zenetet, majd vegy¨ unk egy ugyanilyen hossz´ u ´artalmataln sz¨ oveget(ak´ ar halandzsa is lehet). Ahol a k´odban 0 van, ott kisbet˝ ure v´altunk, ahol 1, ott nagybet˝ ure. 1.1.3. T¨ obb´ ab´ ec´ es helyettes´ıt´ es Vig` enere : K´esz´ıt¨ unk egy k´odol´ o t´abl´ at, sor- ´es oszlopfejl´ecei az ´ab´ec´e bet˝ ui, minden sorba az ´ ab´ec´e permut´ aci´oi ker¨ ulnek (k¨ ul¨ onb¨ oz˝o). A titkos´ıdand´o sz¨ oveg al´ a ´ırjuk a kulcsot, ha r¨ ovidebb a kulcs, ism´etelj¨ uk. Majd a k k´odoland´o bet˝ u ´es kulcsbet˝ u p´ arhoz tartoz´ o bet˝ ut keress¨ uk ki a k´odt´ abl´ ab´ ol. Vig` enere vari´ ans: m´ asoljuk le
Ha r¨ ovid a kulcs nem ism´etelj¨ uk, hanem shiftelve
1.2. ,,Modern” kriptogr´ afia 1.2.1. AES A Sage mini-AES csomagj´ar´ ol k´esz´ıts¨ unk prezent´aci´ot.
3
2. Sz´ amelm´ elet 2.1. M´ odos´ıott euklideszi algritmus A k¨ovetkez˝ o egyszer˝ u sz´ amelm´eleti t´enyeket kihaszn´ alva ´ırjunk m´ odos´ıtsuk u ´gy az euklideszi algoritmust, hogy az algoritmus ,,sz´ amol´ os” r´esze m´ ar egyszeres pontoss´ ag´ u eg´eszekkel dolgozzon: gcd(a, b) = gcd(b, a − mb), minden m ∈ Z eset´en a b gcd(a, b) = 2 · gcd( , ), ha a, b p´ arosak 2 2 b gcd(a, b) = gcd(a, ), ha a p´ aratlan b p´ aros 2
2.2. Ker´ ek–faktoriz´ aci´ o A ker´ekfaktoriz´ aci´ o m´ odszere a k¨ovetkez˝o 1. Valamilyen m´ odszerrel (pl : tudjuk r´ oluk ) hat´ arozzuk meg az els˝ on pr´ımsz´ amot, k´esz´ıts¨ uk el a szorzatukat, legyen ez N 2. Egy k¨or ker¨ ulet´ere ´ırjuk k¨orbe az 1, 2, . . . , N sz´ amokat 3. Egy nagyobb koncentikus k¨or ker¨ ulet´ere ´ırjuk fel az N +1, N +2, . . . , 2N sz´ amokat u ´gy, hogy a sz´ am hely´ehez vezet˝o sug´ aron (k¨ ull˝ o) pont az 1, N + 1, 2, N + 2, . . . sz´ amok legyenek 4. Folytassuk am´ıg kimer´ıtj¨ uk a sz´ amtartom´ anyt 5. Karik´ azzuk be a bels˝ o k¨or¨ on az els˝ o n pr´ımet, majd h´ uzzuk ki a hozz´ atartoz´ o k¨ ull˝ on az ¨osszes sz´ amot 6. Minden pj eredeti pr´ımre h´ uzzuk ki a bels˝ o k¨or¨ on p2j –t˝ol N –ig a pj t¨ obbsz¨or¨ oseit ´es a megfelelel˝o k¨ ull˝ ot is.
2.3. Benford szab´ aly : M´ask´epp az els˝ o sz´ amjegy szab´ alya, azt mondja ki, hogy a val´os forr´asb´ ol ered˝ o (pl. m´er´esi eredm´enyek) sz´ amlist´ ak els˝ o sz´ amjegy´enek eloszl´ asa nem egyenletes. P´eld´ aul az 1 els˝ o sz´ amjegyk´ent majdnem 13 gyakoris´ aggal fordul amok megs´ertik ezt a szab´ alyt. K´esz´ıts¨ unk el˝o. (B˝ovebben itt) A pr´ımsz´ modellt, amelyik k¨ ul¨ onb¨ oz˝ o sz´ amrendszerekben teszteli ezt.
2.4. Pr´ımgener´ al´ as L´etezik olyan a val´ os sz´ am, hogy az f : N → Z, n 7→ a3n csak pr´ımet gener´ al. Modellezz¨ uk ilyen val´os sz´ am keres´es´et.
4
2.5. Primit´ıv gy¨ ok keres´ ese I Adott eg´esz sz´ amra keress¨ uk meg az ¨osszes primit´ıv gy¨ ok´et. Ezut´an 1 ´es 1000 k¨oz¨ ott minden pr´ımnek keress¨ uk meg az ¨osszes primit´ıv gy¨ok´et
3. Kalkulus 3.1. Riemann-integr´ al´ as defin´ıci´ o szerint N´eh´ any elemi f¨ uggv´eny p´eld´ aj´an modellezz¨ uk le a Riemann–integr´ al´ast a defin´ıci´ o alapj´an (Anim´ aci´ o sz¨ uks´eges)
3.2. G¨ orbe ´ıvhossza N´eh´ any egyszer˝ u g¨ orbep´eld´ aj´an modellezz¨ uk le a g¨ orbe–ivhossz sz´ am´ıt´ast (Anim´ aci´ o sz¨ uks´eges)
3.3. Az ´ ehes kutya A der´eksz¨og˝ u koordin´atarendszerben az y = a egyenes ment´en a > 0 haladunk, p´ or´ azon vezet¨ unk egy kuty´at, a p´ or´ az hossza 0 < l < a. Az orig´ oban valaki elhelyezte a kutya kedvenc ´etel´et. A kutyus mindig alehet˝ o legk¨ozelebb igyekszik ker¨ ulni a csemeg´ehez. Modellezz¨ uk le a kuyta ´altal ,,le´ırt” p´ aly´at.
3.4. A h´ az˝ orz˝ o A kutya egy bet¨ or˝ ot kerget, mindig u ´gy, hogy adott pillanatban pont gazfick´o pillanatnyi helyzet´et veszi c´elpontnak. Modellezz¨ uk a kutya mozg´ as´ at a bet¨ or˝ o mozg´ as´ at´ ol f¨ ugg˝ oen.
3.5. Newton-iter´ aci´ o Az f (x) = 0 egyenlet gy¨okeinek megtal´ al´as´ ahoz ´ırjuk meg az iter´ aci´ot. K´esz´ıts¨ unk grafikont is!
4. Val´ osz´ın˝ us´ egsz´ am´ıt´ as 4.1. G¨ orbe alatti ter¨ ulet sz´ am´ıt´ asa Sz´ am´ıtsuk ki egy g¨ orbe alatti ter¨ uletet a k¨ovetkez˝ok´epp: ha az y(x) a g¨orbe egyenlete, akkor az (a, 0), (b, 0), (0, y(a)), (0, y(b)) t´eglalapon (a, b ∈ R) v´eletleszer˝ uen vegy¨ unk fel pontokat, majd adott mintav´etelez´esi hat´ ar el´er´ese ut´ an becs¨ ulj¨ uk a ter¨ uletet a g¨orbe alatti ´es g¨orbe feletti pontok sz´ am´ anak ar´ any´ab´ ol.
5
5. K´ odol´ as 5.1. Huffmann-k´ od A bemen˝ o adataink a jelk´eszlet, a jelek relat´ıv gyakoris´ aga, illetve a kimen˝o jelk´eszlet. K´esz´ıts¨ uk el a k´odot, tesztelj¨ uk is.
5.2. BCH-k´ od K´esz´ıts¨ unk bin´ aris BCD-k´ odot! Bemen˝ o adat (n, k).
6. Algebra 6.1. Diszkr´ et Fourier transzform´ aci´ o K´esz´ıts¨ unk programot a gyors Fourier-transzformc´ aira, invez´ere, ´es a gyorsszorz´ asra.
6.2. Di´ eder–csoport Modellezz¨ uk le adott n eset´en a Dn di´edercsoportot!
7. Line´ aris algebra 7.1. Gauss-elimin´ aci´ o ´Irjunk programot line´ aris egyenletrendszer megold´ as´ ara Gauss-elimin´ aci´oval.
7.2. H´ aromsz¨ og sz¨ og¨ oszege Az A(3, 2), B(2, 5), C(7, 9) pontokr´ol ´allap´ıtsuk meg, hogy lehetnek egy h´ aromsz¨og cs´ ucspontjai. Sz´ am´ıtsuk ki a h´ aromsz¨og ter¨ ulet´et, ker¨ ulet´et, bizony´ıtsuk be, ´ hogy a sz¨ og¨ osszeg 2π. Altal´ anos´ıtsunk
7.3. Forgat´ as Rajzoljunk egy h´ azik´ot (mint kisiskol´as korunkban), majd anim´ aljuk az egyik tengely k¨or¨ uli forgat´as´ at.
8. Egy´ eb 8.1. Nyolc vez´ er Helyezz¨ unk el a sakkt´ abl´ an 8 vez´ert u ´gy, hogy ne u ¨ss´ek egym´ast! Keress¨ uk meg az ¨ osszes lehets´eges elhelyez´est! K´esz´ıts¨ unk anim´ aci´ot !
6
8.2. Ford´ıtott lengyel jel¨ ol´ es ´Irjunk programot, mely a bemen˝ o infix matematikai kifejez´est ´atalak´ıtja ´ ekelj¨ postfixsz´e. Ert´ uk ki a kifejez´est az ut´ obbi alakb´ol!
8.3. ”Tekn˝ oc” - grafika ´Irjunk olyan elj´ ar´ ast, mely r´eszben szimul´ alja a tekn˝oc - grafik´at! A bemen˝ o param´eter egy karaktersorozat, mely f,+,− jelekb˝ ol ´all. Az ”f” egys´egnyi hossz´ u vonal h´ uz´ asa a ”tekn˝oc orra” ir´ any´aba, ”+” elfordul´ as jobbra 900 -al, ”-” ugyanez balra. M´ odos´ıtsuk az el˝ oz˝ o elj´ar´ ast egy helyettes´ıt´esi szab´ aly bevezet´es´evel! A szab´ aly pl. ilyen alak´ u : ”f ← ff+f+f+f+f+f-f”, ami azt jelenti, hogy a nyil baloldal´ an l´ev˝o karaktersorozat minden el˝ofordull´ as´ at helyettes´ıti a ny´ıl jobboldal´ an l´ev˝ovel. M´ odos´ıtsuk iter´ aci´ o bevezet´es´evel a fenti elj´ar´ ast! Harmadik param´erek´ent egy iter´ aci´ o-sz´ amot adunk meg. A helyettes´ıt´es ennyiszer kell v´egrehajtani (Mindig az eredm´enysztringen!)
8.4. R´ omai sz´ amok K´esz´ıts¨ unk olyan programot, amivel r´ omai sz´ amokat tudunk helyi´ert´ekess´e konvert´ alni oda ´es vissza.
7
