Algorithmen und Datenstrukturen (AuD)10 ECTS
(englische Bezeichnung: Algorithms and Data Structures)

Lehrveranstaltungen:

• • Algorithmen und Datenstrukturen
    (Vorlesung, 4 SWS, Christoph Pflaum et al., Di, 8:15 - 9:45, H11; Mi, 14:15 - 15:45, H11; Die Lehrveranstaltungen zu diesem Modul werden letztmalig im WiSe 2021/22 angeboten.)
  • Tafelübungen zu Algorithmen und Datenstrukturen
    (Übung, 2 SWS, Norbert Oster)
  • Rechnerübungen zu Algorithmen und Datenstrukturen
    (Übung, 2 SWS, Norbert Oster)

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:

Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan:
Das Modul ist im Kontext der folgenden Studienfächer/Vertiefungsrichtungen verwendbar:

1. 079#72#H: 1. Semester
   (Po-Vers. 2007 | TechFak | Informatik (1. Staatsprüfung für das Lehramt an Hauptschulen) | Grundlagen- und Orientierungsprüfung | Algorithmen und Datenstrukturen)
2. 079#74#H
   (Po-Vers. 2013 | TechFak | Informatik (1. Staatsprüfung für das Lehramt an Mittelschulen) | Pflichtmodule der Grundlagen- und Orientierungsprüfung (GOP) | Algorithmen und Datenstrukturen)
3. Berufspädagogik Technik (Bachelor of Science)
   (Po-Vers. | TechFak | Berufspädagogik Technik (Bachelor of Science) | Gesamtkonto | Unterrichtsfach (Zweitfach) inkl. Fachdidaktik | Informatik | Algorithmen und Datenstrukturen)
4. Berufspädagogik Technik (Bachelor of Science)
   (Po-Vers. 2010 | TechFak | Berufspädagogik Technik (Bachelor of Science) | alte Prüfungsordnungen | Gesamtkonto | Unterrichtsfach (Zweitfach) inkl. Fachdidaktik | Informatik | Algorithmen und Datenstrukturen)
5. Berufspädagogik Technik (Bachelor of Science)
   (Po-Vers. 2010 | TechFak | Berufspädagogik Technik (Bachelor of Science) | alte Prüfungsordnungen | Gesamtkonto | Unterrichtsfach (Zweitfach) inkl. Fachdidaktik | Informatik | Algorithmen und Datenstrukturen)
6. Berufspädagogik Technik (Bachelor of Science)
   (Po-Vers. 2011 | TechFak | Berufspädagogik Technik (Bachelor of Science) | Studienrichtung Elektrotechnik und Informationstechnik | Gesamtkonto | Unterrichtsfach (Zweitfach) inkl. Fachdidaktik | Informatik | Algorithmen und Datenstrukturen)
7. Berufspädagogik Technik (Bachelor of Science)
   (Po-Vers. 2011 | TechFak | Berufspädagogik Technik (Bachelor of Science) | Studienrichtung Metalltechnik | Unterrichtsfach (Zweitfach) inkl. Fachdidaktik | Informatik | Algorithmen und Datenstrukturen)
8. Berufspädagogik Technik (Bachelor of Science)
   (Po-Vers. 2020w | TechFak | Berufspädagogik Technik (Bachelor of Science) | Studienrichtung Metalltechnik | Gesamtkonto | Unterrichtsfach (Zweitfach) inkl. Fachdidaktik | Informatik | Algorithmen und Datenstrukturen)
9. Berufspädagogik Technik (Bachelor of Science)
   (Po-Vers. 2020w | TechFak | Berufspädagogik Technik (Bachelor of Science) | Gesamtkonto | Unterrichtsfach (Zweitfach) inkl. Fachdidaktik | Informatik | Algorithmen und Datenstrukturen)
10. Computational Engineering (Rechnergestütztes Ingenieurwesen) (Bachelor of Science): 1. Semester
    (Po-Vers. 2007 | TechFak | Computational Engineering (Rechnergestütztes Ingenieurwesen) (Bachelor of Science) | alte Prüfungsordnungen | Grundlagen- und Orientierungsprüfung (GOP) | Algorithmen und Datenstrukturen)
11. Computational Engineering (Rechnergestütztes Ingenieurwesen) (Bachelor of Science): 1. Semester
    (Po-Vers. 2009 | TechFak | Computational Engineering (Rechnergestütztes Ingenieurwesen) (Bachelor of Science) | alte Prüfungsordnungen | Grundlagen- und Orientierungsprüfung (GOP) | Algorithmen und Datenstrukturen)
12. Computational Engineering (Rechnergestütztes Ingenieurwesen) (Bachelor of Science): 1. Semester
    (Po-Vers. 2010 | TechFak | Computational Engineering (Rechnergestütztes Ingenieurwesen) (Bachelor of Science) | Grundlagen- und Orientierungsprüfung (GOP) | Algorithmen und Datenstrukturen)
13. Informatik (1. Staatsprüfung für das Lehramt an Gymnasien): 1. Semester
    (Po-Vers. 2007 | TechFak | Informatik (1. Staatsprüfung für das Lehramt an Gymnasien) | Grundlagen- und Orientierungsprüfung | Algorithmen und Datenstrukturen)
14. Informatik (1. Staatsprüfung für das Lehramt an Realschulen): 1. Semester
    (Po-Vers. 2007 | TechFak | Informatik (1. Staatsprüfung für das Lehramt an Realschulen) | Grundlagen- und Orientierungsprüfung | Algorithmen und Datenstrukturen)
15. Informatik (Bachelor of Arts (2 Fächer)): 1. Semester
    (Po-Vers. 2008 | TechFak | Informatik (Bachelor of Arts (2 Fächer)) | alte Prüfungsordnungen | Grundlagen- und Orientierungsprüfung (GOP) | Module der Grundlagen- und Orientierungsprüfung Informatik | Algorithmen und Datenstrukturen)
16. Informatik (Bachelor of Arts (2 Fächer)): 1. Semester
    (Po-Vers. 2010 | TechFak | Informatik (Bachelor of Arts (2 Fächer)) | Grundlagen- und Orientierungsprüfung (GOP) | Algorithmen und Datenstrukturen)
17. Informatik (Bachelor of Arts (2 Fächer))
    (Po-Vers. 2013 | TechFak | Informatik (Bachelor of Arts (2 Fächer)) | Grundlagen- und Orientierungsprüfung (GOP) | Algorithmen und Datenstrukturen)
18. Informatik (Bachelor of Science): 1. Semester
    (Po-Vers. 2007 | TechFak | Informatik (Bachelor of Science) | Grundlagen- und Orientierungsprüfung (GOP) | Algorithmen und Datenstrukturen)
19. Informatik (Bachelor of Science): 1. Semester
    (Po-Vers. 2009s | TechFak | Informatik (Bachelor of Science) | Grundlagen- und Orientierungsprüfung | Algorithmen und Datenstrukturen)
20. Informatik (Bachelor of Science): 1. Semester
    (Po-Vers. 2009w | TechFak | Informatik (Bachelor of Science) | Grundlagen- und Orientierungsprüfung (GOP) | Algorithmen und Datenstrukturen)
21. Information and Communication Technology (Master of Science)
    (Po-Vers. 2019s | TechFak | Information and Communication Technology (Master of Science) | Gesamtkonto | Wahlmodule | Wahlmodule aus dem Angebot von EEI und Informatik | Algorithmen und Datenstrukturen)
22. Informations- und Kommunikationstechnik (Bachelor of Science): 1. Semester
    (Po-Vers. 2007 | TechFak | Informations- und Kommunikationstechnik (Bachelor of Science) | Grundlagen- und Orientierungsprüfung (GOP) | 1. Semester | Algorithmen und Datenstrukturen)
23. Informations- und Kommunikationstechnik (Bachelor of Science): 1. Semester
    (Po-Vers. 2009 | TechFak | Informations- und Kommunikationstechnik (Bachelor of Science) | Grundlagen- und Orientierungsprüfung (GOP) | Wahlpflichtmodule der Grundlagen- und Orientierungsprüfung | Algorithmen und Datenstrukturen)
24. Informations- und Kommunikationstechnik (Master of Science)
    (Po-Vers. 2010 | TechFak | Informations- und Kommunikationstechnik (Master of Science) | Gesamtkonto | Wahlbereiche, Praktika, Seminar, Masterarbeit | Wahlmodule aus dem Angebot von EEI und Informatik | Algorithmen und Datenstrukturen)
25. Informations- und Kommunikationstechnik (Master of Science)
    (Po-Vers. 2016s | TechFak | Informations- und Kommunikationstechnik (Master of Science) | Gesamtkonto | Wahlbereiche, Praktika, Seminar, Masterarbeit | Wahlmodule aus dem Angebot von EEI und Informatik | Algorithmen und Datenstrukturen)
26. Mathematik (Bachelor of Science): 1. Semester
    (Po-Vers. 2007 | NatFak | Mathematik (Bachelor of Science) | alte Prüfungsordnungen | Grundlagen- und Orientierungsprüfung (GOP) | Algorithmen und Datenstrukturen)
27. Mathematik (Bachelor of Science): 1. Semester
    (Po-Vers. 2007 | NatFak | Mathematik (Bachelor of Science) | alte Prüfungsordnungen | Gesamtkonto | Nebenfach Informatik | Algorithmen und Datenstrukturen)
28. Mathematik (Bachelor of Science): 1. Semester
    (Po-Vers. 2009 | NatFak | Mathematik (Bachelor of Science) | alte Prüfungsordnungen | Nebenfach Informatik | Module im 1. Studienjahr | Algorithmen und Datenstrukturen)
29. Mathematik (Bachelor of Science)
    (Po-Vers. 2015w | NatFak | Mathematik (Bachelor of Science) | Module des Nebenfachs | Nebenfach Informatik | Algorithmen und Datenstrukturen)
30. Mathematik (Bachelor of Science)
    (Po-Vers. 2019w | NatFak | Mathematik (Bachelor of Science) | weitere Module der Bachelorprüfung | Module des Nebenfachs | Nebenfach Informatik | Algorithmen und Datenstrukturen)
31. Physische Geographie (Bachelor of Science)
    (Po-Vers. 2007 | NatFak | Physische Geographie (Bachelor of Science) | alte Prüfungsordnungen | Gesamtkonto | Wahlfächer | 1. Wahlfach | Informatik | Algorithmen und Datenstrukturen)
32. Physische Geographie (Bachelor of Science)
    (Po-Vers. 2007 | NatFak | Physische Geographie (Bachelor of Science) | alte Prüfungsordnungen | Gesamtkonto | Wahlfächer | Weitere Wahlfächer | Informatik | Algorithmen und Datenstrukturen)
33. Technomathematik (Bachelor of Science): 1. Semester
    (Po-Vers. 2007 | NatFak | Technomathematik (Bachelor of Science) | Grundlagen- und Orientierungsprüfung (GOP) | Algorithmen und Datenstrukturen)
34. Technomathematik (Bachelor of Science): 1. Semester
    (Po-Vers. 2009 | NatFak | Technomathematik (Bachelor of Science) | Fachmodule Technik | Module im 1. Studienjahr | Algorithmen und Datenstrukturen)
35. Technomathematik (Bachelor of Science)
    (Po-Vers. 2015w | NatFak | Technomathematik (Bachelor of Science) | Nebenfach Informatik | Algorithmen und Datenstrukturen)
36. Technomathematik (Bachelor of Science)
    (Po-Vers. 2019w | NatFak | Technomathematik (Bachelor of Science) | Gesamtkonto | Nebenfach Informatik | Algorithmen und Datenstrukturen)
37. Wirtschaftsinformatik (Bachelor of Science): 1. Semester
    (Po-Vers. 100 | ReWiFak | Wirtschaftsinformatik (Bachelor of Science) | Gesamtkonto | Grundlagen- und Orientierungsprüfung (GOP) | Algorithmen und Datenstrukturen)
38. Wirtschaftsinformatik (Bachelor of Science): 1. Semester
    (Po-Vers. 2010 | ReWiFak | Wirtschaftsinformatik (Bachelor of Science) | Pflichtbereich (Methodenkompetenz) | Module der Assessmentprüfung (GOP) | Informatik | Algorithmen und Datenstrukturen)
39. Wirtschaftsinformatik (Bachelor of Science): 1. Semester
    (Po-Vers. 2015w | ReWiFak | Wirtschaftsinformatik (Bachelor of Science) | Gesamtkonto | Grundlagen- und Orientierungsprüfung (GOP) | Algorithmen und Datenstrukturen)
40. Wirtschaftsinformatik (Bachelor of Science): 1. Semester
    (Po-Vers. 2017w | ReWiFak | Wirtschaftsinformatik (Bachelor of Science) | Gesamtkonto | Grundlagen- und Orientierungsprüfung (GOP) | Algorithmen und Datenstrukturen)
41. Wirtschaftsinformatik (Bachelor of Science)
    (Po-Vers. 2018w | ReWiFak | Wirtschaftsinformatik (Bachelor of Science) | Gesamtkonto | Grundlagen- und Orientierungsprüfung (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 2021/2022, 1. Wdh.: SS 2022

1. Prüfer:

Philipp/Oster/Riehle/Stammin/Brinda

Termin: 11.04.2022, 08:00 Uhr, Ort: s. Aushang
Termin: 11.08.2022
Termin: 11.08.2022

Ü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 2021/2022, 1. Wdh.: SS 2022

1. Prüfer:

Philipp/Oster/Riehle/Stammin/Brinda