Algorithmen & Datenstrukturen at Hochschule Kempten | Flashcards & Summaries

Select your language

Suggested languages for you:
Log In Start studying!

Lernmaterialien für Algorithmen & Datenstrukturen an der Hochschule Kempten

Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen Algorithmen & Datenstrukturen Kurs an der Hochschule Kempten zu.

TESTE DEIN WISSEN

Welche Eigenschaften besitzt der Dijkstra-Algorithmus?

Lösung anzeigen
TESTE DEIN WISSEN

- Der Dijkstra-Algorithmus liefert keine Näherung, sondern garantiert Optimalität 

- Durch Hinzunahme einer Kante mit positiven Kosten können die Gesamtkosten nur wachsen 

- Der längste beste Pfad hat maximal ( |V|-1) Kanten.

Lösung ausblenden
TESTE DEIN WISSEN

Was muss beim Erweiterungspfad gelten?

Lösung anzeigen
TESTE DEIN WISSEN

- Ein Erweiterungspfad ist ein Pfad im Restnetzwerk von s nach t. 


- Pfad mit größter möglicher Kapazität wählen


-Ohne Zyklus
Lösung ausblenden
TESTE DEIN WISSEN

Erklären Sie das Prinzip des Simulated Annealing (evtl. können)

Lösung anzeigen
TESTE DEIN WISSEN

- Zufällige Lösungsvarianten werden erzeugt 

- Bessere Lösungen werden übernommen 

- Schlechtere Lösungen werden in einer bestimmten Wahrscheinlichkeit übernommen. 


➔ Kann lokale Täler überwinden, da auch schlechtere Lösungen verfolgt werden

Lösung ausblenden
TESTE DEIN WISSEN

Erklären Sie Threshold accepting & Sintflut-Algorithmus (evtl. können)

Lösung anzeigen
TESTE DEIN WISSEN

- Selbes Prinzip wie „Simulated Annealing“ 

- Unterschied: 

o Threshold Accepting: mit einer Schranke für die Verschlechterung 

o Sintflut-Algorithmus: Schranke für die Akzeptanz

Lösung ausblenden
TESTE DEIN WISSEN

Was gilt für Knoten eines Flusses?

Lösung anzeigen
TESTE DEIN WISSEN

- Die Kapazität entspricht dem maximalen Durchfluss von Knoten zu Knoten

Lösung ausblenden
TESTE DEIN WISSEN

Bei Adjazenzmatrix können die Verbindungen direkt abgelesen werden, weitere Vorteile:

Lösung anzeigen
TESTE DEIN WISSEN

Inzidente Kanten eines Knotens und adjazente Knoten sind schnell bestimmbar.

Lösung ausblenden
TESTE DEIN WISSEN

Welche Möglichkeiten gibt es einen minimalen Spannbaum zu finden?

Lösung anzeigen
TESTE DEIN WISSEN

- Prim-Algorithmus 

- Kruskal-Algorithmus

Lösung ausblenden
TESTE DEIN WISSEN

Welche Eigenschaften besitzen Graphen?

Lösung anzeigen
TESTE DEIN WISSEN

- Knoten 

- Kanten 

- Gewicht (bei gewichtetem Graphen) 

- Richtung (bei gerichtetem Graphen) 

- (Heuristik bei A*-Algorithmus) 

- (Zyklus) 

- (Pfad)

Lösung ausblenden
TESTE DEIN WISSEN

Welche Darstellungsformen kennen Sie für Graphen?

Lösung anzeigen
TESTE DEIN WISSEN

- Adjazenzmatrix 

- Adjazenzliste 

- Kantenliste (Kantenorientierte Darstellung) 


➔ Die Dichte eines Graphen ist Hauptkriterium bei der Auswahl einer Darstellungsform

Lösung ausblenden
TESTE DEIN WISSEN

Erklären Sie den Ablauf des A*-Algorithmus:

Lösung anzeigen
TESTE DEIN WISSEN

1. Schritt: Tabelle aufstellen mit 

a. CLOSED: In der CLOSED-Liste warden alle Knoten gesammelt, die fertig bearbeitet sind, also ein kürzester Weg vom Startknoten bekannt ist

b. OPEN: In der OPEN-Liste werden alle Knoten gesammelt, zu denen ein Weg gefunden wurde, der Wert f(u) wird gespeichert. 

c. REST: Noch unbearbeitete Knoten 


2. Schritt: Startknoten in OPEN-Liste eintragen 


3. Schritt: Solange OPEN-Liste nicht leer: 

a. Entnehme Knoten mit kleinstem 

f-Wert = Kosten von Start zu Knoten + Heuristik (von Start zu Knoten) 

i. Fertig, falls Knoten Zielknoten (-> Weg gefunden) 

b. Expandiere Knoten in die CLOSED-Liste

Lösung ausblenden
TESTE DEIN WISSEN

Was berechnet der Dijkstra-Algorithmus?

Lösung anzeigen
TESTE DEIN WISSEN

berechnet alle kürzesten Wege von einem Startknoten (source) zu allen anderen (Single Source Best Path, Dijkstra 1959).

Lösung ausblenden
TESTE DEIN WISSEN

Was ist maximales Matching, Maximum Matching und perfektes Matching?

Lösung anzeigen
TESTE DEIN WISSEN

- Perfektes Matching: Ein Matching M heißt perfekt, wenn es alle Knoten des Graphen überdeckt


- Maximales Matching: Ein Matching M heißt maximal (nicht erweiterbar), wenn es um keine Kante erweitert werden kann


- Maximum Matching: Ein Matching M heißt Maximum, wenn es kein Matching mit mehr Kanten gibt, d.h. |M| ist maximale Größe.

Lösung ausblenden
  • 27421 Karteikarten
  • 762 Studierende
  • 14 Lernmaterialien

Beispielhafte Karteikarten für deinen Algorithmen & Datenstrukturen Kurs an der Hochschule Kempten - von Kommilitonen auf StudySmarter erstellt!

Q:

Welche Eigenschaften besitzt der Dijkstra-Algorithmus?

A:

- Der Dijkstra-Algorithmus liefert keine Näherung, sondern garantiert Optimalität 

- Durch Hinzunahme einer Kante mit positiven Kosten können die Gesamtkosten nur wachsen 

- Der längste beste Pfad hat maximal ( |V|-1) Kanten.

Q:

Was muss beim Erweiterungspfad gelten?

A:

- Ein Erweiterungspfad ist ein Pfad im Restnetzwerk von s nach t. 


- Pfad mit größter möglicher Kapazität wählen


-Ohne Zyklus
Q:

Erklären Sie das Prinzip des Simulated Annealing (evtl. können)

A:

- Zufällige Lösungsvarianten werden erzeugt 

- Bessere Lösungen werden übernommen 

- Schlechtere Lösungen werden in einer bestimmten Wahrscheinlichkeit übernommen. 


➔ Kann lokale Täler überwinden, da auch schlechtere Lösungen verfolgt werden

Q:

Erklären Sie Threshold accepting & Sintflut-Algorithmus (evtl. können)

A:

- Selbes Prinzip wie „Simulated Annealing“ 

- Unterschied: 

o Threshold Accepting: mit einer Schranke für die Verschlechterung 

o Sintflut-Algorithmus: Schranke für die Akzeptanz

Q:

Was gilt für Knoten eines Flusses?

A:

- Die Kapazität entspricht dem maximalen Durchfluss von Knoten zu Knoten

Mehr Karteikarten anzeigen
Q:

Bei Adjazenzmatrix können die Verbindungen direkt abgelesen werden, weitere Vorteile:

A:

Inzidente Kanten eines Knotens und adjazente Knoten sind schnell bestimmbar.

Q:

Welche Möglichkeiten gibt es einen minimalen Spannbaum zu finden?

A:

- Prim-Algorithmus 

- Kruskal-Algorithmus

Q:

Welche Eigenschaften besitzen Graphen?

A:

- Knoten 

- Kanten 

- Gewicht (bei gewichtetem Graphen) 

- Richtung (bei gerichtetem Graphen) 

- (Heuristik bei A*-Algorithmus) 

- (Zyklus) 

- (Pfad)

Q:

Welche Darstellungsformen kennen Sie für Graphen?

A:

- Adjazenzmatrix 

- Adjazenzliste 

- Kantenliste (Kantenorientierte Darstellung) 


➔ Die Dichte eines Graphen ist Hauptkriterium bei der Auswahl einer Darstellungsform

Q:

Erklären Sie den Ablauf des A*-Algorithmus:

A:

1. Schritt: Tabelle aufstellen mit 

a. CLOSED: In der CLOSED-Liste warden alle Knoten gesammelt, die fertig bearbeitet sind, also ein kürzester Weg vom Startknoten bekannt ist

b. OPEN: In der OPEN-Liste werden alle Knoten gesammelt, zu denen ein Weg gefunden wurde, der Wert f(u) wird gespeichert. 

c. REST: Noch unbearbeitete Knoten 


2. Schritt: Startknoten in OPEN-Liste eintragen 


3. Schritt: Solange OPEN-Liste nicht leer: 

a. Entnehme Knoten mit kleinstem 

f-Wert = Kosten von Start zu Knoten + Heuristik (von Start zu Knoten) 

i. Fertig, falls Knoten Zielknoten (-> Weg gefunden) 

b. Expandiere Knoten in die CLOSED-Liste

Q:

Was berechnet der Dijkstra-Algorithmus?

A:

berechnet alle kürzesten Wege von einem Startknoten (source) zu allen anderen (Single Source Best Path, Dijkstra 1959).

Q:

Was ist maximales Matching, Maximum Matching und perfektes Matching?

A:

- Perfektes Matching: Ein Matching M heißt perfekt, wenn es alle Knoten des Graphen überdeckt


- Maximales Matching: Ein Matching M heißt maximal (nicht erweiterbar), wenn es um keine Kante erweitert werden kann


- Maximum Matching: Ein Matching M heißt Maximum, wenn es kein Matching mit mehr Kanten gibt, d.h. |M| ist maximale Größe.

Algorithmen & Datenstrukturen

Erstelle und finde Lernmaterialien auf StudySmarter.

Greife kostenlos auf tausende geteilte Karteikarten, Zusammenfassungen, Altklausuren und mehr zu.

Jetzt loslegen

Das sind die beliebtesten StudySmarter Kurse für deinen Studiengang Algorithmen & Datenstrukturen an der Hochschule Kempten

Für deinen Studiengang Algorithmen & Datenstrukturen an der Hochschule Kempten gibt es bereits viele Kurse, die von deinen Kommilitonen auf StudySmarter erstellt wurden. Karteikarten, Zusammenfassungen, Altklausuren, Übungsaufgaben und mehr warten auf dich!

Das sind die beliebtesten Algorithmen & Datenstrukturen Kurse im gesamten StudySmarter Universum

Algorithmen und Datenstrukturen

Universität Koblenz-Landau

Zum Kurs
Algorithmen und Datenstrukturen

Frankfurt University of Applied Sciences

Zum Kurs
Algorithmen und Datenstrukturen

Universität Jena

Zum Kurs

Die all-in-one Lernapp für Studierende

Greife auf Millionen geteilter Lernmaterialien der StudySmarter Community zu
Kostenlos anmelden Algorithmen & Datenstrukturen
Erstelle Karteikarten und Zusammenfassungen mit den StudySmarter Tools
Kostenlos loslegen Algorithmen & Datenstrukturen