Navigation

Algorithmen und Datenstrukturen

Dozent/in

Details

Zeit/Ort n.V.:

  • Di 16:15-17:45, Raum H11
  • Do 8:15-9:45, Raum H11

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
  • 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: 420

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