Komplexität von Algorithmen 2013

Detailed information

Most recent entry on 2013-07-19 

Faculty

Lehrstuhl für Informatik 8 (Theoretische Informatik)

Recording type

Vorlesungsreihe

Via

Free

Language

German

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

Associated Clips

Episode
Title
Lecturer
Updated
Via
Duration
Media
1
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-04-17
Free
01:30:33
2
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-04-19
Free
01:29:50
3
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-04-24
Free
01:30:18
4
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-04-26
Free
01:26:48
5
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-05-03
Free
01:24:38
6
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-05-08
Free
01:24:08
7
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-05-10
Free
01:21:26
8
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-05-15
Free
01:15:40
9
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-05-17
Free
01:34:00
10
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-05-22
Free
01:29:08
11
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-05-24
Free
01:08:47
12
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-05-29
Free
01:13:23
13
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-05-31
Free
01:19:21
14
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-06-05
Free
01:29:52
15
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-06-07
Free
01:15:44
16
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-06-12
Free
01:31:18
17
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-06-14
Free
01:24:06
18
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-06-19
Free
01:28:10
19
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-06-21
Free
01:21:17
20
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-06-26
Free
01:32:17
21
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-06-28
Free
01:32:38
22
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-07-03
Free
01:16:29
23
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-07-05
Free
01:28:41
24
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-07-10
Free
01:23:07
25
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-07-12
Free
01:28:47
26
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-07-17
Free
01:32:16
27
Komplexität von Algorithmen
Prof. Dr. Lutz Schröder
2013-07-19
Free
01:25:07

More courses from Prof. Dr. Lutz Schröder

Schröder, Lutz
Prof. Dr. Lutz Schröder
2013-07-19
Free
Schröder, Lutz
Prof. Dr. Lutz Schröder
2018-02-07
Free
Schröder, Lutz
Prof. Dr. Lutz Schröder
2015-07-16
Free
Schröder, Lutz
Prof. Dr. Lutz Schröder
2016-02-02
Free
Schröder, Lutz
Prof. Dr. Lutz Schröder
2015-01-29
Free

More courses in this category "Computer Science"

Sieh, Volkmar
Dr. Volkmar Sieh
2013-02-08
Free
Greiner, Günther
Prof. Dr. Günther Greiner
2013-07-17
Studon
Eskofier, Björn
Prof. Dr. Björn Eskofier
2016-02-02
IdM-login
Webkongress
Wolfgang Wiese
2018-09-14
Free
Systemausbildung
Marcel Ritter
2019-07-10
Free / IdM-login / RRZE Intern