6 - Komplexität von Algorithmen/ClipID:10699 previous clip next clip

The automatic subtitles generated using Whisper Open AI in this video player (and in the Multistream video player) are provided for convenience and accessibility purposes. However, please note that accuracy and interpretation may vary. For more information, please refer to the FAQs (Paragraph 14).
Recording date 2013-05-08

Via

Free

Language

German

Organisational Unit

Lehrstuhl für Informatik 8 (Theoretische Informatik)

Format

lecture

  • 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.

Up next

Schröder, Lutz
Prof. Dr. Lutz Schröder
2013-05-10
Free
Schröder, Lutz
Prof. Dr. Lutz Schröder
2013-05-15
Free
Schröder, Lutz
Prof. Dr. Lutz Schröder
2013-05-17
Free
Schröder, Lutz
Prof. Dr. Lutz Schröder
2013-05-22
Free
Schröder, Lutz
Prof. Dr. Lutz Schröder
2013-05-24
Free

More clips in this category "Technische Fakultät"

2024-06-13
Studon
protected  
2024-06-11
IdM-login
protected