témavezető: Herendi Tamás
helyszín (magyar oldal): Debreceni Egyetem Informatikai Kar helyszín rövidítés: DE IK
A kutatási téma leírása:
Álvéletlenszámsorozatok előállítására gyakran használnak véges struktúrákon definiált lineáris rekurzív sorozatokat. Az [1]-ben elért fő eredmény szerint minden lineáris rekurzív sorozathoz megadható egy csak a rekurzió fokszámától függő s egész amelyikre egy tetszőleges p prímre a sorozat egyenletes eloszlású moduló pt minden t egész esetén akkor és csak akkor, ha egyenletes eloszlású moduló ps. Az eredményt speciális esetben, p=2 választással sikerült javítani. Ekkor s=2 -re igazolható az állítás. Erre alapozva megadható egy algoritmus, ami a sorozat egyenletességét teszteli néhány értékének vizsgálata alapján. Ezen értékek kiszámolása viszont meglehetősen számolásigényes feladat. Az egyik lehetséges megoldás során egy nagyméretű mátrixot kell igen magas kitevőre emelni. A számítás különlegessége, hogy a műveleteket egyszerű struktúrában, moduló 4 fölött kell végezni, illetve az egyes alapműveletek egymástól függetlenül hajthatók végre. Természetes lehetőségként merül fel a feladat végrehajtására FPGA alapú eszközök használata. A témát vállaló doktorandusznak gyors és hatékony párhuzamos algoritmusok kidolgozása és FPGA-ra való implementálása a feladata. Ennek megvalósításához rendelkezésre áll egy 16 FPGA modullal ellátott Ryviera szerver.
Irodalom:
[1] T. Herendi: Uniform distribution of linear recurrences modulo prime powers J. Finite Fields And Applications 10 (2004), 1-23
[2] R. Lidl, H. Niederreiter: Finite Fields, Cambridge University Press, 1997.
[3] O. Strauch, S. Porubský: Distribution of Sequences: A Sampler, Frankfurt am Main, Berlin, Bern, Bruxelles, New York, Oxford, Wien, 2005. XXII, 543 pp. ISBN 978-3-631-54013-8 pb.
[4] M. Drmota, R.F. Tichy: Sequences, Discrepancies and Applications, Springer Berlin Heidelberg, Lecture Notes in Mathematics (1651), 1997
ajánlott nyelvtudás (magyar oldal): angol felvehető hallgatók száma: 1