Erstmals bekommen alle angehenden Abiturienten in NRW dieselben Fragen gestellt - wir dokumentieren die Aufgabenstellungen in einigen zentralen Reifeprüfungen. Gestern ging es unter anderem um das Fach Informatik. Hier die Aufgaben, die in eine sehr spezielle Welt führen:

Ein Navigationssystem führt den Benutzer auf einer optimierten Route vom Start (S) gegebenenfalls über Zwischenstationen zum Ziel (Z). Bei der Berechnung der optimierten Route soll die Art der Straße berücksichtigt werden. Der Graph (siehe Grafik) stellt einen Ausschnitt aus einer internen Karte eines Navigationssystems für den Raum Düsseldorf-Nord / Duisburg-Zentrum dar. Das Navigationssystem unterscheiABITUR 2007

Informatik (Leistungskurs)

det innerstädtische Straßen, Landstraßen und Autobahnen, die graphisch durch unterschiedliche Linienformen dargestellt sind. Die in der Darstellung angegebenen Kantengewichte stellen die Entfernungen der Knoten in Kilometern dar. Zunächst bleiben die unterschiedlichen Straßenarten, dargestellt durch die unterschiedlichen Linienformen, unberücksichtigt.

Überführen Sie die Darstellung des Graphen in eine Adjazenzmatrix. Geben Sie an, welche besonderen Eigenschaften diese Adjazenzmatrix hat.

Überführen Sie die Darstellung des Graphen in eine Adjazenzliste. Kanten in dem ungerichteten Graphen sollten dabei jeweils doppelt als entgegengesetzt gerichtete Kanten eingetragen werden.

In der Anlage finden Sie die Klassendokumentationen der Klassen TList, TGraphNode, TEdge und TGraph. Analysieren Sie die Klassendokumentationen und geben Sie alle Objektbeziehungen für ein Objekt der Klasse TGraph und alle Objektbeziehungen für ein Objekt der Klasse TGraphNode in zwei getrennten Klassen-Diagrammen an. Die Attribute und Methoden müssen nicht dargestellt werden. Beurteilen Sie deren Tauglichkeit, um die Karte des Navigationssystems inklusive der Straßenarten abzubilden.

Die konkrete Karte in einfacher Form (ohne Straßenarten) soll in einer Klasse TNaviGraph abgebildet werden. Implementieren Sie den Konstruktor, der einen konkreten Graphen hGraph erzeugt. Es reicht der Teilgraph mit dem Knoten ABCDS. Implementieren Sie eine Methode, die, ausgehend von einem bestimmten Knoten, den Nachbarknoten liefert, der die kürzeste Entfernung von diesem Knoten hat. Wählen Sie als Methodenkopf: function TNavigraph.findeNaechstenNAchbarn (pName: string) :string;

Ein Navigationssystem bestimmt die kürzeste Strecke zwischen zwei beliebigen Orten. Geben Sie einen geeigneten Algorithmus (keinen Programmcode) zur Bestimmung der kürzesten Entfernung an und erläutern Sie diesen. Leiten Sie unter Anwendung dieses Algorithmus bei Angabe aller Zwischenschritte den kürzesten Weg vom Start (S) zum Ziel (Z) her.

Die konkrete Karte enthält unterschiedliche Straßenarten. Das Navigationssystem soll optimale Wege wahlweise nach den Kriterien „kürzester Weg“, „kürzeste Fahrzeit“ oder „günstigster Benzinverbrauch“ liefern. Entwickeln Sie eine Problemlösung für die komplexe Kartenstruktur und leiten Sie bei Angabe aller Zwischenschritte den Weg mit der kürzesten Fahrzeit im Teilgraph ABCDS von S nach D ab. (ksta)

---

---