Protokoll zur Diplomprfung in der theoretischen Informatik


Prfer	: 	J. Hromkovic
Prfung:	30.09.2002
Dauer: 		1h 15 min
Fcher: 	 	
	Effiziente Algorithmen (4 Std.)
	Approximative und Randomisierte Algorithmen (4 Std.)
	Compilerbau (4 Std.)
Note 	: 2.0

Effiziente Algorithmen
1. Dynamisches Programmieren 
	a.	Erklren
	b.	Unterschied zu Teile und hersche
	c.	Matrixmultiplikation erklren und die Formel fr die Rekursion erklren
	2.	NP Vollstndigkeit:

Hromkovic: Sie knnen alle Reduktionen?
Ich: Ja
Hromkovic: Welche war schwer fr Sie?
Ich: Alle sind einfach, wenn man die Idee kennt.
Hromkovic: Welche gefllt Ihnen am besten?
Ich: Ich finde die Frbbarkeit interessant.
Hromkovic: Dann erklren Sie 

2. NP vollstndigkeit
		K-COL <p SAT 
		Konstruktion 
		Umgangssprachliche Begrndung

3. Pseudopolynomiele Algorithmen
	a.	Die Idee erklren fr Zahlenprobleme
	b.	Beispiel: Simple Knapsack
		i)  Definition, Idee
		ii) Algorithmus komplett beschreiben
		iii) Komplexitt begrnden
		iv)  Wichtig ist die Begrndung der Schtzung  der oberen Schranke von |TUPLE(i)|


Approximative und Randomisierte Algorithmen

1.	Was ist ein Approximationsschema?
2.	Metrisches TSP und  Christofides Algorithmus
	a.	Konstruktion und die Begrndung einzelner Schritte
	b.	Beweis der Approximationsgte
	c.	Wichtig: Alle schritte mssen BEGRNDET werden!!!
	d.	Wichtig: Dieses Frage hat groen Wert. Sie berschattet die  vorherige 
		Leistung enorm. Daher sollte sie wirklich SITZEN!
3.	Approximationsschema fr Simple Knapsack
	a.	Modified Greedy SK Algorithm
	b.	Approximationsgte beweisen
4.	Primzahltest,SSA:
	a.	Satz ber die Anzahl von Nicht-Zeugen fr ungerage Zahlen n mit 
		ungeradem (n-1)/2
	b.	Beweis:
		i.	Die injektive Funktion 
		ii.	Wahl von b fr n = p * q  (Chinesicher Restsatz)

Compilerbau
1.	CYK Algorithmus - was ist das, wie funktioniert?
2.	LL(k) Grammatik formal aufschreiben

Kommentar: Man sollte alle Beweise lernen. Alle Konstruktionen sollten begrndet werden 
wenn ntig (z.B. Christofides Algorithmus).  Bei den Beweisen war es folgendermaen. 
Zuerst fragte prof. Hromkovic ob ich das oder dies beweisen kann. Ich habe dann zuerst die 
Idee von dem jeweiligen Beweis erklrt. Prof. Hromkovic wollte die wichtigen Schritte 
wissen. Beispielsweise die Definition der injetiven Abbildung bei dem Satz zum Primzahltest.
Sind diese Punkte erklrt fragte er nach dem Rest des Beweises nicht.

Zu der Note: Ich habe es mir leider mit dem Christofides Algorithmus versaut. Dieser war 
ihm wichtig. Bei EffAlg kommen immer fragen zu Approximationsschemata. Metrisches TSP 
ist wohl beliebte Frage die man besser beantworten sollte. 

Atmosfere recht angenehm und ohne Stress.  Wenn es hackt, versucht prof. Hromkovic mit 
fragen zu helfen. Ich habe mir oft Zeit genommen um kurz nachzudenken. Top Tipp: Zuerst 
sollte man das prfen lassen, wo man gut Punkten kann. Denn ein guter erster Eindruck ist am 
wichtigsten.

That's all folks.

