Ich habe eben meine Algorithmik-Prüfung mit ’ner 2 bestanden. Mein Prof meinte, ich hätte ja über einige Fragen sehr lange nachdenken müssen, aber er hat mich gleich mit der ersten Frage eiskalt erwischt. Nicht, dass ich nicht wüsste, was eine amortisierte Analyse ist – nur war es mir so grundlegend, dass ich nicht davon ausging, dass er sich auf dieses Thema so einschießt. Es war nämlich nicht so, dass ansonsten keine Algorithmen durch genommen worden wären:

• Tiefensuche in Graphen – Struktur-Analyse:
  • Zusammenhangskomponente
  • Bizusammenhangskomponte
  • Starke Zusammenhangskomponente
  • Tarjan’s Algorithmus
  • Bipartite Färbung
  • Topologische Sortierung im DAG
• Breitensuche im Graphen
• Kürzeste Pfade im Graphen (mittels Relaxation)
  • Bellmann-Ford
  • Kürzeste Pfade im DAG
  • Dijkstra-Algorithmus
• Kürzeste Pfade zwischen allen Knoten (All-Pairs)
  • All Pairs über Anzahl Kanten
  • Faster All Pairs
  • Floyd-Warshall
  • Johnson’s Algorithmus
• Flüsse
  • Ford-Fulkerson
  • Edmund-Karp
  • Dinic
  • Generischer Push-Algorithmus
  • Relabel-To-Front Push Algorithmus
• Matching
  • Maximales bipartites Matching
    • Ford-Fulkerson
    • Dinic
  • Maximal gewichtetes bipartites Matching
    • Ungarische Methode
    • Edmund-Karp
  • Maximales Matching in beliebigen Graphen
  • Maximales Matching in beliebigen gewichteten Graphen
• Datenstrukturen
  • Suchbaum
  • Splay-Tree
  • Heap
  • Binomial Heap
  • Fibonacci Heap
• Matrizen
  • Matrix Multiplikation
  • Strassen Algorithmus
  • LUP-Zerlegung
  • Kleinste Quadrate
• Dynamische Programmierung
  • Matrixkettenmultiplikation
• Lineare Programmierung
  • Simplex Algorithmus
  • Ganzzahlige Programmierung – Branch & Bound
• Geometrische Algorithmik
  • Scan Line
    • Vertikale Sichtbarkeit
    • Liniensegment Schnittproblem
  • Konvexe Hülle
    • Graham’s Scan
    • Gift Wrapping
  • Dichteste Punte
    • Naiver Algorithmus: Teste alle Punkte mit allen anderen
    • Divide & Conquer – Algorithmus
  • Geometrische Datenstrukturen
    • Quad-Tree
    • kD-Tree
    • Intervall Baum
  • Voronoi Diagramm
    • Divide & Conquer – Algorithmus
  • Delaunay-Triangulierung
    • Guibas Algorithmus
  • Kleinste umschließende Kreise
    • Naiver Algorithmus
    • beschränkter „kleinste umschließende Kreise“-Algorithmus
    • Linearzeit Algorithmus
    • Minidisk-Algorithmus
    • Minidisk mit Move-to-Front

Generell ist das schon ein spannendes Thema. Wer ein Gefühl dafür bekommen möchte, was sich hinter so einem Algorithmus verbirgt, sollte sich mal diese Beschreibung eines Algorithmus aus dem Problembereich „Kleinste umschließende Kreise“ angucken.

Interessant ist auch der Splay Tree (siehe Abbildung rechts). Hier handelt es sich um einen Suchbaum, der sich selbst ausrichtet. Wenn du bspw. den Begriff „Buch“ suchst, wird „Buch“ nach oben in die Wurzel geschoben. Wenn du das nächste Mal wieder „Buch“ suchst, ist es oben im Baum und es kann schnell darauf zugegriffen werden. Oftgesuchte Begriffe sind also oben und schnell verfügbar, während seltengesuchte Begriffe unten sind.

Also alles faszinierend: Nur wenn du über soo viele Dinge geprüft wirst, kannst du noch so viel üben – das übersteigt einfach deine Speicherkapazität und dann muss man halt nachdenken… ;-)

Jetzt heißt es: format c:\ *g*

Ich mache mir Sorgen. Das Wetter ist schön, ich lag den ganzen Tag in der Sonne und dennoch ist meine größte Entdeckung dieses Tages folgende Formel:

In der Wikipedia steht dazu: Gauß war nach zeitgenössischen Berichten der Ansicht, dass diese Formel einem Schüler der Mathematik sofort ersichtlich sein müsse – oder er würde niemals ein hochkarätiger Mathematiker werden.

Was ist so besonders an dieser Formel? Schauen wir uns mal die Bestandteile an:
e = 2,7182818284590452353602874713526… und hat unendlich viele Nachkommastellen. Auf e (die eulersche Zahl) kommt man folgendermaßen:

informell beschrieben: Wenn man für n unendlich einsetzen würde, käme e heraus.

pi = 3,1415926535897932384626433… hat auch unendlich viele Nachkommastellen. Pi entsteht folgendermaßen:

Also: Der Umfang eines Kreises mit einem Durchmesser von 1 ist pi.

i ist die imaginäre Einheit und wird bei den komplexen Zahlen benutzt. Die komplexen Zahlen wurden eingeführt, weil
x² + 1 = 0
keine Lösung hat, denn bekanntlich ist das Quadrat einer Zahl immer positiv. i ist allerdings so definiert, dass
i² = -1
ist, sprich auch negativ sein kann.

Und jetzt soll

gelten? Ja…

Aber bleiben wir noch ein bißchen bei den komplexen Zahlen:
Eine komplexe Zahl hat zwei Bestandteil: a ist der Realteil und b ist der Imaginärteil. Die Form ist also a + b*i
Für die Multiplikation von komplexen Zahlen gilt diese Rechenregel:

Mal zwei Beispiele:
1.
(2+0i)*(3+0i) = (2*3 – 0*0) + (2*0 + 0*3)i = 6 + 0i
Die Multiplikation funktioniert bei diesem Beispiel wie die ganz normale Multiplikation von 2*3=6, was daran liegt, dass die Multiplikanden ((2+0i) und (3+0i)) nur Realteile haben.
2.
Schauen wir mal, was sich bei dieser Rechnung ergibt:
(0+1i)*(0+1i) = (0*0 – 1*1) + (0*1 + 1*0)i = -1 + 0i
Hier kommt wie gefordert i² = -1 heraus.

Eine komplexe Zahl setzt sich also aus einem Realteil und Imaginärteil zusammen. Die komplexe Zahl ist also zweidimensional. Denkt man an ein Koordinatensystem, kann man die Zahl als Punkt eintragen:

In diesem Fall ist auf der x-Achse der Realteil und auf der y-Achse der Imaginärteil eingetragen. Die eingetragene komplexe Zahl ist also (3+2i).

Dieser Punkt im Koordinatensystem lässt sich auf zwei Weisen eindeutig beschreiben:

1. Mache einen Punkt bei (3|2), also x-Achse = 3, y-Achse = 2 – das kartesische Koordinatensystem spiegelt sich auch in der Form der komplexen Zahl wider: (3+2i)
2. Aber der Punkt ließe sich auch mit Polarkoordinaten beschreiben – ähnlich wie beim Radar (du bist beim Ursprung (Punkt (0|0)) und weißt, in welchem Winkel zur X-Achse (φ) der Punkt ist und wie weit dieser entfernt ist (r). (siehe auch obiges Bild)

Aus den Polarkoordinaten ergibt sich die trigonometrische Form einer komplexen Zahl:

Es gilt also, dass der Realteil a = r * cos φ
und der Imaginärteil b = r * sin φ
Wir erinnern uns an Sinus und Kosinus:

Und jetzt kommt die entscheidende Gleichung (Eulersche Identität), die zum Ah-Ha führen wird:

Wir beweisen diese Gleichung später und setzen erstmal für φ = pi ein.
Es gilt sin(pi) = 0 und cos(pi) = -1, also stimmt die Gleichung

Klar machen kann man es sich auch über diese Abbildung:

Im Fall von φ = pi (pi = 180°) liegt der Punkt bei (-1|0).

Jetzt zum versprochenen Beweis der Eulerschen Identität:

muss für alle x 1 ergeben, damit

stimmt.

Wir zeigen
(1) f ‚(x) = 0, was heißt, dass f(x) konstant ist
f ‚(x)

Der Zähler ist offensichtlich 0.

(2) f(0) = 1
Was gilt, denn cos(0) + i sin(0) = 1, denn sin(0)=0 und cos(0)=1
e^(i*0)=1, denn i*0=0 und e^0=1

Also gilt, das f(x) konstant 1 ist. □

Anhand dieser Formel werden wichtige mathematische Konstanten in Bezug zueinander gestellt und verschiedene Gebiete miteinander verknüpft (komplexe Zahlen, Exponentialfunktion, trigonometrische Funktionen).

Aber mal ganz ehrlich. Mir ist zwar klar, dass der Beweis stimmt, aber wie stimmen kann, wo e und pi reell sind, ist mir schleierhaft. Auf mich wirkt die Formel wie

• entweder ein Glücksgriff der Mathematik, die den dichten Nebel und die Dunkelheit der Unwissenheit an einer winzigen Stelle auf dieser Ebene verschwinden ließ
• oder eine absolute Trivialität, die wir als solche noch nicht erkannt haben.

Informatiker sind komisch. Und trotzdem habe ich manchmal Angst… Diese Mail flatterte soeben vom FSR in meine Mailbox:

Moin, :)

die Fachschaft hat Knoblauch zu verschenken. Es handelt sich dabei
um 5kg gewöhnliche Knoblauchknollen.
Abzuholen (auch einzelne Knollen) im c’t (E-118) unter der Spüle.

Mit besten Grüßen,
i.A. des FSR
***

Ich hoffe die Vampire konnten erfolgreich abgewehrt werden…