Zur Seitennavigation oder mit Tastenkombination für den accesskey-Taste und Taste 1 
Zum Seiteninhalt oder mit Tastenkombination für den accesskey und Taste 2 

Foto: Matthias Friel

Sie sind hier: Startseite

Theoretische Informatik II: Effiziente Algorithmen - Einzelansicht

Veranstaltungsart Vorlesung Veranstaltungsnummer 550411
SWS Semester SoSe 2018
Einrichtung Institut für Informatik und Computational Science   Sprache deutsch
Belegungsfristen 03.04.2018 - 10.05.2018

Belegung über PULS
03.04.2018 - 20.05.2018

Belegung über PULS
Gruppe 1:
     jetzt belegen / abmelden
    Tag Zeit Rhythmus Dauer Raum Lehrperson Ausfall-/Ausweichtermine Max. Teilnehmer/-innen
Einzeltermine anzeigen
Vorlesung Di 08:00 bis 10:00 wöchentlich 10.04.2018 bis 17.07.2018  3.06.H04 Brede ,
Prof. Dr. Kreitz 		 
Kommentar Die Theoretische Informatik beschäftigt sich mit den grundlegenden Fragestellungen der Informatik. Hierzu werden Computer- und Automatenmodelle idealisiert und mathematisch untersucht.

Die Automatentheorie und die Theorie der formalen Sprachen (Thema des ersten Semesters) ist grundlegend für die Entwicklung von Programmiersprachen und Compilern. Sie untersucht, mit welchen Techniken welche Arten von Sprachen effizient analysiert werden können.
Die Berechenbarkeitstheorie befasst sich mit den prinzipiellen Grenzen des Berechenbaren und der Relation zwischen verschiedenen Computer- und Programmiermodellen. Die Komplexitätstheorie untersucht Effizienz von Algorithmen im Hinblick auf Platz- und Zeitbedarf und kümmert sich insbesondere um die Frage, wie effizient man bestimmte Probleme lösen kann.

Gliederung der Theoretischen Informatik II
* Berechenbarkeitstheorie o Turingmaschinen
o Rekursive Funktionen
o Lambda-Kalkül und arithmetische Repräsentierbarkeit
o Die Churchsche These
o Berechenbarkeit, Aufzählbarkeit und Entscheidbarkeit
o Unlösbare Probleme

* Komplexitätstheorie
o Konkrete Komplexitätsanalyse
o Komplexitätsklassen
o Handhabbarkeit: das P - NP Problem o NP-vollständige Problem
o Jenseits von NP-vollständigkeit
o Pseudopolynomielle und approximierende Algorithmen
o Probabilistische Lösung nichthandhabbarer Probleme
Literatur . Hopcroft, R. Motwani, J. Ullman: Einfuehrung in die Automatentheorie, Formale Sprachen und Komplexitaetstheorie, Pearson 2002

Michael Sipser: Introduction to the Theory of Computation. 2. Auflage, PWS 2005

J
Voraussetzungen Erfolgreiche Teilnahme an Theoretische Informatik I ist sehr zu empfehlen
Leistungsnachweis

Klausur zum Ende des vorlesungsfreien Zeitraums

Strukturbaum
Keine Einordnung ins Vorlesungsverzeichnis vorhanden. Veranstaltung ist aus dem Semester SoSe 2018 , Aktuelles Semester: SoSe 2024

© Copyright HIS
Hochschul-Informations-System eG