Einführung in die Informatik II

Voraussetzungen

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

Ablauf der Vorlesung

Dies ist der Ablauf der Vorlesung im letzten Jahr, die Folien werden im Laufe des Semesters aktualisiert. 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.

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)
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)