course: Introduction to Theoretical Computer Science

number:

150310

teaching methods:

lecture with tutorials

media:

black board and chalk

responsible person:

Jun. Prof. Dr. Nils Fleischhacker

lecturer:

Jun. Prof. Dr. Nils Fleischhacker (Mathematik)

language:

german

HWS:

4

CP:

6

offered in:

summer term

dates in summer term

• start: Monday the 20.04.2020

Exam

All statements pertaining to examination modalities (for the summer/winter term of 2020) are given with reservations. Changes due to new requirements from the university will be announced as soon as possible.

goals

The students master the professional interaction with abstract, discrete structures. This includes the ability to model concrete problems with such structures and to draw subtle conclusions from given information. It also includes the knowledge of basic alorithmic techniques and the analysis of algorithms. The basic concepts (in combinatorics, graph theory, elementary number theory, and elementary probability theory) have been learned in the single sections of the lecture. The intellectual ability to overview the logic connections between the concepts and to realize "hidden" possible applications have been trained.

content

The course gives an introduction to coding theory and the theory of computability

• Topic Overview:
  • Turing machine
  • Complexity classes P and NP
  • Polynomial-time reduction
  • Quadratic residues
  • Uniquely decodable codes
  • Compact and optimal codes
  • Linear and dual codes

requirements

keine

recommended knowledge

Basic knowledge of discrete mathematics and algorithms.

miscellaneous

SOMMERSEMESTER 2020

Willkommen zu Vorlesung Einführung in die theoretische Informatik. Aufgrund der außergewöhnlichen Situation wird die Vorlesung, auch nach Vorgaben der Universität, in diesem Jahr komplett ohne Präsenzlehre stattfinden. Wir möchten hier über den Ablauf der Vorlesung und der Übungen informieren.

Für die Vorlesung stellen wir für jede Woche eine Aufzeichnung bereit, die Sie in dieser Woche bearbeiten sollten. Selbstverständlich können Sie jederzeit hier im moodle Fragen zum behandelten Stoff stellen. Zusätzlich wird jede Woche, in der Regel Freitags von 11:00 - 12:00 eine Fragestunde bei Prof. Fleischhacker per Videokonferenz stattfinden.

Die Präsenzübungen werden beginnend mit der Woche vom 27. April alle zwei Wochen stattfinden. Die Präsenzübungen finden hier im moodle in Form von Diskussionsforen statt. Hierzu wird es zu jeder Aufgabe ein gesondertes Diskussionsforum geben, in dem Sie Fragen stellen und diskutieren können. Eine aktive Betreuung in diesen Foren findet in den Wochen mit Präsenzübung Montags von 09:00 bis 12:00 und Dienstags von 13:00 bis 16:00 statt.

Die Hausübungen werden zeitgleich mit den Präsenzübungen ausgegeben und die Lösungen sind stets in der Zwischenwoche Donnerstags bis 12:00 hier im moodle als PDF-Datei abzugeben.

Link zum Moodle-Kurs: https://moodle.ruhr-uni-bochum.de/m/course/view.php?id=25685