Planung der Lehrveranstaltung im SS 02

Einführung in die Informatik II

1. Ziele und Anforderungen

Ziele der Veranstaltung sind:

- die Vermittlung grundlegender Datenstrukturen und zugehöriger Algorithmen,

- Entwicklung von Algorithmen,

- deren Verifikation und Analyse

- sowie die genaue Kenntnis einiger Standardalgorithmen.

Die Veranstaltung ist von zentraler Bedeutung für die gesamte Informatik, da sie die Basisstrukturen (heutiger) informationsverarbeitender Systeme behandelt, wichtige Denkweisen zur Entwicklung von Verfahren vorstellt und zugleich Beurteilungs­krite­rien über Vor- und Nachteile von Algorithmen diskutiert.

Studentischer Aufwand: Für die Lehrveranstaltung "Einführung in die Informatik II" (4 Stunden Vorlesung und 2 Stunden Übungen pro Woche) sind von jedem Studie­renden wöchentlich 12 bis 14 Zeitstunden aufzubringen und zwar im Schnitt:

- 3 Zeitstunden für den Besuch der Vorlesung

- 1,5 Zeitstunden für die Teilnahme an der Übungsgruppe

- 4 bis 5 Stunden Nachbereitung des Vorlesungsstoffs (einschl. Lesen in Büchern)

- 3 bis 5 Stunden Bearbeitungsdauer der Übungen.

Wird diese Zeit regelmäßig (!) aufgewendet, so reichen weitere 60 Stunden zur Prüfungsvorbereitung aus.

Für Personen, die mehr Beispiele kennen lernen möchten oder die den Stoff nochmals erläutert haben wollen, wird zusätzlich ein "Stützkurs" angeboten, der donnerstags von 15.00 bis 16.30 Uhr im Hörsaal V20.01 statt findet.

Die Vorlesung folgt inhaltlich der Vorlesung des Vorjahres, die von Prof. Plödereder gehalten wurde und als Skript bei der Fachschaft erhältlich ist. Wie im jährlichen Rhythmus üblich werden allerdings Teile umgestellt und gewisse Aspekte anders betont.

Die Hörer(innen) sind aufgefordert, den Kontakt zum Dozenten, zu den wissen­schaftlichen Mitarbeiter(inne)n und zu den Tutor(inn)en zu suchen. Hierfür können z.B. Emails und die Sprechstunden genutzt werden. Die Studierenden sollten einen oder zwei Vorlesungssprecher(innen) benennen, die allgemeine Kritik mit dem Lehrpersonal besprechen und Maßnahmen zur Verbesseung vorschlagen sollen.

2. Voraussetzungen

Vorausgesetzt werden die Kenntnisse des ersten Semesters, insbesondere die Inhalte der Lehrveranstaltung "Einführung in die Informatik I" (Prof. Lagally) und mathematische Grundkenntnisse aus einer mindestens 4-SWS-Mathematikver­anstaltung sowie Programmier­kenntnisse. Als Programmiersprache wird Ada 95 verwendet.

Für das Verständnis der Informatik sind die Abstraktion und die Formalisierung besonders wichtig. Abstraktion bezeichnet vor allem das Herausarbeiten gemeinsamer Prin­zipien aus den unterschiedlichsten (Anwendungs-) Gebieten, z.B. die Darstellung von Strukturen in Programmiersprachen, von syntaktischen Gebilden bei natürli­chen Sprachen, von Rechenbäumen oder von Rangier­vorgängen mit Hilfe von (meist kontextfreien) Grammatiken. Bereits die Repräsentation von Objekten der realen Welt durch Buchstaben und Sprachen sowie durch andere Informationen bilden eine Abstraktion, wodurch an Informatiker(innen) wesentlich höhere Abstrak­tionsanforderungen gestellt werden als beispielsweise an "klassische" Ingenieure. Formalisierung umfasst die Fähigkeit, Geschehnisse der realen Welt oder (unscharfe) Informationen so zu präzisieren, dass sie der Verarbeitung durch einen Computer zugänglich werden. Zugleich lassen sich zu formalisierten Objekten oft Aussagen wie Laufzeit, Speicherplatzbedarf, Korrektheit usw. gewinnen, die anderenfalls höchstens grob geschätzt werden könnten. Abstraktion und Formalisierung machen einen großen Teil der Veranstaltung aus.

3. Vorlesung

Dozent: V. Claus.
Termine: Dienstag 8:30 bis 10:00 Uhr, Donnerstag 10:15 bis 11:45 Uhr.

Umfang der Vorlesung: 52 Vorlesungsstunden zu je 45 Minuten.

Geplante Gliederung der Vorlesung:

Manche der Themen wurden bereits in der Vorlesung "Einführung in die Informatik I" behandelt und werden nur in knapper Form wiederholt.

1. Algorithmen 16.4.

- Notation von Algorithmen, Programmiersprache, Mengen

- Rechenmodell, Virtuelle Maschine

- Realisierte Funktion, totale Funktion, Terminierung

- Korrektheit, Beweise

- Äquivalente Algorithmen 18.4.

- Effizienz, Komplexität von Algorithmen

- Gegenläufigkeiten 23.4.

2. Datenstrukturen

- Elementare Datentypen

- Abstrakte Datentypen, Modell, Algebren 25.4.

- Zusammensetzung von Datentypen

- Beispiele: Sequenz, Stack, Queue, Baum, "Geflecht"

3. Graphen 02.5.

- Definitionen

- Darstellungen in Programmiersprachen

- Durchlaufen von Graphen (Tiefe, Breite)

- Durchlaufen von Bäumen 07.5.

- Beispiele 14.5.

4. Suchen 16.5.

- Mengen und ihre Darstellungen

- Suchen in Listen und Feldern

- Suchbäume 21.5.

- Balancierte Bäume 23.5.

- B-Bäume 04.6.

5. Hashverfahren (gestreute Speicherung) 11.6.

- Definitionen, Grundalgorithmus

- Hashfunktionen

- Offene Verfahren (linear, quadratisch, doppelt)

- Rehashing 13.6.

6. Sortieren 18.6.

- Definitionen

- Elementare Sortierverfahren (max, insert, bubble, ..)

- effiziente Sortierverfahren 25.6.

(Tree-, Quick-, Heap-, Merge-, Radix-Sort)

- Externes Sortieren 04.7.

7. Graphenalgorithmen 09.7.

- Wiederholung, Beispiele

- Topologisches Sortieren

- Zuammenhangskomponenten 11.7.

- Kürzeste Wege 16.7.

- Spannende Bäume 18.7.

Literatur:

Manuskript von Prof. Plödereder, SS 01 (bei der Fachschaft erhältlich)

Appelrath, Hans-Jürgen und Ludewig, Jochen, "Skriptum Informatik - eine konventionelle Einführung", Verlag der Fachvereine Zürich und B.G. Teubner Stuttgart, 4. Auflage 1999

Cormen, Leiserson, Rivest, "Introduction to Algorithms", MIT Press, 1996

Güting, R.H., "Datenstrukturen und Algorithmen", B.G.Teubner Stuttgart

Ottmann, T., Widmayer, P., "Algorithmen und Datenstrukturen", 4. Auflage, Spektrum Verlag, Heidelberg, 2002

Schöning, Uwe, "Algorithmik", Spektrum Akademischer Verlag, Heidelberg, 2001

Sedgewick, Robert, "Algorithms in C", 3rd Edition, Addison-Wesley, 1998

[Zu Hinweisen auf die Sprache Ada siehe frühere Vorlesung.]

4. Übungen

Übungsbetreuung: J. Holub, S. Lewandowski, W. Schmid.

Parallel zur Vorlesung werden Gruppenübungen angeboten. Jede Gruppe besteht aus 18 bis 22 Per­sonen. Es wird dringend empfohlen, an diesen Übungsgruppen aktiv teilzunehmen. Es werden 16 Gruppen eingerichtet.

Termine: Montag 13:15 bis 14:45 Uhr, 15:00 bis 16:30 Uhr, 16:45 bis 18:15Uhr,

Donnerstag 13:15 bis 14:45 Uhr, 16:45 bis 18:15Uhr

Das Eintragen in die Übungsgruppen erfolgt online unter

https://inf2.informatik.uni-stuttgart.de/uebungsgruppen-bin/inf2/groups

Der Benutzername lautet ''inf2'', das Passwort ''baum''. Achten Sie darauf, Ihre

Daten korrekt einzugeben. Insbesondere die Email-Adresse sollte gültig sein.

Ablauf

Die Übungsblätter liegen jeweils ab Freitag unter

http://www2.informatik.uni-stuttgart.de/fmi/fk/lehre/ss02/info_II_02.html

im Netz, erstmals am 19.4.02.

Ausgabe der Übungsblätter erfolgt in der folgenden Dienstag-Vorlesung.

Bei Unklarheiten Sprechstunde der Übungsgruppenleiter beachten. Erläuterungen werden ggf. ins Netz gestellt. Fragen können auch per Email gestellt werden und werden - falls von der Kapazität aus gesehen möglich - innerhalb von 24 Stunden beantwortet.

Fragen sowie Anregungen und Kritik können auch auf dem Schwarzen Brett

http://fachschaft.informatik.uni-stuttgart.de/forum/

diskutiert werden.

Abgabe der Lösungen: bis zum nächsten Montag 13:00 Uhr, Programmier­aufgaben per Email an den Übungsgruppenleiter, schriftliche Abgaben in das zugehörige Abgabefach bei den Postschränken im Foyer, 1. Stock, d.h. Be­arbeitungszeit nach Ausgabe: ? 6 Tage. Abgaben in Gruppen bis zu drei Personen sind zugelassen.

Lösungshinweise werden einige Tage nach der letzten zugehörigen Übungsgruppe ins Netz gestellt.

Es gibt folgende 13 Ausgabetermine: 23.4., 30.4., 07.5., 14.5., 21.5., 28.5.,
04.6., 11.6., 18.6., 25.6., 02.7., 09.7., 16.7.

Das letzte Übungsblatt wird nicht mehr besprochen und bewertet.

Aufgaben

Es gibt neben den schriftlichen auch mündlich vorzubereitende Aufgaben, die in den ersten 5 Minuten jeder Übung votiert werden können. Mit der Votierung erklärt sich der/die Betroffene bereit, die Aufgabe in der Übung vorzurechnen und zu erklären. Bei mangelhafter Vorbereitung werden die Votierpunkte dieses Übungsblattes nicht gewertet. Im Wiederholungsfall werden alle bisherigen Votierpunkte gestrichen.

Schwierigkeitsgrad: Die Aufgaben werden so gestellt, dass ihre vollständige Bear­beitung 5 Zeitstunden für einen "durchschnittlichen Studierenden" beansprucht. Wer sich darüber hinaus vertiefen will, kann die Zusatzaufgaben bearbeiten.

Test-Klausuren während der Lehrveranstaltung

Es finden zwei Klausuren im Umfang von je 30 Minuten Dauer am 16.5. und am 20.6. im Rahmen der Vorlesung statt. Sie dienen zum einem dem Selbsttest, zum anderen werden sie dem Dozenten Hinweise geben.

Punktzahlen und Scheinbedingungen

In jedem Übungsblatt können 20 Punkte erreicht werden. Ein Punkt entspricht rund 15 Minuten Bearbeitungszeit. Die Test-Klausuren gehen ebenfalls mit je 20 Punkten ein. Insgesamt können maximal 280 Punkte erreicht werden.

Sofern mindestens 150 Punkte erreicht werden, der/die Betreffende mindestens zwei Aufgaben korrekt vorgetragen hat und durch die Beteiligung in den Übungsgruppen oder durch andere Indizien ersichtlich ist, dass die Übungsaufgaben selbst bear­beitet und die Lösungen verstanden wurden, wird ein Schein über die erfolgreiche Teilnahme ausgestellt. Auf Wunsch wird eine Note hinzugefügt; diese lautet

4,0 für 150 bis 159 Punkte

3,7 für 160 bis 169 Punkte

3,3 für 170 bis 179 Punkte

3,0 für 180 bis 189 Punkte

2,7 für 190 bis 199 Punkte

2,3 für 200 bis 209 Punkte

2,0 für 210 bis 219 Punkte

1,7 für 220 bis 229 Punkte

1,3 für 230 bis 239 Punkte

1,0 für mehr als 240 Punkte