Abteilung Formale Konzepte

Universität Stuttgart
Institut für Informatik
Breitwiesenstr. 20/22
D-70565 Stuttgart
Lageplan
Stadtplan
Abteilung
Institut
Fakultät
Universität

Vorlesung: Einführung in die Informatik II

Grundvorlesung
Folien - Übungsblätter und aktuelle Informationen - Schwarzes Brett
Die Fachschaft Informatik und Softwaretechnik hat eine Vorlesungsumfrage durchgeführt. Die Ergebnisse finden Sie hier.
Vorlesung4V+2Ü
Dozenten:Claus
Lewandowski, Schmid
Termine:Di08:30 bis 10:00im V20.01Vorlesungab 16.4.
Do10:00 bis 11:30im V20.01Vorlesungab 18.4.
Do15:00 bis 16:30im V20.01Stützkursab 18.4.
Übungen:Mo13:15 bis 14:45im V20.03, 1.026, 1.035, 1.039, 1.040 Übungab 29.4.
Mo15:00 bis 16:30im V20.03, 1.026 Übungab 29.4.
Mo16:45 bis 18:15im 1.026, 1.040, 2.026 Übungab 29.4.
Di11:50 bis 13:20im V20.04, 1.034 Übungab 30.4.
Do13:15 bis 14:45im 1.031, 1.034 Übungab 2.5.
Do16:45 bis 18:15im 1.034, 1.035 Übungab 2.5.
Das Eintragen in die Übungsgruppen ist abgeschlossen. Die Belegung der Gruppen können Sie weiterhin hier einsehen. Umtragungen werden nur noch bei begründeten Sonderfällen vorgenommen.

Beschreibung

Vorgehensweise bei der Entwicklung und Implementierung von Algorithmen; Korrektheitsbegriff und -formalismen; Spezifikation und Implementierung; Komplexität und Effizienz von Algorithmen; Wahl der Datenstrukturen; Listen, Bäume, Graphen; diverse interne und externe Such- und Sortierverfahren; diverse Graphenalgorithmen; Algorithmen auf Mengen und Relationen; Nebenläufigkeit; Geometrische Algorithmen

Die detailierte Beschreibung (Planung) wurde den Studenten ausgeteilt, ebenso am Ende des Semesters die rückblickende Zusammenfassung (ps), (pdf).

Voraussetzungen

Kenntnisse aus der Vorlesung "Einführung in die Informatik I" sowie Kentnisse in der Programmiersprache Ada95.

Ablauf der Vorlesung

16.4.0. Vorbemerkungen
1. Algorithmen
1.1 Charakteristika von Algorithmen
1.2 Grenzen der Algorithmen
1.3 Korrektheit von Algorithmen
Folien 1-47: (ps), (pdf)
18.4.1.3 Korrektheit von Algorithmen (Fortsetzung)
1.4 Komplexität von Algorithmen
Folien 48-72: (ps), (pdf)
23.4.1.4 Komplexität von Algorithmen (Fortsetzung)
1.5 Gegenläufigkeiten
Folien 73-99: (ps), (pdf)
25.4.2. Datenstrukturen
2.1 Mengen und elementare Typen
2.2 Datenkonstruktoren
2.3 Aufbau von Programmiersprachen
Folien 1-21: (ps), (pdf)
30.4.2.4 Felder (arrays) Folien 22-46: (ps), (pdf)
02.5.2.5 Pointer, Listen
2.6 Stapel, Warteschlangen
Folien 47-54: (ps), (pdf)
07.5.2.6 Stapel, Warteschlangen (Fortsetzung) Folien 54-75: (ps), (pdf)
14.5.
+
16.5.
2.7 Geflechte, die Halde und Freispeicher
2.7.1 Freispeicherverwaltung
2.7.2 Speicherbereinigung (garbage collection)
2.8 Zusammenfassung
Folien 74-117: (ps), (pdf)

Folien zur Vorlesung

Die Kapitel 0-2 (Vorbemerkungen, Algorithmen, Datenstrukturen: Folien 1-218) stehen jetzt auch komplett in einer Datei als
Postscript (3.29 MB) und PDF (854 KB) zur Verfügung.

Ab Kapitel 3 stehen nur die zusätzlichen Beispiele und Folien aus der Beamerpräsentation zur Verfügung. Die Folien aus der Vorlesung sind dem Skipt Einführung in die Informatik II (Plödereder) entnommen, das Sie sich in der Fachschaft kopieren können.

21.5.3 Graphen und Bäume
3.1 Graphen: Definitionen
Folien 1-12: (ps), (pdf) (Achtung: 18 MB! bzw. pdf mit geringerer Auflösung: 1.5 MB!)
23.5.3.2 Darstellung von Graphen
3.3 Bäume: Definitionen
Folien 1-12: (ps), (pdf) (Achtung: 1.5 MB! bzw. pdf mit geringerer Auflösung: 150 kB!)
28.5. 3.4 Darstellung von Bäumen
3.5 Darstellung von allgemeinen Bäumen als Binärbaum
3.6 Anwendungen von Bäumen
3.7 Bäume: Traversierungsalgorithmen
Folien 1-16: (ps), (pdf)
04.6.4 Suchen
4.1 Suchen in "flachen" Strukturen
4.2 Binärbäume als Suchbäume
Folien 1-11: (ps), (pdf) - Link zum GTA-Visualizer
06.6.
+
11.6.
4.3 AVL-Bäume Folien 1-12: (ps), (pdf)
13.6.4.3 1/2 B-Bäume
18.6.
+
20.6.
4.4 Digitale Suchbäume
5 Hashing (gestreute Speicherung)
5.1 Beispiel "modulo p"
5.2 Hashfunktionen
5.3 Offenes Hashing
Folien 1-51: (ps), (pdf)
25.6.5.4 Analyse der Hashverfahren
5.5 Rehashing
Folien 1-18: (ps), (pdf)
27.6.6 Sortieren
6.0 Überblick, allgemeine Analyse
Folien 1-16: (ps), (pdf)
02.7.6.1 Sortieren durch Aussuchen/Auswählen Folien 1-22: (ps), (pdf)
04.7.
+
09.7.
6.2 Sortieren durch Einfügen
6.3 Sortieren durch Austauschen
6.4 Sortieren durch Mischen
nach Skript Plödereder, zusätzliche handschriftliche Folien zu 6.3 und 6.4 liegen im Semesterapparat zum Kopieren bereit
11.7.6.5 Sortieren durch Streuen und Sammeln
6.6 Paralleles Sortieren
Folien 0-65: (ps), (pdf)
16.7.7 Graphalgorithmen
7.0 Überblick, Definitionen
7.1 Durchsuchen eines Graphens
7.2 Topologisches Sortieren
Folien 1-36: (ps), (pdf)
18.7.7.2 Topologisches Sortieren (Fortsetzung)
7.3 Kürzeste Wege
7.4 Minimale Spannbäume
Folien 1-11: (ps), (pdf)

Übungsblätter

Die Scheine können ab 5. August bei Frau Photien (Raum 1.049) abgeholt werden.

Im System eClaus können Sie weiterhin Ihre korrigierten Abgaben einsehen.

Ein abschließendes Feedback über eClaus ist stets willkommen, bitte einfach per eMail an Stefan Lewandowski (Lewandowski@informatik.uni-stuttgart.de).

Die Tutoren waren ...

Sonstiges

Fragen zur Vorlesung und den Übungen, sowie Anregungen und Kritik können auf dem Schwarzen Brett diskutiert werden.

Literatur

H.-J. Appelrath und J. Ludewig: Skriptum Informatik - eine konventionelle Einführung, 4. Auflage, Teubner, 1999
Robert Sedgewick: Algorithms in C, 3rd Edition, Addison-Wesley, 1998
Cormen, Leiserson, Rivest: Introduction to Algorithms, MIT Press, 1996
U. Schöning: Algorithmen - kurz gefasst, Spektrum Akademischer Verlag, 2001
R.H. Güting: Datenstrukturen und Algorithmen, B.G.Teubner Stuttgart
T. Ottmann und P. Widmayer, Algorithmen und Datenstrukturen, 4. Auflage, Spektrum Verlag, Heidelberg, 2002
Impressum
Last modified: Mon Oct 14 09:17:32 CEST 2002