|
Algorithmen und Datenstrukturen (AuD)10 ECTS (englische Bezeichnung: Algorithms and Data Structures)
Modulverantwortliche/r: Michael Philippsen Lehrende:
Felix Freiling, Norbert Oster
Start semester: |
WS 2019/2020 | Duration: |
1 semester | Cycle: |
jährlich (WS) |
Präsenzzeit: |
120 Std. | Eigenstudium: |
180 Std. | Language: |
Deutsch |
Lectures:
-
-
Algorithmen und Datenstrukturen
(Vorlesung, 4 SWS, Felix Freiling, Tue, 16:15 - 17:45, H11; Thu, 8:15 - 9:45, H11)
-
Tafelübungen zu Algorithmen und Datenstrukturen
(Übung, 2 SWS, Norbert Oster et al.)
-
Rechnerübungen zu Algorithmen und Datenstrukturen
(Übung, 2 SWS, Norbert Oster et al.)
Inhalt:
- Grundlagen der Programmierung
Datenstrukturen
Objektorientierung
JAVA-Grundkenntnisse
Aufwandsabschätzungen
Grundlegende Algorithmen
Lernziele und Kompetenzen:
A - Fachkompetenz:
Die Studierenden...
1.) Grundlagen der Programmierung in Java
interpretieren Syntaxdiagramme für grundlegende Programmstrukturen und übertragen diese in entsprechenden Java-Code
deklarieren und verwenden Variablen mit adäquatem Java-Datentyp (primitive Typen, Reihungen, Zeichenketten)
überprüfen die Zulässigkeit der Variablendeklaration und -Wertzuweisung nach Java-Typ-Regeln
bestimmen den Datentyp und den Wert eines Java-Ausdrucks mit primitivem Datentyp und zugehörigen Operatoren
überführen einfache mathematische Ausdrücke in Java-Code
werten zusammengesetzte Bedingungen nach den Regeln der strikten bzw. faulen Auswertung für Java aus
konzipieren zu einer gegebenen Aufgabenstellung einen Algorithmus
implementieren einfache Algorithmen in Java unter Verwendung verschiedener Kontrollstrukturen
bestimmen die Gültigkeitsbereiche der Variablen anhand der Blockstruktur eines Java-Programms
strukturieren Java-Code in Methoden und entwickeln wiederverwendbare Funktionen
2.) Rekursion
beurteilen den Typ der Rekursion für gegebene Java-Methoden
entwerfen rekursive Algorithmen zu einer gegebenen Problemstellung unter Anwendung des Induktionsprinzips, des Teile-und-Herrsche-Prinzips sowie des Rücksetzverfahrens und implementieren diese jeweils in Java
entwickeln effizientere Lösungen, indem sie rekursive Methoden in endrekursive bzw. iterative Methoden umwandeln, implementieren diese jeweils in Java-Code und bewerten deren Laufzeit- und Speicherverbrauch
bewerten und verbessern rekursive Lösungen unter Verwendung von Dynamischer Programmierung und implementieren diese in Java-Code
3.) Aufwandsanalyse
analysieren den Laufzeitaufwand und den Speicherbedarf verschiedener Implementierungen
klassifizieren den asymptotischen Laufzeitaufwand anhand der Komplexitätsklassen des O-Kalküls
unterscheiden verschiedene Sortierverfahren (Blasensortierung, Sortieren durch Auswählen/Einfügen, Haldensortierung, Sortieren durch Verschmelzen/Zerlegen/Fachverteilen) hinsichtlich ihres Laufzeit- und Speicherplatzbedarfs
4.) Objekt-Orientierte Programmierung in Java
implementieren Java-Klassen gemäß textueller oder graphischer (UML) Spezifikation
wenden Verfahren zur systematischen Ableitung von Klassen und Attributen (Hauptwortextraktion), ihren statischen Beziehungen (Vererbung, Polymorphie, Assoziationen) und ihrem dynamischen Zusammenspiel (CRC, Kollaboration) aus einer textuellen Problemstellung an und entwickeln so kleine objekt-orientierte Java-Programme
instantiieren Klassen und verwenden Objektvariablen sachgerecht
unterscheiden statische und dynamische Bindung gemäß Polymorphie-Konzept von Java und wenden die Erkenntnisse sachgerecht bei der Entwicklung eigener Applikationen an
5.) Robustes Programmieren
wenden Checklisten an, um typische Programmierfehler im Vorfeld zu vermeiden oder nach der Programmierung zu identifizieren
benutzen verschieden Möglichkeiten zur Absicherung gegen Fehlersituationen und zur Fehlerrückmeldung (Rückgabewert, Ausnahmebehandlung)
wenden Junit zum Testen von Java-Programmen an
setzen Verfahren und Werkzeuge zur systematischen Lokalisierung und Behebung von Programmfehlern an (Debugging) und verbessern ihre Lösungen auf diese Weise iterativ
6.) Elementare Datentypen
übertragen eine Spezifikation in Form eines Abstrakten Datentyps (ADT) in ein gleichwertiges Java-Modul
erstellen eine formale Spezifikation eines Datentyps in Form eines Abstrakten Datentyps (ADT) aus einer gegebenen textuellen Beschreibung
verstehen die grundlegende Behälterdatentypen (Liste, Stapel, Schlange, Streutabelle) und deren Eigenschaften (insbesondere Laufzeit- und Speicherplatzbedarf ihrer Operationen)
verwenden generische Behälterdatentypen sachgerecht in eigenen Programmen
kennen die Verfügbarkeit generischer Behälterdatentypen in der Java-API und erschließen sich bei Bedarf selbst neue Datentypen sowie deren Funktionen aus der zugehörigen API-Spezifikation für die Verwendung in eigenen Programmen
7.) Bäume und Graphen
bewerten verschiedene Baum- und Graphdarstellungen hinsichtlich Zeitaufwand und Speicherbedarf
unterscheiden und klassifizieren die grundlegenden Baum-Arten (Suchbaum, AVL-Baum, Halde)
wenden die Grundoperationen (Einfügen, Suchen, Löschen, ggf. Restrukturieren) anhand von Beispieldaten auf gegebene Bäume artgerecht an
implementieren und verwenden verschiedene Baumstrukturen sachgerecht in eigenen Java-Programmen
führen verschiedene Durchlaufmöglichkeiten (Tiefensuche (DFS), Breitensuche (BFS)) für Graphen und Bäume auf Beispieldaten aus und setzen diese zielführend in eigenen Java-Programmen ein
wenden grundlegende Graphalgorithmen (Dijkstra, Floyd, Prim, Kruskal) auf Beispieldaten an und implementieren diese Verfahren in Java-Code
B - Selbst- und Sozialkompetenz:
Die Studierenden...
organisieren sich selbständig zu Gruppen und koordinieren in gegenseitiger Absprache den organisatorischen und technischen Ablauf der Gruppenarbeiten
kommunizieren und erarbeiten gemeinsam Lösungen für theoretische Fragestellungen und praktische Programmieraufgaben in Rahmen von Gruppenaufgaben
planen und wenden zielgerichtet Maßnahmen zu gegenseitigen Qualitätssicherung der eingereichten Lösungen an (prüfen wechselseitig die Gruppenabgaben)
verantworten gemeinsam das Ergebnis ihrer Gruppenarbeit, deren Bewertung für beide Gruppenpartner gleichermaßen gilt
Literatur:
Lehrbuch: Saake, Sattler: „Algorithmen und Datenstrukturen - Eine Einführung mit JAVA“
Weitere Informationen:
www: https://www.studon.fau.de/
Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan: Das Modul ist im Kontext der folgenden Studienfächer/Vertiefungsrichtungen verwendbar:
- Informations- und Kommunikationstechnik (Bachelor of Science): 1. Semester
(Po-Vers. 2009 | TechFak | Informations- und Kommunikationstechnik (Bachelor of Science) | Grundlagen- und Orientierungsprüfung (GOP) | Wahlpflichtmodule GOP | Algorithmen und Datenstrukturen)
Studien-/Prüfungsleistungen:
Algorithmen und Datenstrukturen (Prüfungsnummer: 30501)
- Prüfungsleistung, Klausur, Dauer (in Minuten): 120, benotet
- Anteil an der Berechnung der Modulnote: 100.0 %
- weitere Erläuterungen:
- Zur Klausur sind KEINE Hilfsmittel zugelassen - insbesondere KEINE elektronischen Geräte mit eigenem Betriebssystem (z.B. Handy, SmartWatch o.ä.).
Bei den schriftlichen Prüfungen kann ein zweisprachiges Wörterbuch verwendet werden. Es darf sich dabei auch um ein Fachwörterbuch handeln. Ergänzungen oder Anmerkungen sind nicht erlaubt. Die Kandidaten werden gebeten, ihre Wörterbücher an den jeweiligen Prüfungstagen bei den Aufsichten zur Kontrolle vorzulegen. Elektronische Wörterbücher sind ausdrücklich verboten.
Die Klausur muss mit einem dokumentenechten Stift (Kugelschreiber, Füller) ausgefüllt werden. Bleistifte, Buntstifte o.ä. sind NICHT zugelassen.
- Prüfungssprache: Deutsch
- Erstablegung: WS 2019/2020, 1. Wdh.: SS 2020
1. Prüfer: | Philipp/Oster/Riehle/Stammin/Brinda |
- Termin: 20.08.2020, 08:00 Uhr, Ort: Tentoria
Termin: 29.03.2021, 08:00 Uhr, Ort: s. Aushang
Termin: 29.07.2021, 08:00 Uhr, Ort: BASPH
Übungen zu Algorithmen und Datenstrukturen (Prüfungsnummer: 30502)
- Studienleistung, Übungsleistung, unbenotet
- weitere Erläuterungen:
Bearbeitung wöchentlicher Übungsblätter, die je zur Hälfte aus Einzel- bzw. Gruppenaufgaben bestehen.
Für den unbenoteten Übungsschein sind sowohl 60% der möglichen Einzelpunkte als auch 60% der Gruppenpunkte erforderlich.
- Erstablegung: WS 2019/2020, 1. Wdh.: SS 2020
1. Prüfer: | Philipp/Oster/Riehle/Stammin/Brinda |
|
|
|