Theoretische Grundlagen der Informatik

Navigation Zur Modulseite
PDF PDF generieren
Anzeigesprache

Theoretische Grundlagen der Informatik

6 LP

Deutsch

#40743 / #7

Seit WS 2017/18

Fakultät IV

MAR 5-3

Institut für Softwaretechnik und Theoretische Informatik

34351100 FG Algorithmik und Komplexitätstheorie

Sprekeler, Henning

Sprekeler, Henning

h.sprekeler@tu-berlin.de

http://www.cognition.tu-berlin.de/menue/teaching/

POS-Nummer PORD-Nummer Modultitel
7030 30173 Theoretische Grundlagen der Informatik

Lernergebnisse

Die Studierenden sind in der Lage, die grundlegenden Begriffe und Formalismen der Diskreten Mathematik eigenständig anzuwenden. Sie beherrschen den Umgang mit formalen Sprachen und Grammatiken sowie mit den wichtigsten theoretischen Maschinenmodellen. Sie besitzen ein Verständnis der grundlegenden Komplexitätsklassen und sind befähigt, die Komplexität ausgewählter Beispielprobleme zu beurteilen.

Lehrinhalte

- Mengen, Logik, Abbildungen, Relationen, Ordnungen - Grammatiken, Chomsky-Hierarchie - endliche Automaten, Kellerautomaten, Turingmaschinen, Berechenbarkeit - Aufwand von Algorithmen und Komplexität von Problemen - Komplexität von Wortproblemen der Chomsky-Hierarchie - P, NP und NP-Vollständigkeit

Modulbestandteile

Pflichtteil:

Die folgenden Veranstaltungen sind für das Modul obligatorisch:

Lehrveranstaltungen Art Nummer Turnus Sprache SWS
Theoretische Grundlagen der Informatik IV 0434 L 370 WS/SS Keine Angabe 4

Arbeitsaufwand und Leistungspunkte

Theoretische Grundlagen der Informatik (IV):

Aufwandbeschreibung Multiplikator Stunden Gesamt
Präsenzzeit 15.0 4.0h 60.0h
Vor- und Nachbereitung, Übungsaufgaben 15.0 8.0h 120.0h
180.0h (~6 LP)
Der Aufwand des Moduls summiert sich zu 180.0 Stunden. Damit umfasst das Modul 6 Leistungspunkte.

Beschreibung der Lehr- und Lernformen

Die fachlichen Inhalte des Moduls werden im Vorlesungsstil vermittelt. Die Anwendung und Festigung des Stoffs geschieht durch das Besprechen von Übungsaufgaben im interaktiven Stil.

Voraussetzungen für die Teilnahme / Prüfung

Wünschenswerte Voraussetzungen für die Teilnahme an den Lehrveranstaltungen:

keine

Verpflichtende Voraussetzungen für die Modulprüfungsanmeldung:

1. Voraussetzung:
[MKP] 50 % der Punkte in den Übungsaufgaben

Abschluss des Moduls

Benotung:

benotet

Prüfungsform:

Schriftliche Prüfung

Sprache:

Deutsch

Dauer/Umfang:

150 Minuten

Dauer des Moduls

Dieses Modul kann in einem Semester abgeschlossen werden.

Maximale teilnehmende Personen

Dieses Modul ist nicht auf eine Anzahl Studierender begrenzt.

Anmeldeformalitäten

Die Anmeldung erfolgt entweder über QISPOS (BSc Informatik, Wirtschaftsinformatik, Technische Informatik) oder direkt beim Prüfungsamt.

Literaturhinweise, Skripte

Skript in Papierform

Verfügbarkeit:  nicht verfügbar

Skript in elektronischer Form

Verfügbarkeit:  verfügbar
Zusätzliche Informationen:
Vorlesungsfolien sind unter www.isis.tu-berlin.de verfügbar.

Literatur

Empfohlene Literatur
Automata, Computability, and Complexity. Elaine Rich. Pearson Education (2008).
Diskrete Mathematik für Informatiker. Rod Haggarty. Pearson Studium (2004).
Einführung in die Automatentheorie, Formale Sprachen und Berechenbarkeit. Hopcroft, Motwani & Ullman. Pearson Studium, 3. Auflage (2011).
Theoretische Informatik - kurz gefasst. Uwe Schöning. Spektrum Akademischer Verlag, 5. Auflage (2008).

Zugeordnete Studiengänge

Dieses Modul wird auf folgenden Modullisten verwendet:

Sonstiges

Keine Angabe