# Grundlagen der Theoretischen Informatik III

**Winter**

#### (B.Sc.) 

(engl. Introduction to the Theory of Computation III )

<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-110464** </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 3 </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;">5. 

</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+III&P_start=0&P_anzahl=30&P.sort=veranstaltung.dtxt&_form=display "Grundlagen der Theoretischen Informatik III")</td></tr><tr><td>**Zugang beschränkt:**</td><td></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 III*
- Übung *Grundlagen der Theoretischen Informatik III*

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

**Angestrebte Lernergebnisse:** Studierende lernen, formale Sprachen in die Chomsky-Hierarchie einzuordnen und beurteilen zu können. Sie verstehen algebraische Zugänge zu Formalen Sprachen. Ferner lernen sie Optionen kennen, mit schweren Problemem umzugehen, und diese anzuwenden.

**Inhalt:**

- Weiteres zu regulären und kontextfreien Sprachen,
- Kleene Algebren,
- Exakte Exponentialzeitalgorithmen,
- Algorithmen für spezielle Graphklassen,
- Festparameterhandhabbarkeit,
- Approximationsalgorithmen und Nichatapproximierbarkeit
- Elementare Komplexitätstheorie.

**Arbeitsaufwand:** 56h Präsenzzeit + 94h 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;">Aktive Teilnahme an der Veranstaltung

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

</td><td class="align-left" style="vertical-align: top;">- Vorlesung (3 SWS)
- Übung (1 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 und Grundlagen der Theoretischen Informatik II (Bachelor)

</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
- Shallit; A Second Course on Automata and Computability Theory

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

**Hinweise:** Dies ist die Bachelorvariante zur gleichnamigen Masterveranstaltung. Voraussetzung sind die (Inhalte der) Veranstaltungen Grundlagen der Theoretischen Informatik und Grundlagen der Theoretischen Informatik II. Ein Bachelorzeugnis ist folglich keine zwingende Voraussetzung für diese Veranstaltung, die den Stoff aus den Teilen 1 und 2 vertieft und ergänzt. Der Aufwand ist eigentlich 6 CP, aber dies ist im Bachelorbereich leider nicht möglich, also sind es im Bachelor nur 5. Dafür müssen Studierende in der Bachelorvariante weniger Übungsaufgaben bearbeiten.