Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

Datenstrukturen, Algorithmen und Programmierung 2

Prof. (apl) Dr. Beate Bollig

Sommersemester 2020



Termine

Wann? Wo?
Vorlesung Di 12:15 - 14:00 SRG1/H.001
Vorlesung Do 14:15 - 16:00 SRG1/H.001

Aufgrund der aktuellen Pandemie findet in dieser Vorlesungszeit keine Präsenzlehre statt.
Bitte für weitere Informationen in den Moodle-Arbeitsraum einschreiben.


Hinweise

Die Lehrveranstaltung folgt inhaltlich den entsprechenden Vorlesungen aus den vergangenen Jahren an der Fakultät für Informatik. Die Lehrveranstaltungsmaterialien, insbesondere die Veranstaltungsfolien sind jedoch vollständig überarbeitet worden.

Allgemeine Informationen zu Teilnahmevoraussetzungen und Studienleistungen finden sich in den entsprechenden Modulbeschreibungen der jeweiligen Studiengänge.

Für Studierende der Fächer ETIT und IKT wird von ihrer Fakultät ein eigenes Praktikum angeboten (Informationen siehe auch weiter unten).

Studierende mit besonderen Bedürfnissen (Nachteilsausgleich) melden sich bitte vorab über das im Moodle-Arbeitsraum verlinkte Ticketsystem.
Schülerstudierende melden sich bitte vorab bei Amer Krivošija (LS 2).


Inhalt und Lernziele

Damit ein Algorithmus eine Aufgabenstellung sinnvoll löst, muss er zum einen korrekt arbeiten und zum anderen eine Lösung des betrachteten Problems in akzeptabler Zeit berechnen. Um die Qualität von Algorithmen zu bewerten, muss man daher ihre Korrektheit und ihren Ressourcenverbrauch beurteilen können. Neben der Bewertung vorgegebener Algorithmen ist ein wichtiges Arbeitsfeld eines Informatikers und einer Informatikerin der Entwurf neuer algorithmischer Lösungen. Die Kenntnis grundlegender Methoden zum Entwurf von Algorithmen und des Zusammenspiels von Algorithmen und Datenstrukturen ist dabei ein wichtiges Werkzeug.

Daher gehören zu den Lernzielen der Veranstaltung Datenstrukturen, Algorithmen und Programmierung 2 die folgenden Punkte.

  • Die Studierenden können Kriterien für die Effizienz algorithmischer Lösungen benennen und die Qualität von Algorithmen einschätzen.
  • Sie können mathematische Methoden für den Korrektheitsbeweis und die Effizienzanalyse von Algorithmen anwenden.
  • Die Studierenden können verschiedene Algorithmen für eine gegebene Problemstellung miteinander vergleichen und nach ihrer Effizienz anordnen.
  • Sie können komplexere Datenstrukturen mit ihren Eigenschaften sowie Vor- und Nachteilen beschreiben und erweitern.
  • Sie können die Wechselwirkung zwischen Algorithmen und eingesetzten Datenstrukturen erläutern und geeignete Datenstrukturen für algorithmische Lösungen auswählen.
  • Die Studierenden können grundlegende Entwurfsmethoden für Algorithmen wie Dynamische Programmierung, Greedy-Strategien oder Teile-und-Herrsche beschreiben und sie selbstständig für die Entwicklung algorithmischer Lösungen nutzen.
  • Sie können algorithmische Lösungen in lauffähige Programme übertragen.

Die in der Lehrveranstaltung untersuchten Probleme sind grundlegend für den Algorithmenentwurf und dienen insbesondere auch dazu, Entwurfs- und Analysemethoden zu illustrieren.

Für die präzise Formulierung von Aussagen sind formale Schreibweisen erforderlich. Insbesondere die Bearbeitung der Übungsaufgaben hilft, im Umgang mit formalen Schreibweisen Routine zu bekommen. Darüberhinaus schulen die Übungen die Problemlösungskompetenz und stärken die Kommunikationskompetenz, die notwendig ist, um Ideen und Lösungsvorschläge schriftlich und mündlich überzeugend präsentieren zu können.


Literatur

In dem Bereich Algorithmen und Datenstrukturen existieren eine Vielzahl von guten Lehrbüchern.

  • Die Veranstaltung richtet sich im Wesentlichen nach dem folgenden Buch.
    Cormen, T.H., Leiserson, C.E., Rivest, R., Stein, C.
    Introduction to Algorithms
    (Verschiedene Auflagen)
    MIT Press
    Das Buch ist in der Universitätsbibliothek der TU Dortmund verfügbar.
  • Das folgende Buch ist die deutsche Ausgabe.
    Cormen, T.H., Leiserson, C.E., Rivest, R., Stein, C.
    Algorithmen - Eine Einführung
    4. Auflage (2017)
    De Gruyter Oldenbourg MIT Press
    Das Buch ist in der Universitätsbibliothek der TU Dortmund als ebook verfügbar.
  • Das folgende Buch ergänzt den Vorlesungsinhalt.
    Kleinberg, J., Tardos, E.
    Algorithm design
    (Verschiedene Auflagen)
    Person Education
    Das Buch ist in der Universitätsbibliothek der TU Dortmund verfügbar.
    Drei Teilkapitel, die für die Vorlesung besonders wichtig sind, werden im Moodle-Arbeitsraum zur Verfügung gestellt.
  • Das folgende Buch eignet sich gut als ergänzende Literatur für Studienanfänger und -anfängerinnen und berücksichtigt u.a. auch Implementierungsaspekte.
    Dietzfelbinger, M., Mehlhorn, K., Sanders, P.
    Algorithmen und Datenstrukturen (2014)
    Springer Vieweg
    Das Buch ist in der Universitätsbibliothek der TU Dortmund als ebook verfügbar.

Praktikum

Ansprechpartner für organisatorische Fragen zum Praktikum DAP2 der Fakultät für Informatik ist Erik Thordsen (LS 8).

Weitere Informationen zu diesem Praktikum finden sich im dazugehörigen Moodle-Arbeitsraum.

Für Studierende der Studiengänge Bachelor IKT (Pflicht) und ETIT (Wahlpflicht) wird ein eigenes Praktikum in der Programmiersprache C/C++ vom Lehrstuhl für Kommunikationstechnik angeboten. Eine Teilnahme am Praktikum der Fakultät für Informatik ist nicht möglich. Die Anmeldung erfolgt über das LSF.

Ansprechpartner ist Wolfgang Endemann (LS Kommunikationstechnik, Fakultät 8).


Prüfungen

Prüfungsgrundlage ist der Inhalt der DAP2-Veranstaltung des Sommersemesters 2020

Wann? Wo?
Klausur I: 30.07.20, 12:30 - 15:30 Westfalenhalle 3, SRG1/2.009 und 2.0010
Klausur II: 28.09.20, 14:00 - 17:00 Westfalenhalle 1

Lediglich Studierende mit einem bewilligten Nachteilsausgleich schreiben die Klausuren im SRG1. Alle anderen Studierenden schreiben die erste Klausur in der Westfalenhalle 3 und die zweite in der Westfalenhalle 1.

Aufgrund der aktuellen Pandemie sind Änderungen bezüglich Zeit und Ort der zweiten Klausur möglich. Bitte aktuelle Informationen beachten.

Als erlaubtes Hilfsmittel ist in der Klausur ein selbst erstelltes beidseitig handschriftlich verfasstes DIN-A4-Blatt zugelassen. Auf der Vorder- und Rückseite ist ein oberer Rand von 2cm zu lassen und links oben ist der Name und die Matrikelnummer des Bearbeitenden einzutragen.


Übungen

Informationen zu den Übungen finden sich im Moodle-Arbeitsraum.

Bei organisatorischen Fragen zu den Übungen DAP2 erreichen Sie uns über das im Moodle-Arbeitsraum verlinkte DAP2 Overflow sowie das Ticketsystem.

Der Übungsbetrieb beginnt in der zweiten Vorlesungswoche. Das jeweils aktuelle Übungsblatt wird in der Regel montags im Moodle-Arbeitsraum bereitgestellt, die Abgabe der Bearbeitung erfolgt in der Regel bis zum darauffolgenden Montag 12:00 Uhr.


Veranstaltungsmaterialien

Die aktuellen Veranstaltungsmaterialien finden sich im Moodle-Arbeitsraum.


Vorlesungsplan

Datum Foliensatz Literatur Thema Kommentar
21.04.20 1 und 2 Cormen et al, Kapitel 1-3 Grundlagen Algorithmenanalyse
23.04.20 Grundlagen Algorithmenanalyse Siehe 21.4.20
28.04.20 3 Cormen et al, Kapitel 2.3 Teile-und-Herrsche Verfahren
30.04.20 4 Cormen et al, Kapitel 4 Teile-und-Herrsche Verfahren
05.05.20 5 Siehe auch Cormen et al, Kapitel 33.3 Teile-und-Herrsche Verfahren
07.05.20 6 Kleinberg/Tardos, Kapitel 4.1 Gierige Algorithmen
12.05.20 7 Kleinberg/Tardos, Kapitel 4.2 Gierige Algorithmen
14.05.20 8 Kleinberg/Tardos, u.a. Kapitel 6.4 Dynamische Programmierung
19.05.20 9 Kleinberg/Tardos, u.a. Kapitel 6.4 Dynamische Programmierung
26.05.20 10 Cormen et al, Kapitel 15.3, 15.4 Dynamische Programmierung
28.05.20 11 Cormen et al, Kapitel 10 und 12 Datenstrukturen
02.06.20 12 Siehe auch Cormen et al, Kapitel 13 Datenstrukturen
04.06.20 13 Cormen et al, Kapitel 6 Datenstrukturen
09.06.20 14 Cormen et al, Kapitel 18 Datenstrukturen
16.06.20 15 Cormen et al, Kapitel 11 bis 11.3.1 Datenstrukturen
18.06.20 16 Datenströme
23.06.20 17 Cormen et al, Kapitel 22.1 und 22.2 Graphalgorithmen
25.06.20 18 Cormen et al, Kapitel 24, insbesondere 24.3 Graphalgorithmen
30.06.20 19 Cormen et al, Kapitel 24, insbesondere 24.1 Graphalgorithmen
02.07.20 20 Cormen et al, Kapitel 25.1 und 25.2 Graphalgorithmen
07.07.20 21 Cormen et al, Kapitel 22, insbesondere ab 22.3 Graphalgorithmen
09.07.20 22 Cormen et al, Kapitel 23 Graphalgorithmen
14.07.20 23 U.a. Cormen et al, Kapitel 8.1 Untere Schranken
16.07.20 24 Cormen et al, Kapitel 35.1-35.2.1 Approximationsalgorithmen

Seitenanfang


Letzte inhaltliche Änderung: 28.07.2020 von B. Bollig