wissen.leben | WWU Münster 


Informatik II - Datenstrukturen und Algorithmen

Prof. Dr. Klaus Hinrichs, Aaron Scherzinger

Aktuelles:

  • (02.06.2016) Bitte beachten Sie, dass aktuelle Ankündigungen nur noch über das Learnweb bekannt gegeben werden.
  • (12.04.2016) Bitte beachten Sie die aktualisierten Informationen zur Klausurzulassung, Bearbeitung der Übungen und Berechnung der Gesamtnote der Veranstaltung, die an die Prüfungsordnung bzw. Modulbeschreibung der Wirtschaftsinformatik angepasst wurde.
  • (11.04.2016) Die entfallenden Vorlesungstermine sowie die entsprechenden Ersatztermine finden Sie nun sowohl auf dieser Seite unter den Vorlesungsterminen als auch im Learnweb. Bitte beachten Sie, dass im Gegensatz zur Ankündigung in der Vorlesung ein Ersatztermin am 21.6. anstatt dem 14.6. stattfindet.
  • (08.04.2016) Bitte beachten Sie, dass einer der Übungstermine in der Informatik (Do, 10-12 Uhr) im Zeitraum vom 21.4.-12.5. in einem anderen Raum stattfindet.
  • (09.02.2016) 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)

Bitte beachten Sie die folgenden Ersatztermine für entfallende Vorlesungen:

  • Folgende reguläre Vorlesungstermine entfallen: 9.5., 12.5., 2.6., 11.7. und 14.7.
  • Stattdessen finden Vorlesungen Dienstag, 18-20 Uhr, an den folgenden Terminen statt: 26.4., 24.5., 31.5., 14.6. und 28.6.

Vorlesungsbeginn ist der 11.04.2016.  

Termine (Übung)

Die Anmeldung für die Übungsgruppen erfolgt ab dem 11.04.2016, 10:00 (nach der Vorlesung), bis zum 13.04.2016, 14:00, über die Learnweb-Seite zur Vorlesung.

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

Die Übungen starten direkt in der ersten Vorlesungswoche, also am 14.04. bzw. 15.04.2016.

Übungstermine (nicht Wirtschaftsinformatik)

  • Do. 10:00 bis 12:00, Orléans-Ring 12 - SRZ 205
    (bitte beachten Sie, dass dieser Übungstermin im Zeitraum 21.4.-12.5.im SR1D in der Einsteinstr. 62 stattfindet)
  • Do. 10:00 bis 12:00, Orléans-Ring 12 - SRZ 217
  • Do. 12:00 bis 14:00, Orléans-Ring 12 - SRZ 205
  • Do. 14:00 bis 16:00, Orléans-Ring 12 - SRZ 217
  • Fr. 08:00 bis 10:00, Orléans-Ring 12 - SRZ 205
  • Fr. 08:00 bis 10:00, Orléans-Ring 12 - SRZ 217
  • Fr. 10:00 bis 12:00, Orléans-Ring 12 - SRZ 205
  • Fr. 10:00 bis 12:00, Orléans-Ring 12 - SRZ 217
  • Fr. 12:00 bis 14:00, Orléans-Ring 12 - SRZ 205
  • Fr. 12:00 bis 14:00, Orléans-Ring 12 - SRZ 217
  • Fr. 14:00 bis 16:00, Orléans-Ring 12 - SRZ 205
  • Fr. 14:00 bis 16:00, Orléans-Ring 12 - SRZ 217

Übungstermine (Wirtschaftsinformatik): 

  • Do. 12:00 bis 14:00, Leonardo-Campus 11 - LEO 11.3
  • Do. 14:00 bis 16:00, Leonardo-Campus 11 - LEO 11.3
  • Do. 18:00 bis 20:00, Leonardo-Campus 11 - LEO 11.3
  • Fr. 08:00 bis 10:00, Leonardo-Campus 11 - LEO 11.3
  • Fr. 10:00 bis 12:00, Leonardo-Campus 11 - LEO 11.3
  • Fr. 12:00 bis 14:00, Leonardo-Campus 11 - LEO 11.3
  • Fr. 14:00 bis 16:00, Leonardo-Campus 11 - 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 durch die erfolgreiche Bearbeitung der Übungsaufgaben Bonuspunkte für die Klausur erworben werden können und einige Studierende durch die Bearbeitung der Übungen die Klausurzulassung erwerben müssen (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.


Klausur und Leistungsnachweis

  • 1. Klausurtermin (voraussichtl.): Samstag, 23.07.2016, 8-10 Uhr
  • 2. Klausurtermin (voraussichtl.): Mittwoch, 14.09.2016, 7:45-9:45 Uhr

In der Klausur sind jeweils 120 Punkte zu erreichen. Die Prüfung gilt als bestanden, wenn mindestens 60 Punkte erreicht werden.

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. 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. Die Prüfung gilt als bestanden, wenn mindestens 60 Punkte erreicht werden.

Durch die erfolgreiche Bearbeitung der Übungen können bis zu 10 Bonuspunkte für die Klausur erworben werden. Hierbei wird ab 55% erreichter Punkte in den Übungen 1 Bonuspunkt vergeben. Pro weitere erreichte 4% wird ein zusätzlicher Bonuspunkt vergeben. Beispielsweise erhalten Sie bei insgesamt 75% erreichten Punkten in den Übungen 6 Bonuspunkte. Bitte beachten Sie, dass die Bonuspunkte nur angerechnet werden, wenn die Klausur bereits vor Anrechnung der Bonuspunkte bestanden ist, d.h. ohne Bonuspunkte bereits mindestens 60 Punkte in der Klausur erreicht wurden.

Klausurzulassung und Prüfungsleistung (Wirtschaftsinformatik)

Entsprechend der Prüfungsordnung bzw. Modulbeschreibung 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.

Durch die Bearbeitung der Übungen können zusätzlich für die Klausurnote Bonuspunkte erworben werden, die jedoch vor der Berechnung der Gesamtnote nur auf die Note der Klausur Auswirkung haben.

Durch die erfolgreiche Bearbeitung der Übungen können bis zu 10 Bonuspunkte für die Klausur erworben werden. Hierbei wird ab 55% erreichter Punkte in den Übungen 1 Bonuspunkt vergeben. Pro weitere erreichte 4% wird ein zusätzlicher Bonuspunkt vergeben. Beispielsweise erhalten Sie bei insgesamt 75% erreichten Punkten in den Übungen 6 Bonuspunkte. Bitte beachten Sie, dass die Bonuspunkte nur angerechnet werden, wenn die Klausur bereits vor Anrechnung der Bonuspunkte bestanden ist, d.h. ohne Bonuspunkte bereits mindestens 60 Punkte in der Klausur erreicht wurden.

 

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

Link zur Veranstaltung im Vorlesungsverzeichnis

Link zur Vorlesung


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