A 30 pontos házi feladatként az alábbi 3 feladat valamelyike oldható meg, határidő december 15. A leírttaknak megfelelő megoldásokat elektronikus formában kell elküldeni a cimreh@inf.u-szeged.hu címre. 1. Háziúr algoritmus változatainak tesztelése. A feladat megvizsgálni, hogy a Háziúr algoritmus átlagos hatékonysága miként függ azon lapok kreditjének átállításától, amelyeket akkor kérünk ha bennt vannak a memóriában. 3 algoritmust kell megvizsgálni, a Háziúr(0) a kreditértéket nem változtatja, a Háziúr(1) a kreditértéket a lap letöltési költségére állítja, végül Háziúr(1/2) a lapot az aktuális kreditérték és a letöltési költség számtani közepére állítja be. A 3 algoritmust a következő véletlen teszteken kell megvizsgálni: - A: k=20, 40 lehetséges lap, minden lapra a költség egyenletes eloszlás alapján egész az [1,100] intervallumból, a méret egyenletes eloszlás alapján egész az [1,20] intervallumból. Az input 1000 egyenletes eloszlás alapján generált kérés a lapok közül. - B: k=20, 40 lehetséges lap, minden lapra a költség egyenletes eloszlás alapján egész az [1,100] intervallumból, a méret egyenletes eloszlás alapján egész az [1,10] intervallumból. Az input 1000 egyenletes eloszlás alapján generált kérés. -C: k=20, 10 lehetséges lap, minden lapra a költség egyenletes eloszlás alapján egész az [1,100] intervallumból, a méret egyenletes eloszlás alapján egész az [1,20] intervallumból. Az input 1000 egyenletes eloszlás alapján generált kérés. -D : k=20, 10 lehetséges lap, minden lapra a költség egyenletes eloszlás alapján egész az [1,100] intervallumból, a méret egyenletes eloszlás alapján egész az [1,10] intervallumból.m Az input 1000 egyenletes eloszlás alapján generált kérés. - E: k=20, 40 lehetséges lap, minden lapra a méret egyenletes eloszlás alapján egész az [1,20] intervallumból a költség pedig a méret négyszerese. Az input 1000 egyenletes eloszlás alapján generált kérés a lapok közül. Minden tesztosztályból 50 tesztet kell végrehajtani, és az algoritmusok átlagos költségét kell összehasonlítani az adott osztályra. Beadandó a forráskód és a tesztek dokumentációja, az eredmények táblázatos összefoglalása. 2. Az Ébreszt algoritmus ébresztőbeállítási paraméterének tesztelése. A feladat megvizsgálni, hogy az Ébreszt algoritmus átlagos hatékonysága miként függ az ébresztő átállításától. 3 algoritmust kell megvizsgálni, az Ébreszt_1, Ébreszt_{1/2} és ÉBRESZT_{3/4} algoritmusokat. A 3 algoritmust a következő véletlen teszteken kell megvizsgálni: - A: 5000 csomag az egymás követő csomagok közötti időkülönbség egyenletes eloszlás alapján van generálva a [0,1] időintervallumból. - B: 5000 csomag az egymás követő csomagok közötti időkülönbség egyenletes eloszlás alapján van generálva a [0,1/2] időintervallumból. - C: 5000 csomag az egymás követő csomagok közötti időkülönbség egyenletes eloszlás alapján van generálva a [0,1/4] időintervallumból. - D: 5000 csomag az egymás követő csomagok közötti időkülönbség (x+1)/10, ahol x 5 paraméterű Poisson eloszlás alapján van generálva. - E: 5000 csomag az egymás követő csomagok közötti időkülönbség (x+1)/20, ahol x 5 paraméterű Poisson eloszlás alapján van generálva. Minden tesztosztályból 50 tesztet kell végrehajtani, és az algoritmusok átlagos költségét kell összehasonlítani az adott osztályra. Beadandó a forráskód és a tesztek dokumentációja, az eredmények táblázatos összefoglalása. 3. A Meyerson féle algoritmus tesztelése egyenesen a kiszolgáló elhelyezési feladatra. A feladat implementálni a Meyerson féle algoritmust és az egyenesre vonatkozó dinaimus programozáson alauló optimális megoldó algoritmust. Majd tesztelni a Meyerson algoritmus átlagos hatékonyságát. A 2 algoritmust a következő véletlen teszteken kell megvizsgálni: - A: 150 kérés egyenletes eloszlás alapján a [0,10] intervallumból, a kiszolgáló elhelyezésének költsége 1. - B: 150 kérés egyenletes eloszlás alapján a [0,10] intervallumból, a kiszolgáló elhelyezésének költsége1/2. Minden tesztosztályból 50 tesztet kell végrehajtani, és a Meyerson/OPT költségét kell összehasonlítani az adott osztályra. Beadandó a forráskód és a tesztek dokumentációja, az eredmények táblázatos összefoglalása.