Grundbegriffe der Informatik — Wintersemester 2022/23

Dr. Mattias Ulbrich,
Philipp Kern
am Institut für Theoretische Informatik.

Typ: Vorlesung
Zielgruppe: Bachelor Informatik (Orientierungsprüfung)
Umfang: 3+1 SWS / 6 Leistungspunkte
Ort: Audimax-Hörsaal, (und HS -101 und HS -102 in Gebäude 50.34)
Zeit: Mittwoch, 9:45 - 11:15 Uhr
Freitag, 9:45 - 11:15 Uhr
Veranstaltungs-Nr.: 24001
ILIAS-Kurs: s.kit.edu/gbi

Die Vorlesung „Grundbegriffe der Informatik“ ist Teil der Orientierungsprüfung Informatik. Die Orientierungsprüfung ist spätestens bis zum Ende des dritten Fachsemesters zu bestehen, einschließlich etwaiger Wiederholungen. Sie dient der Kontrolle, ob die für das weiterführende Studium relevanten Grundkenntnisse erworben wurden.

Aus dem Modulhandbuch

Qualifikationsziele

  • Die Studierenden kennen grundlegende Definitionsmethoden und sind in der Lage, entsprechende Definitionen zu lesen und zu verstehen.
  • Sie kennen den Unterschied zwischen Syntax und Semantik.
  • Die Studierenden kennen die grundlegenden Begriffe aus diskreter Mathematik und Informatik und sind in der Lage sie richtig zu benutzen, sowohl bei der Beschreibung von Problemen als auch bei Beweisen

Inhalt

  • Algorithmen informell, Grundlagen des Nachweises ihrer Korrektheit
  • Berechnungskomplexität, „schwere“ Probleme
  • O-Notation, Mastertheorem
  • Alphabete, Wörter, formale Sprachen endliche Akzeptoren, kontextfreie Grammatiken
  • induktive/rekursive Definitionen, vollständige und strukturelle Induktion Hüllenbildung
  • Relationen und Funktionen
  • Graphen
  • Syntax für Aussagenlogik und Prädikatenlogik, Grundlagen ihrer Semantik

Themenauswahl

  • Mengen, Alphabete
  • Wörter, formale Sprachen
  • Aussagenlogik, Prädikatenlogik
  • Induktives Vorgehen
  • Übersetzungen, Codierungen
  • Speicher
  • Prozessor
  • Dokumente
  • kontextfreie Grammatiken
  • Begriff des Algorithmus
  • Graphen
  • Algorithmen in Graphen
  • Quantitative Aspekte von Algorithmen
  • endliche Automaten, reguläre Ausdrücke
  • Turingmaschinen
  • Relationen

Organisatorische Hinweise und Materialien ...

finden Sie im Ilias-Kurs unter s.kit.edu/gbi. Kontaktieren Sie ggf. die Dozierenden, falls Sie Probleme beim Zugriff haben.