Was versteht man unter Traversierung in der Informatik?
Traversierung ist in der Graphentheorie der Name für Verfahren, die eine Route bestimmen,
bei der jeder Knoten und jede Kante eines Graphen genau einmal besucht wird.
Wie funktioniert das In-Order-Verfahren zur Traversierung eines Baums?
Und wie wird es noch bezeichnet?
Hierbei wird ein Binärbaum derart durchlaufen, dass zunächst von den äußersten Blättern des linken Teils eines Baums ausgehend in Richtung Wurzel alle Knoten ausgegeben werden, anschließend die Wurzel selbst, gefolgt von allen Knoten des rechten Teilbaums, ebenfalls wieder ausgehend von den äußersten Blättern.
als symmetrische Reihenfolge oder
In-Order bezeichnet
Zunächst beginnen wir mit dem linken Teilbaum und durchlaufen ihn von den Blättern hin zur Wurzel. Dies führt zur Ausgabe der Knoten mit den Nummern 7 und 11. Der rechte Ast des linken Teilbaums wird nach dem gleichen Prinzip durchlaufen, sodass wir weiter 2 und 14 erhalten. Nun, da wir den linken Teilbaum vollständig abgearbeitet haben, geben wir die Wurzel mit der Knotennummer 17 aus. Im Anschluss wird der rechte Teilbaum durchlaufen und wir erhalten Knotennummer 12 als Ausgabe. Insgesamt können wir die Reihenfolge der Ausgabe also wie folgt zusammenfassen: 7, 11, 2, 14, 17, 12.
Eine weitere Möglichkeit, einen Baum zu durchlaufen, ergibt sich durch die Hauptreihenfolge, welche auch als „Pre-Order“ bezeichnet wird.
Wie funktioniert dabei das Grundprinzip?
Das Grundprinzip ist es hierbei, zunächst die Wurzel auszugeben, gefolgt von den Knoten des linken Teilbaums. Zuletzt wird der rechte Teilbaum durchlaufen, in diesem Szenario jedoch von der Wurzel hin zu den Blättern ausgehend. Betrachten wir dies wieder anhand von Abbildung 4.1, so erhalten wir zunächst als Ausgabe 17, gefolgt von 11 und 7 (linker Ast des linken Teilbaums), gefolgt von 14 und 2 (rechter Ast des linken Teilbaums). Zuletzt wird noch 12 ausgegeben als Vertreter des rechten Teilbaums. Zusammenfassend können wir die Ausgabe wie folgt zusammenfassen: 17, 11, 7, 14, 2, 12.
Ebenso können wir einen Baum gemäß der Nebenreihenfolge durchlaufen, was auch als „Post-Order“ bezeichnet wird.
Wie funktioniert diese?
Hierbei wird zunächst der linke Teilbaum durchlaufen, gefolgt vom rechten Teilbaum (je beginnend von den äußersten Blättern). Zuletzt erfolgt die Ausgabe der Wurzel des Baums. Wir betrachten diese Traversierungsreihenfolge wieder anhand des Baums, dargestellt in Abbildung 4.1. Zunächst erfolgt die Abarbeitung von des linken Teilbaums, beginnend links, also 7 und 11 gefolgt von 2 und 14. Im Anschluss erfolgt die Ausgabe des rechten Teilbaums, in diesem Fall 12. Zuletzt erfolgt die Ausgabe der Wurzel 17. Zusammenfassend können wir die Reihenfolge beim Durchlaufen des Baums wie folgt zusammenfassen: 7, 2, 14, 11, 12, 17.
Eine weitere Möglichkeit, einen Baum zu durchlaufen, bietet sich durch die Level-Order-Methode.
Eine weitere Möglichkeit, einen Baum zu durchlaufen, bietet sich durch die Level-Order-Methode, bei der jeweils eine Ebene, mit den Wurzeln zuerst, komplett durchlaufen wird, gefolgt von der Ebene darunter. Angewandt auf Abbildung 4.1 erhalten wir als Ausgabe so zunächst die Wurzel 17, gefolgt von 11 und 12. Die Betrachtung der nächst tieferen Ebene des Baums führt zur Ausgabe von 7 und 14 sowie zuletzt von 2. Die Reihenfolge des Besuchens der Knoten lässt sich somit als 17, 11, 12, 7, 14, 2 zusammenfassen.
j
Was können Sie mithilfe des Dijkstra-Algorithmus erreichen? Wo könnte dieser Algorithmus eine Praxisanwendung finden?
Mithilfe des Dijkstra-Algorithmus ist es möglich, einen kürzesten Pfad durch einen Graphen zu finden. Eine Praxisanwendung für diesen Algorithmus könnte z. B. im Bereich der Navigation zu finden sein, indem Verkehrsstraßen als Kanten eines Graphen modelliert werden und Knoten Städte repräsentieren.
Sortieren durch Auswahl.
Wie funktioniert dieser und was ist der Nachteil?
Mittels selection sort, also Sortieren durch Auswahl, wird eine ungeordnete Liste dadurch sortiert, dass das i-kleinste Element (i = 1,..., n – 1) entnommen und an die richtige Position der aufsteigenden Liste gesetzt wird.
Hier ist, wie es funktioniert:
Gehe die Liste durch und suche nach dem kleinsten Element.
Sobald du das kleinste Element gefunden hast, tausche es mit dem Element an der ersten Stelle in der Liste.
Dann gehe zur nächsten Position in der Liste und suche das kleinste Element im verbleibenden Teil der Liste.
Tausche das kleinste Element mit dem Element an der zweiten Stelle in der Liste.
Fahre so fort, bis die gesamte Liste sortiert ist.
Dieser Algorithmus ist also relativ leicht umzusetzen, im Vergleich zu anderen Sortieralgorithmen aber sehr ineffizient.
Ein weiterer häufig verwendeter Sortieralgorithmus ist das Sortieren durch Einfügen.
Beschreibe seine funktionisweise.
Hier ist eine einfache Erklärung anhand eines Beispiels:
Du beginnst mit einem Stapel von unsortierten Karten (oder Zahlen in einer Liste).
Nimm die erste Karte und betrachte sie als "sortierten" Teil deiner Hand.
Nimm die nächste Karte aus dem unsortierten Teil und füge sie in den sortierten Teil ein, indem du sie an der richtigen Stelle platzierst.
Wiederhole diesen Vorgang, bis alle Karten in die sortierte Reihenfolge eingeordnet sind.
Das Verfahren Quick Sort wurde 1962 von C. Hoare vorgestellt und erhielt seinen Namen dadurch, dass es als das schnellste interne Sortierverfahren gilt. Es basiert auf einer Divide-and-Conquer-Strategie.
Wie funktioniert dies?
Hier ist eine einfache Erklärung:
Wähle ein Element aus der Liste als Pivot. Dies könnte zum Beispiel die erste oder die letzte Karte in deinem Stapel sein.
Teile die Liste in zwei Teile: Alle Elemente, die kleiner oder gleich dem Pivot sind, kommen in den ersten Stapel, und alle Elemente, die größer als der Pivot sind, kommen in den zweiten Stapel.
Sortiere jeden der beiden Stapel separat, indem du den Quick Sort Algorithmus auf sie anwendest (rekursiv).
Füge die sortierten Stapel wieder zusammen, wobei der Pivot in der Mitte steht: Erst der sortierte Teil mit Elementen kleiner als der Pivot, dann der Pivot selbst, und dann der sortierte Teil mit Elementen größer als der Pivot.
Dieser Prozess wird fortgesetzt, bis alle Teilstapel sortiert sind und die gesamte Liste sortiert ist.
Ein weiteres Sortierverfahren stellt Bubble Sort dar. Es basiert auf der Idee, die Vertauschungen beim Sortieren auf lediglich unmittelbar benachbarte Elemente einer Liste zu beschränken.
Stell es dir wie das Sortieren von Blasen in einem Getränk vor, wo die größeren Blasen nach oben steigen und die kleineren Blasen nach unten sinken.
Beginne am Anfang der Liste und vergleiche jedes Element paarweise mit seinem Nachbarn.
Wenn das aktuelle Element größer ist als sein Nachbar, tausche sie aus.
Fahre fort, die Liste zu durchlaufen und die Elemente paarweise zu vergleichen und gegebenenfalls zu tauschen.
Wiederhole diesen Vorgang, bis keine Vertauschungen mehr erforderlich sind.
Ineffizient für große Listen, da er viele Durchläufe benötigen kann, um die Liste vollständig zu sortieren.
Die einfachste Möglichkeit, eine Suche auszuführen, welche auch keine tiefergehende Kenntnis oder Vorraussetzungen bezüglich der zu durchsuchenden Menge erfordert, ist die sequenzielle bzw. lineare Suche.
Hierbei werden die vorliegenden Daten schlicht systematisch von vorn nach hinten durchlaufen
und die Werte jeweils mit dem aufzufindenden Wert verglichen.
Im Gegensatz zur sequenziellen Suche, die für beliebige unsortierte Listen funktioniert, benötigt die binäre Suche eine sortierte Liste als Startpunkt. Sie basiert auf einem Divide-and-Conquer-Ansatz, bei dem die zu durchsuchende Liste zunächst in zwei Teile aufgeteilt und anschließend nur der relevante Teil weiter durchsucht wird.
Gebe ein Beispiel und beschreibe die Funktionsweise dieses Algorithmus.
Die Binäre Suche ist ein effizienter Algorithmus, um in einer sortierten Liste oder einem sortierten Array nach einem bestimmten Element zu suchen. Stell es dir wie das Suchen nach einem Wort in einem Lexikon vor, indem du immer in der Mitte des Lexikons beginnst und dann entscheidest, ob du im ersten oder zweiten Teil weitersuchen musst.
Beginne mit einer sortierten Liste von Elementen.
Bestimme das mittlere Element der Liste.
Vergleiche das gesuchte Element mit dem mittleren Element.
Wenn das gesuchte Element gleich dem mittleren Element ist, ist die Suche beendet.
Wenn das gesuchte Element kleiner als das mittlere Element ist, suche im ersten (linken) Teil der Liste weiter.
Wenn das gesuchte Element größer als das mittlere Element ist, suche im zweiten (rechten) Teil der Liste weiter.
Wiederhole diesen Prozess, bis das gesuchte Element gefunden wird oder festgestellt wird, dass es nicht in der Liste vorhanden ist.
Die Binäre Suche reduziert die Suchzeit exponentiell, da sie jedes Mal die Liste halbiert, in der das Element gesucht wird. Dadurch ist sie besonders effizient für große sortierte Listen oder Arrays.
Die Fibonacci-Suche verfolgt ein ähnliches Vorgehen wie die binäre Suche,
teilt jedoch die zu durchsuchende Liste nicht strikt mittig in zwei gleich große Teillisten.
Es erfolgt keine ganzzahlige Division, sondern eine Unterteilung der Liste gemäß der
Fibonacci-Zahlenfolge
Beim String Matching wird ganz allgemein versucht, ein sogenanntes „Muster“ in einer Zeichenkette bzw. einem Text wiederzufinden. Es erweitert somit die reine Suche nach einer Zahl oder einem Buchstaben in einer Zeichenkette auf die nach Textabschnitten.
Bennene hierzu 3 bekannte Verfahren.
Naives Verfahren
Verfahren von Knuth-Morris-Pratt
Verfahren von Boyer-Moore
Beschreibe die Funktionsweise des Naiven Verfahrens.
Des weiteren ist das naive Verfahren gedächtnislos.
Was bedeutet dies konkret?
Beginne am Anfang der Liste.
Überprüfe jedes Element nacheinander, beginnend mit dem ersten Element, ob es das gesuchte Element ist.
Wenn das gesuchte Element gefunden wird, beende die Suche.
Wenn das gesuchte Element nicht gefunden wird, gehe zum nächsten Element und wiederhole den Prozess.
Fahre fort, bis das gesuchte Element gefunden wird oder alle Elemente in der Liste überprüft wurden.
Dies bedeutet, dass gegebenenfalls dieselbe Textstelle mehrmals verglichen wird, da sich das Verfahren nicht merkt, welche Zeichen des Textes mit dem zu vergleichenden Muster bereits übereingestimmt haben.
Während das naive Verfahren des String Matching noch gedächtnislos war, wird diese Einschränkung durch das Verfahren von Knuth-Morris-Pratt verbessert.
Wo wird dieser Algorithmus angewendet und wie funktioniert dieser?
Es ist besonders nützlich, wenn das Muster mehrfach im Text vorkommen kann oder wenn man nach dem ersten Vorkommen weitersuchen möchte, anstatt nach allen Vorkommen zu suchen und zu zählen.
Zum Suchen von Mustern in Texten
und wird in vielen Anwendungen wie der Textsuche in Dateien,
der Syntaxhervorhebung und der DNA-Analyse verwendet.
Zuerst wird eine Tabelle erstellt, die angibt, wie weit man das Muster bei einem Mismatch verschieben kann, ohne bereits abgeglichene Zeichen erneut zu überprüfen. Diese Tabelle wird als "Failure Function" oder "Failure Array" bezeichnet.
Dann beginnt man den Text von links nach rechts und vergleicht das Muster mit dem Text.
Wenn ein Zeichen des Musters nicht mit dem entsprechenden Zeichen im Text übereinstimmt, verwendet man die Failure Function, um zu bestimmen, wie weit man das Muster relativ zum Text verschieben kann, ohne bereits verglichene Zeichen erneut zu überprüfen.
Man verschiebt das Muster entsprechend und setzt den Vergleich fort.
Wie funktioniert dieser Algorithmus?
Das Verfahren von Boyer-Moore vergleicht einen Referenztext mit einem vorliegenden Muster nicht mehr von links nach rechts, sondern nun von rechts nach links.
Der Zeichenvergleich findet bei dieser Methode also beginnend beim letzten Zeichen des Musters statt.
Tritt hier ein Mismatch auf, so wird das Muster um so viele Zeichen nach rechts verschoben, bis wieder ein Match gefunden werden kann.
Welche Heuristik nutzt das Boyer-Moore-Verfahren?
Das Boyer-Moore-Verfahren nutzt eine sogenannten „Match-Heuristik“.
Wenn ein Mismatch zwischen dem Muster und dem Text auftritt und das Muster bereits eine Übereinstimmung auf der rechten Seite hat, sucht die Match-Heuristik nach einer Teilübereinstimmung innerhalb des Musters.
Die Idee ist, dass, wenn ein Teil des Musters bereits im Text übereinstimmt und ein Mismatch auftritt, man das Muster so verschieben kann, dass dieser Teil des Musters mit dem übereinstimmenden Teil im Text ausgerichtet ist.
Durch Ausrichten der übereinstimmenden Teile des Musters und des Textes kann die Match-Heuristik die Verschiebung des Musters bestimmen, um eine erneute Überprüfung bereits verglichener Zeichen zu vermeiden und effizienter nach dem gesuchten Muster zu suchen.
Wo werden Hash-Funktionen eingesetzt?
Hash-Funktionen können zum berechnen eines Speicherorts genuzt werden.
in der Kryptografie als Prüfsumme verwendet werden.
Was ist die Grundidee beim abspeichern von Werten im Hashing?
Wie erleichtern uns die Suche, indem wir Werte nicht irgendwo abspeichern sondern an einer berechneten Adresse.
Um den wert K zu finden muss man ihn an der Adresse suchen wo er abgespeichert wurde.
Welche beiden Methoden nutzen Hash-Funktionen?
/
*
Eine vergleichsweise simple Methode zur Erzeugung eines Hash-Wertes ist die Divisions-Rest-Methode,
welche als Ausgabe den Rest vom Schlüssel k bei einer ganzzahligen Division durch m zur Folge hat
Der jeweilige Schlüssel wird mit einer irrationalen Zahl multipliziert und anschließend der ganzzahlige Anteil abgeschnitten.
Für verschiedene Schlüssel folgen so unterschiedliche Werte zwischen 0 und 1.
Was bedeutet Sondieren?
Sondieren bezeichnet das Berechnen eines nächsten möglichen Speicherorts, wenn der Eigentliche berechnete Ort schon belegt ist.
Benenne die gängigsten Sondierungs-Funktionen.
Lineares Sondieren:
Eine Hash-Funktion der Form h(k) = k mod m an, mit m = 7
Schlüssel 12, 53, 5, 14, 2, 19 in eine Hash-Tabelle einfügen.
Quadratisches Sondieren:
Wenn du eine Hash-Tabelle hast und zwei oder mehr Elemente denselben Hash-Wert haben, tritt eine Kollision auf. Das quadratische Sondieren ist eine Technik, um mit solchen Kollisionen umzugehen und einen freien Platz in der Tabelle zu finden, um das neue Element einzufügen.
Wie funktioniert das Quadtarische Sondieren?
Wenn du ein neues Element in die Hash-Tabelle einfügst und feststellst, dass der zugewiesene Speicherplatz bereits von einem anderen Element belegt ist (eine Kollision auftritt), versuchst du einen anderen Platz in der Tabelle zu finden.
Anstatt einfach den nächsten freien Platz zu suchen, versuchst du, einen Platz zu finden, der eine quadratische Anzahl von Schritten vom ursprünglichen Platz entfernt ist.
Du versuchst also, 1212 Schritte, dann 2222 Schritte, dann 3232 Schritte usw. vom ursprünglichen Platz entfernt zu suchen, bis ein freier Platz gefunden wird.
Wenn du einen freien Platz findest, fügst du das neue Element dort ein.
In welche 2 Hashmethoden wird das Dynamische Hashing unterteilt?
Lineares Hashing:
In den einzelnen Tabellenfächern werden keine einzelnen Elemente, sondern Listen von Elementen abgelegt.
Wird ein Element an einer schon belegten Adresse abgespeichert,
wird es an die entsprechende Liste angehängt.
Virtuelles Hashing:
Bei Überlauf: Erstelle neuen Block der selben größe und verteile die vorhandenen Elemente auf beide Blöcke
Wo dieser neue Block angelegt wird erfordert wiederum das Berechnen einer Hash-Funktion
``Virtuelles Hashing`` da an der physischen Adressenicht die Elemente selbst, sondern der Verweis auf die virtuelle Adresse abgelegt wird.
Wie lautet die Formel für den Begelgungsfaktor bf?
Bitte nennen Sie zwei Anwendungsgebiete von Hash-Verfahren.
Hash-Verfahren kommen z. B. zum Einsatz bei der Adressberechnung der Startadresse einer Datei in einem Speicher oder
aber auch im Bereich der Kryptografie, um Verschlüsselungen zu erreichen oder den konsistenten Download einer Datei sicherstellen zu können.
Eine häufig vorzufindende Familie von kryptografischen Hash-Algorithmen ist die der (SHA).
Ein weiterer häufig vorzufindender Hash-Algorithmus trägt den Namen
MD?
Secure Hash Algorithm
„Message-Digest Algorithm“
Wie lautet das einfachste Verfahren der Musterkennung?
Die Regression.
Die Mustererkennung auf Basis der Regression ist eine Technik, die verwendet wird, um Muster oder Trends in Daten zu identifizieren, indem eine Regressionsanalyse durchgeführt wird.
Vorrangig lösen binärer Probleme
Was ist der Unterschied zwischen der Cluster-Analyse und der Regression?
Regression:
Lösen binärer Probleme
Cluster-Analyse:
Mehrere Klassen unterscheiden
Wie funktionieren diese und wofür werden sie genutzt?
zur Aufdeckung von Mustern
Die Funktionsweise neuronaler Netze basiert auf der biologischer Nervenzellen
Auf Basis von Trainingsdaten wird nahezu eigenständig (mittels Learning-Algorithmen) einen Zusammenhang von Eingangs- und Ausgangsdaten hergestellt.
Bitte nennen Sie zwei Anwendungsgebiete von Mustererkennungsverfahren.
Mustererkennungen kommen z. B. zum Einsatz, wenn unstrukturierte Datensätze verstanden werden sollen,
um einen Kundenstamm besser kennenzulernen oder
Anomalien bei Kreditkartenumsätzen aufdecken zu können.
Last changed5 months ago
