Algorithmen Und Datenstrukturen at Frankfurt University Of Applied Sciences | Flashcards & Summaries

Select your language

Suggested languages for you:
Log In Start studying!

Lernmaterialien für Algorithmen und Datenstrukturen an der Frankfurt University of Applied Sciences

Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen Algorithmen und Datenstrukturen Kurs an der Frankfurt University of Applied Sciences zu.

TESTE DEIN WISSEN

BFS(G, s)

Lösung anzeigen
TESTE DEIN WISSEN

for each vertex u € G.V \ {s} do

         u.color <- WHITE

         u.d <- ∞

         u.pi <- NIL

s.color <- GRAY

s.d <- 0

s.pi <- NIL

Q <- leer

ENQUEUE(Q, s)

while Q =/= leer do

          u <- DEQUEUE(Q)

          for each v € G.Adj[u] do

                    if v.color = WHITE then

                              v.color <- GRAY

                              v.d <- u.d + 1

                              v.pi <- u

                              ENQUEUE(Q, v)

         u.color <- BLACK

       

Lösung ausblenden
TESTE DEIN WISSEN

Wenn ein Algorithmus definiert ist, was muss man als nächstes zeigen?

Lösung anzeigen
TESTE DEIN WISSEN

- Korrektheit

- Laufzeit

- Vollständigkeit / Terminierung

Lösung ausblenden
TESTE DEIN WISSEN

Definition Algorithmus (Skript)

Lösung anzeigen
TESTE DEIN WISSEN

Ein Algorithmus A ist eine durch einen endlichen Text gegebene Verarbeitungsvorschrift, die zu jeder zulässigen Eingabe x aus einer Menge X eindeutig eine Reihe von Schritten vorschreibt. Nach Anhalten wird ein Ergebnis erzeugt.

Lösung ausblenden
TESTE DEIN WISSEN

Warum ist Dijkstra ein Greedy-Algorithmus?

Lösung anzeigen
TESTE DEIN WISSEN

(Skript), weil er für den jeweils nächsten Startpunkt für seine Analyse denjenigen Knoten auswählt, der am nächsten ist. Dies ist möglich, weil das kürzeste-Weg-Problem die optimale Teilstruktur hat. So können möglichst schnell die kürzesten Wege gefunden werden

Lösung ausblenden
TESTE DEIN WISSEN

Wieso ist Rekursionsgleichung für BINARY-SEARCH: T(n) = T(n/2) + Θ(n/2) + Θ(1)?

Lösung anzeigen
TESTE DEIN WISSEN

Die Laufzeit halbiert sich bei jedem Rekursionsaufruf bis k gefunden wurde

Lösung ausblenden
TESTE DEIN WISSEN

Unter welcher Voraussetzung können n Schlüssel in eine Hashtabelle mit m Behältern mit Kollisionsbeseitigung durch Offene Adressierung eingefügt werden?

Lösung anzeigen
TESTE DEIN WISSEN

Es muss mindestens genauso viele Behälter wie Schlüssel geben (m >= n)

Lösung ausblenden
TESTE DEIN WISSEN

Binärbaum - was bedeutet "gut balanciert"

Lösung anzeigen
TESTE DEIN WISSEN

Ein Baum ist gut balanciert, wenn er nicht tief ist und somit eine geringere Suchzeit hat

Lösung ausblenden
TESTE DEIN WISSEN

Binärbaum - wie erstellt man aus einem Array einen zu einer Liste degenerierten Baum?

Lösung anzeigen
TESTE DEIN WISSEN

Man sortiert das Array aufsteigend.


Dann wird jeder Knoten im Binärbaum links unten einsortiert und es entsteht ein tiefer Baum in Listenform

Lösung ausblenden
TESTE DEIN WISSEN

Nennen Sie 3 Möglichkeiten, einen Algorithmus zu spezifizieren

Lösung anzeigen
TESTE DEIN WISSEN

- Umgangssprache

- Pseudo-Code

- Graphisch

- konkrete Implementierung in einer Prog.-Sprache

- Formale Spezifikation

Lösung ausblenden
TESTE DEIN WISSEN

Warum ist A* ein Greedy-Algorithmus?

Lösung anzeigen
TESTE DEIN WISSEN

A* ist Greedy, da immer der Knoten mit der geringsten Summe aus Kosten und Heuristik als nächstes behandelt wird. Die naive Annahme ist, dass dieser am schnellsten ans Ziel führt

Lösung ausblenden
TESTE DEIN WISSEN

Geben Sie Work & Span an

Lösung anzeigen
TESTE DEIN WISSEN

Work -> Laufzeit auf einem Prozessor (# alle Knoten)


Span -> Längste Laufzeit einer Teilberechnung eines Pfads (# Knoten des längsten zusammenhängenden Pfades)

Lösung ausblenden
TESTE DEIN WISSEN

Laufzeitübersicht - Average Θ(?)

Lösung anzeigen
TESTE DEIN WISSEN

Bubblesort        Θ(n²)

Insertionsort     Θ(n²) 

Mergesort        Θ(n lg n)

Heapsort          Θ(n lg n)

Quicksort         Θ(n lg n)

Dijkstra            Θ(|V|²)

A*                      Θ(|V|²)

DFS                  Θ(|V|+|E|)

BFS                   Θ(|V|+|E|)

FIB                    Θ(n)

Lösung ausblenden
  • 30445 Karteikarten
  • 1261 Studierende
  • 8 Lernmaterialien

Beispielhafte Karteikarten für deinen Algorithmen und Datenstrukturen Kurs an der Frankfurt University of Applied Sciences - von Kommilitonen auf StudySmarter erstellt!

Q:

BFS(G, s)

A:

for each vertex u € G.V \ {s} do

         u.color <- WHITE

         u.d <- ∞

         u.pi <- NIL

s.color <- GRAY

s.d <- 0

s.pi <- NIL

Q <- leer

ENQUEUE(Q, s)

while Q =/= leer do

          u <- DEQUEUE(Q)

          for each v € G.Adj[u] do

                    if v.color = WHITE then

                              v.color <- GRAY

                              v.d <- u.d + 1

                              v.pi <- u

                              ENQUEUE(Q, v)

         u.color <- BLACK

       

Q:

Wenn ein Algorithmus definiert ist, was muss man als nächstes zeigen?

A:

- Korrektheit

- Laufzeit

- Vollständigkeit / Terminierung

Q:

Definition Algorithmus (Skript)

A:

Ein Algorithmus A ist eine durch einen endlichen Text gegebene Verarbeitungsvorschrift, die zu jeder zulässigen Eingabe x aus einer Menge X eindeutig eine Reihe von Schritten vorschreibt. Nach Anhalten wird ein Ergebnis erzeugt.

Q:

Warum ist Dijkstra ein Greedy-Algorithmus?

A:

(Skript), weil er für den jeweils nächsten Startpunkt für seine Analyse denjenigen Knoten auswählt, der am nächsten ist. Dies ist möglich, weil das kürzeste-Weg-Problem die optimale Teilstruktur hat. So können möglichst schnell die kürzesten Wege gefunden werden

Q:

Wieso ist Rekursionsgleichung für BINARY-SEARCH: T(n) = T(n/2) + Θ(n/2) + Θ(1)?

A:

Die Laufzeit halbiert sich bei jedem Rekursionsaufruf bis k gefunden wurde

Mehr Karteikarten anzeigen
Q:

Unter welcher Voraussetzung können n Schlüssel in eine Hashtabelle mit m Behältern mit Kollisionsbeseitigung durch Offene Adressierung eingefügt werden?

A:

Es muss mindestens genauso viele Behälter wie Schlüssel geben (m >= n)

Q:

Binärbaum - was bedeutet "gut balanciert"

A:

Ein Baum ist gut balanciert, wenn er nicht tief ist und somit eine geringere Suchzeit hat

Q:

Binärbaum - wie erstellt man aus einem Array einen zu einer Liste degenerierten Baum?

A:

Man sortiert das Array aufsteigend.


Dann wird jeder Knoten im Binärbaum links unten einsortiert und es entsteht ein tiefer Baum in Listenform

Q:

Nennen Sie 3 Möglichkeiten, einen Algorithmus zu spezifizieren

A:

- Umgangssprache

- Pseudo-Code

- Graphisch

- konkrete Implementierung in einer Prog.-Sprache

- Formale Spezifikation

Q:

Warum ist A* ein Greedy-Algorithmus?

A:

A* ist Greedy, da immer der Knoten mit der geringsten Summe aus Kosten und Heuristik als nächstes behandelt wird. Die naive Annahme ist, dass dieser am schnellsten ans Ziel führt

Q:

Geben Sie Work & Span an

A:

Work -> Laufzeit auf einem Prozessor (# alle Knoten)


Span -> Längste Laufzeit einer Teilberechnung eines Pfads (# Knoten des längsten zusammenhängenden Pfades)

Q:

Laufzeitübersicht - Average Θ(?)

A:

Bubblesort        Θ(n²)

Insertionsort     Θ(n²) 

Mergesort        Θ(n lg n)

Heapsort          Θ(n lg n)

Quicksort         Θ(n lg n)

Dijkstra            Θ(|V|²)

A*                      Θ(|V|²)

DFS                  Θ(|V|+|E|)

BFS                   Θ(|V|+|E|)

FIB                    Θ(n)

Algorithmen und 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 und Datenstrukturen an der Frankfurt University of Applied Sciences

Für deinen Studiengang Algorithmen und Datenstrukturen an der Frankfurt University of Applied Sciences 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 und Datenstrukturen Kurse im gesamten StudySmarter Universum

Datenstrukturen und Algorithmen

Universität Paderborn

Zum Kurs
Algorithmen & Datenstrukturen

Hochschule Fulda

Zum Kurs

Die all-in-one Lernapp für Studierende

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