Online algoritmusok

Dósa György; Imreh Csanád: Online algoritmusok. (2011) [Jegyzet, tankönyv]

Előnézet

Szöveg 2011_Online algoritmusok_Dósa György_Imreh Csanád.pdf Licenc: Creative Commons Attribution Non-commercial No Derivatives. Letöltés (727kB) | Előnézet

Absztrakt, leírás

Jelen jegyzetet a Szegedi Tudományegyetem programtervező informatikus MSc képzés Online algoritmusok című törzstárgyának tematikája alapján készítettük. Ennek ellenére a jegyzet, illetve az egyes fejezetei jól használhatóak egyéb egyetemek tetszőleges algoritmusokkal foglalkozó kurzusain. A jegyzetünknek nem a témakör részletes áttekintése a célja, hanem a területen használt alapvető algoritmustervezési és elemzési technikák bemutatása az online algoritmusok elméletének különböző részterületein keresztül. A jegyzet első fejezetében a legfontosabb fogalmakat tisztázzuk, egy bevezető egyszerű példa, a síbérlés feladatának bemutatásán keresztül. A második fejezet a lapozási probléma alapvető eredményeit mutatja be. A harmadik fejezetben a dinamikus adatszerkezetek karbantartásának területéről mutatjuk be a lista karbantartás problémáját. A negyedik fejezet a véletlenített online algoritmusokra vonatkozó általános elméleti alapokat mutatja be, majd ezek felhasználására adunk példákat az ötödik fejezetben az első három fejezetben ismertetett problémák alapján. Az hatodik fejezetben a legismertebb online feladat, a k-szerver probléma alapvető eredményeit tekintjük át. A hetedik fejezetben az online ütemezés témakörét tárgyaljuk, bemutatjuk az immár klasszikusnak számító online ütemezési modelleket, és néhány új speciálisabb területről is áttekintést adunk. A nyolcadik fejezet témája a ládapakolás problémája és a sávpakolás, ami a ládapakolás egyik többdimenziós általánosítása. A kilencedik fejezetben három, a számítógépes hálózatokhoz kapcsolódó online problémát ismertetünk. A tizedik fejezet a gépi tanulás területének az online algoritmusokhoz kapcsolódó eredményeiből ismertet néhányat. Végül az utolsó, tizenegyedik fejezetben a jegyzetben használt versenyképességi elemzés lehetséges kiterjesztéseit, módosításait mutatjuk be. Ezúton szeretnénk köszönetet mondani Iványi Antalnak, az ELTE egyetemi tanárjának a kézirat alapos lektorálásáért és hasznos tanácsaiért.

Tétel nézet