Top
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
PULS
Foto: Matthias Friel
Datenschutz
Kontakt
Impressum
Universität Potsdam
Veranstaltungen
Modulbeschreibung
EN
SoSe 2024
Anmelden
Node1
Uni Homepage
Studium
Zugang zu Moodle
Anmeldungs- und Belegungsfristen
Verifikation von Studienbescheinigungen
Sie sind hier:
Startseite
Theoretische Informatik II: Effiziente Algorithmen - Einzelansicht
Funktionen:
belegen/abmelden
Veranstaltungsart
Vorlesung
Veranstaltungsnummer
550411
SWS
Semester
SoSe 2016
Einrichtung
Institut für Informatik und Computational Science
Sprache
deutsch
Weitere Links
Kommentar
Belegungsfristen
01.04.2016 - 10.05.2016
Belegung über PULS
01.04.2016 - 20.05.2016
Belegung über PULS
Gruppe 1:
Vormerken:
jetzt belegen / abmelden
Tag
Zeit
Rhythmus
Dauer
Raum
Lehrperson
Ausfall-/Ausweichtermine
Max. Teilnehmer/-innen
Vorlesung
Fr
08:00 bis 10:00
wöchentlich
15.04.2016 bis 24.06.2016
3.06.H04
Brede
,
Dr. rer. nat. Böhne
10.06.2016:
160
Vorlesung
Fr
08:00 bis 10:00
wöchentlich
10.06.2016 bis 15.07.2016
3.06.H01
Dr. rer. nat. Böhne
,
Brede
17.06.2016:
24.06.2016:
160
Vorlesung
Fr
08:00 bis 10:00
Einzeltermin
am 22.07.2016
3.06.H04
Dr. rer. nat. Böhne
,
Brede
160
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 zu Beginn des vorlesungsfreien Zeitraums
Strukturbaum
Keine Einordnung ins Vorlesungsverzeichnis vorhanden. Veranstaltung ist aus dem Semester SoSe 2016 , Aktuelles Semester: SoSe 2024
© Copyright HIS
Hochschul-Informations-System eG