\documentclass[12pt]{article}
%\usepackage[latin1]{inputenc}
\usepackage{german}
\usepackage{a4}

\pagestyle{empty}

\begin{document}
\centerline{{\it Physik auf dem Computer I}}
\bigskip
\centerline{\bf \"UBUNG 14} 
\medskip
\centerline{\it Perkolation}

\vspace{1.5cm}

In dieser \"Ubung soll das Perkolationsmodell auf dem Quadratgitter in 
zwei Dimensionen untersucht werden. Dazu gibt es 
in \verb|/user0/sts/COMPUTERPHYSIK/BLATT14| das vorbereitete 
Programmger\"ust \verb|perc.cc|, das die n\"otigen Datenstrukturen 
(und Grafik) bereitstellt. \"Ubersetzen Sie das Programm mit
\verb|make|. 

Bearbeiten Sie die Aufgabe 1 soweit wie Sie bis ca. 25 min vor
Schlu\ss{} der \"Ubungen kommen. Es geht hier mehr um ein Hineindenken 
in die Konzepte, als um die vollst\"andige L\"osung. Protokollieren
Sie  die Aufgabe, indem Sie mit eigenen {\it Worten} 
einen L\"osungsalgorithmus formulieren. Falls Sie die Aufgabe bis zu
dieser Zeit nicht vollst\"andig gel\"ost haben, ersetzen Sie 
\verb|perc.cc| durch das Programm \verb|perc-burn.cc|, ebenfalls 
in \verb|BLATT14| und fahren Sie dann mit Aufgabe 2 fort. 

\bigskip 

{\bf Aufgabe 1.\ } {\it Perkolieren oder nicht?}\\
Es soll ein Algorithmus gefunden werden, um die Frage zu beantworten, ob ein 
gegebenes System perkoliert oder nicht (d.h. ob es eine
durchgehende Verbindung besetzter Pl\"atze (im Beispiel Wert=1) 
von der Unterkante des Systems zur Oberkante gibt). 
Dazu soll in \verb|perc.cc| eine Prozedur/Funktion geschrieben werden, 
die als Argument ein vorbereitetes Feld mit Werten 0 (unbesetzt) und 1 
(besetzt) erh\"alt und die entsprechende Information 
(perkolierender Pfad existiert/existiert 
nicht) in geeigneter Form zur\"uckliefert. 

{\it freiwillig} Bearbeiten Sie diese Aufgabe, ohne die
Hilfestellungen im weiteren Aufgabentext zu ber\"ucksichtigen, aber
beachten Sie die Bemerkungen in der Einleitung!

Zur L\"osung dieser Aufgabe kann man einen Brenn- oder
F\"ullalgorithmus verwenden. Dazu identifiziert man zun\"achst alle
besetzten Pl\"atze (Wert des Feldes = 1) an der unteren Feldkante und 
tr\"agt diese in eine Liste ein. Technisch ist ein Platz gegeben durch
zwei ganze Zahlen, die wir wie in der vorhergehenden \"Ubung in einem 
Vektor speichern k\"onnen: 
\begin{verbatim}
  Vec  pos(0,1);              // ein Paar ganzer Zahlen mit Wert (0,1)	
  pos[0]  = 7;                // jetzt  (7,1)
  pos  = pos + Vec(1,1);      // jetzt (8,2)		
\end{verbatim}
Eine Liste von solchen Positionen kann durch einen \verb|vector| der
Standardbibliothek erstellt werden, der beliebig viele Elemente
speichern kann. Die Grundz\"uge der Benutzung sind:
\begin{verbatim}
  std::vector<Vec>  list;     // Deklaration
  list.push_back( Vec(1,1) ); // Element anh\"angen
  Vec next_position = list[0];// Zugriff mit []	
  int n_stored = list.size(); // Zahl der Elemente
  list.clear();               // Loeschen des Inhalts

  std::vector<Vec>  new_list;
  swap(list,new_list);        // Austausch der Inhalte  
\end{verbatim}
Die folgenden Schritte m\"ussen jetzt wiederholt durchgef\"uhrt werden:\\
(A) Markiere alle gefundenen Positionen der Liste als ``brennend''
    (sagen wir, Wert=2).\\ 
(B) F\"ur jede dieser Positionen schaue man sich an, ob sie sich an 
    der Systemoberkante befindet. Falls ja, perkoliert das System.\\
(C) Gleichzeitig schaue man sich die Nachbarn der
    gerade ``angesteckten'' Pl\"atze an und trage alle besetzten, aber 
    nicht brennenden in eine neue Liste ein. Dabei m\"ussen die R\"ander
    des System ber\"ucksichtigt werden (erinnern Sie sich dazu 
    an {\sc Life}).\\
(D) Wenn am Schluss diese neue Liste leer ist 
    (\verb|list.size() == 0|), wir aber nicht die Oberkante erreicht
    haben, dann perkoliert das System {\it nicht.} \\
 
Pr\"ufen Sie die Korrektheit Ihres Algorithmus mittels grafischer 
Darstellung, d.h, verfolgen Sie schrittweise, welche Pl\"atze gerade 
angesteckt wurden (Hilfsmittel im Beispielrogramm vorhanden) und ob die 
zur\"uckgelieferte Information, ob das System perkoliert oder nicht,
korrekt ist. 

\bigskip

{\bf Aufgabe 2.\ } {\it Perkolationsschwelle} \\
Entfernen Sie die grafische Ausgabe aus 1.\\

Ermitteln Sie f\"ur die Besetzungswahrscheinlichkeiten $p=0.4$,
$p=0.55$, $p=0.65$ wie gro\ss{} der Anteil perkolierender Systeme 
der Gr\"o\ss{}e $50\times 50$ ist. 
F\"uhren Sie  dazu das Programm f\"ur jedes $p$ etwa zehnmal aus und
notieren Sie, wie h\"aufig Perkolation auftritt. 

\vfill

\begin{flushright}
\begin{tabular}{lll}
Michael Brunner & Di 9:45 & {\tt michi@ica1.uni-stuttgart.de}\\
Stefan Schwarzer & Di 11:30 & {\tt sts@ica1.uni-stuttgart.de} 
\end{tabular}
\end{flushright}

\end{document}

