Algorithmen und Datenstrukturen (AuD)

Algorithmen und Datenstrukturen

Dozent/in

• Prof. Dr.-Ing. Marc Stamminger

Details

Zeit/Ort n.V.:

• Di 8:15-9:45
• Do 16:15-17:45

Studienfächer / Studienrichtungen

• PF CE-BA-G ab Sem. 1
• PF INF-BA ab Sem. 1
• PF INF-LAG ab Sem. 1
• PF INF-LAG-M ab Sem. 1
• PF INF-LAG-P ab Sem. 1
• PF INF-LAG-E ab Sem. 1
• PF INF-LAG-W ab Sem. 1
• PF INF-LAR ab Sem. 1
• PF INF-LAR-M ab Sem. 1
• PF INF-LAR-P ab Sem. 1
• PF INF-LAR-E ab Sem. 1
• PF INF-LAR-W ab Sem. 1
• PF INF-LAH ab Sem. 1
• PF I2F-BA ab Sem. 1
• PF IuK-BA ab Sem. 1
• WF M-BA ab Sem. 1
• WPF TM-BA ab Sem. 1
• WPF DS-BA ab Sem. 1
• PF BPT-BA-Inf ab Sem. 1

Inhalt

Die Materialien zur Lehrveranstaltung werden über StudOn bereitgestellt.

Bitte beachten Sie unbedingt die wichtigen Hinweise unter: https://www.studon.fau.de/crs2226036.html

Themen der Vorlesung:

1. Algorithmisches Denken

• Einordnung der LV "Algorithmen und Datenstrukturen"

• Was ist Informatik?

• Algorithmisches Denken

2. Grundlagen der Programmierung (Teil 1): Variablen, Datentypen, Operatoren, Ausdrücke

• Grundbegriffe

• Variablen

• Datentypen

• Operatoren und Ausdrücke

• Typumwandlung und Typsicherheit

3. Grundlagen der Programmierung (Teil 2): Ablaufstrukturen, Methoden

• Ablaufstrukturen

• Methoden

4. Rekursion

• Grundbegriffe

• Lineare Rekursion und Endrekursion

• Kaskadenartige Rekursion

• Verschränkte und verschachtelte Rekursion

5. Rekursion im Einsatz

• Teil 1: Beispiele zur Algorithmenherleitung

• > Gebiete in der Ebene

• > Färben von Gebieten

• > Gray-Codes

• > Polynomauswertung, Horner-Schema

• > Maximale Summe zusammenhängender Teilfolge

• > Prominentenproblem

• > Skyline-Problem, Teile-und-Herrsche

• Teil 2: Von Aufrufbäumen und Suchräumen

• > Problembewusstsein

• > Durchreichen von Zwischenergebnissen

• > Dynamisches Programmieren und Memoization

• > Rücksetzverfahren (engl. „backtracking")

• > Gierige Algorithmen

6. Asymptotische Aufwandsanalyse

• Idee

• O-Kalkül

7. Objektorientierte Modellierung und Programmierung (Teil 1): Klassen und Objekte

• Objektorientiertes Denken

• Klassen: Attribute, Methoden, Konstruktoren

• Objekte: Instanziierung, Objektvariablen

• Klassen: Klassenattribute, Klassenmethoden, Sichtbarkeitsmodifikatoren

• Klassendarstellung im UML-Diagramm

8. Objektorientierte Modellierung und Programmierung (Teil 2): Klassenbeziehungen, Polymorphie, Module

• Vorgehensweisen

• Assoziationen, Aggregationen, Kompositionen

• Vererbung

• Polymorphie

• Schnittstellen

• Pakete, Klassenbibliotheken

9. Robustes Programmieren

• Fehlerquellen

• Fehlerbehandlung

• Testen von Programmen

• Zusicherungen

• Formale Verifikation mittels wp-Kalkül

10. Grundlegende Datentypen

• Spezifikation von Datentypen

• Generische/Parametrisierte Klassen

• Elementare Listen

• Keller/Stapel (Stacks)

• (Warte-) Schlangen (Queues)

11. Verkettete Listen, dynamische Arrays, Mengen, Streutabellen

• Java Collection Framework

• Einfach verkettete Listen

• Dynamische Arrays

• Mengen

• Streutabellen (Hash-Tabellen)

12. Bäume

• Allgemeine (und Binäre) Bäume

• (Binäre) Suchbäume

• AVL-Bäume

• Halden

13. Sortieralgorithmen

• Grundbegriffe

• Einfache Sortierverfahren

• Verfeinertes Auswählen

• Teile-und-Herrsche/Divide-and-Conquer-Methoden

• Sortieren durch Fachverteilen

14. Graphen und Graphalgorithmen

• Grundbegriffe

• (Speicher-) Darstellungen von Graphen

• Graphdurchlauf

• Kürzeste Wege in Graphen

• Minimaler Spannbaum

15. Geometrische Algorithmen

• Vorbemerkungen

• Punkt-in-Polygon-Problem

• Konstruktion von Polygonen

• Konvexe Hülle

• Ballung und nächstes Paar

ECTS-Informationen

Titel

Algorithms and Data Structures

Credits

5

Zusätzliche Informationen

Erwartete Teilnehmerzahl: 470

www: https://www.studon.fau.de/crs3063592.html