# Module im Bereich: Mathematik / Theoretische Informatik

# Grundlagen der Theoretischen Informatik

**Winter**


(engl. Introduction to the Theory of Computation )

<table bgcolor="#7FB3D9" border="1" id="bkmrk-%5Btitle%5D" style="width: 100%; border-collapse: collapse; border-width: 1px; border-style: none;"><colgroup><col style="width: 100%;"></col></colgroup><tbody><tr style="background-color: rgb(235, 243, 249);"><td>##### <span style="color: rgb(0, 104, 180);">**Modulnummer: FIN-INF-110105** </span>

</td></tr></tbody></table>

<table bgcolor="#7FB3D9" border="1" id="bkmrk-" style="border-collapse: collapse; width: 100%;"><colgroup><col style="width: 14.2515%;"></col><col style="width: 14.2515%;"></col><col style="width: 13.061%;"></col><col style="width: 15.442%;"></col><col style="width: 14.2515%;"></col><col style="width: 14.2515%;"></col><col style="width: 14.2515%;"></col></colgroup><tbody><tr><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Kürzel**</span>

<span style="color: rgb(61, 61, 61);">GThI </span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**CP**</span>

<span style="color: rgb(61, 61, 61);">5 </span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Semester**</span>

<span style="color: rgb(61, 61, 61);">Winter </span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Fachsem.**</span>

<span style="color: #3d3d3d;">ab 3. </span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);">**<span style="color: rgb(61, 61, 61);">Dauer</span>**

<span style="color: rgb(61, 61, 61);">1 Semester </span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Sprache**</span>

<span style="color: rgb(61, 61, 61);">deutsch</span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Niveau**</span>

<span style="color: rgb(61, 61, 61);">Bachelor </span>

</td></tr></tbody></table>

<table border="1" id="bkmrk-verantwortung%3A-verwe" style="border-collapse: collapse; width: 100%; height: 89.3907px; border-width: 1px; border-style: none;"><colgroup><col style="width: 20.2601%;"></col><col style="width: 79.7399%;"></col></colgroup><tbody><tr><td>**Link zum LSF:**</td><td>[ LSF](https://lsf.ovgu.de/qislsf/rds?state=wsearchv&search=1&subdir=veranstaltung&veranstaltung.semester=20262&veranstaltung.dtxt=Grundlagen+der+Theoretischen+Informatik&P_start=0&P_anzahl=30&P.sort=veranstaltung.dtxt&_form=display "Grundlagen der Theoretischen Informatik")</td></tr><tr><td>**Zugang beschränkt:**</td><td>false </td></tr><tr style="height: 29.7969px;"><td style="height: 29.7969px;">**Verantwortung:**</td><td style="height: 29.7969px;">Prof. Dr. Stefan Schirra </td></tr><tr style="height: 29.7969px;"><td style="height: 29.7969px;">**Dozent:in:**</td><td style="height: 29.7969px;">Prof. Dr. Stefan Schirra </td></tr><tr><td>**Lehrveranstaltungen:**</td><td>- Vorlesung *Grundlagen der Theoretischen Informatik*
- Übung *Grundlagen der Theoretischen Informatik*

</td></tr><tr style="height: 29.7969px;"><td style="height: 29.7969px;">**Verwendbarkeit:**</td><td style="height: 29.7969px;">- B.Sc. INF: Mathematik / Theoretische Informatik  
- B.Sc. INF: Aufbaumodule (SPO 2027)  
- B.Sc. CV: Mathematik / Theoretische Informatik  
- B.Sc. CV: Computervisualistik Pflicht (SPO 2027)  
- B.Sc. INGINF: Mathematik / Theoretische Informatik  
- B.Sc. INGINF: Ingenieurinformatik Pflicht (SPO 2027)  
- B.Sc. WIF: Verstehen und Gestalten - Wahlpflicht  
- B.Sc. WIF: Informatik Wahlpflicht (SPO 2027)  
- B.Sc. INF (bilingual): Mathematik / Theoretische Informatik  
- B.Sc. INF (bilingual): Aufbaumodule (SPO 2027)  
  
</td></tr></tbody></table>

**Angestrebte Lernergebnisse:**

- Grundlagen von Automatentheorie und formalen Sprachen zur Problemlösung
- Fähigkeit, Probleme hinsichtlich Berechenbarkeit und Komplexität einordnen zu können

  
**Inhalt:**

- Einführung in Formale Sprachen (reguläre und kontextfreie Sprachen, Grammatiken),
- elementare Automatentheorie (endliche Automaten, Kellerautomaten),
- Berechnungsmodelle und Churchsche These,
- Entscheidbarkeit und Semi-Entscheidbarkeit,
- Komplexitätsklassen P und NP, NP-Vollständigkeit

**Arbeitsaufwand:**

- 70h Präsenzzeit
- 80h selbstständige Arbeit

  
<table border="1" id="bkmrk-studien-%2Fpr%C3%BCfungslei" style="border-collapse: collapse; width: 100%;"><colgroup><col style="width: 32.6591%;"></col><col style="width: 35.9941%;"></col><col style="width: 31.3468%;"></col></colgroup><tbody><tr><td>**Prüfungsvorleistungen:**</td><td>**Studien-/Prüfungsleistungen:**</td><td>**Lehrform / SWS:**</td></tr><tr><td style="vertical-align: top;">Erfolgreiche Teilnahme an den Übungen, d.h. für je 4 aufeinanderfolgende Übungsblätter 50% der Aufgaben erfolgreich votieren (siehe moodle und Vorlesung) und mindestens einmal erfolgreich eine eigene Lösung präsentieren

</td><td class="align-left" style="vertical-align: top;">Klausur 120 Minuten (schriftliche Prüfung)

</td><td class="align-left" style="vertical-align: top;">- Vorlesung (3 SWS )
- Übung (2 SWS)

  
</td></tr></tbody></table>

<table border="1" id="bkmrk-voraussetzungen-nach" style="font-family: var(--font-body); font-size: 14px; width: 100%;"><colgroup><col style="width: 50%;"></col><col style="width: 50%;"></col></colgroup><tbody><tr><td>**Voraussetzungen nach Prüfungsordnung:**</td><td>**Empfohlene Voraussetzungen:**</td></tr><tr><td class="align-left" style="vertical-align: top;">keine

</td><td class="align-left" style="vertical-align: top;"></td></tr></tbody></table>

<table border="1" id="bkmrk-medienformen%3A-litera" style="border-collapse: collapse; width: 100%;"><colgroup><col style="width: 50%;"></col><col style="width: 50%;"></col></colgroup><tbody><tr><td>**Medienformen:**</td><td>**Literatur:**</td></tr><tr><td class="align-left" style="vertical-align: top;"></td><td class="align-left" style="vertical-align: top;">- Hopcroft, Motwani, Ullmann; Einführung in der Automatentheorie, Formale Sprachen und Komplexitätstheorie
- Lewis, Papadimitriou; Elements of the Theory of Computation
- Sipser; Theory of Computation.

  
</td></tr></tbody></table>

**Hinweise:**

# Introduction to the Theory of Computation

##### Winter 


##### (in German: Grundlagen der Theoretischen Informatik )

<table bgcolor="#7FB3D9" border="1" id="bkmrk-%5Btitle%5D" style="width: 100%; border-collapse: collapse; border-width: 1px; border-style: none;"><colgroup><col style="width: 100%;"></col></colgroup><tbody><tr style="background-color: rgb(235, 243, 249);"><td>##### <span style="color: rgb(0, 104, 180);">**Module-ID:** </span><span style="color: rgb(0, 104, 180);">**FIN-INF-110493** </span>

</td></tr></tbody></table>

<table bgcolor="#7FB3D9" border="1" id="bkmrk-" style="border-collapse: collapse; width: 100%;"><colgroup><col style="width: 14.2515%;"></col><col style="width: 14.2515%;"></col><col style="width: 13.061%;"></col><col style="width: 15.442%;"></col><col style="width: 14.2515%;"></col><col style="width: 14.2515%;"></col><col style="width: 14.2515%;"></col></colgroup><tbody><tr><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Abbreviation**</span>

<span style="color: rgb(61, 61, 61);"></span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Credit Points**</span>

<span style="color: rgb(61, 61, 61);">5 </span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Semester**</span>

<span style="color: rgb(61, 61, 61);">Winter </span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Term**</span>

<span style="color: #3d3d3d;">3. 

</span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);">**<span style="color: rgb(61, 61, 61);">Duration</span>**

<span style="color: rgb(61, 61, 61);">1 Semester </span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Language**</span>

<span style="color: rgb(61, 61, 61);">english</span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Level**</span>

<span style="color: rgb(61, 61, 61);">Bachelor </span>

</td></tr></tbody></table>

<table border="1" id="bkmrk-verantwortung%3A-verwe" style="border-collapse: collapse; width: 100%; height: 124.8px; border-width: 1px; border-style: none;"><colgroup><col style="width: 24.7879%;"></col><col style="width: 75.2121%;"></col></colgroup><tbody><tr style="height: 35.4px;"><td style="height: 35.4px;">**Link:**</td><td style="height: 35.4px;">[ LSF](https://lsf.ovgu.de/qislsf/rds?state=wsearchv&search=1&subdir=veranstaltung&veranstaltung.semester=20262&veranstaltung.dtxt=Grundlagen+der+Theoretischen+Informatik&P_start=0&P_anzahl=30&P.sort=veranstaltung.dtxt&_form=display "Grundlagen der Theoretischen Informatik")</td></tr><tr><td>**Limited accessability:**</td><td></td></tr><tr style="height: 29.8px;"><td style="height: 29.8px;">**Responsibility:**</td><td style="height: 29.8px;">Tetiana Lavynska </td></tr><tr style="height: 29.8px;"><td style="height: 29.8px;">**Lecturer:**</td><td style="height: 29.8px;">Tetiana Lavynska </td></tr><tr><td>**Classes:**</td><td>- Lecture *Introduction to the Theory of Computation*
- Exercise *Introduction to the Theory of Computation*

 </td></tr><tr style="height: 29.8px;"><td style="height: 29.8px;">**Applicability in curriculum:**</td><td style="height: 29.8px;">- B.Sc. INF (bilingual): Mathematik / Theoretische Informatik  
- B.Sc. INF (bilingual): Aufbaumodule (SPO 2027)  
  
</td></tr></tbody></table>

**Intended learning outcomes:**

- Basics of automata theory and formal languages for problem solving
- Ability to classify problems in terms of predictability and complexity

  
**Content:**

- Introduction to Formal Languages (regular and context-free languages, grammars),
- elementary automata theory (finite automata, basement automata),
- Computational models and Church's thesis,
- Decidability and semi-decidability,
- Complexity classes : P and NP, NP-completeness

**Workload:** 70h contact hours + 80h self study

<table border="1" id="bkmrk-studien-%2Fpr%C3%BCfungslei" style="border-collapse: collapse; width: 100%;"><colgroup><col style="width: 32.0641%;"></col><col style="width: 34.9204%;"></col><col style="width: 33.0155%;"></col></colgroup><tbody><tr><td>**Pre-examination requirements:**</td><td>**Type of examination:**</td><td>**Teaching method / lecture hours per week (SWS):**</td></tr><tr><td>Exam preparation: Successful participation in the exercises (see lecture)

</td><td>Written exam 120 minutes

</td><td>Lecture (3 SWS) Exercise (2 SWS)

</td></tr></tbody></table>

<table border="1" id="bkmrk-voraussetzungen-nach" style="font-family: var(--font-body); font-size: 14px; width: 100%;"><colgroup><col style="width: 50%;"></col><col style="width: 50%;"></col></colgroup><tbody><tr><td>**Prerequisites according to examination regulations:**</td><td>**Recommended prerequisites:**</td></tr><tr><td>none

</td><td></td></tr></tbody></table>

<table border="1" id="bkmrk-medienformen%3A-litera" style="border-collapse: collapse; width: 100%;"><colgroup><col style="width: 50%;"></col><col style="width: 50%;"></col></colgroup><tbody><tr><td>**Media:**</td><td>**Literature:**</td></tr><tr><td></td><td>- Hopcroft, Motwani, Ullmann; Einführung in der Automatentheorie, Formale Sprachen und Komplexitätstheorie
- Lewis, Papadimitriou; Elements of the Theory of Computation
- Sipser; Theory of Computation.

  
</td></tr></tbody></table>

**Comments:**

# Grundlagen der Theoretischen Informatik II

**Sommer**


(engl. Introduction to the Theory of Computation II )

<table bgcolor="#7FB3D9" border="1" id="bkmrk-%5Btitle%5D" style="width: 100%; border-collapse: collapse; border-width: 1px; border-style: none;"><colgroup><col style="width: 100%;"></col></colgroup><tbody><tr style="background-color: rgb(235, 243, 249);"><td>##### <span style="color: rgb(0, 104, 180);">**Modulnummer: FIN-INF-110118** </span>

</td></tr></tbody></table>

<table bgcolor="#7FB3D9" border="1" id="bkmrk-" style="border-collapse: collapse; width: 100%;"><colgroup><col style="width: 14.2515%;"></col><col style="width: 14.2515%;"></col><col style="width: 13.061%;"></col><col style="width: 15.442%;"></col><col style="width: 14.2515%;"></col><col style="width: 14.2515%;"></col><col style="width: 14.2515%;"></col></colgroup><tbody><tr><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Kürzel**</span>

<span style="color: rgb(61, 61, 61);">GThI 2 </span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**CP**</span>

<span style="color: rgb(61, 61, 61);">5 </span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Semester**</span>

<span style="color: rgb(61, 61, 61);">Sommer </span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Fachsem.**</span>

<span style="color: #3d3d3d;">ab 4. </span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);">**<span style="color: rgb(61, 61, 61);">Dauer</span>**

<span style="color: rgb(61, 61, 61);">1 Semester </span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Sprache**</span>

<span style="color: rgb(61, 61, 61);">deutsch</span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Niveau**</span>

<span style="color: rgb(61, 61, 61);">Bachelor </span>

</td></tr></tbody></table>

<table border="1" id="bkmrk-verantwortung%3A-verwe" style="border-collapse: collapse; width: 100%; height: 89.3907px; border-width: 1px; border-style: none;"><colgroup><col style="width: 20.2601%;"></col><col style="width: 79.7399%;"></col></colgroup><tbody><tr><td>**Link zum LSF:**</td><td>[ LSF](https://lsf.ovgu.de/qislsf/rds?state=wsearchv&search=1&subdir=veranstaltung&veranstaltung.semester=20261&veranstaltung.dtxt=Grundlagen+der+Theoretischen+Informatik+II&P_start=0&P_anzahl=30&P.sort=veranstaltung.dtxt&_form=display "Grundlagen der Theoretischen Informatik II")</td></tr><tr><td>**Zugang beschränkt:**</td><td>false </td></tr><tr style="height: 29.7969px;"><td style="height: 29.7969px;">**Verantwortung:**</td><td style="height: 29.7969px;">Prof. Dr. Stefan Schirra </td></tr><tr style="height: 29.7969px;"><td style="height: 29.7969px;">**Dozent:in:**</td><td style="height: 29.7969px;">Prof. Dr. Stefan Schirra </td></tr><tr><td>**Lehrveranstaltungen:**</td><td>- Vorlesung *Grundlagen der Theoretischen Informatik II*
- Übung *Grundlagen der Theoretischen Informatik II*

</td></tr><tr style="height: 29.7969px;"><td style="height: 29.7969px;">**Verwendbarkeit:**</td><td style="height: 29.7969px;">- B.Sc. INF: Mathematik / Theoretische Informatik  
- B.Sc. INF: Aufbaumodule (SPO 2027)  
- B.Sc. CV: Informatik - Wahlpflicht  
- B.Sc. CV: Computervisualistik Wahlpflicht (SPO 2027)  
- B.Sc. INGINF: Informatik - Wahlpflicht  
- B.Sc. INGINF: Informatik Wahlpflicht (SPO 2027)  
- B.Sc. WIF: Verstehen und Gestalten - Wahlpflicht  
- B.Sc. WIF: Informatik Wahlpflicht (SPO 2027)  
- B.Sc. INF (bilingual): Mathematik / Theoretische Informatik  
- B.Sc. INF (bilingual): Aufbaumodule (SPO 2027)  
  
</td></tr></tbody></table>

**Angestrebte Lernergebnisse:** Die Studierenden haben erweiterte Fähigkeiten, komplexe Probleme hinsichtlich Berechenbarkeit und Komplexität beurteilen und klassifizieren zu können.

**Inhalt:**

- Weiterführendes zu Formalen Sprachen und Automatentheorie (Abschlusseigenschaften, deterministische Kellerautomaten, Zustandsminimierung endlicher Automaten),
- Äquivalenz verschiedener Berechnungsmodelle (beispielsweise Turingmaschinen, Registermaschinen, primitiv rekursive und mu-rekursive Funktionen, Grammatiken),
- weitere unentscheidbare und NP-vollständige Probleme.

**Arbeitsaufwand:** 56h Präsenzzeit 94h selbstständige Arbeit (Bearbeiten der Übungsaufgaben Nachbereitung der Vorlesungen)

<table border="1" id="bkmrk-studien-%2Fpr%C3%BCfungslei" style="border-collapse: collapse; width: 100%;"><colgroup><col style="width: 32.6591%;"></col><col style="width: 35.9941%;"></col><col style="width: 31.3468%;"></col></colgroup><tbody><tr><td>**Prüfungsvorleistungen:**</td><td>**Studien-/Prüfungsleistungen:**</td><td>**Lehrform / SWS:**</td></tr><tr><td style="vertical-align: top;">Erfolgreiche Teilnahme an den Übungen, d.h. für je 4 aufeinanderfolgende Übungsblätter 50% der Aufgaben erfolgreich votieren

</td><td class="align-left" style="vertical-align: top;">Klausur 120 Min (schriftliche Prüfung)

</td><td class="align-left" style="vertical-align: top;">- Vorlesung (2 SWS)
- Übung (2 SWS)

  
</td></tr></tbody></table>

<table border="1" id="bkmrk-voraussetzungen-nach" style="font-family: var(--font-body); font-size: 14px; width: 100%;"><colgroup><col style="width: 50%;"></col><col style="width: 50%;"></col></colgroup><tbody><tr><td>**Voraussetzungen nach Prüfungsordnung:**</td><td>**Empfohlene Voraussetzungen:**</td></tr><tr><td class="align-left" style="vertical-align: top;">keine

</td><td class="align-left" style="vertical-align: top;">Grundlagen der Theoretischen Informatik

</td></tr></tbody></table>

<table border="1" id="bkmrk-medienformen%3A-litera" style="border-collapse: collapse; width: 100%;"><colgroup><col style="width: 50%;"></col><col style="width: 50%;"></col></colgroup><tbody><tr><td>**Medienformen:**</td><td>**Literatur:**</td></tr><tr><td class="align-left" style="vertical-align: top;"></td><td class="align-left" style="vertical-align: top;">- Sipser; Theory of Computation
- Kozen; Automata and Computability

  
</td></tr></tbody></table>

**Hinweise:** Auch dieses Modul ist zwei Lehrstühlen zugeordnet, die es abwechselnd bedienen

# Introduction to the Theory of Computation II

##### Summer 


##### (in German: Grundlagen der Theoretischen Informatik II )

<table bgcolor="#7FB3D9" border="1" id="bkmrk-%5Btitle%5D" style="width: 100%; border-collapse: collapse; border-width: 1px; border-style: none;"><colgroup><col style="width: 100%;"></col></colgroup><tbody><tr style="background-color: rgb(235, 243, 249);"><td>##### <span style="color: rgb(0, 104, 180);">**Module-ID:** </span><span style="color: rgb(0, 104, 180);">**FIN-INF-110494** </span>

</td></tr></tbody></table>

<table bgcolor="#7FB3D9" border="1" id="bkmrk-" style="border-collapse: collapse; width: 100%;"><colgroup><col style="width: 14.2515%;"></col><col style="width: 14.2515%;"></col><col style="width: 13.061%;"></col><col style="width: 15.442%;"></col><col style="width: 14.2515%;"></col><col style="width: 14.2515%;"></col><col style="width: 14.2515%;"></col></colgroup><tbody><tr><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Abbreviation**</span>

<span style="color: rgb(61, 61, 61);"></span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Credit Points**</span>

<span style="color: rgb(61, 61, 61);">5 </span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Semester**</span>

<span style="color: rgb(61, 61, 61);">Summer </span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Term**</span>

<span style="color: #3d3d3d;">4. 

</span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);">**<span style="color: rgb(61, 61, 61);">Duration</span>**

<span style="color: rgb(61, 61, 61);">1 Semester </span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Language**</span>

<span style="color: rgb(61, 61, 61);">english</span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Level**</span>

<span style="color: rgb(61, 61, 61);">Bachelor </span>

</td></tr></tbody></table>

<table border="1" id="bkmrk-verantwortung%3A-verwe" style="border-collapse: collapse; width: 100%; height: 124.8px; border-width: 1px; border-style: none;"><colgroup><col style="width: 24.7879%;"></col><col style="width: 75.2121%;"></col></colgroup><tbody><tr style="height: 35.4px;"><td style="height: 35.4px;">**Link:**</td><td style="height: 35.4px;">[ LSF](https://lsf.ovgu.de/qislsf/rds?state=wsearchv&search=1&subdir=veranstaltung&veranstaltung.semester=20261&veranstaltung.dtxt=Grundlagen+der+Theoretischen+Informatik+II&P_start=0&P_anzahl=30&P.sort=veranstaltung.dtxt&_form=display "Grundlagen der Theoretischen Informatik II")</td></tr><tr><td>**Limited accessability:**</td><td></td></tr><tr style="height: 29.8px;"><td style="height: 29.8px;">**Responsibility:**</td><td style="height: 29.8px;">Tetiana Lavynska </td></tr><tr style="height: 29.8px;"><td style="height: 29.8px;">**Lecturer:**</td><td style="height: 29.8px;">Tetiana Lavynska </td></tr><tr><td>**Classes:**</td><td>- Lecture *Introduction to the Theory of Computation II*
- Exercise *Introduction to the Theory of Computation II*

 </td></tr><tr style="height: 29.8px;"><td style="height: 29.8px;">**Applicability in curriculum:**</td><td style="height: 29.8px;">- B.Sc. INF (bilingual): Mathematik / Theoretische Informatik  
- B.Sc. INF (bilingual): Aufbaumodule (SPO 2027)  
  
</td></tr></tbody></table>

**Intended learning outcomes:** Students have advanced skills in assessing and classifying complex problems in terms of calculability and complexity.

**Content:**

- Further information on formal languages and automata theory (closure properties, deterministic basement automata, state minimization of finite automata),
- equivalence of different computational models (e.g. Turing machines, register machines, primitive recursive and mu-recursive functions, grammars),
- further undecidable and NP-complete problems.

**Workload:** 56h contact hours + 94h self study (working on the exercises and following up on the lectures)

<table border="1" id="bkmrk-studien-%2Fpr%C3%BCfungslei" style="border-collapse: collapse; width: 100%;"><colgroup><col style="width: 32.0641%;"></col><col style="width: 34.9204%;"></col><col style="width: 33.0155%;"></col></colgroup><tbody><tr><td>**Pre-examination requirements:**</td><td>**Type of examination:**</td><td>**Teaching method / lecture hours per week (SWS):**</td></tr><tr><td>Exam admission prerequisites: Successful participation in the exercises (see lecture)

</td><td>Written exam 120 min

</td><td>- Lecture (2 SWS)
- Exercise (2 SWS)

</td></tr></tbody></table>

<table border="1" id="bkmrk-voraussetzungen-nach" style="font-family: var(--font-body); font-size: 14px; width: 100%;"><colgroup><col style="width: 50%;"></col><col style="width: 50%;"></col></colgroup><tbody><tr><td>**Prerequisites according to examination regulations:**</td><td>**Recommended prerequisites:**</td></tr><tr><td>none

</td><td>Introduction to the Theory of Computation

</td></tr></tbody></table>

<table border="1" id="bkmrk-medienformen%3A-litera" style="border-collapse: collapse; width: 100%;"><colgroup><col style="width: 50%;"></col><col style="width: 50%;"></col></colgroup><tbody><tr><td>**Media:**</td><td>**Literature:**</td></tr><tr><td></td><td>- Sipser; Theory of Computation
- Kozen; Automata and Computability

  
</td></tr></tbody></table>

**Comments:**

# Mathematik M5d

**Sommer**

(engl. Mathematics M5d )

<table bgcolor="#7FB3D9" border="1" id="bkmrk-%5Btitle%5D" style="width: 100%; border-collapse: collapse; border-width: 1px; border-style: none;"><colgroup><col style="width: 100%;"></col></colgroup><tbody><tr style="background-color: rgb(235, 243, 249);"><td style="background-color: rgb(245, 217, 221);">##### <span style="color: rgb(209, 63, 88);">**Modulnummer: FMA-INF-501329** </span>

</td></tr></tbody></table>

<table border="1" id="bkmrk-verantwortung%3A-verwe" style="border-collapse: collapse; width: 100%; height: 89.3907px; border-width: 1px; border-style: none;"><colgroup><col style="width: 20.2601%;"></col><col style="width: 79.7399%;"></col></colgroup><tbody><tr><td>**Link zum LSF:**</td><td>[ **(Angeboten wenn im LSF)**](https://lsf.ovgu.de/qislsf/rds?state=wsearchv&search=1&subdir=veranstaltung&veranstaltung.semester=20261&veranstaltung.dtxt=Mathematik+M5d&P_start=0&P_anzahl=30&P.sort=veranstaltung.dtxt&_form=display "Mathematik M5d")</td></tr><tr style="height: 29.7969px;"><td style="height: 29.7969px;">**Verantwortung:**</td><td style="height: 29.7969px;">Prof. Dr. Thomas Kahle </td></tr><tr style="height: 29.7969px;"><td style="height: 29.7969px;">**Dozent:in:**</td><td style="height: 29.7969px;">, Prof. Dr. Thomas Kahle </td></tr><tr><td>**Lehrveranstaltungen:**</td><td>Vorlesung Mathematik M5d Globalübung Mathematik M5d Gruppenübung Mathematik M5d </td></tr></tbody></table>

<table bgcolor="#7FB3D9" border="1" id="bkmrk-" style="border-collapse: collapse; width: 100%; height: 67.3906px;"><colgroup><col style="width: 16.6467%;"></col><col style="width: 15.3293%;"></col><col style="width: 18.0838%;"></col><col style="width: 16.6467%;"></col><col style="width: 16.6467%;"></col><col style="width: 16.6467%;"></col></colgroup><tbody><tr style="height: 67.3906px;"><td class="align-center" style="border: 5px solid rgb(255, 255, 255); background-color: rgb(232, 136, 152); height: 67.3906px;"><span style="color: rgb(61, 61, 61);">**Leistungspkt.**</span>

<span style="color: rgb(61, 61, 61);">5 </span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255); background-color: rgb(232, 136, 152); height: 67.3906px;"><span style="color: rgb(61, 61, 61);">**Semester**</span>

<span style="color: rgb(61, 61, 61);">Sommer </span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255); background-color: rgb(232, 136, 152); height: 67.3906px;"><span style="color: rgb(61, 61, 61);">**Fachsem.**</span>

<span style="color: #3d3d3d;">3. 

</span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255); background-color: rgb(232, 136, 152); height: 67.3906px;">**<span style="color: rgb(61, 61, 61);">Dauer</span>**

<span style="color: rgb(61, 61, 61);">1 Semester </span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255); background-color: rgb(232, 136, 152); height: 67.3906px;"><span style="color: rgb(61, 61, 61);">**Sprache**</span>

<span style="color: rgb(61, 61, 61);">deutsch </span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255); background-color: rgb(232, 136, 152); height: 67.3906px;"><span style="color: rgb(61, 61, 61);">**Niveau**</span>

<span style="color: rgb(61, 61, 61);">Bachelor </span>

</td></tr></tbody></table>

**Ziele und Kompetenzen:** Die Studierenden erlangen auf Verständnis beruhende Vertrautheit mit den für fachwissenschaftliche Module in der Informatik relevanten mathematischen Konzepten und Methoden. Sie erwerben technische Fähigkeiten im Umgang mit diesen, insbesondere unter Verwendung fachspezifischer Beispiele. Thematische Schwerpunkte des Moduls sind diskrete und algebraische Strukturen sowie algorithmische Aspekte.

**Inhalt:**

- Algebraische Strukturen
- Kombinatorik und Graphen
- Grundlagen der Optimierung
- Numerische Lösungsverfahren
- Geometrische Methoden

**Arbeitsaufwand:**

<table id="bkmrk-pr%C3%A4senszeit-selbstst"><thead><tr><th></th><th>Präsenszeit</th><th>Selbststudium</th></tr></thead><tbody><tr><td>Vorlesung</td><td>3 SWS / 42 h</td><td>66 h</td></tr><tr><td>Globalübung</td><td>2 SWS / 28 h</td><td></td></tr><tr><td>Gruppenübung</td><td>1 SWS / 14 h</td><td></td></tr></tbody></table>

  
<table border="1" id="bkmrk-studien-%2Fpr%C3%BCfungslei" style="border-collapse: collapse; width: 100%;"><colgroup><col style="width: 32.3004%;"></col><col style="width: 33.4927%;"></col><col style="width: 34.207%;"></col></colgroup><tbody><tr><td>**Voraussetzungen für die Teilnahme:**</td><td>**Prüfungsvorleistung:**</td><td>**Prüfungsleistung:**</td></tr><tr><td class="align-left" style="vertical-align: top;"></td><td class="align-left" style="vertical-align: top;"></td><td style="vertical-align: top;"></td></tr></tbody></table>

<table border="1" id="bkmrk-verwendbarkeit-fma%3A-" style="border-collapse: collapse; width: 100%; height: 89.3907px; border-width: 1px; border-style: none;"><colgroup><col style="width: 20.2601%;"></col><col style="width: 79.7399%;"></col></colgroup><tbody><tr style="height: 29.7969px;"><td style="height: 29.7969px;">**Verwendbarkeit:**</td><td style="height: 29.7969px;">- B.Sc. INF: Mathematik / Theoretische Informatik  
- B.Sc. INF: Mathematik (SPO 2027)  
- B.Sc. CV: Mathematik / Theoretische Informatik  
- B.Sc. CV: Mathematik (SPO 2027)  
- B.Sc. INGINF: Mathematik / Theoretische Informatik  
- B.Sc. INGINF: Mathematik (SPO 2027)  
- B.Sc. WIF: Verstehen - Pflicht  
- B.Sc. WIF: Mathematik (SPO 2027)  
- B.Sc. INF (bilingual): Mathematik / Theoretische Informatik  
- B.Sc. INF (bilingual): Mathematik (SPO 2027)  
  
</td></tr><tr><td>**Verwendbarkeit andere Fakultäten:**</td><td>  
</td></tr></tbody></table>

**Hinweise:**

# Mathematics M5e

**Summer**

(engl. Mathematics M5e )

<table bgcolor="#7FB3D9" border="1" id="bkmrk-%5Btitle%5D" style="width: 100%; border-collapse: collapse; border-width: 1px; border-style: none;"><colgroup><col style="width: 100%;"></col></colgroup><tbody><tr style="background-color: rgb(235, 243, 249);"><td style="background-color: rgb(245, 217, 221);">##### <span style="color: rgb(209, 63, 88);">**Module-ID: FMA-INF-5013292** </span>

</td></tr></tbody></table>

<table border="1" id="bkmrk-verantwortung%3A-verwe" style="border-collapse: collapse; width: 100%; height: 89.3907px; border-width: 1px; border-style: none;"><colgroup><col style="width: 20.2601%;"></col><col style="width: 79.7399%;"></col></colgroup><tbody><tr><td>**Link:**</td><td>[ **(Angeboten wenn im LSF)**](https://lsf.ovgu.de/qislsf/rds?state=wsearchv&search=1&subdir=veranstaltung&veranstaltung.semester=20261&veranstaltung.dtxt=Mathematik+M5e&P_start=0&P_anzahl=30&P.sort=veranstaltung.dtxt&_form=display "Mathematik M5e")</td></tr><tr style="height: 29.7969px;"><td style="height: 29.7969px;">**Responsibility:**</td><td style="height: 29.7969px;">Prof. Dr. Thomas Kahle </td></tr><tr style="height: 29.7969px;"><td style="height: 29.7969px;">**Lecturer:**</td><td style="height: 29.7969px;">, Prof. Dr. Thomas Kahle </td></tr><tr><td>**Classes:**</td><td>Lecture Mathematics M5e Global tutorial Mathematics M5e Group tutorial Mathematics M5e </td></tr></tbody></table>

<table bgcolor="#7FB3D9" border="1" id="bkmrk-" style="border-collapse: collapse; width: 100%; height: 67.3906px;"><colgroup><col style="width: 16.6467%;"></col><col style="width: 15.3293%;"></col><col style="width: 18.0838%;"></col><col style="width: 16.6467%;"></col><col style="width: 16.6467%;"></col><col style="width: 16.6467%;"></col></colgroup><tbody><tr style="height: 67.3906px;"><td class="align-center" style="border: 5px solid rgb(255, 255, 255); background-color: rgb(232, 136, 152); height: 67.3906px;"><span style="color: rgb(61, 61, 61);">**Credit Points**</span>

<span style="color: rgb(61, 61, 61);">5 </span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255); background-color: rgb(232, 136, 152); height: 67.3906px;"><span style="color: rgb(61, 61, 61);">**Semester**</span>

<span style="color: rgb(61, 61, 61);">Summer </span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255); background-color: rgb(232, 136, 152); height: 67.3906px;"><span style="color: rgb(61, 61, 61);">**Term**</span>

<span style="color: #3d3d3d;">3. 

</span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255); background-color: rgb(232, 136, 152); height: 67.3906px;">**<span style="color: rgb(61, 61, 61);">Duration</span>**

<span style="color: rgb(61, 61, 61);">1 Semester </span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255); background-color: rgb(232, 136, 152); height: 67.3906px;"><span style="color: rgb(61, 61, 61);">**Language**</span>

<span style="color: rgb(61, 61, 61);">english </span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255); background-color: rgb(232, 136, 152); height: 67.3906px;"><span style="color: rgb(61, 61, 61);">**Level**</span>

<span style="color: rgb(61, 61, 61);">Bachelor </span>

</td></tr></tbody></table>

**Goals and qualifications:** The students acquire comprehension of and familiarity with concepts and methods that  
are relevant for subject-specific classes in computer science. They develop technical skills by applying those methods, in particular to subject-specific examples. The topical focus of the module is on discrete and algebraic structures, and algorithmic aspects.

**Content:**

- Algebraic structures
- Combinatorics, graphs
- Foundations of Optimization
- Numerical solving
- Geometric methods

**Workload:**

<table id="bkmrk-in-class-self-study-"><thead><tr><th></th><th>In class</th><th>self-study</th></tr></thead><tbody><tr><td>Lecture</td><td>3 SWS / 42 h</td><td>66 h</td></tr><tr><td>Global tutorial</td><td>2 SWS / 28 h</td><td></td></tr><tr><td>Group tutorial</td><td>1 SWS / 14 h</td><td></td></tr></tbody></table>

  
<table border="1" id="bkmrk-studien-%2Fpr%C3%BCfungslei" style="border-collapse: collapse; width: 100%;"><colgroup><col style="width: 32.3004%;"></col><col style="width: 33.4927%;"></col><col style="width: 34.207%;"></col></colgroup><tbody><tr><td>**Prerequisites for participation:**</td><td>**Pre-examination requirements:**</td><td>**Type of examination:**</td></tr><tr><td class="align-left" style="vertical-align: top;"></td><td class="align-left" style="vertical-align: top;"></td><td style="vertical-align: top;"></td></tr></tbody></table>

<table border="1" id="bkmrk-verwendbarkeit-fma%3A-" style="border-collapse: collapse; width: 100%; height: 89.3907px; border-width: 1px; border-style: none;"><colgroup><col style="width: 27.2899%;"></col><col style="width: 72.7101%;"></col></colgroup><tbody><tr style="height: 29.7969px;"><td style="height: 29.7969px;">**Applicability in curriculum:**</td><td style="height: 29.7969px;">- B.Sc. INF: Mathematik / Theoretische Informatik  
- B.Sc. INF: Mathematik (SPO 2027)  
- B.Sc. CV: Mathematik / Theoretische Informatik  
- B.Sc. CV: Mathematik (SPO 2027)  
- B.Sc. INGINF: Mathematik / Theoretische Informatik  
- B.Sc. INGINF: Mathematik (SPO 2027)  
- B.Sc. WIF: Verstehen - Pflicht  
- B.Sc. WIF: Mathematik (SPO 2027)  
- B.Sc. INF (bilingual): Mathematik / Theoretische Informatik  
- B.Sc. INF (bilingual): Mathematik (SPO 2027)  
  
</td></tr></tbody></table>

**Comments:**