/
-
- 1 / 83
-
Cartes-fiches
Welche Aussagen über die Ordnung einiger wichtiger Wachstumsfunktionen stimmen?
Was ist das allgemeine Vorgehen bei der Laufzeitanalyse?
- Identifizierung des Parameters n, der die Eingabegröße darstellt
- Basisoperation ermitteln
- best, worst und average case für Eingabe der Größe n bestimmen
- Erstellung einer Summenformel für die Ausführungsanzahl der Basisoperation
- Vereinfachung der Summenformel (Regeln und Formeln nutzen)
Was ist der Brute Force-Ansatz?
- relativ schlichter Ansatz, direkt auf Problembeschreibung und Definition der beteiligten Konzepte basierend
- "mit Kanonen auf Spatzen schießen"
Welche Vor- und Nachteile bringt der Brute-Force-Ansatz mit sich?
Vorteile:
- breites Einsatzfeld
- einfach zu entwerfen
- Vergleichsmaßstab für komplexere Algorithmen
Nachteile:
- liefert selten den effizientesten Algorithmus
- für einige Probleme unakzeptabel langsam
Wie läuft Selectionsort ab?
a[0] wird im ersten Durchlauf mit den folgenden Elementen eines Arrays verglichen. Sobald sich ein kleineres Element findet, vergleicht man die folgenden Elemente mit diesem. Hat sich am Ende des Arrays kein kleineres Element gefunden, wird das in einer Variablen gespeicherte Element an die erste Stelle gesetzt.
Das kleinste Element des nächsten Durchlaufs wird dann entsprechend an die zweite Stelle gesetzt - anders ausgedrückt: das im unsortierten Arrayteil gefundene kleinste Element wird immer an die letzte Position des sortierten Arrayteils gesetzt.
Wie läuft Bubblesort ab?
Das erste Element des unsortierten Arrayteils wird mit allen folgenden Elementen verglichen und gegebenenfalls getauscht, wenn es größer als eins dieser Elemente sein sollte. Damit steigen die jeweils größten Elemente jedes Durchlaufs wie Blasen zum Ende des Arrays auf.
Was versteht man unter einer erschöpfenden Suche?
Suche nach einem Element mit speziellen Eigenschaften aus einer kombinatorischen Menge von Objekten
Methode:
- systematische Generierung aller in Frage kommenden Elemente
- Betrachten aller potentiellen Lösungen nacheinander: Verwerfen ungültiger Lösungen, bisher beste gültige Lösung merken
- Lösung(en) ausgeben
Hoher Zeitaufwand, daher nur für sehr kleine Problemgrößen anwendbar.
Beschreiben Sie die Tiefensuche / Depth-First-Search (DFS).
Besuch aller Graphen-Knoten:
- kommt man bei einem Knoten mit einem unbesuchten Nachbarn vorbei, geht man zunächst zu diesem weiter - hat der ebenfalls unbesuchte Nachbarn, geht man gleich zu einem von denen, usw.
- backtracking: sind alle Nachbarn eines Knoten besucht, geht man zum Knoten davor zurück
- Nutzung eines Stacks: Ein Knoten wird auf den Stack gepackt, wenn er das erste mal besucht wird und wieder heruntergenommen, sobald man alle Nachbarn von ihm besucht hat
Beschreiben Sie die Breitensuche / Breadth-First-Suche (BFS).
Besuch aller Graphen-Knoten:
- Abarbeitung aller unbesuchten Nachbarn des aktuellen Knotens, anschließend gleiches Verfahren mit den Nachbarn der nun bekannten Nachbar-Knoten
Nutzung einer Queue:
- Einreihung eines Knotens in die Queue, sobald er das erste mal entdeckt wird und Löschen des Knotens aus der Queue, sobald alle seine Nachbarn überprüft wurden
Welche Knotenordnungen entstehen bei der DFS bzw, der BFS?
DFS: zwei Knotenordnungen, eine Einfüge-Ordnung auf den Stack und eine Lösch-Ordnung vom Stack
BFS: eine Knotenordnung, da Einfüge- und Lösch-Ordnung in der Queue identisch sind
Was besagt die Decrease-and-Conquer-Strategie?
- Reduzierung des Problems auf ein kleineres, gleichartiges Problem
- Lösen des kleineren Problems durch bottom-up oder top-down-Ansatz
- Erweitern der gefundenen Lösung zur Lösung für das größere Problem
Welche 3 Typen der Decrease-and-Conquer-Strategie gibt es?
- Reduktion des Problems um Konstante (z.B. Insertionsort)
- Reduktion um konstanten Faktor (z.B. binäre Suche)
- Reduktion um variable Größe (z.B. euklidischer Algorithmus)
Wie läuft Insertionsort ab?
bottom up: Man nimmt sich das erste Element eines Arrays. Dieses ist für sich allein schon sortiert, weshalb man anschließend das nächste Element nimmt und dieses entsprechend vor oder hinter dem ersten Element einsortiert. Ebenso wird mit den nächsten Elementen verfahren, bis das gesamte Array sortiert ist.
Was ist ein DAG?
Directed Acyclic Graph: gerichteter Graph ohne Zyklen, zur Modellierung von Problemen mit Abhängigkeiten/Vorbedingungen
Was meint topologisches Sortieren?
lineare Anordnung der Knoten, sodass die Startknoten aller Kanten vor den jeweiligen Endknoten liegen
topologisches Sortieren bei einem DAG möglich
- bei einer Tiefensuche entspricht umgekehrte Löschreihenfolge vom Stack der topologischen Sortierung
- bei einer Breitensuche ist Einordnungsreihenfolge in Queue eine Lösung
Wie läuft die binäre Suche ab?
- Voraussetzung: sortiertes Array
- mittlerer Eintrag wird mit Suchschlüssel verglichen, ist der Eintrag kleiner als der Suchschlüssel, wird entsprechend mit dem mittleren Eintrag der rechten Hälfte fortgefahren, andernfalls mit der linken Hälfte
- dies wird gemacht, solange der Schlüssel nicht gefunden wurde bzw. bis keine Halbierung des Suchraums mehr möglich ist
Was besagt die Divide-and-Conquer-Strategie?
- Teilung des gegebenen Problems in mehrere kleine, gleichartige Problem-Exemplare
- rekursives Lösen der kleineren Problem-Exemplare
- Kombination der Lösungen für die kleinen Problem-Exemplare zur Lösung des großen Problems
Wie funktioniert Mergesort?
- Teilung eines Arrays A in zwei gleichgroße Arrays B und C durch Kopieren der einen Hälfte der Elemente in B und der anderen Hälfte in C
- Rekursion: gleiches Verfahren mit B und C, bis die Arrays nur noch je ein Element enthalten (in der Implementierung ist es auch schon bottom-up möglich)
- Sortieren der Arrays, indem die Elemente von je zwei Arrays miteinander verglichen und entsprechend in ein gemeinsames Array sortiert werden (aus je zwei Arrays mit einem Element wird dann ein Array mit 2 Elementen)
- die nun entstandenen Arrays werden auch jeweils in Paaren sortiert, indem jeweils die vorderen Elemente miteinander verglichen und in der richtigen Sortierung in ein neues Array gespeichert werden
- Wiederholung, bis das ursprüngliche Array sortiert wurde
Was sind die Vorteile von Mergesort?
- kein wahlfreier Zugriff nötig
- gut geeignet zur Sortierung verketteter Listen
- gut geeignet zur Sortierung von Daten auf externen Speichermedien
Wie funktioniert Quicksort?
- Wahl eines Pivotelementes p (Partitionselement), z.B. das erste Element
- Verschiebung der restlichen Elemente, sodass alle größeren Elemente rechts von p stehen und alle kleineren Elemente links von p
- Tausch des Pivotelementes mit dem letzten Element der linken Seite --> Pivotelement hat nun schon richtige Position im Array
- rekursive Bearbeitung der beiden Unterarrays (Wahl neuer Pivotelemente)
Welche Schritte beinhaltet das Partitioning nach Hoare (Quicksort)?
- Pivotelement = erstes Element eines Arrays
- Nutzung von 2 Zählvariablen l und r: l durchläuft die Arrayelemente von links (Beginn: Pivotelement) und r von rechts (Beginn: Index außerhalb des Arrays)
- Schleife: l wird solange um 1 erhöht, bis man auf ein Element trifft, das größer gleich dem Pivotelement ist (erst erhöhen, dann Überprüfung)
- Schleife: r wird solange um 1 erniedrigt, bis man auf ein Element trifft, das kleiner gleich dem Pivotelement ist
- die beiden gefundenen Elemente werden getauscht
- Wiederholung der Schritte, bis l größer gleich r ist
- da Schleifenabbruchbedingung erst am Ende der Schleife überprüft wird, findet ein falscher Swap statt --> der wird nach Abbruch der Schleife wieder zurückgetauscht
- das Pivotelement wird dann mit dem Element getauscht, dass sich an der Position von r befindet (äußerstes Element der linken Seite)
Was besagt das Master-Theorem für
T(n) = a·T(n/b) + f(n) mit f(n) e Groß-Theta(nd) ?
a < bd, dann T(n) e Groß-Theta(nd)
a = bd, dann T(n) e Groß-Theta(nd * log n)
a > bd, dann T(n) e Groß-Theta(nlogb a)
Ebenso für Groß-O
Welche 3 Varianten gibt es bei Transform-and-Conquer?
Vereinfachung: Transformation in einfachere Form desselben Problems
Änderung der Darstellung
Problemreduktion: Transformation in anderen Problemtyp mit bereits bekannten algorithmischen Lösungen
Nennen Sie Beispiele für Probleme, bei denen mit Listen gearbeitet wird und die einfacher werden, wenn die Listen sortiert sind.
- Medianbestimmung
- Unterschiedlichkeit der Elemente
- Suche in Listen
Wie werden bei binären Suchbäumen Schlüssel gelöscht?
Blatt: direktes Löschen
Knoten mit einem Nachfolger: Nachfolger mit Vorgänger verbinden, Schlüssel löschen
Knoten mit zwei Nachfolgern: Schlüssel aus Knoten löschen, Schlüssel des Ordnungsnachfolgers / -vorgängers in Knoten eintragen und dessen Knoten löschen (Ordnungsvorgänger: nächstkleinster Wert, Knoten am rechten Ast der linken Seite - Ordnungsnachfolger: nächstgrößter Wert, Knoten am linken Ast der rechten Seite)
Wie werden bei binären Suchbäumen Schlüssel gelöscht?
Blatt: direktes Löschen
Knoten mit einem Nachfolger: Nachfolger mit Vorgänger verbinden, Schlüssel löschen
Knoten mit zwei Nachfolgern: Schlüssel aus Knoten löschen, Schlüssel des Ordnungsnachfolgers / -vorgängers in Knoten eintragen und dessen Knoten löschen (Ordnungsvorgänger: nächstkleinster Wert, Knoten am rechten Ast der linken Seite - Ordnungsnachfolger: nächstgrößter Wert, Knoten am linken Ast der rechten Seite)
Der Worst-Case bei binären Suchbäumen ist ein linearer Baum, also maximale Unausgeglichenheit. Welche Möglichkeiten gibt es, einen balancierten Suchbaum zu schaffen?
AVL-Bäume, Rot-Schwarz-Bäume --> Rebalancieren eines Baumes
2-3-Bäume / 2-3-4-Bäume, B-Bäume --> mehr als einen Schlüssel pro Knoten erlauben
Was gilt für AVL-Bäume?
Höhe des linken Unterbaumes - Höhe des rechten Unterbaumes <= 1 (Betrag)
Was gilt für Rotationen?
- Rotation des Unterbaumes mit dem unbalancierten Knoten als Wurzel, der den eingefügten Blatt am nächsten ist
- v = unterster unausbalancierter Knoten (Knoten, bei dem Differenz größer 1 steht)
- Linksrotation, wenn neues Element im rechten Teilbaum von v eingefügt wurde
- Rechtsrotation, wenn neues Element im linken Teilbaum von v eingefügt wurde
- Links-Rechts-Rotation, wenn neues Element im "mittleren" Teilbaum von v eingefügt wurde, also im rechten Ast des linken Teilbaumes (analog Rechts-Links-Rotation)
Was ist ein 2-3-Baum?
- Suchbaum
- besitzt 2 oder 3 Kinder je Knoten (bei 3 Kinder sind 2 Schlüssel im Knoten, Schlüssel des mittleren Astes befinden sich zwischen den beiden Schlüsselwerten)
- vollständig höhenbalanciert (alle Blätter auf einer Ebene)
Wie wird in 2-3-Bäume einsortiert?
- "2-3-Bäume wachsen an der Wurzel" --> Wurzel wird sozusagen nach oben gedrückt
- Einfügen immer in bereits bestehende Blätter
- sobald Blatt drei Schlüssel enthält, wird mittlerer Schlüssel nach oben gedrückt und die beiden anderen Schlüssel werden in zwei einzelne Knoten aufgespalten und erhalten mittleres Element als Elternknoten
Was ist ein Heap?
- Binärbaum mit einem Schlüssel pro Knoten
- Vollständigkeit: alle Ebenen vollständig gefüllt, nur in der letzten Ebene dürfen Knoten fehlen (dann aber nur rechts, es wird immer von links aufgefüllt)
- Teilgeordnet: Jeder Knotenschlüssel ist bei einem Max-Heap größer gleich den Schlüsseln seiner Kinder, bei einem Min-Heap entsprechend kleiner gleich (Schlüssel von oben nach unten sortiert, nicht von links nach rechts)
Wie berechnet sich die Höhe h eines Heaps mit n Schlüsseln?
h = log2 n (abgerundet)
Was lässt sich zu der Position von Schlüsseln in der Array-Repräsentation eines Heaps sagen?
linkes Kind eines Schlüssels an Position j: Position 2j
rechtes Kind von j: 2j + 1
Elternknoten von j: Position j/2 (abgerundet)
Elternknoten belegen die ersten n/2 (abgerundet) Positionen
Wie wird ein Heap konstruiert?
- Wahl des letzten Elternknotens (unten rechts)
- Heap-Eigenschaft für Teilbaum ab diesem Elternknoten herstellen
- Wiederholung des Schrittes für die vorherigen Elternknoten
Wann ist das Vorgehen der Problemreduktion bei Transform-and-Conquer-Algorithmen sinnvoll?
Aufwand für Transformation + Aufwand zur Lösung des anderen Problems < Aufwand zur Lösung des originalen Problems
Was meint Space/Time-Tradeoff und welche Varianten gibt es?
Nutzung von zusätzlichem Speicherplatz zur Verbesserung der Laufzeit
- Eingabeerweiterung: Vorverarbeitung der Eingabe zur Ermittlung von Informationen, mit denen das Problem später effizienter gelöst werden kann
- Vorstrukturierung: Vorverarbeitung der Eingabe, um später schneller auf die Eingabeelemente zugreifen zu können
Wie funktioniert Counting Sort?
Es wird für jedes Arrayelement gezählt, wie viele Elemente kleiner sind als das jeweilige Element. Die ermittelte Anzahl wird in ein zweites Array geschrieben, sodass die Position eines Elementes mit der Position der ermittelten Anzahl übereinstimmt. Mittels der Anzahl wird das Array dann aufsteigend sortiert. Das kleinste Element hat 0 Elemente, die kleiner sind und wird damit an Arrayindex 0 gesetzt. Das zweitkleinste Elemente hat ein kleineres Element und kommt damit an den Index 1.
Wie funktioniert der Horspool-Algorithmus?
Beim Zeichenketten-Vergleich wird jedes Zeichen des Suchmusters mit einem Zeichen des Textes verglichen. Sobald ein Dismatch auftritt, wird das Suchmuster verschoben und das Vergleichen wird erneut begonnen. Der Horspool-Algorithmus verschiebt das Suchmuster jedoch nicht jedes Mal um 1. Wenn der Dismatch durch ein Zeichen im Text auftrat, der im Suchmuster gar nicht auftritt, kann das Suchmuster gleich um die Suchmusterlänge verschoben werden, da das Zeichen sonst immer zu einem Dismatch führen würde. Existiert das Zeichen im Suchmuster, wird dieses um die am weitesten rechts befindliche Position des Zeichens im Suchmuster verschoben. Dafür wird zu Beginn eine Shift-Tabelle angelegt, in der für jedes Zeichen des Suchmusters die Position des ersten Vorkommens von rechts angegeben wird.
Was ist die Grundidee einer Hashfunktion?
Abbildung der n Schlüssel einer potenziell sehr großen Schlüsselmenge K mittels einer Hashfunktion auf eine Hashtabelle der Größe m
Bsp: h(k) = k mod m
Es ist also möglich, dass 2 Schlüssel auf die gleiche Position abgebildet werden (Kollision).
