■
Team
■
Teaching
Information for students of B.Sc./M.Sc. Mathematics
Summer 2021
■
Winter 2020
Summer 2020
■
Winter 2019
■
Summer 2019
■
Winter 2018
■
Summer 2018
■
Winter 2017
■
Summer 2017
■
Winter 2016
■
Summer 2016
■
Winter 2015
Algorithmen und Berechenbarkeit / Formale Methoden
Algorithms for OpenStreetMap data
Discrete Optimization
Erg. zu Algorithmen, Berechenbarkeit & Komplexität
Seminar: Fortgeschrittene Routenplanung
Ergänzungen zu Logik & DS
■
Summer 2015
■
Winter 2014
■
Summer 2014
■
Winter 2013
■
Summer 2013
■
Winter 2012
■
Summer 2012
■
Winter 2011
Former Semester
BSc, Master-, Student-, Diplomathesis
StuPro/ ProjektINF/ SoPra/ FaPra
■
Research
Publications
Projects
Student Projects
 

Ergänzungen zu Algorithmen, Berechenbarkeit und Komplexität

Aktuelles

Kurzfristige Themenänderung

Heute 12.11.2015 BuK: Reduktionen (hilfreich für das nächste Übungsblatt)

vorläufige Formelsammlung

Tex-Datei zur Formelsammlung (Änderungen bitte mir als diff/patch oder besser die ganze Datei schicken)

Vorlesung

Daniel Bahrdt

Diese Veranstaltung ergänzt die Module Berechenbarkeit und Komplexität, Algorithmen und Berechenbarkeit. Die Veranstaltung gliedert sich in drei Bereiche:

  • Wiederholung der Inhalte aus den Vorlesungen und Übungen mit zusätzlichen oder ausführlicheren Erklärungen, sowie Wiederholung wichtiger Themen aus Mathematik und theoretischer Informatik des ersten Semesters
  • Ergänzung des Stoffes mit weiterführenden Ergebnissen, alternativen Beweisen, zusätzlichen Beispielen und Verknüpfung mit praktischen Anwendungen
  • Hilfe bei Schwierigkeiten mit den Hausübungen

Themenwünsche können per E-Mail an den Dozenten geäußert werden.

Termine und Materialien

Achtung: Die Termine können sich noch ändern!

Woche Wann / Wo / Was / Prüfungsrelevanz / Material
KW 42 Do 15.10
17:30-19:00
V38.03
Programmlaufzeiten / Organisatorisches
AuB, BuK
Blatt0
KW 43 Do 22.10
17:30-19:00
V38.03
Grundlagen Wahrscheinlichkeitstheorie
AuB
KW 44 Do 29.10
17:30-19:00
V38.03
entfällt
KW 45 Do 5.11
17:30-19:00
V38.03
entfällt
KW 46 Do 12.11
17:30-19:00
Reduktionen
BuK
KW 47 Do 19.11
17:30-19:00
Lösen von Rekursionsgleichungen
AuB
KW 48 Do 26.11
17:30-19:00
Reduktionen
BuK
Blatt
KW 49 Do 3.12
17:30-19:00
Lösen von Rekursionsgleichungen
AuB
Blatt
KW 50 Do 10.12
17:30-19:00
Reduktionen
BuK
Blatt vom letzten mal, Vorlesungsumfrage
KW 51 Do 17.12
17:30-19:00
Berechenbarkeit / Entscheidbarkeit / Reduktionen / Vorlesungsumfrage
AuB
Blatt
KW 1 Do 07.01
17:30-19:00
Reduktionen von berechenbaren Problemen
BuK
KW 2 Do 14.01
17:30-19:00
Präsenzübung zu Reduktionen von Entscheidungsproblemen
Blatt
AuB
KW 3 Do 21.01
17:30-19:00
Präsenzübung Polynomialzeitreduktionen, Hierarchiesätze
BuK
Blatt
KW 4 Do 28.01
17:30-19:00
Beispiel-MC-Test, Klausur WS 2010
AuB
KW 5 Do 04.02
verschoben auf Do 14.02
KW 6 Do 11.02
17:30-19:00
Raum 0.447

Entscheidbarkeit
KW 7 Mi 17.02
14:00 Uhr
Raum 0.108
Prüfungsvorbereitung AuB und BuK
Themenwünsche bis 15.02 einsendbar

Es werden nur Themen besprochen,
die zuvor per Mail eingegangen sind.

Literatur

Algorithmik

Berechenbarkeit / Komplexitätstheorie

  • Theoretische Informatik - kurzgefasst von Uwe Schöning
  • Theoretische Informatik von Dirk W. Hoffmann

Grundwissen (und darüber hinaus)

  • Taschenbuch der Mathematik
  • Repetitorium der Mathematik
  • Logik für Informatiker von Uwe Schöning

Wahrscheinlichkeitstheorie

  • Elemente der diskreten Mathematik
  • Stochastik: Einführung in die Wahrscheinlichkeitstheorie und Statistik

News

[Oct’21] We have migrated to our new webssite here!

[Jun’19] Our paper on trajectory storage and retrieval has been accepted at SSTD 2019!

[Nov’18] Our paper on regret minimization has been accepted at AAAI 2019 (acceptance rate 16.2%)!

[Oct’18] Our paper on alternative route planning for bicycles has been accepted at ALENEX 2019!

[Apr’18] Martin has successfully defended his Ph.D. thesis. Congratulations!

[Jan’18] The journal version of our paper on k-hop path covers will receive a publication award from our university!

[Nov’17] Our paper on a theoretical explanation for several speed-up techniques for route computation has been accepted at AAAI 2018!

[Oct’17] Thomas’ paper on area preserving map simplification has been accepted at ALENEX 2018!

[May’17] Daniel’s and Martin’s paper on rational points on the unit sphere has been accepted at ISSAC 2017!

[Apr’17] Our paper on personalized route planning with dynamic approximation guarantees has been accepted at SEA 2017!

[Jan’17] Martin’s paper on map matching has been accepted at SIAM SDM 2017!

[Nov’16] Our paper on simultaneous maze solving has been accepted at AAAI 2017.

[Okt’16] Two papers, one on growing balls (!), the other on map simplification will be presented at ALENEX 2017.

[Sep’16] Our paper on Deducing Individual Driving Preferences has been accepted at the 24th ACM SIGSPATIAL GIS 2016.

[Feb’16] Our paper on placing loading stations for EVs has been accepted at ICAPS 2016.

[Jul’15] Paper about our GeoSearch Engine OSCAR at the 16th Int. Conf on Web Information Systems Engineering (WISE)!

[Jun’15] We feel very honored to have our VLDB’14 paper almost verbatimly reproduced in the ‘prestigous’ journal IJSETR, see here. Yeah! 😉

[Feb’15] We were lucky to receive a Google Research Award for research on personalized route planning!

[Sep’14] Our paper “On k-Path Covers and their Applications” has received a Best Paper Award at the 40th Int. Conference on Very Large Databases (VLDB) in Hangzhou (5 out of 139 accepted out of 695 submitted papers).

[Sep’14] Our paper on “Energy-efficient Routing: Taking Speed into Account” has received a Best Paper Award at the 37th German Conference on Artificial Intelligence (KI).

[Jul’14] Our paper “Placement of Loading Stations for Electric Vehicles: No Detours Necessary!” has received a Honorable Mention at the 28th AAAI Conference on Artificial Intelligence (AAAI) in Quebec City (5 nominated out of 398 accepted out of 1406 submitted papers).

[Mar’14] Our StuPro-Team has completed their great “SchulScheduler” project.

[Nov’13] Jochen has defended his PhD thesis and moved on to TomTom.

[Feb’13] Sabine has defended her PhD thesis (already in Dec’12) and received the INFOS award for best CS PhD thesis in 2012!

[Mar’12] Our paper Path Shapes - An Alternative Method for Map Matching and Fully Autonomous Self-Localization presented at GIS 2011 has received the Best Paper Award, also see the ACM SIGSPATIAL newsletter.