Universität Mannheim
Lehrstuhl für Praktische Informatik IV
Prof. Dr. W. Effelsberg
R. Lienhart 416
S. Pfeiffer 417

Bitte unbedingt beachten:

Die Programme müssen in ANSI-C geschrieben werden.
Sie müssen im Pool mit dem GNU C-Compiler gcc -Wall -ansi -pedantic fehlerfrei übersetzbar und lauffähig sein.
Wenn mehrere Dateien mit der abox abgegeben werden sollen, müssen sie vorher mit dem Befehl tar zu einer Datei zusammengebunden werden.

Übungsblatt 8

Abgabe: 8.2.96 um 12:00 Uhr

Aufgabe 1 [20 Punkte] String Matching

Gegeben sei ein String b1 b2 ... bm und ein Muster a1 a 2 ... an, n <= m. Gesucht sind alle Vorkommen des Musters in dem String.
  1. Programmieren Sie die "naive" Suche.
  2. Programmieren Sie das Suchverfahren nach Knuth-Morris-Pratt.
  3. Schreiben Sie für beide Verfahren jeweils ein Hauptprogramm, so daß die beiden Verfahren wie folgt von der Kommandozeile aufgerufen werden können:

    naiveSuche <Datei mit String b> <Datei mit Muster a>
    bzw.
    KnuthMorrisPrattSuche <Datei mit String b> <Datei mit Muster a>

    In den beiden Dateien stehen das Muster bzw. der String. Lesen Sie diese Zeichen für Zeichen ein.

  4. Testen Sie ihre beiden Implementierungen mit langen Mustern und sehr langen Strings. Vergleichen Sie die Laufzeit beider Verfahren.

Aufgabe 2 [20 Punkte] Planare Graphen

Gegeben sei ein Graph als Menge von Knoten und Kanten. Beschreiben Sie einen Algorithmus, der feststellt, ob der Graph planar ist, d.h. ob er so gezeichnet werden kann, daß sich die Kanten nicht überschneiden. Implementieren Sie ihn anschließend.

Hinweis: Finden sie den Algorithmus in der Literatur! Geben Sie bitte bei Ihrer Lösung die Literaturquelle an.

Last modified: Thu Jan 25 14:04:12 MET 1996