Algorithmen und Programmieren 3 WS 2003/2004, Endklausur Donnerstag, 19. Februar 2004

Anleitung: Streichen Sie eine Aufgabe deutlich auf dem Angabeblatt. Diese Aufgabe wird nicht in die Bewertung einbezogen. Alle Antworten sind zu begründen! Jede Aufgabe hat 10 Punkte. Bearbeitungszeit: 90 Minuten

1. Die folgende Java-Klasse implementiert (teilweise) die Mengenoperationen für Mengen, die Teilmengen von {1, 2, …, 100} sind.

     class Menge100
     {  boolean [ ] a = new boolean[100];
        int größe = 0;
        public void enfügen(int x)
        {  if(a[x-1]==false) { a[x-1]=true; größe++; }
        }
        public boolean istleer() { return größe==0; }
        ...
     }

Geben Sie die Abstraktionsfunktion und die Darstellungsinvariante an, und beweisen Sie, dass die Operationen einfügen und istleer (mit geeigneten Vorbedingungen, falls nötig) korrekt implementiert sind.

2. Eine Zeichenkette p_{1}p_{2} … p_{m} heißt periodisch mit Periode k, (1 ≤ k ≤ m) wenn p_{i} = p_{i+k} für 1 ≤ i < i + k ≤ m ist, mit anderen Worten, wenn

p_{1} … p_{m−k} = p_{k+1} … p_{m}

ist. (Für k = m ist die Folge unperiodisch.)

(a) (3 Punkte) Bestimmen Sie die Periode und berechnen sie die Verschiebefunktion h für das Muster ababcababcabab. Verwenden Sie die Definition der Verschiebefunktion aus der Vorlesung.^{1} Berechnen Sie auch den Wert h(m + 1).

(b) (0 Punkte) Berechnen sie die Verschiebefunktion für abcabcabcab.

(c) (7 Punkte) Wie kann man mit Hilfe der Verschiebefunktion die (kleinste) Periode k einer Zeichenkette bestimmen?

3. Konstruieren Sie mit dem Huffman-Algorithmus einen optimalen Kode für die Verteilung (p_{1}, …, p_{6}) = (\frac{8}{25}, \frac{2}{25}, \frac{1}{25}, \frac{5}{25}, \frac{5}{25}, \frac{4}{25}). Zeigen Sie in einzelnen Schritten, wie der Algorithmus abläuft, und zeichnen Sie den optimalen Kode-Baum. Ist der optimale Kode eindeutig?

4. Leiten Sie aus der algebraischen Spezifikation für Mengen

istenthalten(x, leer) = falsch  (1)
istenthalten(x, einfüge(x, M)) = wahr  (2)
istenthalten(x, einfüge(y, M)) = istenthalten(x, M), für x ≠ y (3)
istenthalten(x, lösche(x, M)) = falsch  (4)
istenthalten(x, lösche(y, M)) = istenthalten(x, M),  für x ≠ y  (5)

folgende Identität her:

istenthalten(u, einfüge(x, lösche(u, M))) = istenthalten(u, einfüge(x, leer))

Geben Sie dabei in jedem Beweisschritt die Nummer der verwendeten Gleichung an.

1Die ursprüngliche Definition der Verschiebefunktion aus der Vorlesung lautet

h_{i} = max { k | 1 ≤ k < i, p_{1} … p_{k−1} = p_{i−k+1} … p_{i−1} } ∪ {0}, für i ≥ 1.

Die verbesserte Verschiebefunktion vom 12. Übungsblatt ist so definiert:

h_{i} = max { k | 1 ≤ k < i, p_{1} … p_{k−1} = p_{i−k+1} … p_{i−1} und p_{k} ≠ p_{i} } ∪ {0}, für i ≥ 1.