312.258 (17W) Mathematische Analyse von Algorithmen

Wintersemester 2017/18

Anmeldefrist abgelaufen.

Erster Termin der LV
02.10.2017 14:00 - 16:00 , HS 6
... keine weiteren Termine bekannt

Überblick

Lehrende/r
LV-Titel englisch
Mathematical Analysis of Algorithms
LV-Art
Vorlesung
Semesterstunde/n
2.0
ECTS-Anrechungspunkte
4.0
Anmeldungen
9
Organisationseinheit
Unterrichtssprache
Englisch
mögliche Sprache/n der Leistungserbringung
Deutsch , Englisch
LV-Beginn
01.10.2017
eLearning
zum Moodle-Kurs
Anmerkungen

People who analyze algorithms have double happiness. First of all they experience the sheer beauty of elegant mathematical patterns that surround elegant computational procedures. Then they receive a practical payoff when their theories make it possible to get other jobs done more quickly and more economically.     D. E. Knuth

LV-Beschreibung

Intendierte Lernergebnisse

After successful completion of this course, students will know methods and correspondings theorems in (analytic) combinatorics as listed in the contents section below. They will understand and will be able to prove these theorems and will be able to apply these methods to the analysis of algorithms.

Lehrmethodik

Lecture with an emphasis on examples concerning the analysis of algorithms.

Inhalt/e

  1. Introduction. Example: Sorting algorithms.
  2. Generating Functions (Review and Advanced Techniques)
  3. Mellin Transform and Mellin-Perron Summation
  4. Singularity Analysis
  5. Saddle-Point Method
  6. Limiting Distributions (Overview)

Erwartete Vorkenntnisse

Basic knowledge on generating functions is useful, a review will be given at the beginning of the course. Complex analysis is an important tool.

Literatur

Prüfungsinformationen

Prüfungsmethode/n

Oral exam

Prüfungsinhalt/e

Contents of the lecture.

Beurteilungskriterien/-maßstäbe

  • The grade is obtained by a single oral exam (45 minutes), until November 30th, 2018.
  • For the oral exam, you may bring copies of the slides of the lecture (containing formulae) and additional cheat-sheets containing formulae. How much and what you look up influences the grade.

Beurteilungsschema

Note/Grade Benotungsschema

Position im Curriculum

  • Masterstudium Technische Mathematik (SKZ: 401, Version: 13W.1)
    • Fach: Diskrete Mathematik (Wahlfach)
      • Mathematische Analyse von Algorithmen ( 2.0h VO / 4.0 ECTS)
        • 312.258 Mathematische Analyse von Algorithmen (2.0h VO / 4.0 ECTS)

Gleichwertige Lehrveranstaltungen im Sinne der Prüfungsantrittszählung

Diese Lehrveranstaltung ist keiner Kette zugeordnet