Nachdem wir heute in der theoretischen Informatik wieder mal einen Beweis des Halteproblems gehört haben, wage ich auch mal einen Versuch, das ganze möglichst einfach für jedermann zu erklären, der Programmieren kann, aber ansonsten kein Wissen der theoretischen Informatik hat.

Annahme: Wir haben eine Funktion terminate?(f) welche true zurückgibt, wenn die als Parameter übergebene Funktion f terminiert, also irgendwann mal anhält, und ansonsten false. (Ende der Annahme.)

Nun schreiben wir eine andere Funktion, welche folgendes tut:

def f
  while terminate? f
    # Endlosschlaufe
  end
end

Das wars eigentlich schon. Was erwarten wir nun, wenn wir f aufrufen? Falls die Funktion anhält, würde das ja heissen, dass terminate?(f) false zurückgegeben hat, dass die Funktion also nicht terminiert, obwohl sie das soeben getan hat. Das gleiche haben wir, wenn wir annehmen, dass f nicht anhält: einen Widerspruch! Die Annahme ist also falsch. ∎

Ganz einfach und völlig logisch, oder? Was das ganze für Auswirkungen hat lässt sich sehr ausführlich diskutieren. Aber alle Mathematiker und Informatiker die ihren Job mögen sollten froh sein

(Und ich konnte endlich mal das coole ∎ Symbol benutzen.)

Wie kleine unsere Welt manchmal doch ist: da stöbere ich durch ein Diskrete-Mathematik-Skript und stosse auf den Solovay-Strassen Primzahl-Test und denke mir, ich kenne doch einen Herrn Strassen, das ist doch nicht etwa unser Dozent für theoretische Informatik? Nein, ist es nicht, es ist sein Vater.

Mit Latex kann man nicht nur sehr schöne Dokumente erstellen, auch die zugehörigen Illustrationen sehen genial aus. Kürzlich habe ich das Vaucanson-G-Paket entdeckt, welches auf PSTricks aufsetzt, aber die Dinge noch ein weniger einfacher macht. Ein NFA mit 3 Zuständen beispielsweise, entsteht mit nur diesen Zeilen Code:

\begin{VCPicture}{(0,0)(1,1)}
\FinalState[q_{1}]{(2,1)}{q1}
\State[q_{2}]{(0,-1)}{q2}
\State[q_{3}]{(4,-1)}{q3}
\Initial{q1}
\ArcR{q1}{q2}{b}
\ArcR{q2}{q3}{a,b}
\ArcL{q1}{q3}{\varepsilon}
\ArcL{q3}{q1}{a}
\LoopW{q2}{a}
\end{VCPicture}

Und sieht folgendermassen aus:

Natürlich muss man sich bei der Platzierung bereits im Vorfeld ein paar Gedanken machen, automatisch gelayoutet wird nämlich nicht. Allerdings lassen sich dazu Hilfslinien und ein Raster einblenden, was das ganze wiederum ziemlich vereinfacht.

Auch aufwändigere Dinge gehen ziemlich gut, so beispielsweise dieser Program Dependence Graph, den ich für meine Seminararbeit gezeichnet habe:

Ein Tipp für alle IEEE Xplore Nutzer, die einen eigenen Account haben, aber um vollen Zugriff zu erlangen durch das Netz der Hochschule gehen: unbedingt seinen persönlichen Account ausloggen.

Ansonsten ist man in der Situation, dass man angemeldet weniger Rechte hat als unangemeldet.

Hat mich einige Haare gekostet das herauszufinden.. so, und nun wird weiter recherchiert.

Die erste Woche im MSE ist also überstanden, Zeit für einen kleinen Rückblick.

• Ich bereue es nicht, den MSE machen.
• Unterrichtssprache Englisch ist teilweise etwas merkwürdig, aber noch merkwürdiger finde ich die Studenten, die sich daran stören.
• Ein Modul wird wohl wieder aus meinem Stundenplan fallen, Stochastic Modelling ist zu hart, wir haben einfach zu wenig Vorkentnisse in Analysis.
• Highlight ist ganz klar die theoretische Informatik, mit einem sehr guten Dozenten, und interessanten Themen.
• Die Räumlichkeiten sind eine Zumutung. Meistens bis ans Maximum gefüllt, mit teilweise schlechter Sicht auf die Leinwand, WLAN tut bockig, nicht alle Plätze sind mit Strom versorgt (Verlängerungskabel mitnehmen, ja klar), und ziemlich klein. Und die einzigen Schulzimmer die ich kenne, deren Wandtafeln sich nicht heben und senken lassen.
• Im Gegensatz zum Diplomstudium scheint es diesmal ernster zu sein mit 1 ECTS = 30 Stunden Arbeit…
• … und deshalb schreibe ich jetzt noch ein wenig was für unser Seminar zum Thema Programm-Analyse und Transformation.
• Noch ein (sinngemässes) Zitat eines Dozenten: “Ich muss mich erst noch daran gewöhnen, motivierte Studenten zu unterrichten”.
• Und noch ein anderes: “Ich freue mich, endlich mal richtig unterrichten zu dürfen, nicht nur so Bac..”

So, das wars auch schon. An alle, die nicht den MSE machen: schönes Wochenende; an die anderen: 30 Stunden pro ECTS!

Heute ist es wieder so weit, nach mehr als zwei Jahren ohne Vorlesung, startet heute der MSE—der Master of Science in Engineering.

Los geht es gleich mit Angewandter Statistik und Datenanalyse, danach folgt Kryptographie und Codierungstheorie. Die Skripte sind ausgedruckt, R ist installiert, der Taschenrechner (seit bald 10 Jahren mein treuer HP 48G+) ist eingepackt, auch der Tee ist gekocht und die Thermosflasche hoffentlich immer noch dicht; es kann also definitiv losgehen!

Juhui, endlich haben wir unseren detaillierten (also mit Zeiten und Räumen) MSE Stundenplan erhalten, meiner sieht dabei so aus:

(Schade, dass der Stundenplan nicht in irgend einem akzeptablen Format herausgegeben wird; auch wenn PDF das portable document format ist, ist es eigentlich nicht für den Datenaustausch geeignet.)

Bin eigentlich ziemlich zufrieden mit dem Stundenplan, auch wenn der Donnerstag Abend wohl etwas hart wird. Grundsätzlich finde ich es sehr merkwürdig, erst um 9:10 anzufangen—ich bin mir nicht sicher, ob jemand von so weit her kommt, dass man nicht eine Stunde früher anfangen könnte. Andererseits ist es auch reizvoll, bis um 8:40 schlafen zu können

Wen die einzelnen Module genauer interessieren, der findet auf der MSE-Seite die genauen Beschreibungen.

Wer generall am Master interessiert ist, dem empfehle ich den Blog von Thomas Kälin, der mit mir zusammen studieren wird.