|
| Code: | 237400 |
| Modul: | Algorithmen und Komplexität |
| Module title: | Algorithms and Complexity |
| Version: | 1.0 (01/2018) |
| letzte Änderung: |
02.12.2021 |
| Modulverantwortliche/r: |
Prof. Dr. rer. nat. Wagenknecht, Christian
c.wagenknecht@hszg.de |
|
angeboten in den 3 Studiengängen:
| Informatik (B.Sc.) gültig ab Matrikel 2018 |
Informatik (B.Sc.) gültig ab Matrikel 2020 |
Informatik (B.Sc.) gültig ab Matrikel 2024 |
|
| Modul läuft im: | SoSe+WiSe (Sommer- und Wintersemester)
|
| Niveaustufe: | Bachelor/Diplom |
| Dauer des Moduls: | 1 Semester |
| Status: | Pflichtmodul |
| Lehrort: | Görlitz |
| Lehrsprache: | Deutsch |
| Workload* in |
SWS ** |
Semester |
| Zeit- std. | ECTS-
Pkte |
1 |
2 |
3 |
4 |
5 |
6 |
|
V |
S |
P |
W |
V |
S |
P |
W |
V |
S |
P |
W |
V |
S |
P |
W |
V |
S |
P |
W |
V |
S |
P |
W |
| 150 | 5 | 4.0 |
|
|
2 |
2 |
0 |
0 |
|
|
|
| * | Gesamtarbeitsaufwand pro Modul
(1 ECTS-Punkt entspricht einem studentischen Arbeitsaufwand von 30 Zeitstunden) |
| ** | eine Semesterwochenstunde (SWS) entspricht 45 Minuten pro Woche |
| Selbststudienzeit in h |
Angabe gesamt |
davon |
| 105 |
90
Vor- und Nachbereitung LV |
15
Vorbereitung Prüfung |
0
Sonstiges |
|
Lehr- und Lernformen: | - Inverted classroom als didaktisches Grundkonzept mit Anpassungen aufgrund kleiner Gruppengrößen
- Mediendidaktische Unterstützung mit Jupyter Notebooks (https://github.com/wagenkn/AuK) zur Dokumentation selbstständig erarbeiteten Materials; vorbereitete Übungsaufgaben und komplexere Anwendungen
- Vortrag und kritische Diskussion, kommentierte Bearbeitung der Aufgaben
|
| Hinweise: | - Erfahrungen zur Umsetzung des Konzeptes "Inverted classroom"
wurden auch aus internationaler wissenschaftlicher Kooperation (USA, Dänemark, Deutschland) gewonnen.
- Das Testat wird bei gegebenem Lernfortschritt begleitend zu den Diskussionen vorbereiteter Materialien und deren Anwendung im entsprechenden Kontext erteilt.
- In der Prüfung geht es um die Reflexion algorithmischer Entwurfsmuster.
|
| Prüfung(en) |
| Prüfungsvorleistung | Prüfungsvorleistung als Teilnahme/Testat (VT) |
|
| Prüfung | mündliche Prüfungsleistung (PM) |
20 min |
100.0% |
|
| Lerninhalt: |
- Ressourcenproblem und Aufwandsmaße, Asymptotische Ordnungen, Effizienzbegriff,
- Teile und Herrsche, greedy-Strategie, Dynamische Programmierung, Memoizing,
- Systematisches Suchen, Verzweigen und Beschränken,
- Probabilistische Algorithmen, Neuronale Netze, Evolutionare Algorithmen
- Rucksackprobleme, Problem des Handlungsreisenden, Springerproblem, Erfüllbarkeitsproblem
- Lösungsmethoden für Rekursionsgleichungen, P-, NP- und NP-vollständige Probleme, Satz von Cook, P-NP-Problem
- Heuristiken zur näherungsweisen Lösung NP-vollständiger Probleme
|
| Lernergebnisse/Kompetenzen: |
| Fachkompetenzen: | Nach erfolgreichem Studium dieses Moduls kennen die Studierenden den Begriff der Effizienz von Algorithmen. Sie wissen, dass dafür das O-Kalkül geschaffen wurde, das sie in APIs, aus denen Sie Entscheidungen zur Wahl angemessener Datenstrukturen und Methoden treffen, wiederfinden. Die Studierenden sind nun in der Lage, den Zeitaufwand von Algorithmen funktional zu analysieren und theoretische Betrachtungen mit empirischen Untersuchungen abzugleichen.
Sie kennen wichtige Entwurfsmuster für Algorithmen und deren aufwandsmäßige Klassifikation. Die Studierenden haben mit dem Absolvieren dieses Moduls Entscheidungskompetenz zur Verwendung geeigneter Software-Werkzeuge (GTR, Computeralgebrasysteme, Programmiersprachen, Anwendungsprogramme) sowohl zur Implementation ausgewählter Algorithmen als auch in der empirischen Effizienzanalyse erworben. |
| Fachübergreifende Kompetenzen: | Am Ende dieses Moduls haben die Studierenden erkannt, dass es (neben absoluten) auch praktische (aufwandsmäßige) Grenzen algorithmischer Berechenbarkeit gibt. Sie erwarben Entscheidungskompetenz in der Auswahl und Anwendung geeigneter Software zur Durchführung empirischer Effizienzanalysen. Durch erfolgreiche Arbeit mit diesem Modul erwirbt der Studierende wichtige Metaqualifikationen, wie die Fähigkeit zur Anwendung mathematischer Analyse-Methoden und Ergebnisinterpretation. Durch freie Fachvorträge konnten die Studierenden Beiträge zu ihrer sprachlichen Kompetenz leisten. |
|
| Notwendige Voraussetzungen für die Teilnahme: | Mathematische Grundkenntnisse vor allem über Funktionen |
