Formale Grundlagen WS 2019/2020

• Die Tutoriumseinteilung findet in Moodle statt. Bitte beachten Sie die Anmelde-Deadline am 23. Oktober 2019! Es finden in den ersten drei Vorlesungswoche keine Tutorien statt.
• Das erste Übungsblatt wird in der zweiten Vorlesungswoche online gestellt.
• Die Ausgabe der Vorlesungsskripte findet ausschließlich in der ersten Vorlesung am Donnerstag, den 17. Oktober 2019 statt.
• Die erste Vorlesung findet am Donnerstag, den 17. Oktober 2019, statt.

Der gesamte Vorlesungs-, Übungs- bzw. Tutorienbetrieb sowie wichtige Ankündigungen und Informationen zu Klausuren wird über die Lernplattform Moodle durchgeführt. Bitte melden Sie sich rechtzeitig in der ersten Semesterwoche an!

Im Modul werden die notwendigen Grundbegriffe für den Umgang mit der mathematisch-formalen Symbolik wie Mengen, Folgen, Quantoren, Codes, Boole’sche Algebra sowei die hierzu notwendigen Beweistechniken behandelt.

• Formalismen zur Beschreibung von Mengen, Mengensystemen, Folgen, Alphabeten, Wörtern, Sprachen, Codes, Relationen, Funktionen, Permutationen sowie deren elementaren Eigenschaften.
• Elementare Beweistechniken: direkter Beweis, indirekter Beweis, Fallunterscheidung, Induktionsbeweis, Abzählargument, Schubfachprinzip, Inklusions-Exklusionsprinzip, Existenz und Eindeutigkeit
• Elemente der Codierungs- und Informationstheorie. Entropiebegriff.
• Boole’sche Algebra, Boole’sche Funktionen, das Perzeptron, Schaltkreiskomplexität
• Formale Grammatiken und Automaten/Turingmaschinen und deren Eigenschaften. Chomsky-Hierarchie.

Der Inhalt dieser Vorlesung bildet eine der wichtigsten Grundlagen des Informatikstudiums.

Ziel der Vorlesung ist:

Die Studierenden können mit den in der Mathematik und Theoretischen Informatik gebräuchlichen Formalismen zur Beschreibung von Mengen, Mengensystemen, Folgen, Alphabeten, Wörtern sowie den einschlägigen Beweistechniken wie direkter, indirekter Beweis, Induktionsbeweis, Strukturelle Induktion, Schubfachschlussprinzip souverän umgehen und verstehen diese Methoden geeignet anzuwenden. Sie sind mit den Einsatz und Nutzen von formalen Grammatiken, Automaten, Codes und Booleschen Funktionen vertraut und wissen diese in ihrer Komplexität einzuordnen.

Präsenzzeit: 90 h

Vor- und Nachbereitung: 150 h

Summe: 240 h

Siehe https://ulm.ibs-bw.de/aDISWeb/app?service=direct/0/Home/$DirectLink&sp=SOPAC00&sp=SWI00000915&noRedir 

• Vorlesungsskript
• U. Schöning, H.A. Kestler: Mathe-Toolbox. Lehmanns Media, 2. erw. Auflage, 2011.
• U. Schöning: Theoretische Informatik - kurz gefasst. 5. Auflage, Spektrum, 2008
• I. Wegener: Theoretische Informatik. Teubner, 1993.
• N. Blum: Einführung in Formale Sprachen, Berechenbarkeit, Informations- und Lerntheorie. Oldenbourg, 2007.