Zur Hauptnavigation Zum Inhaltsbereich Zur Suche Zum Seitenfu├č


Vorlesung: Grundzüge der Informatik A3

Deutsche Version. This page is available in German only. Cette page n'existe qu'en Allemand. Ésta página sólo existe en Alemán.


Veranstaltungsnummer: 18.005 / 18.006 (Übungen) / 18.903 /Tutorium)

Titel: Grundzüge der Informatik A3

Veranstalter: Rüdiger Valk

Ort und Zeit:

Di 10-12 Audi I und Fr 10-12 Audi II.
Dazu gehören 2-std. Übungen n.V. (10 Gruppen) und ein Tutorium (4 Gruppen).

Lernziel:

Kennenlernen und Vertrautwerden mit grundlegenden formalen Konzepten und Methoden, die für fast alle Teilgebiete der Informatik wichtig sind. Erwerben und Einüben der Standardhilfsmittel für Beschreibung, Analyse, Entwurf und Bewertung von Problemen und deren Lösung.

Inhalt:

Denkmethoden und ihre Formalisierung
Formalisierung von Sachverhalten, Problemen, Zusammenhängen, Methoden zur Spezifikation von Algorithmen, Regeln des vernünftigen Schlußfolgerns, Aussagenlogik und Prädikatenlogik.
Probleme der Textverarbeitung
Formale Beschreibung von Texten, Erzeugung, Änderung und Prüfung der syntaktischen Korrektheit, Einführung in Syntaxanalyse und Compilerbau, Kontextfreie Grammatik, Einführung in die Theorie formaler Sprachen, speziell Chomsky-Hierarchie.
Automaten, Maschinen, Petrinetze
Methoden zur Erkennung und Übersetzung formaler Sprachen: Endliche Automaten, Kellerautomaten und Turingmaschinen. Klassifikation der formalen Sprachen durch Automaten. Vergleich mit Chomsky-Grammatiken. Deterministische, nichtdeterministische Arbeitsweise, Petrinetze. Aufwand, Komplexität, Effizienz Bewertung von Algorithmen und Verfahren hinsichtlich der Zeit und des Platzes, den sie bei ihrer Ausführung im ungünstigsten Fall benötigen.
Absolute Grenzen (prinzipiell nicht mögliche Verfahren) und durch den
Aufwand bestimmte Grenzen. Einführung in die Komplexitätstheorie. Rekursive Funktionen, Entscheidbarkeit und Berechenbarkeit Algorithmusbegriff, Turing'sche These, aufzählbare versus entscheidbare Mengen und ihr Zusammenhang zu Turingmaschinen bzw. Programmiersprachen. Primitiv rekursive Funktionen im Vergleich dazu. Unentscheidbare Probleme: Halteproblem bei Turingmaschinen.

Voraussetzung: Teilnahme an den Übungen

Stellung im Studienplan: Für 3. Semester, Stoff für die Vordiplomprüfung "Informatik".

Literatur:

Bemerkungen:

Für LehrerInnen / NebenfächlerInnen mit mathematischem Interesse geeignet.

Letzte Änderung: 17:40 19.05.2011
Impressum