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 3

Abgabe: 16.11.95 um 12:00 Uhr

Aufgabe 1 [10 Punkte]

Schreiben Sie zwei Funktionen zum Ein- und Auslesen von Daten aus einer Datei in einen/von einem Array: 
int readData ( FILE *fileptr, int *arrayptr )
int writeData ( FILE *fileptr, int *arrayptr )
Dabei soll die Funktion readData die ihr übergebene Datei von Anfang bis Ende in den Array einlesen, wobei genau ein malloc-Befehl eingesetzt werden soll. Die Datei ist so aufgebaut, daß in jeder Zeile genau ein Integerwert steht. writeData soll eine entsprechende Datei erzeugen.

Aufgabe 2 [20 Punkte]

  1. Berechnen Sie den Aufwand an Speicherplatz und an Rechenzeit, den der Algorithmus 3 aus der Vorlesung zur Lösung des N-Damen-Problems benötigt (auf Papier). Begründen Sie detailliert Ihre Ergebnisse.
  2. Implementieren Sie den Algorithmus 3 aus der Vorlesung und führen Sie Laufzeitmessungen durch, indem Sie die Bibliotheksfunktion times (-> man-pages) verwenden. Testen Sie Ihr Programm dazu mit so vielen Damen wie möglich. Messen Sie auf Ihrem Praktikumsrechner, für wieviele Damen das Programm benötigt.

Aufgabe 3 [50 Punkte]

In der Vorlesung haben Sie den Algorithmus von Prim zur Berechnung des minimal spannenden Baumes für einen gewichteten, ungerichteten Graphen kennengelernt. Sie sollen diesen Algorithmus nun implementieren. Der Graph sei dabei in einer Datei gespeichert, die wie folgt aufgebaut ist: 
\Anzahl_Knoten\
\Knoten1_von_Kante\ \Knoten2_von_Kante\ \Kantengewicht\
\Knoten1_von_Kante\ \Knoten2_von_Kante\ \Kantengewicht\
...
\Knoten1_von_Kante\ \Knoten2_von_Kante\ \Kantengewicht\

Beispiel:

  1. Überlegen Sie sich zunächst Datenstrukturen (auf Papier), mit denen Sie den Graphen effizient speichern können. Begründen Sie ihre Wahl kurz.
  2. Implementieren Sie dann ihre Datenstrukturen, eine Routine zum Einlesen des Graphen von der Datei in Ihre Datenstrukturen und den Algorithmus von Prim.
  3. Überlegen Sie, welchen Aufwand der Algorithmus größenordnungsmäßig hat und begründen Sie.
  4. Führen Sie Laufzeitmessungen an ihrem Programm durch, indem Sie die Bibliotheksfunktion times verwenden. Testen Sie Ihr Programm dazu mit Graphen mit bis zu 20 Knoten.

Last modified: Thu Nov 9 12:37:45 MET 1995