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

Modul: Theoretische Grundlagen: Effiziente Algorithmen


Das hier aufgeführte Modul basiert auf in den Amtlichen Bekanntmachungen der Universität Potsdam veröffentlichten Studien- und Prüfungsordnungen.
Verbindliche Regelungswirkung haben nur die veröffentlichten Ordnungen.


INF-1021: Theoretische Grundlagen: Effiziente Algorithmen Anzahl der Leistungspunkte (LP):
6 LP
Modulart (Pflicht- oder Wahlpflichtmodul): Abhängig vom Studiengang (siehe unten)
Inhalte und Qualifikationsziele des Moduls:

Inhalte

Berechenbarkeit und ihre Grenzen, deterministische und nichtdeterministische Algorithmen, unlösbare Probleme. Komplexität, effiziente Algorithmen, nicht-handhabbare Probleme, Berechenbarkeits- und Komplexitätsklassen, NP-Vollständigkeit und Reduktionen. 

 

Qualifikationsziele

Die Studierenden

  • verstehen die Relation zwischen verschiedenen Computer- und Programmiermodellen
  • sind in der Lage, mit abstrakten Konzepten wie Entscheidbarkeit und Berechenbarkeit umzugehen
  • verstehen die prinzipiellen Grenzen des Berechenbaren
  • können die Komplexität von Algorithmen und Problemen abschätzen, effiziente Lösungsmuster erkennen und anwenden sowie die Angemessenheit und algorithmische Effizienz von Lösungsansätzen einordnen
  • verstehen den Zusammenhang verschiedener Komplexitätsklassen und der Grenzen des effizient Lösbaren. 
Modul(teil)prüfung (Anzahl, Form, Umfang, Arbeitsaufwand in LP):

Klausur, 180 Minuten

Selbstlernzeit (in Zeitstunden (h)): 90

Veranstaltungen
(Lehrformen)
Kontaktzeit
(in SWS)
Prüfungsnebenleistungen
(Anzahl, Form, Umfang)
Lehrveranstaltungsbegleitende Modul(teil)prüfung
(Anzahl, Form, Umfang)
Für den Abschluss des Moduls Für die Zulassung zur Modulprüfung
Vorlesung und Übung und Tutorium (Vorlesung und Übung) 6 -

erfolgreiche Bearbeitung von Testaten (50 %)

-

Häufigkeit des Angebots:

SoSe

Voraussetzung für die Teilnahme am Modul: keine
Anbietende Lehreinheit: Informatik
Zuordnung zu Studiengängen Modulart
Bachelor of Science Computerlinguistik WiSe 2017/18 Wahlpflichtmodul
Bachelor of Science Informatik/Computational Science WiSe 2013/14 Pflichtmodul
Bachelor of Science Informatik/Computational Science WiSe 2019/20 Pflichtmodul
Bachelor of Science Mathematik WiSe 2015/16 Wahlpflichtmodul
Master of Science Computational Science WiSe 2013/14 Wahlpflichtmodul