MODULBESCHREIBUNG

Mathematische Grundlagen der Informatik 2

Kurzzeichen:
M_Math2I
Durchführungszeitraum:
SS/06-FS/14
ECTS-Punkte:
4
Lernziele:
  • Grundlagen zur Verarbeitung formaler Sprachen.
  • Fähigkeit, formale Spezifikationen (z.B. in BNF) zu erstellen und zu verstehen.
  • Beherrschung verschiedener Berechenbarkeitsbegriffe.
  • Grundlagen der Komplexitätstheorie.
Verantwortliche Person:
Müller Andreas
Zusätzlich vorausgesetzte Kenntnisse:
keine, kann unabhängig vom Modul Mathematische Grundlagen der Informatik 1 belegt werden
Skriptablage:
Modultyp:
Standard-Modul für Informatik STD_05(Empfohlenes Semester: 2)
Standard-Modul für Informatik STD_02(Empfohlenes Semester: 2)
Standard-Modul für Informatik U1_01(Empfohlenes Semester: 2)
Standard-Modul für Informatik STD_11(Empfohlenes Semester: 2)

ECTS-Punkte pro Kategorie

Kategorie:
Mathematik / 4 Punkte
Mathematik / 4 Punkte
Mathematik / 4 Punkte

Modulbewertung

Bewertungsart:
Note von 1 - 6

Leistungsbewertung

Während der Prüfungssession:
Schriftliche Prüfung, 120 Minuten

Kurse in diesem Modul

Mathematische Grundlagen der Informatik 2

Kurzzeichen:
Math2I
Lernziele:
Plan und Lerninhalt:
  1. Reguläre Sprachen
    (Reguläre Ausdrücke, deterministische und nicht-deterministische endliche Automaten, Äquivalenz von regulären Sprachen und endlichen Automaten, Pumping-Lemma für reguläre Sprachen)
  2. Kontextfreie Sprachen
    (Kontextfreie Grammatiken, deterministische und nicht-deterministische Keller-Automaten, Äquivalenz von regulären Sprachen und Keller-Automaten, Pumping-Lemma für kontextfreie Sprachen)
  3. Berechnungstheorie
    (Turing-Maschinen, Halteproblem, Satz von Rice)
  4. Komplexitätstheorie
    (Die Klassen P und NP, NP-vollständige Probleme)
Kursart:

(Durchführung gemäss Stundenplan)

Vorlesung mit 3 Lektionen pro Woche
   - Max. Teilnehmer: 36
   - Harte Grenze: ja
Uebung mit 1 Lektionen pro Woche
   - Max. Teilnehmer: 18
   - Harte Grenze: ja

Übergangsregelungen:
Theoretische Grundlagen der Informatik (mUk_ThGlI) (nicht durchgeführt)