Bevor wir zum Material kommen, zwei Dinge vorweg. Erstens Evaluation.
Erfreulicherweise hat es also den meisten, jedenfalls soweit sie an der Evaluation
teilgenommen haben, relativ gut gefallen. Das freut mich. Es gab natürlich
trotzdem kritische Anmerkungen. Ich liste mal die, die sich am meisten
wiederholt haben auf oder die, die am klarsten sind. Also einmal werden
kritisiert über Schneidungen mit BFS. Gut, ich würde sagen, also ich könnte jetzt
so Dinge sagen, wie wir versuchen das stärker auseinander zu halten, aber das
ist natürlich völlig müde, weil wir den Kurs jetzt zum letzten Mal halten. Ich
hatte selber nicht den Eindruck, muss ich sagen, dass es so fürchterlich viele
Überschneidungen gab. Natürlich haben wir die Turing-Maschine nochmal definieren
müssen und wir haben einmal einen Clash gehabt bei NP-Reduktion, glaube ich.
Ansonsten wäre mir jetzt gar nicht so richtig klar, wie viele Überschneidungen
wir da hatten. Ich koordiniere mich natürlich durchaus mit Herrn Wanka, mit
dem ich mich gut verstehe. Es ist jetzt nicht so, dass wir da völlig
nebeneinander herarbeiten. Dann wird darum gebeten, wenn ich an der Tafel was
korrigiere, was ich ja nun gelegentlich mal tue, dass ich dann stärker darauf
hinweise, damit die Leute, die irgendwie noch mit dem Abschreiben hinterher
hächeln, das jetzt in ihre Mitschrift einarbeiten können. Ja, gut. Also sowieso
bitte ich darum, wenn jemand mit dem Nachschreiben nicht nachkommt, ja also
auch in so einer großen Veranstaltung hier bitte brüllen. Also es soll nicht so
sein, dass ich irgendwie an der Tafel irgendwie schon drei Tafeln weiter bin
als sie mit dem Abschreiben. Dann muss da bitte unterbrochen werden. Das
gilt auch noch für den Rest des Semesters. So lang ist er nicht mehr,
aber wenn sie mit dem Abschreiben nicht nachkommen, bitte Bescheid sagen.
Umgekehrt wurde merkwürdigerweise angerichtet, ich sollte effizienter Tafel
wischen, indem ich mehrere Tafeln auf einmal wische. Das würde ich
also lieber nicht tun. In meinen radikaleren Momenten behaupte ich am Anfang
der Vorlesung sollte die Tafel vollgeschrieben sein, damit man am Anfang
schon Wischpausen hat. Ja, dann wird beklagt, es würde zu viel bewiesen.
Daran kann ich in diesem Kurs, wie auch in zukünftigen, nichts ändern.
Ich bemühe mich auch Anwendungen natürlich zu zeigen und müssen aber die
zentralen Statements, die müssen natürlich voll bewiesen werden und es
ist auch eins der Dinge, die Sie hier lernen sollen, wie das geht, da das ja
relativ wenig in Ihrem Studium stattfindet. Das ist natürlich gleichzeitig der Grund,
warum das vielen nicht so leicht vonstatten geht, aber irgendwann muss man
es mal machen. Es wird angeregt, Nummern an Sätzen anzubringen. Das hatte ich auch
im letzten Mal schon. Also das letzte Mal hat das jemand gesagt und ich habe es
daraufhin gemacht. Den Effekt fand ich insgesamt nicht gut. Es ist mir also zu
unspontan. Ich weiß selber nicht mehr, wie die Sätze irgendwie im
Zweifelsfall irgendwann mal nummeriert waren, wenn ich darauf zurück verweisen
will. Ich bin eben nicht latech. Ich bemühe mich, Sätzen sprechende Namen zu
geben. Die fallen mir dann später wieder ein und die finden sie vielleicht auch
wieder. Wie ist das mit der allgemeinen Sichtweise? Ist das also weit verbreitet,
dass die Leute gerne statt Namen Nummern an den Sätzen hätten? Da drüben kommt
ein Ja. Ja gut, das sind zwei. Wer kommt mit den Namen der Sätze gut klar? Das
sind die meisten, würde ich sagen. Das gefällt mir persönlich wesentlich
besser. Zumal ich also irgendwie, wenn ich was einschiebe oder sowas, dann kann ich ja
nicht wie latech dann umnummerieren oder so. Also wenn ich meinem Satz keine
sprechenden Namen gebe, dann sagen sie doch mal Bescheid, dann denke ich mir einen
aus. Also die Sätze, die heute kommen, haben alle Namen.
Presenters
Zugänglich über
Offener Zugang
Dauer
01:23:07 Min
Aufnahmedatum
2013-07-10
Hochgeladen am
2019-04-22 13:09:02
Sprache
de-DE
- Mathematische Hilfsmittel der Algorithmenanalyse: Abschätzung des asymptotischen Wachstums von Funktionen, Summationen, Anzahlen, divide-and-conquer-Rekursionen, etc.
-
Grundbegriffe der quantitativen Algorithmenanalyse: worst-case- und average-case-Analsyse, obere und untere Schranken, Algorithmen- und Problemkomplexität
-
Exemplarische Analysen von Sortieralgorithmen
-
Sortierkomplexität und Entropie
-
Quellcodierung und Datenkompression
-
Komplexität von arithmetischen Operationen und Problemen (Multiplikation, Primtest, Faktorisierung)
-
modulare Arithmetik und schnelle Fouriertransformation
-
Kryptographie und Komplexität
Lernziele und Kompetenzen:
Die Studierenden
-
erwerben fundierte Kenntnisse über die Grundbegriffe der quantitativen Algorithmenanalyse (Laufzeit) und die benötigten mathematischen Methoden
-
verstehen die Komplexität (Laufzeitverhalten) von Standardalgorithmen (z.B. Sortieren, arithmetische Algorithmen) und können deren praktische Bedeutung erklären
-
sind in der Lage, an einfachen, exemplarischen Algorithmen Analysen des worst-case-Verhaltens und des average-case-Verhaltens durchzuführen
-
können exemplarisch Algorithmenkomplexität und Problemkomplexität in Bezug setzen
-
können die Beziehungen zwischen Sortier- und Suchkomplexität und dem Entropiebegriff darstellen
-
erwerben Grundkenntnisse über algebraische Strukturen der Arithmetik und die Komplexität arithmetischer Operationen
-
können die Rolle von Komplexitätsaussagen für die Beurteilung der Sicherheit einfacher kryptografischer Protokoll darstellen
Literatur:
Graham, Knuth, Patashnik, Concrete Mathematics, Addison-Wesley, 1994.
Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, MIT-Press, 2001.
Heun, Grundlegende Algorithmen, Vieweg, 2001.