Datenstrukturen Und Algorithmen at Universität Paderborn | Flashcards & Summaries

Select your language

Suggested languages for you:
Log In Start studying!

Lernmaterialien für Datenstrukturen und Algorithmen an der Universität Paderborn

Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen Datenstrukturen und Algorithmen Kurs an der Universität Paderborn zu.

TESTE DEIN WISSEN
Was sind inkrementelle Algorithmen?
Lösung anzeigen
TESTE DEIN WISSEN
aufeinander aufbauende Algorithmen
Lösung ausblenden
TESTE DEIN WISSEN
Wie funktioniert Insertion-Sort?
Lösung anzeigen
TESTE DEIN WISSEN
Insertion-Sort ist ein Algrotihmus, mit dem man ein Array sortieren kann, indem man das erste Element, mit dem zweiten vergleicht, diese dann sortiert und dies immer so weiter, bis man an n-ter Stelle, also der Länge des Arrays angelangt ist.
Lösung ausblenden
TESTE DEIN WISSEN
Was ist die Invariante bei Insertion-Sort?
Lösung anzeigen
TESTE DEIN WISSEN
I(j): A[1...j-1] enthält die Zahlen in A_0[1...j-1] in sortierter Reihenfolge.
Ziel: A[1...n] ist sortiert.
Initiliasierung: Anfangs gilt I(2) offensichtlich, da am Anfang das Array immer sortiert ist j=2.
Erhaltung: am Anfang gilt I(j) und am Ende gilt I(j+1)
Terminierung: Am Ende gilt I(length(A)+1)

Lösung ausblenden
TESTE DEIN WISSEN
Was ist eine Invariante?
Lösung anzeigen
TESTE DEIN WISSEN
Eine Invariante ist dazu da um die Korrektheit eines Algorithmus zu überprüfen.
Es gitb 3 Schritte dafür:
1. Initialiserung
2.Erhaltung
3.Terminierung
Lösung ausblenden
TESTE DEIN WISSEN
Wie kann man mit linearer Zeit sortieren?
Lösung anzeigen
TESTE DEIN WISSEN
man verkleinert den Definitionsbereich.
Lösung ausblenden
TESTE DEIN WISSEN
Wie funktioniert Counting-Sort?
Lösung anzeigen
TESTE DEIN WISSEN
Counting-Sort ist ein Abzähl-Algorithmus, der die j-ten Einträgen in die i-ten Felder kopiert.
Der Algorithmus zählt die Werte der Elemente des Arrays und sortiert die selben Werte zusammen.
Lösung ausblenden
TESTE DEIN WISSEN
Wie funktioniert Radix-Sort?
Lösung anzeigen
TESTE DEIN WISSEN
Man sortiert Ziffer für Ziffer gemäß Counting-Sort und Behalte bei Betrachtung der i-ten Ziffer die Reihenfolge der Elemente mit gleicher i-ter Ziffer bei.
Annahme: für alle Zahlen z: 0<=z<k^d.
for i←1 to d do
Counting-Sort(A,B,i,k-1)

Laufzeit: O(d(n+k))
k=n und d konstant: Laufzeit O(n)
Lösung ausblenden
TESTE DEIN WISSEN
Definition 10.2?
Lösung anzeigen
TESTE DEIN WISSEN
Die Operationen, Einfügen, Entfernen und Suchen heißen zusammen Wörterbuch (engl. Dictonary) 
Lösung ausblenden
TESTE DEIN WISSEN
Elementare Operationen?
Lösung anzeigen
TESTE DEIN WISSEN
Insert(S,x)
Search(S,k)
Remove(S,x)
Minimum(S)
Maximum(S)
Lösung ausblenden
TESTE DEIN WISSEN
Was ist ein Stack?
Lösung anzeigen
TESTE DEIN WISSEN
Stacks(Stapel) sind eine Datenstruktur, die die LIFO (last-in-first-out) Regel implementiert.
LIFO Regel = das zuletzt eingefügte Element wird entfernt.
Lösung ausblenden
TESTE DEIN WISSEN
Was ist eine Queque?
Lösung anzeigen
TESTE DEIN WISSEN
Queques sind eine Datenstruktur, die die FIFO (first-in-first-out) Regel implementiert.
FIFO = das Element, welches am längsten in der Menge ist, wird entfernt.
Lösung ausblenden
TESTE DEIN WISSEN
Welche Operationen gibt es für Stacks?
Lösung anzeigen
TESTE DEIN WISSEN
Push
Lösung ausblenden
  • 79538 Karteikarten
  • 2111 Studierende
  • 35 Lernmaterialien

Beispielhafte Karteikarten für deinen Datenstrukturen und Algorithmen Kurs an der Universität Paderborn - von Kommilitonen auf StudySmarter erstellt!

Q:
Was sind inkrementelle Algorithmen?
A:
aufeinander aufbauende Algorithmen
Q:
Wie funktioniert Insertion-Sort?
A:
Insertion-Sort ist ein Algrotihmus, mit dem man ein Array sortieren kann, indem man das erste Element, mit dem zweiten vergleicht, diese dann sortiert und dies immer so weiter, bis man an n-ter Stelle, also der Länge des Arrays angelangt ist.
Q:
Was ist die Invariante bei Insertion-Sort?
A:
I(j): A[1...j-1] enthält die Zahlen in A_0[1...j-1] in sortierter Reihenfolge.
Ziel: A[1...n] ist sortiert.
Initiliasierung: Anfangs gilt I(2) offensichtlich, da am Anfang das Array immer sortiert ist j=2.
Erhaltung: am Anfang gilt I(j) und am Ende gilt I(j+1)
Terminierung: Am Ende gilt I(length(A)+1)

Q:
Was ist eine Invariante?
A:
Eine Invariante ist dazu da um die Korrektheit eines Algorithmus zu überprüfen.
Es gitb 3 Schritte dafür:
1. Initialiserung
2.Erhaltung
3.Terminierung
Q:
Wie kann man mit linearer Zeit sortieren?
A:
man verkleinert den Definitionsbereich.
Mehr Karteikarten anzeigen
Q:
Wie funktioniert Counting-Sort?
A:
Counting-Sort ist ein Abzähl-Algorithmus, der die j-ten Einträgen in die i-ten Felder kopiert.
Der Algorithmus zählt die Werte der Elemente des Arrays und sortiert die selben Werte zusammen.
Q:
Wie funktioniert Radix-Sort?
A:
Man sortiert Ziffer für Ziffer gemäß Counting-Sort und Behalte bei Betrachtung der i-ten Ziffer die Reihenfolge der Elemente mit gleicher i-ter Ziffer bei.
Annahme: für alle Zahlen z: 0<=z<k^d.
for i←1 to d do
Counting-Sort(A,B,i,k-1)

Laufzeit: O(d(n+k))
k=n und d konstant: Laufzeit O(n)
Q:
Definition 10.2?
A:
Die Operationen, Einfügen, Entfernen und Suchen heißen zusammen Wörterbuch (engl. Dictonary) 
Q:
Elementare Operationen?
A:
Insert(S,x)
Search(S,k)
Remove(S,x)
Minimum(S)
Maximum(S)
Q:
Was ist ein Stack?
A:
Stacks(Stapel) sind eine Datenstruktur, die die LIFO (last-in-first-out) Regel implementiert.
LIFO Regel = das zuletzt eingefügte Element wird entfernt.
Q:
Was ist eine Queque?
A:
Queques sind eine Datenstruktur, die die FIFO (first-in-first-out) Regel implementiert.
FIFO = das Element, welches am längsten in der Menge ist, wird entfernt.
Q:
Welche Operationen gibt es für Stacks?
A:
Push
Datenstrukturen und Algorithmen

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 Datenstrukturen und Algorithmen an der Universität Paderborn

Für deinen Studiengang Datenstrukturen und Algorithmen an der Universität Paderborn 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 Datenstrukturen und Algorithmen Kurse im gesamten StudySmarter Universum

Algorithmen und Datenstrukturen

Universität Koblenz-Landau

Zum Kurs
Algorithmen und Datenstrukturen

Fachhochschule Wiener Neustadt

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 Datenstrukturen und Algorithmen
Erstelle Karteikarten und Zusammenfassungen mit den StudySmarter Tools
Kostenlos loslegen Datenstrukturen und Algorithmen