Abschnittsübersicht

  • Allgemeines

    Alles einklappen Alles aufklappen

  • 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: Markov, Newson & 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)

    • Übungsblätter

      Allgemeiner Abgabetermin: eine Woche später, Mittwoch 10:00.