WS 97/98: Algorithmen und Programmierung III - Übungsblatt 12
- das letzte Blatt!
Abgabe bis 5.2., 12.30 Uhr
Aufgabe 1 (8 Punkte)
Wir betrachten ein Straßennetz ohne Einbahnstraßen. Von einer
Kreuzung gehen mindestens drei Straßen aus, jede in einer
bestimmten Richtung.
Ich bin mit dem Auto in Brandenburg unterwegs, will nach Wurzelow
und habe keine Straßenkarte. Die sehr hohe Kirchturmspitze von
St. Michael in Wurzelow kann ich allerdings schon erkennen.
Außerdem habe ich meinen Wanderkompaß dabei. Wie verhalte ich mich?
a) Verfasse einen umgangssprachlichen - aber präzisen - Algorithmus
und diskutiere seine Praktikabilität!
b) Das Straßennetz kann durch einen ungerichteten Graphen modelliert
werden, bei dem allerdings die Richtungen der Abzweigungen an den
Kreuzungen zu berücksichtigen sind. Ferner muß für jede Kreuzung
angegeben sein, in welcher Richtung der Kirchturm zu sehen ist.
Verfasse eine Spezifikation für einen solchen Graphen, auf die
sich der Wegsuch-Algorithmus beziehen kann!
c) Implementiere den Algorithmus imperativ oder funktional!
d) Implementiere den Graphen imperativ oder funktional!
Aufgabe 2 (6 Punkte)
Wir betrachten gerichtete Graphen, die als Geflechte implementiert
sind. Die Spezifikation sehe wie folgt aus:
DEFINITION MODULE Graph; (* Gerichteter Graph natürlicher Zahlen,
anfangs leer;
Inv.: zyklenfrei, keine isolierten Ecken *)
TYPE AdjMatrix = ...;
PROCEDURE add(a,b: CARDINAL): BOOLEAN;
(* Vor.: (Effekt verletzt nicht die Invariante.)
Eff.: Graph ist um Kante (a,b) erweitert. *)
PROCEDURE reachable(from: CARDINAL; VAR graph: AdjMatrix): BOOLEAN;
(* Vor.: Graph enthält die Ecke from.
Eff.: graph ist die Adjazenzmatrix desjenigen Graphen,
der aus allen Kanten besteht, die von from aus
erreicht und durchlaufen werden können.
Graph bleibt unverändert. *)
PROCEDURE .....
END Graph.
Wähle einen geeigneten Feldtyp für die Adjanzenzmatrix
(erzwingt das ein Modifikation der Spezifikation?)
und implementiere Graph als Geflecht!
27.1.1998