108.036 Theoretische Informatik
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2021S, VO, 2.0h, 3.0EC
TUWEL

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VO Vorlesung
  • Format der Abhaltung: Distance Learning

Lernergebnisse

Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage...

Das intendierte Lernergebnis dieser LVA besteht darin den Inhalt der LVA zu verstehen. Dieses Verständnis bildet unter anderem die Basis für die Fähigkeit die in der LVA besprochenen Aussagen und Begriffe korrekt wiederzugeben, sowie dafür die in der LVA eingesetzten Beweismethoden erklären und anwenden zu können.

Inhalt der Lehrveranstaltung

Die Vorlesung beginnt mit einer Einführung in die Theorie endlicher Automaten und formaler Sprachen. Wir lernen die Klassen der regulären und der kontextfreien Sprachen kennen, sowie verschiedene Beschreibungsformalismen für derartige Sprachen, insbesondere endliche Automaten und formale Grammatiken. Im zweiten Teil, nach einem starken Sprung in der Ausdrucksstärke, beschäftigen wir uns mit Berechenbarkeitstheorie, d.h. mit der Frage welche Funktionen überhaupt prinzipiell berechenbar sind. Dazu verwenden wir die Operatordarstellung partiell rekursiver Funktionen sowie Turingmaschinen. Wir diskutieren die Church-Turing-These und beweisen die grundlegenden Resultate der Berechenbarkeitstheorie. Im dritten Teil behandeln wir die Komplexitätstheorie. Diese erhält man aus der Berechenbarkeitstheorie durch eine Einschränkung der für eine Berechnung zur Verfügung stehenden Resourcen, z.B. auf polynomiale Zeit. In dieses Gebiet fällt das P vs. NP - Problem das wir ins Zentrum unserer Diskussion der Komplexitätstheorie stellen werden.

Methoden

Lektüre des Skriptums, Konversatorium zum Inhalt

Prüfungsmodus

Mündlich

Weitere Informationen

Weitere Informationen entnehmen Sie bitte der TUWEL-Seite zu dieser LVA.

Vortragende Personen

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Fr.13:00 - 14:0005.03.2021 Zoom (LIVE)Vorbesprechung

Leistungsnachweis

Positive Absolvierung einer mündlichen Prüfung.

LVA-Anmeldung

Von Bis Abmeldung bis
12.02.2021 00:00

Anmeldemodalitäten

Melden Sie sich bitte zu dieser LVA an um auf den zugehörigen TUWEL-Kurs zugreifen zu können.

Curricula

Literatur

Ein Skriptum zur Lehrveranstaltung ist erhältlich.

Begleitende Lehrveranstaltungen

Sprache

bei Bedarf in Englisch