Main Page: Difference between revisions
From Alda
Jump to navigationJump to search
No edit summary |
No edit summary |
||
| Line 4: | Line 4: | ||
# [[Einführung]] (9.4.2008) | # [[Einführung]] (9.4.2008) | ||
#* Organisatorisches: Übungsbetrieb, Scheinbedingungen, Gliederung der Vorlesung | #* Organisatorisches: Übungsbetrieb, Scheinbedingungen, Klausurtermin, Gliederung der Vorlesung | ||
#* Definition von Algorithmen und Datenstrukturen, Geschichte | #* Definition von Algorithmen und Datenstrukturen, Geschichte | ||
#* Fundamentale Algorithmen: create, assign, copy, compare etc. | #* Fundamentale Algorithmen: create, assign, copy, compare etc. | ||
| Line 13: | Line 13: | ||
#* Einteilung der Container | #* Einteilung der Container | ||
#* Grundlegende Container: Array, verkettete Liste, Stack und Queue | #* Grundlegende Container: Array, verkettete Liste, Stack und Queue | ||
#* Ranges in Containern | |||
<!-------------> | <!-------------> | ||
# [[Sortieren | # [[Sortieren]] (16. und 17.4.2008) | ||
#* Spezifikation des Sortierproblems | #* Spezifikation des Sortierproblems | ||
#* Selection Sort | #* Selection Sort | ||
#* Merge Sort | #* Merge Sort | ||
#* Quick Sort und seine Varianten | |||
#* Vergleich der Anzahl der benötigten Schritte | #* Vergleich der Anzahl der benötigten Schritte | ||
#* Laufzeitmessung in Python | #* Laufzeitmessung in Python | ||
<!-------------> | <!-------------> | ||
# [[ | # [[Korrektheit]] (23. und 24.4.2008) | ||
#* | #* Definition von Korrektheit, Algorithmen-Spezifikation | ||
#* | #* Korrektheitsbeweise versus Testen | ||
#* Programming by contract, Vor- und Nachbedingungen, Invarianten | |||
#* Testen, Execution paths, Unit Tests in Python | |||
#* Ausnahmen (exceptions) und Ausnahmebehandlung in Python | |||
<!-------------> | |||
# [[Effizienz]] (24. und 30.4.2008) | |||
#* Laufzeit und Optimierung: Innere Schleife, Caches, locality of reference | |||
#* Laufzeit versus Komplexität | |||
#* Komplexitätsklassen | |||
#* Bester, schlechtester, durchschnittlicher Fall | |||
#* Amortisierte Komplexität | |||
<!-------------> | |||
# [[Suchen]] (7. und 8.5.2008) | |||
#* Binäre Suche in sortierten Arrays | |||
#* Suchbäume | |||
#* balancierte Bäume | |||
#* selbst-balancierende Bäume, Rotationen | |||
#* Komplexität der Suche | |||
# [[Prioritätswarteschlangen]] (14.5.2008) | |||
#* Heap-Datenstruktur | |||
#* Einfüge- und Löschoperationen | |||
#* Heapsort | |||
#* Komplexität des Heaps | |||
# [[Dictionaries]] (15.5.2008) | |||
Mengen | |||
Hashing | |||
Dictionaries als Baum und als Hashtabelle | |||
Iteration vs. Rekursion | |||
Typen der Rekursion und ihre Umwandlung in Iteration | |||
Iteratoren | |||
Übungen zu Rekursion und Iteration: Fakultät, Koch-Schneeflocke, Auflösung rekursiver Formeln, Umwandlung von Rekursion in Iteration | |||
Fronleichnam | |||
Abstrakte Datentypen | |||
Generizität: Required Interface, Adapter und Typattribute | |||
Funktoren (Beispiel: Ordnung für Sortieren) | |||
Übungen zur Generizität: Sortieren mit veränderter Ordnung, Adapterklassen | |||
Zahlendatentypen und Arithmetik, Byteorder, IEEE floating point | |||
Algebraische Konzepte | |||
Operator Overloading, Anwender-definierte Zahlentypen (z.B mit physikalischen Einheiten) | |||
== Getting started == | == Getting started == | ||
Revision as of 15:45, 5 April 2008
Vorlesung Algorithmen und Datenstrukturen SS 08
Vorläufiger Inhalt der Vorlesungen und Übungen
- Einführung (9.4.2008)
- Organisatorisches: Übungsbetrieb, Scheinbedingungen, Klausurtermin, Gliederung der Vorlesung
- Definition von Algorithmen und Datenstrukturen, Geschichte
- Fundamentale Algorithmen: create, assign, copy, compare etc.
- Fundamentale Datenstrukturen: Zahlen, Container, Handles
- Container (10.4.2008)
- Anforderungen von Algorithmen an Container
- Einteilung der Container
- Grundlegende Container: Array, verkettete Liste, Stack und Queue
- Ranges in Containern
- Sortieren (16. und 17.4.2008)
- Spezifikation des Sortierproblems
- Selection Sort
- Merge Sort
- Quick Sort und seine Varianten
- Vergleich der Anzahl der benötigten Schritte
- Laufzeitmessung in Python
- Korrektheit (23. und 24.4.2008)
- Definition von Korrektheit, Algorithmen-Spezifikation
- Korrektheitsbeweise versus Testen
- Programming by contract, Vor- und Nachbedingungen, Invarianten
- Testen, Execution paths, Unit Tests in Python
- Ausnahmen (exceptions) und Ausnahmebehandlung in Python
- Effizienz (24. und 30.4.2008)
- Laufzeit und Optimierung: Innere Schleife, Caches, locality of reference
- Laufzeit versus Komplexität
- Komplexitätsklassen
- Bester, schlechtester, durchschnittlicher Fall
- Amortisierte Komplexität
- Suchen (7. und 8.5.2008)
- Binäre Suche in sortierten Arrays
- Suchbäume
- balancierte Bäume
- selbst-balancierende Bäume, Rotationen
- Komplexität der Suche
- Prioritätswarteschlangen (14.5.2008)
- Heap-Datenstruktur
- Einfüge- und Löschoperationen
- Heapsort
- Komplexität des Heaps
- Dictionaries (15.5.2008)
Mengen Hashing Dictionaries als Baum und als Hashtabelle Iteration vs. Rekursion Typen der Rekursion und ihre Umwandlung in Iteration Iteratoren Übungen zu Rekursion und Iteration: Fakultät, Koch-Schneeflocke, Auflösung rekursiver Formeln, Umwandlung von Rekursion in Iteration Fronleichnam Abstrakte Datentypen Generizität: Required Interface, Adapter und Typattribute Funktoren (Beispiel: Ordnung für Sortieren) Übungen zur Generizität: Sortieren mit veränderter Ordnung, Adapterklassen Zahlendatentypen und Arithmetik, Byteorder, IEEE floating point Algebraische Konzepte Operator Overloading, Anwender-definierte Zahlentypen (z.B mit physikalischen Einheiten)
Getting started
- Wiki Hilfe (für alle, die Seiten ändern wollen)
- MediaWiki Manual (für Administratoren)
- Sandbox (zum ungefährlichen Ausprobieren von Änderungen)
