Navigation

Algorithmen und Datenstrukturen

Lecturers

Details

Time and place:

  • Tue 08:15-09:45, Room H11
  • Thu 16:15-17:45, Room H11

Fields of study

  • PF CE-BA-G from SEM 1
  • PF INF-BA from SEM 1
  • PF INF-LAG from SEM 1
  • PF INF-LAG-M from SEM 1
  • PF INF-LAG-P from SEM 1
  • PF INF-LAG-E from SEM 1
  • PF INF-LAG-W from SEM 1
  • PF INF-LAR from SEM 1
  • PF INF-LAR-M from SEM 1
  • PF INF-LAR-P from SEM 1
  • PF INF-LAR-E from SEM 1
  • PF INF-LAR-W from SEM 1
  • PF INF-LAH from SEM 1
  • PF I2F-BA from SEM 1
  • PF IuK-BA from SEM 1
  • WF M-BA from SEM 1
  • WPF TM-BA from SEM 1
  • PF BPT-BA-Inf from SEM 1

Content

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 information

Title

Algorithms and Data Structures

Credits

5

Additional information

Expected participants: 470

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