Navigation

Algorithmen und Datenstrukturen

Dozent/in

Details

Zeit/Ort n.V.:

  • Di 8:15-9:45, Raum H7
  • Di 8:15-9:45, Raum H8
  • Mi 14:15-15:45, Raum H7
  • Mi 14:15-15:45, Raum H8

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
  • PF WINF-BA ab Sem. 1
  • WPF IIS-MA 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: https://www.studon.fau.de/crs2281471.html

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
- 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: 638

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