/
Kartei Details
| Karten | 83 |
|---|---|
| Sprache | Deutsch |
| Kategorie | Informatik |
| Stufe | Universität |
| Erstellt / Aktualisiert | 19.01.2016 / 01.03.2016 |
| Weblink |
https://card2brain.ch/box/algorithmen_und_datenstrukturen_3_semester
|
| Einbinden |
<iframe src="https://card2brain.ch/box/algorithmen_und_datenstrukturen_3_semester/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
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).
Was ist unter Open Hashing und Closed Hashing zu verstehen?
Open Hashing:
- mehrere Schlüssel pro Zelle in der Hashtabelle
- Zelle = Kopf einer verketteten Liste aller auf sie abgebildeten Schlüssel
Closed Hashing:
- nur ein Schlüssel pro Zelle möglich, daher dürfen nicht mehr Schlüssel als Zellen existieren
- Suchen einer anderen Zelle bei Kollision (verschiedene Verfahren möglich, z.B. lineares Sondieren - nächste Zelle testen)
Was sind B-Bäume?
- Baum der Ordnung m >= 2
- Wurzel = Blatt oder Knoten mit 2 bis m Kindern
- alle anderen Knoten: zwischen m/2 (aufgerundet) und m Kinder
- vollständig balanciert
Wofür sind B-Bäume besonders geeignet?
B-Bäume sind besonders geeignet für die Suche auf Datenbeständen, die aufgrund ihrer Größe auf externen Speichermedien abgelegt werden müssen. Bei B-Bäumen werden pro Knoten relativ viele Schlüssel gespeichert, da dadurch die Knotenzahl und die Höhe des Baums stark sinken. Eine geringere Höhe bedeutet weniger (zeitlich sehr teure) Zugriffe auf externe Speichermedien. Da von externen Speichern typischerweise blockweise gelesen wird, erhöht die größere Schlüsselzahl pro Knoten nicht die Anzahl der notwendigen Zugriffe, solange ein Knoten noch in einen Block passt. Die Ordnung eines B-Baums (und damit die maximale Schlüsselzahl) wird daher meist so festgelegt, dass ein Block möglichst vollständig gefüllt wird.
