Véletlen

Szerencsére az nem véletlen, hogy újra jelentkezett a hallgató, aki most kezdi a diplomamunkáját. A véletlenített online algorimusok témakörét szemelte ki, és szimpatizál a ládapakolással (bin-packing). Ez ígéretes, kellőképpen leszűkítette a témát, de bőven hagyott lehetőséget, hogy a dolgozat célja szándékai szerint alakulhasson. Mivel szorgalmas és időben vagyunk, nem szeretnék beleszólni. Véleményem szerint egy jó témavezető nem a saját elképzelését erőlteti a hallgatóra, hanem elmondja a lehetőségeket (a számára nem szimpatikusakat is), és hagyja, hogy a dolgozat készítője alakítsa. Közben fejlődik, képezi magát, hogy a lehető legtöbb segítséget meg tudja adni (bin-packing témakörben nem vagyok a legjártasabb, ideje még többet olvasnom róla :) ). A ládapakolás nagy témakör, és ha valaki nem jártas benne, könnyen elveszhet a sok irodalom között. A téma szűkítése segít, de ilyenkor nem szégyen, és hasznos, ha olyan kutatóhoz fordulunk tanácsért, aki ezzel foglalkozik.

Újabb diplomamunka

Elkezdődött a tanév, és nagy örömömre újabb MSc hallgató érdeklődött az online algoritmusok témaköre iránt. Mivel nem határozott témajavaslattal kopogott be, végigjárjuk a témakeresés és a cél megfogalmazásának útját. Hosszadalmas, de megéri. Először egy általános leírás (újra csak Dósa György és Imreh Csanád tananyaga) a kiindulópont, szűkítjük a témát, ahhoz keresünk célirányos irodalmat, közben megfogalmazzuk a dolgozat célját. Ezek a következők szoktak lenni (de egy szokatlan javaslatnak is örülnék):

• adott témában a lényegesebb eredményeket összefoglaló munka (survay)

•  egy konkrét (angol) nyelvű cikk fordítása és magyarázata, pl. a nem részletezett, pontatlan bizonyítások kirészletezésével, példákkal

•  speciálisabb téma esetén önálló munka, pl. egy matematikai eszköz önálló alkalmazása problémákra (akár már megoldott problémák új megoldása), vagy egy probléma általánosítása, esetleg épp speciális esetek vizsgálata (amiket nem részleteznek ki cikkekben, de nem feltétlen új eredmények)

• új, önálló eredmény, ebből TDK is születhet, de ha nem sikerül, pl. nem jön ki ismertnél jobb eredmény, diplomamunkának az még akkor is jó

• elméleti eredmények gyakorlati alkalmazása (ez általában akkor merül fel, ha céggel van kapcsolatban a dolgozat írója, és konkrét problémára keresnek megoldást, pl. egy gyárban a gépek beállítása bizonyos feladatokhoz, anyag szabása optimálisan, stb.), persze ilyet hipotetikusan is lehet vizsgálni, de nagyon meg kell magyarázni a motivációt

• oktatási célú tananyag készítése (nem survay, de ha a hallgató nem tanárszakos, a középiskolás szintnél tovább kell mutasson, szemléltetéssel, emellett tanításra alkalmas anyagnak kell lennie).

 Persze ez nem rögtön körvonalazódik, jó esetben is hónapok telhetnek el, mire kialakul egy konkrét elképzelés, miről és hogyan fog szólni a dolgozat.

Ú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 :)