Topic outline

  • Onlinekommunikation

    Während keine Präsenzveranstaltungen stattfinden, werden die Vorlesungen online als Aufnahme oder mit Livestreaming präsentiert.


    • Überblick

      Kursinhalte

      Diese Vorlesung befasst sich mit den algorithmischen Grundlagen geographischer Informationssysteme (GIS) und deren Anwendung in ausgewählten Problemen bei der Erfassung, Verarbeitung, Analyse und Präsentation raumbezogener Information. Im Vordergrund stehen Verfahren der diskreten und kontinuierlichen Optimierung. Zu den besprochenen Anwendungen gehören die Erstellung digitaler Höhenmodelle, die Arbeit mit GPS-Trajektorien, Aufgaben der räumlichen Planung sowie die kartographische Generalisierung.

      Zielgruppe & Prüfung

      Die Vorlesung richtet sich an Studierende im Master-Studiengang Informatik sowie Studierende verwandter Disziplinen (Mathe, Geografie, ...). Grundlagenkenntnisse in Algorithmen und Datenstrukturen werden vorausgesetzt.

      Durch erfolgreiche Prüfung erwerben die TeilnehmerInnen 5 ECTS-Punkte.

      Prüfungsform: abhängig von Infektionsschutzmaßnahmen. Vermutlich mündlich Prüfung.

      Dozent

      Thomas van Dijk

      Übungen

      Betreuung: Felix Klesen, donnerstags, 16:00 Uhr, online

      Es gibt wöchentliche Übungsblätter zu Verfahren und Algorithmen aus der Vorlesung, mit Aufgaben wie z.B.:
      • Formalisierung eines Problems,
      • Berechnungen ("zu Fuß", kleinere Programme schreiben),
      • Fragen zur Theorie.
      Bearbeitung in 2er-Gruppen ist erlaubt und bevorzugt; einreichen über WueCampus. Bearbeitungszeit ist in der Regel 1 Woche. Wenn Sie am Ende mindestens 50% der Punkte auf den Übungsblättern haben, erhalten Sie 0,3 Bonus auf Ihre Note (falls Prüfung bestanden).


      Anmeldung

      Hier im WueCampus (klicken Sie dazu ganz oben links auf das Feld mit den weißen Zahnrädern auf blauem Grund und wählen Sie dann "Mich in diesem Kurs einschreiben" aus.) sowie in WueStudy (später im Semester; noch nicht freigestaltet).


      • Termine

        Erster Termin: Vorlesung Mittwoch 14. 4. 2021

        Vorlesung:mittwochs 10:15 bis 11:45
        Übung:donnerstags 16:00 bis 17:30


        • Vorlesungen

          Woche Thema Material
          0 Begrüßungsvideo Playlist
          1 Einführung Geographische Informationswissenschaft
          • Was ist Geoinformatik?
          • Was ist Geodäsie?
          • Kartenabbildungen
          Playlist
          Folien: A, B, C
          Mercator puzzle
          2 Map Matching, Ansatz 1
          • Was ist Map Matching?
          • Hausdorff-Distanz
          • Fréchet-Distanz
          • Map Matching mit Fréchet-Distanz (neu)
          Playlist
          Interactive Fréchet-Distanz-Parameterraum Demo
          Folien
          Intermezzo GIS Safari
          • OpenStreetMap
          • Herumspielen mit QGIS
          Video

          OpenStreetMap
          QGIS
          3 Map Matching, Ansatz 2
          • Map Matching nach Newson & Krumm (Einführung)
          • Maximum-likelihood Explanation (MLE)
          • Markov Chains
          • Hidden Markov Models
          • Map Matching nach Newson & Krumm (diesmal wirklich)
          Playlist
          Folien: MarkovNewson & Krumm
          Intermezzo GIS Safari 2
          • Simplifizierung
          • Zeichenstile
          Video
          4 Kartografische Generalisierung
          • Generalisierung
          • Der Algorithmus von Douglas-Peucker
          • Der Algorithmus von Imai-Iri
          • Der Algorithmus von Chan-Chin
          • Zusammenfassung und Ausblick
          Playlist
          Folien
          5 Automatisierte Beschriftungsplatzierung
          • Einführung
          • Beschriftungskriterien nach Imhof
          • Problemstellung
          • Ein Greedy Algorithmus
          • Ein Approximationsalgorithmus
          Playlist
          Folien
          Intermezzo GIS Safari 3
          • Schriftplazierung
          Video 1
          Video 2
          6 Clustering
          • Einführung
          • DBSCAN: Definition und Laufzeitbehauptung
          • "Faster DBSCAN": Algorithmus von De Berg, Gunawan, Roefloffzen
          Playlist
          Folien
          7 Location-dependent Generalisation
          • Einführung
          • Definitionen
          • Clustering-Algorithmus
          • Visualisierung (neu)
          Playlist
          Folien
          8 Bloom Filters
          • SetMembership-Datenstrukturen
          • Herkunft und Anwendungen
          • Ein Bitvektor mit Hashing + Analyse
          • Ein Bloom Filter + Analyse
          • GloBiMaps (neu)
          Playlist
          Folien
          9 Ein paar Ergänzungen
          • Map Matching mit Fréchet-Distanz
          • GloBiMaps
          Playlist
          10 Methode der kleinsten Quadrate (Least Squares Adjustment)
          • Einführung
          • historischer Kontext
          • Definitionen
          • Gauß-Normalgleichung (neu)
          • Beweise (neu)
          • Beispiel: Höhenmessungen (neu)
          • Messgenauigkeit (neu)
          • Kovarianzfortpflanzungsgesetz (neu)
          • Beispiel: Messgenauigkeit bei Höhenmessungen (neu)
          Playlist
          Folien
          Folien (pdf; Animationen teilweise kaputt)