Theoretische Informatik I (1. Semester) (Wintersemester 2004/2005)

Lecturer:
Course Website: http://www.cs.uni-potsdam.de/ti/lehre/04-WS-Theorie-I/index.html

General Information

• Weekly Hours: 4
• Credits: 6
• Graded: yes
• Enrolment Deadline: 01.01.1970
• Teaching Form:
• Enrolment Type: Compulsory Elective Module

Programs

• IT-Systems Engineering BA

Description

Die Theoretische Informatik beschäftigt sich mit den grundlegenden Fragestellungen der Informatik. Hierzu werden Computer- und Automatenmodelle idealisiert und mathematisch untersucht.

Die Automatentheorie und die Theorie der formalen Sprachen ist grundlegend für die Entwicklung von Programmiersprachen und Compilern. Sie untersucht, mit welchen Techniken welche Arten von Sprachen effizient analysiert werden können.

 

Die Berechenbarkeitstheorie (Thema des zweiten Semesters) befasst sich mit den prinzipiellen Grenzen des Berechenbaren und der Relation zwischen verschiedenen Computer- und Programmiermodellen.

 

Die Komplexitätstheorie (Thema des zweiten Semesters) untersucht Effizienz von Algorithmen im Hinblick auf Platz- und Zeitbedarf und kümmert sich insbesondere um die Frage, wie effizient man bestimmte Probleme lösen kann.

 

Gliederung

• Einführung in die Theoretische Informatik
  • Automaten, Sprachen und Berechenbarkeit
  • Informale und formale Beweisführung
• Endliche Automaten und Reguläre Sprachen
  • Deterministische und nichtdeterministische endliche Automaten
  • Reguläre Ausdrücke und Typ-3 Grammatiken
  • Lexikalische Analyse
  • Charakterisierung und Abschlusseigenschaften regulärer Sprachen
  • Minimierung von Automaten
  • Grenzen regulärer Sprachen (Pumping Lemma)
• Kontextfreie Sprachen
  • Kontextfreie Grammatiken
  • Syntaxanalyse und Semantik
  • Pushdown Automaten
  • Charakterisierung und Abschlusseigenschaften kontextfreier Sprachen
  • Grenzen und Normalformen kontextfreier Sprachen

Literature

Sehr empfehlenswert:

• J. Hopcroft, R. Motwani, J. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie., Pearson 2002 Dieses Buch bildet den Leittext für diese Veranstaltung.
• Folien der Vorlesung.
• M. Sipser: Introduction to the Theory of Computation. PWS 1997
• A. Asteroth, C. Baier: Theoretische Informatik. Pearson 2002
• Mitschriften von Kommilitonen früherer Semester liegen auf dem Server des Lehrgebiets "Didaktik der Informatik" bereit: Theorie I Theorie II

 

Auch lesenswert:

• I. Wegener: Theoretische Informatik. Teubner Verlag 1993
• U. Schöning: Theoretische Informatik - kurzgefaßt. Spektrum-Verlag 1994
• K. Erk, L. Priese: Theoretische Informatik. Springer Verlag 2000
• H. Lewis, C. Papadimitriou: Elements of the Theory of Computation. Prentice-Hall 1998

 

Lesenswertes zur Arbeitsethik

• Code of Academic Integrity (Cornell University)
• Aufdeckung von Plagiaten (FHTW Berlin)
• Missverständnisse zum Urheberrecht

Learning

In der Vorlesung (wöchentlich Donnerstags 11:00-12:30, HPI HS1) werden die zentralen Konzepte der theoretischen Informatik vorgestellt und an Beispielen illustriert. Die in der Vorlesung verwendeten Folien werden auf den Servern des Lehrgebiets (wenn möglich im Voraus) bereitgestellt.

Die Übungen (wöchentlich 2 Stunden, in Gruppen) dienen der Vertiefung und Anwendung der in der Vorlesung vorgestellten Themen. Dies geschieht durch Bearbeitung von ad hoc Übungsaufgaben unter Betreuung von Tutoren, einem 5-Minuten "Quiz" zur Überprüfung eigener Kenntnisse, durch Diskussion von Fragen zur Vorlesung, und durch die Korrektur von Lösungen zu Hausaufgaben. Die Übungsblätter werden wöchentlich herausgegeben.

Examination

Zur Leistungsbewertung wird ausschließlich eine abschließende Klausur herangezogen. Die Klausur findet voraussichtlich in der letzten Vorlesungswoche statt.

Eine Nachklausur wird angeboten für Studenten, die in der ersten Klausur durchgefallen sind. In dieser Nachklausur kann maximal die Note 4.0 erreicht werden

Als Mittel der Selbstkontrolle wird eine Probeklausur angeboten. Das Ergebnis der Probeklausur geht nicht in die Endnote ein. Die Teilnahme an der Probeklausur ist Voraussetzung für die Zulassung zur Klausur.

 

Zur Klausur wird zugelassen, wer an der Probeklausur teilnimmt und mindestens 50% der Punkte in den Hausaufgaben erreicht.

 

Hausaufgaben werden wöchentlich auf den Servern des Lehrgebiets bereitgestellt. Gruppen von bis zu 3 Studenten dürfen eine gemeinsame Lösung zur Korrektur einreichen.

Dates

Vorlesung (wöchentlich Donnerstags 11:00-12:30, HPI HS1)

Übungen (wöchentlich 2 Stunden, in Gruppen)

Aktuelle Informationen sind auf den

Webseiten der Professur Theoretische Informatik

zu finden

Zurück