Újabb cikk

Újabb cikkünket fogadták el (Iván Szabolccsal közöset: On nonpermutational transformation semigroups with an application to syntactic complexity), a megjelenésre egyelőre még várunk (valószínűleg hónapokat, remélhetőleg nem éveket...) Ez kicsit más témájú. A tudományterületeket megpróbálják körülhatárolni, de a kutatások sokszor átlépnek határokat, ún. interdiszciplináris témává válnak. Az algoritmusok témakörét sem lehet élesen elválasztani más területektől: szoros kapcsolatban van az automaták elméletével, az algebrával, a bonyolultságelmélettel, a kombinatorikával, a geometriával... Minél több területtel van kapcsolata, annál gazdagabb az eszköztára egy témának. Persze már volt róla szó, hogy előre sosem tudhatjuk, hogy egy eszköz hasznos lesz-e számunkra. Az online algoritmusokat természetesen az algoritmuselmélet részterületének tekinthetjük, de nagyon szoros kapcsolatban van a kombinatorikával, és a bonyolultságelmélettel (complexity theory). Ezért óvatosan, de érdemes néha más területekre evezni.

Globposzt

Ezen a vidám április elejei napon egy érdekes alkalmazásról írok. A Globulation nevű real-time (valós idejű) stratégiai alkalmazás valóságközelibb, mint a turn-based alkalmazások. Van offline, valamint  hálózatban futó változata. Több algoritmus van mögötte, különböző módokon próbálnak optimalizálni. Kétféle egység kaphat utasításokat, amelyeket az alkalmazás automatikusan oszt ki az egyes egységeknek, az egyik a worker, a másik a warrior, nevük is jelzi funkcióbeli különbségüket. Amennyiben az adott egység sérült vagy erőforráshiány lép fel, a feladatot visszautasíthatja. A cél  a presztízspontok mennyisége valamint az elfoglalt terület maximalizálása. A célfüggvény összetettsége miatt több optimális stratégia létezik, ez okozza a feladat nehézségét. A versenyképességi hányadosra éles korlát nem ismert a számítás komplexitása miatt, bár valójában kevesen foglalkoztak még a kérdéssel. Legtöbb esetben nem optimalizálni próbálnak, hanem egy adott célfüggvényértéket elérni, ennek elérése esetén nem növelik tovább a célfüggvényt, ilyen megközelítésben a versenyképességi hányadost számolni nincs értelme. Más célfüggvény vizsgálata merülhet fel ilyenkor, például az adott terület/pontérték eléréséhez szükséges idő, természetesen ennek a minimalizálása a cél. Sem éles versenyképességi korlátok, sem approximációs algoritmusok nem ismertek erre a kérdésre sem.

Megjelenik egy újabb cikk -- vééégre

A napokban kaptam értesítést arról, hogy megjelenik egy cikkünk. Hirtelen nem is tudtam, melyik cikkről szólnak. Aztán összeállt a kép. Ugyanis egy régen (még jóval a jelen projekt kezdete előtt fogadták el, és online nem sokkal a projekt kezdete előtt meg is jelent) elfogadott cikk papír változatáról szólt az értesítés. Volt már róla szó, hogy a matematikai témájú cikkek publikálási folyamata lassú, nem ritkán évekig eltarthat, elsősorban a bírálati folyamat nehézkessége miatt. Matematikában az eredmények helyességét ellenőrizni nehezebb, mint például egy pszichológiai témájú írás esetén. Itt azonban nem arról van szó: már elfogadott, online változatban megjelent cikk újságváltozatáról, évfolyammal, számmal, oldalszámmal. Rangosabb folyóiratoknál előfordul, hogy sok színvonalas írást küldenek be, egy számban korlátozott a benne megjelenő cikkek száma, így várólista alakul ki az elfogadott cikkekből, amelyek várják a sorukat, hogy bekerüljenek valamelyik számba. Ezért vezették be az online megjelentetést, hogy más kutatók addig is láthassák és hivatkozhassák (hiszen az impakt faktorba is csak a két éven belüli hivatkozások számítanak bele, a hivatkozás pedig az újság érdeke). Az online megjelenés is megjelenésnek számít, tehát nem változtatható, vagyis utólag nem íratható bele még támogatás szövege sem, hiába jelenik meg az újságváltozat egy adott projekt ideje alatt. Viszont az online megjelenés sok helyütt nem számít publikációnak, így kerül két szék között a földre egy kutató ilyen helyzetben, hiszen előfordulhat, hogy emiatt sehová sem tudja elszámolni a publikációját. Így jártam.

Visszatérve a hamarosan megjelenő cikkre: csak hogy nevet adjak a gyereknek, a

L. Epstein, Cs. Imreh, A. Levin, J. Nagy-György, Online File Caching with Rejection Penalties, ALGORITHMICA 71:279–306, 2015 

munkáról van szó. Ebben a publikációban a lapozási (paging) probléma kicsit más irányú általánosításáról van szó, mint a k-szerver probléma, de rokon vele valamilyen értelemben. A file caching problémában az input fájlokból álló kérések sorozata egy lassú memóriából. A fájlnak két attribútuma van, egy pozitív kinyerési költség és egy egész méret. Egy algoritmusnak egy k méretű cache-t kell fenntartani, úgy, hogy a cache-ben tárol fájlok teljes mérete sosem haladhatja meg k-t. Adott egy kérés egy fájlra, amely nincs jelen a cache-ben a kérés időpontjában, ekkor a fájlt a lassú memóriából a cache-be kell vinni, valószínűleg más fájlok elmozgatásával onnan. Ez a kért fájl kinyerési költségével jár. A lapozási problémán kívül (ahol minden költség és méret 1) a probléma jól ismert speciális esete a költség modell vagy más néven a súlyozott (weighted) lapozás, ahol minden méret 1, a hiba (fault) modell, ahol minden költség 1, és a bit modell, ahol minden fájl mérete és kinyerési költsége megegyezik. Ha figyelmen kívül hagyás (bypassing) megengedett, akkor a fájl hiány még mindig a fájl elérését eredményezi a lassú memóriából, de annak későbbi cache-be beszúrása optimális. Mi a fenti problémák online elutasításos változatát vizsgáltuk, amelyben minden egyes kéréshez büntetés is tartozik. Ekkor ha a cache-ben jelen nem lévő fájl kérését elutasítja az algoritmus, akkor a költségéhez a kérés büntetése járul hozzá. A célfüggvény az elutasított kérések büntetésének és az elfogadott kérések kinyerési költségének összege. Ez a probléma mind a caching, mind a caching with bypassing probléma általánosítása. Determinisztikus és véletlen algoritmusokat is kidolgoztunk. A véletlen algoritmus versenyképességi hányadosa O(log k), és ez konstans faktortól eltekintve optimális. A determinisztikus esetben ismert  k-versenyképes algoritmus a cachingre és (k+1)-versenyképes algoritmus a caching with bypassig problémára.Továbbá ezek a legjobb ismert versenyképességi hányadosok. Ezzel ellentétben megmutattunk egy 2k+1-es alsó korlátot az elutasításos változat determinisztikus algoritmusainak versenyképességi hányadosára, amely még a lapozásra is érvényes. Kidolgoztunk egy (2k+2)-versenyképes algoritmust az elutasításos caching problémára, valamint egy (2k+1)-versenyképes algoritmust, amely alkalmazható az elutasításos lapozásra, valamint a caching hiba és bit modelljeiben.

Tudományos diákmunka

Elkezdődött a második szemeszter, újabb mérföldkő a hallgatók életében. A diplomamunka készítés újabb fázisa kezdődik. A hallgató, aki az online elutasításos ütemezés kutatásába bekapcsolódott, úgy döntött, hogy ezt a félévet halasztja. Ez nem jelenti a munka szüneteltetését (kutatási munka esetén ez nem is lenne szerencsés), így nyer is egy fél évet, nem kell kapkodni. Másrészt a TDK (Tudományok Diákköri Konferencia) szempontjából sem mindegy, egy hallgató melyik félévben aktív. TDK-n hallgatók mutatják be eredményeiket, amelyeket témavezetőik irányításával értek el. Kér fordulója van, a helyi, és az onnan továbbjutók számára az országos. Mindkettőn három helyezést, valamint különdíjat kaphatnak a legjobbnak ítélt munkák. Egy OTDK első helyezés nyílt utat biztosít a PhD képzésre, természetesen az adott területen. Mint írtam, OTDK (országos TDK) kétévente van, mindig tavaszi félévben. Abban a tanévben, amikor OTDK van, a helyi TDK-t őszi félévben rendezik meg, egyébként a tavasziban. Ezért számít, hogy egy hallgató mikor kezdi a munkát, és utána mely félévekben, meddig aktív a hallgatói státusza. Nem szerencsés tanulmányok végén kezdeni a tudományos munkát, aki utolsó évben kap észbe, szinte biztosan lecsúszik az OTDK-ról, hiszen az eredmények eléréséhez is idő szükséges. Ez mind a hallgató, mind az oktató felelőssége, hiszen az oktatónak kell felfedeznie a jó hallgatókat, a hallgatóknak pedig előrelátóan időben át kell gondolniuk, mit terveznek a jövőjükkel. Hiszen hiába fedezi fel az oktató a jó hallgatót, aki az iparban szeretne elhelyezkedni, ott nem sok plusz értéke van a PhD fokozatnak.
A hallgatóm a fentiek alapján nem jókor kezdett a kutatáson gondolkodni (nekem pedig nem volt esélyem felfedezni őt, mivel a kutatásommal kapcsolatos tárgyat nem tanítottam neki), ezért a mostani OTDK-ról lecsúszott. Eredeti tervei szerint ebben a szemeszterben szeretett volna végezni, de valamilyen okból félévet halasztott, ami járulékos nyereségként új lehetőséget nyitott a TDK-ra. Már "csak" eredmény kell, ami néha akadozva, néha lendületesebben, de alakul. Persze le is kell írni, ez -- főleg elsőre -- nem egyszerű feladat. Hajrá!

Új év, új lendület

Decemberben végül elfogadták a hányatott sorsú cikkünket, így újabb feladatokra koncentrálhattunk. Persze szigorúan csak ünnepek után, hiszen addig kényszerpihenőn voltunk (kötelező szabadság) :)

Több lehetőség adódik. Egyrészt belevágunk a színezés advice complexity vizsgálatába, folytatjuk a megkezdett ütemezős témát, illetve új vizekre is evezhetünk: felmerült automataelméleti téma is, gráfpakolás, illetve a korábban vizsgált gráf-láda pakolás is. Ez utóbbi lényegében már kész, az év végén sokat dolgoztunk rajta, de az utolsó simítások is sok munkát tudnak generálni. Időközben kiderülhet, hogy egy-két dolog nem teljesen korrekt a kéziratban, új ötletek merülhetnek fel, amit még bele szeretnénk írni, illetve az utolsó "Conclusion, further questions" fejezet, és a bevezető is (mindkettőt utolsó lépésként szokás megírni) is okozhat még némi fejtörést. Illetve sok szerző esetén a munka összehangolása is nehezítheti a folyamatot. Természetesen miután a rám eső résszel végeztem, a többi dologra koncentráltam: foglalkoztam az ütemezéssel, elővettem a gráfpakolásos kérdést, amivel szintén már korábban kezdtünk foglalkozni egy munkatársammal, de nagyon szeretnék végre már ezt a megkezdett munkát is befejezni, és az advice complexity kérdésével foglalkozni, ami már izgatja egy ideje a fantáziám. Természetesen lehet párhuzamosan is dolgozni több témán, szoktam is, de azt tapasztalom (nem csak magamon, másokon is), hogy kettőnél (na jó, szélsőséges esetben háromnál) többel egyszerre nem érdemes. Tehát mielőtt újba kezdenék, be szeretném fejezni, aminek a végén járunk. És úgy érzem, a gráfpakolásnak kezdünk a végére érni (a gráf-láda pakolásnak pedig már a végén vagyunk). De már többször csalt meg ez az érzés. Mindenesetre ha nem is újévi fogadalom, de a lendület megvan, hogy az új témát lehetőleg még idén kivesézzem. Alig várom :)

Kellemes ünnepeket!

x = (y + 10) sin (0.2y)

x = (y + 10) sin y

x = – (y+10) sin (0.22y)

Gráf-láda pakolás

Úgy tűnik, kicsit parkoltatjuk még az advice complexity témát. Leporoltunk egy régi, félig befejezett anyagot, hogy tovább dolgozzunk rajta. Ilyen gyakran előfordul: az ember dolgozik valamin, aztán jön valami sürgősebb, vagy egyszerűen nem akaródzik összejönni egy cikkre való, és félreteszi, hátha később előszedve friss szemmel sikerül összehozni. Korábban írtunk egy témaindító cikket a gráf-láda pakolásról Bujtás Csillával, Dósa Györggyel, Imreh Csanáddal és Tuza Zsolttal. Új fogalmat, sőt, új témakört vezettünk be, ami viszont általánosítása sok ismert problémának: ládapakolás (konfliktusokkal és anélkül), gráfpakolás, gráfhomomorfizmus és -izomorfizmus, különböző gráfszínezések, távolság címkézés, csatorna hozzárendelés, partíció, stb.

Az összejött anyagból nem minden került bele a végső cikkbe, a kimaradt anyag pedig nem volt egy teljes cikkre való, és nem is volt egységes. Eljött az ideje, hogy gatyába rázzuk, mivel nem érdemes tovább várni vele, hisze, elfelejtődik, vagy megcsinálja más (a legelső eredmények némelyike nem túl bonyolult), és a kimaradt részek témája is aktuális: online problémák egy formája, valamint egy erősebb modell. Mielőtt az elutasításos változatot definiáljuk, természetesen meg kell vizsgálni az elutasítás nélküli változatot, hogy lássuk, van-e relevanciája egyáltalán az előzőnek. Az erősebb modellben, az ún. jópakolási feladattal kapcsolatban egészen jó eredmények jöttek ki (több gráfosztályra elegendő feltételek, valamint kicsit általánosabban hasonló szerkezetű szükséges valamint elégséges feltételek, amik rögtön fel is vetették a karakterizálhatóság és a bonyolultság kérdését), az online problémának abban a változatában pedig, amelyben az input összefüggő módon kell érkezzen. Ebben a modellben eleve kérdés az online pakolhatóság, ezzel kapcsolatban  az eredeti problémával és a jólpakolás feladattal összehasonlító eredmények jöttek ki, amelyek segítenek elhelyezni a kérdést. És persze egy-két egyszerű állítás különböző feltételekre vonatkozóan, valamint annál több nyitott kérdés. Továbbá az optimalizásálási kérdésekkel kapcsolatban is sikerült megfogalmazni néhány állítást, és persze sok kérdést. A nyitott kérdések, és megfelelő megfogalmazásuk rendkívül fontosak, hiszen ezek tartják mozgásban a kutatást: ha minden érdekes nyitott problémát megoldunk egy adott területen, legfeljebb a nagyon nehezeket nem, akkor annak kutatása előbb-utóbb elhal. Még kerekítjük-gombolyítjuk, hogy csinos cikk váljon belőle, és beküldjük valahová, hátha valóban beindul a téma szélesebb körű vizsgálata. Hajrá, itt sok lehetőség van bizonyítani!