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

Theoretische Informatik II: Effiziente Algorithmen - Einzelansicht

Veranstaltungsart Vorlesung/Übung Veranstaltungsnummer 550421
SWS Semester SoSe 2020
Einrichtung Institut für Informatik und Computational Science   Sprache deutsch
Belegungsfrist 20.04.2020 - 10.05.2020

Belegung über PULS
Gruppe 1:
     jetzt belegen / abmelden
    Tag Zeit Rhythmus Dauer Raum Lehrperson Ausfall-/Ausweichtermine Max. Teilnehmer/-innen
Einzeltermine anzeigen
Vorlesung Mo 08:00 bis 10:00 wöchentlich 20.04.2020 bis 20.07.2020  3.06.H04 Dr. rer. nat. Böhne  
Einzeltermine anzeigen
Tutorium Di 08:00 bis 10:00 wöchentlich 21.04.2020 bis 21.07.2020  3.06.H04 Dr. rer. nat. Böhne ,
Frank
 
Einzeltermine anzeigen
Übung Mi 10:00 bis 12:00 wöchentlich 22.04.2020 bis 22.07.2020  3.06.S19 Dr. rer. nat. Böhne ,
Frank
 
Gruppe 2:
     jetzt belegen / abmelden
    Tag Zeit Rhythmus Dauer Raum Lehrperson Ausfall-/Ausweichtermine Max. Teilnehmer/-innen
Einzeltermine anzeigen
Vorlesung Mo 08:00 bis 10:00 wöchentlich 20.04.2020 bis 20.07.2020  3.06.H04 Dr. rer. nat. Böhne  
Einzeltermine anzeigen
Tutorium Di 08:00 bis 10:00 wöchentlich 21.04.2020 bis 21.07.2020  3.06.H04 Dr. rer. nat. Böhne ,
Frank
 
Einzeltermine anzeigen
Übung Mi 14:00 bis 16:00 wöchentlich 22.04.2020 bis 22.07.2020  3.01.H10 Dr. rer. nat. Böhne ,
Frank
17.06.2020: 
Einzeltermine anzeigen
Übung Mi 14:00 bis 16:00 Einzeltermin am 17.06.2020 3.06.H01 Dr. rer. nat. Böhne ,
Frank
 
Gruppe 3:
     jetzt belegen / abmelden
    Tag Zeit Rhythmus Dauer Raum Lehrperson Ausfall-/Ausweichtermine Max. Teilnehmer/-innen
Einzeltermine anzeigen
Vorlesung Mo 08:00 bis 10:00 wöchentlich 20.04.2020 bis 20.07.2020  3.06.H04 Dr. rer. nat. Böhne  
Einzeltermine anzeigen
Tutorium Di 08:00 bis 10:00 wöchentlich 21.04.2020 bis 21.07.2020  3.06.H04 Dr. rer. nat. Böhne ,
Frank
 
Einzeltermine anzeigen
Übung Do 12:00 bis 14:00 wöchentlich 23.04.2020 bis 23.07.2020  3.04.1.02 Dr. rer. nat. Böhne ,
Frank
 
Gruppe 4:
     jetzt belegen / abmelden
    Tag Zeit Rhythmus Dauer Raum Lehrperson Ausfall-/Ausweichtermine Max. Teilnehmer/-innen
Einzeltermine anzeigen
Vorlesung Mo 08:00 bis 10:00 wöchentlich 20.04.2020 bis 20.07.2020  3.06.H04 Dr. rer. nat. Böhne  
Einzeltermine anzeigen
Tutorium Di 08:00 bis 10:00 wöchentlich 21.04.2020 bis 21.07.2020  3.06.H04 Dr. rer. nat. Böhne ,
Frank
 
Einzeltermine anzeigen
Übung Fr 12:00 bis 14:00 wöchentlich 24.04.2020 bis 24.07.2020  3.06.S14 Dr. rer. nat. Böhne ,
Frank
 
Kommentar

%%%%% Wichtig %%%%%

- Schauen Sie sich bis spätestens 20.04. das erste Vorlesungsvideo an:

https://mediaup.uni-potsdam.de/Play/11633

Sie erhalten dort alle benötigten Informationen (insbsondere zum Zugang zum Moodle-Kurs)

- Sehen Sie sich spätestens bis zum 21.04. das Vorlesungsvideo zur Turing-Berechenbarkeit sowie das Video zu Loop-, While- und Goto-Programmen bis einschließlich Folie 33 an. Die Videos werden über Moodle verlinkt.

- Wählen Sie in der ersten Woche einfach eine Übungsgruppe aus (Zeiten in Moodle), bei der Sie teilnehmen wollen. Sie müssen nicht(!) über PULS für diese Übungsgruppe zugelassen worden sein.

%%%%% %%%%%%%%%%

 

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 Loop-, While- und Goto-Programme
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 Programmverifikation und -synthese

Literatur
  • Hopcroft, R. Motwani, J. Ullman: Einfuehrung in die Automatentheorie, Formale Sprachen und Komplexitaetstheorie, Pearson 2002
  • Hoffmann, Dirk: Theoretische Informatik, Hanser 2011
  • 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 2020 , Aktuelles Semester: SoSe 2024