Theoretische Grundlagen der Informatik I (Wintersemester 2003/2004)

Lecturer:

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

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

Requirements

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.

Literature

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

Examination

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

Dates

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

Zurück