MIN-Fakultät
Department Informatik
UHH > MIN > Informatik > Studium > Bachelor/Master-Studiengang > Modul Formale Grundlagen der Informatik I Web-Mail Suche Seitenende

Modulbeschreibung Formale Grundlagen der Informatik I (FGI I)

 

Bachelor-Pflichtmodul: Formale Grundlagen der Informatik I (FGI I)

1. Modulkennung
IP8

2. Studiengang
Bachelorstudiengang Informatik

3. Modulbezeichnung
Formale Grundlagen der Informatik I (FGI I), engl.: Theoretical Foundations of Computing I

4. Modul-Verantwortliche(r)
Jantzen, Valk

5. Veranstalter(in)/Dozent(in)
Jantzen, Valk

6. Sprache
Deutsch mit deutsch- und englischsprachigem Lehrmaterial

7. Motivation, Bedeutung für / Stellung im Gesamtprogramm
Die Modellierung und Analyse von Problemen sowie die Beurteilung gefundener Lösungen sind grundlegende Bestandteile der Informatik. Das Modul Grundlagen der Theoretischen Informatik beschäftigt sich auf mathematischer Basis mit Abstraktionen, Modellbildungen und Verfahren zur Beschreibung und Analyse von Algorithmen und Prozessen. Formale Methoden spielen in der Informatik die Rolle eines „Denkzeugs“, mit dem der (abstrakte) Kern einer Sache knapp und präzise beschrieben werden kann. Wesentliche Hilfsmittel zur Modellierung von Problemen sind Kalküle, formale Sprachen, Grammatiken und Automaten. Dadurch werden Modelle und Problemlösungen einer mathematischen Analyse zugänglich.
Die Logik bildet die Grundlage für eine formale Semantik von sprachlichen Beschreibungen und Anweisungen in Programmier-, Spezifikations- und Repräsentationssprachen.
Das Gebiet Automatentheorie behandelt einfache mathematische Modelle, die dem Computer und Algorithmen zu Grunde liegen. In dem Teilgebiet Formale Sprachen wird der prinzipielle, strukturelle Aufbau von Programmier- und Spezifikationssprachen untersucht, welche wichtige Hilfsmittel zur Modellierung und exakten Beschreibung von Problemen sind.
Die Theorie der Berechenbarkeit untersucht die Abgrenzung zwischen effektiv Ausführbarem und prinzipiell niemals Möglichem, wodurch sich für letztere eine Behandlung auf Computern nur nach angemessener Modifikation anbieten würde.
Die Komplexitätstheorie fragt danach, welchen rechnerischen Aufwand die Lösung gewisser Probleme erfordert und hilft so bei deren Beurteilung.
Die in dieser Veranstaltung beschriebenen Techniken finden Anwendungen in nahezu allen Modulen der Bachelor- und Masterstudiengänge. Auf mathematische Begriffe und Modelle aus dem Pflichtmodul Diskrete Mathematik (DM) wird zurückgegriffen und besonderer Wert wird gelegt auf die Berücksichtigung der Bezüge zu Anwendungen.  Der Ausbau dieser Konzepte, insbesondere im Pflichtmodul Algorithmen und Datenstrukturen I (AD I) sowie den Wahlpflichtmodulen Modellierung und Analyse paralleler und verteilter Systeme (ModPVS) und Logik, formale Sprachen und Semantik (LoFoS) wird vorbereitet.

8. Lernziele/Kompetenzen

8.1 Passung Leitbild

  • Vermittlung von Fähigkeiten zum Erkennen von Strukturen in Problembereichen und zur Analyse von Zusammenhängen,
  • Bewertung von Sachverhalten und deren Einordnung in auch fachübergreifende Zusammenhänge.
  • Einschätzung von Grenzen und Klassifikation der prinzipiellen Möglichkeiten zur Bewältigung von Komplexität mit Hilfe von theoretisch fundierten Aussagen.

8.2 Grundlagen-/Faktenwissen

  • Erlernen der formalen Konzepte der Modellierung auf Basis von Kalkülen und Grammatiken
  • Verständnis der Grundkonzepte der vermittelten Kalküle,
  • Kennenlernen und Vertiefen von Definitionsprinzipien und Beweistechniken,
  • Determinismus und Nicht-Determinismus als fundamentale Begriffe verstehen lernen.

8.3 Methodenwissen

  • Einsatz von Methoden der diskreten Mathematik für informatische Probleme,
  • Anwendung von Definitionsprinzipien und Beweistechniken in unterschiedlichen Bereichen und an typischen Beispielen,
  • Methoden zu Korrektheitsbeweisen von Modellen und Algorithmen,
  • Erkennen der Gemeinsamkeiten von Strukturen und Beherrschung des konzeptionellen Kerns der Kalküle.

8.4 Transferkompetenz

  • Fähigkeit zum Entwickeln neuer Definitionen sowie zur exakten Beschreibung von neuen Spezifikationen in allen Bereichen der Informatik und deren Anwendungen,
  • Erkennen von Strukturen in informatischen Problemstellungen und Übertragen der mathematischen Methoden zu deren präzisen Modellierung,
  • Anwendung der vermittelten Techniken zur Formulierung und Analyse der Algorithmen.

8.5 Normativ-Bewertende Kompetenz

  • Den praktischen Wert von präzisen Beschreibungen erkennen,
  • Beurteilung der Qualität von Algorithmen und computergeeigneten Verfahren im Hinblick auf Korrektheit, Effizienz und Vollständigkeit,
  • Erkennen der grundlegenden Beschränktheit gegebener automatisierter Verfahren oder der Nichtexistenz von gewünschten Algorithmen.

8.6 ABK/BOK/Schlüsselqualifikation

  • Kooperations- und Teamfähigkeit in den Präsenzübungen,
  • Strategien des Wissenserwerbs: Kombination aus Vorlesung, Vor- und Nachbereitung am Vorlesungsmaterial, Präsenzübungen mit betreuter Gruppenarbeit und eigenständiges Lösen von Übungsaufgaben
  • Kreatives Spezifizieren am Beispiel der Entwicklung von Grammatiken, Automaten und Algorithmen

9. Lehrveranstaltungen

  • 4 SWS Vorlesung Formale Grundlagen der Informatik (Plenum)
  • 2 SWS Übungen Formale Grundlagen der Informatik (Präsenzübungen, Kleingruppen)

10. Inhalt

10.1 Grundlagen der Logik:

  • Kalkülbegriff
  • Einführung in die Aussagenlogik: wohlgeformte Ausdrücke, Wahrheitswerte, Wahrheitstafeln, Belegungsfunktion, Normalformen, Literale und Klauseln,
  • Grundkonzepte der Semantik: Allgemeingültigkeit, Unerfüllbarkeit, Erfüllbarkeit und Folgerung,
  • Beweistheorie und Ableitungssysteme für die Aussagenlogik: Schlussregeln, modus ponens, Resolution in der Aussagenlogik
  • Syntax der Prädikatenlogik erster Stufe: Charakterisierung wohlgeformter Ausdrücke, Quantoren und Quantorenskopus, freie und gebundene Variablen, geschlossene Formeln
  • Semantik der Prädikatenlogik: Modell, Interpretation, Allgemeingültigkeit, Unerfüllbarkeit, Erfüllbarkeit, Folgerung

10.2 Grundlagen der Formalen Sprachen und der Automatentheorie:

  • Anwendungen von Beweismethoden: Schubfachprinzip, Beweis durch Gegenbeispiel, indirekter Beweis, Induktion, Diagonalisierung, strukturelle Induktion
  • Modelle einfacher Automaten: endlicher Automat, endlicher Transduktor, Kellerautomat, Determinismus versus Nichtdeterminismus
  • Definitions- und Spezifikationsmethoden: Induktive und rekursive Definitionen über Mengen, Relationen, Funktionen, formale Sprachen, Operatoren, transitive Hüllen, Graphen und Bäume,
  • Automaten vs. Grammatiken: endliche Automaten, Determinismus vs. Nichtdeterminismus, reguläre Ausdrücke, Kellerautomaten, kontextfreie Grammatiken, Ableitungsbegriff, Ableitungs- und Syntaxbaum, Eigenschaften und Grenzen der Ausdrucksfähigkeit, Chomsky-Hierarchie
  • Grundlagen kontextfreier Syntaxanalyse: Syntaxanalyse für deterministische und beliebige kontextfreie Grammatiken, top-down und bottom-up Verfahren
  • Höhere Grammatiken: Chomsky Typ-0 und Typ-1 Grammatiken, Normalformen,
  • Modelle Universeller Automaten: Turing-Maschine, Registermaschine Zusammenhang mit Typ-0 und Typ-1 Grammatiken

10.3 Grundlagen von Berechenbarkeit und Komplexität:

  • Entscheidbarkeit und Berechenbarkeit: primitiv rekursive und allgemein-rekursive Funktionen, Register- und Turing-Maschine als allgemeine, formale und besonders kompakte Algorithmusdefinition, Halteproblem und andere unentscheidbare Fragen
  • Konkrete Komplexitätstheorie: Landausche Notation, einfache Algorithmen aus den vorgestellten Bereichen der Automatentheorie,
  • Strukturelle Komplexitätstheorie: Darstellung von Problemen als Mengen, Zeit- und Platzkomplexitätsklassen, Beschleunigungs- und Kompressions-Sätze, Reduktionsbegriff, NP-Vollständigkeit

11. Bezüge zu anderen Modulen

  • Innerhalb des Studienganges:
    Im Rahmen der Pflichtmodule greift das Modul auf das Modul Diskrete Mathematik zurück, unterstützt Teile der linearen Algebra und ist grundlegend für das  Modul Algorithmen und Datenstrukturen. Es legt darüber hinaus die Grundlagen für das Modul Formale Grundlagen der Informatik II und das Wahlpflichtmodul Grundlagen der Wissensverarbeitung.
  • Im konsekutiven Masterstudiengang: Das Modul schafft Grundlagen für das Theorie-Pflichtmodul sowie die Wahlpflichtmodule Datenbanken und Informationssysteme, Algorithmisches Lernen und Algorithmik.
  • In anderen Studiengängen:
    Dieses Modul eignet sich als Nebenfachmodul sowie als Bestandteil von Wirtschafts- und Bioinformatik Studiengängen. Darüber hinaus ist ein Einbringen als Wahlmodul naturwissenschaftlicher Studiengänge denkbar.

12. Modulvoraussetzungen

  • Verbindlich: keine
  • Empfohlen: Diskrete Mathematik, Softwareentwicklung I

13. Semester, Studienjahr /-phase
Studienabschnitt: 1
Referenzsemester: 2

14. Prüfungsleistungen
Die Zulassung zur Modulprüfung setzt die regelmäßige und erfolgreiche Teilnahme an den Übungen voraus; die Teilnahme gilt grundsätzlich als erfolgreich, wenn alle Aufgaben bearbeitet und mindestens 50% richtig gelöst wurden; im Falle abweichender Kriterien müssen diese zu Beginn der Veranstaltung bekannt gemacht werden.
Gemeinsame Modulprüfung für alle Lehrveranstaltungen des Moduls; in der Regel schriftlich (Klausur) und in deutscher Sprache; bei Modus-Abweichung Bekanntgabe zu Beginn der Veranstaltung.

15. Bewertung
Gesamt: 9 Leistungspunkte
(Formale Grundlagen der Informatik I: 5 Leistungspunkte,
Übungen zu Formale Grundlagen der Informatik I: 4 Leistungspunkte)

16. Periodizität
Sommersemester, jährlich, Dauer: 1 Semester

17. Methodische Aufbereitung und Medienformen

  • Vorlesung mit Beamer, Overhead und Tafel,
  • Vorlesungs- und Übungsmaterial wird online zur Verfügung gestellt,
  • Erwartete Aktivitäten der Studierenden: selbständiges Bearbeiten von Übungsaufgaben, aktive Mitarbeit in den Präsenzübungen

18. Literatur

18.1 Grundlage zum Logik Teil

  • Wolfgang Rautenberg: Einführung in die Mathematische Logik, vieweg(2002)
  • John Kelly: Logik im Klartext, Pearson Studium, Prentice Hall (2003)*
  • Mordechai Ben-Ari: Mathematical Logic for Computer Science, Springer (2001)

18.2 Grundlage zu Automaten und Formale Sprachen

  • Alexander Asteroth / Christel Baier: Theoretische Informatik, Pearson Studium (2002)
  • John E. Hopcroft / Rajeev Motwani / Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Pearson Studium (2002)
  • Gottfried Vossen / Kurt-Ullrich Witt: Grundkurs Theoretische Informatik, Vieweg (2002)
  • Dexter C. Kozen: Automata and Computability, Springer (2000),
  • John E. Hopcroft / Rajeev Motwani / Jeffrey D. Ullman: Introduction to Automata Theory,  Languages and Computation (second edition), Addison Wesley Longman (2001)