Online-Algorithmen für Paging

In dieser Unterrichtseinheit vergleichen wir das Offline- mit dem Online-Paging-Problem. Während Instanzen des Offline-Problems eindeutige Lösungen haben, die mit der LFU-Strategie («longest future distance») leicht gefunden werden können, gibt es für das Online-Problem unterschiedliche Strategien, die jedoch unterschiedliche Erfolgsgarantien haben.

Wir untersuchen dabei die FIFO- («first in first out») und die LRU-Strategie («least recently used»). Um die Güte der Online-Strategien zu messen, führen wir das Konzept des kompetitiven Faktors ein. Beide der untersuchten Online-Strategien sind dabei strikt k-kompetitiv, wobei k die Grösse des Cache-Speichers bezeichnet.

Die Unterlagen richten sich an Klassen ab der Gymnasialstufe 9. Spezifisches Vorwissen aus dem Informatikunterricht ist für die Behandlung dieser Unterrichtseinheit im Prinzip nicht nötig. Der Schwierigkeitsgrad der Unterrichtseinheit ist jedoch abhängig davon, wie viel Erfahrung die Klasse damit hat, Tabellen für die Darstellung von Strategien (d. h. deren zeitlichen Verlauf) zu nutzen. Wir setzen darüber hinaus voraus, dass die Klasse damit umgehen kann, Elemente einer Menge (in unserem Fall unterschiedliche Buchtitel) durch allgemeine Symbole mit Indizes (in unserem Fall b1, b2, b3 usw.) darzustellen. Zuletzt nutzen wir aus der Mathematik das Vorwissen über Parameter, um der Grösse des Cache-Speichers durch einen Buchstaben einen festen, aber allgemeinen Wert zuzuweisen.