312.258 (20W) Mathematical Analysis of Algorithms

Wintersemester 2020/21

Anmeldefrist abgelaufen.

Erster Termin der LV
06.10.2020 13:00 - 15:00 HS 7 On Campus
... keine weiteren Termine bekannt

Überblick

Bedingt durch die COVID-19-Pandemie können kurzfristige Änderungen bei Lehrveranstaltungen und Prüfungen (z.B. Absage von Präsenz-Lehreveranstaltungen und Umstellung auf Online-Prüfungen) erforderlich sein.

Weitere Informationen zum Lehrbetrieb vor Ort finden Sie unter: https://www.aau.at/corona.
Lehrende/r
LV-Titel englisch Mathematical Analysis of Algorithms
LV-Art Vorlesung
LV-Modell Präsenzlehrveranstaltung
Semesterstunde/n 2.0
ECTS-Anrechnungspunkte 4.0
Anmeldungen 12
Organisationseinheit
Unterrichtssprache Englisch
mögliche Sprache/n der Leistungserbringung Englisch
LV-Beginn 06.10.2020
eLearning zum Moodle-Kurs

Zeit und Ort

Beachten Sie bitte, dass sich aufgrund von COVID-19-Maßnahmen die derzeit angezeigten Termine noch ändern können.
Liste der Termine wird geladen...

LV-Beschreibung

Intendierte Lernergebnisse

After successful completion of this course, students will know methods and corresponding 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

This course discusses tools which are useful in determining the asymptotic behaviour of functions. As an example, the factorial function n! can be approximated by sqrt(2 pi n)*(n/e)^n. These tools are very useful in combinatorial analysis, for example in determining an approximation for large coefficients of a given generating function which are in turn used to analyse algorithms.

Contents:

  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

Im Fall von online durchgeführten Prüfungen sind die Standards zu beachten, die die technischen Geräte der Studierenden erfüllen müssen, um an diesen Prüfungen teilnehmen zu können.

Geänderte Prüfungsinformationen (COVID-19 Ausnahmeregelung)

If necessary, oral exams will be held via video conference.

Prüfungsmethode/n

Oral exam

Prüfungsinhalt/e

Contents of the lectures.

Beurteilungskriterien/-maßstäbe

  • The grade is obtained by a single oral exam (45 minutes), until November 30th, 2021.
  • 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 Benotungsschema

Position im Curriculum

  • Masterstudium Mathematics (SKZ: 401, Version: 18W.1)
    • Fach: Discrete Mathematics (Wahlfach)
      • 6.5 Mathematical Analysis of Algorithms ( 2.0h VO / 4.0 ECTS)
        • 312.258 Mathematical Analysis of Algorithms (2.0h VO / 4.0 ECTS)
  • Masterstudium Mathematics (SKZ: 401, Version: 18W.1)
    • Fach: Applied Mathematics (Wahlfach)
      • Lehrveranstaltungen aus den Vertiefungsfächern ( 0.0h XX / 12.0 ECTS)
        • 312.258 Mathematical Analysis of Algorithms (2.0h VO / 4.0 ECTS)

Gleichwertige Lehrveranstaltungen im Sinne der Prüfungsantrittszählung

Wintersemester 2023/24
  • 312.258 VO Mathematical Analysis of Algorithms (2.0h / 4.0ECTS)
Wintersemester 2017/18
  • 312.258 VO Mathematische Analyse von Algorithmen (2.0h / 4.0ECTS)