|
|
|
|
Allgemeines
|
|
| Semester | WS 2005/06 |
| Zielgruppe | 1. BNC, 1. BWM, 1. Mm, 1. EC, 2. EC, 1. GIn |
| SWS | 2 / 1 / 0 |
| Credits (ECTS) | 
(5)
|
| Vorlesung | Oliver Ernst |
| Übung | Elisabeth Ullmann |
|
Inhalt/Contents |
|
|
Diese Vorlesung ist eine Einführung in zwei Kernbereiche der Informatik, den Algorithmen und Datenstrukturen. Nach einer Einführung zum Begriff des Algorithmus werden Techniken vorgestellt, mit denen Korrektheit und Laufzeiten von Algorithmen analysiert werden können. Neben Algorithmenanalyse werden ausführlich verschiedene Algorithmen zum Suchen und Sortieren besprochen. Im Bereich Algorithmenentwurf werden Greedy-Strategien und dynamisches Programmieren behandelt. Schliesslich werden neben den wichtigsten einfachen Datenstrukturen wie Stapel, Liste usw. einige fortgeschrittene Beispiele wie binäre Suchbäume und Hash-Tabellen behandelt.
Voraussetzungen: keine |
|
|
This course provides an introduction to algorithms and data structures, two fundamental areas of computer science. After an introductory discussion of the concept of an algorithm we introduce techniques for analyzing the correctness and running time of algorithms. In addition to analysis techniques, we provide an extensive discussion of various algorithms for sorting and searching. The algorithm design methodologies of greedy strategies and dynamic programming are also introduced. On the topic of data structures we cover the basic simple varieties such as stacks and lists as well as more advanced examples including binary search trees and hash tables.
Prerequisites: none |
|
|
Termine
|
|
| Vorlesungen | Dienstag, 11-13:00 Uhr, GEL-0001 |
| Übungen | Donnerstag, 16-18:00 Uhr, FOR-0095, gerade Wochen Freitag, 11-13:00 Uhr, FOR-0095, ungerade Wochen |
| Prüfungen | Klausur am Dienstag, 07.02.2006, 9:00-11:00 Uhr, WER-1045 (BWM und GIn) sowie WIN-1005 (BNC und EC) Hilfsmittel (Bücher, Skripte etc.) sind zugelassen.
Die Klausurergebnisse sind hier. |
| Sprechstunden |
O. Ernst: nach Vereinbarung (am besten per E-Mail nachfragen) E. Ullmann: Donnerstags 12:30-14:00 Uhr, Mittelbau Raum 2.12 |
|
Folien |
|
| Hinweis |
Um den Aufwand beim Mitschreiben zu reduzieren werden die in der Vorlesung eingesetzten Folien sukzessive an dieser Stelle herunterladbar zur Verfügung gestellt. Es sei allerdings ausdrücklich darauf hingewiesen, dass diese Foliensammlung nicht als Vorlesungsskript zum Erlernen des Stoffes geeignet ist, sondern dass hierzu die Teilnahme an den Lehrveranstaltungen und/oder Konsultieren der empfohlenen Literatur unabdingbar ist.
Die Folien sind im PDF-Format und von der Formattierung her am besten am Bildschirm zu lesen. Wer die Folien ausdrucken möchte, dem sei die Auswahl von 4 Folien pro Seite als Layout empfohlen (steht bei den meisten Druckertreibern zur Verfügung).
|
| Kapitel 0 | Titel, Organisatorisches (11.10.2005) |
| Kapitel 1 | Einleitung (18.10.2005) |
| Kapitel 2 | Wachstumsverhalten von Funktionen (18.10.2005) |
| Kapitel 3 | Rekursionen (25.10.2005) |
| Kapitel 4 | Probabilistische Analyse und randomisierte Algorithmen (08.11.2005) |
| Kapitel 5 | Heapsort (21.11.2005) |
| Kapitel 6 | Quicksort (29.11.2005) |
| Kapitel 7 | Sortieren in linearer Zeit (02.12.2005) |
| Kapitel 8 | Elementare Datenstrukturen (19.12.2005) |
| Kapitel 9 | Hash-Tabellen (17.01.2006) |
| Kapitel 10 | Binäre Suchbäume (31.01.2006) |
| Kapitel 11 | Dynamisches Programmieren (23.01.2006) |
| Kapitel 12 | Greedy-Algorithmen (23.01.2006) |
| Anhang A | Grundbegriffe der Wahrscheinlichkeitsrechnung (14.11.2005) |
| Anhang B | Graphen und Bäume (01.11.2005) |
|
Übungen |
| 1. Übungsblatt, Rahmen für Programmieraufgabe 1 |
| 2. Übungsblatt |
| 3. Übungsblatt |
| 4. Übungsblatt, Zufallsgenerator für Programmieraufgabe 4 |
| 5. Übungsblatt |
| 6. Übungsblatt, Rahmenprogramm Aufgabe 29 (PA 6) |
| 7. Übungsblatt |
| Die genauen Modalitäten zum Erwerb von Bonuspunkten für die Klausur durch Bearbeiten von Programmieraufgaben stehen hier. Den aktuellen Stand der Bonuspunkte finden Sie hier. |
| Probeklausur, wird in der Übung der letzten Vorlesungswoche vorgerechnet. Lösungshinweise. Klausuren aus Vorjahren zur weiteren Übung: 2004, 2005. |
|
Links |
|
| Literatur |
Die Vorlesung folgt dem Buch
Introduction to Algorithms
von Cormen, Leiserson, Rivest und Stein (2. Auflage, MIT Press, 2001) Weitere Literaturhinweise hier. |
| Programmierhilfen | Nützliches für den Einstieg in die Programmiersprache C bieten folgende Webseiten an der Uni Leicester und der UC San Diego. |
| Monty Hall Paradox | Hier findet man Hintergründe und weitere Erklärungen, hier einen Artikel aus der New York Times, und hier etwas zur Sendung Let's Make a Deal. |