{"id":520,"date":"2015-10-17T18:53:12","date_gmt":"2015-10-17T16:53:12","guid":{"rendered":"http:\/\/vmdok.org.rs\/vajgen\/?p=520"},"modified":"2015-10-17T18:58:49","modified_gmt":"2015-10-17T16:58:49","slug":"vatai-emil","status":"publish","type":"post","link":"http:\/\/vmdok.org.rs\/vajgen\/2015\/10\/vatai-emil\/","title":{"rendered":"VATAI EMIL"},"content":{"rendered":"

\"vatai\"<\/a>1983-ban sz\u00fcletett Zent\u00e1n, jelenleg az E\u00f6tv\u00f6s Lor\u00e1nd Tudom\u00e1nyegyetem Informatika Kara (ELTE IK) Komputeralgebra Tansz\u00e9k\u00e9n tan\u00e1rseg\u00e9d \u00e9s a zentai Bolyai Tehets\u00e9ggondoz\u00f3 Gimn\u00e1zium \u00e9s Koll\u00e9gium sz\u00e1m\u00edt\u00e1stechnika \u00e9s informatika szakos tan\u00e1ra. Diplom\u00e1j\u00e1t az ELTE IK-n szerezte 2007-ben programtervez\u0151 matematikus szakon. Itt folytatta tanulm\u00e1nyait az ELTE Doktori Iskol\u00e1ja Numerikus \u00e9s Szimbolikus Sz\u00e1m\u00edt\u00e1sok Programj\u00e1n J\u00e1rai Antal t\u00e9mavezet\u00e9s\u00e9vel sz\u00e1m\u00edt\u00f3g\u00e9pes sz\u00e1melm\u00e9let kutat\u00e1si t\u00e9m\u00e1ban. 2013-\u00f3ta doktorjel\u00f6lt. Anyanyelvi szinten besz\u00e9li a magyar \u00e9s szerb nyelvet, tov\u00e1bb\u00e1 angolb\u00f3l fels\u0151fok\u00fa \u00e9s n\u00e9metb\u0151l k\u00f6z\u00e9pszint\u0171 tud\u00e1ssal rendelkezik.<\/p>\n

Tudom\u00e1nyter\u00fclet:<\/strong> term\u00e9szettudom\u00e1nyok, matematika- \u00e9s sz\u00e1m\u00edt\u00e1studom\u00e1nyok
\nE-mail: emil.vatai@gmail.com<\/p>\n

A doktori \u00e9rtekez\u00e9s t\u00e9m\u00e1ja:<\/strong>
\nA sz\u00e1melm\u00e9let az eg\u00e9sz sz\u00e1mok tulajdons\u00e1gaival foglalkozik, \u00e9s k\u00e9t alapvet\u0151 k\u00e9rd\u00e9se van: egy adott sz\u00e1m pr\u00edm mivolta, illetve faktoriz\u00e1ci\u00f3ja. Egy eg\u00e9sz sz\u00e1mr\u00f3l akkor mondjuk, hogy pr\u00edm, ha nincsenek val\u00f3s oszt\u00f3i, azaz l\u00e9nyeg\u00e9ben csak eggyel \u00e9s \u00f6nmag\u00e1val oszthat\u00f3. Ezt \u00fagy is felfoghatjuk, hogy nem bonthat\u00f3 fel kisebb eg\u00e9sz sz\u00e1mok szorzat\u00e1ra, ez\u00e9rt szok\u00e1s felbonthatatlannak is nevezni a pr\u00edmsz\u00e1mokat. Ellenkez\u0151 esetben, amikor egy sz\u00e1m felbonthat\u00f3, akkor term\u00e9szetesen ad\u00f3dik az a k\u00e9rd\u00e9s, hogy mely sz\u00e1mok szorzat\u00e1ra bomlik fel, illetve mik a faktorai. P\u00e9ld\u00e1ul 5 pr\u00edmsz\u00e1m, m\u00edg 6 nem az, \u00e9s 6 faktorai 2 \u00e9s 3.
\nNyilv\u00e1nval\u00f3, hogy az a k\u00e9rd\u00e9s, hogy egy sz\u00e1m pr\u00edm-e, vagy mi a faktoriz\u00e1ci\u00f3ja, ann\u00e1l bonyolultabb \u00e9s ann\u00e1l tov\u00e1bb tart egy sz\u00e1m\u00edt\u00f3g\u00e9pes programmal megv\u00e1laszolni, min\u00e9l nagyobb a vizsg\u00e1lt sz\u00e1m. Naiv programokkal (algoritmusokkal), mint p\u00e9ld\u00e1ul a pr\u00f3baoszt\u00e1s (ahol megpr\u00f3b\u00e1lkozunk minden sz\u00e1mmal elosztani, hogy megvizsg\u00e1ljuk az adott sz\u00e1m oszthat\u00f3-e vele), nem jutunk nagyon el\u0151re, mivel nagyon gyorsan romlik az ilyen programok hat\u00e9konys\u00e1ga a vizsg\u00e1lt sz\u00e1m m\u00e9ret\u00e9nek f\u00fcggv\u00e9ny\u00e9ben.
\nEz\u00e9rt k\u00fcl\u00f6nb\u00f6z\u0151 (matematikai) algoritmusokat fejlesztettek ki, melyek nagys\u00e1grendekkel fokozz\u00e1k az ilyen algoritmusok gyorsas\u00e1g\u00e1t \u00e9s hat\u00e9konys\u00e1g\u00e1t. T\u00f6bb algoritmusnak fontos r\u00e9sz\u00e9t alkotj\u00e1k az \u00fagynevezett szit\u00e1k. K\u00f6z\u00e9piskol\u00e1ban vagy m\u00e9g kor\u00e1bban is be szokt\u00e1k mutatni a legismertebb (\u00e9s tal\u00e1n az egyik legegyszer\u0171bb) pr\u00edmkeres\u0151 szit\u00e1t, az Eratoszthen\u00e9sz-szit\u00e1t: a kettessel kezdj\u00fck, a kettes pr\u00edm, de a t\u00f6bbi p\u00e1ros sz\u00e1m nem lehet pr\u00edm, mivel kett\u0151vel oszthat\u00f3. Ezeket a sz\u00e1mokat megjel\u00f6lj\u00fck, azaz elimin\u00e1ljuk \u0151ket. A k\u00f6vetkez\u0151 megjel\u00f6letlen (elimin\u00e1latlan) sz\u00e1m a h\u00e1rmas, ami azt jelenti, hogy a h\u00e1rmas is pr\u00edm. De ism\u00e9t a h\u00e1romnak a t\u00f6bbsz\u00f6r\u00f6sei nem lehetnek pr\u00edmek, \u00e9s ezeket is elimin\u00e1lhatjuk. A k\u00f6vetkez\u0151 elimin\u00e1latlan sz\u00e1m az \u00f6t\u00f6s, ism\u00e9t pr\u00edm, \u00e9s \u00edgy folytatjuk (egy alkalmas fels\u0151 korl\u00e1tig). Hasonl\u00f3 szit\u00e1l\u00e1st alkalmaznak m\u00e1s sz\u00e1melm\u00e9leti algoritmusok, mint p\u00e9ld\u00e1ul a leggyorsabb faktoriz\u00e1ci\u00f3s algoritmusok: a n\u00e9gyzetes \u00e9s az \u00e1ltal\u00e1nos sz\u00e1mtestszit\u00e1k.
\nSajnos, matematikailag kidolgozni az algoritmusokat nem el\u00e9g, ugyanis amikor implement\u00e1lj\u00e1k \u0151ket sz\u00e1m\u00edt\u00f3g\u00e9peken a hardver \u00fajabb akad\u00e1lyokat emel. Az egyik ilyen akad\u00e1ly az \u00fagynevezett mem\u00f3riafal, amelybe az\u00e9rt \u00fctk\u00f6z\u00fcnk, mivel a CPU-k (a sz\u00e1m\u00edt\u00f3g\u00e9pek k\u00f6zponti egys\u00e9gei) \u00f3rajel\u00e9nek (sebess\u00e9g\u00e9nek) n\u00f6vel\u00e9se sokkal nagyobb temp\u00f3val fejl\u0151d\u00f6tt mint a sz\u00e1m\u00edt\u00f3g\u00e9pek t\u00f6bbi alkatr\u00e9sz\u00e9\u00e9, t\u00f6bbek k\u00f6z\u00f6tt a f\u0151t\u00e1r\u00e9, azaz a RAM mem\u00f3ri\u00e1\u00e9. Mivel a f\u0151t\u00e1r is n\u00e9lk\u00fcl\u00f6zhetetlen a programok futtat\u00e1s\u00e1hoz, ez\u00e9rt nem ritk\u00e1n fordul el\u0151 az, hogy a fut\u00f3 program nem az\u00e9rt vesz sok id\u0151t ig\u00e9nybe, mert a CPU nem sz\u00e1molja ki az adatokat el\u00e9g gyorsan, hanem mivel a mem\u00f3ria nem tudja \u0151ket el\u00e9g gyorsan el\u00e9rhet\u0151v\u00e9 tenni.
\nA doktori \u00e9rtekez\u00e9sem, melynek c\u00edme Sieving in primality testing and factorization, azaz Szit\u00e1l\u00e1s a pr\u00edmtesztel\u00e9sben \u00e9s faktoriz\u00e1ci\u00f3ban, az ilyen algoritmusoknak a hat\u00e9kony sz\u00e1m\u00edt\u00f3g\u00e9pes implement\u00e1ci\u00f3j\u00e1t vizsg\u00e1lja, \u00e9s megold\u00e1st javasol a mem\u00f3riafal kiker\u00fcl\u00e9s\u00e9re, a mem\u00f3riahierarchia jobb kihaszn\u00e1lts\u00e1g\u00e1val. A fent eml\u00edtett probl\u00e9m\u00e1ra m\u00e1r a hardverk\u00e9sz\u00edt\u0151k is felfigyeltek, \u00e9s a sz\u00e1m\u00edt\u00f3g\u00e9pet ell\u00e1tt\u00e1k seg\u00e9d gyors\u00edt\u00f3 t\u00e1rakkal, \u00fagynevezett cache mem\u00f3ri\u00e1kkal, melyek egy piramist, egy hierarchi\u00e1t alkotnak. A hierarchia cs\u00facs\u00e1n a processzor tal\u00e1lhat\u00f3 a regisztereivel, melyek a leggyorsabb, de a legkisebb t\u00e1rol\u00f3k. Alatta helyezkedik el az els\u0151 szint\u0171 L1 cache mem\u00f3ria, amely kicsit nagyobb, de egy kicsit lassabb is (de m\u00e9g mindig j\u00f3val gyorsabb a f\u0151t\u00e1rn\u00e1l), majd ut\u00e1na a m\u00e1sod szint\u0171 L2 cache, amely m\u00e9g nagyobb, de m\u00e9g lassabb is, \u00e9s v\u00e9g\u00fcl az alj\u00e1n a f\u0151t\u00e1r, amely a leglassabb.
\nA cache mem\u00f3ri\u00e1k seg\u00edts\u00e9g\u00e9vel, ha egy program s\u0171r\u0171n f\u00e9r hozz\u00e1 egy adathoz, akkor azok bem\u00e1sol\u00f3dnak a cache-be \u00e9s gyorsan hozz\u00e1f\u00e9rhet\u0151ek a processzor sz\u00e1m\u00e1ra, \u00e9s \u00edgy el lehet rejteni a mem\u00f3ria lass\u00fas\u00e1g\u00e1t. Viszont a szit\u00e1l\u00f3 algoritmusok (f\u0151leg ahol sok sz\u00e1mot szit\u00e1lunk nagy pr\u00edmekkel) nagyon nem illenek bele ebbe a modellbe, mivel az algoritmus olyan, hogy oda-vissza ugr\u00e1l a mem\u00f3ri\u00e1ban, \u00e9s nagyon \u00fcgyesen kell \u00fctemezni \u00e9s t\u00e1rolni az adatokat, hogy mindig minden a megfelel\u0151 pillanatban a megfelel\u0151 (r\u00f6vid id\u0151 alatt el\u00e9rhet\u0151) helyen legyen. Ezt a COLS (Cache optimized linear sieve, azaz Cache optimiz\u00e1lt line\u00e1ris szita) nevet visel\u0151 algoritmus val\u00f3s\u00edtja meg. Tov\u00e1bbi optimaliz\u00e1ci\u00f3s lehet\u0151s\u00e9gek a szit\u00e1l\u00f3 programok p\u00e1rhuzamos\u00edt\u00e1sa \u00e9s t\u00f6bb g\u00e9pen val\u00f3 futtat\u00e1sa. Erre egy javaslat az \u00fagynevezett Inverz szita (Inverse sieve). Ezzel az elj\u00e1r\u00e1s elosztott m\u00f3don (azaz t\u00f6bb sz\u00e1m\u00edt\u00f3g\u00e9pen futva) elimin\u00e1lja a felesleges szit\u00e1l\u00e1sokat, \u00e9s csak a marad\u00e9k munk\u00e1t k\u00fcldi vissza, hogy t\u00e9nylegesen elv\u00e9gz\u0151dj\u00f6n (innen ered a neve is \u2013 nem a sz\u00e1mokat szit\u00e1lja, hanem a szit\u00e1t szit\u00e1lja valamilyen \u00e9rtelemben visszafel\u00e9, azaz inverz m\u00f3don).<\/p>\n

Jelent\u0151sebb publik\u00e1ci\u00f3k:<\/strong>
\nA. J\u00e1rai\u2013E. Vatai 2010: Cache Optimized Sieve. \u2013 8th Joint Conference on Math and Computer Science MaCS. Kom\u00e1rno. 249\u2013256. o.<\/p>\n

A. J\u00e1rai\u2013E. Vatai 2011: Cache Optimized Linear Sieve. \u2013 Acta Univ. Sapientiae. Inform. 3. \u00e9vf. 2. sz. 205\u2013223. o.<\/p>\n

G. Farkas\u2013E. Vatai 2013: Sieving for Large Cunningham Chains of Length 3 of the First Kind. \u2013 Annales Universitatis Scientiarum Budapestinensis de Rolando E\u00f6tv\u00f6s Nominatae Sectio Computatorica. 40. sz. 215\u2013222. o.<\/p>\n

E. Vatai 2013: Inverse Sieve. \u2013 Annales Universitatis Scientiarum Budapestinensis de Rolando E\u00f6tv\u00f6s Nominatae Sectio Computatorica. 41. 355\u2013360. o.<\/p>\n

Gondolataim a vajdas\u00e1gi magyar tudom\u00e1nyos \u00e9letr\u0151l \u00e9s tudom\u00e1nyos ut\u00e1np\u00f3tl\u00e1sr\u00f3l:<\/strong>
\nM\u00edg fiatalon nagyon \u00f6r\u00fcltem, hogy Vajdas\u00e1gban n\u0151ttem fel, \u00e9s nehezemre esett elmenni Magyarorsz\u00e1gra, ma m\u00e1r kicsit m\u00e1sk\u00e9pp l\u00e1tom a dolgokat. M\u00edg az itthoni mentalit\u00e1st tov\u00e1bbra is saj\u00e1tomnak tekintem, kezdem felfedezni (nemzetis\u00e9gt\u0151l f\u00fcggetlen\u00fcl) egy olyan oldal\u00e1t, ahol a nagy szavak \u00e9s er\u0151fitogtat\u00e1s \u00e9lveznek el\u0151nyt, nem pedig a munka, illetve az eredm\u00e9nyek. \u00dagy \u00e9rzem pozit\u00edv hat\u00e1ssal volt r\u00e1m, hogy ebben a k\u00f6rnyezetben n\u0151ttem fel, ugyanis azt tapasztaltam, hogy sokszor talpraesettebb voltam, mint hallgat\u00f3t\u00e1rsaim. Viszont ez a k\u00f6rnyezet, \u00edgy m\u00e1r kicsit feln\u0151ttebb fejjel nem annyira vonz\u00f3, ugyanis az alap k\u00f6z\u00e9leti hangulat Szerbi\u00e1ban nagyon megnehez\u00edti a munk\u00e1t. Sajnos kezdem meg\u00e9rteni, mit jelent az, hogy Szerbia le van maradva a nyugathoz k\u00e9pest, \u00e9s arra, hogy itt nem csak a gazdas\u00e1gi szempontr\u00f3l van sz\u00f3, azaz a p\u00e9nzhi\u00e1nyr\u00f3l, hanem az \u00e1tlagemberek felfog\u00e1s\u00e1r\u00f3l, \u00e9rt\u00e9krendj\u00e9r\u0151l \u00e9s elv\u00e1r\u00e1sair\u00f3l. Nagyon fontosnak tartom Vajdas\u00e1gban (\u00e9s orsz\u00e1gszerte is) a m\u00faltb\u00f3l megmaradt, diszfunkcion\u00e1lis \u00e9s elf\u00e1sult (ak\u00e1r jogi, ak\u00e1r h\u00e9tk\u00f6znapi) gyakorlatok \u00e9s gondolkod\u00e1si m\u00f3dok \u00fajra\u00e9p\u00edt\u00e9s\u00e9t, fel\u00faj\u00edt\u00e1s\u00e1t.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"

1983-ban sz\u00fcletett Zent\u00e1n, jelenleg az E\u00f6tv\u00f6s Lor\u00e1nd Tudom\u00e1nyegyetem Informatika Kara (ELTE IK) Komputeralgebra Tansz\u00e9k\u00e9n tan\u00e1rseg\u00e9d \u00e9s a zentai Bolyai Tehets\u00e9ggondoz\u00f3 Gimn\u00e1zium \u00e9s Koll\u00e9gium sz\u00e1m\u00edt\u00e1stechnika \u00e9s informatika szakos tan\u00e1ra. Diplom\u00e1j\u00e1t az ELTE IK-n szerezte 2007-ben programtervez\u0151 matematikus szakon. Itt folytatta tanulm\u00e1nyait az ELTE Doktori Iskol\u00e1ja Numerikus \u00e9s Szimbolikus Sz\u00e1m\u00edt\u00e1sok Programj\u00e1n J\u00e1rai \u2026<\/p>\n

Tov\u00e1bb…<\/i><\/a><\/p>\n","protected":false},"author":1,"featured_media":192,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":"","_links_to":"","_links_to_target":""},"categories":[44,38],"tags":[],"class_list":["post-520","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-matematika-es-szamitastudomanyok","category-termeszettudomanyok"],"_links":{"self":[{"href":"http:\/\/vmdok.org.rs\/vajgen\/wp-json\/wp\/v2\/posts\/520","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/vmdok.org.rs\/vajgen\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/vmdok.org.rs\/vajgen\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/vmdok.org.rs\/vajgen\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/vmdok.org.rs\/vajgen\/wp-json\/wp\/v2\/comments?post=520"}],"version-history":[{"count":2,"href":"http:\/\/vmdok.org.rs\/vajgen\/wp-json\/wp\/v2\/posts\/520\/revisions"}],"predecessor-version":[{"id":537,"href":"http:\/\/vmdok.org.rs\/vajgen\/wp-json\/wp\/v2\/posts\/520\/revisions\/537"}],"wp:featuredmedia":[{"embeddable":true,"href":"http:\/\/vmdok.org.rs\/vajgen\/wp-json\/wp\/v2\/media\/192"}],"wp:attachment":[{"href":"http:\/\/vmdok.org.rs\/vajgen\/wp-json\/wp\/v2\/media?parent=520"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/vmdok.org.rs\/vajgen\/wp-json\/wp\/v2\/categories?post=520"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/vmdok.org.rs\/vajgen\/wp-json\/wp\/v2\/tags?post=520"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}