Algorithmen und Datenstrukturen
10 Questions
0 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Welcher Algorithmus ermöglicht das Finden von kürzesten Pfaden auch mit negativen Gewichten?

  • Breitensuche
  • Bellman und Ford (correct)
  • Floyd Warshall
  • All Pairs Shortest Paths

    • Was ist das Gegenteil von Tiefensuche?

  • All Pairs Shortest Paths
  • Floyd Warshall
  • Netzwerkfluss
  • Breitensuche (correct)

    • Welcher Algorithmus wird verwendet, um den kürzesten Pfad zwischen allen Knotenpaaren zu finden?

  • Bellman und Ford
  • Breitensuche
  • All Pairs Shortest Paths
  • Floyd Warshall (correct)

    • Was beschreibt die Funktion eines Flusses in einem Netzwerk?

    <p>Eine Funktion, die Paare von Knoten auf reele Zahlen abbildet</p> Signup and view all the answers

    Was ist die Besonderheit von Breitensuche im Vergleich zu Tiefensuche?

    <p>Aktive Knoten werden auf einer FIFO-Queue gespeichert</p> Signup and view all the answers

    Was ist die Bedingung für einen Fluss in einem Netzwerk?

    <p>Der Fluss kann maximal die Kapazität c erreichen</p> Signup and view all the answers

    Welcher Algorithmus wird verwendet, um den maximalen Fluss in einem s-t-Netzwerk zu finden?

    <p>Netzwerkfluss</p> Signup and view all the answers

    Was ist das Ziel bei der Berechnung des maximalen Flusses?

    <p>Einen Fluss mit dem maximalen Wert zu erhalten</p> Signup and view all the answers

    Was beschreibt die Symmetrie eines Flusses?

    <p>f(u,v) = f(v,u)</p> Signup and view all the answers

    Was ist die Bedingung für die Flussverhaltung in einem Netzwerk?

    <p>Das was rein kommt geht wieder raus, außer bei s und t</p> Signup and view all the answers

    Study Notes

    Graphenalgorithmen

    • Ein ungerichteter Graph ist ein Paar (V,E) mit V als Menge der Knoten und E als Menge der Kanten.
    • Graphen können durch Adjazenzmatrix (O(∣V∣²)) oder Adjazenzliste (O(∣V∣ + ∣E∣)) dargestellt werden.
    • In O(n^2) Schritten kann man zwischen diesen Darstellungen konvertieren.

    Tiefensuche

    • Die Tiefensuche wird verwendet, um einen gerichteten Tiefensuchwald berechnen, welcher bei einem ungerichteten Graphen ein Baum darstellt.
    • Jeder Knoten bekommt eine Start- und Endzeit.
    • Es gibt Baum-, Vorwärts-, Rückwärts- oder Querkanten.

    Zusammenhangskomponenten

    • U und V sind zusammenhängend, wenn es einen Pfad von u nach v gibt.
    • Es gibt keine echte Obermenge davon.
    • In einer Tiefensuche sind alle schwarzen Knoten eine Zusammenhangskomponente.

    Finden von Kreisen

    • Azyklisch = kein Kreis, dies geschieht, wenn es keine Rückwärtskante gibt.

    Residualnetzwerke

    • Ein Residualnetzwerk ist ein Netzwerk, dem Fluss.
    • Es wird als G_f bezeichnet.

    Augmentierende Pfade

    • Ein s-t Pfad p in G_f ist ein Augmentierender Pfad.
    • c_f(p) heißt Restkapazität von p.
    • Das ist die kleinste Kapazität einer Kante im Augmentierenden Pfad.

    Ford-Fulkerson-Methode

    • Zur Bestimmung des maximalen Flusses.
    • Wir wählen einen Augmentierenden Pfad.
    • Wir wählen hierbei immer den kürzesten Weg.

    Schnitte in Netzwerken

    • Ein Schnitt teilt einen s-t-Netzwerk in S und T auf.
    • f(S,T) ist der Fluss über (S,T), dass heißt, was von S nach T fließt.
    • Die Kapazität ist c(S,T), dass heißt, was von S nach T fließen kann.

    Bipartites Matching

    • Wir haben einen ungerichteten Graphen gegeben, der der aus zwei Gruppen besteht.
    • Wir wollen ein Matching (Paarung) maximaler Kardinalität, also möglichst viele.

    Edmonds-Karp-Algorithmus

    • Hierbei wird der kürzeste Pfad gewählt.
    • Man sucht wieder einen Augmentierenden Pfad und versucht dann die Vorwärtskante zu erhöhen und die Rückwärtskanten zu verringern.

    Bellman und Ford

    • Dieser Algorithmus ermöglicht das Finden von kürzesten Pfaden auch mit negativen Gewichten.
      1. Der Startknoten bekommt die Kosten 0, die anderen n ∞.
      1. Danach wird geprüft, ob die Kosten für den Anfangsknoten der Kante plus den Wert der Kante.

    All Pairs Shortest Paths

    • Eingabe: gerichteter Graph mit Kiantengewichten, Ausgabe: Abstände und kürzester Weg zwischen allen Knotenpaaren.

    Floyd Warshall

    • Wir erstellen eine Matrix wie bei den Graphen, nur, dass wir dort das Kantengewicht eintragen.
    • Wir versuchen nun den Pfad zu finden für die mit unendlich markierten Felder.

    Breitensuche

    • Breitensuche ist das Gegenteil von Tiefensuche.
    • Eine Breitensuche enthält kürzeste Pfade.
    • Hier gibt es nur die Discoverytime.

    Netzwerkalgorithmen

    • Netzwerkfluss: Ein Fluss hat eine Quelle s und eine Senke t.
    • s-t-Netzwerke: In einem solchen Netzwerk hat jede Kante eine Kapazität > 0 und eine Quelle und eine Senke.

    Flüsse

    • Ein Fluss ist eine Funktion, die Paare von Knoten auf reelle Zahlen abbildet.
      1. Zulässigkeit: Der Fluss kann maximal die Kapazität c erreichen.
      1. Symmetrie: f(u,v) = -f(v,u).
      1. Fluerhaltung: Das, was rein kommt, geht wieder raus, außer bei s und t.
      1. |f| ist der Gesammtfluss.

    Maximaler Fluss

    • Wir haben ein s-t-Netzwerk gegeben und wollen einen Fluss mit dem maximalen Wert erhalten.

    Studying That Suits You

    Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

    Quiz Team

    Related Documents

    zusammenfassung-dsal-datenstrukturen-algorithmen.pdf

    Description

    Dieser Quiz behandelt die Eigenschaften von verschiedenen Algorithmen und Datenstrukturen, wie Laufzeit und vergleichsbasierte Verfahren. Es werden die Worst-Case und Mittel-Laufzeiten von verschiedenen Algorithmen verglichen.

    More Like This

    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser