Veranstaltung: Einführung in die theoretische Informatik

Nummer:
150310
Lehrform:
Vorlesung und Übungen
Medienform:
Tafelanschrieb
Verantwortlicher:
Prof. Dr. Alexander May
Dozent:
Prof. Dr. Alexander May (Mathematik)
Sprache:
Deutsch
SWS:
4
LP:
6
Angeboten im:
Sommersemester

Termine im Sommersemester

  • Beginn: Freitag den 21.04.2017
  • Vorlesung Freitags: ab 09:00 bis 12.00 Uhr im HID
  • Übung (alternativ) Dienstags: ab 12:00 bis 14.00 Uhr im ND 3/99
  • Übung (alternativ) Mittwochs: ab 12:00 bis 14.00 Uhr im UFO 0/1

Prüfung

Schriftliche Prüfung am 28.02.2018

Dauer: 120min
Prüfungsanmeldung: FlexNow
Beginn: 10:30

Raum:

HNC 10: Alle Studierenden

Ziele

Die Studierenden beherrschen den pro­fes­sio­nel­len Um­gang mit abs­trak­ten, dis­kre­ten Struk­tu­ren. Dazu ge­hört die Fä­hig­keit, kon­kre­te Pro­blem­stel­lun­gen mit sol­chen Struk­tu­ren zu mo­del­lie­ren, und scharf­sin­ni­ge Schluss­fol­ge­run­gen aus ge­ge­be­nen In­for­ma­tio­nen zu zie­hen. Dazu ge­hört wei­ter­hin ein Ver­ständ­nis für grund­le­gen­de al­go­rith­mi­sche Tech­ni­ken und die Ana­ly­se von Al­go­rith­men. In den ein­zel­nen Ab­schnit­ten der Vor­le­sung wurden die je­weils grund­le­gen­den Kon­zep­te (in Kom­bi­na­to­rik, Graph­theo­rie, ele­men­ta­rer Zah­len­theo­rie und ele­men­ta­rer Wahr­schein­lich­keits­theo­rie) er­lernt. Die in­tel­lek­tu­el­le Fä­hig­keit, die lo­gi­schen Zu­sam­men­hän­ge zwi­schen den Kon­zep­ten zu über­bli­cken, und "ver­steck­te" An­wen­dungs­mög­lich­kei­ten zu er­ken­nen, 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 entschlüsselbare Codes
    • Kompakte und optimale Codes
    • Lineare und duale Codes

Voraussetzungen

keine

Empfohlene Vorkenntnisse

Grundkenntisse über Diskrete Mathematik und Algorithmen

Sonstiges

Zur Vorlesung existiert ein Skript.

There exist lecuture notes.