Einführung Algorithmen und Datenstrukturen

exemplarische Lösung der Aufgaben WS 02/03 von Markus Durzinsky. Zurück zur Algodat Hauptseite.

08. Übungsblatt

Aufgabe 36 - Chiffrierung durch Permutation

Die Permutation besteht hier aus dem Vertauschen von Elementen. Dabei steht an der Stelle i der neuen Zeichenkette, das Element der Stelle a[i]-1 der alten Zeichenkette. Also


  h += s.charAt(a[i] - 1);
Dabei ist h der neue String, der den chiffrierten Text enthält. Man muss sich noch Gedanken über die "Zerlegung" des Originaltextes in Abschnitte der Länge a.length machen. Dazu wird die Position gespeichert bei der der Abschnitt beginnt.


  String h = "";
  int pos = 0;
  while (pos <= s.length()) {
    for (int i = 0;  i < perm.length;  i++) {
      h += s.charAt(pos + perm[i] - 1);
    }
    pos += perm.length;
  }

Chiffre durch Permutation Bleibt nur das Problem des "Reststrings", das heisst: Was passiert, wenn die Länge der Permutation kein Teiler der Länge der Nachricht ist? Eine Möglichkeit ist die fehlenden Zeichen mit Leerstellen zu füllen. Dies macht das dechiffrieren einfacher, lässt aber auch Rückschlüsse auf die Länge des Schlüssels zu. Sogar die Position bestimmter Zeichen innerhalb der Permutation kann so herausgefunden werden. Die zweite (und in Bezug auf die Dechiffrierung auch sicherste) Variante ist, diese Zeichen einfach wegzulassen. Das Hinzufügen des neuen Zeichens muss man entsprechend anpassen:


      if (pos + perm[i] <= s.length()) {
        h += s.charAt(pos + perm[i] - 1);
      }

Sicherlich wird die Methode dann h zurückgeben.

Da die überschüssigen Zeichen entfernt wurden (siehe Abbildung), ergibt sich ein kleines Problem für die Dechiffrierung. Dazu müssen die Zeichen wieder an der richtigen Stelle eingefügt werden. Dies gehört aber zu einer anderen Aufgabe.

Zusatzaufgabe

  1. Bei der freiwilligen Zusatzaufgabe geht es um das Dechiffrieren von Nachrichten. Es muss also eine Methode entwickelt werden, die einen Permutationsschlüssel "umgekehrt" anwendet. Zum Testen ist dieser Code gegeben:

    eeiLbgt ru ereWnchiasathm,mnn hkca  ineMneekkhr ,ei m t sedGekhcne

    Die zum Verschlüsseln verwendete Permutation ist praktischerweise gleich mit angegeben wurden: (3,5,2,1,4).

    Wie das nun funktioniert, kann auf dieser Seite nachgelesen und ausprobiert werden.

  2. Der zweite Teil der Aufgabe ist komplizierter. Gemeinerweise wurde weder die Permutation, noch dessen Länge angegeben. Letztere wird sich aber in der Grössenordnung von 5 bis 6 befinden (weniger ist unsinnig, mehr ist gemein). Und dies ist der Code:

    eatvndeatvndndaihebneyrdenstrnetniadntdneedaeninttnseaauedmndnreedzgkneaeatns

    Wie man auch damit leicht zurecht kommt steht hier.

Aufgabe 37 - SimpleList

Vorweg ein paar Bemerkungen:

Als erstes muss die Klasse Node implementiert werden. In Java ist es möglich Klassen innerhalb von Klassen zu deklarieren.


  public class SimpleList {
    ...
    private class Node implements ListPosition {
       ...
    }
  }
Dadurch wird eine Datei namens "SimpleList$Node.class" erstellt. Es gibt zwei Vorteile bei dieser Verfahrensweise:
  1. Nur die Klasse SimpleList kann die Klasse Node benutzen (weil private).
  2. Jedes Node-Objekt gehört genau zu einem Objekt von SimpleList, weshalb es auch auf die Eigenschaften und Methoden von SimpleList zugreifen kann. Wie dies geschieht wird später erläutert.

Die folgende Implementierung von Node ist bereits aus der Vorlesung bekannt:


    private ListPosition next;
    private Object o;

    public Node(ListPosition n, Object e) {
      next = n;  o = e;
    }

    public Object element() throws InvalidListPositionException {
      if (isInvalid())
        throw new InvalidListPositionException("nicht in Liste");
      return o;
    }

    public ListPosition getNext() { return next; }

    public ListPosition getPrev() {
      throw new InvalidListPositionException("not implemented in SimpleList");
    }
Die Methode zum Ändern von next müss prüfen, ob das übergebene Objekt auch wirklich vom Typ Node ist (sonst ist es eine Position aus irgend einer anderen Implementierung einer Liste). Dies ist deshalb wichtig, weil einige Programmteile davon ausgehen, dass dies der Fall ist. Ausserdem soll kein Programmierer von ausserhalb mit den Node-Objekten herumspielen, ohne die Klasse SimpleList zu verwenden.

    public void setNext(ListPosition newNext) {
      if (newNext == null) next = null;
      else if (newNext instanceof Node) next = newNext;
      else throw new InvalidListPositionException("falscher Typ");
    }

    public void setPrev(ListPosition newPrev) {
      throw new InvalidListPositionException("not implemented in SimpleList");
    }

Es fehlt noch die Methode isInvalid(), die prüfen soll, ob das Objekt nicht schon aus der Liste entfernt wurde. Da die Objekte first und last nicht existieren, zeigt next eventuell auf null, dann muss aber das Element das letzte in der Liste sein.


    protected boolean isInvalid() {
      if (next == null && !SimpleList.this.isLast(this)) return true;
      return false;
    }
SimpleList.this verweist genau auf das Objekt von SimpleList, welches den Knoten erstellt hat (das funktioniert nur weil Node innerhalb von SimpleList deklariert wurde). Ein Knoten ist ungültig, wenn er keinen Nachfolger hat und nicht das letzte Element ist.

Nun zurück zur Liste. Die bereits verwendeten Methoden isFirst() und isLast() prüfen nur die Gleichheit des übergebenen Objektes mit den Referenzen first und last:


  public boolean isFirst(ListPosition n) {
    return n == first;
  }

  public boolean isLast(ListPosition n) {
    return n == last;
  }

Es folgen die in der Aufgabenstellung geforderten Methoden:

Wer den kompletten Code sehen will und sich für den Inhalt der Klassen InvalidListPositionException, ListException und das Interface ListPosition interessiert, wird hier fündig.

Aufgabe 38 - Landkarten

  1. worst case Gegeben sind n durchnummerierte Punkte einer Strasse. Diese Kurve soll so zerlegt werden, dass sie durch lineare Abschnitte approximiert wird. Die Grenzen dieser Abschnitte sind Punkte der Strasse. Der Anfangszustand besteht aus dem Anfangs- und Endpunkt der Strasse. Nun wird geprüft, ob es Punkte der Strasse gibt, die weiter als eine gewisse Toleranz von der Gerade entfernt sind. Ist dies der Fall wird der Punkt zur Approximation hinzugefügt (sie besteht dann aus drei Punkten bzw. zwei Geraden). Dieser Vorgang wird wiederholt.
  2. Aufwand Was ist denn hier der worst case? Dieser tritt ein, wenn alle Punkte der Strasse in die Approximation übernommen werden müssen. Die Zahlen in den Balken geben an, wie viele Abstände berechnet werden. Demnach steigt die Anzahl der Gesamttests quadratisch: O(n2).

Aufgabe 39 - Interface - Menge

  1. Bei einer Menge besteht im Wesentlichen die Möglichkeit zu testen ob ein Element darin enthalten ist oder nicht. Darauf basierend können einige Operationen definiert werden:

    • Vereinigung von Mengen: Elemente die in mindestens einer der beiden Mengen enthalten sind.
    • Differenz von Mengen: Elemente die in der ersten, aber nicht in der zweiten Menge sind.
    • Durchschnitt von Mengen: Elemente die in beiden Mengen enthalten sind.

    Ebenfalls sollte es möglich sein zu testen, ob die Menge leer ist. Angenommen die Menge ist abzählbar und endlich. Dann ist es sinnvoll die Elemente einzeln aufzulisten. Dazu ist das Interface java.util.Enumeration hilfreich (Dieses enthält die Methoden boolean hasMoreElements() und Object nextElement()).

    
      import java.util.Enumeration;
    
      public interface Menge {
    
        boolean contains(Object element);
        boolean contains(Menge set);
        boolean isEmpty();
        int size();
        Menge union(Menge set);
        Menge difference(Menge set);
        Menge mean(Menge set);
        Enumeration elements();
    
      } // interface Menge
    Methoden zum Einfügen und Entfernen von Elementen aus der Menge sollten nicht im Interface deklariert werden, da dies bei speziellen Mengen notwendig, aber im Allgemeinen nicht möglich ist.

  2. Welche Datenstruktur ist nun zur Realisierung der Menge geeignet. Prinzipiell stehen Felder und Listen zur Verfügung (weil die Menge sicherlich die Elemente speichert, die sie enthält). Da sich eine Menge theoretisch nicht ständig ändert, sondern häufige Lesezugriffe erfolgen, fällt die Liste aus. Beim Zugriff auf ein beliebiges Element ist der Aufwand bei einer Liste O(n).

    Beim Durchlaufen der gesammten Elemente besteht dagegen kein Unterschied. Wenn hingegen häufig Mengen erstellt (mit Durchschnitt, Differenz, Vereinigung) oder gar Mengen direkt verädert werden sollen, ist die Liste vorteilhaft.

    Denkbar sind auch Mengen, bei denen eine Formel bzw. Algorithmus aussagt, ob eine Element dazu gehört oder nicht. Zum Beispiel die Menge der positiven geraden Zahlen. Diese Menge ist unendlich, soweit dies mit int möglich ist. Die Methoden size() und elements() würden in diesem Fall nichts bzw. einen Fehler zurückliefern.

Aufgabe 40 - erweitertes Rational

Ein Blick auf die Tutorseite wird zeigen, dass dort schon eine im Rahmen der Aufgabe 28 (von mir erstellte) Lösung sammt Applet zur Demonstration eingehängt wurde :-> (hier nochmal der Link). Ich denke, dass jeder in der Lage ist, die Berechnung von Brüchen nachzuvollziehen:


  public Rational sub(Rational r) {
    return new Rational(num * r.denom - r.num * denom, denom * r.denom);
  }

  public Rational multiply(Rational r) {
    return new Rational(num * r.num, denom * r.denom);
  }
Der Quelltext ist selbsterläuternd und die gesonderte Testklasse besteht aus diesem Applet.


Erstellt von Markus Durzinsky, aktualisiert 11. Januar 2003
Für Fragen, Probleme oder Anregungen stehe ich gerne zur Verfügung