Fragen und Antworten zur Klausur

Wieviel an Begründung wird denn bei den Antworten erwartet?
Das steht normalerweise dabei. Bei Multiple-Choice-Aufgaben braucht man keine Begründung anzugeben. Wenn dabeisteht "Begründen Sie Ihre Antworten", ist auch genau das gemeint. Wie kurz das genau ausfällt, hängt davon ab, wie präzise Sie sich ausdrücken. Verweise auf das Skript oder auf Übungsblätter sind generell erlaubt. Bitte aber keine Verweise auf Klausuren, Skripte oder Übungsblätter vergangener Jahre!
Ich glaube, in der Musterlösung zu Klausur x ist ein Fehler.
Das kann schon sein. Ich habe von vielen alten Klausuren nur die Aufgaben ohne Lösungen und kann deswegen nicht viel zu möglichen Fehlern sagen.
Gibt es ein Rezept für die O-Kalkül-Aufgaben?
Rezepte gibt es generell zu den wenigsten Aufgabentypen. Das einzige, was ich hier zur Vorgehensweise sagen kann, ist folgendes:

Begriffe wie O(n), usw. bezeichnen immer Mengen. Die Aufgaben zum O-Kalkül verlangen normalerweise, dass man eine Beziehung zwischen solchen Mengen nachweist oder widerlegt. Wie man zum Beispiel eine Teilmengenbeziehung beweist, wissen Sie sicher. Häufig erhält man einen Großteil des Beweises schon dadurch, dass man sich die Definitionen der Mengen, um die es geht, klarmacht und dann genau aufzuschreibt, was eigentlich zu zeigen ist.

Wie war das noch mal mit P und NP?
P ist die Menge aller Probleme, die man mit deterministischen Algorithmen in Polynomialzeit lösen kann. NP ist die Menge aller Probleme, die man mit nichtdeterministischen Algorithmen in Polynomialzeit lösen kann.

Sowohl P als auch NP umfassen eine Menge Probleme, die man auch schneller als in Polynomialzeit lösen kann; zum Beispiel das Problem: gegeben eine Zahl x, ist x gerade oder ungerade?
Dass ein Problem in P ist, heißt also nur, dass es von einem deterministischen Algorithmus gelöst wird, dessen Zeitaufwand nicht schneller als polynomial wächst.

P ist eine Teilmenge von NP. Ob P gleich NP ist oder nicht, ist eines der großen ungelösten Probleme der Informatik. Es gibt eine Reihe von Problemen in NP, von denen nicht bekannt ist, ob sie auch in P liegen. Einige von diesen Problemen hängen in dem folgenden Sinn miteinander zusammen: wenn man auch nur von einem dieser Probleme zeigen könnte, dass es in P liegt, wären die anderen auch alle in P. Probleme mit dieser Eigenschaft bezeichnet man als NP-hart. Probleme, die in NP liegen und NP-hart sind, heißen NP-vollständig.

Um nachzuweisen, dass ein Problem NP-vollständig ist, muss man also zwei Dinge prüfen:

  1. Es liegt in NP, das heißt, es gibt einen nichtdeterministischen Algorithmus, der das Problem in Polynomialzeit löst.
  2. Es ist NP-hart, d.h. es hängt mit mindestens einem bekannten NP-vollständigen Problem in der gerade beschriebenen Weise zusammen.
In den Lösungen zu den Aufgaben 3 und 4 von Blatt 4 wird vorgeführt, wie man die entsprechenden Beweise angeht.

Beachten Sie: Es gibt auch oberhalb von NP noch Zeit- und Platzkomplexitätsklassen! Zum Beispiel gibt es Probleme, die Exponentialzeit benötigen. Ein Beispiel ist die Äquivalenz von regulären Ausdrücken.

Gibt es NP-vollständige Probleme, die in P liegen?
Wenn Sie eines finden, ist Ihnen die Professur in Informatik sicher, denn daraus würde folgen, dass P = NP.
Gibt es Probleme, die in NP liegen, nicht NP-vollständig sind und zu denen trotzdem kein deterministischer Polynomialzeit-Algortihmus bekannt ist?
Vielleicht. Ein Beispiel ist die Primfaktorzerlegung. Das Problem ist in NP (man rät eine Primfaktorzerlegung und kann dann in Polynomialzeit nachprüfen, ob sie korrekt ist), aber ein deterministischer Polynomialzeit-Algorithmus ist nicht bekannt. Ebensowenig weiß man, ob das Problem NP-vollständig ist.
Ist es bei der Angabe von endlichen Automaten, regulären Ausdrücken oder kontextfreien Grammatiken nötig, die Anzahl Zustände, Regeln, Symbole, usw. zu minimieren?
Nein. Es gibt einen Algorithmus, um endliche Automaten zu minimieren, aber er kam in der Vorlesung nicht vor. Reguläre Ausdrücke sind ausgesprochen schwierig zu minimieren, und für kontextfreie Grammatiken ist das Problem sogar unentscheidbar.

Lesbarkeit ist natürlich erfreulich, aber letzten Endes zählt die Korrektheit.

Darf man auch nichtdeterministische EA angeben? In den alten Musterlösungen kommen nur deterministische vor.
Selbstverständlich dürfen Sie auch NEA angeben; wenn ich das nicht will, schreibe ich es dazu. In den alten Klausuren kommen deswegen keine NEA vor, weil diese früher nicht behandelt wurden.
Was bedeuten Zustand und Markierung bei Petri-Netzen?
Ein Zustand ist das gleiche wie eine Markierung. Das neueste Skript sollte eigentlich nur noch den Begriff Markierung verwenden. Was eine Markierung ist, steht in Definition 152 auf Seite 113:

Eine Funktion von S (Menge der Stellen) nach N (natürliche Zahlen inklusive 0), die für jede Stelle angibt, wieviele Marken sie enthält.

Kann eine Stelle mehrere Marken enthalten? Das haben wir letztes Semester anders gelernt.
Es gibt für Petri-Netze ungefähr so viele Definitionen wie Wissenschaftler, die sich damit beschäftigen. Für die Übungsblätter und die Klausur maßgeblich sind die Definitionen aus dem aktuellen Skript. Und die besagen, dass eine Stelle mehrere Marken enthalten kann.
Was ist der Unterschied zwischen partiellen und totalen Funktionen?
Die Definitionen finden Sie im Skript auf Seite 18. Eine Funktion f von X nach Y ist total, wenn f(x) fuer alle x aus X definiert ist.
Was bedeutet der Punkt über dem Minuszeichen bei Registermaschinen?
Registermaschinen rechnen nur mit nichtnegativen Zahlen. Das heißt, wenn man mit Registermaschinen 5 - 7 berechnet, kommt 0 heraus. Demnach ist die Subtraktion mit Registermaschinen nicht die, die man von den ganzen Zahlen her gewohnt ist. Um dies zu verdeutlichen, benutzt man ein etwas anderes Symbol, eben das Minuszeichen mit dem Punkt darüber.
Wie findet man gute Schleifeninvarianten?
Ein allgemeines Verfahren gibt es nicht (und kann es auch nicht geben, das Problem ist unentscheidbar). Man sieht sich den Algorithmus an und macht sich klar, wie sich die Variablenbelegung in Iteration n + 1 aus der in Iteration n ergibt. Im allgemeinen gibt es mehrere mehr oder weniger gleich gute Schleifeninvarianten; falls man ungeschickt wählt, hat man eventuell mehr Schreibarbeit, es ist aber kein Fehler.

Eine Heuristik, um Schleifeninvarianten zu finden, ist folgende: Man erstellt eine Tabelle mit so vielen Spalten, wie in der Schleife Variable vorkommen. Dann trägt man in die i-te Zeile der Tabelle ein, welche Werte diese Variablen zu Beginn des i-ten Schleifendurchlaufes haben. Daraus versucht man dann eine Formel zu entwickeln, die beschreibt, wie die Variablen voneinander abhängen. Dies wird zum Beispiel in Aufgabe 1 des zehnten Übungsblattes vorgeführt.

Wie herum 'zählt' man beim Caesar-Chiffre? Heißt 'drei vorwärts', dass A durch D ersetzt wird, oder durch X?
Das ist mir egal. Bei den Aufgaben wird es immer so sein, dass es entweder egal ist oder eindeutig angegeben ist.
Fängt beim Caesar-Chiffre die Nummerierung des Alphabets bei 1 oder bei 0 an?
Das macht keinen Unterschied.
Sind Aufgaben wie 2a) von Blatt 11 nicht unfair denjenigen gegenüber, deren Muttersprache nicht deutsch ist?
Finde ich nicht. Erstens ist es in jeder geschriebenen Sprache der Welt so, dass manche Schriftzeichen häufiger vorkommen als andere; zweitens gibt es auch noch eine Menge anderer Lösungswege. Zum Beispiel: In dem Text zur Aufgabe kommt ein Wort der Länge zwei vor. Falls einem gar nichts besseres einfällt, kann man also immer noch alle Möglichkeiten durchgehen, dieses Wort zu entschlüsseln (und sie gegebenenfalls alle im Wörterbuch nachschlagen).
Ich habe versucht, die Beispielmatrizen zu Hills Kryptosystem zu invertieren und komme nicht auf das richtige Ergebnis.
Haben Sie schon die Fußnote auf Seite 222 gelesen?
Was hat es mit dem 'Satz von Fermat' auf sich, der in der Lösung zu Blatt 10 vom vorletzten Jahr erwähnt wird?
Der ist mir beim copy-and-paste mit auf das Lösungsblatt gerutscht. Der Satz (auch bekannt als 'der kleine Fermat') besagt:

Seien a und p zwei ganze Zahlen. Falls p eine Primzahl ist und p kein Teiler von a ist, dann gilt: a hoch (p - 1) ist kongruent zu 1 modulo p.

Man kann das gelegentlich benutzen, um Modulo-Rechnungen etwas abzukürzen, sollte dann aber prüfen, dass wirklich beide Voraussetzungen erfüllt sind. Beispiel:

7 hoch 4 ist kongruent zu 1 modulo 5, denn

5 ist eine Primzahl und 5 ist kein Teiler von 7.

9 hoch 2 ist nicht kongruent zu 1 modulo 3:

der Satz von Fermat ist nicht anwendbar, denn 3 ist ein Teiler von 9.

Der Satz von Fermat wird auch im Rabin-Miller-Algorithmus verwendet (Skript Seite 228f).

In der Klausur vom Sommersemester 1999 kommen Fragen zu one-time pads und linearen Kongruenzgeneratoren vor, muss man das kennen?
Beide Begriffe kamen in der entsprechenden Vorlesung vor; falls Herr Vollmar sie dieses Mal nicht erwähnt hat, können sie auch nicht in der Klausur vorkommen. Falls es Sie interessiert: one-time pads finden Sie in einem Buch über Kryptographie, und lineare Kongruenzgeneratoren in einem Buch, das Pseudo-Zufallszahlen behandelt.
Im gelben Skript verstehe ich die Beispielautomaten auf Seite 111 nicht.
Das glaube ich sofort, da sind nämlich Fehler drin. In dem oberen Automaten müssen die beiden Zustände rechts akzeptierend sein. In dem unteren Automaten muss an der obersten Kante ein b stehen, an der zweiten ein a, un an der Kante, die vom Startzustand aus nach untern führt, ein b.
Das Skript ist mir zu schwer zu lesen.
Ich behaupte nicht, das Skript wäre perfekt. Wenn Sie einen Fehler gefunden haben oder eine Stelle, die missverständlich ist, dann teilen Sie mir das bitte mit. Wenn Sie aber nur "ganz allgemein" das Skript zu schwierig finden, kann ich Ihnen auch nicht helfen. Da müssen Sie durch.

Kathrin Paschen   paschen@ira.uka.de