RUB » LMI » Lehre » Datenstrukturen SS 2017

Datenstrukturen SS 2017

LVR-Nr: 150 322
Veranstaltung: Datenstrukturen
4-std.
Di, 14-16 Uhr, HNC 30
Do, 14-16 Uhr, HNC 30
Dozentin: Maike Buchin
Übungsgruppen: Folgende Übungstermine werden angeboten.
Gruppe 1: Di, 10-12 Uhr, NB 02/99 - Stef Sijben
Gruppe 2: Di, 12-14 Uhr, NB 3/99 - Stef Sijben
Gruppe 3: Di, 16-18 Uhr, NA 2/99 - Lars Schlieper
Für den Besuch der Übungen ist eine Anmeldung via Blackboard erforderlich.
Korrekteure:
  • Lea Thiel
    • Sprechstunde Mo 14-15 Uhr, NA 1/31
  • Lars Schlieper
    • Sprechstunde Mo 14-15 Uhr, NA 1/31

    Aktuelles

    • 5.2.2018: Die Einsicht zur Nachklausur findet am Fr 9.2.2018 von 11:00 Uhr bis 12:00 Uhr in NA 1/70 statt.
    • 23.10.2017: Die Nachklausur findet am Mo 5.2.2018 von 14:00 Uhr bis 16:00 Uhr im HZO 40 statt.

    Materialien

    Hier gibt es im laufenden Semester die Übungsblätter und weitere Materialien zur Vorlesung.

    Hausaufgaben

    Präsenzaufgaben

    Themenliste

    Die Kapitelangaben beziehen sich auf das Buch von Dietzfelbinger, Mehlhorn, Sanders (siehe "Literatur").

    • 1. Woche (KW 16): Asymptotische Analyse, Maschinenmodell, Pseudocode, Invarianten, Binäre Suche, Mastertheorem, Analyse im mittleren Fall, Amortisierte Analyse, Randomisierte Algorithmen, P und NP, (Kurzfassung der Abschnitte 2.1, 2.2, 2.3, 2.4, 2.5, 2.6, 2.7.1, 2.8, 2.10, 3.2.3)
    • 2. Woche (KW 17): Graphen (Abschnitt 2.9), Listen und Arrays (Kurzfassung der Abschnitte 3.1, 3.2, 3.4)
    • 3. Woche (KW 18): Hashing (Abschnitt 4)
    • 4. Woche (KW 19): Sortieren und Auswählen (Abschnitte 5.1, 5.2, 5.3, 5.4, 5.5)
    • 5. Woche (KW 20): Sortieren fortgesetzt (Abschnitt 5.6), Prioritätswarteschlangen (Abschnitt 6.1)
    • 6. Woche (KW 21): Adressierbare Prioritätswarteschlangen (Abschnitt 6.2)
    • 7. Woche (KW 22): Sortierte Folgen (Abschnitt 7.1,7.2,7.3)
    • 8. Woche (KW 24): Sortierte Folgen fortgesetzt (Abschnitt 7.4, 7.5)
    • 9. Woche (KW 25): Graphendarstellungen (Abschnitt 8), Graphendurchläufe (Abschnitt 9)
    • 10. Woche (KW 26): Anwendungen der Tiefensuche (Abschnitt 9.2)
    • 11. Woche (KW 27): Kürzeste Wege: Grundbegriffe (Abschnitt 10.1), Algorithmus von Dijkstra (Abschnitt 10.2,10.3,10.5.1)
    • 12. Woche (KW 28): Minimale Spannbäume (Abschnitt 11)

    Das Thema der 12. Woche ist nicht klausurrelevant.

    Informationen

    Kommentar aus dem Vorlesungsverzeichnis

    Für Studierende der Mathematik mit Nebenfach Informatik ist diese Vorlesung ein obligatorischer Bestandteil des B.Sc.. Bei Wahl des Schwerpunkts Informatik ist sie im B.Sc. zu empfehlen, da andere Vorlesungen auf ihr aufbauen. Weiterhin ist die Vorlesung in den Studiengängen "Angewandte Informatik" und "IT-Sicherheit" vorgesehen.

    Nach einer Besprechung grundlegender Datentypen (wie Listen, Stacks, Queues und Bäume) werden zunächst Datenstrukturen diskutiert, die zur Repräsentation von Mengen geeignet sind und dabei bestimmte Mengenoperationen unterstützen (wie zum Beispiel Dictionaries, Priority Queues und UNION-FIND-Datenstruktur). Weiterhin gehen wir auf Repräsentationen von Graphen ein, behandeln diverse Graphalgorithmen (wie zum Beispiel Tiefen- und Breitensuche, kürzeste Wege, transitive Hülle, starke Komponenten und minimaler Spannbaum) sowie diverse Sortierverfahren (Mergesort, Heapsort, Quicksort, Bucketsort, Radixsort). Die Vorlesung soll die Fähigkeit schulen, bekannte Datenstrukturen professionell einzusetzen, neue Datenstrukturen bei Bedarf selbst zu entwerfen, die Korrektheit eines Algorithmus sauber zu begründen und seine Laufzeit zu analysieren.

    Voraussetzungen

    Die Kenntnis einer höheren Programmiersprache ist hilfreich, aber nicht im engeren Sinne erforderlich.

    Literatur

    Die Vorlesung orientiert sich an den folgenden Quellen:
    Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen - Die Grundwerkzeuge. Springer. Das Buch ist über den OPAC der RUB innerhalb des Campusnetzes kostenlos erhältlich!
    Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Oldenbourg Verlag.
    Aho, Hopcroft & Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley.


    Zu den Übungsaufgaben

    Zur Teilnahme am Übungsbetrieb ist eine Anmeldung über Blackboard erforderlich. Die Anmeldung wird am 18. April nach der Vorlesung freigeschaltet.

    Während der Vorlesungszeit wird jeden Freitag ein neues Übungsblatt auf dieser Seite bereitgestellt. Die bearbeiteten Aufgaben sind am Dienstag 11 Tage später bis spätestens 10:00 Uhr abzugeben. Die Abgabekästen befinden sich auf NA 02 gegenüber von Raum 257. Die Abgabe soll nach Aufgaben getrennt erfolgen. Bitte auf jedes Blatt die Namen und die Übungsgruppe schreiben! Die korrigierten Blätter werden in den Übungen zurückgegeben.

    Die Blätter können in Gruppen bis zu maximal drei Personen bearbeitet und abgegeben werden.

    Einen Übungsschein erhält, wer mindestens die Hälfte der Punkte erreicht, mindestens einmal vorrechnet und regelmäßig an den Übungen teilnimmt.

    Die durch Übungsaufgaben erreichten Punkte werden anteilig auf die Abschlussklausur als Bonus angerechnet, wobei 100% der bei den Übungen maximal vergebenen Punkte 10% der bei der Abschlussklausur maximal vergebenen Punkten entsprechen. Dabei kann die maximal erreichte Punktezahl in der Abschlussklausur 100% nicht übersteigen. Dieser Bonus gilt nur für die Klausur im Sommersemester 2017 und nicht für Klausuren in späteren Semestern. Bei einer mündlichen Prüfung wird bei Erreichen von 60% der Punkte in den Übungen ein Bonus von -0,3 gewährt, wobei die Bestnote von 0,7 nicht verbessert werden kann. Dieser Bonus gilt nur für mündliche Prüfungen am ersten Termin direkt nach Vorlesungsende.

    Zur Klausur

    Die 120 minütige Klausur findet am Dienstag, den 25. Juli 2017 von 14:00 Uhr bis 16:00 Uhr in den Hörsälen HNB und HIC statt. Die Verteilung der Klausurteilnehmer auf die Hörsäle erfolgt nach dem Anfangsbuchstaben des Nachnamens:

    • A-K: Hörsaal HIC
    • L-Z: Hörsaal HNB

    Als Hilfsmittel dürfen 3 handgeschriebene oder 2 maschinell beschriebene DIN A4-Seiten benutzt werden.

    Die Teilnahme an der Klausur ist nur nach vorheriger Anmeldung möglich. Die Anmeldung zur Klausur erfolgt nach den Regeln und Fristen des für Sie zuständigen Prüfungsamtes. Wenden Sie sich bei Fragen hierzu am besten direkt an Ihr Prüfungsamt.

    Im Wintersemester 2017/2018 wird eine Nachklausur stattfinden. Bitte beachten Sie, dass für die Nachklausur keine Bonuspunkte aus Übungsaufgaben angerechnet werden!

    Zu mündlichen Prüfungen (nur relevant für B.Sc. in Mathematik)

    Für die Studierenden, die "Datenstrukturen" im Hauptfach des Bachelor of Science in der Mathematik belegen, wird am Ende des Semesters eine mündliche Prüfung angeboten. Hierfür stehen die folgenden beiden Termine zur Wahl:

    • Dienstag, der 25. Juli 2017
    • Dienstag, der 26. September 2017

    Bitte beachten Sie, dass Bonuspunkte aus den Übungsaufgaben nur im ersten Termin angerechnet werden!

    Achtung: Bitte vereinbaren Sie vor der Prüfungsanmeldung zunächst Ihren Prüfungstermin mit Uhrzeit mit Stef Sijben.

    Die Anmeldung muss mindestens zwei Wochen vor der jeweiligen Prüfung per VSPL erfolgen. Ein Rücktritt von einer angemeldeten Prüfung muss mindestens drei Tage vor der Prüfung in schriftlicher Form ohne Angabe von Gründen im Prüfungsamt erfolgen.

    Kontakt