Tips zu Vordiplomsprüfungen

Informatik I/II bei Prof. Schmidt-Schauß

Thema: Informatik I/II - Prüfung, Niederschrift (fast) aller Fragen an einen (uns wohl bekannten) Prüfling in einer Prüfung bei Prof. Dr. Inf. Manfred Schmidt-Schauss

(Bem. des Autors: Dieser Text sowie die Stichpunkt-Kladde hierzu wurden erst nach(!) der Pruefung erstellt, weshalb auch von Ungenauigkeiten bzw. Luecken abzusehen ist ...... also: keine Gewaehr)

1. Themengebiet: die bei uns allzu beliebte Programmiersprache SCHEME

   - Prozedur gegeben durch   (define (f x)
                                 (* x x))
        - Aufgabe: Auswertung der folgenden Aufrufe im Substitutionsmodell
                   (f 5)
                   ==> (* 5 5)

                   (f (+ 3 3))
                   ==> a) applikative Reihenfolge:
                          (f 6)
                          (* 6 6)
                       b) normale Reihenfolge:
                          (* (+ 3 3) (+ 3 3))
                          (*     6       6  )

"So schnell kann das also gehen", womit er wohl meinte, dass bisher (immer noch) niemand die Auswertung im Subst.- Modell so fluessig wie eben unser Pruefling beherrschte !)

- dann so`ne komische Frage wie "Was fehlt Scheme ?" (?? *** hierzu uebrigens von mir die Bemerkung, dass unser * Prof. des oefteren viel Zeit damit verbrachte, zu * ueberlegen, was er denn jetzt als naechstes fuer * eine Frage stellen koennte ... dabei kamen ab und zu * eben solche Fragen bei heraus, von denen er nach * kurzer Zeit selber merkte, dass sie allzu unsinnig * oder unklar gestellt waren...er war scheinbar recht *** unvorbereitet)

...nu abbae ma wiedae zurueck zu unse Fraage "Was fehlt Scheme ?" ==> er wollte wohl evtl. sowas hoeren wie `kein Betriebssystem` (er war sich da wohl selbst nicht sicher und kam dann auf eine andere Frage:...)

- Typueberpruefung: - Wo/Wann gibt`s bei Scheme `nen Typfehler ? ==> unser Pruefling bot das Beispiel (car 3) - Und warum ? ==> naja, halt `n Atom und keine Liste, von der man das erste Element waehlen kann (*** Antwort uebrigens wie einiges andere *** auch frei nach Autor) - Von welchem Datentyp ist denn `car` ? ==> car: list(alpha) --> alpha

(nun dauerte es uebrigens mal wieder bannich lang, bis der Prof. sich `n neues Gebiet ausgedenkt getan -oder so- hatte: Zeitgewinn......)

2. Themengebiet: Mehrzahl eines wehklagenden Gemuesefrucht-Mannequins (zu deutsch: Au-Tomaten-Modelle !!)

- Turingmaschinen: - Was laesst sich mit ihnen berechnen ? ==> Funktionen von N->N (also rek. aufz. Fkt., was der Prof. allerdings wohl weniger wissen wollte -da Info IV- als folgendes:) ==> alles, was berechenbar ist (reichte ihm)

- Laesst sich mit einer TM genausoviel berechnen wie z.B. mit Scheme ? (Anm. des Autors: mal wieder eine unsinnige Frage, da dies mittels der vorherigen Frage ja schon zu bejahen ist, denn Scheme ist wohl `allem, was berechenbar ist` unterzuordnen.... es laesst sich mit TMen hoechstens mehr berechnen) ==> Ja. (?!)

- Was kann man mit einer TM berechnen, die ein endliches(!) Band hat ? (unserer -das sind der Pruefling und ich- Meinung nach immer noch das gleiche, allerdings verringert um Probleme, die mehr als den zur Verfuegung stehenden Speicherplatz benoetigen, sei es zur Berechnung oder Ausgabe...) ==> (der Prof. meinte hier:) "dasselbe wie mit einem EA" (*** unserer Meinung nach voelliger Quatsch, denn mit einer TM mit endl. Band laesst sich immer noch die Sprache (a^n b^n) erkennen, was einem EA gleich welcher Art durchaus schwerfallen duerfte...schier unloesbar sozusagen ! ***)

Hierzu ein Einschub: Gerhard Auer wies mich freundlicherweise darauf hin, daß man hier dazusagen sollte, daß das so nicht stimmt. Ein Auszug aus seiner Mail an mich:

Dazu zwei Bemerkungen:
1.) Eine TM mit endlichem Band kann die Sprache (a^n b^n) sicher NICHT erkennen - denn wenn die Länge von a beispielsweise größer ist als die größte Zahl, die mit der (festen!) Anzahl der Speicherzellen auf dem Arbeitsband der TM dargestellt werden kann, bekommt sie gröbere Schwierigkeiten - "schier unlösbar sozusagen". (...der Schreib-Lesekopf ist ja ziemlich "dumm", was bei einem Modell für real existierende Computer nicht weiter verwundert ;-) Wenn unser Maschinchen etwas zählen soll, muß die Länge des Weges, den der SLK zurücklegt, irgendwo zwischengespeichert werden, und ab irgendeiner Inputlänge ist das schlichtweg unmöglich, wenn das Arbeitsband nur endliche Länge hat. - Man könnte für diesen Sachverhalt sicherlich auch leicht einen formalen Beweis finden, aber ich bin kurz vorm Schlafengehen...

2.) Was kann eine TM mit endlichem Band tatsächlich berechnen? Natürlich genau die Probleme, die mit konstantem Zwischenspeicher auskommen, also die Klasse SPACE(k) (k konstant). Es ist nun ein fundamentaler Satz, daß endliche Automaten genau diese Probleme entscheiden können - nachzulesen z.B. im Buch "Computational Complexity" von Christos Papadimitriou.

Was folgern wir daraus? Der Prof hat recht - die Sprachklassen, die von einem EA und von einer TM mit endlichem Band entschieden werden können, sind identisch.

Nur zur Information, nicht, daß sich jetzt jemand etwas falsches merkt, weil es hier so stand... ;)

Jan, 21.01.99

(aber wahrscheinlich brauchte er das Stichwort EA nur zur Ueberleitung auf das folgende Thema:) - DEA / NEA: (doofer eigensinniger Affe oder so aehnlich, naja ihr wisst schon, was gemeint ist) - Zeichnen Sie mal so`n Graphen eines DEA und erlaeutern Sie. (Sag mir mal einer, wie ich denn jetzt hier so`ne Graphik hinmalen soll ?!? Naja, die Erlaeuterungen, die unser Pruefling nun anhand dieses Graphen vornahm -uebrigens malte er natuerlich nur so`n Ding mit 3 Zustaenden, davon ein Endzustand, auf- , waren keineswegs komplex und hochtrabend und sollten problemlos von jedem, der schon mal so`n Teil gesehen und gezeichnet hat, gegeben werden koennen)

- kurze Erlaeuterung zum Unterschied beim NEA - was sind die neuen Zustaende ? ==> Zustandsmengen - was sind nun die Endzustaende ? ==> die Zust.mengen, in denen ein (oder mehrere) Endzustaende des urspruengl. NEA vorkommen

- Laesst sich mit NEA / DEA dasselbe erkennen ? ==> Ja, da Umwandlung moeglich mittels Teilmengen- konstruktion

- Sind Regulaere Ausdruecke und EA-Modelle aequivalent ? ==> Ja.

3. Themengebiet: Rechnerarchitektur

- RISC / CISC: - Unterschied ? (sollte wohl klar sein)

- Warum sind RISC-Architekturen heutzutage auf dem Vormarsch ? ==> Pipelining moeglich.

(Nun zeichnete der Pruefling noch so zwei Pipeline- Stufen anhand des Skript-Bsp. von Pipeline-Stufen bei einem DLX-Prozessor mit den hierfuer benoetigten Mikrooperationen IF ID EX MEM WB untereinander, wobei dem Prof. allerdings wohl schon die Kaesten allein genuegt haetten) (Anmerkung: das Wort `Mikrooperation` ist in der Pruefung nicht einmal gefallen)

- Was ist fuer Pipelining denn noch so notwendig? ==> gleiche Laenge der Befehlscodes, gleiche Zeitdauer der einzelnen `Kasten- abschnitte` (hier z.B. haette das Wort `Mikro- operationen` ja mal fallen koennen, aber es ging ja auch so....)

- Warum hier 5 Unterteilungen ? ==> Unterteilung in Befehle von jeweils einem Takt (Mikroop. benoetigen ja jeweils nur 1 Takt)

- Stackmaschine: - Wie arbeitet SM ? (Jan wollte uebrigens an dieser Stelle, dass ich `Stackmaschine` statt `SM` schreibe, da er mit dieser Abkuerzung andere Worte assoziiert...Zensur !!) ==> operiert auf einem Stapelspeicher (Keller) usw. (wurd nicht mehr viel zu gesagt)

- Wie wuerde z.B. a*a+b*b mit (egal welchen) Stackmaschinenbefehlen programmiert ?

                    ==> push a             (nebenbei zeichnete
                        push a             der Pruefling uebrigens
                        mul                den jeweils aktuellen
                        push b             Zustand des Stacks auf
                        push b             und erlaeuterte hiermit
                        mul                zugleich die Funktions-
                        add                weise der Stackmaschine)

Fazit: Alles doppelt so locker und halb so schwer wie zuvor befuerchtet, unser Pruefling erhielt uebrigens (obwohl er nicht alle hier auftauchenden Antworten gegeben hatte) `ne nette 1-.

ND und Gruss von euerm Wikinger-Nordlicht Torben

(Torben Kroll)

Informatik III/IV bei Prof. Kemp

Hier die Prüfungsfragen, die Prof. Kemp in meiner Prüfung zur Theoretischen Informatik (Info III/IV) stellte. (11.5.95)

Thema war Info III Becker und Info IV Schnitger.

(* bedeutet, daß er da in die Tiefe gegangen ist.)

Info III:

- AVL-Bäume. Was ist das, Vorteile, Nachteile. Rekursionsgleichung

* Höhenabschatzung AVL-Baume ( Theta(log n) warum?, Fibonacci genau vorrechnen)

- ändert sich das, wenn man über die _Bäume_ statt uber die n! Eingabefolgen mittelt? (Ja)

* Rotationen dazu aufzeichnen, erklären, wie verändern die die asymptotische Laufzeit?

* untere Schranke fur Sortierverfahren mit Vergleichen (vorrechnen)

- binare Suchbaume und Laufzeitabschätzungen bei Insert, Delete, Search, ...

- wie kann man strenge Zusammenhangskomponenten in einem Graphen finden? (DFS)

* DFS, BFS, mit completion numbers etc.

- 2 Verfahren fur Minimum Spanning trees

Info IV:

- kontextfreie Sprachen:

* CYK-Algorithmus: erklären, Abschätzung, an Beispiel vorführen, Dynamisches Programmieren erklären.

- Chomsky-Normalform

- PKP: was ist das? Dann brach er ab, als ich ihm erklärte, daß ich wirklich nur wußte, _was_ das ist, aber er nicht in der Vorlesung drankam

- "Nennen sie mir doch mal ein paar NP-vollständige Probleme" (Clique, HP, SAT, 3-SAT, TSP)

- was ist eine "mehrdeutige Sprache" (Achtung Falle: es gibt nur _inhärent_ mehrdeutige Sprachen und mehrdeutige Grammatiken!)

* Mehrdeutige Grammatiken erklären, Syntaxbaume ganz genau.

- Greibach-Normalform

- Kann man jede k.f. Grammatik in Greibach-NF beschreiben, wenn nur _eine_ Variable in den Produktionen zugelassen ist? (Nein, denn dann hat man eine reguläre Grammatik)

(Jan Haase)

Informatik III/IV bei Prof. Kemp

Pruefung Info 3/4 bei Prof. Kemp, 11.05.1995

Pruefungsstoff  : Info 3 - Becker / Info 4 - Schnitger
Beisitzer       : Uwe Trier
Dauer           : 30 Minuten
Note            : 2.0

INFO 3

* Quicksort
-Verfahren erklaert
-Rek.-Gl. fuer WC und AC aufgestellt, Loesungsidee fuer beide skizziert
-Wann tritt der BC/WC ein? (Pivotelement=Median/vorsortierte Liste)

* Radix-Sort
-Ich wusste nichts darueber :-((

* Red-Black-Trees
-Definition eines binaeren Baumes, Def. des RB-Trees
-Wozu sind RB-Trees gut?

* Bayer-Baeume
-Definition, Sinn
-Einfuegen im B-Baum muendlich erklaert, Baum waechst nur duch Aufspalten der
 Wurzel

* Registermaschine
-Architektur erklaert
-Vergleich Registermaschine (RM)/Turingmaschine (TM):
    -Kann die RM mehr als die TM? (Nein)
    -Laufzeitverlust bei Simulation einer RM durch eine TM: t(n) -> O(t^6(n)),
     also polynomiell

INFO 4

* Rekursive und rekursiv aufzaehlbare Mengen
-Definitionen
-Welches ist die staerkere Eigenschaft?
-Abschlusseigenschaften rekursiv aufzaehlbarer Sprachen:
    -Vereinigung, Schnitt, Komplement (mit Bew.-Idee)

* Halteproblem fuer Turingmaschinen (H)
-Wie beweist man, dass H unentscheidbar ist? ( Reduktion D <= U <= H )
-Reduktion von U auf H im Detail durchgefuehrt.

* Regulaere Sprachen/endliche Automaten
-Wie kann man feststellen, ob zwei regulaere Sprachen gleich sind?
    -3 Moeglichkeiten:  -Entscheide Lehrheitsproblem fuer Kreuzproduktautomat
                        -Minimierg. d. geg. DFAs, Gleichheit bis auf Isomorphie
                        -Konstruktion eines NFAs aus den beiden geg. DFAs,
                         neuer Startzustand q0, delta(q0,#)=q1, delta(q0,#)=q2,
                         falls q1 bzw. q2 die Startzustaende der DFAs sind.
                         Teste nun, ob q1 und q2 aequivalente Zustaende sind.
-Formale Definition der Aequivalenz von Zustaenden in einem DFA
-Warum ist es 'schwierig', ueber die Def. die Aequivalenz zweier Zustaende
 nachzupruefen? (wegen dem Allquantor: Fuer alle w # E* ...)
-Idee fuer Minimierungsalgorithmus (Suche alle NICHT-aequivalenten
 Zustandspaare)
-Wie macht man das? (Beginnen mit Paaren, deren Nicht-Aequivalenz durch das
 leere Wort bezeugt wird; dann alle 'erzwungenen' Nicht-Aequivalenzen
 betrachten usw.)
-Wann stellt sich spaetestens eine Invarianz ein? (Wenn alle Woerter mit Laenge
 kleiner |Q| betrachtet wurden, Q = Zustandsmenge des geg. DFAs)

Bemerkungen:

Herr Kemp ist m.E. ein ruhiger, sachlicher und fairer Pruefer. Er stellt praezise Fragen und laesst einen ausreden.

(Thorsten Dröge)

Mathematik B bei Prof. Behr

Herr Prof. Behr läßt jeden Prüfling etwa 1 Woche vor der Prüfung ein "Spezialgebiet" auswählen, das ist dann ein Gebiet, wo man auch mal einen längeren Beweis können sollte - im Endeffekt kann man sagen, dab er versucht, aus beiden Teilbereichen je zwei große Themen anzuschneiden, und durch die Wahl des Spezialgebietes kann man somit quasi schon einen der vier Bereiche selber festlegen. Herr Behr fängt damit auch an, sodab man gleich zu Anfang schonmal "punkten" kann und sich besser fühlt.

Die Themen in meiner Prüfung:

LA:

• Lösbarkeit von linearen Gleichungssystemen (mit Beweis)
• Rang, was ist das, wie berechnet man ihn, was stellt er dar?
• eindeutige Lösbarkeit, Dimension des Lösungsraums
• Dimensionsformel fur lineare Abbildungen: rg A + dim (Kern A) = n (Beweis in Stichworten) wo sehe ich bei einer Matrix dieses n?
• Def. Determinante
• Cramersche Regel (erklären, beweisen)
• Eigenwerte, Eigenvektoren (Def, Bedeutung)
• Diagonalisierbarkeit, char. Polynom
• wenn Matrix nicht diagonalisierbar, ist die Dimension des Eigenraums dann größer oder kleiner?
• Beweis: zwei Eigenvektoren zu zwei verschiedenen Eigenwerten sind stets linear unabhangig

Diskrete Mathematik:

• was sind prime Restklassen (Beschreibung, wieso prim)
• Zusammenhang Zp zu Zp*
• wie bekommt man die Anzahl der Elemente einer primen Restklasse?
• Satz von Euler
• 4 Eulerformeln (phi-Funktion), alle herleiten

Note: 2.0 - m.E. auch berechtigt, weil ich ab und zu "auf dem Schlauch stand".

Herr Behr war sehr ruhig, wollte aber im großen und ganzen seine Fragen beantwortet haben - wenn man etwas nicht wußte, dann half er bereitwillig mit vielen Tips und Ansätzen, kehrte aber immer wieder zur Ausgangsfrage zurück.

M.E. ist Herr Behr für eine Prufung sehr empfehlenswert, er kam mir eher wie der wohlwollende väterliche Typ vor als ein strenger Prof.

Beisitzer war Hr. Abramenko, der nur einmal kurz in Erscheinung trat, als er eine Antwort von mir als "das wäre aber sehr einfach" abtat.

(Jan Haase)

Hier also erstmal ein Abriss. (Muss erst mal sehen, ob ich an das
Originalprotokoll komme...) Die hier gezeigte Aufstellung ist also
*nicht* vollständig....

Info III
- Was ist eine Erzeugendenfunktion?
- Wofür setzt man Erz. ein?
- Wie setzt man Erz. ein?
Als nächstes kam ein Beispiel:
a[0] = 0
a[1] = 1
a[n] = a[n-1] + a[n-3]
(Aufpassen: Hier fehlt eine Anfangsbedingung)
- Aufschreiben der Erz., rechnen bis zur expliziten Form.
- Wie geht es dann weiter (Taylorreihenentwicklung war gefragt)

- Gegeben seien zwei unsortierte verkettete Listen A und B. Welchen
  Aufwand benötigt man im wc , um die Schnittmenge zu bilden?
  ( O(|A|*|B|) )
- Geht es besser? ( Ja, O(|A|+|B|) )
- Wie macht man das?

- Gegeben ein Digraph. Es gibt Verfahren, um die Knoten in bestimmten
  Reihenfolgen zu traversieren. Welche sind dies? (DFS, BFS)
- Funktion?
- Aufwand? ( O(|V|+|E|), V=Knotenmenge, E=Kantenmenge)

Note dieses Teils 3 (bis 4). Wieso: Siehe Erz. (Anfangsbedingung). Bei
den Listen hatte ich zwar zuerst den richtigen Aufwand genannt
(|A|+|B|), dann aber ein falsches Verfahren erklärt.

Info IV (Wotschke)
- Wie kann man zeigen, daß zwei DFA die gleiche Sprache erkennen?
  (Minimieren, vergleichen. bis auf Benennung identisch. War mir
   entfallen. Ich versuchte nur unzureichend eine Maschine zu bauen, die
   die Automaten parallel abarbeitet, was auch ginge. Aber ich hing fest.)
- [Nachfrage, da ich hing]: Wieviele minimale DFA gibt es zu einer
  reg. Sprache? (genau einen)
- Wie minimiert man einen endl. Automaten? (Äquivalente Zustände finden
  und zusammenfassen)
- Zurück zu den beiden Automaten. Genügt es, die Äquivalenz der
  Anfangszustände zu zeigen? (Ja. Siehe auch Nerode).
- Was ist eine mehrdeutige Sprache? (Eine Sprache zu der keine
  eindeutige Grammatik gefunden werden kann.)
- Kennen Sie ein Beispiel? (Nein.)
- Wie kann man herausfinden, ob eine Sprache mehrdeutig ist?
  (Keine Ahnung. Erklärung wäre gewesen: "Mit dem Pumping Lemma").

- Erzählen Sie mir mal was über die Greibach Normalform. Was ist das?
  Wie sieht das aus? (Da erzählte ich fast das Richtige. Die
  Produktionen müssen aussehen wie folgt: A->aX, wobei X eine Folge von
  Nichtterminalen ist.)
Die folgende Frage:
- Ist X _ein_ oder _mehrere_ NT?
verunsicherte mich dummerweise. Anscheinend hatte ich mich nicht klar
ausgedrückt, oder was falsches gesagt. Ich warf mein Wissen über
rechtslineare Grammatiken über Bord, und erklärte, es sei _ein_ NT.
Der Prüfer unterrichtete mich darüber, daß dies Unsinn sei, und sagte
mir, daß Grammatiken dieser Form rechtslinear sind.
- Welche Sprachen werden von rechtslinearen G. erzeugt? (reguläre)
Also: Nicht (echt) kontextfreie. Damit war die GNF dann vergessen.

Summa sumarum stolperte ich mehr durch den Info IV Teil. immer wieder
ungenügend detaillierte Antworten, Unsicherheit. Note dieses Teils: 5

Summe: Bei einer einzelnen 5 darf nicht mehr gemittelt werden, daher
also eine 5. Neuer Termin am 18.07.1997.

Wenn Ihr weitere Vordiploms-Prüfungsprotokolle habt, dann mailt sie mir, ich binde sie gerne ein.