Theoretische Informatik | Diplom | Informatik | Universität Hamburg

Theoretische Informatik | Informatik

29.09.1998

Art der Hochschule:

Universität

Prüfungsort:

Hamburg

Studienfach:

Informatik

Art der Prüfung:

Diplom

Prüfungsfach:

Theoretische Informatik

Dauer:

20-30 Minuten

Note:

2-;

Konntest du mit einem selbst gewählten Thema beginnen?

keine Angabe

Versucht der Prüfer bei Schwierigkeiten zu helfen?

keine Angabe

Prüfungsablauf / Tipps

Vorbereitung
Skript: "Modelle für Rechensysteme" (Jessen/*****) ohne Kap. 3 und 7. TGP-Skript (Jantzen) SoSe'98. Zum besseren Verständnis: "Foundations of Computing" (J.Gruska).
Lernen: ca. zwei Monate: Skripte lesen, Karteikarten anfertigen und lernen, Prüfungsprotokolle und Übungsaufgaben durcharbeiten. Zwischendurch Treffen mit Kommilitonen (Dreier- bis Fünfergruppe) und Zuhören bei zwei Prüfungen.

Prüfungsfragen

Prüfungsverlauf
Die Prüfung begann mit ca. 20 Minuten Verspätung. Ich hatte drei Zuhörer. Zum Glück fing Herr ***** mit MfR an:

Was ist denn ein S/T-Netz? Definition siehe Skript. Die Flußrelation hatte ich anfangs falsch geschrieben; außerdem habe ich Kapazitätsfunktion und Kantenbewertung verwechselt. Diese Fehler habe ich aber zum Glück sofort nach dem Hinschreiben selber bemerkt und korrigiert - ich war am Anfang etwas nervös...
Und die Schaltregel? Definition von aktivierter und schaltender Transition laut Skript. Hier war mir mein Flüchtigkeitsfehler ("größer-gleich" statt "kleiner-gleich" geschrieben) nicht aufgefallen. Da Prüfer und Beisitzer dies wohl aber als Flüchtigkeitsfehler erkannt hatten und mich nicht weiter beunruhigen wollten, haben sie hier nichts gesagt. ***** hat mich nach der Prüfung darauf hingewiesen.
Was versteht man unter Lebendigkeit? Definitionen (beide!) aus dem Skript aufgeschrieben und kurz erklärt.
Was ist Fairneß? Auch hier die formale Definition aus dem Skript mit Erläuterung.
Und die faire Schaltregel? Die Prüfung ging wirklich in die gewünschte Richtung! In diesem Teil habe ich wohl im wesentlichen meine Pluspunkte gesammelt. Aber da es sich um ein Standardthema von *****s Prüfungen handelt, sollte man das wirklich drauf haben. - Also nochmal 'ne formale Definition aufgeschrieben.
Impliziert die faire Schaltregel faires Verhalten? Nein! Als Beispiel die vergröberte Version des Philosophenproblems (die, in der die beiden Gabeln oder Eßstäbchen gleichzeitig aufgenommen werden) skizziert und erklärt: Auch unter der fairen Schaltregel verhält sich das Netz nicht fair, da ein Philosoph von seinen beiden Nachbarn blockiert werden kann.
Und folgt aus fairem Verhalten Verklemmungsfreiheit? Auch nicht! Als Beispiel habe ich hier ein Netz, das aus einer Transition mit einer Eingangsstelle besteht, aufgemalt: Die Transition kann nur so oft schalten, wie Marken in der Stelle liegen. Danach liegt eine Verklemmung vor. Das Netz ist aber fair, da die Transition nur deshalb irgendwann nicht mehr schaltet, weil es keine unendliche Schaltfolge gibt (d.h. für jede unendliche Schaltfolge - auch wenn es nur null davon gibt - gilt, daß jede Transition darin unendlich oft vorkommt).
Kommen wir noch zu elementaren Wartesystemen... Erklären Sie doch mal, wie man im M/M/m/k-System den Erwartungswert der Wartezeit berechnet. Uups?! - Da mir der Weg nicht auf Anhieb klar war, habe ich erstmal den Zustandsgraphen aufgezeichnet und die mittlere Füllung (bzw. den Erwartungswert) berechnet. Dann dauerte es leider eine Weile, bis ich auf die Idee kam, die Littlesche Formel zu verwenden, um weiterzukommen.
Kommen wir mal zum Thema Berechenbarkeit. Was fällt Ihnen da so ein? Alle Maschinenmodelle, die mir gerade so einfielen, aufgezählt und (in der Hoffnung, daß ***** in der Richtung weitergeht) auch partiell rekursive Funktionen erwähnt. Entgegen meiner Erwartung fragte er aber bei keinem Stichwort nach, so daß ich ihn (vielleicht etwas zu direkt) fragte, wozu er denn nun genau etwas wissen wollte. Statt auf eines der angebotenen Themen einzugehen, fragte er nach einem der Modelle, die ich in meiner Aufzählung vergessen hatte:
Erzählen Sie doch mal was zur RAM, wie die aufgebaut ist und funktioniert... Registermaschine, also besteht aus Speicher und Eingabeband, die jeweils aus abzählbarer Folge von Registern bestehen. Akkumulator, Befehlszähler, festes Programm,... (siehe Skript)
Kann man in den Registern denn nun unendlich große Zahlen abspeichern? Ja, die Zahlen können (bei der arithmetischen RAM) aus einem beliebigen Körper stammen.
Und wie realisiert man das auf realen Maschinen?
Wie ist das denn mit der Komplexität? Zeit- und Platzkomplexität erläutert, uniform und logarithmisch...
Warum verwendet man da den Logarithmus? Hier war er nicht so ganz zufrieden mit meiner Antwort... Dann definieren Sie doch mal das logarithmische Komplexitätsmaß! Definition aufgeschrieben. Ja, und warum benutzt man da nun den Logarithmus? Hier ging es eine ganze Weile hin und her (kam mir zumindest ziemlich lang vor...). Olaf stellte mir einige recht simple Fragen und ich fragte mich schon, ob ich bei diesem Prüfungsverlauf überhaupt noch durchkommen würde. Aber als ich als Beispiel die Komplexität von ADD A B erläutert habe, hat sich ***** erbarmt und diesem Problem, das wohl zum Großteil ein Kommunikationsproblem zwischen uns war, ein Ende gesetzt: Ich glaube schon, daß Sie das begriffen haben, und haben das ja im Prinzip auch schon gesagt...
Wie kann man denn so eine RAM auf einer Turing-Maschine simulieren? Simulation auf 5-Band-DTM skizziert.
Und wie sieht da die Komplexität aus? Das wollte mir auf Anhieb nun leider nicht so gelingen - habe ein paar Gedanken dazu geäußert. Und den Rest müßte ich mir noch mal genauer überlegen...

Studienfächer