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

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 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

 

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

 

  • Zum Lesen und Drucken der Folien und der Übungsblätter kann der kostenlose Adobe Acrobat Reader verwendet werden.

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