Informatika | Információelmélet » Tóth Ákos - Bevezetés az informatikába, 2003

by rz4s™ Bevezetés az Informatikába Jegyzet Tóth Ákos előadása alapján BMF-NIK 2002/2003 by rz4s & UFO Szabadon felhasználható, de kéretik a szerzők „nick”-jét nem törölni! Köszi 1 by rz4s™ Az információ fogalma: Információn egy adott véges halmaz egy elemének megnevezését értjük Hartley-formula: Ha n lehetséges választás van, akkor az információ tárolásához szükséges mennyiség I = log 2 n [bit]. Ha n nem egész szám, akkor felfelé kerekítünk, hogy ne vesszen el adat Kétféle információt lehet egy biten tárolni : 0 és 1 Példa: Ötös lottó, 6 lehetőség, 0-5 találat,  n = 6 X = {x1 ,., xn } P = { p1 ,., pn } Akkor beszélünk információról, ha a valószínűsége (p) is adott ! n ∑p i =1 i =1 0 ≤ pi ≤ 1 Példa: Fej vagy Írás, 50% esély  n=2 I = log 2 2 = 1 ennyi bit kell Az információ mennyisége 1 ∀i -re , pi = esetén visszaadja a Hartley-formulát, és figyelembe veszi a

valószínűséget is. n 1 I = log p ( A) Információn általában valamely véges számú, és előre ismert lehetőség valamelyikének megnevezését értjük. A problémát úgy fogalmazhatjuk meg, hogy mennyi információra van szükség egy adott ( x1 ,., xn ) véges halmaz valamely tetszőleges elemének kiválasztásához Információmennyiségről csak akkor beszélhetünk, ha a lehetséges alternatívák X halmaza adott. Hartley nem veszi figyelembe, hogy az egyes alternatívák ( információk ) nem feltétlenül egyenértékűek. 1 mennyiségű p ( A) információt szolgáltat, vagyis az információ annál több, minél kevésbé valószínű. 1 valószínűségű, akkor a H formulához jutunk: Ha az n lehetőség mindegyike n Shannon szerint p(A) valószínűségű A esemény bekövetkezése I = log n H = −∑ pi log pi ( az információ átlagos mennyisége bitben ) i =1 ξ = log 1 (entrópiasűrűség) p (ξ ) Fának nevezzük az olyan irányított gráfokat,

amelyekben egy kitüntetett kezdőponttól ágak indulnak ki, melyek a későbbi szögpontokban ismét elágaznak, de újra nem találkozhatnak. 2 by rz4s™ Azokat a szögpontokat, melyekből további élek nem indulnak ki, végpontoknak (levélpontoknak) nevezzük. A kezdőpontot mindegyik végponttal pontosan egy ág köti össze Az ágat alkotó élek számát az ág hosszának nevezzük. Tekintsünk egy n végpontú fát, és rendeljük hozzá a fa ágaihoz a fenti n elemű x halmaz elemeit. Valószínűség: Valós rendszerekben az egyes szimbólumok előfordulási valószínűsége nem azonos, így információ tartalmuk sem azonos. Az információ tartalma és az előfordulás valószínűsége fordított arányban áll egymással. Az egyes szimbólumok pi valószínűséggel jelennek meg, n ∑p i =1 i = 1 (azaz 100%) Shannon-entrópia: A független események együttes előfordulásának törvényszerűségét felhasználva Shannon szerint a következő formulával

számolható az átlagos információ tartalma: n H = −∑ pi log pi [bit/szimbólum] i =1 Az entrópia tulajdonságai: Def: Az entrópia a rendszerben lévő határozatlanság ( rendezetlenség, bizonytalanság ) mértéke. Maximális értékét akkor veszi fel, ha minden állapot bekövetkezési valószínűsége 1 azonos, azaz, ha pi = n Példa: Pénzfeldobás, lehetséges esetek száma  n=2 H = −( p ⋅ log p + (1 − p ) ⋅ log(1 − p )) p = 0 esetén H = 0 Ebben az esetben a bizonytalanság akkor a legnagyobb, ha a pénz szabályos (50-50%). N tetszőleges n H = −∑ pi log pi i =1 ∀i -re pi =0 esetén létezik olyan pk=1, amely 1-el egyenlő H = − p1 log p1 + −( p2 log p2 ) + . + −( pn log pn ) 0 1 0 Nem negatív tagok összege akkor 0, ha mindegyik tag 0 3 by rz4s™ Mi az entrópia maximális értéke? N = tetszőleges Hmax=? n H max = −∑ log 2 pi = i =1 n 1 1 = −∑ ⋅ log 2 = n i =1 n 1 1 1 1 = − (log 2 + log 2 + . + log 2 ) = n n n

n n 1 = − log 2 = n n 1 = − log 2 = log 2 n n Az entrópia további tulajdonságai: - az entrópia csak az eloszlástól függ, az értékkészlettől nem - negatív értéket nem vehet fel - invariáns az állapotok sorrendjére nézve - az entrópia csökkenése csak befektetés útján lehetséges - ha a rendezettség nő, az entrópia és a stabilitás csökken - a stabil rendszerek teljesen rendezettlenek Keresés-elmélet: Feladat: Bar-Kochba: igen/nem ( 1bit információ ) H = összes biten 8 pénzről el kell dönteni melyik az, amelyik könnyebb mint a többi Kétkarú mérleggel 1. módszer: ( 3 lépés ) 2.módszer ( 2 lépés ) 4 balra – 4 jobbra 3 balra – 3 jobbra – 2 asztalon 2 balra – 2 jobbra 1 balra – 1 jobbra – esetleg 1 asztalon 1 balra – 1 jobbra H = log 2 2 = 1 3 3 3 1 2 H = −( ⋅ log + ⋅ log + ⋅ log 2 8) 8 8 8 8 8 ( 1 méréssel több információhoz jutunk, mint az előbb, ezért kisebb a H ) Fealdat: 1000 katonából egy vérbajos,

hány vizsgálatból lehet megállapítani melyik az ? Mo: Felezéssel H = log 2 1000 = 10 , 1024-re kiegészítve ( ? ) 1 1 108 1023 (?) ⋅ log + ⋅ log 1024 1024 1024 1024 4 by rz4s™ Kódolás , tömörítés: Fa-összefüggő, körmentes gráf Def: xi elem kódjának hossza az az ágszám, ahány ágon át eljutunk hozzá. L( xi ) n átlagos kódhossz: L = ∑ L( xi ) ⋅ pi i =1 Példa: L( x3 ) = 2, L( x5 ) = 3 n Ha p1  pn valószínűség is adott: L = ∑ L( xi ) ⋅ pi i =1 Def: v szó a u folytatása, ha u-hoz további karaktereket adva v-hez jutunk. Pl: u = 0010 v = 001011 Def: Prefix kód: Ha a kód minden kódszava különböző, és egyik sem folytatása a másiknak. Morse-kód: - kódhossza változó - nem prefix kód, mert van benne folytatás - nem kódolható egyértelműen, mert nincsen benne elválasztó szimbólum Tétel: Ha egy kód prefix, akkor rajzolható hozzá kódfa. Minden levélpontra egy elemet teszünk Cél: az átlagos kódhossz

minimalizálása, az adatok minél kisebb helyen való tárolása - S betűkből álló kódábécé esetén a prefix kód átlagos kódhossza nem lehet kisebb, mint H log s Shanno-Fano kód: Probléma – elemeket rendezni kell ( x1 , xn ), ( p1 , pn ) csökkenő valószínűség szerinti rendezés 5 by rz4s™ Addig kell osztani, míg egy intervallumon csak egy elem marad. S=3, x1=0 A nagyobb valószínűségű elemek korábban kerültek egy intervallumba. H (ξ ) Átlagos kódhossz: s: az elágazások száma +1 log 2 s ξ = Shannon − entrópia Gilbert-Moore kód: ( x1 , xn ), ( p1 , pn ) prefix kód H (ξ ) + 1 L≤ +1 log 2 s - ez nagyobb, mint a SF - ennél nem lesz rosszabb az átlagos kódhossz Tétel: H (ξ ) ≤L log 2 s Az SF és GM koraiak, de jól megközelítik az alsó korlátot A kódolás során lukak keletkeznek. Elméleti alsó korlát tetszőleges prefix kódra: Az optimális kódolás kritériumai: A) p1 ≥ p2 ≥  ≥ pn biz: ∃k, j

hogy pk ≥ p j és, Lk ≥ L j L1 ≥ L2 ≥  ≥ Ln Így lehetne kódok felcserélésével optimális kódot csinálni  ellentmondás B) A kódfának teljesnek kell lennie, minden pontból pontosan s ér indulhat ki, kivéve a végpontot (ha ezt nem tartanánk be, egy üres helyre átmozgathatnánk egy elemet, így jobb kódot kapnánk) C) A két legkisebb gyakoriságú/valószínűségű elem kódhossza egyenlő, ezek a gyökértől a legtávolabb eső elemek. Javítani ezen elemek felcserélésével  nem optimális kód  szabály felrúgása A Huffmann-kód: 1) Felírjuk a kódolandó szöveg egyes karaktereinek előfordulásait Szöveg: Geza kek az eg hello G – 2db, e – 4db, z – 2db, a – 2db - 4db, k – 2db, h – 1db, l – 2db, o – 1db 2) Csökkenő sorrendbe felírjuk a karaktereket 6 by rz4s™ 3) A 2 legkisebbet összekötjük, és odaírjuk a gyakoriságát, felül:0 – alul: 1 - prefix, mert kódfa rajzolható hozzá a kódfát tárolni

kell optimális kódot ad, A,B,C feltétel teljesül a gyakran szereplő elemek magasabbra kerülnek, később kötődnek össze Példa: Egy fekete-fehér kép tömörítetlenül tárolva 700E bit kell Huffmann-kódolással: 700E bit + kódfa ( tehát hosszabb ) Oka, hogy nem veszi figyelembe az egymás után következést RLE: A Run Length Encoding viszont csak bizonyos típusú adatokra működik jól. Választunk egy karaktert, amely legritkábban szerepel, pl: $ Így sakkkkkmattt sa$5kma$3t 4 ismétlődéstől érdemes használni ( PCX így működik ) Az LZW ( Lempel – Ziv – Welch módszer ) - merevlemez tömörítésre használják - 3 ismétlődéstől éri meg, de az egységben tárolt adatmennyiség határozza meg, hogy mennyire érdemes visszahivatkozni. - Nem muszáj mindig az először előforduló elemre hivatkozni Pl: The rain in Spain falls mainly on the plain The rain 33Sp84falls m123ly on 304p ezelőtt, hosszan - akkor működik jól, ha ismétlődő elemek

vannak a szövegben megállapodnak az 1 karakteres azonosítók kódjában, és rögzítik megnézzük, hogy az első és a második együtt benne van-e? pl: ABACABABAB A:=#1, B:=#2, C:=#3, D:=#4, AB:=#5, BA:=#6, AC:=#7, CA:=#8, ABA:=#9, ABAB:=#10 Kimenet: # 1, 2, 1, 3, 5, 1, 2 - nem prefix kód - az ismétlődések számától függ a kimenet ( rögzített kódtábla – 10-12bit ) Ha betelik a kódtábla: 7 by rz4s™ - elölről kezdjük az építést, töröljük az 1-nél nagyobb kódokat figyeljük, hogy az egyes elemeket milyen sűrűn használjuk a ritkán használtakat töröljük nem építünk minden egyes szövegre kódtáblát, hanem előre kiszámolunk egyet Kell tárolni a kódtáblát ? Nem, mert dekódolásnál AB találat esetén csak A kódját írja ki, így fel tudja építeni a kódtáblát. Dekódólás: - látja az első karakter kódját ( a szimplákét tudja ) - a következő kód az első kettőből jön létre - csak az első karaktert írja le

Kimenet: A,B,A,C Algoritmus: String := olvass 1 karaktert // objektumok: string, ch, kódtábla Ciklus amíg van input karakter Ch := olvas 1 karaktert Ha ( string + ch ) benne van a kódtáblában akkor string := string + ch Különben írd ki a string kódját és add hozzá( string + ch )-t a kódtáblához String := ch Ciklus vége Dekódolás: Olvass régi kód Írd ki régi kód Ciklus amíg van input Olvas új kód String := értelmezd új kódot Írd ki := string Ch := string első karaktere Hozzáadni régi kód + ch-t az értelmező táblához Régi kód := új kód Ciklus vége Számábrázolás-számrendszerek Az ember száméra a 3-as ill 2-es számrendszer túl hosszú, a 16-os túl rövid, mégis a 10-es számrendszert szoktuk meg. 2  16 Tetrádokat képzünk, majd ezeket egyenként átváltjuk 0010|1100|0100|.0100|1000 16 10 8 by rz4s™ pl: 3B(16 ) = B ⋅160 + 3 ⋅161 = 11 + 48 = 59 Valamely N szám az R alapú számrendszerben N egész = An−1 R n−1 +

 + A1 R + A0 N tört = A−1 R −1 +  + A−n+1 R − n+1 + A−n R − n rövidítve N r = An−1  A1 A0 , A−1  A−n+1 A−n ( R) radix vessző 10  2 - törtek esetén szorozzuk kettővel míg nullára , vagy ismétlődésre nem jutunk - a szorzat eredményének külső 0/1 értékét írjuk le - 1-nél nagyobb esetén kivonunk 1-et Általános algoritmus N ⋅ R = a1 + b1 b1 ⋅ R = a2 + b2 Állj: 0, ismétlődés, elfogytak a bitek Numerikus kódok: - csak számokat kódolnak - oktális/hexadecimális kód: a bináris egy-egy megjelenési formája, a rövidebb leírás érdekében BCD kód: - a számjegyeket külön kódoljuk, majd egymás mellé írjuk, így a gép tárolni tudja az adatokat. A BCD kód 12biten, míg hagyományos módon 8biten tárolhatunk - BCD-vel le lehet írni a tizedes jegyeket pontosan, könnyű az átalakítás - A CPU-kban van BCD aritmetika - A BCD 8421 a szabványos BCD kód, nem hatékony, mert 10 számjegy tárolására 4bit kell,

így 6 helyet feleslegesen foglalunk le NBCD átváltása decimális alakra: A számokat tetrádokra osztjuk, így kódoljuk. Az utolsó 6 kombináció nem fordul elő AIKEN-kód: Súlyozása: 2421 Képzése: helyiértékenként NAIKEN – N binárisan, ha N < 5, – N+6 binárisan, ha N ≥ 5 Pl: 472(10 ) = 0100 | 1101 | 0010 4 7+6 2 9 by rz4s™ Az AIKEN-kód kódszó készlete a 4bites bináris kód első és utolsó 5 kombinációját tartalmazza, a középső hat kombináció nem létezik. Előnyei: - az első helyérték alapján eldönthető, hogy a szám 5-nél kisebb vagy sem. Gray-kód: Az egymást követő számok egy biten térnek el egymástól Steibitz-kód: (N+3)Binárisan – helyértékek lévő számok összege 3-al több, mint a számjegy. Képek kódolása Alfanumerikus-kódok: ASCII kód (1963) 8bites, a 8. bit a paritás, amely a 7 hasznos karakteren szereplő 1-esek számát párosra egészíti ki. A maradék 7 bit szolgál az információ kódolására,

a 6 és 7 bit határozza meg, hogy a legkisebb 5 bit kisbetű, nagybetű, szám vagy írásjel-e. Így történik a kommunikáció a CPU –klaviatúra, -display között, soros átvitel A telex-kód: 5bites – külön kell gondoskodni a betűk és a többi jel kódolásáról Az 5 lyuk azt jelenti, hogy utána betűk következnek, a 4 lyuk egyéb jeleket jelent. EBCDIC: 8bites, IBM, lyukkártyákhoz Unicode: 16bit, több nyelvet is támogat, részekre van osztva Hibafelfedő és javító kódok Zajos csatorna esetén a küldött kódszó megváltozhat 1  0, ill. 01 csere léphet fel A gyakorlati valószínűsége általában 1 helyen változik a kódszó. Egyetlen hiba paritásos ellenőrzéssel felfedhető. Alapelve: minden kódszóval +1 paritásbitet is átviszünk a csatornán, páros vagy páratlan 0/1 biteket tartalmazzon. Ez a járulékos helyérték a paritásbit Hamming-távolság: Hány bitet kell az egyik kódszóban megváltoztatni, hogy a másikat kapjuk meg. Pl.

0011 ill. 0010  Hamming-távolság: 1 Hibafelfedés feltétele, hogy D ≥ 2 legyen, D=1 esetén bármelyik kódszót eredményezheti. Maximálisan d-1 hiba fedhető fel. m információs bithez k ellenőrző érték kell: 2 k ≥ m + k − 1 A hiba javításához a helyét is ismerni kell. Tételezzük fel, hogy 1 bithiba van. d = 1  nem fedhető fel mindig 10 by rz4s™ d = 2  mindig felfedhető, nem biztos, hogy paritható ( d=1 sugarú gömbben 2 elem is lehet ) d = 3  egységsugarú gömbjében csak egy elem lehet, ami lehetővé teszi a hibafelfedést, javítást ED paritás ellenőrzés: 1 bithiba felfedezésére alkalmas, ha az 1esek száma páratlan  1, ha az 1esek száma páros  0 A paritásos kódok 1 bithiba felfedezésére alkalmasak d=2 esetén Gyakorlatban: - vesz egy kódszót az adó, majd átküldi a csatornán pl. 1001100|1 , a paritásbittel együtt - a vevő megnézi a 8 bitet, kiszámolja rá a paritást, ha egyezik nem sérült - ha

sérült nem tudja eldönteni hol a hiba, újraküldeti - a paritás ellenőrzése páratlan bithibák felfedésére alkalmas ( 1,3,5) Hamming-kód: Automatikus hibajavítást tesz lehetővé 1 bithiba esetén 1. oszlop: 3-5-7 oszlopokra paritásellenőrzés 2. oszlop: 2-3-6-7 - || 4. oszlop: 4-5-6-7 oszlopokra páros paritásellenőrzés 0 1 2 3 4 0 0 1 0 1 1 1 BCD kód 0 8 0 4 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 1 2 3 4 5 Oszlop 2 0 0 1 1 0 6 1 0 1 0 1 0 7 ? pl. átjön ez: 1101101 nincs ilyen a kódtáblában, melyik bit rossz ? Számoljuk ki a megfelelő oszlopokra a paritást 1:1 3:0  1 ⋅ 20 + 0 ⋅ 21 + 1 ⋅ 22 = 5 ( 5. a hibás bit ) 5:1 Számábrázolás digitális számítógépeken - rögzített bitméret mellett beszélünk számábrázolásról, jelenleg max. 64bit a szóhossz ( 8-16-32-64 ) eldönthetjük, hogy mekkora legyen a bitméret, és hogy előjeles szám-e 11 by rz4s™ Egész számok ábrázolása: - egész számok egyenlő távolságban

helyezkednek el egymástól - a pozitív szám ábrázolása közvetlen bináris kódban történik 8bit nem negatív 0-255 byte 16bit, nemnegatív 0-65535 word 32bit, nemnegatív 0 − 232 − 1 longint 8bit előjeles -128127 16bit, előjeles -3276832767 integer 32bit, előjeles − 231 − 231 − 1 longint ábrázolás 8 biten: 1 bit előjel 0/1, további 27 lehetőség Műveletek: Egyes komplemens ( negáció ): pl: 00011111 11100000 Kettes komplemens ( negált +1 )pl: 00011111 11100000 + 1 11100001 Összeadás: Előjelesen: pozitív 0, negatív 1 Kivonás: kettes komplemens 31 0|0011111  -47 1|0101111  pozitív számot nem kell visszaalakítani + Bináris szorzás: 1010 * 1100 1010 0000 0000 1111000 = 120 Algoritmus: AR – szorzó BR – szorzandó Eljárás szorzás ( A * B ) AR := A 12 0|0011111 1|1010001 1|1110000 1|0001111 1 1|0010000 = -16 by rz4s™ BR := 2 L * B // hogy hány 0-át írunk utána Ciklus i:=1-től L-ig C := AR // mennyi a 0. bitje AR :=

AR/2 Ha C = 1 akkor AR := AR+BR Ciklus vége AR := AR/2 Eljrás vége Magyarázat: AR 0000|1010  itt, a második szakaszban jelenik meg az eredmény BR 1100|0000 AR 0.bitje: C = 0 1. lépés: AR 2. lépés: C=1, AR 3. lépés C=0, 4. lépés C=1, Egyel jobbra eltolva 00000101 00000010 11000000 11000010 AR: 01100001 00110000 11000000 11110000 01111000 Algoritmus ( osztás ) - egész osztás történik, keletkezik egy maradék - sorozatos kivonás + eltolás AR BR maradék|hányados osztó|osztandó? Eljárás osztás ( A/B ) AR := A BR := 2 L * B Ha AR > BR akkor hiba Különben 13 by rz4s™ Ciklus i:=1-től L-ig AR:=AR*2 // balra léptetés Ha AR > BR akkor AR := AR-BR AR := AR+1 // AR 0.bitjét egyesre állítjuk Ciklus vége Elágazás vége Eljárás vége Pl. AR 01010|1101 BR 01011|0000 1. lépés balra eltolás  101011010 2. ha kivonható kivonjuk, utolsó bitet 1-esre állítjuk Valós számok ábrázolása: Általában csak közelítő értéket tudunk

ábrázolni Fixpontos ábrázolás: - hány bitet szánunk az ábrázolásra - hova kerüljön a kettedespont: a, végére ( egész számok ) b, közepére ( tört ) c, elejére ( 1-nél kisebb szám ) Tört: Ha a kettedespontot balra visszük, pontosabb lesz az ábrázolás, de a tartomány kisebb lesz. A számok ugyanolyan távolságra vannak egymástól Normál alak: nagy számoknál, nem olyan fontos a pontosság Lebegőpontos ábrázolás: mantissza ⋅10 karakterisztika | előjel|törtrész|előjel|kitevő Real típus: 80 bit A legkisebb szám amit ábrázolni tudunk: normál alakban a kettedes ponttól jobbra az első bitnek 1-nek kell lennie: 0.1 ⋅ 2 −127 Két szám közötti távolság nem állandó CRC ( Cyalic Redundance Check ) A hiba felfedése a cél. Módja : - az üzenethez hozzáfűzünk egy ellenőrző összeget ( hitelesítést ), alapja a polinom aritmetika ( polinom osztás - mod2-ben való műveletvégzés ( összeadás = kivonás ) 1+1=0 ( túlcsordulás

)  a XOR-ral megegyezik ( két igaz nincsen ) - A xor B * B = A ( titkosításhoz használják ) A CRC használata: zajos csatornán, csomagok hitelesítésére Müködése: 14 by rz4s™ Veszünk egy üzenetet vagy fájlt, legyen M(x). Ez egy bitminta, ezt akarjuk átküldeni El kell dönteni, hogy hányadfokú CRC polinomot használunk ( 8-12-16-32 ) Hozzáfűzünk az üzenethez annyi 0-t, amilyen a CRC ( 8db 0-át ) M(x) R G(x) 01011000010 | 00000000 : osztópolinom A maradék az osztás után max R-edfokú lesz. Elvégezzük a maradékos osztást, a maradékot pedig kivonjuk az eredeti polinomból . Így kapjuk T(x)-et. Ezt fogjuk elküldeni A vevő elosztja a T(x)-et G(x)-el Ha el tudja maradék nélkül osztani, akkor minden rendben, ha nem, akkor az üzenet sérült. Bithibák típusai amelyeket képes felfedni: - 1 bit - minden páros számú bithiba - csoporthibákat ( egymás után álló hibás tagok ) akkor fed fel, ha ezek max R/2 hosszúak, ennél hosszabbra nem

müködik Algoritmus: Eljárás calculate CRC ( Count, CRC, buffer ) B := 0 While count < > 0 do Begin Tmp1 := ( CRC Shr8 ) and 00FFFFFF p := p+1 tmp2 := CRCTABLE [ CRC xor buffer[p] and FF ] CRC := tmp1 xor tmp2 Count := count-1 End; Eljárás vége Müködése: A while ciklus végigmegy a bufferbeli elemeken, p=0-tól. Shr – Shift Right ( eltolás jobbra ) az utána megjelölt számmal Tmp1 – az első kettő 0 ( levágjuk ), a többi 1 ( változatlan ) CRCTABLE – 256 eleme van, letároljuk, kiválasztjuk [].elemét ezt összeéseljük, mert nem akarunk kicsordulni A CRC polinom érték nem jelenik meg A CRC a legjobb és legelterjedtebb hibafelfedő, előnye a gyorsaság A véletlen számok Könyv ahol kinyílik, lottó, rulett, dobókocka Mire használják? : - numerikus integrálás ( matematikai módszerek ) - titkosítás, játékprogramok, szimuláció, időjárás modellezés - atomenergia, tesztelő programok - rendezési algoritmusok továbbfejlesztése

Követelmények 15 by rz4s™  0 és 1 közé eső valós számok legyenek  az igazi véletlen számok nem jók  helyette egy pszeudóvéletlen számgenerátor kell Neumann-féle négyzetközép módszer: - vegyünk egy x-jegyű számot ( pl.7 ) - a közepét emeljük négyzetre : pl: 1352151  521*521 = 0271441  714714 Hibái: - nagyon függ a kiindulási számtól - könnyen ciklusba kerül, ismétlődni kezd Lineáris koncepciók módszere: Rn+1=(aRn+b) mod m // hogy ne legyenek túl nagyok a számok // ha integer kell : mod 65535 // eredménye a maradék - válasszunk egy Ro véletlen számot: - gép időzítője - a,b,m nem történeht véletlenszerűen, nehéz feladat - értékük nem változik pl: a = 32749, b = 3 m = 32749 vagy a = 10001, b = 3, m = 17417 Ál-véletlen számok generálása: A generált számok ellenőrzésének módszerei A) egyenletesség-próba: egyenletes eloszlást kell hogy mutassunk B) sorozat-próba : - kell valami ami kiszűri a nem

jó sorozatokat: pl. 0-99 tartományban 0-1,1-2 stb x 2 próba : milyen hasonlóság van két számsorozat között C) hézag-próba: - megadunk egy változtatható intervallumot – ez a hézag - vizsgáljuk, hogy a sorozat elemei ( sorban ) benne vannak-e a hézagban - mindig leírjuk , hogy D) póker-próba: - előállítjuk a tényleges lapokat egy kódolási rendszerrel véletlen sorozatként, vizsgáljuk az előfordulást, összehasonlítjuk egy valós sorozattal Algoritmus: Function RndNam ( mean, StandDev : real ) //mean : ami körül szór, StandD: görbe szélesség Var randomA, randomB, Radius2, Deviate : real; Begin Repeat randomA := 2*Random-1.0; randomB := 2*Random-1.0; Radius2 := sqr(randomA) + sqr(randomB); Until radius 2 < 1.0;  amíg benne van az egy sugarú körben 16 by rz4s™ Deviate := randomA*sqrt((-2ln(radius2)) / radius2); RndNam := mean + deviate*StandDev; End; Kiegészítés: Ha az adott p eloszlás entrópiája H, akkor s kódjelből mindig

készíthető olyan prefix kód, H hogy L átlagos kódhosszra L < + 1 teljesül. log S 17