course: Theoretical Computer Science

number:
150240
teaching methods:
lecture with tutorials
media:
overhead transparencies, black board and chalk
responsible person:
Prof. Dr. Maike Buchin
lecturer:
Prof. Dr. Maike Buchin (Mathematik)
language:
german
HWS:
6
CP:
9
offered in:
winter term

dates in winter term

  • start: Wednesday the 09.10.2019
  • lecture Mondays: from 10:00 to 12.00 o'clock in HZO 70
  • lecture Wednesdays: from 10:00 to 12.00 o'clock in HNC 20
  • tutorial (alternativ) Tuesdays: from 14:00 to 16.00 o'clock in IA 1/63
  • tutorial (alternativ) Tuesdays: from 14:00 to 16.00 o'clock in NB 5/99
  • tutorial (alternativ) Wednesdays: from 08:00 to 10.00 o'clock in IA 1/181
  • tutorial (alternativ) Wednesdays: from 14:00 to 16.00 o'clock in IA 1/63

Exam

All statements pertaining to examination modalities (for the summer/winter term of 2020) are given with reservations. Changes due to new requirements from the university will be announced as soon as possible.

Termin wird vom Dozenten bekannt gegeben

Form of exam:written
Registration for exam:FlexNow
Duration:180min

goals

Die studierenden haben fundamentale Einsichten zum Verhältnis zwischen Automaten und Grammatiken und zum Verhältnis von Determinismus und Nicht-Determinismus. Durch Einüben von Beweistechniken wie wechselseitige Simulation oder (polynomiell) berechenbare Reduktionen ist die Einsicht gereift, dass an der Oberfläche verschieden aussehende Konzepte im Kern identisch sein können. Zudem wurde ein tieferes Verständnis von Komplexität erreicht. Auf den unteren Ebenen der Chomsky-Hierarchie finden sich effizient lösbare Anwendungsprobleme der Textmanipulation und Textanalyse. Auf den oberen Ebenen der Hierarchie haben die Studierenden Bekanntschaft mit dem Phänomen der inhärenten Härte (oder gar Unentscheidbarkeit) eines Problems gemacht.

content

  • Grammatiken (mit Schwerpunkt auf kontextfreien Grammatiken)
  • Automaten
  • endliche Automaten
  • Kellerautomaten
  • Turing-Maschinen
  • Berechenbarkeitstheorie
  • NP-Vollständigkeitstheorie

requirements

keine

recommended knowledge

Nützlich (aber nicht zwingend erforderlich) sind elementare Grundkenntnisse in Informatik und Diskreter Mathematik sowie Vertrautheit mit mindestens einer Programmiersprache.

literature

  1. Hopcroft, John E., Motwani, Rajeev, Ullman, Jeffrey D. "Introduction to Automata Theory, Languages, and Computation", Addison Wesley Longman Publishing Co, 2001
  2. Sipser, Michael "Introduction to the Theory of Computation", Brooks Cole, 2005
  3. Schöning, Uwe "Theoretische Informatik - kurzgefasst", Spektrum Akademischer Verlag, 2001

miscellaneous

Master-Studierende der Angewandten Informatik die Theoretische Informatik innerhalb des Bachelorstudiums abgelegt haben, belegen im Masterstudium die Veranstaltung Datenbanksysteme.