Fleury Algorithmus: Eulerwege und Eulertouren

Algorithmus von Fleury

• Der Algorithmus von Fleury dient dazu, Eulerwege oder Eulertouren in Graphen zu finden.

Eulertour

• Eine Eulertour ist eine geschlossene Kantenfolge, die jede Kante eines Graphen genau einmal enthält.
• Eine Eulertour existiert in einem zusammenhängenden Graphen, wenn jeder Knoten geraden Grad hat.

Eulerweg

• Ein Eulerweg ist eine Kantenfolge, die jede Kante eines Graphen genau einmal enthält.
• Ein Eulerweg existiert in einem zusammenhängenden Graphen, wenn er höchstens zwei Knoten mit ungeradem Grad hat.

Algorithmusablauf

• Überprüfe, ob ein Eulerweg oder eine Eulertour existiert.
• Wähle einen Startknoten: beliebig für Eulertour, Knoten mit ungeradem Grad für Eulerweg (oder beliebig, falls keiner existiert).
• Erweitere den Pfad, indem eine noch nicht besuchte Kante vom aktuellen Knoten gewählt wird, wobei Brücken nur als letzte Option genutzt werden.
• Entferne die gewählte Kante aus dem Graphen.
• Gehe zum Endknoten der gewählten Kante.
• Wiederhole die Schritte, bis keine Kanten mehr vom aktuellen Knoten ausgehen.
• Die gewählte Kantenfolge ist der Eulerweg bzw. die Eulertour.

Beispielanwendung

• In einem Graphen mit Knoten A, B, C, D und Kanten AB, BC, CD, DA, AC existiert eine Eulertour, da alle Knoten Grad 2 haben.
• Bei Startknoten A ergibt sich die Eulertour AB-BC-CD-DA-AC.

Hinweise zur Nutzung

• Die Kantenauswahl beeinflusst den resultierenden Weg, aber der Algorithmus findet immer eine Lösung, wenn die Existenzbedingungen erfüllt sind.
• Die Erkennung von Brücken kann mit Algorithmen zur Bestimmung von Zusammenhangskomponenten effizient erfolgen.

Matematica

• Die Ergebnisse der schriftlichen Prüfung vom 14. Februar 2023 sind verfügbar.
• Die Aufgaben können am Dienstag, den 21. Februar um 15:00 im Büro des Dozenten eingesehen werden.
• Studenten mit ungenügender Punktzahl können die Aufgaben einsehen, sind aber nicht zur mündlichen Prüfung zugelassen.
• Der Dozent ist Marco Squassina.

Lineare Algebra

• Ein Vektorraum ist eine Menge mit Addition (+) und skalarer Multiplikation (·), die bestimmte Eigenschaften erfüllt.
• Eine Linearkombination von Vektoren $v_1,..., v_n$ ist ein Ausdruck der Form $a_1v_1 +... + a_nv_n$, wobei $a_1,..., a_n \in \mathbb{R}$ (oder $\mathbb{C}$).
• Eine Familie von Vektoren $v_1,..., v_n$ ist linear unabhängig, wenn $a_1v_1 +... + a_nv_n = 0$ nur gilt, wenn $a_1 = a_2 =... = a_n = 0$. Andernfalls ist sie linear abhängig.
• Eine Familie von Vektoren ist erzeugend, wenn jeder Vektor des Vektorraums als Linearkombination dieser Vektoren geschrieben werden kann.
• Eine Basis eines Vektorraums ist eine Familie, die sowohl linear unabhängig als auch erzeugend ist.
• Die Dimension eines Vektorraums ist die Anzahl der Vektoren in einer Basis. Beispiel: $\mathbb{R}^2$ hat die Dimension 2, eine Basis ist ${(1, 0), (0, 1)}$.
• Eine lineare Abbildung ist eine Funktion, die die Addition und die skalare Multiplikation erhält: $f(u + v) = f(u) + f(v)$ und $f(\lambda v) = \lambda f(v)$.
• Der Kern einer linearen Abbildung $f: E \rightarrow F$ ist die Menge der Vektoren in E, die auf den Nullvektor in F abgebildet werden: $ker(f) = {v \in E \mid f(v) = 0}$.
• Das Bild einer linearen Abbildung $f: E \rightarrow F$ ist die Menge der Vektoren in F, die das Bild von mindestens einem Vektor in E sind: $im(f) = {w \in F \mid \exists v \in E, f(v) = w}$.
• Eine Matrix ist ein Zahlenschema mit m Zeilen und n Spalten, genannt $m \times n$ Matrix.
• Matrizen gleicher Dimension können addiert und mit Skalaren multipliziert werden.
• Zwei Matrizen A und B können multipliziert werden, wenn die Spaltenanzahl von A gleich der Zeilenanzahl von B ist.
• Die Determinante einer quadratischen Matrix ist eine Zahl, die bestimmte Eigenschaften der Matrix charakterisiert (Invertierbarkeit usw.).
• Die Inverse einer Matrix A ist eine Matrix $A^{-1}$ mit $A A^{-1} = A^{-1} A = I$, wobei I die Einheitsmatrix ist. Eine Matrix ist invertierbar, wenn ihre Determinante nicht Null ist.
• Ein Eigenvektor einer Matrix A ist ein Vektor $v \neq 0$, sodass $Av = \lambda v$, wobei $\lambda$ ein Skalar (Eigenwert) ist.
• Eigenwerte einer Matrix A findet man durch Lösen der charakteristischen Gleichung: $det(A - \lambda I) = 0$.
• Für jeden Eigenwert $\lambda$ findet man die zugehörigen Eigenvektoren durch Lösen des linearen Systems: $(A - \lambda I)v = 0$.

Algorithmische Komplexität

• Ein Algorithmus ist eine wohldefinierte Berechnungsprozedur, die Eingabewerte entgegennimmt und Ausgabewerte produziert.
• Die algorithmische Komplexität misst den Ressourcenbedarf (Zeit und Speicher) für die Ausführung eines Algorithmus.
• Die Big-O-Notation beschreibt das asymptotische Verhalten einer Funktion. Sie wird in der Informatik verwendet, um die Leistung oder Komplexität eines Algorithmus zu beschreiben, im schlimmsten Fall.
  • $O(1)$: Konstante Ausführungszeit, unabhängig von der Eingabegröße.
  • $O(N)$: Lineares Wachstum der Ausführungszeit mit der Eingabegröße.
  • $O(N^2)$: Quadratisches Wachstum der Ausführungszeit mit der Eingabegröße.
  • $O(2^N)$: Exponentielles Wachstum der Ausführungszeit mit der Eingabegröße.
  • $O(log N)$: Die Größe der Eingabedaten wird mit jedem Schritt halbiert.
  • $O(N log N)$: Effizienter als $O(N^2)$, aber weniger effizient als $O(N)$.
• Die Tabellen geben die durchschnittliche und die Worst-Case-Komplexität für gängige Datenstruktur-Operationen als auch für Sortieralgorithmen an.
• Array
  • Zugriff ist $O(1)$.
  • Einfügen und Löschen ist $O(N)$.
• Stapel, Schlange
  • Push, Pop, Enqueue und Dequeue ist $O(1)$.
• Verkettete Liste
  • Zugriff ist $O(N)$.
  • Einfügen und Löschen ist $O(1)$.
• Hash-Tabelle
  • Einfügen, Nachschlagen und Löschen ist durchschnittlich $O(1)$, Worst-Case $O(N)$.
• Binärer Suchbaum
  • Einfügen, Nachschlagen und Löschen ist durchschnittlich $O(log N)$, Worst-Case $O(N)$.
• Bubble Sort, Selection Sort, Insertion Sort
  • $O(N^2)$
• Heap Sort, Merge Sort
  • $O(N log N)$
• Quicksort
  • Durchschnittlich $O(N log N)$, Worst-Case $O(N^2)$

Delaunay-Triangulierungsalgorithmen (2D)

• Eine Triangulierung einer Punktmenge P in der Ebene ist eine Zerlegung der konvexen Hülle von P in Dreiecke, deren Eckpunkte Punkte von P sind.
• Eine Delaunay-Triangulierung ist eine Triangulierung, bei der der Umkreis jedes Dreiecks keinen anderen Punkt der Menge P enthält.

Inkrementeller Algorithmus

• Punkte von P nach X-Koordinate sortieren.
• Ein umfassendes Dreieck erstellen, das alle Punkte von P enthält.
• Für jeden Punkt p in P (in sortierter Reihenfolge):
  • Finde das Dreieck T, das p enthält.
  • Unterteile T in drei Dreiecke, indem p mit den Eckpunkten von T verbunden wird.
  • Führe Kanten-Flips durch, um die Delaunay-Eigenschaft lokal um p zu gewährleisten.
• Das umfassende Dreieck und alle Dreiecke, die eine Kante mit ihm teilen, entfernen.
• Ein Kanten-Flip ersetzt eine gemeinsame Kante zweier Dreiecke durch die andere mögliche Diagonale des durch die beiden Dreiecke gebildeten Vierecks.

Lawson-Algorithmus

• Der Lawson-Algorithmus ist ein inkrementeller Algorithmus zum Erstellen einer Delaunay-Triangulierung, bei dem Punkte einzeln eingefügt und Kanten-Flips durchgeführt werden, um die Delaunay-Eigenschaft zu erhalten.

Bowyer-Watson-Algorithmus

• Ein umfassendes Dreieck erstellen, das alle Punkte von P enthält.
• Für jeden Punkt p in P:
  • Finde alle Dreiecke, deren Umkreis p enthält.
  • Entferne diese Dreiecke.
  • Erstelle ein Polygon, das durch die nicht geteilten Kanten der entfernten Dreiecke gebildet wird.
  • Trianguliere dieses Polygon, indem p mit allen Eckpunkten des Polygons verbunden wird.
• Das umfassende Dreieck und alle Dreiecke, die eine Kante mit ihm teilen, entfernen.
• Die Komplexität des Bowyer-Watson-Algorithmus beträgt im Durchschnitt $O(n \log n)$ und im schlimmsten Fall $O(n^2)$, wobei n die Anzahl der Punkte ist.

Teile-und-Herrsche-Algorithmus

• Teile die Punktmenge P in zwei Teilmengen $P_1$ und $P_2$ gleicher Größe auf.
• Berechne rekursiv die Delaunay-Triangulierung von $P_1$ und $P_2$.
• Verschmelze die beiden Triangulierungen mithilfe eines Verschmelzungsalgorithmus, der die Delaunay-Eigenschaft beibehält.
• Die Verschmelzung besteht darin, eine Kante zwischen den beiden konvexen Hüllen von $P_1$ und $P_2$ zu erstellen und diese Kante dann zu propagieren, bis die beiden Triangulierungen verschmolzen sind. Dabei werden Kanten-Flips durchgeführt, um die Delaunay-Eigenschaft beizubehalten.
• Die Komplexität des Teile-und-Herrsche-Algorithmus beträgt $O(n \log n)$, wobei n die Anzahl der Punkte ist.

Algorithmischer Handel und Orderausführung

• Die Marktstruktur bildet die Grundlage zum Verständnis von Handelsstrategien, wie Aufträge in Trades umgesetzt werden, sowie deren Auswirkungen auf Preise. Sie informiert über die beste Auftragserteilung und -ausführung und ist entscheidend für algorithmischen und Hochfrequenzhandel (HFT).
• Marktteilnehmer sind Buy-Side (institutionelle und Kleinanleger), Sell-Side (Broker-Dealer, Market Maker, HFTs), Börsen/ECNs (Electronic Communication Networks) und Regulierungsbehörden.
• Institutionelle Anleger verwalten grosse Beträge und werden von langfristigen Anlagezielen geleitet, sind jedoch auch an kurzfristiger Performance interessiert. Zu den institutionellen Anlegern gehören Investmentfonds, Pensionsfonds und Hedgefonds.
• Retail-Anleger sind Einzelpersonen, die für eigene Rechnung handeln. Sie handeln kleinere Auftragsgrössen.
• Broker-Dealer fungieren als Vermittler zwischen Käufern und Verkäufern und bieten Handelsdienstleistungen, Research und Beratung.
• Market Maker stellen Liquidität bereit, indem sie Gebots- und Angebotspreise notieren und aus der Geld-Brief-Spanne profitieren.
• Hochfrequenzhändler (HFTs) nutzen ausgeklügelte Algorithmen und Hochgeschwindigkeitsverbindungen, um schnell zu handeln und mit Market Makern um Liquidität zu konkurrieren, mit sehr kurzfristigem Fokus.
• Börsen sind traditionelle Marktplätze, auf denen Wertpapiere gehandelt werden, während ECNs elektronische Systeme sind, die Kauf- und Verkaufsaufträge direkt zusammenführen.

Regulierungsbehörden

• Die Securities and Exchange Commission (SEC) beaufsichtigt die Wertpapiermärkte und schützt Investoren.
• Die Financial Industry Regulatory Authority (FINRA) ist eine Selbstregulierungsorganisation, die Broker-Dealer reguliert.
• Die Commodity Futures Trading Commission (CFTC) reguliert Termin- und Optionsmärkte.
• Ein Market Order ist ein Auftrag, ein Wertpapier sofort zum bestmöglichen Preis zu kaufen oder zu verkaufen. Die Ausführung ist garantiert, der Preis jedoch nicht.
• Ein Limit Order ist ein Auftrag, ein Wertpapier zu einem bestimmten Preis oder besser zu kaufen oder zu verkaufen. Der Preis ist garantiert, die Ausführung aber nicht.
• Ein Stop Order wird zu einem Market Order, wenn der Preis ein bestimmtes Niveau erreicht (der Stop-Preis).
• Ein Stop-Limit-Order wird zu einem Limit Order, wenn der Preis ein bestimmtes Niveau erreicht.
• Fill or Kill (FOK) wird sofort vollständig ausgeführt oder storniert.
• Immediate or Cancel (IOC) führt einen Teil sofort aus und storniert den Rest.
• All or None (AON) führt den gesamten Auftrag auf einmal aus oder gar nicht.
• Hidden Orders (Iceberg Orders) zeigen nur einen Teil des Auftrags auf dem Markt an.

Auftragsbuch

• Im Auftragsbuch werden die verfügbaren Kauf- (Bid) und Verkaufsaufträge (Ask/Offer) zu verschiedenen Preisniveaus angezeigt. Die Differenz zwischen dem besten Gebots- und Angebotspreis ist die Geld-Brief-Spanne.
• Bei Order-Matching-Systemen werden Aufträge nach dem besten Preis und der Reihenfolge ihres Eingangs ausgeführt (Preis-Zeit-Priorität), oder Aufträge werden anteilig basierend auf der Auftragsgrösse ausgeführt (Pro-rata-Zuteilung).
• Marktfragmentierung bedeutet, dass der Handel auf mehrere Börsen und ECNs verteilt ist, was ausgeklügelte Routing-Algorithmen erfordert, um die besten Preise zu finden.
• Market-Data-Feeds liefern Echtzeitinformationen über Preise, Volumen und Auftragsbuchdaten und sind für den algorithmischen Handel unerlässlich.
• Dark Pools sind private Börsen, in denen institutionelle Anleger grosse Aktienblöcke anonym handeln können, um Marktauswirkungen und Preisvolatilität zu reduzieren.
• Regulation NMS (National Market System) fördert einen fairen Zugang zu Börsen und Marktdaten, während der Dodd-Frank Act die Finanzsysteme nach der Krise von 2008 reformieren soll.
• Algorithmus-Händler nutzen die Marktstruktur zur Optimierung der Auftragsausführung und Gewinnerzielung, z. B. durch optimale Auftragsgrösse, -zeitpunkt und -ort, Liquiditätsbereitstellung, statistische Arbitrage und ereignisgesteuerten Handel.
• Die aufgeführten Referenzen von Hasbrouck (2007) und O'Hara (1995) liefern detaillierte Einblicke in die empirische Marktstruktur und die Theorie der Marktstruktur.