möchte­gern­geek

Ein Algorithmus, von dem jeder schoneinmal gehört haben sollte, ist die Tiefensuche (Depth First Search). Wenn man Zusammenhangskomponenten in einem Graphen finden will oder nach einem bestimmten Knoten in einem Graphen sucht, ist die Tiefensuche meist der einfachste und oft ein geeigneter Algorithmus mit einer Zeitkomplexität $\mathcal{O}(N+M)$, die linear in der Anzahl der Knoten und der Kanten ist. Da man gefühlt alle Graphalgorithmen am besten rekursiv beschreiben kann, folgt hier eine (nichtrigorose) Beschreibung.

1. Man startet die Tiefensuche an einem beliebigen Knoten.
2. Bei jedem noch nicht besuchten Nachbarn startet man wieder eine Tiefensuche.

Aber was macht man im Alltag mit einer Tiefensuche? Meine Antwort darauf ist: Labyrinthe bauen.

Bei dieser Gelegenheit muss NetworkX erwähnt werden. Ein Python Modul, das sehr schöne Klassen für Graphen bereitstellt und perfekt geeignet ist, um schnell Prototypen von Graphalgorithmen zu testen.

Der Code ist als Gist auf GitHub verfügbar.

Man arbeitet an einem Seminarvortrag und will ein Modell auf einem periodischen Gitter erklären. Natürlich kann man sich nicht entscheiden, wie viele Elementarzellen man darstellen möchte. Außerdem ist es einem zuwider mehrere Elementarzellen per Hand zu schreiben.

Wer kennt das nicht?

Glücklicherweise gibt es eine Lösung. Weil man alle seine Aufzeichnungen sowieso in LaTeX setzt, benutzt man TikZ, bastelt eine Elementarzelle und kachelt sie über die Ebene, bis man das Gefühl hat, dass es genau passend für die Präsentation ist. Als Bonus kann man noch mit den Parametern spielen, um einen möglichst überzeugenden pseudo 3D-Effekt zu erzielen.

\documentclass{standalone}

\usepackage{tikz}

\begin{document}
    \begin{tikzpicture}
        \newcommand*{\shear}{0.2}
        \newcommand*{\height}{1.0}
        \newcommand*{\radius}{0.1}
        \newcommand*{\xspacing}{1}
        \newcommand*{\yspacing}{0.5}

        % two-dimensional lattice, with three dimensional basis
        % decreasing counter, otherwise there will be lines through the circles
        \foreach \x in {4,...,0}{
            \foreach \y/\dx in {3,...,0}{
                % primitive vectors
                \draw (\x+\y*\shear-\xspacing/2 , \y*\yspacing            )
                    -- (\x+\y*\shear+\xspacing/2, \y*\yspacing            );
                \draw (\x+\y*\shear-\shear/2    , \y*\yspacing-\yspacing/2)
                    -- (\x+\y*\shear+\shear/2   , \y*\yspacing+\yspacing/2);
                \draw (\x+\y*\shear             , \y*\yspacing            )
                    -- (\x+\y*\shear            , \y*\yspacing+\height    );

                % base
                \fill[white] (\x+\y*\shear, \y*\yspacing        ) circle(\radius);
                \draw        (\x+\y*\shear, \y*\yspacing        ) circle(\radius);

                \fill[gray]  (\x+\y*\shear, \y*\yspacing+\height) circle(\radius);
                \draw        (\x+\y*\shear, \y*\yspacing+\height) circle(\radius);
            }
        }
    \end{tikzpicture}
\end{document}

Und damit wäre wiedereinmal die Vorliebe dieses Blogs für schwarz-weiße Bilder, die entweder Linien und Kreise oder zu große Pixel enthalten, bestätigt.

Vor kurzem habe ich angefangen „Think Complexity“ zu lesen — ein leicht verständliches, interessantes Buch, in dem unter anderem Zelluläre Automaten angesprochen werden. Und zwar die von Stephen Wolfram — ja der Stephen Wolfram, der Mathematica und Wolfram|Alpha entwickelt hat (vermutlich jedoch nicht allein). Zelluläre Automaten eignen sich natürlich sehr gut, pixelige Bilder zu erstellen, wie der Conways-Game-of-Life-Post beweist. Daher, lasse ich erstmal ein Bild sprechen.

Die Idee ist, dass man mit einem eindimensionalen Zustand startet, und einen neuen Zustand daraus mit lokalen Regeln, die je einen rechten und linken Nachbarn berücksichtigen, erzeugt. Stellt man diese Zustände untereinander da, entstehen Strukturen, wie die, die an ein Sierpinski-Dreieck erinnert. Die Erklärung, wie genau diese Regeln lauten, und wie sie definiert sind, überlasse ich passenderweise Wolfram|Alpha.

Und damit ich auch etwas sage, das tiefsinnig erscheint: Die Dreieckige Form entspricht übrigens dem Vorwärtslichtkegel des Startwertes in der ersten Zeile. Die $y$-Achse entspricht hier schließlich einer Zeit und die „Lichtgeschwindigkeit“, mit der Beeinflussungen propagieren können, ist 1 Pixel pro Iteration.

Den Quellcode gibt es natürlich bei GitHub. Wenn auch nur in einem „kleine Fingerübungen in C“-Repo.

Für Liebhaber, hier noch eins im original 1982 Retro-Look.

Passend zur Jahreszeit, wie ich finde.