Main Page: Difference between revisions

From Alda
Jump to navigationJump to search
Line 160: Line 160:
#* Wert- und Referenzsemantik
#* Wert- und Referenzsemantik
<!-------------------->
<!-------------------->
# [[Media:Übung-2.pdf|Übung]] (Abgabe 24.4.2008)
# [[Media:Übung-2.pdf|Übung]] (Abgabe 24.4.2008) sowie Musterlösungen für [[Media:muster_blatt2-aufgabe1.pdf|Aufgabe 1]] und [[Media:muster_blatt2-aufgabe2.pdf|Aufgabe 2]]
#* Sortieren: Implementation und Geschwindigkeitsvergleich (Diagramme in Abhängigkeit von Problemgröße)
#* Sortieren: Implementation und Geschwindigkeitsvergleich (Diagramme in Abhängigkeit von Problemgröße)
#* Entwicklung eines effizienten Algorithmus: Bruchfestigkeit von Gläsern
#* Entwicklung eines effizienten Algorithmus: Bruchfestigkeit von Gläsern

Revision as of 20:48, 30 April 2008

Getting started

Vorlesung Algorithmen und Datenstrukturen

Dr. Ullrich Köthe, Universität Heidelberg, Sommersemester 2008

Die Vorlesung findet mittwochs um 11:15 Uhr in INF 227, HS 2 und donnerstags um 11:15 Uhr in INF 308, HS 2 statt. Der Termin der Abschlussklausur wird noch bekannt gegeben. (Hinweis: Sie benötigen einen Lichtbildausweis, um sich bei der Klausur zu indentifizieren!)

Leistungsnachweise

  • Für alle Leistungsnachweise sind die erfolgreiche Teilnahme an den Übungen und das Bestehen der schriftlichen Prüfung erforderlich.
  • Es kann ein benoteter Übungsschein oder
  • für Informatiker: ein Leistungsnachweis über 8 Leistungspunkte nach ECTS (European Credit Transfer System, vgl. Modulhandbuch B.Sc. Angewandte Informatik) oder
  • für Physiker: ein Leistungsnachweis über 7 Leistungspunkte nach ECTS (vgl. Modulhandbuch B.Sc. Physik) erworben werden.

Übungsbetrieb

  • Termine der Übungsgruppen:
  • Übungsaufgaben (Übungszettel mit Abgabetermin, Musterlösungen)
  • aktueller Punktestand (PDF, anonymisiert -- Immatrikulationsnummer 0 bedeutet, dass wir Ihre Nummer noch nicht haben, bitte nachreichen!)
  • Zur Klausur wird zugelassen, wer mindestens 60% der Übungspunkte erreicht. Außerdem muss jeder Teilnehmer eine Lösung (bzw. einen Teil davon) in der Übungsgruppe vorrechnen. Es gibt verschiedene Möglichkeiten, Zusatzpunkte zu erlangen (Bonusaufgaben, Anfertigung der Wiki-Seiten, gute Mitarbeit in den Übungen).

Literatur

  • R. Sedgewick: Algorithmen (empfohlen für den ersten Teil, bis einschließlich Graphenalgorithmen)
  • J. Kleinberg, E.Tardos: Algorithm Design (empfohlen für den zweiten Teil)
  • T. Cormen, C. Leiserson, R.Rivest: Algorithmen - eine Einführung (empfohlen zum Thema Komplexität)
  • Wikipedia und andere Internetseiten (sehr gute Seiten über viele Algorithmen und Datenstrukturen)

Gliederung der Vorlesung

(Übersicht als PDF mit Übungsthemen)

  1. Einführung (9.4.2008)
    • Definition von Algorithmen und Datenstrukturen, Geschichte
    • Fundamentale Algorithmen: create, assign, copy, swap, compare etc.
    • Fundamentale Datenstrukturen: Zahlen, Container, Handles
    • Python-Grundlagen
  2. Container (10.4.2008)
    • Anforderungen von Algorithmen an Container
    • Einteilung der Container
    • Grundlegende Container: Array, verkettete Liste, Stack und Queue
    • Sequenzen und Intervalle (Ranges)
  3. Sortieren (16. und 17.4.2008)
    • Spezifikation des Sortierproblems
    • Selection Sort und Insertion Sort
    • Merge Sort
    • Quick Sort und seine Varianten
    • Vergleich der Anzahl der benötigten Schritte
    • Laufzeitmessung in Python
  4. Korrektheit (23. - 30.4.2008)
    • Definition von Korrektheit, Algorithmen-Spezifikation
    • Korrektheitsbeweise versus Testen
    • Vor- und Nachbedingungen, Invarianten, Programming by contract
    • Testen, Execution paths, Unit Tests in Python
    • Ausnahmen (exceptions) und Ausnahmebehandlung in Python
  5. Effizienz (30.4. - 8.5.2008)
    • Laufzeit und Optimierung: Innere Schleife, Caches, locality of reference
    • Laufzeit versus Komplexität
    • Komplexitätsklassen
    • Bester, schlechtester, durchschnittlicher Fall
    • Amortisierte Komplexität
  6. Suchen (14. und 15.5.2008)
    • Lineare Suche
    • Binäre Suche in sortierten Arrays, Medianproblem
    • Suchbäume, balancierte Bäume
    • selbst-balancierende Bäume, Rotationen
    • Komplexität der Suche
  7. Prioritätswarteschlangen (21.5.2008)
    • Heap-Datenstruktur
    • Einfüge- und Löschoperationen
    • Heapsort
    • Komplexität des Heaps
  8. Dictionaries (28.5.2008)
    • Implementation mit Bäumen
    • Hashing
    • Implementation als Hashtabelle
  9. Iteration versus Rekursion (29.5.2008)
    • Typen der Rekursion und ihre Umwandlung in Iteration
    • Iteratoren
  10. Generizität (4. und 5.6.2008)
    • Abstrakte Datentypen, Typspezifikation
    • Required Interface versus Offered Interface
    • Adapter und Typattribute, Funktoren
    • Beispiel: Algebraische Konzepte und Zahlendatentypen
    • Operator overloading in Python
  11. Graphen und Graphenalgorithmen (11. bis 19.6.2008)
    • Einführung
    • Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen
    • Gerichtete und ungerichtete Graphen
    • Vollständiger Graph
    • Pfade, Zyklen
    • Tiefensuche und Breitensuche
    • Zusammenhang, mehrfacher Zusammenhang, Komponenten
    • Gewichtete Graphen
    • Minimaler Spannbaum
    • Kürzeste Wege, Best-first search (Dijkstra)
    • Most-Promising-first search (A*)
  12. Prinzipien des Algorithmenentwurfs (25.6.2008)
    • Repetition
    • Orthogonale Zerlegung des Problems
    • Hierarchische Zerlegung der Daten (Divide and Conquer)
    • Randomisierung
    • Optimierung, Zielfunktionen
    • Systematisierung von Algorithmen aus der bisherigen Vorlesung
  13. Analytische Optimierung (25.6.2008)
    • Methode der kleinsten Quadrate
    • Approximation von Geraden
  14. Randomisierte Algorithmen (26.6. und 2.7.2008)
    • Zufallszahlen, Zyklenlänge, Pitfalls
    • Zufallsverteilungen, Box-Muller Transformation
    • Randomisierte vs. deterministische Algorithmen
    • Las Vegas vs. Monte Carlo Algorithmen
    • Beispiel für Las Vegas: Randomisiertes Quicksort
    • Beispiele für Monte Carlo: randomisierte Integration, randomisierter Primzahltest
    • RANSAC-Algorithmus, Erfolgswahrscheinlichkeit
  15. Greedy-Algorithmen (3.7.2008)
    • Prinzip
    • Bedingung für Optimalität
    • Beispiele für Greedy-Algorithmen
  16. Dynamische Programmierung (9.7.2008)
    • Prinzip
    • Beispiele für Dynamische Programmierung
  17. Erschöpfende Suche (10. und 16.7.2008)
    • Beispiele: u.a. Problem des Handlungsreisenden
    • Exponentielle Komplexität, NP-Vollständigkeit
    • Approximation bei NP-vollständigen Problemen
  18. Quantum computing (17.7.2008)

Übungsaufgaben

(im PDF Format). Die Abgabe erfolgt am angegebenen Tag bis 11:00 Uhr per Email an den jeweiligen Übungsgruppenleiter. Bei Abgabe bis zum folgenden Montag 11:00 Uhr werden noch 50% der erreichten Punkte angerechnet. Danach wird die Musterlösung freigeschaltet.

  1. Übung (Abgabe 17.4.2008) und Musterlösung
    • Python-Tutorial
    • Sieb des Eratosthenes
    • Wert- und Referenzsemantik
  2. Übung (Abgabe 24.4.2008) sowie Musterlösungen für Aufgabe 1 und Aufgabe 2
    • Sortieren: Implementation und Geschwindigkeitsvergleich (Diagramme in Abhängigkeit von Problemgröße)
    • Entwicklung eines effizienten Algorithmus: Bruchfestigkeit von Gläsern
  3. Übung (neuer Abgabetermin 7.5.2008)
    • Experimente zur Effektivität von Unit Tests
    • Deque-Datenstruktur: Vor- und Nachbedingungen der Operationen, Implementation und Unit Tests
  4. Übung (Abgabe 15.5.2008)
    • Theoretische Aufgaben zur Komplexität
    • Amortisierte Komplexität von array.append()
    • Optimierung der Matrizenmultiplikation
  5. Übung (Abgabe 23.5.2008)
    • Implementation und Analyse eines Binärbaumes
    • Anwendung: einfacher Taschenrechner
  6. Übung (Abgabe 29.5.2008)
    • Treap-Datenstruktur: Verbindung von Suchbaum und Heap
    • Anwendung: Worthäufigkeiten
    • Suche mit linearer Komplexität
  7. Übung (Abgabe 5.6.2008)
    • Übungen zu Rekursion und Iteration: Fakultät, Koch-Schneeflocke, Auflösung rekursiver Formeln, Umwandlung von Rekursion in Iteration
  8. Übung (Abgabe 12.6.2008)
    • Übungen zur Generizität: Sortieren mit veränderter Ordnung, Adapterklassen, Benutzer-definierte Zahlentypen
  9. Übung (Abgabe 19.6.2008)
    • Elementare Graphenaufgaben (Adjazenzlisten aufschreiben, Beweis e <= 3n-6 für planare Graphen, Zyklen eines vollständigen Graphen)
    • Implementation einer Graphklasse
    • Iteratoren für Tiefensuche und Breitensuche
  10. Übung (Abgabe 26.6.2008)
    • Anwendung: Weg aus einem Labyrinth
    • Anwendung: Erzeugen einer perfekten Hashfunktion
  11. Übung (Abgabe 3.7.2008)
    • Anwendung: Routenplaner
    • Beispiele für Divide and Conquer: pow-Funktion
    • Beispiel für Methode der kleinsten Quadrate: Approximation von Kreisen
  12. Übung (Abgabe 10.7.2008)
    • Naiver (deterministischer) und randomisierter Primzahltest, Laufzeitvergleich
    • RANSAC für Kreise
  13. Übung (Abgabe 17.7.2008)
    • Theoretische und praktische Aufgaben zur dynamische Programmierung
Retrieved from "https://alda.iwr.uni-heidelberg.de/index.php?title=Main_Page&oldid=419"