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: Monday the 26.10.2020
  • lecture Mondays: from 10:00 to 12.00 o'clock in Online
  • lecture Wednesdays: from 10:00 to 12.00 o'clock in Online
  • tutorial (alternativ) Tuesdays: from 14:00 to 16.00 o'clock in Online
  • tutorial (alternativ) Tuesdays: from 14:00 to 16.00 o'clock in Online
  • tutorial (alternativ) Wednesdays: from 12:00 to 14.00 o'clock in Online
  • tutorial (alternativ) Wednesdays: from 14:00 to 16.00 o'clock in Online

Exam

Die Angaben zu den Prüfungsmodalitäten (im WiSe 2020/2021 | SoSe 2021) erfolgen vorbehaltlich der aktuellen Situation. Notwendige Änderungen aufgrund universitärer Vorgaben werden zeitnah bekanntgegeben.

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.