Algorithmen und Datenstrukturen Flashcards
Was ist Komplexität? Wofür und warum wird Komplexität verwendet?
Die Komplexität eines Computerprogramms beschreibt, wie lange dieses Programm für die Durchführung braucht. Komplexität wird beispielsweise verwendet, um Algorithmen einen Wert zuzuteilen, der die Effizienz des Algorithmus’ bewertet. Diese Wertzuteilung macht man, da Computer unterschiedlich schnell sind, also verwendet man eine standardisierte Weise, um die Laufzeit zu bemessen.
Was sind die Landau-Symbole? Benenne und beschreibe diese.
Big-O: ist der “schlimmste” Fall, also das Maximum, was an Komplexität erreicht werden kann - ab n0 gilt, dass die Funktion immer unter der Big-O Schwelle liegt
Ω: entspricht dem Minimum, ab n0 gilt, dass die Funktion über der Ω-Schwelle liegt
θ: ist die Mischform aus Big-O und Omega - ab n0 ist die Funktion nach oben und nach unten hin gedeckelt
Was ist Rekursion? Nenne ein Beispiel, wo Rekursionen gut wären.
Eine Rekursion ist eine Funktion, die sich selbst wieder aufruft - dabei muss eine Abbruchbedingung enthalten sein, damit es nicht zu einem Infinite-Loop kommt –> ein Beispiel für eine Rekursion wäre die Fibonacci-Folge, wo sich die nächste Zahl immer aus der Summe der beiden Vorgänger berechnen lässt.
Datenstruktur: Was ist ein Stack?
Ein Stack basiert auf dem LIFO-Prinzip - last-in first-out, was so viel bedeutet wie, dass zuletzt eingefügte Elemente auch zuerst wieder vom Stack genommen werden.
Datenstruktur: Was ist ein Heap? Welche Varianten von Heap gibt es? Welche essentiellen Methoden werden zur Erhaltung der Heap-Eigenschaften verwendet?
Ein Heap basiert auf der Baum-Datenstruktur, wo Elemente abgespeichert werden - es gibt einen Min-Heap und einen Max-Heap. Beim Min-Heap ist die Wurzel des Baums das kleinste Element, wobei auch die Eltern eines Knoten immer kleiner gleich der Knoten selbst sind. Beim Max-Heap ist diese Reihenfolge umgekehrt, sodass die Wurzel des Max-Heaps immer die größte Zahl ist und die Elternknoten immer größer gleich der Kinder sind.
Methoden:
Min/Max-Heapify: stellt die Heap-Eigenschaften wieder her, indem größere / kleinere Schlüssel nach unten geschoben werden
ExtractMin/Max: nimmt kleinstes / größtes Element (Wurzel), platziert den letzten Knoten als neue Wurzel und führt dann Min/Max-Heapify aus
Decrease/IncreaseKey: Wenn der Elternknoten größer / kleiner ist, wird die Reihenfolge getauscht und das solange, bis die Heap-Eigenschaften wieder hergestellt sind
Einfügen: Neues Element ans Ende einfügen, dann Decrease/IncreaseKey ausführen
Datenstruktur: Was sind Listen? Was unterscheidet diese Datenstruktur von Arrays?
Listen sind eine Datenstruktur, die wie Arrays verwendet werden, nur mit einer Logik dahinter: Arrays haben eine fixe und nicht veränderbare Größe und liegen direkt hintereinander im Speicher, was das Anpassen der Arraygröße aufwändiger macht - Listen können beliebig größer und kleiner gemacht werden von der Länge und die Elemente liegen deswegen auch verteilt im Speicher.
Datenstruktur: Was ist eine verkettete Liste? Was ist eine doppelt verkettete Liste?
Eine verkettete Liste ist eine normale Liste, die zwei Pointer enthält: einen Head, der als Einstiegspunkt dient und einen Tail, der das letzte Element repräsentiert. Die einzelnen Elemente in einer verketteten Liste zeigen immer auf das jeweils darauffolgende Element.
Eine doppelt-verkettete Liste hat zusätzlich zur verketteten Liste noch die Eigenschaft, dass jedes Element einen Verweis auf den Vorgänger als auch Nachgänger hat, was das Löschen von Elementen in der Liste vereinfacht.
Algorithmus: Beschreibe den Insertion Sort Algorithmus. Welche Komplexität weist dieser auf?
Der Insertion-Sort Algorithmus basiert auf derselben Logik, wie das Einsortieren von Spielkarten. Man nimmt eine Karte vom Stapel und legt diese ganz rechts in die Kartenhand hin, man geht dann so lange nach links, bis man die richtige Position für die Karte gefunden hat. Das Element ganz links ist immer sortiert.
Komplexität: Big-O (n²)
Was ist ein Divide-and-Conquer Algorithmus?
Bei einem Divide-and-Conquer Algorithmus wird zuerst die Aufgabe aufgeteilt (Divide), über diese wird dann geherrscht (Conquer) und am Ende kommt dann oft noch der Combine-Step dazu, wo die aufgeteilten Aufgaben wieder zusammengefügt werden.
Algorithmus: Beschreibe den Merge Sort Algorithmus. Welche Komplexität weist dieser auf?
Der Merge-Sort Algorithmus gehört zu den Divide-and-Conquer Algorithmen
Divide: Teile Array in zwei gleich große Hälften (Index der Mitte wird dem Merge Sort übergeben)
Conquer: (Rekursion) führe Merge Sort auf beide Teilarrays aus
Combine: füge die Teilarrays wieder zusammen
DIe Abbruchbedingung für die Rekursion ist, wenn der linke Index größer gleich dem rechten Index ist, also wenn das Array nur mehr ein Element enthält.
Beim Mergen schaut man sich von den Teilarrays immer das Element an der linken Stelle an und vergleicht diese - ist das linkste Element von Array A kleiner als das linkste Element von Array B, so nimmt man das Element von Array A und erhöht den “Links-Pointer” um 1, dann macht man diesen Algorithmus weiter bis man alle Teilarrays durchgegangen ist und am Ende dann ein Sortiertes Array entsteht.
Komplexität: Big-O (n log n)
Algorithmus: Beschreibe den Quick Sort Algorithmus. Welche Komplexität weist dieser auf?
Der Quick-Sort Algorithmus gehört zu den Divide-and-Conquer Algorithmen.
Divide: Wähle Pivot und Teile Array anhand dessen in 2 - alles kleiner gleich Pivot ist im 1. Array, alles größer Pivot ist im 2. Array
Conquer: (Rekursion) führe Quick Sort auf beide Teilarrays aus
Combine: Nicht notwendig, da Teilarrays schon sortiert sind
Bei der Partitionierung geschieht folgendes: Das Pivot-Element startet immer an der rechten Stelle des Arrays, der pivot selbst ganz links bei left - 1. Wenn das Element, wo der Pivot derzeit ist, kleiner als das Pivot-Element ist, wird der pivot um 1 erhöht und die Elemente, wo die derzeitige Loop ist, ausgetauscht, bis man am Ende der Loop angelangt, wo man dann das Pivot-Element an die Stelle setzt, wo sich der Pivot gerade befindet.
Komplexität:
Best Case (Durchschnittsfall): Big-O (n log n)
Worst Case: Big-O (n²) - wenn die Liste schon sortiert ist
Datenstruktur: Was ist ein Baum? Welche Elemente beinhaltet dieser?
Ein Baum ist eine Datenstruktur für hierarchische Daten, dieser kann unendlich viele Kinder haben und beinhaltet folgende Elemente:
Wurzelknoten
Jeder Knoten hat Kinder
Beziehung zwischen Knoten werden über Kanten dargestellt
Knoten mit denselben Elternknoten werden Geschwister genannt
Knoten ohne Kinder sind Blätter
Höhe eines Baums entspricht der Anzahl der Ebenen
Mit welchem Algorithmus können Bäume traversiert werden? Beschreibe den Algorithmus kurz.
In-Order-Tree-Walk - bei diesem Algorithmus geht man rekursiv durch alle Kinder durch (zuerst links, beim Heraufgehen dann rechts), bis man einen Nullknoten erreicht (Abbruchbedingung)
Komplexität: Big-O (n)
Datenstruktur: Was ist ein Binärer Suchbaum?
Ein binärer Suchbaum ist ein Baum, wo die Knoten nur maximal zwei Kinder haben kann, ein linkes und ein rechtes Kind - wobei das linke Kind immer kleiner ist als der Schlüssel selbst und das rechte Kind größer gleich dem Knoten ist.
Wie funktioniert das Einfügen von Elementen in einem Binären Suchbaum?
Der Baum wird solange abgestiegen (mit Schlüssel-Checks für die Richtung), bis null gefunden wird (also ein leeres Kind), wo dann das neue Objekt (Key) erzeugt wird
Wie funktioniert das Löschen von Knoten in einem Binären Suchbaum?
Es wird der Nachfolger des zu-löschenden Elements ermittelt - wenn der Knoten einen rechten Teilbaum hat, ist der Nachfolger das Minimum von diesem Teilbaum, ansonsten wird solange aus dem Baum aufgestiegen, bis man aus einem linken Teilbaum kommt.
Beim Minimum wird der Baum so lange abgestiegen, bis ein Element gefunden worden ist, das keinen linken Teilbaum hat.
Beim Löschen kann es zu vier verschiedenen Fällen kommen:
1) Knoten hat keine Kinder - dann wird der Knoten einfach gelöscht
2) Knoten hat nur ein Kind - dann wird das Kind nach oben geschoben und der Knoten gelöscht
3) Knoten hat zwei Kinder, der Nachfolger ist das rechte Kind - Nachfolger wird an Stelle des gelöschten Knotens gesetzt
4) Knoten hat zwei Kinder, aber Nachfolger ist irgendwo im Teilbaum - der zu löschende Knoten und der linke Teilbaum werden aufgeteilt, Nachfolger wird an Stelle des zu löschenden Knotens gesetzt, Knoten wird gelöscht und Teilbaum wieder angehängt
Datenstruktur: Was ist ein AVL-Baum?
Ein binärer Suchbaum, der balanciert ist - der Höhenunterschied vom linken und rechten Teilbaum ist höchstens 1, ansonsten wird dieser rebalanciert an hand des Balancierungsfaktors
Was ist der große Vorteil von AVL-Bäumen?
Die Höhe des Baums ist immer auf Höhe von log n beschränkt (schnelle Operationen)
