Moduldetails
Algorithmen und Softwareentwicklung
DIS 2.1
Workload Credits Studiensemester Frequenz Dauer
180 h 6 2. Sem. jährlich 1 Sem.
1 Lehrveranstaltungen Kontaktzeit Selbststudium Sprache Gruppengröße
∑ 4 SWS / 60 h ∑ 120 h
DIS2.1
Algorithmen und Softwareentwicklung (Seminaristischer Unterricht)
DIS2.1
4 SWS / 60 h
DIS2.1
120 h
DIS2.1
Deutsch
DIS2.1
70
2 Lernergebnisse (learning outcomes / Kompetenzen):

Grundverständnis von Algorithmen

Das Modul vermittelt:

  • Verständnis für die Bedeutung von Algorithmen und Datenstrukturen
  • Kenntnis grundlegender Begriffe und Programmierparadigmen
  • Verständnis und Implementierung von oft genutzten komplexen Datentypen

Dies wird vertieft durch die Umsetzung von Algorithmen in einer Programmiersprache sowie durch die Diskussion von praktischen Anwendungen und realen Beispielen aus der IT.

Die Studierenden lernen auf diese Weise, die Relevanz, die Effizienz und den Nutzen von komplexeren Algorithmen in der Praxis zu erkennen, diese anzuwenden und erwerben die Fähigkeit zur Analyse und zum Verständnis komplexer technischer Probleme.
3 Inhalte:
DIS2.1

Einleitung

1. Motivation und Anwendungsbeispiele

  • Bedeutung von Algorithmen und Datenstrukturen in der Informatik
  • Praktische Anwendungen in verschiedenen Bereichen (z.B. Websuche, soziale Netzwerke, Bioinformatik)

2. Grundbegriffe und Notationen

  • Algorithmus, Pseudocode, Datenstruktur
  • Komplexitätsanalyse (Big O und andere Notation)

Grundlegende Datenstrukturen besser verstehen

3. Arrays und Listen

  • Statische vs. dynamische Arrays
  • Verkettete Listen (einfach, doppelt, zirkulär)
  • Implementierung und grundlegende Operationen (Einfügen, Löschen, Durchlaufen)

4. Stapel (Stacks) und Warteschlangen (Queues)

  • Konzepte und Anwendungsfälle
  • Implementierung mit Arrays und Listen

5. Bäume und binäre Bäume

  • Definitionen und Eigenschaften
  • Traversierungen (in-order, pre-order, post-order)
  • Implementierung und grundlegende Operationen
  • Binäre Suchbäume

6. Hash-Tabellen

  • Prinzipien des Hashing

7. Grundlegende Graphenkonzepte

  • Definitionen und Darstellungsformen (Adjazenzliste, Adjazenzmatrix)
  • Gewichtete vs. ungewichtete
  • Gerichtet vs. ungerichtet

8. Graphenalgorithmen (ein Überblick)

  • Tiefensuche (DFS) und Breitensuche (BFS)
  • Kürzeste Wege (Dijkstra, Bellman-Ford, Floyd-Warshall)
  • Minimaler Spannbaum (Prim, Kruskal)

Sortieren

9. Einführung in Sortierverfahren (ein Überblick)

  • Einfache Sortierverfahren: Bubble Sort, Insertion Sort, Selection Sort
  • Merge Sort, Quick Sort, Heap Sort
  • Linearzeit-Sortierverfahren: Counting Sort, Radix Sort, Bucket Sort

Fortgeschrittene Themen

10. Dynamische Programmierung

  • Prinzipien und Techniken
  • Beispielprobleme (z.B. Rucksackproblem, längste gemeinsame Teilfolge)

11. Greedy-Algorithmen

  • Konzept und Anwendungsfälle
  • Beispielalgorithmen (z.B. Huffman-Codierung, Aktivitätsauswahl)

Abschluss (optional)

12. Komplexitätstheorie und NP-Vollständigkeit

  • P vs. NP, NP-vollständige Probleme
  • Reduktionstechniken und praktische Relevanz
4 Lehrformen:
Seminaristischer Unterricht (DIS2.1)
5 Teilnahmevoraussetzungen:

Keine
6 Art der Prüfung:
Klausurarbeit
7 Voraussetzungen für die Vergabe von Kreditpunkten:
-
8 Art: Pflicht- oder Wahlmodul
Pflichtmodul
9 Bewertungsmethoden benotet/unbenotet
benotet
10 Stellenwert der Note für die Endnote:
3 %
11 Modulbeauftragte/r und hauptamtlich Lehrende
Modulbeauftragte/r: Prof. Dr. Matthias Groß
Hauptamtlich Lehrende: Prof. Dr. Matthias Groß
12 Sonstige Informationen:
-
13 Literatur / Quellen

Blum, Norbert (2013): Algorithmen und Datenstrukturen. München: Oldenbourg Wissenschaftsverlag (E-Book: https://doi.org/10.1524/9783486719666)

Häberlein, Tobias (2012): Praktische Algorithmik mit Python. München: Oldenbourg Wissenschaftsverlag (E-Book: https://doi.org/10.1524/9783486714449)

Sweigart, Al (2020): Automate the boring stuff with Python. San Francisco: No Starch Press, Inc. (E-Book: https://automatetheboringstuff.com/)