24 - Komplexität von Algorithmen [ID:10717]
50 von 527 angezeigt

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.

Teil einer Videoserie :

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.

Einbetten
Wordpress FAU Plugin
iFrame
Teilen