Modulcode:	Inf-I2-2F
Englische Bezeichnung:	Computer Science II
Modulverantwortliche(r):	Prof. Dr. Andreas Mühling
Turnus:	jedes Jahr im SS (SS17 SS18)
Präsenzzeiten:	4V 2Ü
ECTS:	8
Workload:	60 Std. Vorlesung, 30 Std. Übung, 150 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	2F-BSc (2F-BSc Inf) NF (Inf. als NF)
Lehrsprache:	Deutsch
Voraussetzungen:

Kurzfassung:

Lernziele:

• Komplexere Programme unter Verwendung effizienter Datenstrukturen entwickeln.
• Effiziente Algorithmen implementieren und deren Laufzeit analysieren.
• Objektorientiert modellieren und diese Modellierung in der Programmierung verwenden.
• Reguläre Ausdrücke, endliche Automaten, kontextfreie Grammatiken und Kellerautomaten für formale Sprachen endwickeln und deren Korrektheit begründen.
• Für einfachere formale Sprachen einschätzen, ob sie regulär oder kontextfrei sind, und die Einschätzung begründen.
• Automatentheoretische und verwandte Konstruktionen allgemein beschreiben und im Einzelfall anwenden.
• Für einfachere Probleme einschätzen, ob sie entscheidbar sind, und die Einschätzung begründen.
• Deterministische und nichtdeterministische Polynomzeitalgorithmen entwickeln.
• Für einfachere Probleme einschätzen, ob sie in polynomieller Zeit determinisch oder nichtdeterministisch lösbar sind, und die Einschätzung begründen.
• Die Bedeutung des Nichtdeterminismus, der Klasse NP und des Entscheidbarkeitsbegriffs erklären.
• Wie man prinzipielle und praktische Grenzen der Lösbarkeit von Problemen formalisiert, erklären.

Lehrinhalte:

• fortgeschrittene Themen der Programmiersprache Ruby
• Dynamischer Datenstrukturen
• Effiziente Algorithmen
• Analyse von Algorithmen
• objektorientierte Datenmodellierung
• reguläre Sprachen: reguläre Ausdrücke, deterministische und nichtdeterministische endliche Automaten, Begriff der regulären Sprache, Konstruktionen zu regulären Sprachen
• kontextfreie Sprachen: kontextfreie Grammatiken, Kellerautomaten, Begriff der kontextfreien Sprache, Konstruktionen zu kontextfreien Sprachen
• Berechenbarkeit: Programm als Grundlage für einen semi-formalen Berechen- und Entscheidbarkeitsbegriff, Begriff der berechenbaren Funktion und des entscheidbaren Problems, Diagonalisierung, Unentscheidbarkeit
• Komplexität: pessimale Laufzeit, P, NP

Weitere Voraussetzungen:

Die in der Beschreibung des Moduls Inf-I1-2FNF aufgeführten Lernziele.

Prüfungsleistung:

Prüfungsgespräch

Lehr- und Lernmethoden:

Verwendbarkeit:

Literatur:

M. Sipser: Introduction to the Theory of Computation, 3rd ed., Cengage Learning, Boston, 2013, ISBN 978-1-133-18779-0

Verweise:

Kommentar: