Qualifikationsziele:

·       Studierende kennen grundlegende Definitionsmethoden und sind in der Lage, entsprechende Definitionen zu lesen, zu verstehen und selbst aufzustellen.

·       Die Studierenden kennen die grundlegenden Begriffe aus diskreter Mathematik und theoretischer Informatik und sind in der Lage sie richtig zu benutzen, sowohl bei der Beschreibung von Problemen als auch bei Beweisen.

·       Studierende können einfache Probleme korrekt und vollständig formalisieren, eine gewisse Anzahl von gängigen Verfahren beschreiben und anwenden, sowie einfache Beweise selbstständig durchführen.

·       Studierende beherrschen grundlegende mathematische Methoden aus der Kombinatorik und Graphentheorie. Sie sind in der Lage diese im Kontext der Korrektheit und Laufzeit von Algorithmen, im Kontext der Modellierung und Formalisierung von Problemen der theoretischen Informatik und im Kontext der formalen Sprachen anzuwenden.

Inhalt:

• Grundlagen des Aufbaus und der Analyse von Algorithmen, Sortieralgorithmen
• Korrektheit und Laufzeit in O-Notation
• Grundlagen zu Graphen, Bäume, Färbungen, Matchings
• Alphabete, Wörter, formale Sprachen, reguläre Ausdrücke
• mathematische Beweistechniken, Induktionsbeweise
• Kodierungen und Zahlendarstellungen
• Aussagenlogik, das Erfüllbarkeitsproblem
• Grundlagen der Kombinatorik, Binomialkoeffizienten, Permutationen
• Formalisierung von Entscheidungsproblemen, Einführung in Entscheidbarkeit und NP-Schwere

Arbeitsaufwand

Vorlesung: 18 x 1.5 h = 27.00 h
Übung: 12 x 0.75 h = 9.00 h
Tutorium: 14 x 1.5 h = 21.00 h
Nachbereitung: 18 x 0.5 h = 9.00 h
Bearbeitung von Aufgaben: 12 x 6 h = 72.00 h
Klausurvorbereitung: 1 x 40 h = 40.00 h
Klausur: 1 x 2 h = 2.00 h

Summe 180 h