Hasso-Plattner-Institut
Hasso-Plattner-Institut
  
Login
  • de
 

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

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.

  •  

     

Allgemeine Information

  • Semesterwochenstunden : 4
  • ECTS : 6
  • Benotet : Ja
  • Einschreibefrist : 01.01.1970
  • Programm : IT-Systems Engineering BA
  • Lehrform :
  • Belegungsart : Wahl

Zurück