Theoretische Grundlagen der Programmierung
|
|
|
|
|
Veranstaltungsnummer: 18.111 / 18.112 (Übungen in 8 Gruppen je 1 SWS) / 19.905 (Tutorien in 5 Gruppen je 1 SWS)
Titel: Theoretische Grundlagen der Programmierung
Veranstalter: Matthias Jantzen
Ort und Zeit: Mo 10-12, Do 10-12 (ESA-J)
Lernziel:
Kennenlernen grundlegender theoretischer Modelle, Begriffe, Methoden und Ergebnisse. Aneignung von wichtigen Techniken für die Analyse und das Verständnis der grundlegenden Berechnungs-, Kommu-nikations- und Beschreibungssysteme der Informatik (sequentielle, verteilte, probabilistische...). Kennenlernen von Beziehungen zwischen den grundlegenden Begriffen, Modellen und Methoden .
Inhalt:
- Grundmethoden der Komplexitätsanalyse
- Analyse der Algorithmen, Lösung von Rekurrenzgleichungen
- Asymptotische Analyse
- Grundbegriffe diskreter Mathematik
- Mengen, Relationen, Graphen, Bäume, Sprache
- Modelle von Automaten
- Endlicher Zweiweg-Automat, Stochastische endliche Automaten
- Zwischen endlichen Automaten und Turing Maschinen
- Turing Maschinen - Universalität, Simulationen
- Berechenbarkeit
- Rekursivität, Entscheidungsprobleme, Formale Systeme
- Modelle von universellen Computern
- Registermaschinen - RAM
- Parallele Registermaschinen - PRAM
- Zelluläre Automaten, Schaltkreise, Neuronale Computer
- Formale Systeme und Grammatiken
(über den Stoff des Grundstudiums hinausgehend)
- Chomsky Grammatiken und Automaten
- Kontextfreie Grammatiken
- Parallele Grammatiken
- Kryptographie
- Klassische Kryptographie
- Public-key Kryptographie und Anwendungen
- Komplexitätstheorie
- Vollständigkeit
- Komplexitätsklassen
- Kommunikationsmodelle
- Netzwerk-Eigenschaften, Relationen, Programmierung
- Hypercube-Eigenschaften, PRAM-Simulationen, Einbettungen
- Concurrency
- Grundmodelle und ihre Anwendungen
- Prozeßkonstruktion
Voraussetzung:
Grundstudium
Vorgehen:
Vorlesung
Literatur:
Periodizität:
jährlich
Bemerkungen:
Für Lehrer und Nebenfächler geeignet.