= DATUM
November 04

= LERNAUFWAND
Empfehlung für die Lernzeit: mindestens vier Wochen
(ich habe abzgl. des Lernens vor Klausuren direkt davor 
ca. zehn Tage gelernt, das war zu wenig)

= Verwendete Materialien (Bücher, Skripte etc...):
Vorlesungsskript von Köbler WS 03/04; Lern-PDF eines
Studierenden; Mitschriften, Übungsblätter, selektiv
verschiedene Bücher - 
empfehlenswert bei ausreichender Zeit, auch Beweise 
und Beispiele gut zu verstehen, sind:

eher anschaulicher:
Sipser, M.: Introduction to the Theory of Computation, 
PWS Publishing Company, 1996.

Parkes, A.: Introduction to Languages, Machines and Logic:
Computable Languages, Abstract Machines and Formal Logic,
Springer Verlag, 2002.

Horn, Christian; Kerner, Otto: Lehr- und Übungsbuch 
Informatik, Band 2: Theorie der Informatik. Leipzig:
Fachbuchverlag Leipzig, 2000.

eher weniger anschaulich:
Schöning, Uwe: Theoretische Informatik kurz gefasst. 
4. Auflage. Mannheim: BI Wissenschaftsverlag, 2001. 

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer:
eigentlich entspannt, viel Möglichkeit, selbst Ausführungen
zu machen und das Gelernte zu präsentieren (das hat mich 
ziemlich überrascht, da viele Prüfungen extrem schneller
ablaufen); 
wurde so gut wie nie unterbrochen und es wurde
immer gewartet, ob noch etwas kommt - sehr viel Wert wurde
auf exakte, formale  Notation gelegt, was mir leider
beinahe zum Verhängnis geworden wäre

= Prüfungsfragen:
Sprachtypen der Chomsky-Hierarchie, explizite Definition
der klass. Beispielsprachen (a*b*, a^nb^n, a^nb^nc^n, H),
Wie sehen deren Grammatiken aus?, 
Beispiele für Automatenkonfigurationen von Akzeptoren 
dieser Sprachen,
Unterschied Determinismus / Nichtdeterminismus, 
Nachweis der Nichtregularität einer Sprache (Pumping Lemma)

Wichtig ist, dass das Erklären nicht ausreicht - es muss
formal aufgeschrieben werden können.

= FAZIT:
ich habe leider eine schlechte Prüfung abgelegt, fand 
es insgesamt aber angemessen - der abgefragte Stoff ist 
erlernbar, das schwierige daran ist vor allem das Erklären
mit unterstützender formal exakter Notation

= Datum der Prüfung
08.02.05

= Benötigte Lernzeit als Empfehlung
kommt drauf an; so man sich in den mathematischen Grundlagen
der Stochastik und der Zahlentheorie leidlich auskennt, 
reichen zwei Wochen, für die meisten Informatiker ist also 
zusätzlich noch ca. eine Woche für diese Grundlagen zu 
veranschlagen.


= Verwendete Materialien (Bücher, Skripte etc...)
Auf der Homepage von Prof. Köbler ist ein Skript zu finden, 
leider umfasst dies aber nicht den gesamten in der Vorlesung
behandelten Stoff. So fehlt insbesondere das Kapitel über 
Secret-Sharing-Verfahren. (zumindest in der mir bekannten 
Version, aber vielleicht hat sich da ja schon was getan. Man 
ist also gut beraten, auch die eigene Mitschrift, sowie 
möglicherweise andere Literatur zu Rate zu ziehen


= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Die Prüfung verlief in recht entspannter aber konzentrierter
Athmosphäre. Es sei an dieser Stelle gleich darauf hin 
gewiesen, dass Prof. Köbler seine mündlichen Prüfungen meist
über 55-60 Minuten abhält.

Die Aufgabe des Beisitzers beschränkte sich im wesentlichen 
darauf, die behandelten Themen mit zu protokolieren.


= Prüfungsfragen
* Was ist ein MAC (Message Authenication Code) und wie 
  funktioniert er prinzipiell
* was bedeuten dabei die Wahrscheinlichkeiten Alpha und Beta
* wie kann man sie minimieren
* was bedeutet Lambda
* wie kann man allgemein Verfahren mit Lambda=1 erzeugen
* wie kann man diesesd Verfahren für beliebige Lambda 
  erweitern

* was sind SSV (Secret-Sharing-Verfahren)
* wie kann man sie konstruieren
* was bedeutet der Expansionsfaktor
* wieso kann der nicht kleiner als 1 werden

* was ist der Unterschied zwischen Signatur Verf. und MAC`s
* beliebiges Beispiel für Signatur Verf.

= Note 2,7
= Fazit 
Man sollte darau achten, dass Prof. Köbler die konkreten 
Verfahren (MD4/5/SHA-1/DSA/etc.)nicht unbedingt bis ins 
Kleinste wissen will. Ihn interessieren vielmehr die 
theoretischen Hintergründe und allgemeine 
Konstruktionsmethoden, so dass man sich unbedingt die 
Beweise anschauen sollte.

= Benötigte Lernzeit als Empfehlung

Man braucht eine Woche um alle Definitionen und 
Sätze zu beherrschen. Je nachdem wie schnell man die 
Beweise versteht und verinnerlicht muss man Zeit 
dazuschlagen.

= Verwendete Materialien (Bücher, Skripte etc...)

Vorlesungsmitschrift, die existierenden Teile des 
Skriptes und den Link www.tele-task.de

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer

Es war eine angenehme Athmosphäre, man hat genug Zeit 
zu antworten. Mit der Zeit hat sich ein Gespräch über 
das Gebiet entwickelt, so dass es dann keine explizieten 
Fragen mehr gab. Es wurde auch mal nach Ideen gefragt, 
die nicht dran waren. Prof. köbler unterstützt einen bei 
den Beweisen und gibt auch Tipps, um auf den richtigen 
Weg zu kommen.
Der Beisitzer verhält sich ruhig und schreibt nur das 
Protokoll. Er ist nicht aufgefallen.

= Prüfungsfragen

- Arten von Komplexitätsklassen?
- Wie werden die getrennt?
- Polynomialzeithierachie (und wo liegt dort PSPACE)
- Das Graphenisomorphieproblem

= Fazit 

Die Prüfung verlief gut, allerdings muss man sich schon 
in dem Gebiet auskennen und auch Beweise mögen (halt eine
typische theoretische Prüfung)

= Datum der Prüfung
09.08.05

= Benötigte Lernzeit als Empfehlung
Ich habe kanpp drei Wochen gelernt, gemessen am Umfang des
Stoffes ist das ok, besser jedoch etwas mehr ;-)

= Verwendete Materialien (Bücher, Skripte etc...)
Skript (das MUSS man einmal verstanden haben)
dann Lernzusammenfassung eines Kommilitonen +
Prüfungsprotokolle (auch von anderen Unis, man bekommt nen
guten Überblick, was gefragt werden könnte).
Dann hab ich mir die "wichtigsten" Definitionen
rausgeschrieben und auswendig gelernt (es ist sehr wichtig
alles formell aufschreiben zu können)

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Herr Herold war Beisitzer, aber man hat ihn gar nicht
wahrgenommen. Die Prüfung war eher ein Gespräch zwischen
Herrn Köbler und mir: sehr nett, er hat immer gewartet ob
noch was kommt und wenn ich gestockt habe, hat er nach
kurzer Zeit geholfen/weiter erklärt. 

= Prüfungsfragen
Wie sind die Regulären Sprachen definiert?
- Konzentration auf Äquivalenzklassen
- dann Beispielsprache a^nb^m, wie sieht der DFA aus?

Allgemein ein Automat für 10 Zeichen über unärem Alphabet
- ist der minimal, warum => Äquivalenzklassen

Chomsky-Hierarchie

Kontextfreie Sprachen
- PDA, Beispielsprache angeben, dann PDA konstruieren für
a^n b^m c^n-m
- Unterschied DPDA-PDA, wie bekommt man für o.g. Sprache den
DPDA
- Wie kann man erkennen, ob eine Sprache kontextfrei, aber
nicht deterministisch kontextfrei ist? (Abschlusseigenschaften)
- Beispiel Sprache der Pallindrome

Da war es auch schon vorbei, hab zu lange getrödelt.

Sehr wichtig alle Definitionen der Automaten exakt
aufschreiben zu können, Beispielsprachen zu wissen und den
dazugehörigen Automaten / Grammatik aufschreiben zu können.
Betrachtung der Sonderfälle: Ist Epsilon teil der Sprache,
wie krieg ich das da rein/raus?

= Note (Optional)
mit 3.3 nicht ganz so doll, aber ok, ich hab mich bei den
Definitionen ein paar Mal vertan und kam da ins wanken (und
die sind wichtig, wichtig, wichtig), dann hab ich nicht
damit gerechnet, noch soviel am Automaten rumbasteln zu
müssen, Pumping-Lemma kam dementsprechend nicht mehr dran,
hätte mir aber (ausnahmsweise) besser gefallen ;-)

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Die Prüfung war gut, die Benotung angemessen.
Das Problem sind hauptsächlich die formellen Notationen,
kann man die, ist das ein Selbstgänger.

= Datum der Prüfung:
19.04.06
= Benötigte Lernzeit als Empfehlung:
ca. 2 Wochen wenn man relativ intensiv lernt

= Verwendete Materialien (Bücher, Skripte etc...):
hauptsächlich das skript 
ansonsten noch gelegentlich das buch von douglas r. stinson
- cryptography theory and practice

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
angenehm, wenn man selbst nicht so nervös gewesen wäre

= Prüfungsfragen

zunächst was heißt asymmetrische und symmetrisches
Kryptosystem? und was ist der vorteil des asym.? (beim sym.
muss der schlüssel unter geheimhaltung dem anderen
zugänglich gemacht werden, beim asym. nur authentisch)

dann zu den 2 asym. verfahren:
was ist RSA und wie funktioniert es?
wie berechne ich d? (erweiterter euklid. alg.)
wie genau? 
wieso ist x^(e*d) = x mod n? (Beweis)
wie verhalten sich RSA und das Faktorisierungsproblem?
und wir kamen zum Alg RSA-Factorize (erklären)
und frage wieso ist in dem alg. irgendwann b^2=1 mod n?

zum rabin-system:
verhalten von rabin-sestem zum faktorisierungsproblem und
erläuterung, dass wenn rabin gebrochen ist, man
faktoriesieren kann, also rabin-factorize erklären.
frage: wieso liefert A(c,n) nicht immer wieder das a, was
vorher quadriert wurde?
wahrscheinlichkeit das alg erfolgreich?

Wechsel zu sym. verfahren
erst allg. fragen.
wie sehen modernere sym. verschlüsselungsverfahren aus?
(iterationen bestehend aus subst., perm. und schlüssel addieren)
durch fragen an die ich mich nicht mehr erinnern kann, zum
lin. kryptoanalyse gelangt.
(fragen zum verständnis von weshalb der Begriff linear
gewählt wurde)
was ist der bias?
was ist der nichtlineare teil eines kryptosystems (die
substitutionen)

(+ das was ich vergessen habe)

= Note (Optional)
1.0

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
ich habe aus nervösität sehr viele fehler eingebaut, wurde
aber selbst oder durch herrn köblers bemerkung alla "gucken
sie sich das nochmal an", darauf aufmerksam (gemacht).
herr köbler hat einem, wenn man sich irgendwo verhaspelt
hat, mit einer nicht zuviel aber gerade den richtigen
denkanstoß gebenden bemerkung oder frage weitergeholfen.
hätte mir selbst eine 1.7 oder 2.0 gegeben.

= Datum der Prüfung
21.4.2006

Ich kann mich hier nur dem Protokoll der anderen 1,0
anschließen (vom 19.4.2006), es könnte bis auf einige
Details auch meines sein. Ich benutzte zur Vorbereitung
ausschließlich das Skript.

= Prüfungsfragen

Ergänzend erinnere ich mich noch an das Brechen der
Hill-Chiffre, und die Frage des Invertierens von Elementen
der endlichen Körper (Erw. Eukl. Algorithmus), wovon jeweils
alle Details erfragt wurden.

= Note (Optional)

1,0

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)

Es war kein Problem, Herrn Köbler manchmal misszuverstehen
(also nicht zu wissen was er wirklich meint und in eine
andere Richtung loszumarschieren). Er korrigiert das dann
bald und es hat keine negativen Auswirkungen.

Bemerkenswert ist, wie umfangreiche Bedeutung doch das
letzte Kapitel der Vorlesung (RSA) hatte, offenbar nicht nur
bei mir. Es gehörte immerhin zu den schwersten.

= Datum der Prüfung
4.8.2006

= Benötigte Lernzeit als Empfehlung
Wenn man fast immer in der Vorlesung war (auch geistig
anwesend) und die Ideen zumindest in Grundzügen verstanden,
dann reicht durchaus eine gute Woche. Die Konzepte sind
jedoch noch etwas schwieriger als in Kryptologie 1 zu
verstehen, also lieber genug Zeit einplanen, um das
nachzuholen, falls es in den Vorlesungen nicht geklappt hat.

= Verwendete Materialien (Bücher, Skripte etc...)
Vorlesungs-Mitschriften und den Stinson, an den sich die
Vorlesung stark anlehnt (und zwar an alle drei Auflagen, die
sich durchaus unterscheiden!). Da es in diesem Semester kein
Skript gab (bzw. bis zu meiner Prüfung war nur das 1.
Kapitel verfügbar, vielleicht ca. 15-20% von allem) war eine
lückenlose Mitschrift umso wichtiger - zum Lernen. Nicht
unbedingt für die Prüfung, denn die meisten Details waren in
der Prüfung dann nämlich nicht so wichtig, s.u.

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Wie schon Kryptologie 1 sehr entspannte Prüfung (von der
eigene Aufgeregtheit mal abgesehen), in der Prof. Köbler
auch selbst gern mal eine Weile über den Stoff nachdenkt
bevor er weiterfragt. Falls man anfängt in ungewollte
Richtungen zu erzählen, wird man rechtzeitig zurückgewunken
und die Frage neu formuliert. Naja, letztlich hab ich ihn
halt immer gleich mit allem zugequatscht was mir so einfiel.
Beisitzer (wieder Herr Beyersdorff) wieder absolut unauffällig.

= Prüfungsfragen
Allgemein hatte ich mich auf viel mehr Detailfragen und den
ein oder anderen Beweis eingestellt (wobei in der
Kryptologie 1 Prüfung ja auch kaum einer dran war), die
haben aber nicht interessiert. Vielmehr ging es um einen
groben Überblick über sämtlichen Stoff, aus dem er sich dann
ein paar Dinge rauspickte:

* Womit haben wir uns denn beschäftigt? Was sind die
Schutzziele und wie kann man die erreichen? 
* Eine Weile in MDCs herumgestochert, wünschenswerte
Eigenschaften und welche braucht man in welchem Szenario?
(Da rutschte ich schon zu Signaturen, aber da wollte er noch
nicht hin.) Kurz MD4/MD5/SHA-0/SHA-1 und Merkle-Damgård
Konstruktion erwähnt und Idee erläutert, wozu die gut ist
(Übertragung der Kollisionsfreiheit von Kompressionsfunktion
auf resultierenden Hash unter Vorauss. der Suffixfreiheit).
* Schwenk auf MACs, wozu sind die gut, wünschenswerte
Eigenschaft (nennt sich "Berechnungsresistenz", der Begriff
fiel mir nicht ein, aber konnte erläutern was er wohl heißen
mag, also dass selbst bei bel. Rechenresourcen ein Brechen
nur Glückssache ist).
* Angriffe auf MACs: Imp. und Subst. als Spezialfälle.
Abschätzungen der Wahrscheinlichkeiten auf >=1/m und dass
diese "hart" (d.h. erreichbar) sind. Charakterisierung, wann
 diese "Härte" erreicht ist (anhand der
Authentikationsmatrix). Schlüsselraumgröße dabei (linear für
Alpha, quadratisch für Beta). Beziehung der Größen von Text-
und Hashwerträumen, Abschätzung von Lambda im allgemeinen
(da musste ich bissel grübeln). Konkrete Konstruktionsidee
von "perfekten" MACs (für Lambda=1 und allgemein), aber eher
als Kochrezept und Hintergrund, warum das so geht (paarweise
lin. Unabhängigkeit der Klartexte, wenn man sie als d-Tupel
über Z_p baut).
* Was gibt`s noch für Möglichkeiten? Asymmetrie! Paar
Signaturverfahren genannt, Details waren aber nicht gefragt.
Detaillierter ging es dann nur um Undeniable Signatures
(Motivation, Idee), aber weder konkrete Abläufe noch Beweise
 warum das so geht.
* Schluss: PRNGs - was für Ideen gibt es? Was für Kriterien
gibt es, anhand derer man die beurteilen kann? (dst und nbp)
Sind die äquivalent? (fjen) Kurz Lin. Kongruenzgenerator
genannt und warum der so (kryptographisch) schlecht ist.
Dann Idee des BBS-Generators erklärt und Problem, auf dem
der beruht (QR). Schlussfrage war, wie sich QR, Wurzelziehen
und Faktorisieren in Beziehung setzen lassen (und da fiel
ihm dann ein, dass das teils Stoff von Kryptologie 1 war,
Stichwort Rabin-Verfahren).

Das alles mündlich wohlgemerkt, einzig die
Lambda-Abschätzung und das MAC-Bauen schrieb ich skizzenhaft
auf.

= Note (Optional)

1,0

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)

"Super gelaufen! Schnelle Überweisung! Gerne wieder! +++"

Benotung war schon angemessen (haha), aber so wirklich
zeigen was ich wusste konnte ich gar nicht, nur Überblick
geben. Aber man will sich ja nicht beschweren. :) Im Vorfeld
bloß nicht zu viel Stress mit Details machen!

= Datum der Prüfung
Juli 2007

= Benötigte Lernzeit als Empfehlung
2 Wochen recht intensiv, vor allem wenn man noch ein paar
Mathegrundlagen
wiederholen muss (so wie ich)

= Verwendete Materialien (Bücher, Skripte etc...)
* Das Skript (sehr wichtig)
* Buch "Cryptography Theory and Practice" (daran orientiert
sich das Skript)
* Buch "Einführung in die Kryptographie" von Buchmann
(erklärt nochmal ein paar Beweise)
* Buch "Algebraische Grundlagen der Mathematik"

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Sehr angenehm

= Prüfungsfragen
 - Wie kann man Kryptosysteme klassifizieren?
(Substitution/Transposition, Blockchiffre)
 - 4. Kapitel in vielen Einzelheiten: Was sind
Substitutions-Permutationsnetzwerke, wie funktioniert
Lineare Approximation, wie ein Linearer Angriff. Wie kann
man lineare S-Boxen darstellen?
 - Wie ist DES aufgebaut? Was ist die Idee der Feisler-Chiffre? 
 - Wie ist AES aufgebaut?
 - Vergleich symmetrische und asymmetrische Verfahren
 - Wie funktioniert RSA?
 - Angenommen, es wäre ein Algorithmus bekannt, der mir e, d
und n liefert. Wie kann ich damit n faktorisieren?

= Note (Optional)
2.3

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Ich hatte doch leider einige Lücken (insbesondere zu AES
wusste ich nicht viel zu sagen). Prof. Koebler fragt eher
wenige Themen ab, die dann aber in einer großen Detailtiefe.
Die Benotung ist in Ordnung, die Prüfung war anspruchsvoll
aber fair.

= Datum der Prüfung
04/02/1009

= Benötigte Lernzeit als Empfehlung
Mindestens 3 Wochen - man sollte das Skript durchgearbeitet haben!

= Verwendete Materialien (Bücher, Skripte etc...)
Skript von Prof Koebler und viel Wikipedia

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Tolle Prüfungsatmosphäre! Prof Koebler lässt genug Zeit, um Gedanken auszuführen
und weist, wenn man etwas vom Pfad abgekommen ist, wieder auf den richtigen Weg
zurück.
Der Beisitzer hat sich relativ ruhig verhalten und nur ein oder zwei Fragen gestellt.

= Prüfungsfragen
- Stringmatching:
 - Naiver Algorithmus
 - DFA
 - KMP

- Dijkstra - Algorithmus

Zu den Algorithmen musste jeweils die Komplexität angegeben werden. Hierzu
gehört aber nicht einfach nur die Komplexitätsklasse, sondern auch eine genaue
Erklärung über das Zustandekommen. Beiweisen muss man sie nicht.
Wichtig ist auch vor allem Formalität. Es reicht nicht zu erklären, wie zB beim
KMP-Algorithmus die Präfixfunktion arbeitet, man muss sie auch formal exakt
definieren können. Das selbe gilt für alle anderen Algorithmen.

Den Dijkstra Algorithmus sollte ich in Pseudocode angeben und anschließend an einem Beispiel abarbeiten.

Einen Hinweis kann ich euch noch geben: Macht nicht den selben Fehler, wie ich
und bereitet euch auf die Prüfung mit Hilfe der Übungen vor. Sie mögen zwar
eine gute Klausurvorbereitung sein, aber für eine mündliche Prüfung trifft das
nicht zu. Wichtig sind formale Definitionen der Algorithmen und Unterfunktionen,
deren Komplexität und Arbeitsweise.

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Keine gute Prüfung meinerseits. Ich hätte mich selber eine Note schlechter 
gesehen. Die Benotung war also echt angemessen!

= Datum der Prüfung
12.04.10

= Benötigte Lernzeit als Empfehlung
ca. 50 Stunden reine Lernzeit

= Verwendete Materialien (Bücher, Skripte etc...)
nur das Skript

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
ruhige Atmosphäre, man kann alles ausführlich erläutern was man weiß, zwischendurch hatte ich sogar das Gefühl, dass ich zu detailreich erzählt hätte und evtl. Prof Köbler auf etwas ganz anderes wartet. Darüber bin ich mir auch nach der Prüfung nicht ganz sicher, da es diesbezüglich keine Rückmeldung gab, also zumindest wird es an der Note nichts geändert haben.
Beisitzer war Sebastian Kuhnert, führte nur Protokoll, stellte selbst keine Fragen

= Prüfungsfragen
Erzählen Sie was über die klassischen Verschlüsselungssysteme? (additive, multiplikative, affine Chiffre, Hill-Chiffre, Vigenere-Chiffre, andere Stromchiffren, auch Autokey) Habe alle genannt, wie man ver- und entschlüsselt erläutert, wie man sie brechen kann, was Vor- und Nachteile sind, bei Vigenere-Chiffre auch zur Kasiski-Methode (erläutert) und zum Koinzidenzindex gekommen (definiert, erklärt, was er anschaulich heißt und wie man damit die Schlüssellänge bestimmt).
Was sind Maße für die Sicherheit von Kryptosystemen? Wahrscheinlichkeitsbegriff definiert, bedingte Wahrscheinlichkeit und absolute/informationstheoretische Sicherheit damit erläutert.
Beispiele für absolut sichere Systeme?
Welche Sicherheitsbegriffe gibt es noch und was ist ein Maß dafür?
Da wollte ich dann über den Vorteil, den ein Gegner haben kann, anfangen, wurde allerdings ausgebremst und war mir dann leider gar nicht mehr sicher, was denn gemeint sein könnte. Habe dann nachgefragt, ob vielleicht die Entropie gemeint ist, war aber auch nicht so. Die gewollte Antwort war hier letztendlich die Eindeutigkeitsdistanz. 
Dann noch ziemlich kurz zu modernen Kryptosystemen: rasch den Algorithmus von AES skizziert und erklärt wie RSA funktioniert (auch nur sehr skizzenhaft, weil die Zeit schon rum war)


= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Ich kann mich den vorherigen Protokollen überhaupt nicht anschließen, gerade die letzten Kapitel zu DES/AES und den asymmetrischen wie RSA und Rabin wurden so gut wie gar nicht abgefragt, obwohl ich mich da ziemlich gut darauf vorbereitet hatte und auch alle Beweise parat hatte. Daher war ich auch entsprechend überrascht in der Prüfung. Das Hauptaugenmerk lag vor allem auf den Kapiteln 1-3 (klassiche Kryptosysteme, deren Klassifizierung und Analyse, sowie Sicherheitsbegriffe), Kapitel 4 und 6 (SPN-Systeme, deren Analyse, sowie Angriffsstrategien) wurden völlig ausgelassen und Kapitel 5 (DES/AES) und 7 (RSA/Rabin) und in sehr groben Grundzügen. Im Großen und Ganzen war die Benotung okay, etwas schlechter als erwartet, da anscheinend das mit der Eindeutigkeitsdistanz ziemlichen Abzug gab.

= Datum der Prüfung
Sommersemester 2010

= Benötigte Lernzeit als Empfehlung
1 Woche (geht auch kürzer wenn man gut mitarbeitet)

= Verwendete Materialien (Bücher, Skripte etc...)
-Skript der Vorlesung (SS2010)
-ganz wenig Krypto1 Skript (WS0910) zum wiederholen
-ganz wenig Douglas Stinson "Cryptography" 2. Auflage, die 3. Auflage ist wohl deutlich hilfreicher

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
locker, nett

= Prüfungsfragen
-Klassifizieren von Hashverfahren
-Unterschied zwischen MDCs, MACs und Signaturverfahren
-Anforderungen an MDCs, MACs
-Merkle-Damgard
-Erfolgswk. für Impesonation
-2-universalität, einmal den nichtkomprimierenden affinen Hash, und dann den komprimierenden
-Pseudozufallsgeneratoren was ist das, Bsp.
-Sicherheitskriterien (eps-Unterscheider)
-Erfolgswk. eines optimalen Unterscheiders (die ist 1-2^(k-l) wenn der Zufallsgen. f:{0,1}^k->{0,1}^l ist)

Aus Zeitgründen bei mir keine Signaturverfahren.

= Note (Optional)
wesentlich besser als ich dachte

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Nette Prüfung, gern wieder zu einem anderen Thema.
Benotung meiner Meinung nach eher zu gut als zu schlecht. (Aber man will sich ja nicht beschweren.)

*Rächtshreipvehler sint kostenlohß.

= Datum der Prüfung
26.11.2010
= Benötigte Lernzeit als Empfehlung
4 Wochen(intensiv)
= Verwendete Materialien (Bücher, Skripte etc...)
Schöning + Script
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
entspannte und lockere Atmpsphäre, wenn man nicht weiter wusste, gabs schnell ein Tip
= Prüfungsfragen
1)Chomsky
2)Beispiel für jeden Typ von G
3) Einschränkunger für Typ 0, u -> v
4)bei mir, Schwerpunkt auf TM, entscheidbarkeit, berechenbarkeit, H / K, 
musste zeigen, dass H el. RE
dann war die zeit schon vorbei
= Note (Optional)
2.0, hab mich aber schlechter eingeschätzt(erste mündliche Prüfung meinerseits)
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
kann ich nur empfehlen :)

Empfohlene Vorbereitungszeit: 2 Wochen.

Lernmaterial: Prof. Köbler stellt ein ausgezeichnetes Skript zur Verfügung, dessen Inhalte anscheinend den Prüfungsthemenrahmen stecken. In den Übungen wird noch einmal sehr viel mehr Stoff behandelt (auch fast wie Vorlesung) der aber glücklicherweise anscheinend nicht prüfungsrelevant ist.

Die Atmosphäre war entspannt, Herr Köbler hält die Gesprächszügel eher locker. Hier heißt es selbstbewusst sein und den Themen, in denen man sich auskennt, selbst Raum einräumen. Generell zählen die Ideen, wohingegen die exakte Wiedergabe von Definitionen und Algorithmen nicht gefordert wurde.

Insgesamt wurden zwei von den drei bis vier Haupt-Themengebieten der Vorlesung abgefragt. Was die Algorithmen betrifft, muss man auf jeden Fall auch zur Korrektheit und Laufzeit Auskunft geben können. Denn tendenziell ist es eine Theorie-Vorlesung.

Es gab zunächst eine einfache Einstiegsfrage, aber es wird auch bis in die schwierigen Ecken gefragt, wobei aber wirklich die Ideen zählen. Wenn man also den Stoff gründlich verstanden hat, muss man nicht auch noch spezifische Notation oder Pseudocode auswendig lernen.

Insgesamt eine sehr angenehme Prüfung.

=mündlich/schriftlich
schriftlich, 120 Minuten Zeit
= Datum der Prüfung
21.2.2014
= Benötigte Lernzeit als Empfehlung
(kann ich schwer einschätzen)
= Verwendete Materialien (Bücher, Skripte etc...)
Alles außer Kommunikationsmitteln
= \"Atmosphäre\" der Prüfung / Verhalten der Beisitzer
(war schriftlich)
= Prüfungsfragen
https://www.dropbox.com/s/34e9fgpcg8kw29r/ETI-Klausur%2014.pdf

falls der Link nich mehr stimmt: hier grob die Aufgaben

1. Aufgabe: (35 Punkte)
NFA war gegeben
a) sind bestimmte Wörter enthalten?
b) umwandeln in DFA
c) DFA minimieren
d) sind Paare von Wörtern in Relation RL enthalten?
e) Repräsentantensystem aufstellen
f) minimalen regulären Ausdruck angeben

Aufgabe 2: (40 Punkte)
2 Typ-2-Grammatiken gegeben (die 2. war abgewandelt von der ersten)
a) explizite Beschreibung angeben
b) beweisen, dass 1. Sprache nicht regulär ist
c) 2. Grammatik in CNF umwandeln
d) CYK durchführen
e) PDA aufstellen

Aufgabe 3: (10 Punkte)
finde Sprachklasse C so dass jeweils die Eigenschaften erfüllt sind: 
( c= ... ist Teilmenge von)
a) C c= P und co-C != C
b) C c= co-RE und co-C = C
c) C c= RE und co-C != REC \\ C
d) C c= REG und co-C = REC \\ C
e) C c= REC und co-C = REC \\ C

Aufgabe 4: (10 Punkte)
monotone Klausel ist eine Klausel, in der nur Variablen mit <oder> Verknüpft sind, eine antimonotone Klausel ist eine Klausel, in der nur negierte Variablen mit <oder> verknüpft sind, sind die folgenden KNF-Formeln F effizient lösbar(in P) oder nicht effizient lösbar(NP)?
a) F enthält nur monotone Klauseln
b) F enthält keine monotone Klauseln
c) F enthält nur monotone oder antimonotone Klauseln

Aufgabe 5: (25 Punkte)
Graph gegeben
bestimme Stabilitätszahl, Chromatische Zahl, Matchingzahl, Cliquenzahl, minimale Kantenüberdeckungszahl und begründe
wieviele Kanten muss man für Eulerpfad/tour, Hamiltonpfad/kreis hinzufügen, begründe

= Note (Optional)
--
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
--

= Datum der Prüfung
25.02.14

= Benötigte Lernzeit als Empfehlung
Eine Woche, bei regelmäßigem Besuch der Vorlesung

= Verwendete Materialien (Bücher, Skripte etc...)
Skript, Wikipedia

= \"Atmosphäre\" der Prüfung
Sehr entspannt. Herr Köbler lässt einem bei den meisten Fragen genug Zeit, um auf den richtigen Ansatz zu kommen, hilft aber auch aus, wenn man gerade nicht weiter weiß.

= Prüfungsfragen
Die Fragen gingen eher in die Tiefe als in die Breite, weshalb man sich in allen behandelten Themen gut auskennen sollte.
Folgende Themen wurden bei mir abgefragt:

1. Symmetrische und Asymmetrische Kryptografie:
- Formal Definieren, Praktische Unterschiede aufzeigen (symmetrische Kryptografie ist schneller, dafür muss man aber einen vertraulichen und authentischen Schlüsselaustausch gewährleisten. Bei asymmetrischer Kryptografie reicht für jede Richtung ein authentischer Kanal, Vertraulichkeit ist bei der Schlüsselweitergabe nicht nötig.)

2. Sicherheitsbegriffe:
- Informations- und Komplexitätstheoretische Sicherheit definieren
- Erklären, welche Sicherheitsbegriffe auf asymmetrische Kryptosysteme zutreffen (Absolute Sicherheit nie, Komplexitätstheoretische Sicherheit nur bei randomisierten Kryptosystemen)

3. Moderne symmetrische Kryptosysteme:
- Erklären, nach welchem Prinzip die S-Box bei AES funktioniert (Invertierung im endlichen Körper)
- Lineare Approximation einer S-Box und den linearen Angriff auf ein SPN im Detail erklären
- Das Prinzip hinter der differentiellen Analyse erklären (Hier wurden nicht so viele Details gefragt)

4. Asymmetrische Kryptosysteme:
- RSA erklären, Ver- und Entschlüsselungsfunktion definieren
- Zeigen, wie der Klartext ohne den privaten Schlüssel berechnen lässt, wenn man n faktorisieren kann und darauf hinweisen, dass die Umkehrung nicht gilt. 
- Wenn der private Schlüssel d bekannt ist, lassen sich p und q wiederum bestimmen. Den Algorithmus (RSA-Factorize) erklären und die Korrektheit beweisen (also dass die Ausgabe immer ein Teiler von n ist, NICHT mit welcher Wahrscheinlichkeit der Algorithmus erfolgreich ist)
- Ein Kryptosystem nennen, das ähnlich wie RSA funktioniert, bei dem aber die Bestimmung des Klartextes mindestens so schwer wie die Faktorisierung ist (Rabin-System) und diese Sicherheit auch beweisen (also Rabin-Factorize erklären und die Korrektheit beweisen)

= Note
1.0

= Fazit
Anspruchsvolle, aber faire Prüfung. Die beiden Korrektheitsbeweise basierten auf dem Lemma 131 aus dem Skript und waren dann eigentlich Einzeiler, wenn man sie bei der Vorbereitung verstanden hat und einigermaßen sicher mit Kongruenzen umgehen kann. Bei manchen Fragen war ich mir nicht sofort sicher und brauchte weitere Hinweise, was sich aber nicht negativ auf die Note ausgewirkt hat. Ich denke deshalb, dass es Herrn Köbler wichtiger ist, dass man die Themen verstanden hat und die richtigen Schlussfolgerungen ziehen kann, auch wenn einem nicht alle Details sofort einfallen.

= Datum der Prüfung
19.02.2016

= Benötigte Lernzeit als Empfehlung
1 Woche

= Verwendete Materialien (Bücher, Skripte etc...)
Skript

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
locker aber konzentriert

= Prüfungsfragen
- Wörter eines (gegeben) NFAs entscheiden und den Automaten in einen DFA umwandeln
- Einen DFA minimieren, Relationen angeben, Repräsentantensystem
- Zeigen das eine Sprache nicht regülär ist, Pumpingzahl einer Sprache finden
- PDA zu Grammatik und in CHompskynormalform umwandeln
- Typ-1 Grammatik zu einer Sprache finden
- Aussagen zu Sprachen bezüglich Schnitt etc entscheiden
- Aussagen bezüglich entscheidbarkeit entscheiden
- Reduktion
- Graphenprobleme (Matching, Färbarkeit, Eulertour...)

= Datum der Prüfung
22.02.16

= Benötigte Lernzeit als Empfehlung
eine Woche hat mir knapp gereicht, 2 wären besser gewesen

= Verwendete Materialien (Bücher, Skripte etc...)
nur das Script

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Enstpannte Prüfung, Prüfer und Beisitzer haben beide Fragen gestellt und geholfen

= Prüfungsfragen

1) -Wie kann man Kryptosysteme Klassifizieren? (Substitution, permutation, Blocktransposition, ein Satz zu 
    jedem hat gereicht)
   -Wie kann man die Sicherheit von KS klassifizieren? (absolut, komplexitätstheoretisch sicher)
   -Welche komplexitätstheoretisch sicheren KS kennen sie? (wusste nur das OTP)
   -Sind komplexitätstheoretisch sichere KS immer absolut sicher? (ja hat gereicht)
   -Wie kann man KS noch klassifizieren?(symetrisch, asymetrisch)
   -Was ist der Vorteil von asymetrischen KS?(Schlüssel nur unter Authentifizierung übertragen werden, nicht 
    unter Geheimhaltung)

2) -AES grob erklären
   -gegen welchen Angriff wurde AES speziel designt? (Differentielle Kryptoanalyse)
   -Differentielle Kryptoanalyse erklären

3) -RSA erklären
   -wieso ist D((d,n), E((e,n),x)) = x? (x^ed = x beweisen, hier war ihm auch die Ausnahme x mod n = 0 wichtig
   -Wie kann man mit Kenntnis von e und d n faktorisieren? (RSA factorize erklären)
   -wieso ist b^2 = 1 irgendwann erfüllt? (v vielfaches von p-1 und q-1 -> kleiner satz von Fermat auf a^v 
    mod n)

= Note (Optional)
1,7

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
faire Prüfung, war nicht schlimm wenn, man mal ein paar Sachen verwechselt oder eine Frage falsch versteht. Es war auf jeden fall wichtig, nicht nur zu wissen, was gemacht wird, sondern auch wieso. Benotung war angemessen. 

= Datum der Prüfung
August 2016

= Benötigte Lernzeit als Empfehlung
Ich habe drei Tage intensiv gelernt. Es reicht, um oberflächlich Bescheid zu wissen,
aber man sollte mathematisches Grundlagenverständnis mitbringen (d.h. Matrizen, endliche Gruppen, etc.).
Bestehen kann man damit dann gut, aber für eine sehr gute Note sollte man vielleicht noch
etwas tiefer in die Materie tauchen.

= Verwendete Materialien (Bücher, Skripte etc...)
Vorlesungsskript, Wikipedia

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Anfangs sehr entspannt, aber es wurde auf Fragen beharrt, ohne Möglichkeit zu geben, bei anderen
Themen zu glänzen. Nach 40 Minuten fragte Herr Köbler den Beisitzer, wieviele Minuten bereits um wären.
Auf die Antwort "gut 40 Minuten" war die Reaktion, das nächste große Thema betrachten zu wollen.
Da habe ich ihn dann gestoppt - 40 Minuten sind bereits 10 zuviel. Da sollte man also aufpassen,
sonst geht die Prüfung sicherlich gut und gerne doppelt so lange wie vorgesehen.

= Prüfungsfragen
- MAC:
  * Was macht man? Wozu?
  * Welche Angriffe sind möglich? Wie hoch sind die Wahrscheinlichkeiten?
  * Wie lassen sich diese Wahrscheinlichkeiten erreichen, bzw. wie erzeugt man einen MAC mit optimalen Bedingungen?
    (Hierbei wurde sehr intensiv auf die zugrundeliegende Mathematik eingegangen, d.h. wie könnte eine solche
    Hashfunktion aussehen? Wie beweist man die Optimalität? (voller Rang in Matrix) Wie kann man den Textraum erweitern (und mit welchen Werten genau)?
    Wie sieht die Matrix dann aus? Warum gilt das?)
- Hashfunktionen:
  * Welche Anforderungen stellt man an diese? Wie stehen diese im Zusammenhang?
  * Wie sehen Angriffe auf die Hashfunktionen aus, die diese Eigenschaften nicht erfüllen?

= Note (Optional)
2.0

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Ich war sehr erstaunt über die bewusste Überschreitung der Zeit. Außerdem wurde auf einzelne Details eingegangen,
die mir eher unrelevant erscheinen im Vergleich zu allgemeineren Konzepten. In der Tiefe konnte ich ein paar Fragen nicht beantworten und dafür erscheint mir die Note angemessen.

= Datum der Prüfung
24.02.2017

= Benötigte Lernzeit als Empfehlung
Ich habe eine Woche lang jeden Tag etwa 6-8h gelernt, allerdings einige Themen ausgelassen. Daher empfehle ich etwa 2 Wochen, je nachdem wie gut man die Übungen erledigen konnte

= Verwendete Materialien (Bücher, Skripte etc...)
Ich habe mir die wichtigsten Automaten, Algorithmen etc. auf ca 10 Seiten zusammengefasst und mitgenommen. Erlaubt war aber alles außer Bücher und elektronische Hilfsmittel.

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Typische Prüfungsstimmung. Zu Anfang wurde jede einzelne Frage vorgelesen und es konnten Fragen gestellt werden, was ich als sehr angenehm empfand.

= Prüfungsfragen
1) 13pt
Gegeben: zwei DFAs (wie im Skript, nur a's und b's vertauscht)
-Explizite Beschreibung und regulären Ausdruck für beide DFAs angeben
-Aus beiden DFAs einen Automaten für den Schnitt konstruieren
-Einen DFA für die Vereinigung angeben, der höchstens 4 Zustände hat

2) 18pt
Gegeben: ein DFA
-DFA minimieren
-Repräsentantensystem für die Nerode Relation angeben
-4 unterschiedliche Wörter der Länge 4 welche bezüglich der Nerode Relation zu einem gegebenen Wort äquivalent sind

3) 15pt
Gegeben: eine Sprache
-Typ-0 Grammatik angeben
-PDA angeben
-DTM angeben

4) 22pt
Gegeben: 2 Sprachen und eine Definition (welche im Skript steht) als Hilfestellung
-Eine eindeutige Typ-2 Grammatik für eine Sprache angeben und den Syntaxbaum für ein Wort
-Mithilfe eines gegebenen Wortes zeigen, dass die andere Sprache nicht Kontextfrei ist
-Zwei Aufgaben vom Typ „gibt es eine Sprache die mit Schnitt einer der gegebenen Sprachen in einer bestimmten Klasse ist“

5) 10pt
Gegeben: 2 Sprachen
-Für jede Sprache begründen ob sie entscheidbar ist oder nicht

6) 10pt
Für zwei Probleme angeben ob sie in P liegen oder NP-hart oder co-NP-hart sind

7) 26pt
Gegeben: ein Graph
-4 Parameter bestimmen (max-Clique, min-färbung, max-Matching und min-Knotenüberdeckung)
-für 2 Subgraphen entscheiden ob es einen Homomorphismus gibt

8) 6pt
-Gebe einen Graphen mit 8 Knoten an, dessen maximales Matching 1 ist
-Gebe einen Graphen mit Hamiltonpfad, aber ohne Eulerlinie an

= Note (Optional)
Noch nicht korrigiert

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Prüfung schien einfacher als die Übungsaufgaben. Viele „leichte“ Punkte (DFA, Graphen), wenig Punkte für „komplexere“ Aufgaben. Etwas knappe Zeit (habe 2 Aufgaben nicht gemacht und war trotzdem erst kurz vor Ende fertig). Angemessene Benotung kann ich noch nicht beurteilen.

= Datum der Prüfung
24.02.2017
= Benötigte Lernzeit als Empfehlung
-4 Wochen
= Verwendete Materialien (Bücher, Skripte etc...)
-das Skript (sehr gut)
-die Vorlesungsfolien(das selbe wie das Skript nur bunter)
-die Übungsaufgaben
-die Klausuren der letzten Jahre
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
angenehm
= Prüfungsfragen
ist 2018 wahrscheinlich die Probeklausur
= Note (Optional)
4,0
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Auch wenn man sich immer auf alles vorbereiten soll, waren diese Aufgaben komplett anders als die Jahre zuvor, deshalb sehr überraschende Prüfung

= Datum der Prüfung
05.04.2017
= Benötigte Lernzeit als Empfehlung
4 Wochen
= Verwendete Materialien (Bücher, Skripte etc...)
Skript und Übungsaufgaben
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
angenehm
= Prüfungsfragen
1) 20 Punkte
Gegeben ein NFA
- Wörter entscheiden, Automaten in einen DFA umwandeln und äquivalenten Ausdruck angeben
2) 19 Punkte
Gegeben ein DFA
- Minimierung und 2 disjunkte Repräsentatensysteme für die Nerode-Relation
3) 16 Punkte
Gegeben Grundmenge und Relationen
- Finden zusätzlicher Parre zur Erfüllung bestimmter Eigenschaften
- Ordnung nestimmen
- Relation zur Herstellung von Isomorphie bestimmen
4) 35 Punkte
Gegeben eine CNF-Grammatik
- CYK-Algorithmus
- PDA konstruieren
- Beweis der Kontextfreiheit
- Pumping-Lemma anwenden
5) 10 Punkte
Gegeben 2 Sprachen
-Für jede Sprache begründen ob sie entscheidbar ist oder nicht
6) 10pt
Für zwei Probleme angeben ob sie in P liegen oder NP-hart oder co-NP-hart sind
7) 10 Punkte
2 Graphen mit best. Eigenschaften angeben
= Note (Optional)
3,7
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Prüfung schien einfacher als die Übungsaufgaben, aber Zeit sehr knapp bemessen

= Datum der Prüfung
27.2.2018

= Benötigte Lernzeit als Empfehlung
Ich habe 2-3 Tage intensiv gelernt, habe aber die Übungsbeispiele größtenteils gar nicht verstanden (hatte eine sehr gute Gruppe)
Da ich generell sehr schnell lerne und an diesen Tagen durchschnittlich 8h gelernt habe würde ich allerdings ein paar Tage mehr einplanen.

= Verwendete Materialien (Bücher, Skripte etc...)
Ich habe nur das Skript gelesen und mir zu den diversen Verfahren (RSA, AES, etc.) YouTube Videos angesehen. Das Buch von Stinson sollte aber auch helfen.

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Bei der Prüfung waren Köbler und Fuhlbrück. Köbler hat versucht ein Gespräch aufzubauen, da ich aber kein allzu tiefgründiges Wissen hatte war dies leider nicht der Fall. Fuhlbrück hat oft geholfen und auch versucht es angenehm zu gestalten.

= Prüfungsfragen
Kryptosysteme allgemein (Klartext-, Kryptotextraum, a-/symmetrische Schlüssel, etc.)
Sicherheit (absolut sicher, kompl.th. sicher, etc; auch Vorteil von Gegner)
Dann durfte ich mir irgendein Verfahren aussuchen, (was ich sehr nett fand) habe DES genommen da wurde alles dazu gefragt
Zum Abschluss noch RSA, hat er ganz detailliert gefragt (inkl. RSA-Factorize)

= Note (Optional)
3.0, war sehr fair hatte wie gesagt zwar Wissen über fast alle Themen habe aber nirgends wirklich vertiefend gelernt

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Alles in allem voll OK, leider hatte ich das Gefühl, dass die beiden bald einschlafen, da sie wahrscheinlich schon zig andere Prüfungen an dem Tag hatten.

= Datum der Prüfung
= Benötigte Lernzeit als Empfehlung
4 Wochen
= Verwendete Materialien (Bücher, Skripte etc...)
Skript, Folien (WS17/18), Theoretische Informatik kurzgefasst (Uwe Schöning), 
https://www.youtube.com/user/leifaktor
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Sehr entspannt. Prof. Dr. Köbler gestaltet die Prüfung ruhig, aber anspruchsvoll. Wenn man mal nicht weiterkommt, wird mit kleinen Denkanstößen geholfen. Dr. Kössler war Protokollant und hat sich bis auf ein Kopfnicken bei korrekten Antworten sehr unauffällig verhalten. Das gelernte Wissen muss ggf. auf einem Blatt Papier formal korrekt aufgeschrieben werden und auf die Korrektheit wird sehr geachtet. Also nicht nur einfach auswendig lernen, sondern auch verstehen, warum man z.B. bei Produktionen mit -> arbeitet und bei Ableitungen von Wörtern mit => (wie unterscheiden sich diese beiden Relationen voneinander?)
= Prüfungsfragen
Die mündliche Prüfung verläuft wohl immer relativ ähnlich. Zuerst geht es durch gesamte Chomsky-Hierachie, angefangen mit den einzelnen Sprachtypen, später dann zu Berechenbarkeitstheorie (wenn man soweit kommt).
Regulären Sprachen (Typ-3):
-Reguläre sprachen wie haben wir diese in der VL definiert? (Charakteristika)
-Beispielsprache selbst überlegen (a*b*), die reguläre Grammatik aufstellen (welche Einschränkungen gibt es hier?(u -> v; u € V, v € SIGMA V ∪ SIGMA ∪ {epsilon}; A->aB, A->a, A->epsilon), den dazugehörigen DFA konstruieren, wie kann man hier die Korrektheit zeigen?
-Wie sieht die Sprache aus, die von einem DFA erkannt wird? (L(M)={...})
-Ist der Automat minimal? Woran erkennt man das? -> Äquivalenzklassen/Nerode Relation definieren und erklären, warum die Anzahl der Zustände minimal ist.
Kontextfreie Sprachen (Typ-2):
-Wie wurde CFL in der VL definiert? (Charakteristika)
-Kontextfreie Grammatiken, welche Einschränkungen gibt es hier? Beispiel für eine Kontextfreie Grammatik geben (a^n b^n), wie sieht die Grammatik aus? 
-Wie sieht die Sprache aus, die von einer kontextfreien Grammatik erkannt wird? (L(G)={...})
Kontextsensitive Sprachen (Typ-1):
-Wie wurde CSL in der VL definiert? (Charakteristika) 
-Einschränkungen von CSG (|u|<=|v|)
-Tupelbeschreibung für LBA, wie sieht die Bedingung aus, damit eine NTM ein LBA ist?
-Wird bei der Übergabe des Wortes an den LBA nur das letzte Zeichen markiert? Warum nicht das Erste?

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Da es hier noch keine (bis auf alte Prüfungen; Theoretische Informatik 2) Gedächtnisprotokolle zu mündlichen Prüfungen in EThI gibt (3. Versuch), füge ich das hier mal hinzu, damit anderen Leuten etwas die Angst vor dem Ungewissen genommen wird. Die Prüfung ist sehr machbar und man merkt, dass es Prof. Dr. Köbler wichtig ist, dass der Student die Prüfung besteht. Wie die älteren Protokolle bereits gesagt haben, muss man sehr fit im Umgang mit der formellen Schreibweise sein. In dieser Prüfung kam nichts zu Berechenbarkeit oder Komplexität ran. Je schneller man die Fragen beantwortet, desto weiter geht es im Stoff und desto besser wird auch die Note. Wenn man mal irgendwo hängt, dann wird dieses Thema nicht übersprungen, sondern durch Hilfestellungen versucht, einen noch auf den richtigen Gedanken zu lenken. Wenn man die Maschinenmodelle verstanden hat (Tupelschreibweise, Startkonfiguration, Folgekonfiguration, akz. Sprache, etc.), Algorithmen wie Potenzmengenkonstruktion/DFA Minimierung (wie verändern sich hier die Tupel?), Beispiele für alle Typen der Chomsky-Hierachie (Maschinenmodelle für Beispielsprachen, Grammatiken für diese Sprache etc.), dann muss man sich kaum Sorgen machen vor der Prüfung. Viel Erfolg!!

= Datum der Prüfung
28.02.19
= Benötigte Lernzeit als Empfehlung
4 mal 4,5h. Allerdings lag die Vorlesung bei mir schon ein Jahr zurück, hatte im ersten Semester nicht mitschreiben können. 
= Verwendete Materialien (Bücher, Skripte etc...)
Übungsaufgaben und alte Probeklausuren
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
angenehm, konzentriert.
= Prüfungsfragen
1) Grammatik G gegeben (30 Punkte)
a) NFA N zur Grammatik erstellen
b) NFA N', der L(N)* als Srpache hat
c) N zum DFA machen
d) regulären Ausdruck für L(G) angeben
e) andere Sprache gegeben, dafür Minimal-DFA angeben und Index der Nerode-Relation angeben

2) Menge A gegeben mit Relation R (11 Punkte)
a) Zeigen, dass Schnitt einer Äquivalenzrelation mit Ordnung ebenfalls eine Ordnung ist
b) Hasse Diagramm von R
c) Supremum/Infimum einer Menge bzgl R

3) 16 Punkte Zeigen oder Widerlegen
a) Für beliebige A, B e DCFL gilt (A Komplement vereinigt B Komplement)* e NP
b) Es gibt ein GOTO-Programm P, das die Funktion f(n)=2^n berechnet und für jede Einfaben n höchstens n Befehle ausführt
c) PCP-Instanz hat eine Lösung
d) f, g, h totale Funktionen von {0,1}* nach {0,1}* mit h(x) =f(x)g(x) (Konkatenation)
Falls dann f und h berechenbar sind, ist auch g berechenbar

4) 21 Punkte, kontextfreie Grammatik gegeben
a) Grammatik in CNF umwandeln
b) Entscheiden ob andere Sprache kontext frei ist oder nicht
c) Entscheiden ob andere Sprache kontext frei ist oder nicht

5) Für jede der Sprachen entscheiden ob entscheidbar, semi-entscheibar oder nicht semi-entscheidbar.  Begründen. w jeweils aus {0,1}*. 12 Punkte.
a) Es gibt ein x aus {0,1}*: |x|<=|w| und Mw(x) hält nicht innerhalb von |w| Schritten ("<=" soll kleiner gleich sein)
b) Es gibt ein x aus {0,1}*: Mw(x) hält nicht innerhalb von |w| Schritten
c) Es gibt ein x aus {0,1}*: Mw(x) hält nicht 

6) 2 Graphen G, H gegeben, 30 Punkte
a) Zeigen dass G und H nicht isomorph
b) Zeigen dass isomorphe Graphen entstehen wenn je ein gegebener Knoten entfernt wird
c) 4 Cliquen angeben, die G komplett abdecken
d) Cliquenzahl und Stabilitätszahl von G angeben
e) CliqueFREE(G,k,l): Gibt es eine Knoten-Teilmenge der Größe |l| die keine Clique der Größe K als Teilmenge hat? Für 3 Instanzen entscheiden ob ja oder nein
f) Zeigen, dass CliqueFREE NP-hart und co-NP-hart ist indem sie zeigen dass sowohl IS als auch Komplement von CLIQUE in Polynomialzeit auf CliqueFREE reduzierbar sind
g) Geben sie mit Begründung jeweils an, ob G einen Hamiltonpfad bzw, Hamiltonkreis enthält

= Note (Optional)
2,0

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
In der Klausur wird viel mehr Grundlagenwissen abgefragt, als die Probeklausuren vermuten lassen. Also nicht verunsichern lassen, wenn ihr da irgendwas nicht wisst. In der Klausur habt ihr eh nicht genug Zeit für alle Aufgaben (ich habe z.B. die 6f gar nicht gemacht), da bringt es euch nichts, wenn ihr beim Lernen viel Zeit darauf verwendet, die schwereren Sachen wie z.B. Reduktion zu üben. Lieber NFA/DFA minimieren/umformen und ein bisschen mit Grammatiken üben und das dafür dann sicher und schnell können!
Hatte das Gefühl, dass diese Klausur etwas härter benotet wurde als sonst (und das haben auch die Übungsleiter so ins Forum geschrieben). 41 von ~120 sind durchgefallen, mal sehen ob bei der Klausureinsicht etwas Kulanz gezeigt wird.

= Datum der Prüfung

08.06.2020

= Benötigte Lernzeit als Empfehlung

Hab 2 Wochen Entspannt das Skript gelesen, dann eine Woche Prüfungsprotokolle gemacht, man kann es sicherlich auch mit weniger Lernzeit machen.

Die Prüfungen im Fach "Einführung in die Kryptologie" sind analog zu den Prüfungen in "Kryptologie 1" (so hieß das Fach davor), also hab ich auch mit denen gelernt.

= Verwendete Materialien (Bücher, Skripte etc...)

Skript

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer

Die Prüfung fand über Zoom statt, ich musste meinen Ausweis über die Webcam zeigen (ich weiß nicht was passiert wäre, hätte ich mich geweigert, die Cam anzumachen/wäre sie kaputt). Ich hab die Webcam die ganze Zeit über angelassen, da ich das Gefühl hatte, ich konnte meine Antworten besser rüberbringen, wenn die Prüfer meine Gesten sehen.
Sowhohl Herr Köbler als auch der Beisitzer (Herr Fuhlbrück) hatten ihre Kamera die ganze Zeit über an.
Vor der Prüfung musste ich ihnen bestätigen, dass sich keine andere Person im Raum befindet und ich wurde belehrt, dass ich keine anderen Materialien benutzen dürfe.
Die Prüfung wurde 8 Minuten überzogen.

= Prüfungsfragen

1. Wie ist ein Kryptosystem mathematisch definiert? Was sind Eigenschaften der Ver- und Entschlüsselungsfunktion
2. asymmetrische und symmetrische Kryptosysteme. Wie sind sie definiert, was kann man allgemein über deren Sicherheit sagen (also welche Sicherheitsbegriffe darauf zutreffen). Bei der Frage "Warum sind asymmetische Kryptosysteme nicht absolut sicher" wusste ich nicht weiter. (Die Antwort: Ein IND-CPA Gegner kann einfach beide Texte nochmal verschlüsseln, da der Schlüssel ja öffentlich ist und dann mit Wahrscheinlichkeit 1 sagen, welcher Klartext verschlüsselt wurde)
3. SPN: Wie ist es allgemein aufgebaut, lineare & differentielle Analyse erklären
4. Ich durfte mir ein asymmetrisches Kryptosystem aussuchen, hab RSA gewählt.
Wie funktioniert es? Warum funktioniert es? Falls der Kryptotext durch p, aber nicht durch q teilbar ist, wie kann man damit n faktorisieren? (Antwort: GGT(Kryptotext, n) ist ja dann größer 1). Was kann man über die Sicherheit von RSA sagen, RSA-Factorize erklären.

= Note (Optional)

1.3

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)

= Datum der Prüfung
12.08.2020

= Benötigte Lernzeit als Empfehlung
mindestens eine Woche für Skript wiederholen und mündliche Prüfung mit den hier vorhandenen Protokollen üben

= Verwendete Materialien (Bücher, Skripte etc...)
Skript, YouTube (intrigano, spannagel, weitz /haw hamburg)

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Fuhlbrück und Köbi waren beide sehr entspannt und ruhig

= Prüfungsfragen
. Formale Definition eines Kryptosystems
. SPN (AES, lineare Approximation, lineare Analyse)
. Unterschied symmetrisch/asymmetrisch Kryptosystem 
. Sicherheitsbegriffe (absolut, komplexitätstheoretisch, nachweisbar, praktisch) und deren Zusammenhänge
. Wie sieht die Sicherheit bei asymmetrischen Kryptosystemen aus, können diese komplexitätstheoretisch sicher sein?
. Unterschied RSA/Rabin und ElGamal 
. Funktionsweise RSA, warum gilt x^(ed) = x mod n beweisen, RSA Factorize erklären (keine Zeit mehr am Ende), Zusammenhang RSA und Primfaktorzerlegung

= Note (Optional)
1.7

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
hab auf Lücke ElGamal überhaupt nicht angeschaut, Benotung daher fair und nette Prüfung

= Datum der Prüfung
12.08.2020 

= Benötigte Lernzeit als Empfehlung
2 Wochen 

= Verwendete Materialien (Bücher, Skripte etc...)
Skript

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
War über Zoom, ich hatte vorher gefragt, ob ich mich mit Tablet +Stift dazu schalten kann und das war erlaubt, was erklären bisschen einfacher gemacht hat

= Prüfungsfragen
- Kryptosystem erklären 
- Dann wollte er wissen, dass E injektiv ist
- asymmetrisch/symmetrisch, zwei Vorteile von asymmetrisch nennen
- zur Sicherheit von asymmetrischen etwas sagen
- Wieso können asymmetrische nicht absolut sicher sein
- Wieso klappt der Angriff bei randomisierten asymmetrischen nicht mehr?
- DES (durfte zwischen DES und AES entscheiden)erklären
- muss die Funktion F in der Feistel-Chiffre injektiv sein?
- wie dechiffriert man
- Welche Art von Angriff für DES?
- Lineare Analyse erklären?
- RSA (durfte mir aussuchen)
- Wie kann man es brechen?
- Wieso ist v ein Vielfaches von (p-1)(q-1)?
- RSA Factorize
- Beweis x^2 kongruent y^2 mod n

= Note (Optional)
2.0

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
 war angemessen, konnte im Grunde alles beantworten, manche Voraussetzungen konnte ich nicht immer sofort nennen, ca. 10 min überzogen