% Fuer diejenigen, die sich mit TeX nicht besonders gut auskennen folgt 
% eine hoffentlich detaillierte Beschreibung der Arbeitsschritte, die zu 
% einer druckfertigen Postscript-Datei fuehren: 
%
% 1) Man kopiere sich diese Datei und editiere sie
%
% 2) Kommentarzeilen kennzeichnen die Stellen im Text, (ein LaTeX-Kommentar 
%    beginnt mit einem Prozentzeichen `%') an denen Text einzufuegen ist.
%    Hat man alle Aenderungen vorgenommen, speichert man die Datei ab.
%
% 3) Dann fuegt man das Paket `teTeX' vorne an seinen Pfad an, indem man in 
%    seiner shell folgenden Befehl tippt
%
%    set path=($path /local/teTeX/bin)
%
% 4) Danach kann man seine Datei `pruefungsbescheinigung.tex' vom LaTeX-System 
%    uebersetzen lassen. Dazu tippt man in der shell den Befehl
%
%    latex pruefungsvorlage.tex 
%
% 5) Wenn alles gut geht, dann erzeugt das LaTeX-System eine Datei
%    `pruefungsbescheinigung.dvi', die man sich mit dem Befehl
%
%    xdvi pruefungsbescheinigung.dvi &
%
%    ansehen kann.
%
% 6) Wenn man sich ueberzeugt hat, dass alle Aenderungen korrekt waren, dann
%    wandelt man abschliessend die .dvi-Datei in eine Postscript-Datei um, 
%    und zwar mit Hilfe des Befehls
%
%    dvips -o pruefungsbescheinigung.ps pruefungsbescheinigung.dvi
%
% 7) Um ganz sicher zu gehen, kann man sich die .ps-Datei dann noch im 
%    ghostview ansehen.
%
% 8) Falls bei Punkt 5) etwas schiefgehen sollte (das LaTeX-System stoppt
%    bei jedem Fehler; man kann den Uebersetzungslauf dann abbrechen, 
%    indem man  `q <return>'  eingibt) sollte man nachsehen, ob man bei der 
%    Anpassung der .tex-Datei einen Fehler gemacht hat, oder ob man vielleicht
%    ein altes LaTeX-System benutzt hat (der Befehl `which latex' sollte als 
%    Ausgabe `/local/teTeX/bin/latex' liefern, wenn nicht, muss man seinen Pfad
%    umsetzen). Falls das alles nicht hilft, bleibt nur noch der Griff zu 
%    einem LaTeX-Buch oder die Suche nach einem LaTeX-kundigen Mitmenschen, 
%    sorry ...
%
% Und nun suche man die Kommentarzeilen ...


\documentclass[a4paper, twocolumn]{article}

\usepackage{fancyhdr}
\usepackage[german]{babel}
\usepackage{umlaut}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\headsep}{18pt}
\renewcommand{\footskip}{35pt}

\pagestyle{fancy}

\begin{document}

\cfoot{ \begin{tabular}{|c|} \hline 
\sf Damit wir auch in Zukunft aktuelle Pr"ufungsfragen haben, sind wir auf Deine Mithilfe angewiesen.\\
  \sf Bitte maile uns die Fragen Deiner Pr"ufung, ein Formular dazu findest Du auf unserer Homepage.\\ 
\hline \end{tabular}}

%
% Bitte hier jeweils den Faechernamen eintragen!
%

\rhead{Pr"ufungsfragen Programmiersprachen und -methodik Sommer 2006}
\section*{Pr"ufungsfragen Programmiersprachen und -methodik Sommer 2006}

% Vorlage zur Erstellung eines Pr"ufungsprotokolls
% Umlaute k"onnen sowohl als "a, "A, "o, "O, "u, "U, "s
% als auch als ä, Ä, ö, Ö, ü, Ü, ß eingegeben werden.
% Im "ubrigen k"onnen alle TeX-Befehle eingegeben werden --
%   solange man nur ANSI-Text eingibt kann man aber auch ohne 
%   TeX-Kenntnisse nichts falsch machen.

% Bitte die Vorlesungen die Gegenstand der Pr"ufung waren,
% den Pr"ufer, soweit bekannt den Beisitzer und den
% Pr"ufungszeitraum angeben.
% Beispiel:
% \subsection*{Beispielvorlesung I u. II,
%             Musterpraktikum \\
%             Fritz Professor, Beisitzer: Hans Assistent \\
%             Oktober 1972}

\subsection*{Analyse und Design objektorientierter Softwaresysteme mit UML (Prof. Kips), 
	     Syntaxanalyse (Ingrid Fischer) \\
	     Prüfer/Schriftführer: Prof. Philippsen \\
             August 2006}

\subsubsection*{Bemerkungen zu Pr"ufung und Pr"ufer}
% Im folgenden kannst Du einige Bemerkungen zum Ablauf der Pr"ufung
% und zum Verhalten des Pr"ufers machen. Stichpunkte bitte mit
% \item beginnen. Fragen die hier beantwortet werden koennten sind:
% Gibt der Pr"ufer Hilfestellungen? Fragt er direkt oder um 5 Ecken?
% Wird eher Verst"andnis gefragt oder eher Detailwissen?
% Wie ist der Schwierigkeitsgrad? 
% Gehen Fragen "uber den Vorlesungsstoff hinaus?
% Tips f"ur k"unftige Pr"uflinge? (Zu lernender Stoff, Verhalten in
%   der Pr"ufung, B"ucher die man gelesen haben muss, ...)
Allgemein:
\begin{itemize}
\item Nette Prüfungsatmosphäre - Prof. Philippsen saß nur dabei und führte Protokoll
\item 2 x 15 min
\item Ich durfte mir aussuchen, mit was ich anfangen will.
\end{itemize}

Syntaxanalyse:
\begin{itemize}
 \item Ging gleich in die vollen - keine Einstiegsfrage, kein grober Überblick - voll ins Detail.
 \item Schaut euch unbedingt die formale (!!!) Definition der LL(k), LR(k) Sprachen an !!! (nicht nur - Naja, man kann anhand der k nachfolgenden Symbole entscheiden, wohin die Reise geht.)
 \item CYK war sehr human - aber auch hier war die formale Definition der Tabelleneinträge gefragt.
 \item Nur LL(k) und CYK kamen dran - kein Earley, Natural Language Processing oder Graphtransformationssysteme
\end{itemize}

UML:
\begin{itemize}
 \item Prof. Kips legt sehr großen Wert auf das Metamodell der UML, also UNBEDINGT anschauen !!!
 \item Er hilft weiter, wenn man mal hängen bleibt (Wink mit dem Gartenzaun - ``Sie haben gesagt, dass man im Kommunikationsdiagramm KLEINE Buchstaben hinter die Sequenznummern schreiben kann.'' $\rightarrow$ Aha, dann wird es wohl auch große geben... *überleg* ... Na klar, man kann auch große davor schreiben ;-) !) und erklärt auch nochmal (Na was braucht man denn, um mehrere Prozesse ausführen zu können? *überleg* ... Na klar, aktive Klassen wären gut!). 
\end{itemize}

\subsubsection*{Fragen Syntaxanalyse}
LL(k):
\begin{itemize}
  \item Was ist eine LL(k) Sprache (Compilerbau, Teilmenge der kfr Sprachen, Parsen in O(n) mögl.)
  \item Wie sieht die Definition von LL(k) formal aus?
  \item Wie konstruiert man die LL(k) Parsing-Tabelle? (Anfangs, Ende, Nachbarrelation $\rightarrow$ LL(k)-Tabelle)
  \item Welche Sprache ist nicht LL(k)? (linksrekursive)
  \item Gibt es ein k, für das $\{a^nb^n; n \ge 1\}$ LL(k) ist? (nein)
  \item Welche Komplexität hat das Parsen einer LL(k) Grammatik? (O(n))
\end{itemize}
Parser für allgemeine kfr. Grammatiken, CYK:
\begin{itemize}
  \item Welche Verfahren können alle kfr Grammatiken parsen? (Top-Down/Bottom-Up mit Backtracking (exponentielle Laufzeit), CYK, Earley (O($n^3$)))
  \item Was braucht man für CYK? (CNF: $S \rightarrow \epsilon, A \rightarrow BC, A \rightarrow a$)
  \item Wie parst man dann mit CYK? (Tabelle: $start \times length \rightarrow A$ mit
	$A_{i,j} = \{A \in N; A \Rightarrow^* w_i \dots w_{i+j-1}\}$; Zusammenfassen von zwei Tabelleneinträgen: $A_{i,j}=\{A; A \rightarrow BC \in P \wedge B \in A_{i,k} \wedge C \in A_{i+k,j-k}\}$, dabei merken, welche zwei Kinder man zusammengefasst hat. Wenn $A_{1,len}$ das Startsymbol enthält hat man einen gültigen Parse-Baum gefunden.
  \item Komplexität von CYK? (O($n^3$))
\end{itemize}

\subsubsection*{Fragen UML}
\subsubsection*{Fragen Syntaxanalyse}
Dies hier ist ja eine Programmiersysteme-Prüfung - deshalb werden wir uns auf das ``L'' der UML konzentrieren.
\begin{itemize}
 \item Einstiegsfrage: Erläutern Sie, warum UML zu Recht als Sprache betrachtet werden kann? (UML ist semi-formale Modellierungsnotation, Syntax formal im Metamodell, Semantik semi-formal)
\end{itemize}
Metamodell:
\begin{itemize}
 \item Erläutern Sie die 4-Stufige Hierarchie der verschiedenen Modellebenen der UML. (Meta-Metamodell, Metamodell, System-Modell, instanzierte Objekte des System-Modells)
 \item Was steht z.B. im Meta-Metamodell? (Class, Relationship)
 \item Welche Beziehungstypen gibt es im Metamodell? (Assoziationsbeziehung(Aggregationsbeziehung, Kompositionsbeziehung), Gen-/Spez-Beziehung, Abhängigkeitsbeziehung(Realisierungsbezierung))
 \item Was davon ist im Meta-Metamodell definiert? (Assoziation, Gen/Spez, Abhängigkeit)
 \item Was ist mit Realisierung? (Instanz von Abhängigkeit im Metamodell)
\end{itemize}
Interaktionsdiagramme:
\begin{itemize}
 \item Genug ge-Meta-t - Lernfrage: Welche Interaktionsdiagramme gibt es? (Sequenzdiagramm, Kommunikationsdiagramm, Interaktionsübersichtsdiagramm, Zeitdiagramm)
 \item Software-Engineering: Wo und wozu haben wir die verschiedenen Interaktionsdiagramme in unserem Vorgehensmodell eingesetzt?
\end{itemize}
Sequenz- und Kommunikationsdiagramm:
\begin{itemize}
 \item Wie sehen Sequenz- und Kommunikationsdiagramm aus? (hinmalen)
 \item Wie kann man im Kommunikationsdiagramm Nebenläufigkeit beschreiben? (Sequenznummern: A1.1... - verschiedene Prozesse, 1.1a - parallele Nachrichten, 1.1 || [i:=1..n] val[i]:=msg(i,...) - parallele, iterierte Nachrichten)
 \item Woran erkennt man, dass ein Kommunikationspartner mehrere Prozesse trägt? (aktive Klasse - doppelter Rahmen oder Stereotyp \{active\})
 \item Von Welcher Klasse im Metamodell sind die Interaktionspartner und Konnektoren im Kommunikationsdiagramm abgeleitet? (ConnectorEnd, Connector)
\end{itemize}
% Ende
\end{document}
