Vorlesung Algorithmen und Datenstrukturen

Wintersemester 1997/1998 und Sommersemester 1998

• Allgemeines
• Termine und Räume
• Inhalt der Vorlesung
• Spielregeln
• Übungsblätter
• Testat- und Belegaufgaben
• Zusätzliche Materialien
• Diskussion zu Übungsaufgaben
• Hamster-Programmierwettbewerb
• Betreuer
• Literatur
• Verweise

Auf dieser Seite finden Sie verschiedene Informationen zu der Einführungsvorlesung "Algorithmen und Datenstrukturen", die im Wintersemester 1997/1998 und im Sommersemester 1998 von Prof. Dr. Rudolf Kruse an der Otto-von-Guericke-Universität Magdeburg für Informatiker, Wirtschaftsinformatiker und Computervisualisten gehalten wird. Diese Seite wird im Laufe des Semesters aktualisiert.

Die Vorlesung findet im Sommersemester 1998 zu den folgenden Zeiten statt:

Die Vorlesung beginnt am Montag, den 06.04.1998.

Die Übungen finden, nach Gruppen geordnet, im Sommersemester 1998 zu den folgenden Zeiten statt:

Die Übungen beginnen in der ersten Vorlesungswoche, d.h. ab Montag, den 06.04.1997.

Die Tutorien (siehe Spielregeln) finden, nach Gruppen geordnet, im Sommersemester 1998 zu den folgenden Zeiten statt:

Die Tutorien beginnen in der dritten Vorlesungswoche, d.h. ab Dienstag, den 14.04.1998.

• Algorithmen
  • Der Algorithmusbegriff
  • Berechenbarkeit und Komplexität
  • Effizienz von Algorithmen
  • Sortieren und Suchen
  • Dynamische Programmierung
  • Greedy-Algorithmen
  • Teile-und-Herrsche-Algorithmen (divide and conquer)
• Datenstrukturen
  • Felder (Vektoren) und Verbunde
  • Listen (einfach und doppelt verkettete Listen, Keller und Schlangen)
  • Bäume (Binärbäume, AVL-Bäme und B-Bäume)
  • Hash-Tabellen

1. Die Übungen werden mit einem Schein abgeschlossen. Dieser dient gleichzeitig als Zulassungsvoraussetzung für die vierstündige Klausur im Sommer 1998.
2. Organisatorische Regelungen für den Übungsschein:
   1. Zu den Übungen gibt es Übungsblätter. Es müssen (bis eine Stunde vor jeder Übung per E-mail an den Übungsleiter, erste Übung ausgenommen) von jedem Studenten Aufgaben votiert werden. Zu den votierten Aufgaben ist der jeweilige Student bereit vorzutragen (Lösungsvorschläge werden diskutiert, sie müssen nicht gleich richtig sein!).
   2. Am Rechner werden ein Testat (nur mündlich) und ein Beleg (mündlich und schriftlich, d.h. mit abzugebender Ausarbeitung) abgenommen.
   3. Wer mindestens
      • 2/3 der Übungsaufgaben votiert,
      • viermal in den Übungen vorgetragen,
      • das Testat erfüllt und
      • den Beleg erfolgreich verteidigt hat,
      bekommt den Schein.
3. Zusätzlich zu Vorlesung und Übung werden Tutorien angeboten. Der Besuch dieser Veranstaltung ist freiwillig und dient dem Erlernen des Programmierens
   • am Unix-Rechner in C (Informatiker und Wirtschaftsinformatiker) bzw.
   • in Smalltalk (VisualWorks) unter Unix oder Windows (Computervisualisten).
   Die Tutorien werden nicht bewertet.

An dieser Stelle finden Sie alle bisher bearbeiteten Übungsblätter sowie das jeweils aktuelle Übungsblatt als Postscript und Microsoft Word oder LaTeX Datei.

• 1. Übungsblatt: Algorithmische Grundbegriffe
  Postscript Microsoft Word
• 2. Übungsblatt: Entwurf von Algorithmen, applikative Algorithmen, Registermaschinen
  Postscript Microsoft Word
  
• 3. Übungsblatt: Effizienz/Komplexität von Algorithmen
  Postscript LaTeX Registermaschine aus Beispiel 3.8
• 4. Übungsblatt: Komplexitätsanalyse und Entwurf von Algorithmen
  Postscript Microsoft Word
• 5. Übungsblatt: C-/Smalltalk-Programmierung
  IF/WIF (C): Postscript LaTeX
  CV (Smalltalk): Postscript
• 6. Übungsblatt: Entwurf und Analyse von Algorithmen, Sortieralgorithmen
  Postscript Microsoft Word
• 7. Übungsblatt: Entwurf und Analyse von Algorithmen
  Postscript Microsoft Word
• 8. Übungsblatt: Dynamische Programmierung
  Postscript LaTeX
• 9. Übungsblatt: abstrakte Datentypen, Listen und Keller
  Postscript Microsoft Word
• 10. Übungsblatt: abstrakte Datentypen, Graphen und Bäume
  Postscript Microsoft Word
• 11. Übungsblatt: ausgeglichene Bäume, Hash-Verfahren, Sortieren
  Postscript Microsoft Word

Zu folgenden Übungsaufgaben (siehe Übungsblätter) werden Testate abgenommen: 4, 7, 8, 9, 10, 11, 13, 18, 20, 22 und 24 (weitere Aufgaben nach Absprache mit dem zuständigen Übungsleiter). Die Abnahme erfolgt in den Tutorien durch die Übungsleiter, ggf. nach Absprache eines Termins. Zum Erwerb des Testats ist ein Programm, das eine der oben genannten Aufgaben löst, am Rechner vorzuführen und zu erklären. Programme von dieser Seite werden allerdings nicht akzeptiert.

Belegaufgaben

Informatiker/Wirtschaftsinformatiker (C)

In der Belegaufgabe für Informatiker/Wirtschaftsinformatiker werden einfach verkettete Listen und Operationen auf diesen behandelt.

• Aufgabenstellung
  Postscript Microsoft Word
• Hinweise zu einfach verketteten Listen in C
  Postscript LaTeX
  

Kopien der Aufgabenstellung, der Hinweise zu einfach verketteten Listen in C, sowie englischsprachiger Literatur zum diesem Thema werden in den Übungen verteilt.

Abgabe der schriftlichen Belegarbeit: 24.04.1998
Abnahme der Programme am Rechner: im Mai 1998, nach Absprache mit dem zuständigen Übungsleiter

Computervisualisten (Smalltalk)

• Aufgabenstellungen
  Postscript

Abgabe der schriftlichen Belegarbeit: 31.05.1998
Abnahme der Programme am Rechner: Anfang Juni 1998, nach Absprache mit dem zuständigen Übungsleiter

Wegen des stark gewachsenen Umfangs dieses Abschnittes wurde für ihn eine eigene Seite angelegt.

Für die Diskussion von Übungsaufgaben und Lösungen steht eine eigene Seite zur Verfügung.

Für den Hamster-Programmierwettbewerb steht eine eigene Seite zur Verfügung.

Professor

• Prof. Dr. Rudolf Kruse, rudolf.kruse@cs.uni-magdeburg.de
  

Übungsleiter

• Dipl. Math. Ilona Blümel, ilona.bluemel@cs.uni-magdeburg.de
• Dipl. Inform. Christian Borgelt, christian.borgelt@cs.uni-magdeburg.de
• Dipl. Inf. Jörg Hamel, hamel@isg.cs.uni-magdeburg.de
• Dipl. Inform. Matthias König, koenig@isg.cs.uni-magdeburg.de
• Dr.-Ing. Bernhard Preim, bernhard@isg.cs.uni-magdeburg.de
• Dipl. Inf. Stefan Schlechtweg, stefans@isg.cs.uni-magdeburg.de

Tutoren

• Stud. Inf. Marcel Korn, korn@hppool.cs.uni-magdeburg.de
• Stud. WiInf. Mario Krüger, mkrueger@hppool.cs.uni-magdeburg.de
• Stud. WiInf. Jens Lehmkau, lehmkau@hppool.cs.uni-magdeburg.de
• Stud. Inf. Nico Rose, nrose@hppool.cs.uni-magdeburg.de
• Stud. CV. Peter Schulze, pschulze@sunpool.cs.uni-magdeburg.de
• Stud. CV. Denis Kalkofen, kalkofen@hppool.cs.uni-magdeburg.de
• Stud. CV. Alexander Lazarevic, alexander.lazarevic@student.cs.uni-magdeburg.de
• Stud. CV. Oliver Schmieding

Die folgende Literaturliste ist alphabetisch geordnet, die Reihenfolge stellt also keine Bewertung dar. Sie brauchen sich keines der aufgeführten Bücher zu kaufen, alle sind in der Bibliothek (bzw. die Skripte von Prof. Dassow und Prof. Ehrich im WWW, das Skript von Prof. Ehrich außerdem als Kopiervorlage in der Fakultätsbibliothek) verfügbar.

• Alfred V. Aho, John E. Hopcroft und Jeffrey D. Ullman
  The Design and Analysis of Computer Algorithms
  Addison-Wesley 1974
• Alfred V. Aho und Jeffrey D. Ullman
  Informatik - Datenstrukturen und Konzepte der Abstraktion
  Thomson Publishing 1996
• Jürgen Dassow
  Vorlesungsskript Algorithmen und Datenstrukturen I, Wintersemester 1996/1997
  Postscript-Dateien
• H.-D. Ehrich
  Einführung in die Informatik
  Auszug aus einem Vorlesungsskript der TU Braunschweig
  Postscript-Datei
• L. Goldschlager und A. Lister
  Informatik - Eine moderne Einführung
  Hanser-Verlag 1990
• Donald E. Knuth
  The Art of Computer Programming
  Volume I: Fundamental Algorithms
  Addison-Wesley 1968
• K. Mehlhorn
  Effiziente Algorithmen
  Teubner-Verlag 1977
• Ch. Meinel
  Effiziente Algorithmen
  Fachbuchverlag Leipzig 1991
• T. Ottmann und O. Widmayer
  Algorithmen und Datenstrukturen
  BI Wissenschaftsverlag 1993
• R. Sedgewick
  Algorithmen in C
  Addison-Wesley 1992
• Niklaus Wirth
  Algorithmen und Datenstrukturen
  Teubner-Verlag 1995

• Otto-von-Guericke-Universität Magdeburg
• Fakultät für Informatik
• Institut für Wissens- und Sprachverarbeitung
• Arbeitsgruppe Neuronale Netze und Fuzzy-Systeme
  • andere Lehrveranstaltungen
  • Informationen zum Studium