Online-Algorithmen für Paging

In dieser Unterrichtseinheit vergleichen wir das Offline- mit dem Online-Paging-Problem. Während das Offline-Problem eine eindeutige Lösung hat, die mit der LFU-Strategie («longest future distance») leicht gefunden werden kann, gibt es für das Online-Problem unterschiedliche Strategien, die jedoch keine Erfolgsgarantie 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 kkompetitiv, wobei k die Grösse des Cache-Speichers bezeichnet. Die Unterlagen richten sich an Klassen ab der Gymnasialstufe 9. Spezifisches Vorwissen aus dem Informatik-Unterricht ist im Prinzip für die Behandlung dieser Unterrichtseinheit 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.