Das Student-Self-Service ist auf Grund eines technischen Problems derzeit nur eingeschränkt verfügbar. Wir bitten um Ihr Verständnis.

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.

2023S, VO, 2.0h, 3.0EC

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VO Vorlesung
  • Format der Abhaltung: Präsenz

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

Vortrag

Prüfungsmodus

Mündlich

Vortragende Personen

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Mo.18:00 - 19:0013.03.2023 Besprechungsraum des Instituts, Freihaus grün, 5. StockVorbesprechung

Leistungsnachweis

Positive Absolvierung einer mündlichen Prüfung.

LVA-Anmeldung

Von Bis Abmeldung bis
17.02.2023 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

Es wird kein Skriptum zur Lehrveranstaltung angeboten.

Begleitende Lehrveranstaltungen

Sprache

bei Bedarf in Englisch