MATEMAATIKA ARVESTUS 1. Kombinatoorika põhiprintsiibid-liitmis ja korrutamisprintsiip. Liitmisprintsiip- ,,kas üks või teine" . kui mingit objekti A on võimalik valida n erineval viisil ja objekti B m erineval viisil ning valida tuleb kas objekt A või objekt B, siis kõigi erinevate võimalike valikute arv on n + m. Korrutamisprintsiip- ,, nii üks kui ka teine" kui mingit objekti A on võimalik valida n erineval viisil ja objekti B m erineval viisil ning valida tuleb nii objekt A kui ka objekt B, siis kõigi võimalike erinevate valikute arv on n · m. 2. Permutatsiooni permutatsioonideks n erinevast elemendist nimetatakse nende elementide kõikvõimalikke erinevaid järjestusi. Pn = n! 3. Variatsioonid Variatsioonideks n elemendist k-kaupa (k n) nimetatakse nelemendilise hulga kõigi k-elemendiliste osahulkade elementide erinevaid järjestusi. Vnk = n!/(n-k)! k 0! = 1 Variatsioonides on oluline liikmete järjestus erinevalt kombinats...
n elementi on erinevad ja et ühes ühendis võib iga element esineda ülimalt ühe korra. Praktika probleemid nõuavad aga vahel ühendite üldistamist ka nendele juhtudele, mil kas antud elementide hulgas esineb ühesuguseid või antud elementidest igaüks võib ühes ja samas ühendis esineda mitu korda. Esinegu antud n elemendi hulgas korda element a, korda element b jne, korda element l, kusjuures + + ... + = n. Neist n elemendist moodustatud permutatsioone nimetatakse kordumistega permutatsioonideks. Kõigi võimalike erinevate kordumistega permutatsioonide arvu n elemendist (mis ei pruugi olla erinevad) tähistatakse sümboliga Pn(,,...,). Kui = = ...= = 1 (iga element esineb ainult üks kord), siis muidugi Pn(1,1,...,1) = Pn = n! . Arvu Pn(,,..,) leidmiseks üldjuhul arutleme järgmiselt. Varustame elemendid a (neid on tükki) indeksitega 1,2,...,, ele- mendid b indeksitega 1,2,..., jne, elemendid l indeksitega 1,2, ...,. Sel teel
positsioonides on samad väärtused. Järjendi puhul on oluline temas sisalduvate elementide järjestus. (Nt. hulk [3] järjendeid on 9: 11,12,13,21,22,23,31,32,33) Permutatsioonid- n-permutatsioonideks nimetatakse järjendeid, mis on mingi lõpliku hulga A kõikkide elementide n kõikvõimalikud ümberpaigutused. (n!) k-permutatsioonideks nimetatakse järjendeid, mis on mingi lõpliku hulga A teatud alamhulga elementide kõikvõimalikud ümberpaigutused. k-permutatsioone nim. ka variatsioonideks. (Nt. hulk[3] 1-permutatsioonid: 1,2,3) *Arvutada saab: n-permutatsioone Pn = n! ning k-permutatsioone Kombinatsioonid- k-kombinatsiooniks nimetatakse hulga A igat k-elemendilist alamhulka. (Nt. hulk[3] 2-kombinatsioonid: {12,13,23}). *Arvutada saab: [4]. Binoomi valem. Pascali kolmnurk. *Kombinatsioonide arvu tähist nimetatakse sageli ka binoomkordajaks. See tulenebgi aga (Newtoni) binoomivalemist.
Kombinatoorika valemeid ja mõisteid · Variatsioonideks n erinevast elemendist k kaupa nimetame ühendeid, mis sisaldavad k elementi antud n elemendist ning erinevad kas elementide või nende järjestuse poolest. Erinevaid variatsioone on A =n(n-1) ...(n-k+1)=n!/(n-k)! · Permutatsioonideks n elemendilisest hulgast nimetame ühendeid, mis sisaldavad kõiki n elementi (üks kord) ja erinevad järjestuse poolest. Erinevaid permutatsioone on Pn=n (n-1) ...1 = n! · Kombinatsioonideks n elemendist k kaupa nimetame ühendeid, mis sisaldavad k elementi (antud n elemendi hulgast) ja erinevad vähemalt ühe elemendi poolest. n! · Erinevaid kombinatsioone on C =A /Pk C nk = ( n - k )!k! Tõenäosusteooria
i2 3 . . . n , 21 kus (n - 1)-elemendiline permutatsioon 2 3 . . . n on permutatsioon hulga {1, 2, . . . , i - 1, i + 1, . . . , n} elementidest. Matemaatilise induktsiooni eel- duse kohaselt on selles hulgas (n - 1)! permutatsiooni. Mistahes i, j Nn , (i) (j) kus i = j, korral ei ole hulkadel Pn ja Pn u ¨hiseid permutatsioone, sest erinevus on juba esimeses arvus. Seega hulga Pn permutatsioonide arv (1) (2) (n) v~ordne hulkade Pn , Pn , . . . , Pn permutatsioonide arvu summaga, s.o. (n - 1)!n = n! Definitsioon 2.1. Oeldakse, ¨ et permutatsioonis 1 2 . . . i . . . j . . . n elemendipaar (i , j ) moodustab inversiooni, kui selles paaris esimene arv i on suurem teisest arvust j , s.o. i > j .
iα2 α3 . . . αn , 21 kus (n − 1)-elemendiline permutatsioon α2 α3 . . . αn on permutatsioon hulga {1, 2, . . . , i − 1, i + 1, . . . , n} elementidest. Matemaatilise induktsiooni eel- duse kohaselt on selles hulgas (n − 1)! permutatsiooni. Mistahes i, j ∈ Nn , (i) (j) kus i = j, korral ei ole hulkadel Pn ja Pn u ¨hiseid permutatsioone, sest erinevus on juba esimeses arvus. Seega hulga Pn permutatsioonide arv (1) (2) (n) v˜ordne hulkade Pn , Pn , . . . , Pn permutatsioonide arvu summaga, s.o. (n − 1)!n = n! ♠ Definitsioon 2.1. Oeldakse, ¨ et permutatsioonis α1 α2 . . . αi . . . αj . . . αn elemendipaar (αi , αj ) moodustab inversiooni, kui selles paaris esimene arv αi on suurem teisest arvust αj , s.o. αi > αj
. . , _n on I (_1, _2, . . . , _n). Paaritu permutatsioon permutatsiooni nimetatakse paarituks permutatsiooniks, kui tema inversioonide arv on paaritu Paaris permutatsioon - permutatsiooni nimetatakse paaris permutatsiooniks, kui tema inversioonide arv on paaris OMADUSED: 1) Hulga n elementidest saab moodustada n! permutatsiooni 2) Kui permutatsioonis omavahel ära vahetada 2 elementi, siis permutatsioon muudab paarsust 3) kui n>=2, siis permutatsioonide hulgas Pn on paaris ja paarituid permutatsioone samapalju, st kumbagi ½n! DETERMINANT: Determinant Me nimetame n-järku ruutmaatriksi determindandiks reaalarvu, mida tähistame |X| ja leiame valemiga |X|= OMADUSED: 1) maatriksi ja transponeeritud maatriksi determinandid on võrdsed, s.t. X Mat(n, n) => | X |=| XT | 2) maatriksi kahe rea (veeru) äravahetamisel muudab maatriksi determinant märki. 3) Kui maatriksi kaks rida (veergu) on võrdsed, siis maatriksi determinant on 0
Nagu näha, seisnebki algoritmi turvalisus kõigepealt plokis E teatud bittide duplikatsioonide võrra 32 bitisest jadast 48 bitise kasvatatamises, S-plokkides toimuvast teisendusest maatriksite alusel ja lõpus toimuvast fikseeritud permutatsioonist. Sellega saab asja ajada päris sogaseks. . Alamvõtmete koostamine toimub järgmist algoritmi kasutades. Siin <<< kastid on nihkeregistrid PC kastid teostavad permutatsioone. Nende abiga genereeritakse igal ringil uus 48 bitine alamvõti. Kokku genereeritakse 16 alamvõtit, kuna ringe feisteli funktsioonidega ongi kokku ju 16. Dekrüpteerimisel tehakse kõiki tehteid tagurpidi järjestuses ja sama võtit kasutades. Kuna see asi muugiti lahti, siis tänaseks on kasutusel 3DES algoritm, mis oma olemuselt on sama, ainult et esialgne info krüpteeritakse kolm korda: esimene kord esimese võtmega, teine kord juba uue võtmega ja kolmas kord jälle uue võtmega
annaabi.ee 
