Begrüßung

Informatik II
Vorlesung: Montag 8:15 - 10:00 Donnerstag 8:15 - 10:00
Hörsaal: M1 M1
Übung: diverse Gruppen
Anmeldung ab 04.04.2006, 00:00 Uhr über das
Anmeldungssystem (Link auf der WWW-Übungsseite!)
Beginn der Übungen: 06.04.2006
Dozent: Koordination der Übungen:
Prof. Dr. Klaus Hinrichs Dipl.-Math. Kai Rothaus
Institut für Informatik Institut für Informatik
Einsteinstr. 62 Einsteinstr. 62
6. Stock, Raum 606 6. Stock, Raum 602b
khh@[Link] rothaus@[Link]
© Klaus Hinrichs Informatik II – Intro 1

Informatikbezogene Studiengänge
• Diplomstudiengang Informatik
• Diplomstudiengang Geoinformatik
• Bachelorstudiengang Language, Text and Information
• Bachelorstudiengang Wirtschaftsinformatik
• Informatik Lehramt: 2-Fach Bachelor
• Nebenfach Informatik im Diplomstudiengang Mathematik
• Nebenfach / Wahlpflichtfach / Wahlfach Informatik zu diversen
Studiengängen, z.B. Biologie, Physik

© Klaus Hinrichs Informatik II – Intro 2

Webseite zu Vorlesung und Übung
Aktuelle Informationen online unter
[Link]
zu
• Vorlesung, Übung, Anmeldung
• Literatur
• Folien und Übungszettel im PDF-Format
• JAVA: Dokumentation, Installation etc. siehe
[Link]
• Bedingungen zur Erlangung des Übungsscheins
• Abgabetermin und Abgabeort für Übungen
• Bereitstellung des 1. Übungsblattes: 03. April 2006
• …
• Klausurtermin: Sonnabend, 15. Juli 2006, 8 - 10 Uhr

© Klaus Hinrichs Informatik II – Intro 3

Ziele der Vorlesung

• Fortsetzung der Vorlesung Informatik I
• Einführung in Grundbegriffe, Denkweisen und Techniken der Informatik
• Techniken der Entwicklung und Analyse von Algorithmen und
Datenstrukturen: Sortieren, Speichern (Suchbäume, ausgewogene
Bäume, Hashing), Graphenalgorithmen, geometrische Algorithmen etc.
• Design, Realisierung und Test von Programmen und Benutzung von
Programm-Bibliotheken
• Programmiersprache: Java
• Erkenntnis, daß Informatik nicht mit Hacken am Computer
gleichzusetzen ist
• Neugier auf Ihr weiteres Informatik-Studium

© Klaus Hinrichs Informatik II – Intro 4

Anforderungen an die Beteiligten
Dozent:
• Vermitteln des Stoffes in angemessenem Tempo
• Gratwanderung zwischen Breite und Tiefe
• Blick über den Vorlesungstellerrand

Übungsorganisatoren / Tutoren:
• Vertiefen der Vorlesungsinhalte durch Übungen
• Einführung in die praktische Nutzung der Programmiersprache Java
• Lernhilfen und zusätzliche Herausforderungen

© Klaus Hinrichs Informatik II – Intro 5

Anforderungen an die Beteiligten

Studierende:Punkte Note Anzahl Prozent
• Teilnahme an der59.5Vorlesung und5 an den133 34.82%
Übungen
65
• Eigenständige Nachbearbeitung 17 4.45%
4 des Vorlesungsstoffes
70.5 soviel 3.7
Richtlinie: mindestens 21 5.50%
Zeit wie für Vorlesung, d.h. 4 Stunden
pro Woche 76Einsichtnahme / Rückgabe
3.3 32 8.38%
81.5dermit
Klausur 3 28 7.33%
• Auseinandersetzung Primär- zur
und Informatik I:
Sekundärliteratur
87Dienstag, 2.7
25. 4. 2006, 32 M68.38%
• Aktive Bearbeitung
92.5 der Übungsaufgaben 29 7.59%
Näheres 2.3auf der Homepage
• Eigeninitiative bei98
der Erweiterung der Programmierfähigkeiten
2 Informatik15 3.93%
der Vorlesung I
• Überwinden der Praxisschwelle
103.5 1.7 26 6.81%
• Feedback an den 109 15 3.93%
1.3 Übungsleiter
Dozenten bzw.
114.5 1 10 2.62%
130 0.7 24 6.28%
382

© Klaus Hinrichs Informatik II – Intro 6

Hinweise zu Materialien
• Folienskript wird zur Verfügung gestellt, einige Teile werden in der
Vorlesung entwickelt
• Skript existiert nicht!
• Ergänzende Literaturhinweise in der Vorlesung
• Folien sind Stichpunkte! Es gilt das, was in der Vorlesung gesagt
wurde!
• Hilfreich: Anmerkungen in den Folien und handschriftliche
Ergänzungen (! aktive Teilnahme)

© Klaus Hinrichs Informatik II – Intro 7

Literatur
J. Nievergelt, K. Hinrichs:
Algorithms and Data Structures -
with Application to Graphics and Geometry,
Prentice-Hall, Englewood Cliffs, NJ, 1993.
vdF Hochschulverlag, Zürich, 1999, ISBN 3-7281-2523-7.
T. Cormen, C. Leiserson, R. Rivest:
Introduction to Algorithms, 2nd ed.,
MIT Press, Cambridge, MA, 2001.
M. Goodrich, R. Tamassia:
Data Structures and Algorithms in JAVA, 2nd ed.,
John Wiley & Sons, New York, 2005.

© Klaus Hinrichs Informatik II – Intro 8

Literatur
D. E. Knuth, The art of computer programming,
Vol. 1 - Fundamental algorithms, 3rd ed., 1997,
Vol. 2 - Seminumerical algorithms, 3rd ed., 1998,
Vol. 3 - Sorting and searching, 2nd ed., 1998,
Addison-Wesley, Reading, MA.
T. Ottmann, P. Widmayer:
Algorithmen und Datenstrukturen,
4. Aufl., Spektrum Akad. Verlag, 2002.
M. Weiss:
Data Structures and Algorithm Analysis in JAVA, Addison-Wesley,
Reading, MA, 2006.
Diverse Exemplare dieser Bücher stehen
in der Fachbereichsbibliothek
zur Ausleihe zur Verfügung!

© Klaus Hinrichs Informatik II – Intro 9

Gliederung der Vorlesung

Informatik II: Datenstrukturen und Algorithmen

1 Algorithmen auf primitiven Datentypen

2 Matrizen und Graphen: Transitive Hülle
3 Berechenbarkeit und Komplexität
4 Mathematische Grundlagen der Analyse von Algorithmen
5 Suchen und Sortieren
6 Datenstrukturen und abstrakte Datentypen
7 Implizite Datenstrukturen
8 Listenstrukturen
9 Adressberechnungsverfahren (Hashing)
10 Geometrische Algorithmen

© Klaus Hinrichs Informatik II – Intro 10

Einleitung Informatik II
• Programmieren im Großen vs.
Programmieren im Kleinen

• Historischer Rückblick:
Rechnen mit Zahlen und anderen Objekten

• Algorithmen und Programme

© Klaus Hinrichs Informatik II – Intro 11

Programmieren im Großen
• Entwicklung großer Systeme, z. B. Betriebssysteme und Datenbanken,
erfordert Organisationstalent!
• Organisatorische Aspekte stehen im Vordergrund!
• Wichtige Fragestellungen bzw. Probleme:
– Analyse der Anforderungen – Anpaßbarkeit an neue Systeme
– Funktionale Spezifikation – Anpaßbarkeit an neue Anforderungen
– Verträglichkeit mit anderen Systemen – Organisation des Projektteams
– Modularisierung / Architektur – Testen der Software
– Dokumentation
" Software Engineering
• Große Programme sind gewöhnlich flach, d.h. viele Kommentare,
Definitionen, Deklarationen, Initialisierungen und viel Code, der nur
selten ausgeführt wird!
• Verständnisprobleme auf Grund des Umfangs!
• Frederick Brooks: The Mythical Man-Month

© Klaus Hinrichs Informatik II – Intro 12

Programmieren im Kleinen
• Kleine Programme erfordern techn. Kenntnisse und Einfallsreichtum!
• Algorithmische Aspekte stehen im Vordergrund!
• Wichtige Fragestellungen bzw. Probleme:
– Welcher von verschiedenen Algorithmen, die alle dasselbe Problem
lösen, ist unter gegebenen Umständen am effizientesten?
– Wieviel Zeit und Speicherplatz werden benötigt?
– Welche Datenstrukturen sollen wir einsetzen?
• Kleine Programme sind gewöhnlich tief, d.h. sie sind aus kurzen,
kompakten Programmfragmenten (z. B. Schleifen) aufgebaut, die
sehr oft ausgeführt werden.
• Verständnisprobleme auf Grund schwieriger Gedankengänge!
• Diese Vorlesung: Programmieren im Kleinen!
Ziel: Verständnis eleganter, interessanter, kleiner Programme bis ins
letzte Detail!
• Programmieren im Großen " Vorlesungen über Software-Engineering.
© Klaus Hinrichs Informatik II – Intro 13

Rechnen mit Zahlen und anderen Objekten

• Computation bezog sich ursprünglich auf Zahlen, heute auf Bilder,
Texte und andere Typen von Objekten
Erste Generation:
• Wissenschaftliche / technische Anwendungen " Numerisches Rechnen
• Daten: Zahlen oder Mengen von Zahlen mit einfacher Struktur, z.B.
Vektoren und Matrizen
• Programme: lange Laufzeiten, kleine Mengen an Ein- / Ausgabedaten
• Algorithmen wichtiger als Datenstrukturen
! Erfindung vieler numerischer Algorithmen
• Dauerhafte Errungenschaften:
– Systematische Entwicklung von Algorithmen und Methoden
zu ihrer Bewertung
– Fehleranalyse
– Programmbibliotheken (libraries)
– erste höhere Programmiersprachen: FORTRAN und ALGOL.
© Klaus Hinrichs Informatik II – Intro 14
Rechnen mit Zahlen und anderen Objekten
Zweite Generation:
• Kommerzielle Anwendungen "
Verwaltung und Aktualisierung großer Datenmengen, Text- und
Maskenverarbeitung, Reportgenerierung
• Wenig rechenintensiv, sehr datenintensiv:
Eingabe, Speichern, Transfer, Ausgabe von Daten
• Effiziente Verwaltung umfangreicher, dynamischer (d.h. sich
verändernder) Datenmengen ! Erfindung vieler Datenstrukturen
und der entsprechenden Algorithmen zur Verwaltung von Daten, z.B.
Such- oder Sortieralgorithmen
• Dauerhafte Errungenschaften:
– Systematische Entwicklung von Datenstrukturen
– Programmiersprachen: COBOL
– Datenbanken: Hierarchisches Datenmodell, Netzwerkmodell,
Relationales Modell
© Klaus Hinrichs Informatik II – Intro 15

Rechnen mit Zahlen und anderen Objekten

Dritte Generation:
• Computer mit Rastergraphik " Rechnen mit geometrischen und
bildhaften Objekten, Speicherung geometrischer Daten
• Hochentwickelte, graphische Benutzerschnittstellen
• Viele neue Anwendungen:
CAD, Bildverarbeitung, Mustererkennung
• Effiziente Verarbeitung geometrischer und bildhafter Objekte "
Algorithmische Geometrie
• Dauerhafte Errungenschaften:
– Entwicklung neuer Datenstrukturen und Algorithmen zur
Verarbeitung geometrischer Daten
– Programmiersprachen: C++
– Computergraphik
– Objekt-orientierte Datenbanken
– Geoinformationssysteme
© Klaus Hinrichs Informatik II – Intro 16
Rechnen mit Zahlen und anderen Objekten
Jetzt:
• Internet, Netzwerke, mobile Telekommunikation "
verteilte Systeme und Anwendungen, verteiltes Rechnen
• Viele neue Anwendungen
• Effizienter Zugriff auf sehr umfangreiche, verteilte Daten "
Data Warehousing, Data Mining
• Dauerhafte Errungenschaften:
– …
– Höhere Programmiersprachen: JAVA
– Verfahren zum Zugriff auf verteilte, heterogene Datenbestände
– Datenstrukturen zur Verwaltung und Algorithmen zur Analyse sehr
umfangreicher Datenbestände "
externe Algorithmen

© Klaus Hinrichs Informatik II – Intro 17

Algorithmen und Programme

• Theoretische Informatik:
Algorithmus als formaler Begriff, streng definiert auf verschiedene
Arten, z.B. durch Turing-Maschinen oder #-Kalkül.
• Programmieren:
Algorithmus als intuitiver Begriff
• Formalisierung eines Algorithmus durch ein Programmfragment, das
den Algorithmus in einer formal definierten Programmiersprache
ausdrückt " Entwurfsentscheidungen
• Darstellung von Algorithmen in einer Notation, die die
Schlüsselideen am besten aufzeigt
" Ein Bild sagt mehr als tausend Worte!!!
• Programme in erweiterter JAVA-Notation!
Übertragung in andere Programmiersprache sollte nicht
schwerfallen!

© Klaus Hinrichs Informatik II – Intro 18