I310 – Foundations of Computer Science II

Module
Foundations of Computer Science II
Grundlagen der Informatik II
Module number
I310 [I-310]
Version: 2
Faculty
Informatics/Mathematics
Level
Bachelor/Diploma
Duration
1 Semester
Semester
Summer semester
Module supervisor

PD Prof. Dr.-Ing. habil. Hans-Joachim Böhme
hans-joachim.boehme(at)htw-dresden.de
Lecturer(s)

PD Prof. Dr.-Ing. habil. Hans-Joachim Böhme
hans-joachim.boehme(at)htw-dresden.de
Course language(s)

German
in "Grundlagen der Informatik II"
ECTS credits

4.00 credits

Workload

120 hours

Courses

3.00 SCH (2.00 SCH Lecture | 1.00 SCH Seminar)
Self-study time

75.00 hours

Pre-examination(s)
None
Examination(s)

Written examination
Examination time: 90 min | Weighting: 100%
in "Grundlagen der Informatik II"
Form of teaching

2/1/0  V/Ü/P
Media type

Skripte, Folien, Arbeitsblätter, Aufgabensammlung
Instruction content/structure

1. Einführung in die Theoretische Informatik

  • Historische Entwicklung
  • Teilgebiete

2. Mathematische Grundlagen

  • Mengenbegriff, Mengenoperationen, Potenzmenge
  • Relationen und Funktionen
  • Zahlen: natürliche, rationale und reelle Zahlen
  • Rekursion und induktive Beweise

3. Formale Sprachen und endliche Automaten

  • Sprache und Grammatik, Chomsky-Hierarchie
  • Reguläre, kontextfreie und kontextsensitive Sprachen
  • Deterministische und nichtdeterministische endliche Automaten
  • Kellerautomaten
  • Turing-Maschine

4. Berechenbarkeit und Entscheidbarkeit

  • Berechnungsmodelle: Loop-, While-, Goto-Programme, primitiv-rekursive Funktionen, Turing-Maschinen
  • Definition von Entscheidbarkeit
  • Konzept der charakteristischen Funktion
  • Unentscheidbare Probleme

5. Komplexitätstheorie

  • Algorithmische Komplexität, O-Kalkül, Rechnen im O-Kalkül
  • Komplexitätsklassen
  • NP-Vollständigkeit

6. Zusammenfassung

  • Wechselbeziehungen zwischen den einzelnen behandelten Konzepten
Qualification objectives

Die Studierenden sollen nach dem Absolvieren der Lehrveranstaltung

  • die Grundkonzepte der Theoretischen Informatik kennen und verstehen,
  • algorithmische und strukturelle Problemstellungen analysieren und einordnen sowie
  • die vermittelten Konzepte sicher auf diese Problemstellungen anwenden können.
Social and personal skills
No information
Special admission requirements
No information
Recommended prerequisites

Aufbauend auf Grundlagen der Informatik I (I-110)
Continuation options
No information
Literature
  • Skripte zur Lehrveranstaltung
  • Dirk W. Hoffmann: Theoretische Informatik, Hanser
Current teaching resources
  • Skripte zur Lehrveranstaltung
  • Tutorials der Webseite NLogSpace: https://www.youtube.com/c/NLogSpace
  • Aufgabensammlung
Notes
No information
Link to course/learning resources in OPAL
https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/29611524098?4
Close detail view
© Modulux (Version 4.3)