zum Inhalt springen

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)

Creditpoints: 9

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

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