Modul: Einführung in die theoretische Informatik

Nummer:149667
Kürzel:EinfTheoInf
Verantwortlicher: Prof. Dr. Alexander May

Ziele

Der professionelle Umgang mit abstrakten, diskreten Strukturen wird beherrscht. 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. Die jeweils grundlegenden Konzepte (in Kombinatorik,Graphtheorie, elementarer Zahlentheorie und elementarer Wahrscheinlichkeitstheorie) wurden erworben. Die intellektuelle Fähigkeit, die logischen Zusammenhänge zwischen den Konzepten zu überblicken, und "versteckte" Anwendungsmöglichkeiten zu erkennen, wurde geschult.

Inhalt

Es wird eine Einführung in die Kodierungstheorie und in die Theorie der Berechenbarkeit gegeben.

  • Themenübersicht:
    • Turingmaschine
    • Komplexitätsklassen P und NP
    • Polynomielle Reduktion
    • Quadratische Reste
    • Eindeutig entschlüsselbare Codes
    • Kompakte und optimale Codes
    • Lineare und duale Codes

Veranstaltungen

Einführung in die theoretische Informatik (Jun. Prof. Dr. Nils Fleischhacker) 4 SWS