# 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:**

# 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:**