Click here to exit full screen mode.
Sakai works much better when JavaScript is enabled. Please enable JavaScript in your Browser.
jump to content
[c]
Sites
[w]
Tools
[l]
Syllabus
Log In
Tools list begins here
Home
Klausursitzplan
Syllabus
Assignments
Section Info
Sign-up
Forums
Exam Registration
Help
Opens in a new window
Expand/collapse tool navigation
Algorithmen, Datenstr ...
Syllabus
Content begins here
Syllabus
Link
Direct link to this tool
Short URL
https://mycampus.imp.fu-berlin.de/portal/directtool/ce4e78bc-c8dc-4a0b-a4d9-4ed8f19effd5/
Help
Opens in a new window
Syllabus
Expand All
Collapse All
Print View
1. Vorlesung Dienstag
Tue Oct 17, 2023 02:15 PM - | 03:45 PM
Überblick: Qualifikationsziele
Organisatorisches: Vorlesung und Übung
Überblick über vergleichsbasierte Sortieralgorithmen (Wiederholung)
Sortieren durch Vergleichen (Bubblesort)
Sortieren durch Einfügen
Sortieren durch Auswahl
Quicksort
Sortieren durch Verschmelzen (mergesort)
Asymptotische Laufzeitanalyse,
O
-Notation (Wiederholung). Ω-Notation (untere Schranken), Θ-Notation
Teile und herrsche (divide-and-conquer)
2. Vorlesung Donnerstag
Thu Oct 19, 2023 02:15 PM - | 03:45 PM
Quicksort mit zufälliger Pivotauswahl
Verschiedene Analysen von Algorithmen
randomisierte Algorithmen, schlechtester Fall, Analyse für durchschnittliche Eingaben, in Abhängigkeit von der Eingabe
Topologisches Sortieren
Problemdefinition und Beispiel
Algorithmus und Charakterisierungssatz
3. Vorlesung Dienstag
Tue Oct 24, 2023 02:15 PM - | 03:45 PM
Topologisches Sortieren:
Implementierungen
Auswahl der Datenstrukturen; Laufzeit und Speicherplatz
Programm
TopoSort.java
Man benötigt für dieses Programm auch die Klasse
IntReader.java
zum Einlesen ganzer Zahlen
Das Gleiche in Python:
topoSort.py
und
intReader.py
Gerichtete Graphen mit Adjazenzlisten
4. Vorlesung Donnerstag
Thu Oct 26, 2023 02:15 PM - | 03:45 PM
Abstrakte Datentypen
Spezifikation abstrakter Datentypen
verbale Spezifikation
modellierende Spezifikation. Beispiel: Mengen
algebraische Spezifikation. Beispiel: Mengen
Beweis von Eigenschaften durch algebraische Manipulation
Referenzimplementierung direkt aus der Spezifikation in Haskell (
Menge.hs
)
Stückweise konstante Funktionen
Beispielprogramm in Python
StueckweiseKonstant_mit_Generator.py
5. Vorlesung Dienstag
Tue Oct 31, 2023 02:15 PM - | 03:45 PM
Stückweise konstante Funktionen (Fortsetzung)
Flexiblere Handhabung der Intervallgrenzen; erweiterte Zahlenordnung, Python-Klasse
Number_extended.py
Modellierende Spezifikation von abstrakten Datentypen: Vor- und Nachbedingungen, (V) und (N)
Beispiel: Menge durch eine Feld konstanter Länge implementiert:
SmallIntSet.java
Abstraktionsfunktion zur Übersetzung zwischen Implementierung und Spezifikation
Darstellungsinvarianten der Implementierung von Datenstrukturen (D)
Nebenbedingungen (Zusatzrestriktionen Z)
6. Vorlesung Donnerstag
Thu Nov 02, 2023 02:15 PM - | 03:45 PM
Darstellungsinvarianten der Implementierung von Datenstrukturen
Nebenbedingungen (Zusatzrestriktionen)
Korrektheit der Implementierung von abstrakten Datentypen
Beispiel: Implementierung der Menge durch ein Feld
Einsatz beim Korrektheitsbeweis auf höherer Ebene
Unterstützung für Datenabstraktion in verschiedenen Programmiersprachen
Wörterbuch als abstrakter Datentyp (
dictionary, Map
)
Wörterbuchoperationen: Einfügen, Suchen, Löschen
geordnetes Wörterbuch: Nachfolger finden, Intervallabfrage, geordnetes Durchlaufen
Unterscheide: OrderedDict in Python
Wiederholung: binäre Bäume und Suchbäume
Höhe und Tiefe
ausgeglichene und entartete Bäume
7. Vorlesung Dienstag
Tue Nov 07, 2023 02:15 PM - | 03:45 PM
Höhenbalancierte Bäume (AVL-Bäume)
Analyse der Höhe
Rotationen und Doppelrotationen
8. Vorlesung Donnerstag
Thu Nov 09, 2023 02:15 PM - | 03:45 PM
Höhenbalancierte Bäume
AVL-Bäume
Einfügen
Löschen
erweiterte Suchabfragen in Suchbäumen, bsp. Rang
(exkurs: Rot-Schwarz-Bäume)
Einstieg (a,b)-Bäume
9. Vorlesung Dienstag
Tue Nov 14, 2023 02:15 PM - | 03:45 PM
Wiederholung: AVL-Bäumen
(a,b)-Bäume
Einfügen
Löschen
Einstieg Skiplisten
10. Vorlesung Donnerstag
Thu Nov 16, 2023 02:15 PM - | 03:45 PM
Skiplisten
Einfügen
Löschen
Laufzeitanalyse
(nicht) vergleichsbasierte Wörterbücher
untere Schranke für vergleichsbasierte Sortieralgorithmen und Datenstrukturen
11. Vorlesung Dienstag
Tue Nov 21, 2023 02:15 PM - | 03:45 PM
untere Schranke für vergleichsbasierte Sortieralgorithmen und Datenstrukturen (Fortsetzung)
Digitale Suchbäume (
tries
) zum Speichern von Zeichenketten
komprimierte digitale Suchbäume
12. Vorlesung Donnerstag
Thu Nov 23, 2023 02:15 PM - | 03:45 PM
Suffixbäume, Aufbau und Anwendungen
Teilwortsuche
naiver Algorithmus
Definition der
Verschiebefunktion
Algorithmus von Knuth-Morris-Pratt (1977)
Berechnung der Verschiebefunktion
13. Vorlesung Dienstag
Tue Nov 28, 2023 02:15 PM - | 03:45 PM
Teilwortsuche
Hintergrund und Entstehung des Algorithmus (deterministische Zwei-Wege-Kellerautomaten)
Algorithmus von Boyer und Moore
Fingerabdrücke nach Rabin und Karp
Grundidee, Interpretation einer Zeichenkette als Zahl
Restklassenbildung
Auswahl des Moduls, Analyse
14. Vorlesung Donnerstag
Thu Nov 30, 2023 02:15 PM - | 03:45 PM
Nachtrag: Fingerabdrücke nach Rabin und Karp
Zufallsauswahl des Moduls, Analyse der Wahrscheinlichkeit eines Fehlalarms
Graphenalgorithmen
Wiederholung der Grundbegriffe
Speicherung von Graphen im Computer: Adjazenzmatrix und Adjazenzliste
Breitensuche
15. Vorlesung Dienstag
Tue Dec 05, 2023 02:15 PM - | 03:45 PM
Tiefensuche
kürzeste Wege, der Algorithmus von Dijkstra
Simulation von Breitensuche, der kürzeste-Wege-Baum
dfs_sssp.pdf
16. Vorlesung Donnerstag
Thu Dec 07, 2023 02:15 PM - | 03:45 PM
kürzeste Wege, der Algorithmus von Dijkstra
Korrektheit
Reduktion auf
O
(
n
2
) Laufzeit
Implementierung mit Prioritätswarteschlangen
rudmentäre Python-Klasse
Halde
mit den Operationen
einfügen
und
entferneMin
Prioritätswarteschlange als abstrakter Datentyp
Implementierung als Halde mit Zugriffshenkeln:
Halde.py
Algorithmus von Dijkstra unter Verwendung dieser Prioritätswarteschlange:
Dijkstra.py
17. Vorlesung Dienstag
Tue Dec 12, 2023 02:15 PM - | 03:45 PM
kürzeste Spannbäume
Baum als Graph vs Baum als Datenstruktur
Algorithmus von Kruskal
Korrektheit bei unterschiedlichen Kantengewichten
Korrektheit bei ggf. gleichen Kantengewichten
18. Vorlesung Donnerstag
Thu Dec 14, 2023 02:15 PM - | 03:45 PM
das UNION-FIND-Problem
Vereinigung nach Größe
erwähnt: die inverse Ackermannfunktion α(n) und Pfadverkürzung
der Algorithmus von Prim
der Algorithmus von Borůvka
mst.pdf
19. Vorlesung Dienstag
Tue Dec 19, 2023 02:15 PM - | 03:45 PM
Hash-Tabellen und gestreute Speicherung
Einführung Multiplikative Hashfunktion
Behandlung von Kollisionen: Verkettete Listen
Behandlung von Kollisionen: offene Adressierung, lineares Sondieren
Einführung Kuckuckshashing
20. Vorlesung Donnerstag
Thu Dec 21, 2023 02:15 PM - | 03:45 PM
Analyse von multiplikativem Hashing
alternative multiplikative Hashfunktionen mit Primzahlen
21. Vorlesung Dienstag
Tue Jan 09, 2024 02:15 PM - | 03:45 PM
kurze Wiederholung: Hashing
Wiederholung: Alternative multiplikative Hashfunktionen mit Primzahlen
erweiterter euklidischer Algorithmus
Hashcodes für längere Schlüssel
andere use cases von Hashfunktionen
Einstieg: Analyse von Kuckuckshashing
hashing.pdf
22. Vorlesung Donnerstag
Thu Jan 11, 2024 02:15 PM - | 03:45 PM
Analyse von Kuckuckshashing (Fortsetzung)
Backtracking
Systematisches Durchsuchen von Lösungsbäumen/Backtracking
Das Acht-Damen-Problem
Verbesserte Datenstrukturen
Python-Programm
8Damen.py
23. Vorlesung Dienstag
Tue Jan 16, 2024 02:15 PM - | 03:45 PM
Die Klasse
P
der in Polynomialzeit lösbaren Probleme
Algorithmische Probleme, Eingabe, Ausgabe
Rechnermodelle: RAM (Registermaschine), Turingmaschine
Polynomielle Reduzierbarkeit zwischen Problemen (Turing-Reduzierbarkeit):
A
<
P
B
Beispiel: Hamiltonkreis <
P
Rundreiseproblem
Das Erfüllbarkeitsproblem (Satisfiability, SAT)
Graphenfärbung als Optimierungsproblem
24. Vorlesung Donnerstag
Thu Jan 18, 2024 02:15 PM - | 03:45 PM
Graphenfärbung als Optimierungsproblem (COL-O) und die Entscheidungsvariante (Färbbarkeit, COL-D)
Reduktion: Färbbarkeit <
P
SAT
Entscheidungsprobleme, Karp-Reduktion
Die Klasse NP, Entscheidungsprobleme, Zertifikatskriterium
NP-schwere und NP-vollständige Probleme
Bedeutung der NP-Schwerheit
Satz von Cook/Levin: SAT ist NP-schwer
Beweis der NP-Schwerheit durch Reduktion
Beispiel einer Reduktion: SAT <
P
3-Färbbarkeit
Zusammenfassung: NP-Schwerheit, NP, Reduktion
25. Vorlesung Dienstag
Tue Jan 23, 2024 02:15 PM - | 03:45 PM
Amortisierte Analyse
Listen variabler Länge
Umbau von Hashtabellen
potential function method
Vorlesungsevaluation
amort.pdf
26. Vorlesung Donnerstag
Thu Jan 25, 2024 02:15 PM - | 03:45 PM
Laufzeit von Listenoperationen in Python
dynamische Speicherverwaltung, Stapel und Halde,
garbage collection
Mengen und Wörterbücher als abstrakte Datentypen in Java (die
Collection
- und
Map
-Klassen
)
Quellcode
, siehe zum Beispiel
TreeMap.java
Definition Optimale Suchbäume
dynspeicher.pdf
27. Vorlesung Dienstag
Tue Jan 30, 2024 02:15 PM - | 03:45 PM
Optimale Suchbäume
dynamische Programmierung
Implementierungen in Python:
optSuchbaum.py
Zurückverfolgen der Lösung (abspeichern oder neu berechnen)
Variante: unsystematisches Lösen der Teilprobleme und Tabellieren der Ergebnisse (Merken,
memoization
) zur Vermeidung von Mehrfachberechnungen
Radix-Sort
zum Sortieren von kurzen Daten
optsearchtree.pdf
radix.pdf
28. Vorlesung Donnerstag
Thu Feb 01, 2024 02:15 PM - | 03:45 PM
Editierabstand
Dynamische Programmierung und Wege in azyklischen Graphen
29. Vorlesung Dienstag
Tue Feb 06, 2024 02:15 PM - | 03:45 PM
Dynamische Programmierung für das Rundreiseproblem
heuristische Suche mit dem Algorithmus A*
Folien zur Veranschaulichung des Algorithmus
(von Prof. Mulzer)
DPTSP.pdf
astern.pdf
30. Vorlesung Donnerstag
Thu Feb 08, 2024 02:15 PM - | 03:45 PM
Übersicht über Algorithmenentwurfsprinzipien:
teile und herrsche
siehe Sortieren, dichtestes Punktpaar
dynamische Programmierung
siehe optimaler Suchbaum, Edit-Abstand, Rundreiseproblem
systematisches Durchsuchen von Lösungsbäumen (backtracking)
siehe Acht-Damen-Problem
gierige Algorithmen (greedy)
siehe kürzeste Spannbäume, Algorithmus von Kruskal
Näherungslösung, Approximationsalgorithmen
31. Vorlesung Dienstag
Tue Feb 13, 2024 02:15 PM - | 03:45 PM
lokale Optimierung, steilster Abstieg
Zielfunktion, Nachbarschaftsrelation
heuristische Suchverfahren (z. B.
Simulated annealing
, genetische Algorithmen, Tabusuche, Ameisenalgorithmen)
...
uebersicht.pdf
32. Vorlesung Donnerstag
Thu Feb 15, 2024 02:15 PM - | 03:45 PM
Optional: Algorithmus von Dantzig für kürzeste Wege mit negativen Kantengewichten
OPTIONAL: Optimale präfixfreie Kodes
der Algorithmus von Huffman
die Kraft-McMillan'sche Ungleichung (erwähnt)
(Ergänzung:
Beweis der Kraft-McMillan'schen Ungleichung für eindeutig entzifferbare Kodes
)
OPTIONAL: Analyse von Stellungsspielen
OPTIONAL: Zweipersonen-Nullsummenspiele mit vollständiger Information, Spielgraph
OPTIONAL: Min-Max-Algorithmus, optimale Spielstrategie
OPTIONAL Exkurs: Optimale Strategie für Tic-Tac-Toe
OPTIONAL: heuristische Bewertungsfunktion
OPTIONAL: α-β-Suche
OPTIONAL: Convex Hull
Fallstudie: längste aufsteigende Teilfolge
dynamische Programmierung,
O
(
n
²)
mit Bereichsabfragen,
O
(
n
log
n
)
Darstellung einer Funktion,
O
(
n
log
n
)
geometrische Algorithmen
konvexe Hülle
Orientierungstest
diskrete Ereignissimulation
randomisierte Auswahl des
k
-kleinsten Elements: Quickselect
spiele.pdf
Are you sure you want to delete
Title
Content
Click to add title
Start Date
End Date
Click to add start date
Click to add end date
Click to add body text
Saved
Deleted
An error occurred while saving. Refresh the page and try again.
This field is required.
Start date must be before end date.
Please select a start or end date before posting to the calendar.
Click to expand/collapse, change attachments or edit body content.
Delete
Cancel
Are you sure you want to delete
Delete Item
Delete Attachment
Add
Add and Publish
Add Item
DRAFT -
WARNING: this action cannot be undone.