TDK témák

Vé­let­le­ní­tett lo­ká­lis al­go­rit­mu­sok és füg­get­len­ség [fog­lalt]

Ve­gyünk egy grá­fot (há­ló­za­tot), ahol min­den csúcs­ra füg­get­len azo­nos el­osz­lás sze­rint va­ló­szí­nű­sé­gi vál­to­zó­kat sor­so­lunk. Ez­után min­den csúcs a kör­nye­ze­té­ben lá­tott vé­let­len cím­kék alap­ján egy (meg­fe­le­lő fel­té­te­le­ket tel­je­sí­tő) de­ter­mi­nisz­ti­kus függ­vény se­gít­sé­gé­vel egy új ér­té­ket kap. Ezt ne­vez­zük vé­let­le­ní­tett lo­ká­lis al­go­rit­mus­nak (vagy ál­ta­lá­no­sab­ban, fac­tor of i.i.d. fo­lya­mat­nak). A lét­re­jö­vő va­ló­szí­nű­sé­gi vál­to­zók ter­mé­sze­te­sen már nem füg­get­le­nek. Az ál­ta­lá­nos kér­dés, hogy tá­vol lévő csú­csok ese­té­ben mit le­het még­is ál­lí­ta­ni, mennyi­re kell az új va­ló­szí­nű­sé­gi vál­to­zók­nak füg­get­le­nek­hez ha­son­ló­an vi­sel­ked­ni­ük: nagy su­ga­rú göm­bö­ket te­kint­ve tel­je­sül-e pél­dá­ul nagy szá­mok tör­vé­nye, van­nak-e kon­cent­rá­ci­ós ered­mé­nyek vagy nagy­el­té­rés-té­tel jel­le­gű ál­lí­tá­sok. A kér­dé­sek egy má­sik irá­nya bi­zo­nyos sta­tisz­ti­kus fi­zi­kai mo­del­lek­re fac­tor of i.i.d. konst­ruk­ci­ó­kat adni, ez­zel kap­cso­lat­ban is sok nyi­tott kér­dés van. A fel­adat te­hát fac­tor of i.i.d. fo­lya­ma­tok­ra szük­sé­ges fel­té­te­lek meg­fo­gal­ma­zá­sa, il­let­ve konst­ruk­ci­ók meg­adá­sa, fő­ként a re­gu­lá­ris fán, az ed­dig is­mer­te­ken túl­me­nő­en.

Iro­da­lom:
Rus­sell Lyons, Fac­tor of iid on tre­es, to ap­pear in Com­bi­na­to­rics, Pro­ba­bi­lity and Com­pu­t­ing. ar­Xiv:1401.4197

El­mé­le­ti téma

Az al­geb­rai va­ló­szí­nű­ség­szá­mí­tás meg­ala­po­zá­sa Ru­zsa-Szé­kely [1] ne­vé­hez köt­he­tő. En­nek lé­nye­ge, hogy ál­ta­lá­nos, kom­mu­ta­tív fél­cso­por­tok­ra bi­zo­nyí­tot­tak olyan té­te­le­ket, ame­lyek­nek ér­de­kes va­ló­szí­nű­ség­szá­mí­tá­si kö­vet­kez­mé­nyei vol­tak a va­ló­szí­nű­ség­el­osz­lá­sok kon­vo­lú­ció-fél­cso­port­ja­i­ra, pél­dá­ul a prím­fak­to­ri­zá­ci­ó­hoz ha­son­ló fel­bon­tá­si té­tel el­osz­lá­sok­ra (és eset­leg egy ma­ra­dék­tag­ra).

Az­óta több te­rü­le­ten is al­kal­maz­ták az ered­mé­nye­i­ket, el­ső­sor­ban kü­lön­bö­ző struk­tú­rá­kon vizs­gál­ták eze­ket az arit­me­ti­kai tu­laj­don­sá­go­kat. A fel­adat ed­dig nem vizs­gált kon­vo­lú­ció-fél­cso­por­tok­ra vo­nat­ko­zó ered­mé­nyek ki­dol­go­zá­sa.

Hi­vat­ko­zás
[1] I Ru­zsa, GJ Szé­kely (1988): Al­geb­ra­ic pro­ba­bi­lity the­ory. John Wi­ley & Sons Inc

Al­kal­ma­zott téma

Meg­vizs­gál­ni a kü­lön­bö­ző in­téz­mé­nyek ál­tal al­kal­ma­zott ta­nul­má­nyi ösz­tön­díj-szá­mí­tá­si mód­sze­re­ket és össze­ha­son­lí­ta­ni őket az ELTE TTK-n hasz­nált el­já­rás­sal, ame­lyik a kur­zus vé­lel­me­zett ne­héz­sé­gét is fi­gye­lem­be ve­szi. A fő cél egy olyan al­ter­na­tí­va ki­dol­go­zá­sa len­ne, amely nem hát­rá­nyos azok­ra, akik jó cso­por­tok­ba jár­nak (in­ten­zív tárgy­vál­to­za­tok, ma­te­ma­ti­kus szak­irány). A vizs­gá­lat­hoz szi­mu­lá­ci­ós mód­sze­re­ket és eset­leg a teszt­el­mé­let meg­kö­ze­lí­tés­mód­ját cél­sze­rű al­kal­maz­ni.