Datenstrukturen und Algorithmen
Algorithmen und Datenstrukturen vom dpunkt.verlag
Algorithmen und Datenstrukturen vom dpunkt.verlag
Set of flashcards Details
| Flashcards | 96 |
|---|---|
| Language | Deutsch |
| Category | Computer Science |
| Level | University |
| Created / Updated | 08.02.2015 / 12.10.2022 |
| Weblink |
https://card2brain.ch/box/datenstrukturen_und_algorithmen
|
| Embed |
<iframe src="https://card2brain.ch/box/datenstrukturen_und_algorithmen/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
Was ist Hashing?
Idee: Widerfinden von Objekten mittels eindeutigem Objektschlüssel
Grundprinzpien sind:
- Die Speicherung der Datensätze erfolgt in einme Feld mit Indexwerten von 0 bis N-1, wobei die einzelnen Positionen oft als "Buckets" bezeichnet werden.
- Eine Hashfunktion h bestimmt für ein Element e die Position h(e) im Feld.
- Die Funktion h sorgt für eine gute kollisionsfreie bzw. kollisionsarme Verteilung der zu speichernden Elemente.
Was ist Lineares Sondieren?
Da die Anzahl der Schlüssel im Hashverfahren begrenzt ist, werden notwendigerweise Schlüssel mehrfach besetzt. Das Lineare Sondieren versucht durch eine lineare Konstante eine Gleichverteilung zu erreichen, um eine "Entartung" des Hashs zu verhindern. Dabei wird T(h(e)) gerechnet (Objekt MOD #Schlüsselelemente) und falls der Schlüssel besetzt ist, nochmal um 1 inkrementiert, also T(h(e)+1) berechnet, bis man einen leeren Eintrag findet.
Es sind auch andere Konstanten als 1 zulässig. Dabei ist zu beachten, dass ggT von Konstante c und Tabellenlänge N = 1 ist.
Was ist quadratisches Sondieren?
Ähnlich wie beim Linearen Sondieren werden Quadratzahlen für die Sondierabstände benutzt, also {T(h(e)), T(h(e)+1), T(h(e))+4, T(h(e))+9, T(h(e))+16,...,T(h(e))+i²} berechnet.
Empfehlenswert ist die Wahl einer Primzahl für N, die modulo 4 den Rest 3 liefert, da die Sondierungsfolge alle Plätze der Hashtabelle erreicht.
Welche Anforderungen gibt es an eine Hashfunktion?
- Surjektivität: Jedes Element der Zielmenge muss erreicht werden
- Gleichverteiltheit: gute Streuung, sonst kommes es an bestimmten Stellen zu mehr Kollison als nötig
- Berechenbarkeit in konstanter Zeit
Was ist dynamisches Hashing?
Hashfunktion mit erweiterbarem Bildbereich.
Was ist die Levenshtein-Distanz?
Minimale Anzahl von Editierfunktionen, um einen String in einen anderen überzuführen.
Was ist ein invertierter Index?
Datenstruktur, die für eine Menge an Dokumenten, für jedes Wort speichert:
Anzahl Vorkommen, Dokument ID, evtl. Position
Was sind die Schaltregeln bei Petri-Netzen?
- Eine Transistion kann schalten (bzw. feuern), wenn jede Eingabestelle von t mindestens eine Marke enthält.
- Schaltet eine Transition, dann wird aus jeder Eingabestelle eine Marke entfernt und zu jeder Ausgabestelle eine Marke hinzugefügt.
- Bei Stellen mit Kapazitäten darf das Hinzufügen nicht die Kapazitätsbegrenzung verletzen
Erweiterung um gewichtete Kanten: bewegen mehrere Marken auf einmal.
Was ist ein Monitor?
Garantiert wechselseitigen Ausschluss durch Synchronisation Prozeduren mit kritischen Abschnitten werden als Monitor Operationen gekennzeichnet.
Metapher: Raum, in dem sich nur eine Person (ein Prozess) zur Zeit aufhalten kann. Weitere Personen müssen warten, bis der Raum wieder frei ist.
Was ist ein Semaphor?
Analogie mit mechanischen Eisenbahnsignalen: ein kritischer Gleisabschnitt darf nur von je einem Zug zur
Zeit befahren werden
Konstrukt zur Kontrolle des Zugriffs auf gemeinsame Ressourcen
Was sind Greedy-Algorithmen?
Greedy-Algorithmen (gierige Algorithmen) zeichnen sich dadurch aus, dass sie immer denjenigen Folgezustand auswählen, der zum Zeitpunkt der Wahl den größten Gewinn bzw. das beste Ergebnis verspricht
Was ist Divide-and-Conquer?
Rekursive Rückführung eines zu lösenden Problems auf ein identisches Problem mit kleinerer Eingabemenge
Was ist Backtracking?
Teillösung werden schrittweise zu einer Gesamtlösung ausgebaut
• Falls Teillösung nicht zu einer Lösung führt…
• … letzten Schritt bzw. letzte Schritte zurücknehmen und alternative Wege probieren
Was ist Dynamische Programmierung?
Bei der dynamischen Programmierung werden kleinere Teilprobleme zuerst gelöst, um aus diesen größere Teillösungen zusammenzusetzen.
Was sind die Nachteile der Dynamischen Programmierung?
Nicht immer ist es möglich, die Lösungen kleinerer Probleme so zu kombinieren, dass sich die Lösung eines größeren Problems ergibt.
Die Anzahl der zu lösenden Probleme kann unvertretbar groß werden
- zu viele Teillösungen, die dann doch nicht benötigt werden
- Gewinn durch Wiederverwendung zu gering da Lösungszweige disjunkt
Formel für Multiplikatives Verfahren beim Hashing?
\(h(x)= N \cdot (k \cdot z - \lfloor k \cdot z \rfloor\) mit N ist Anzahl der Hashingschlüssel und k ist Element das eingefügt werden soll und z eine irrationale Zahl (in der Regel der Goldene Schnitt: 0,362)
