Vorlesung über "Informatik I"

Die Vorlesung Informatik I schließt sich an den Programmierkurs Java an, Programmierkenntnisse in Java werden vorausgesetzt. Es werden u.a. die folgenden Themen behandelt:

• Was ist Informatik?
• Aufbau und Funktionsweise von Computern
• Entwurf von Algorithmen (Problemspezifikation, Verifikation)
• Analyse von Algorithmen (Terminierung, Laufzeit)
• O-Notation, Worst-Case-Laufzeit, amortisierte Laufzeit
• einfache Datenstrukturen (Listen, Stapel, Schlangen)
• Sortierverfahren (u.a. Radix-, Quick-, Merge- und Heapsort, externe Verfahren)
• Suchverfahren (u.a. lineare, binäre, exponentielle Suche)
• Hashverfahren
• Bäume (heaps, Suchbäume, balancierte Bäume)
• Union-Find-Datenstrukturen
• effiziente Textsuche
• einfache Graphenalgorithmen (u.a. aufspannende Bäume, kürzeste Wege)

Termine

• Vorlesungsbeginn: Mittwoch, den 5. April, um 13.15 Uhr!!
• Montags 15.15-16.45 Uhr und mittwochs 13.00-14.30 Uhr im Hörsaal II der Physikalischen Institute.
• Übungen: nach Vereinbarung, im Pohlighaus; Betreuer: S. Porschen

Creditpoints: 9

Scheinerwerb

Erwerb durch erfolgreiche Bearbeitung von Übungsaufgaben und Teilnahme an einer Klausur am Ende des Semesters.

Die ausgearbeitete Mitschrift finden Sie hier als pdf-Datei. Bitte teilen Sie uns Fehler mit, die Sie im Skript finden. Danke!

Zur Vorlesung wurden auch Folien von Küchlin und Weber mit freundlicher Genehmigung bereitgestellt.

Literatur

• Gumm/Sommer: Einführung in die Informatik. 6. Aufl. Oldenbourg Verlag 2004
• Ottmann/Widmayer: Algorithmen und Datenstrukturen. 4. Aufl. Spektrum Verlag 2002
• Küchlin/Weber: Einführung in die Informatik. 3. Aufl. Springer-Verlag 2005
• Sedgewick: Algorithmen in Java. 3. Aufl. Pearson 2003
• Cormen/Leiserson/Rivest/Stein: Introduction to Algorithms. Second Edition. MIT Press 2001