0 Daumen
575 Aufrufe

Könnte mir jemand helfen einen Pseudocode zu erstellen?

Aufgabe 1:

Entwirf einen Algorithmus EXZENTRIZITAT in Pseudocode (maximal 10 Zeilen \( ^{1} \) ) mit Laufzeit \( O(n+m) \), der für einen gegebenen Graphen \( G \) und Knoten \( v \in V \) den Wert ex \( (v) \) bestimmt.

Aufgabe 2:

Entwirf einen Algorithmus DURCHMESSER in Pseudocode (maximal 10 Zeilen \( ^{1} \) ) mit Laufzeit \( O\left(n^{2}+n m\right) \), der für einen gegebenen Graphen \( G \) den Wert \( \operatorname{diam}(G) \) bestimmt. Begründe kurz, warum die Laufzeit eingehalten wird.

Infos:

- Die Distanz dist \( (v, w) \) zwischen zwei Knoten \( v, w \in V \) in einem Graphen \( G \) ist die Anzahl an Kanten auf einem kürzesten Weg zwischen \( v \) und \( w \) in \( G \). Gibt es keinen Weg zwischen \( v \) und \( w \), so ist \( \operatorname{dist}(v, w)=\infty \).


- Die Exzentrizität ex \( (v) \) eines Knotens \( v \in V \) bezeichnet die Länge eines kürzesten Pfades zu dem am weitesten entfernten Knoten, d.h. \( \operatorname{ex}(v):=\max _{w \in V}(\operatorname{dist}(v, w)) . \)


- Der Durchmesser eines Graphen \( G \) entspricht dem Maxinum iber die Exzentrizitäten, d.h. \( \operatorname{diam}(G):=\max _{v \in V}(\operatorname{ex}(v)) \).

4D215C89-D7DB-48D3-BE8B-4BF83B2A3E28.jpeg

Avatar von

1 Antwort

0 Daumen

Beschäftige dich mal mit dem Sinn und Zweck sowie dem möglichen Aussehen von Pseudocode, zum Beispiel nach

https://de.wikipedia.org/wiki/Pseudocode,

und den darin enthaltenen Verweisen. Vermutlich wird auch das Skript helfen.

Weiterhin musst du natürlich auch geeignete Algorithmen finden. Das sollte bei dem sehr übersichtlichen Graphen aber nicht sehr schwer sein.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community