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

    • 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 und Folien

    Die Kapitelangaben beziehen sich, falls nicht anders angegeben, 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) - Folien VL1 Folien VL2
    • 2. Woche (KW 17): Graphen (Abschnitt 2.9), Listen und Arrays (Kurzfassung der Abschnitte 3.1, 3.2, 3.4) - Folien VL3 Folien VL4
    • 3. Woche (KW 18): Hashing (Abschnitt 4) - Folien VL5 und VL6
    • 4. Woche (KW 19): Sortieren und Auswählen (Abschnitte 5.1, 5.2, 5.3, 5.4, 5.5) - Folien VL7 und VL8
    • 5. Woche (KW 20): Sortieren fortgesetzt (Abschnitt 5.6), Prioritätswarteschlangen (Abschnitt 6.1) - Folien VL9
    • 6. Woche (KW 21): Adressierbare Prioritätswarteschlangen (Abschnitt 6.2) Folien VL10 und VL11
    • 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) Folien VL12 bis VL14
    • 9. Woche (KW 25): Graphendarstellungen (Abschnitt 8), Graphendurchläufe (Abschnitt 9) Folien VL15
    • 10. Woche (KW 26): Anwendungen der Tiefensuche (Abschnitt 9.2) Folien VL16 und VL17
    • 11. Woche (KW 27): Kürzeste Wege: Grundbegriffe (Abschnitt 10.1), Algorithmus von Dijkstra (Abschnitt 10.2,10.3,10.5.1) Folien VL18 und VL19
    • 12. Woche (KW 28): Minimale Spannbäume (Abschnitt 11) Folien VL20 und VL21

    Das Thema der 12. 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 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