1. Einleitung

Im Kurs Theoretische Informatik I haben Sie allerhand Problemstellungen und Algorithmen kennengelernt und können nun (hoffentlich) auch für manche Ihnen noch unbekannten Probleme neue Algorithmen entwickeln.

In diesem Kurs stellen wir uns abstrakter die Frage, was denn ein Algorithmus ist; was es denn heißt, etwas zu berechnen. Ein Algorithmus, beispielsweise ein Sortieralgorithmus, kann ja prinzipiell Arrays beliebiger Länge sorteren. Es gibt also unendlich viele potentielle Eingaben. Dennoch ist der Algorithmus selbst ein endliches Objekt - der Programmcode beispielsweise besteht aus endlich vielen Zeichen. Noch dazu kann ein Algorithmus nur beschränkt die ihm gegebenen Daten manipulieren; in jedem Schritt immer nur an einer bestimmten Stelle und nach festen Regeln.

Emailadressen und Arithmetische Ausdrücke

Die Menge aller denkbaren Emailadressen ist unendlich - zumindest, solange wir für Nutzernamen und Domainnamen keine Längenbeschränkung haben. Nach welchen Regeln sind sie gebildet?

Übungsaufgabe 1.1 Überlegen Sie sich, wie eine gültige Emailadresse auszusehen hat. Als konkrete Beispiele nehmen Sie bitte 

thomas.schmitz@hszg.de                              
dominik@cs.sjtu.edu.cn                              
raffaela@mayer@gmail.com                            
lorenz.klein@greatest/company/in/the/world.com      
.schlaumeier@gmail.com

Welches davon sind gültige Emailadressen? Können Sie genaue Regeln angeben, nach denen eine solche gebildet sein muss? Können Sie die Regeln formal aufschreiben?

Übungsaufgabe 1.2 Sie alle kennen arithmetische Ausdrücke, wie wir sie zum Beispiel in Python eingeben und auswerten lassen können: 

(6 + 8) * 3      
42  
(24 / 4 / 2) * (24 / ( 4 / 2)) + 1     
37
3 + 7 * 8
59
 (2 * 3))       
File "<stdin>", line 1
    (2 * 3))
           ^
SyntaxError: unmatched ')'
 (* 3)       
File "<stdin>", line 1
    (* 3)
     ^^^
SyntaxError: cannot use starred expression here

Die letzten beiden waren in Pythons Augen offensichtlich nicht korrekt. Wie sind korrekte arithmetische Ausdrücke aufgebaut? Beschränken Sie sich gerne auf * und + und / und - und Zahlen und ignorieren Sie erst mal Variablen, Funktionsaufrufe und weitere Operatoren.

Versuchen Sie, eine Art formale Sprache zu entwickeln, die die korrekten arithmetischen Ausdrücke beschreibt.

Endliche Regeln und unendliches Verhalten

Das klassische Beispiel, wie sehr einfache Regeln ein extrem komplexes Verhalten erzeugen können, ist Conways Game of Life. Hier ist der Wikipedia-Artikel dazu. Die Welt von Conways Game of Life ist ein unendliches Schachbrett, in jedem jedes Feld entweder leer ist oder von einem Einzeller bevölkert ist.

Eine Population in Conways Game of Life. Bildquelle: Icongeek26 on flaticon.com

In jedem Zeitschritt weicht die derzeitige Generation einer neuen. Wo neue Einzeller entstehen, das hängt davon ab, wie viele der benachbarten 8 Felder von Einzellern besetzt sind.

  1. Einzeller bleibt: wenn auf einem Feld ein Einzeller lebt und in seiner 8-Nachbarschaft zwei oder drei Einzeller leben, dann überlebt er; in der nächsten Generation wird dort wieder ein Einzeller leben.
  2. Einzeller entsteht: wenn auf einem Feld im Moment kein Einzeller lebt, in der 8-Nachbarschaft aber genau drei Einzeller leben, dann entseht hier in der nächsten Generation ein neuer Einzeller.

Im Umkehrschluss: wenn ein Einzeller in seiner 8-Nachbarschaft vier oder mehr weitere Einzeller hat, dann stirbt er an Überbevölkerung; gibt es in der 8-Nachbarschaft keinen oder nur einen Einzeller, dann stirbt er an Vereinsamung. Wir müssen also für jedes Feld zählen, wieviele der benachbarten Felder bevölkert sind:

Zu jedem Feld schreiben wir die Anzahl seiner Nachbarfelder, die bevölkert sind.
Die nächste Generation.

Was geschieht nun, wenn wir weitere Generationen betrachten? Stirbt die Population aus? Explodiert sie? Stabilisiert sie sich irgendwann?

Übungsaufgabe 1.3 Spiele Sie mit Conways Game of Life! Hier finden Sie einen Simulator: playgameoflife.com

  1. Probieren Sie aus, was geschieht, wenn die Anfangspopulation ein "Pfad" ist, z.B.
    Probieren Sie Pfade verschiedener Länge aus. Welche sterben aus? Welche überleben, und was geschieht mit ihnen?
  2. Probieren Sie das "f-Pentomino" als Startkonfiguration aus:
  3. Probieren Sie meine obige Startkonfiguration aus.
  4. Finden Sie weitere interessante Startkonfigurationen.

Was hat das Game of Life mit TI-2 zu tun? Nun, es illustriert, wie eine endliche, sogar sehr kleine Regelmenge sehr komplexe Phänomene erzeugen kann. In der Tat, das Game of Life ist Turing-vollständig; das heißt in etwa, sie können eine Anfangskonfiguration bauen, die dann einen ganzen Rechner simuliert. Klingt kaum vorstellbar. Wenn wir am Ende dieses Kurses angelangt sind, werden Sie aber verstehen, warum das sogar recht plausibel ist.

Zusammenfassung

Es geht also in diesem Kurs vor Allem um folgende Fragen:

  • Wie können wir endliche Beschreibungen von unendlichen Objekten angeben?
  • Was heißt es, etwas zu berechnen? Welche Modelle fürs Rechnen gibt es, die einerseits umfassend sind, also die möglichst viel können, andererseits auch physikalisch realisierbar sind?