Theoretische Grundlagen der Informatik II (HPI + ifi) (Sommersemester 2005)
Dozent:
Website zum Kurs:
http://www.cs.uni-potsdam.de/ti/lehre/05-Theorie-II/index.html">Webseiten
Allgemeine Information
- Semesterwochenstunden: 4
- ECTS: 6
- Benotet:
Ja
- Einschreibefrist: 01.01.1970
- Lehrform:
- Belegungsart: Wahlpflichtmodul
Studiengänge
- IT-Systems Engineering BA
Beschreibung
p>
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 (Thema des ersten Semesters)
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 befasst sich mit den prinzipiellen Grenzen des
Berechenbaren und der Relation zwischen verschiedenen
Computer- und Programmiermodellen.
Die Komplexitätstheorie 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
- Berechenbarkeitstheorie
- Turingmaschinen
- Rekursive Funktionen
- Lambda-Kalkü und arithmetische Repräsentierbarkeit
- Die Churchsche These
- Berechenbarkeit, Aufzählbarkeit und Entscheidbarkeit
- Unlösbare Probleme
- Komplexitätstheorie
- Konkrete Komplexitätsanalyse
- Komplexitätsklassen
- Handhabbarkeit: das P - NP Problem
- NP-vollständige Problem
- Jenseits von NP-vollständigkeit
- Pseudopolynomielle und approximierende Algorithmen
- Probalistische Lösung nichthandhabbarer Probleme
Literatur
Sehr empfehlenswert:
-
J. Hopcroft, R. Motwani, J. Ullman:
Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie.,
Pearson
2002
- Folien der Vorlesung.
-
M. Sipser:
Introduction to the Theory of Computation.
PWS
1997
-
A. Asteroth, C. Baier:
Theoretische Informatik.
Pearson
2002
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
Programme
Lern- und Lehrformen
- In der Vorlesung (wöchentlich Mittwochs 17:00-18: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 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 <a
href="http://www.cs.uni-potsdam.de/ti/lehre/05-Theorie-II/uebungen.html"> Übungsblätter werden wöchentlich
herausgegeben.
- Das Tutorium (zweiwöchentlich Dienstags 9:25-10:45,
HPI HS2) ist eine freiwillige Zusatzveranstaltung
die zur Besprechung allgemeiner Fragen vorgesehen ist.
- Im Kontrast zum Tutorium dienen die Sprechstunden der
persönlichen Beratung. Das Ziel ist dabei vor allem
Optimierung des individuellen Lernstils und die Klärung von
spezifischen Schwierigkeiten.
Leistungserfassung
-
Zur Leistungsbewertung wird ausschließlich eine
abschließende Klausur herangezogen.
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
-
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.
Zurück
