Veranstaltung: Einführung in die theoretische Informatik

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

Termine im Sommersemester

  • Beginn: Freitag den 05.04.2019
  • Vorlesung Freitags: ab 09:00 bis 12.00 Uhr im HID
  • Übung (alternativ) Montags: ab 10:00 bis 12.00 Uhr im NB 3/99
  • Übung (alternativ) Montags: ab 12:00 bis 14.00 Uhr im IA 1/71
  • Übung (alternativ) Montags: ab 12:00 bis 14.00 Uhr im NB 2/99
  • Übung (alternativ) Dienstags: ab 12:00 bis 14.00 Uhr im ND 3/99
  • Zusatzübung (alternativ) Dienstags: ab 14:00 bis 16.00 Uhr im NB 02/99

Prüfungen

Prüfungsform:schriftlich
Prüfungsanmeldung:FlexNow
Datum:27.02.2019
Beginn:10:30
Dauer:120min
Raum: HZO 30
Prüfungsform:schriftlich
Prüfungsanmeldung:FlexNow
Datum:07.08.2019
Beginn:08:30
Dauer:120min
Räume: HIA ,  HIC ,  HID
Die Hörsaalaufteilung wird vom Lehrstuhl bekannt gegeben.

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.