Subnavigation: 

Teaching

Metanavigation: 


wissen.leben | WWU Münster 


Informatik II - Datenstrukturen und Algorithmen

Prof. Dr. Klaus Hinrichs, Aaron Scherzinger

Aktuelles:

  • (12.01.2017) Bitte beachten Sie, dass aktuelle Informationen über das Learnweb bekannt gegeben werden.
  • (12.01.2017) Erste Version der Vorlesungsseite ist online.

Inhalt:

Datenstrukturen und Algorithmen und ihre Realisierung in Java bilden den Schwerpunkt dieser Vorlesung. Zunächst werden Algorithmen für verschiedene primitive Typen von zugrunde liegenden Daten vorgestellt, z.B. für Bitmengen, ganze Zahlen oder Gleitkommazahlen. Nach grundlegenden Betrachtungen zur Berechenbarkeit und Komplexität werden die mathematischen Werkzeuge zur Analyse von Algorithmen behandelt und anschließend auf die Probleme des Suchens und Sortierens angewendet. Der in der Vorlesung Informatik I eingeführte Begriff des abstrakten Datentyps (ADT) wird am Beispiel weiterer ADTs, z. B. Priority Queue und Dictionary, vertieft. Sodann werden verschiedene Datenstrukturen zur Realisierung von ADTs vorgestellt, z.B. der Heap, verschiedene Typen von Listenstrukturen und Bäumen sowie Adressberechnungsverfahren. Zum Abschluss der Vorlesung wird die Anwendung der vorgestellten Konzepte am Beispiel von Algorithmen zur Lösung geometriebezogener Probleme aufgezeigt.

Vorlesungsmaterialien

Alle Materialien zur Vorlesung werden über die Learnweb-Seite zur Vorlesung zur Verfügung gestellt. Der Einschreibeschlüssel wird in der ersten Vorlesung bekannt gegeben.

Termine (Vorlesung)

Montag, 8:15 - 10:00 (M1)
Donnerstag, 8:15 - 10:00 (M1)

Zusätzliche Termine: Dienstag, 18:00 - 19:45 (M1) am 25.4., 2.5., 16.5., 23.5. und 13.6.

Vorlesungsbeginn ist der 20.04.2017

Termine (Übung)

Die Übungen finden wöchentlich Donnerstags und Freitags statt. Die Anmeldung für die Übungen findet über das Learnweb statt, unten finden Sie eine Auflistung der Übungstermine. Die ersten Übungen finden am 27.4. bzw. 28.4. statt. Bitte seien Sie am ersten Übungstermin anwesend, da dort die Einteilung in Abgabegruppen für die Übungszettel stattfinden wird. Sollte dies nicht möglich sein, so melden Sie sich bitte unter Angabe von Namen, Matrikelnummer und Ihrer Übungsgruppe bei Aaron Scherzinger.

ACHTUNG: Bitte beachten Sie, dass es sich bei den untenstehenden Übungsterminen um vorläufige Termine handelt und noch Änderungen möglich sind.

NICHT Wirtschaftsinformatik 

  • Do, 10-12 Uhr, SRZ 214
  • Do, 10-12 Uhr, SRZ 217
  • Do, 12-14 Uhr, SRZ 205
  • Do, 14-16 Uhr, SRZ 205
  • Fr, 08-10 Uhr, SRZ 205
  • Fr, 08-10 Uhr, SRZ 217
  • Fr, 10-12 Uhr, SRZ 205
  • Fr, 10-12 Uhr, SRZ 217
  • Fr, 12-14 Uhr, SRZ 205
  • Fr, 12-14 Uhr, SRZ 217
  • Fr, 14-16 Uhr, SRZ 205 

Wirtschaftsinformatik

  • Do, 12-14 Uhr, LEO 1.8
  • Do, 14-16 Uhr, LEO 11.3
  • Do, 18-20 Uhr, LEO 11.3
  • Fr, 08-10 Uhr, LEO 11.3
  • Fr, 10-12 Uhr, LEO 11.3
  • Fr, 12-14 Uhr, LEO 11.3
  • Fr, 14-16 Uhr, LEO 11.3  

Bearbeitung der Übungsaufgaben

Die Übungszettel werden wie die restlichen Vorlsungsmaterialien im Learnweb zur Verfügung gestellt. Die Abgabe der Übungsaufgaben erfolgt ebenfalls ausschließlich über das Learnweb. Es ist keine zusätzliche schriftliche Abgabe vorgesehen.

Bitte beachten Sie, dass einige Studierende durch die Bearbeitung der Übungen die Klausurzulassung erwerben müssen, während bei anderen die erreichten Punkte in den Übungen anteilig in die Note der Veranstaltung einfließen (siehe unten).

Falls Sie Probleme oder Fragen zur Koordination / Anmeldung zu den Übungen oder der Anmeldung im Learnweb haben, melden Sie sich bitte bei Aaron Scherzinger.

Hinweise zur Abgabe und Bewertung von Übungsaufgaben

Bitte beachten Sie, dass bei Nichteinhalten der Abgabeformate die Abgabe nicht korrigiert, d.h. mit 0 Punkten bewertet, wird.

Abgabe schriftlicher Aufgaben

Bitte geben Sie schriftliche Aufgaben jeweils als PDF-Datei ab.

Abgabe von Programmieraufgaben

Bitte geben Sie Programmieraufgaben als *.zip-Archiv ab, in dem kompilierbare (!) Quelltextdateien enthalten sind. Das Archiv sollte zudem eine PDF-Datei mit Hinweisen zum Kompilieren und Ausführen Ihrer Abgabe enthalten. Alternativ können Sie auch eine ausführbare *.jar-Datei abgeben, in der auch die Quelltextdateien enthalten sind. Wird der Quelltext nicht abgegeben, kann die Abgabe nicht korrigiert werden und wird daher mit 0 Punkten gewertet.

Hinweise zur Bewertung von Programmieraufgaben

Bitte beachten Sie die folgenden Hinweise zur Bewertung von Programmieraufgaben:

  • Die Dokumentation des Quellcodes geht, wie bereits in den Übungen bekannt gegeben, in die Bewertung der Programmieraufgaben mit ein. Hierbei wird erwartet, dass Klassen und Methoden mittels Javadoc dokumentiert werden, inkl. der Eingabeparameter und Rückgabewerte der Methoden (abgesehen von Settern und Gettern). Längere und / oder komplexere Programmabschnitte müssen ausreichend kommentiert werden, um die Funktionsweise zu erläutern.
  • Eine sinnvolle Benennung von Variablen und Methoden wird erwartet - Hilfsmethoden sollten keine Namen wie foo() oder doStuff() erhalten. Generell soll die Namensgebung das Verständnis des Codes unterstützen.
  • Umlaute sollten weder im Code noch in den Kommentaren auftauchen. Für Umlaute in den Quelltextdateien werden Punkte bei der Abgabe abgezogen.
  • Die Abgaben müssen kompilierbar sein. Bei einer nicht kompilierbaren Abgabe liegt es im Ermessen des Tutors, diese mit 0 Punkten zu bewerten.
  • ISO- bzw. UTF-8 Zeichenkodierung: bitte sprechen Sie mit Ihrem Tutor die Zeichenkodierung ab, in der Quelltextdateien abgegeben werden sollen. Bei Nichteinhaltung der Absprache werden bei der Abgabe Punkte abgezogen.

Hinweise zur Abgabe von Beweisen durch erschöpfende Auflistung der Möglichkeiten durch Programme

Bei der Durchführung eines Beweises durch erschöpfendes Auflisten aller Möglichkeiten mit Hilfe eines Programmes ist das verwendete Programm mit abzugeben, sowie die Korrektheit des verwendeten Programmes formal zu beweisen.

Abgaben, bei denen die obigen Bedigungen nicht erfüllt sind, werden ggf. mit 0 Punkten bewertet.

Hinweise zur mehrfachen Abgabe von Übungsaufgaben (Plagiaten)

Bitte beachten Sie, dass die Abgaben, insbesondere auch die Programmieraufgaben, unter der Verwendung entsprechender Software auf abgeschriebene oder kopierte Lösungen überprüft werden. Bei entsprechenden Fällen, in denen die gleiche oder eine klar abgeschriebene Lösung abgegeben wird, erhalten alle betreffenden Gruppen für die Aufgabe keine Punkte - unabhängig davon, welche Gruppe die entsprechende Lösung ursprünglich erstellt hat.

Klausur und Leistungsnachweis

1. Klausurtermin: voraussichtlich 29.07.2017, 8:00 Uhr

2. Klausurtermin: tba

In der Klausur sind jeweils 120 Punkte zu erreichen. Die Prüfung gilt als bestanden, wenn mindestens 60 Punkte erreicht werden. Bitte beachten Sie zudem die untenstehenden Hinweise.

Hinweise zur Klausurzulassung und Prüfungsleistung

Klausurzulassung und Prüfungsleistung (NICHT Wirtschaftsinformatik)

Für alle Teilnehmer, die nicht Studierende der Wirtschaftsinformatik sind, ist die Bearbeitung der Übungsaufgaben verpflichtend. Um die Zulassung zur Klausur zu erhalten, müssen mindestens 50% der Übungspunkte erreicht werden. Eine bereits in einem früheren Semester in der Informatik II erreichte Klausurzulassung kann übernommen werden. Bitte melden Sie sich in diesem Fall bei Aaron Scherzinger. Wir empfehlen auch bei bereits vorhandener Klausurzulassung, die Übungsaufgaben zu bearbeiten. Die Abschlussnote entspricht genau der in der Klausur erreichten Note. Die Klausur ist 120 Minuten lang und insgesamt können 120 Punkte in der Klausur erreicht werden.

Klausurzulassung und Prüfungsleistung (Wirtschaftsinformatik)

Entsprechend der Prüfungsordnung bzw. Modulbeschreibung für den Bachelorstudiengang Wirtschaftsinformatik gilt die obige Regelung nicht für Studierende der Wirtschaftsinformatik. Für Studierende der Wirtschaftsinformatik ist der Erwerb einer Klausurzulassung nicht erforderlich. Aus den erreichten Übungspunkten wird eine Übungsnote berechnet. Hierbei sind 50% der Übungspunkte für die Note 4,0 erforderlich. Die Gesamtnote der Veranstaltung berechnet sich gewichtet aus der Klausurnote (80%) und der in den Übungen erreichten Note (20%). Die Klausur ist 120 Minuten lang und insgesamt können 120 Punkte in der Klausur erreicht werden. Die Klausur gilt als bestanden (4,0) wenn mindestens 60 von 120 Punkten erreicht werden. Bitte beachten Sie, dass (wie in der Vergangenheit bereits geschehen) durch die gewichtete Berechnung der Abschlussnote der Fall auftreten kann, dass die Klausur mit 4,0 bestanden ist, aber bei nicht bestandenen Übungen die Veranstaltung insgesamt trotzdem als nicht bestanden gewertet wird.

Literatur

  • J. Nievergelt, K. Hinrichs: Algorithms and Data Structures - with Applications to Graphics and Geometry, Prentice Hall, Englewood Cliffs, NJ, 1993. vdF Hochschulverlag, Zürich, 1999, ISBN 3-7281-2523-7.
  • T. Cormen, C. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms, 3rd ed., MIT Press, Cambridge, MA, 2009.
  • M. Goodrich, R. Tamassia: Data Structures and Algorithms in JAVA, 6th ed.,John Wiley & Sons, New York, 2014.
  • D. E. Knuth: The Art of Computer Programming,
            Vol. 1 - Fundamental Algorithms, 3rd ed., 1997,
            Vol. 2 - Seminumerical Algorithms, 3rd ed., 1998,
            Vol. 3 - Sorting and Searching, 2nd ed., 1998,
            ...
    Addison-Wesley, Reading, MA.
  • T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen, 5. Aufl., Springer Spektrum, 2012.
  • M. Weiss: Data Structures and Algorithm Analysis in JAVA, 3rd ed., Addison-Wesley, Reading, MA, 2012.

Voraussetzung

Informatik I - Grundlagen der Programmierung 

Studiengänge

  • Bachelorstudiengang Informatik
  • Bachelorstudiengang Wirtschaftsinformatik
  • Bachelorstudiengang Geoinformatik
  • 2-fach Bachelor Informatik
  • Nebenfach Informatik im Bachelorstudiengang Mathematik
  • Nebenfach / Wahlpflichtfach / Wahlfach Informatik zu diversen Studiengängen, z.B. Physik

Links

Link zur Veranstaltung im Vorlesungsverzeichnis

Link zum Learnweb-Kurs


Impressum | © 2009 Arbeitsgruppe VisCG | Edit this page
Arbeitsgruppe Visualisierung und Computergrafik
Einsteinstraße 62 · 48149 Münster
Tel.: +49 (251) 83-32700 · Fax: +49 (251) 83-33755