Einfuhrung in die theoretische Informatik

NUMMER: 150310
KÜRZEL: EinTI
MODULBEAUFTRAGTE:R: Prof. Dr. Alexander May
DOZENT:IN: Prof. Dr. Alexander May
FAKULTÄT: Fakultät für Informatik
SPRACHE: Deutsch
SWS: 4
CREDITS: 6
WORKLOAD: 180 Stunden
ANGEBOTEN IM: jedes Sommersemester

PRÜFUNGEN

FORM: schriftlich
ANMELDUNG:
DATUM: 0000-00-00
BEGINN: 00:00:00
DAUER: 120 Minuten
RAUM:

LERNFORM

Vorlesungen und Übungen

LERNZIELE

Die Studierenden beherrschen den professionellen Umgang mit abstrakten, diskreten
Strukturen. Dazu gehört die Fähigkeit, konkrete Problemstellungen mit solchen Strukturen zu modellieren, und scharfsinnige Schlussfolgerungen aus gegebenen Informationen zu ziehen. Dazu
gehört weiterhin ein Verständnis für grundlegende algorithmische Techniken und die Analyse ¨
von Algorithmen. In den einzelnen Abschnitten der Vorlesung wurden die jeweils grundlegenden
Konzepte (in Kombinatorik, Graphtheorie, elementarer Zahlentheorie und elementarer Wahrscheinlichkeitstheorie) erlernt. Die intellektuelle Fähigkeit, die logischen Zusammenhänge zwischen den Konzepten zu überblicken, und “versteckte” Anwendungsmöglichkeiten zu erkennen, wurde geschult.

INHALT

Die Vorlesung gibt eine Einführung in die Kodierungstheorie und in die Theorie der Berechenbarkeit.
• Themen Übersicht:
– Turingmaschine
– Komplexitätsklassen P und NP
– Polynomielle Reduktion
– Quadratische Reste
– Eindeutig entschlusselbare Codes
– Kompakte und optimale Codes
– Lineare und duale Codes

VORAUSSETZUNGEN CREDITS

Keine

EMPFOHLENE VORKENNTNISSE

Grundkenntnisse über Diskrete Mathematik und Algorithmen