Mathematische Grundlagen der Informatik

ECTS 3.0

Inhaltsübersicht

Ziel des Moduls ist es einerseits die Studierenden mit den für die Informatik typischen und grundlegenden mathematischen Denk- und Argumentationsweisen vertraut zu machen und andererseits konkretes Wissen zu vermitteln, welches Grundlage für praktische Anwendungen und für weitere Module im Verlauf des Studiums ist.

Mengen und Operationen auf Mengen

Relationen, Funktionen und Graphen

  • Relationen
  • Äquivalenz- und Ordnungsrelationen
  • Funktionen und ihre Eigenschaften
  • Eigenschaften von Graphen
  • Modellierung mit Graphen

Logik

  • Aussagenlogik
  • Existenz- und Allquantoren

Sprachen, Grammatiken und Automaten

  • Produktionsgrammatiken
  • Chomsky-Hierarchie
  • Endliche Automaten
  • Endliche Automaten und reguläre Sprachen

Mengen und Operationen auf Mengen
Die Studierenden wissen, was eine Menge ist, und können die wichtigsten Operationen auf Mengen (Schnitt, Vereinigung, Differenz, Potenzmengenbildung, kartesisches Produkt) durchführen.

Relationen, Funktionen und Graphen
Sie verstehen den Begriff der Relation und können diese auf Reflexivität, Symmetrie, Transitivität und Antisymmetrie untersuchen. Sie können die Komposition zweier Relationen bestimmen.
Sie kennen Äquivalenzrelationen und Ordnungsrelationen sowie den Zusammenhang zwischen Äquivalenzrelationen und Partitionen. Sie können (totale/partielle) Funktionen auf Injektivität, Surjektivität und Bijektivität untersuchen und gegebenenfalls die Umkehrfunktion bestimmen. Die Studierenden kennen die wichtigsten Eigenschaften von (un)gerichteten Graphen und sind in der Lage, Probleme aus der Praxis mit Hilfe von Graphen zu modellieren.

Logik
Die Studierenden wissen, was eine Aussage ist, und können den Wahrheitsgehalt von zusammengesetzten Aussagen (Disjunktion, Konjunktion, Negation, Implikation, Äquivalenz) berechnen. Sie kennen den Existenz- und den Allquantor und können den Wahrheitsgehalt quantifizierter Aussagen bestimmen.

Induktion und Rekursion
Die Studierenden verstehen das Prinzip der vollständigen Induktion und sind in der Lage, Induktionsbeweise zu führen. Sie können lineare homogene sowie einfache inhomogene Rekursionsgleichungen (bis zum Grad 2) lösen. Sie sind fähig, durch Variablentransformation Rekursionsgleichungen zu erhalten und zu lösen, die häufig bei der Analyse von Algorithmen auftreten.

Sprachen und Grammatiken
Die Studierenden verstehen Grammatiken und wie man mit ihnen formale Sprachen beschreibt. Sie können Grammatiken und Sprachen gemäss der Chomsky-Hierarchie klassifizieren. Sie wissen, was ein DFA ist, kennen den Zusammenhang zu den regulären Sprachen und können zu ausgewählten regulären Sprachen einen DFA konstruieren.

Induktion und Rekursion
Die Studierenden verstehen das Prinzip der vollständigen Induktion und sind in der Lage, Induktionsbeweise zu führen. Sie können lineare homogene sowie einfache inhomogene Rekursionsgleichungen (bis zum Grad 2) lösen. Sie sind fähig, durch Variablentransformation Rekursionsgleichungen zu erhalten und zu lösen, die häufig bei der Analyse von Algorithmen auftreten.

Sprachen und Grammatiken
Die Studierenden verstehen Grammatiken und wie man mit ihnen formale Sprachen beschreibt. Sie können Grammatiken und Sprachen gemäss der Chomsky-Hierarchie klassifizieren. Sie wissen, was ein DFA ist, kennen den Zusammenhang zu den regulären Sprachen und können zu ausgewählten regulären Sprachen einen DFA konstruieren.

Leistungsbewertung

Erfahrungsnote und MSP schriftlich