 |
| Detailinformationen |
| Quellcurriculum |
Bachelorstudium Elektronik und Informationstechnik 2020W |
| Ziele |
Algorithmen sind das formale Grundgerüst für die Software-Entwicklung. Sie sind das Bindeglied zwischen der Theoretischen Informatik und der eigentlichen Programmierung.
In dieser Lehrveranstaltung werden die wesentlichen Eigenschaften von Algorithmen untersucht und wichtige Klassen von Algorithmen in Bezug auf ihre praktische Anwendung vorgestellt.
|
| Lehrinhalte |
- Der Algorithmusbegriff: Definition, Abgrenzung zwischen Algorithmen und Programmen, Darstellungsarten, Abstraktionsschichten und Bestandteile von Algorithmen
- Spezifikation: Zweck, Schnittstellenbeschreibung, Aufgabenbeschreibung, Darstellungsarten
- Schrittweise Verfeinerung: "Divide & Conquer", systematisches Lösen großer Probleme, Beispiele
- Algorithmen mit Gedächtnis: Begriff, Implementierungsvarianten
- Komplexität: Begriff, Laufzeitanalyse, Laufzeitmessung, Asymptotische Komplexität, Minimale Komplexität von Problemen
- Dynamische Datenstrukturen: Klassen als Referenztypen, Lineare Listen, Unsortierte Listen, Sortierte Listen, Ringlisten, Doppelt verkettete Listen, Stacks, Queues, Mengen
- Rekursion: Begriff, Klassifizierung, Terminierung, Anwendungen, Umwandlung rekursiver Algorithmen in iterative und umgekehrt
- Sortieren: Auswahlverfahren, Einfügeverfahren, Shellsort, Quicksort, internes und externes Mischsortieren, Sortieren von Listen, Heapsort, Topologisches Sortieren, Komplexität von Sortierverfahren
- Bäume: Begriffe, Binäre Suchbäume, Balancierte Bäume, Topdown-234-Bäume, Rot-Schwarz-Bäume, B-Bäume
- Graphen: Begriffe, Depth-First-Search, Breadth-First-Search, Kleinster spannender Baum, Kürzester Pfad, Transitive Hülle, Serialisierung von Graphen
- Exhaustion: Das n-Damen-Problem, Schema zum Suchen einer Lösung, Exhaustionsvariante, Optimierungsvariante, Darstellung von Lösungsvektoren, Näherungsverfahren, Nichtdeterministische Algorithmen
- Klassifikation von Algorithmen
|
| Beurteilungskriterien |
Vorlesungsklausur am Ende des Semesters
|
| Lehrmethoden |
Die Behandlung der Algorithmen erfolgt großteils in Pseudocode. Dies erlaubt die Betrachtung von Algorithmen losgelöst von einer konkreten Programmiersprache.
Manche Lehrinhalte werden durch Vorführungen (Demo-Videos) veranschaulicht. Manche Algorithmen werden auch an der Tafel/am Whiteboard gemeinsam konstruiert.
|
| Abhaltungssprache |
Deutsch |
| Literatur |
- Aho A.V., Hopcroft J.E., Ullman J.D.: Data Structures and Algorithms. Addison-Wesley 1983.
- Goodrich, M. T., Tamassia, R., and Goldwasser, M. H.: Data structures and algorithms in Java. John Wiley & Sons. 2014.
- Knuth D.E.: The Art of Computer Programming. Addison-Wesley 1973.
Band 1: Fundamental Algorithms.
Band 2: Seminumerical Algorithms.
Band 3: Sorting and Searching.
- Pomberger G., Dobler H.: Algorithmen und Datenstrukturen. Pearson 2008.
- Saake G., Sattler K.: Algorithmen und Datenstrukturen. dpunkt 2006.
- Sedgewick R.: Algorithmen in Java. Pearson 2014.
- Wirth N.: Algorithmen und Datenstrukturen. Teubner Studienbücher Informatik 1986.
|
| Lehrinhalte wechselnd? |
Nein |
| Sonstige Informationen |
Die Vorlesung wird foliengestützt abgehalten. Die Folien und ergänzende Unterlagen werden zum Download im PDF-Format bereitgestellt.
|
| Äquivalenzen |
MEBPFVOPIN1: VL Praktische Informatik 1 (3 ECTS)
|
|
