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

Theoretische Grundlagen der Informatik I (Wintersemester 2003/2004)

Dozent:

Beschreibung

Der zweisemestrige

Kurs "Theoretische Informatik" liefert eine Einführung in die grundlegenden

Begriffe, Methoden und Ergebnisse der Theoretischen Informatik unter besonderer

Berücksichtigung der Erfordernisse der Softwaresystemtechnik. Von den

traditionellen Gebieten der Theoretischen Informatik werden besonders diejenigen

schwerpunktmäßig behandelt, die theoretisch die Grenzen des Programmierbaren

abstecken und somit die Notwendigkeit der strukturierten Beschreibung großer,

komplexer Systeme und der Kommunikation zwischen den Entwicklern von

Teilsystemen beweisen. Dazu gehörten:

     

  • Berechnungstheorie
    Algorithmen,

    Turing-Maschinen, Register-Maschinen, Rekursive Funktionen, Berechenbarkeit,

    Entscheidbarkeit, Unentscheidbarkeit, Aufzählbarkeit

  • Komplexitätstheorie
    O- und

    Omega-Notation, Zeit- und Platz-Komplexität, Untere Schranken, Determinismus

    versus Nichtdeterminismus, polynomiale Berechenbarkeit, NL- und

    NP-vollständige Probleme

Die traditionell in der Vorlesung

"Theoretische Informatik" vermittelten Begriffsbildungen der Theorie der

formalen Sprachen wie Reguläre Sprachen, kontextfreie und kontextsensitive

Sprachen, Chomsky-Hierarchie, Grundlagen der Programmiersprachen, Endliche

Automaten, Pushdown-Automaten, Akzeptoren, Syntaxanalyse waren z.T. bereits

Gegenstand der schon in den ersten beiden Semestern laufenden Vorlesung "Systeme

und ihre Modellierung". Sie werden also nur verkürzt in die "Theoretische

Informatik" aufgenommen.
Statt dessen werden theoretische Problemstellungen

im Umkreis der Spezifikation und des Entwurfs großer Systeme in die Vorlesung

aufgenommen:

 

     

  • Wintersemester 2003/2004

       

    • Algebraische und konstruktive Spezifikationen

    • Theoretische Prinzipien der Gestaltung von Softwarearchitekturen

    • Komplexität: Untere Schranken

  • Sommersemester 2004

       

    • Theoretische Grundlagen der imperativen und objektorientierten

      Programmierung

    • Grenzen der Berechenbarkeit

    • Komplexitätstheoretische Grenzen: Zeit- und Platzbeschränkungen von

      Algorithmen

    • Grenzen der Korrektheit von Programmen: Validierung und Verifizierung

 

 

Behandelte Stoffgebiete

Die in der Vorlesung verwendeten Folien werden im

Internet veröffentlicht.

     

  • Einführung

       

    • Motivation und Charakterisierung des Gegenstandes

    • Überblick über den in den beiden Semestern vermittelten Stoff

    • Beispiel einer durch Computer nicht berechenbaren Funktion

    • Wiederholung mathematischer Grundbegriffe

  • Algebraische Spezifikationen I

       

       

    • Motivation: Versuch einer Beschreibung der Semantik von Teilen der

      Windows Interface Language (WIL) der Firma Wilson

    • Signaturen und Algebren

    • Beispiele aus der Mathematik: Halbgruppen, Monoide, Gruppen,

      Vektorräume; ein praktisches Beispiel: Spezifikation von Teilen der Windows

      Interface Language (WIL) der Firma Wilson

    • Terme und Gleichungen, algebraische Spezifikationen

    • Zerlegung einer algebraischen Spezifikation in Typspezifikationen,

  • Die Spezifikation der natürlichen Zahlen

       

    • Das Peanosche Axiomensystem

    • Das Lawveresche Axiom

    • Der Dedekindsche Rekursionssatz und seine Anwendungen; Primitiv

      rekursive Funktionen

    • Die Äquivalenz des Peanoschen Axiomensystems mit dem Lawvereschen Axiom;

      Charakterisierung der natürlichen Zahlen als initiale Algebra

     

  • Algebraische Spezifikationen II

       

    • Homomorphismen, Isomorphismen, Kongruenzrelationen in mehrsortigen

      Algebren, Faktoralgebren, Noetherscher Homomorphiesatz

    • Die Kategorie der Algebren über einer Signatur; die Termalgebra als

      iniitale Algebra; freie Algebren

    • Initiale Algebra-Semantik: Die Kategorie der Algebren über einer

      Spezifikation, die initiale Algebra, Varietäten

    • Beispiele: Ganze Zahlen, Zeichenketten, Listen und Stacks, Bäume

      Korrektheit einer Spezifikation

  • Parametrisierte Spezifikationen und Moduln

       

    • Schnittstellen: Das Konzept des Imports, Exports und der Common

      Parameters einer (nicht notwendigerweise algebraischen) Spezifikation

    • Kategorien, Funktoren, Freie Konstruktionen; Spezifikationsmorphismen

      und dadurch definierte Funktoren

    • Parametrisierte Spezifikationen und lose Funktorsemantik

    • Freie Funktorsemantik

     

  • Daten und ihre Modellierung

       

    • Mathematische Grundbegriffe aus der Graphentheorie, Graphen und

      Hypergraphen als Hilfsmittel der Modellierung

    • Konstruktoren als Datenbausteine, Selektoren

    • syntaktische Beschreibung von natürlichen Zahlen, ganzen Zahlen,

      rationalen Zahlen, Listen, doppelt verkettete Listen, zyklische Listen,

      Bäumen

    • Architekturbeschreibungen Grenzen der Repräsentation: doppelt verkettete

      Listen, zyklische Listen, FIFO-Schlangen;

  • Ersetzungssysteme

       

    • Termersetzungssysteme, Graphersetzungssysteme

    • Konfluenz und Termination, Noethersche Ersetzungssysteme

    • Korrektheit, Vollständigkeit, Church-Rosser-Eigenschaft

    • Algebraische Spezifikationen und Termersetzungssysteme

     

  • Konstruktive Spezifikationen

       

    • Begriff der konstruktiven Spezifikation

    • Definition von Operationen; konstruktive Spezifikationen und funktionale

      Programme

    • konstruktive Spezifikationen und Graphersetzungssysteme; die

      Konstruktoralgebra

    • Initiale Algebra und Konstruktoralgebra

    • Die Übersetzung einer konstruktiven Spezifikation in ein

      objektorientiertes Programm,

  • Konzepte von Spezifikationssprachen

       

    • Basisspezifikationen und ihre Semantik, Initiale Semantik und

      Konstruktorsemantik

    • Parametrisierte Spezifikationen und lose, bzw. freie Funktorsemantik

    • Spezifikationen mit formalen Parametern - Schablonen (Templates)

    • Der Namensraum eines Moduls

    • Konstruktion neuer Datentypen und Templates, interne und externe

      Konstruktionen

    • Die Spezifikationssprache Pi-: der Pi-Modul-Syntaxchecker und -Compiler,

      die Möglichkeit separater Compilation und der Compilation unvollständiger

      Komponenten

     

  • Konstruktionstechniken für Architekturen

       

    • Der Komponentenbegriff

    • Hierarchische Graphen, Konstruktion neuer Komponenten durch das

      Zusammenfügen bereits vorhandener Komponenten

    • Ersetzung von Parametern oder Importen durch exportierte Spezifikationen

      anderer Komponenten

    • Konfigurationen, Inkarnationen, Umbenennungen, Aktualisierungen

    • Der Pi-Konfigurationscompiler

    • Die Notwendigkeit der Kommunikation bei der Analyse und Synthese großer

      Softwaresysteme

  • Spezifikationen und Namensräume

       

    • Grenzen der Beschreibung großer statischer Systeme und ihre Überwindung

      durch Zerlegung und Hierarchisierung

    • Begriffsanalyse, extensional (Beschreibung des Begriffsumfangs durch

      Instanzen) und intensional (Beschreibung des Begriffsinhalts bzw. des

      Konzeptes, das diesem Begriff zugunde liegt, in verbaler Form); Erkennung

      und Definition relevanter Begriffe

    • Gliederung der Begriffe und bildliche Gruppierung hinsichtlich des

      Enthaltenseins (Subalternation), der Identität, der Überschneidung

      (Interferenz) und des Disjunktseins

    • Namensräume: Namensbegriff, Bindung, Gültigkeit, Sichtbarkeit;

      Hierarchien, stufenweise Abstraktion;

     

  • Modulspezifikationen

       

    • Die Grundbestandteile eines Moduls: Export, Import, Common Parameters,

      Body

    • Typspezifikation, Operationsspezifikation

    • Formaler und aktueller Import; Modularisierung: Spezifikation im Großen

      durch Zerlegung in separate Komponenten mit wohldefinierten formalen

      Schnittstellen

    • Prinzipien der modularen Programmierung: Kapselung, Geheimhaltung,

      Prinzip der Übersichtlichkeit und Verständlichkeit einzelner Komponenten

      ohne die Kenntnis anderer Komponenten

    • Modularisierung und ihre Realisierung in unterschiedlichen

      Sprachkonzepten: Pi-, Z, Java

  • Komplexität - Untere Schranken

       

    • Informationssysteme und Klassifikationsprobleme

    • Abschätzung der Komplexitäten von Algorithmen

    • Komplexität im schlechtesten Fall; Komplexität im Mittel

    • Untere Schranken der Komplexitäten ausgewählter Algorithmen

       

Voraussetzungen

Für die Veranstaltung sind Kenntnisse nützlich, die

in einer einsemestrigen Vorlesung "Diskrete mathematische Strukturen" vermittelt

werden (Elemente der Mengentheorie, abzählbare, überabzählbare Mengen,

Relationen, Relationenkalkül, Funktionen als Spezialfälle von Relationen,

Grundlagen der Universellen Algebra und der Kategorietheorie, teilweise

geordnete Mengen, Graphen). In der Vorlesung werden diese Grundkenntnisse noch

einmal wiederholt.

Literatur

Allgemeine Grundlagen

     

  • A. V. Aho, J.D. Ullman, Informatik, Datenstrukturen und Konzepte der

    Abstraktion (Intern Thomson Publ. 1996).

  • A. V. Aho, J.E.Hopcroft, J.D. Ullman, Data Structures and Algorithms

    (Addison-Weley 1983).

Berechnungstheorie und Komplexität

(vorwiegend für das zweite Semester)
Ergänzungen aus der Theorie der formalen

Sprachen und endlichen Automaten

     

  • N. Blum, Theoretische Informatik: Eine anwendungsorientierte Einführung

    (München, Wien, Oldenburg, 1998).

  • J. E. Hopcroft, R. Motvani, J. D. Ullman, Introduction to automata theory,

    languages and computation (Addison-Wesley Boston, San Francisco, New York,

    London, Toronto, Sydney, Tokyo, Singapore, Madrid, Mexico City, Munich, Paris,

    Cape Town, Hong Kong, Montreal, 2001).

  • K. Erk, L. Priese, Theoretische Informatik: Eine umfassende Einführung

    (Springer-Verlag, Berlin, Heidelberg, New York, Barcelona, Hongkong, London,

    Mailand, Paris, Singapur, Tokyo 2000).

  • F. Stetter, Grundbegriffe der Theoretischen Informatik (Springer-Verlag,

    Berlin, Heidelberg, New York, London, Paris, Tokyo 1988).

  • U. Schöning, Theoretische Informatik kurz gefasst (BI-Wiss.-Verlag,

    Mannheim, Leipzig, Wien, Zürich, 1992).

  • K. W. Wagner, Einführung in die Theoretische Informatik (Springer-Verlag,

    Berlin, Heidelberg, New York, London, Paris, Tokyo 1991).

  • I. Wegener, Theoretische Informatik: Eine algorithmenorientierte

    Einführung (Teubner, Stuttgart 1993).

  • A. Asteroth, Ch. Baier Theoretische Informatik, Eine Einführung in

    Berechenbarkeit, Komplexität und formale Sprachen mit 101 Beispielen (Pearson

    Studium, München 2002)

 

Spezifikation

     

  • H. Ehrig, B. Mahr, Fundamentals of Algebraic Specifications I

    (Springer-Verlag Berlin Heidelberg New York Tokyo 1985).

  • J. Loeckx, H.-D. Ehrich, M. Wolf Specification of Abstract Data Types

    (John Wiley & Sons Ltd and B.G. Teubner 1996).

  • J. M. Spivey, The Z notation: a reference manual (Prentice Hall London,

    Toronto, Sydney, Tokyo, Singapore 1992).

Graph-Ersetzung

     

  • H. Ehrig, G. Engels, H.-J. Kreowski, G. Rozenberg (Eds.) Handbook of Graph

    Grammars and Computing by Graph Transformations, Vol. 2 (Wold Scientific

    Singapore, New Jersey, London, HongKong 1997)

Funktionale Programmierung

 

     

  • R. Bird, Ph. Wadler Introduction to Functional Programming, (Prentice Hall

    1988).

  • P. Hudak, J. H. Fasel, A Gentle Introduction to Haskell, ACM SIGPLAN

    NOTICES 27 (5) (May 1992).

  • P. Hudak, S. Peyton Jones, P. Wadler, Report on the Programming Language

    Haskell: A non-strict, purely functional language, ACM SIGPLAN NOTICES

    27 (5) (May 1992).

Semantik

     

  • D. A. Schmidt Denotational Semantics - A Methodology for Language

    Development (Wm. C. Brown Publishers Dubuque, Iowa, 1986).

Leistungserfassung

     

  • Für die Belegung der Vorlesung sind 6 Belegungspunkte zu entrichten. Ein

    erfolgreicher Abschluss wird mit 6 benoteten Leistungspunkten bestätigt. Die

    Belegungsfrist endet am 29. Oktober 2003.

  • In der Vorlesung werden mittwochs Übungsaufgaben gestellt und erläutert.

  • Eine Woche später werden die Aufgaben in der Vorlesung besprochen. Darüber

    hinaus werden die Lösungen von Dr. Wilhelm im Netz veröffentlicht. Die

    Übungsaufgaben bilden die Basis für die Klausur.

  • Im Verlaufe des Semesters (im Dezember und am Ende des Semesters) werden

    zwei Klausuren geschrieben, die jeweils 90 Minuten dauern. Der Modus der

    Duchführung der Klausuren und der erwartete Wissensumfang werden eine Woche

    vorher in der Vorlesung mitgeteilt.

  • Für alle Klausuraufgaben wird die Zahl der erreichbaren Punkte vorgegeben.

    Die Sollpunktzahl einer Klausur wird auf der Basis der Gesamtzahl der von den

    besten Studenten erreichten Punkte definiert. Der Quotient aus der Gesamtzahl

    der erreichten Punkte beider Klausuren und der Summe der beiden

    Sollpunktzahlen ist Basis für die (algorithmisch definierte) Festlegung der

    gemäß §§ 6 und 9 der Prüfungsordnung erforderlichen Benotungsinformation der

    Leistungspunkte.

  • Ist die erhaltene Note schlechter als 4,0, wird kein Leistungspunkt

    vergeben.

Termine

Vorlesung: Mo 15.15-16.45 Uhr, HPI HS2
Vorlesung

und Übung (gemeinsam mit Dr. O. Wilhelm): Mi 9.15-10.45 Uhr, HPI HS3

Allgemeine Information

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

Zurück