Main Page: Difference between revisions
From Alda
Jump to navigationJump to search
| Line 180: | Line 180: | ||
#* Anwendung: einfacher Taschenrechner | #* Anwendung: einfacher Taschenrechner | ||
<!--------------------> | <!--------------------> | ||
# [[Media:Übung-6.pdf|Übung]] (Abgabe 5.6.2008) | # [[Media:Übung-6.pdf|Übung]] (Abgabe 5.6.2008) und [[Media:muster_blatt6.pdf|Musterlösung]] | ||
#* Treap-Datenstruktur: Verbindung von Suchbaum und Heap | #* Treap-Datenstruktur: Verbindung von Suchbaum und Heap | ||
#* Anwendung: Worthäufigkeiten (Dazu benötigen Sie das File [http://klimt.iwr.uni-heidelberg.de/mip/people/ukoethe/download/die-drei-musketiere.txt die-drei-musketiere.txt]. Die Zeichenkodierung in diesem File ist Latin-1.) | #* Anwendung: Worthäufigkeiten (Dazu benötigen Sie das File [http://klimt.iwr.uni-heidelberg.de/mip/people/ukoethe/download/die-drei-musketiere.txt die-drei-musketiere.txt]. Die Zeichenkodierung in diesem File ist Latin-1.) | ||
Revision as of 16:36, 10 June 2008
Getting started
- Wiki Editierhilfe (Wiki-Syntax usw.)
- MediaWiki Manual (für Administratoren)
- Sandbox (zum ungefährlichen Ausprobieren von Änderungen)
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 ist die erfolgreiche Teilnahme an den Übungen erforderlich. Für Leistungspunkte bzw. den Klausurschein muss außerdem die schriftliche Prüfung bestanden werden. Im einzelnen können erworben werden:
- ein benoteter Übungsschein (Magister mit Computerlinguistik im Nebenfach, Physik Diplom)
- ein Klausurschein (Magister mit Computerlinguistik im Hauptfach)
- ein Leistungsnachweis über 9 Leistungspunkte (B.A. Computerlinguistik - alte Studienordnung)
- ein Leistungsnachweis über 8 Leistungspunkte (B.Sc. Informatik, B.A. Computerlinguistik - neue Studienordnung)
- ein Leistungsnachweis über 7 Leistungspunkte (B.Sc. Physik).
Übungsbetrieb
- Termine der Übungsgruppen:
- Mo 11:00 - 13:00 Uhr, INF 350 (Otto-Meyerhof-Zentrum, Seiteneingang), Raum 014 (Tutor: Rahul Nair, rnair (at) gmx (punkt) de)
- Di 11:00 - 13:00 Uhr, INF 350 (Otto-Meyerhof-Zentrum, Seiteneingang), Raum 014 (Tutor: Thomas Gerlach, gerlach@kip.uni-heidelberg.de)
- Mi 14:00 - 16:00 Uhr, neu: INF 327, Raum SR 5 (Tutor: Christoph Sommer, christoph.sommer@iwr.uni-heidelberg.de)
- Do 14:00 - 16:00 Uhr, INF 294, Raum -113 (im Untergeschoss, Tutor: Daniel Kondermann, daniel.kondermann@iwr.uni-heidelberg.de)
- Ü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)
- 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
- Container (10.4.2008)
- Anforderungen von Algorithmen an Container
- Einteilung der Container
- Grundlegende Container: Array, verkettete Liste, Stack und Queue
- Sequenzen und Intervalle (Ranges)
- 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
- 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
- Effizienz (30.4. - 14.5.2008)
- Laufzeit und Optimierung: Innere Schleife, Caches, locality of reference
- Laufzeit versus Komplexität
- Landausymbole (O-Notation, <math>\Omega</math>-Notation, <math>\Theta</math>-Notation), Komplexitätsklassen
- Bester, schlechtester, durchschnittlicher Fall
- Amortisierte Komplexität
- Suchen (14. - 21.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
- Prioritätswarteschlangen (28.5.2008)
- Heap-Datenstruktur
- Einfüge- und Löschoperationen
- Heapsort
- Komplexität des Heaps
- Hashing und assoziative Arrays (29.5.und 4.6.2008)
- Implementation assoziativer Arrays mit Bäumen
- Hashing und Hashfunktionen
- Implementation assoziativer Arrays als Hashtabelle mit linearer Verkettung bzw. mit offener Adressierung
- Anwendung des Hashing zur String-Suche: Rabin-Karp-Algorithmus
- Iteration versus Rekursion (5.6.2008)
- Typen der Rekursion und ihre Umwandlung in Iteration
- Auflösung rekursiver Formeln mittels Master-Methode und Substitutionsmethode
- Generizität (11.6.2008)
- Abstrakte Datentypen, Typspezifikation
- Required Interface versus Offered Interface
- Adapter und Typattribute, Funktoren
- Beispiel: Algebraische Konzepte und Zahlendatentypen
- Operator overloading in Python
- Graphen und Graphenalgorithmen (12. 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*)
- 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
- Analytische Optimierung (25.6.2008)
- Methode der kleinsten Quadrate
- Approximation von Geraden
- 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
- Greedy-Algorithmen (3.7.2008)
- Prinzip
- Bedingung für Optimalität
- Beispiele für Greedy-Algorithmen
- Dynamische Programmierung (9.7.2008)
- Prinzip
- Beispiele für Dynamische Programmierung
- 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
- 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.
- Übung (Abgabe 17.4.2008) und Musterlösung
- Python-Tutorial
- Sieb des Eratosthenes
- Wert- und Referenzsemantik
- Ü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
- Übung (neuer Abgabetermin 7.5.2008) und Musterlösung
- Experimente zur Effektivität von Unit Tests
- Deque-Datenstruktur: Vor- und Nachbedingungen der Operationen, Implementation und Unit Tests
- Übung (Abgabe 15.5.2008) und Musterlösung
- Theoretische Aufgaben zur Komplexität
- Amortisierte Komplexität von array.append()
- Optimierung der Matrizenmultiplikation
- Übung (neuer Abgabetermin 29.5.2008) und Musterlösung
- Implementation und Analyse eines Binärbaumes
- Anwendung: einfacher Taschenrechner
- Übung (Abgabe 5.6.2008) und Musterlösung
- Treap-Datenstruktur: Verbindung von Suchbaum und Heap
- Anwendung: Worthäufigkeiten (Dazu benötigen Sie das File die-drei-musketiere.txt. Die Zeichenkodierung in diesem File ist Latin-1.)
- Suche mit linearer Komplexität
- Übung (Abgabe 12.6.2008)
- Übungen zu Rekursion und Iteration: Fakultät, Koch-Schneeflocke, Komplexität rekursiver Algorithmen, Umwandlung von Rekursion in Iteration
- Übung (Abgabe 19.6.2008)
- Übungen zur Generizität: Sortieren mit veränderter Ordnung, Adapterklassen, Benutzer-definierte Zahlentypen
- Übung (Abgabe 26.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
- Übung (Abgabe 3.7.2008)
- Anwendung: Weg aus einem Labyrinth
- Anwendung: Erzeugen einer perfekten Hashfunktion
