| Pruefer: | Dr. Slim |
| Studiumsabschnitt: | Vordiplom |
| Stoff: | |
| Pruefungsdatum: | 17. Mar 2003 |
| Vorlesung: | Informatik 4, Effiziente Algorithmen |
| Dozent: | Bry; Hoffmann |
| Bericht: | Vorbereitung auf die Prüfung:
In Info4 habe ich das Uwe Schöning "Einführung in die Theoretische Informatik" gelernt. Hieraus sogut wie alles. Nur im letzten Abschnitt hatte ich keine Lust mir die verschiedenen Probeme und deren Beweise der NP-Vollständigkeit zu merken. In Effiziente habe ich vom Stoffinhalt her das gelernt, was beim Hoffmann in der Vorlesung kam. Dies allerdings aus vielen verschiedenen Quellen (Hoffmann-Folien, Schöning "Algorithmik", Kriegel Skript, viele anschauliche Beispiele im Internet). Hier empfiehlt es sich wirklich die Algorithmen und Datenstrukturen anhand von Java Applet Animationen im Netz zu lernen. Beisitzer war Sebastian Schaffert. Info4 und Effiziente wurden in etwa zu gleichen teilen geprüft: Zunächst Info4: ? "Was ist eine formale Sprache." ? "Was ist Sigma." ? Grammatik zu (aba)^n , n >= 0 angeben. - Ich habe eine kontextfreie angegeben. ? "Wie können Sie einen Mathematiker davon überzeugen, dass diese Grammatik exakt der obigen Sprache entspricht." - Ich muß beide Richtungen beweisen. Die Richtung Sprache -> Grammatik hab ich mit Induktion erklärt. Die andere Richtung wollte ich intuitiv erklären. ? "Intuitiv kann man nicht beweisen. Wie könnten Sie es noch tun." Nach langem Überlegen meinte er "Auch mit Induktion!" - "Ja ok, Induktion ist immer gut!" ? "Von welchem Typ ist die von ihrer Grammatik definierte Sprache." - "Sie ist zumindest vom Typ 2, könnte aber auch noch regulär sein." ? "Ist sie das?" - Hingesehen... "Ja natürlich." ? Reguläre Grammatik für die Sprache angeben. ? Welche Automatenmodelle gibt es und was sind die Unterschiede. Allgemeine Zusammenhänge. ? Zwei reguläre Sprachen geschnitten ergibt was. Wie kann man das beweisen. ? Kontextfreie Sprachen unter Schnitt abgeschlossen? - "Nein" ? "Können sie ein Beispiel dazu angeben?" - Habe zwei kontextfreie Sprachen angegeben, deren Schnitt nicht kontextfrei war. ? Wie beweisen sie das. - Hab ich mit Pumping Lemma für kontextfreie Sprachen erklärt. ? Definition von rekursiver Aufzählbarkeit. Allgemine Zusammenhänge. Entscheidbarkeit. Chomsky Hierarchy... ? Ist das Halteproblem rekursiv aufzählbar. - Zögerlich "ja" ? Ist ihr komplement rekursiv aufzählbar. - Nein, denn sonst wäre das Halteproblem entscheidbar. Ist aber eben nur semi-entscheidbar. Übergang zu Effiziente: Hier möchte ich keine Antworten angeben, denn ich bin hier nicht so sicher gewesen. Ich habe mich eigentlich eher durchgemogelt. Ich möchte keinem hier nicht so ganz richtige Antworten geben. ? Unterschied "Divide & Conquer" zu "Dynamischer Programmierung", Beispiele. ? Laufzeitanalyse bei "Divide & Conquer" wie? ? Dynamische Programmierung, Prinzip erklären und für welche Probleme. ? Unterschied Dynamische Programmierung zu Greedy, Beispiele. ? Huffman Code erklären zusammen mit dem Algorithmus. Warum ist der Greedy. Komplexität davon? ? Welche Bäume kennen Sie. ? Was ist ein B-Baum, wie kann er aussehen. Wie ist die Komplexität bei den verschiedenen Operationen auf B-Bäume. ? Hat eine Frage gestellt, worauf ich Hashtabellen antworten musste. Was ist das Hashing? Umgang mit Kollisionen, Chaining, Tabelle vergrössern. Welche Probleme können hier auftreten. Offene Adressierung, Clusterbildung... Komplexitäten Das war's. Ich hatte mächtig viel Schiss vor der Prüfung, da ich im Vorfeld ziemlich viele schlechte Gerüchte gehört hatte. Deswegen schreibe ich auch diesen Bericht, um damit aufzuräumen. Slim ist ein sehr guter Prüfer. Die Atmosphäre bei ihm ist sehr angenehm. Man diskutiert zwischendurch auch mal vom Thema weg, es wird oft gelacht. Wenn man den Stoff und die Zusammenhänge gut verstanden hat, dann kann nichts mehr schief gehen. Man sollte von sich aus die Zusammenhänge erklären und nicht erst, wenn er danach frägt. Mein plus war das sehr gute Wissen um die Zusammenhänge in Info4. Bei vielen Fragen habe ich nicht einfach nur die Anwort gegeben, sondern auch das drum herum erklärt. Dies ist sehr zu empfehlen; wenn der Prüfer merkt, dass man es kann dann wird er auch nichts tun, um die Note zu versaun. Und ein oder zwei kleine Beweise zwischendurch tun auch niemandem weh. Dauer: 30 min Note: 1,0 Wer anhand dieses Berichts lernt, kann mir einen gefallen tun indem er sein Analysis Rost Prüfungsprotokoll bis zum 28. März ins Netz stellt. Ich kenne viele, die vor dem 28ten bei ihm Prüfung haben. Ich weiß auch, wo ihr wohnt!!! |