■
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
 

Algorithmen und Berechenbarkeit / Formale Methoden

Aktuelles

Nachhol-Einsicht: 19.10., 14:00, Raum: 1.140

Die Ergebnisse der Klausur (Herbst 2016) hängen am Brett des Instituts aus.

Einsicht: 26.9., 14:00, 1.140

Für die Klausur im SS16 gelten die selben Themen (-Auschlüsse) wie im WS15/16.

 

Die Ergebnisse der Klausur hängen am Brett des Instituts aus.

Zusammenfassungsfolien inkl. Ausschlüssen hier.

Die Ergebnisse des 3. MC-Tests hängen samt der Scheinliste am Brett des Instituts aus.

Für den MC-Test sind Bleistift und Radiergummi (oder Tipp-Ex) notwendig! Anders können markierte Antworten nicht korrigiert werden.

Der Aushang über den 2. MC-Test und den Scheinstatus wurde aktualisiert. (05.02.16, 14:30)

Die Ergebnisse des zweiten MC-Tests hängen am schwarzen Brett des FMI (neben 1.101) aus.

Die Vorlesung am 07.01.2016 fällt aus, Ersatztermin 14.01.2016!

Einen Test MC-Test gibt es hier: download

Scheinbedingungen aktualisiert.

Die Ergebnisse des ersten MC-Tests hängen am schwarzen Brett des FMI (neben 1.101) aus.

Die Scheinbedingungen sind unter dem entsprechenden Unterpunkt aufgeführt.

Votieren in eClaus: Für jede Votieraufgabe kann ein Haken bei “Ich votiere” gesetzt werden.

Bildung von Abgabegruppen (bei Bedarf) über: Ilias (Kurspasswort wie für eClaus)

Anmeldung zu den Übungen: eClaus (Login wird in der Vorlesung 15.10. bekanntgegeben)

Intro-Slides hier.

Vorlesung

Zeit Raum Termine
Okt. Nov. Dez. Jan. Feb.
Mo 15:45-17:15 V38.04 12., 19, 26. 9., 16., 23., 30. 07.*, 14., 21. 11., 18., 25. 01.*
Do 14:00-15:30 V38.04 15., 29. 12., 19. 03., 17. 07., 14., 21. 04.**

* MC-Test     ** Fragestunde

Übungen

  Blatt 1 Blatt 2 Blatt 3 Blatt 4 Blatt 5 Blatt 6
Ausgabe: 15.10. 29.10. 12.11. 26.11. 21.12. 14.01.
Abgabe: 22.10. 05.11. 19.11. 03.12. 07.01. 21.01.
Gruppe Zeit Raum Tutor Besprechungstermine
1 Mo 11:30-13:00 0.118 Rieger 26.10. 09.11. 23.11. 07.12. 11.01. 25.01.
2 Mo 11:30-13:00 0.183 Rieger 02.11. 16.11. 30.11. 14.12. 18.01. 01.02.
3 Di 09:45-11:15 0.363 Nusser 27.10. 10.11. 24.11. 08.12. 12.01. 26.01.
4 Di 09:45-11:15 0.363 Nusser 03.11. 17.11. 01.12. 15.12. 19.01. 02.02.
5 Di 14:00-15:30 0.447  Schreiber 27.10. 10.11. 24.11. 08.12. 12.01. 26.01.
6 Di 14:00-15:30 0.447  Schreiber 03.11. 17.11. 01.12. 15.12. 19.01. 02.02.
7 Mi 17:30-19:00 0.447 Mendel 28.10. 11.11. 25.11. 09.12. 13.01. 27.01.
8 Mi 17:30-19:00 0.457  Mendel 04.11. 18.11. 02.12. 16.12. 20.01. 03.02.
  1. Blatt (Änderungen - 4a: “Dies führen wir n-1 mal aus”, 5: “P Teilmenge von R²”)
  2. Blatt
  3. Blatt (Aufgabe 5: “ich votiere” in eClaus ergibt 2 Votierpunkte)
  4. Blatt (Änderung - 4: Adjazenz bzgl. E’ statt E)
  5. Blatt
  6. Blatt (Ergänzung: Sprache E klassifiziert bzgl. Entscheidbarkeit)

Scheinbedingungen

  • Bestehen von zwei der drei MC-Tests (1.: 07.12., 2.: 01.02., 3.: 19.02)
  • In den Übungen mind. einmal vorrechnen.
  • Mind. die Hälfte der schriftlichen Übungspunkte erreichen. (“P” auf den Ü-Blättern - Abgabe der Lösungen in eClaus)
  • Mind. die Hälfte der Votieraufgaben votieren. (“V” auf den Ü-Blättern - “Ich votiere” in eClaus)
  • Alle votierten oder abgegebenen Aufgaben müssen in der Übung vorgerechnet werden können.

Ergänzungen

Website

Literatur

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms (Second Edition), MIT Press, 2001
  • T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen, Spektrum Verlag, 1996
  • J. Kleinberg, É. Tardos: Algorithm Design, Addison-Wesley, 2006
  • Uwe Schöning: Theoretische Informatik – kurzgefasst, 5. Auflage, Spektrum, 2008. (Die ältere Auflage von 2000 tut’s auch!)
  • Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger: Diskrete algebraische Methoden, Walter de Gruyter, 2013.
  • Notizen zu Contraction Hierarchies
  • Skript von Prof. Voecking (zuletzt RWTH Aachen)

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.