RUB » LMI » Lehre » Datenstrukturen SS 2016

Datenstrukturen SS 2016

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 - Thorsten Kiss
Gruppe 3: Di, 16-18 Uhr, NA 2/99 - Leonie Selbach
Für den Besuch der Übungen ist eine Anmeldung via Blackboard erforderlich.
Korrekteure:
  • Leonie Selbach, Sprechstunde Mo 14-15 Uhr, NA 1/31
  • Hendrik Waldner, Sprechstunde Mo 14-15 Uhr, NA 1/31
    		•

    Aktuelles

    • 20.2.2017: Die Einsicht zur Nachklausur findet am Donnerstag, den 23.02.2017, von 11 bis 12 Uhr in NA 1/70 statt.
    • 29.9.2016: Die Nachklausur findet statt am 20.02.2017 von 13:00-15:30 Uhr im HNC 20.
    • 30.8.2016: Der 2. Termin für mündliche Prüfungen für Studierende der Mathematik ist der 6.10.16.
    • 28.7.2016: Die Ergebnisse der Klausur vom 26.07.2016 stehen ab sofort in Blackboard.
    • 27.7.2016: Die Einsicht zur Klausur vom 26.07.2016 findet am Freitag, den 29.07.2016, von 11 bis 12 Uhr in NA 1/64 statt.
    • 20.7.2016 Die Klausur schreiben Teilnehmer mit Nachname beginnend mit A-K in HNC 10 und mit L-Z in HNC 20.
    • 6.7.2016: Die Vorlesung am 14.7.16 entfällt.
    • 5.7.2016: In der Klausur dürfen als Hilfsmittel 3 handgeschriebene oder 2 maschinell beschriebene DIN A4-Seiten benutzt werden.
    • 23.5.2016: Ab 24.5. leitet Thorsten Kiss die Übungsgruppe am Dienstag, 12-14 Uhr.
    • 19.4.2016: Ab kommender Woche (25.4.) finden nur die drei Übungen am Dienstag statt. Teilnehmer der vierten Gruppe tragen sich bitte neu ein.
    • 19.4.2016: Die Uhrzeiten der Klausur haben sich geändert: sie findet statt am Di 26.7.16 von 11:15 bis 13:45.
    • 13.4.2016: Bitte melden Sie sich bis spätestens Fr 15.4. um 12:00 Uhr für die Übungen in Blackboard an!

    Materialien

    Hausaufgaben

    Präsenzaufgaben

    Themenliste

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

    • 1. Woche (KW 15): Asymptotische Analyse, Maschinenmodell, Pseudocode, Invarianten, Binäre Suche, Mastertheorem, Analyse im mittleren Fall (Kurzfassung der Abschnitte 2.1, 2.2, 2.3, 2.4, 2.5, 2.6, 2.7.1)
    • 2. Woche (KW 16): Randomisierte Algorithmen, P und NP, Amortisierte Analyse, Listen und Arrays (Kurzfassung der Abschnitte 2.8, 2.10, 3.2.3, 3.1, 3.2, 3.4), Graphen (Abschnitt 2.9)
    • 3. Woche (KW 17): Hashing (Abschnitt 4)
    • 4. Woche (KW 18): Sortieren (Abschnitte 5.1, 5.2, 5.3)
    • 5. Woche (KW 19): Sortieren und Auswählen (Abschnitt 5.4, 5.5, 5.6)
    • 6. Woche (KW 21): Prioritätswarteschlangen (Abschnitt 6.1)
    • 7. Woche (KW 22): Adressierbare Prioritätswarteschlangen (Abschnitt 6.2 ohne 6.2.2), Sortierte Folgen (Abschnitt 7.1)
    • 8. Woche (KW 23): Sortierte Folgen (Abschnitt 7)
    • 9. Woche (KW 24): Graphendarstellungen (Abschnitt 8), Graphendurchläufe (Abschnitt 9)
    • 10. Woche (KW 25): Anwendungen der Tiefensuche (Abschnitt 9.2), Kürzeste Wege: Grundbegriffe (Abschnitt 10.1)
    • 11. Woche (KW 26): Kürzeste Wege: Algorithmus von Dijkstra (Abschnitt 10.2,10.3,10.5)
    • 12. Woche (KW 27): Minimale Spannbäume (Abschnitt 11)
    • 13. Woche (KW 28): Analyse der Union-Find-Datenstruktur (Abschnitt 11.4) und Steinerbaumproblem (11.6.1)
    • 14. Woche (KW 29): Greedy und Dynamisches Programmieren (Auschnitt aus 12), kd-Bäume als geometrische Datenstruktur

    Die Themen der 14. Woche sind 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 hauptsächlich an der folgenden Quelle:
    Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen - Die Grundwerkzeuge. Springer.
    Das Buch ist über den OPAC der RUB innerhalb des Campusnetzes kostenlos erhältlich!

    Außerdem empfohlen:
    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 12. 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. Jedes Gruppenmitglied muss aber in der Lage sein, die Aufgaben vorzurechnen.

    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 2016 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 150 minütige Klausur findet am Dienstag, den 26. Juli 2016, um 11:15 Uhr in den Hörsälen HNC 10 und HNC 20 statt. Die Verteilung der Klausurteilnehmer auf die Hörsäle erfolgt nach dem Anfangsbuchstaben des Nachnamens:

    • A-K: Hörsaal HNC 10
    • L-Z: Hörsaal HNC 20

    Als Hilfsmittel dürfen 3 handgeschriebene oder 2 maschinell beschriebene DIN A4-Zettel 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 2016/2017 wird eine Nachklausur stattfinden, undzwar am 20.02.2017 von 13:00-15:30 Uhr im HNC 20. 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:

    • Montag, der 25. Juli 2016
    • Donnerstag, der 6. Oktober 2016

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

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

    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 (NA 02/73) erfolgen.

    Kontakt