Modulbeschreibung Algorithmen und Datenstrukturen
Bachelor-Pflichtmodul: Algorithmen und Datenstrukturen
1. Modulkennung
IP4
2. Studiengang
Bachelorstudiengang Informatik, Masterstudiengang Bioinformatik
3. Modulbezeichnung
Algorithmen und Datenstrukturen (AD), Algorithms and Data Structures (AD)
4. Modul-Verantwortlicher
Menzel
5. Veranstalter/Dozent
Jantzen, Kurtz, Menzel, Neumann, Rarey, Ritter, Valk,
6. Sprache
Deutsch mit deutsch- und englischsprachigem Lehrmaterial
7. Motivation, Bedeutung für / Stellung im Gesamtprogramm
Die Entwicklung von Algorithmen zur Lösung von Problemen mit dem Computer sind zentraler Bestandteil der Informatik. Unabhängig von einer späteren Ausrichtung in theoretischer, praktischer und anwendungsbezogener Informatik bzw. einer Vertiefung in einer der zahlreichen Spezialgebiete sind fundamentale Kenntnisse und Fähigkeiten zur Auswahl problemnaher Datenstrukturen, zum Algorithmenentwurf, sowie zur Analyse und Bewertung von Algorithmen unabdingbar. Jeder Informatiker sollte zudem eine Reihe von grundlegenden Algorithmen und Datenstrukturen kennen, um diese als Teillösungen bzw. als Ausgangspunkt für komplexe Fragestellungen gewinnbringend einsetzen zu können. Wesentlich hierfür ist auch die Fähigkeit zum Umsetzen eines Algorithmus in eine effiziente Implementierung.
In der Veranstaltung werden wichtige Klassen von Algorithmen vorgestellt und exemplarische Anwendungen in den verschiedensten Bereichen der Informatik diskutiert. Damit werden die Grundlagen für ein vertieftes algorithmisches Verständnis gelegt, das in zahlreichen auf diesem Modul aufbauenden Wahlpflichtmodulen erworben werden kann
8. Lernziele/Kompetenzen
8.1 Passung Leitbild
Vermittlung von Problemlösungskompetenz (Konzeptionalisierung und Realisierung) zur Lösung formalisierbarerer, schwieriger Probleme meist kombinatorischer Natur.
8.2 Grundlagen-/Faktenwissen
- Datenstrukturen und ihre Eigenschaften
- Bewertungskriterien für Algorithmen
- Effiziente Datenstrukturen und Algorithmen für ausgewählte grundlegende Probleme
- Wechselwirkungen zwischen Algorithmus und Datenstruktur
8.3 Methodenwissen
- Methoden für das selbständige, kreative Entwickeln geeigneter Datenstrukturen und effizienter Algorithmen
- Methoden zum Korrektheitsbeweis und zur Effizienzanalyse von Algorithmen und Datenstrukturen
- Erkennen von Gemeinsamkeiten innerhalb von Algorithmenfamilien im Hinblick auf eine modularisierte Umsetzung als flexibel einsetzbare Rahmenwerke
8.4 Transferkompetenz
- Fähigkeit zum selbständigen Aneignen von neuen Algorithmen, Datenstrukturen, sowie algorithmischen Ideen und Analysen
- Übertragen bekannter Algorithmen auf neue Problemstellungen
- Modifikation von Algorithmen im Hinblick auf veränderte Anforderungen
- Einsetzen mathematischer Methoden zum Korrektheitsbeweis und zur Effizienzanalyse
8.5 Normativ-bewertende Kompetenz
- Beurteilen der Qualität von Algorithmen und algorithmischen Ansätzen im Hinblick auf Problemadäquatheit, Effizienz, Korrektheit, Vollständigkeit und praktische Verwertbarkeit
- Erkennen grundlegender Beschränkungen von gegebenen Algorithmen
- Einschätzen von Informationsverarbeitungsproblemen in Hinblick auf ihre algorithmische Komplexität
8.6 ABK/BOK/Schlüsselqualifikationen
- Kooperations- und Teamfähigkeit in den Präsenzübungen
- Strategien des Wissenserwerbs: Kombination aus Vorlesung, Vor- und Nachbereitung am Vorlesungsmaterial, Präsenzübungen mit betreuter Gruppenarbeit und eigenständiges Lösen von Übungsaufgaben
- Kreatives Problemlösen am Beispiel der Entwicklung effizienter Algorithmen
9. Lehrveranstaltungen
4 SWS (3V, 1Ü), maximale Übungsgruppengröße: 20
10. Inhalt
- Einführung
- Algorithmen und ihre Bewertung, Bewertungskriterien (Problemadäquatheit, Zeit- und Platzkomplexität, (strukturelle) Echtzeitfähigkeit, Korrektheit und Vollständigkeit)
- Komplexität
Rechnermodelle und Komplexitätsmaße; Komplexitätsanalyse von iterativen und rekursiven Algorithmen; untere und ober Schranken, beobachtbare Komplexität - Algorithmen für lineare Datenstrukturen
- Arrays, Listen, Stapel, Schlangen; Suchen und Sortieren; Hash-Indizierung; Anwendungen
- Algorithmen für hierarchische Datenstrukturen
- (balancierte) Suchbäume, dynamisches Balancieren; Zugriff zu semistrukturierten Daten
- Algorithmen über Graphen
- Durchlaufen von Graphen, Graphunifikation
- Nichtdeterministische Suche
- Suche in Bäumen und Graphen, Suchstrategien; Optimierungsprobleme (kürzeste Wege: dynamische Programmierung; heuristische Suche: A*); Anwendungen (symbolischer Mustervergleich, Wegsuche, usw.)
11. Bezüge zu anderen Modulen
- Innerhalb des Studiengangs: Aufbauend auf Kenntnissen und Fertigkeiten aus dem Zyklus Entwicklung von Softwaresystemen und dem Modul Formale Grundlagen der Informatik I schafft das Modul die Voraussetzungen für das Verständnis der algorithmischen Grundlagen von Informatiksystemen, insbesondere in den Wahlpflichtmodulen Interaktive Visuelle Computing, Grundlagen der Wissensverarbeitung, Verteilte Systeme und Informationssicherheit, sowie Datenbanken und Informationssysteme. Eine weitere Vertiefung ist im Wahlpflichtmodul Algorithmik möglich.
- In anderen Studiengängen: Das Modul eignet sich als Nebenfachmodul sowie als Bestandteil von Wirtschafts- und Bioinformatik-Studiengängen. Darüber hinaus ist ein Einbringen als Wahlmodul naturwissenschaftlicher Studiengänge denkbar.
12. Modulvoraussetzungen
- Verbindlich: keine
- Empfohlen: Softwareentwicklung I, Diskrete Mathematik, Formale Grundlagen der Informatik I
13. Semester, Studienjahr /-phase
- Studienabschnitt: 1
- Referenzsemester: 3
14. Prüfungsleistungen
Die Zulassung zur Modulprüfung setzt die regelmäßige und erfolgreiche Teilnahme
an Übungen/Praktikum voraus; die Teilnahme gilt grundsätzlich als erfolgreich,
wenn alle Aufgaben bearbeitet und mindestens 50% richtig gelöst wurden; im Falle
abweichender Kriterien müssen diese zu Beginn der Veranstaltung bekannt
gemacht werden.
Gemeinsame Modulprüfung für alle Lehrveranstaltungen des Moduls; in der Regel
schriftlich (Klausur) und in deutscher Sprache; bei Modus-Abweichung Bekanntgabe
zu Beginn der Veranstaltung.
15. Bewertung
Gesamt: 6 Leistungspunkte
(Algorithmen und Datenstrukturen: 3 Leistungspunkte, Übungen zu Algorithmen und Datenstrukturen: 3 Leistungspunkte)
16. Periodizität
Wintersemester, jährlich, Dauer (1 Semester)
17. Methodische Aufbereitung und Medienformen
- Vorlesung mit Beamer, Overhead und Tafel
- Übungen in Kleingruppen
- Erwartete Aktivitäten der Studierenden: selbständiges Bearbeiten von Übungsaufgaben, aktive Mitarbeit in den Präsenzübungen
18. Literatur
- Ralf Hartmut Güting & Stefan Diekert: Datenstrukturen und Algorithmen, Teubner (2003)
- Norbert Blum: Algorithmen und Datenstrukturen, Oldenbourg (2004)
- Thomas Ottmann & Peter Widmayer: Algorithmen und Datenstrukturen, B·I· Wissenschaftsverlag (1992)
- Thomas H. Corman & Charles E. Leiserson & Ronald L. Rivest & Clifford Stein: Introductions to Algorithms, MIT-Press (2003)
- Sara Base & Allen van Gelder. Computer Algorithms, Addison Wesley (2000)
- Richard Johnsonbaugh & Marcus Schaefer: Algorithms, Pearson (2004)
- Gilles Brassard & Paul Brately. Fundamentals of Algorithms, Prentice Hall (1996)
