Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:repraesentation:effizienz:start [30.11.2022 20:07] – angelegt Frank Schiebel
+++ faecher:informatik:oberstufe:graphen:zpg:repraesentation:effizienz:start [15.04.2024 06:21] (aktuell) – [Laufzeitanalyse] Marco Kuemmel
@@ Zeile 6: / Zeile 6: @@
 Repräsentiert der Graph z.B. eine Karte mit Straßen und Kreuzungen, gehen von jedem Knoten (=Kreuzung) nur wenige Kanten (=Straßen) ab. Mehr als 4-5 Straßen gehen üblicherweise nicht von einer Kreuzung aus. Diese Zahl ändert sich auch nicht, wenn die Anzahl der Knoten steigt. Der Graph ist also sehr dünn. Betrachtet man hingegen das Traveling Salesman Problem, dann kann man von jeder Stadt in jede andere reisen. Der Graph ist also vollständig. Bei einer Erhöhung der der Knotenzahl steigt damit auch die Zahl der Kanten pro Knoten.
+===== Speicherplatz (ungerichteter, gewichteter Graph) =====
+  * Adjazenzliste: Zwei Zahlen (Nummer des Nachbarknoten, Entfernung) werden gespeichert.
+  * Adjazenzmatrix: Eine Zahl (Entfernung) wird in jeder Zelle gespeichert (Die Zahl 0 für keine Kante).
+----
+{{:aufgabe.png?nolink  |}}
+=== (A1) ===
+Vervollständige die folgende Tabelle und formulieren einen Ergebnissatz für die Bewertung des Speicherplatzbedarfs.
+{{ :faecher:informatik:oberstufe:graphen:zpg:repraesentation:effizienz:auswahl_414.png |}}
+===== Laufzeitanalyse =====
+Die Laufzeit einzelner Operationen hängt von der Art der Implementierung ab.
+  * Adjazenzliste: 	Ein Array enthält für jeden Knoten eine einfach verkettete Liste der Kanten.
+  * Adjazenzmatrix: 	Zweidimensionales Array.
+----
+{{:aufgabe.png?nolink  |}}
+=== (A2) ===
+Vervollständige die folgende Tabelle und formuliere einen Ergebnissatz für die Bewertung des Laufzeitverhaltens bei den gegebenen Implementierungen.
+{{ :faecher:informatik:oberstufe:graphen:zpg:repraesentation:effizienz:auswahl_415.png |}}