Hasso-Plattner-InstitutSDG am HPI
Hasso-Plattner-InstitutDSG am HPI
Login
 

Theoretische Informatik I (Wintersemester 2014/2015)

Dozent: Prof. Dr. Jürgen Dassow

Allgemeine Information

  • Semesterwochenstunden: 4
  • ECTS: 6
  • Benotet: Ja
  • Einschreibefrist: 24.10.2014
  • Lehrform: VU
  • Belegungsart: Pflichtmodul

Studiengänge, Modulgruppen & Module

IT-Systems Engineering BA

Beschreibung

  • Berechenbarkeit auf der Basis von LOOP/WHILE-Programmen, partiell-rekursiven Funktionen, Registermaschinen, Turingmaschinen; 
  • Äquivalenz der Berechenbarkeitsbegriffe; 
  • Existenz von durch Algorithmen nicht berechenbarer Funktionen und unentscheidbarer Probleme;
  • Beispiele unentscheidbarer Probleme;
  • formale Grammatiken und die von ihnen erzeugten Sprachen; 
  • rekursiv-aufzählbare, kontextabhängige, kontextfreie und reguläre Sprachen; 
  • Normalformen; 
  • Chomsky-Hierarchie

Literatur

  • U. Schöning: Theoretische Informatik kurz gefasst. B.I.-Wissenschaftsverlag, 1992.
  • K. Wagner: Einführung in die Theoretische Informatik. Springer-Verlag, 2003.
  • I. Wegener: Theoretische Informatik. Teubner-Verlag, 1993.
  • J.E. Hopcroft, J.D. Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 2. Aufl., Addison-Wesley, 1990.
  • G. Vossen, K.-U. Witt: Grundlagen der Theoretischen Informatik mit Anwendungen.
  • Vieweg-Verlag, Braunschweig, 2000.
  • A. Asteroth, Ch. Baier: Theoretische Informatik. Pearson Studium, 2002.

Leistungserfassung

Die Leistungsbewertung erfolgt durch eine abschließende Klausur.

Zulassungsvoraussetzung für die Klausur ist die erfolgreiche Teilnahme an den Übungen.

Die Teilnahme an den Übungen ist für Studierende erfolgreich, wenn er oder sie durch Votierungen für mindestens zwei Drittel aller Übungsaufgaben erklärt, dass er oder sie die Lösung der jeweiligen Übungsaufgaben präsentieren kann und dies auf Aufforderung nachweist.

Für Studierende, die zum wiederholten Mal teilnehmen und die oben genannte Teilleistung bereits erbracht haben, gilt: die Prüfungsnebenleistung muss nicht erneut erbracht werden

Termine

Vorlesung in HS 3

Übungsgruppen:

Die Übungsgruppen beginnen ab dem 20.10.2014

  • Gruppe 1: Montags, 9:15-10:45 Uhr, Raum A-1.1
  • Gruppe 2: Montags, 13:30-15:00 Uhr, Raum A-1.1
  • Gruppe 3: Montags, 15:15-16:45 Uhr, Raum A-1.1
  • Gruppe 4: Dienstags, 17:00-18:30 Uhr, A-1.2

Mögliche Änderungen siehe Stundenplan
Die Übungen zur LV "Theoretische Informatik I" beginnen in der zweiten Vorlesungswoche (ab dem 20.10.2014).

Die Einschreibelisten für die Übungen liegen ab dem 13.10.2014, 13.00 Uhr im Studienreferat aus.

Zurück