E-Book Content
Írta: DÓSA GYÖRGY IMREH CSANÁD ONLINE ALGORITMUSOK Egyetemi tananyag 2011 COPYRIGHT: 2011–2016, Dósa György, Pannon Egyetem Műszaki Informatikai Kar Matematika Tanszék, Imreh Csanád, Szegedi Tudományegyetem Természettudományi és Informatikai Kar Számítógépes Algoritmusok és Mesterséges Intelligencia Tanszék LEKTORÁLTA: Dr. Iványi Antal, Eötvös Loránd Tudományegyetem Informatikai Kar Komputeralgebra Tanszék Creative Commons NonCommercial-NoDerivs 3.0 (CC BY-NC-ND 3.0) A szerző nevének feltüntetése mellett nem kereskedelmi céllal szabadon másolható, terjeszthető, megjelentethető és előadható, de nem módosítható. TÁMOGATÁS: Készült a TÁMOP-4.1.2-08/1/A-2009-0008 számú, „Tananyagfejlesztés mérnök informatikus, programtervező informatikus és gazdaságinformatikus képzésekhez” című projekt keretében. ISBN 978 963 279 508 9 KÉSZÜLT: a Typotex Kiadó gondozásában FELELŐS VEZETŐ: Votisky Zsuzsa AZ ELEKTRONIKUS KIADÁST ELŐKÉSZÍTETTE: Gerner József KULCSSZAVAK: algoritmusok, online-problémák, legrosszabb eset korlátok, versenyképességi elemzés, optimalizálási problémák, erőforrás allokáció ÖSSZEFOGLALÁS: A gyakorlati problémákban gyakran fordulnak elő olyan optimalizálási feladatok, ahol a bemenetet csak részenként ismerjük meg, és a döntéseinket a már megkapott információ alapján, a további adatok ismerete nélkül kell meghoznunk. Ilyen feladatok esetén online problémáról beszélünk. Az algoritmusokat egy legrosszabb eset korlát elemzéssel szokás vizsgálni, amelyet versenyképességi elemzésnek neveznek. Az online algoritmusok elméletének igen sok alkalmazása van a számítástudomány, a közgazdaságtan és az operációkutatás különböző területein. A jegyzetnek 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 (lapozás, lista karbantartás, k-szerver feladat, ütemezés, ládapakolás, számítógépes hálózatok online problémái, online tanulás) keresztül. Tartalomjegyzék 1. Alapfogalmak, bevezet˝o példák 1.1. Bevezetés . . . . . . . . . . . . 1.2. Fogalmak, definíciók . . . . . . 1.3. Síbérlési feladat . . . . . . . . . 1.4. A síbérlési feladat általánosítása . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 6 6 7 8 2. Lapozási (memóriakezelési) probléma 10 3. Lista hozzáférési probléma 12 4. Véletlenített online algoritmusok 15 4.1. Alapvet˝o definíciók . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.2. Játékelméleti alapfogalmak . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.3. A játékelméleti reprezentáció . . . . . . . . . . . . . . . . . . . . . . . . . . 17 5. Példák véletlenített online algoritmusokra 5.1. Síbérlési feladat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2. Lapozás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3. Lista hozzáférés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 18 19 21 6. A k-szerver probléma 23 7. Ütemezési feladatok 7.1. Online ütemezési modellek . . . 7.1.1. Lista modell . . . . . . 7.1.2. Id˝o modell . . . . . . . 7.2. A Lista modell . . . . . . . . . 7.2.1. Az Id˝o modell . . . . . 7.3. Visszautasításos modellek . . . 7.4. A gépköltséges ütemezési feladat 30 30 31 31 33 38 39 42 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .