I310 – Grundlagen der Informatik II

Modul
Grundlagen der Informatik II
Foundations of Computer Science II
Modulnummer
I310 [I-310]
Version: 2
Fakultät
Informatik/Mathematik
Niveau
Bachelor/Diplom
Dauer
1 Semester
Turnus
Sommersemester
Modulverantwortliche/-r

PD Prof. Dr.-Ing. habil. Hans-Joachim Böhme
hans-joachim.boehme(at)htw-dresden.de
Dozent/-in(nen)

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

Deutsch
in "Grundlagen der Informatik II"
ECTS-Credits

4.00 Credits

Workload

120 Stunden

Lehrveranstaltungen

3.00 SWS (2.00 SWS Vorlesung | 1.00 SWS Übung)
Selbststudienzeit

75.00 Stunden

Prüfungsvorleistung(en)
Keine
Prüfungsleistung(en)

Schriftliche Prüfungsleistung
Prüfungsdauer: 90 min | Wichtung: 100%
in "Grundlagen der Informatik II"
Lehrform

2/1/0  V/Ü/P
Medienform

Skripte, Folien, Arbeitsblätter, Aufgabensammlung
Lehrinhalte/Gliederung

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
Qualifikationsziele

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.
Sozial- und Selbstkompetenzen
Keine Angabe
Besondere Zulassungsvoraussetzung
Keine Angabe
Empfohlene Voraussetzungen

Aufbauend auf Grundlagen der Informatik I (I-110)
Fortsetzungsmöglichkeiten
Keine Angabe
Literatur
  • Skripte zur Lehrveranstaltung
  • Dirk W. Hoffmann: Theoretische Informatik, Hanser
Aktuelle Lehrressourcen
  • Skripte zur Lehrveranstaltung
  • Tutorials der Webseite NLogSpace: https://www.youtube.com/c/NLogSpace
  • Aufgabensammlung
Hinweise
Keine Angabe
Link zu Kurs/Lernressourcen im OPAL
https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/29611524098?4
Detailansicht schließen
© Modulux (Version 4.3)