PULS
Foto: Matthias Friel
%%%%% 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
© Copyright HISHochschul-Informations-System eG