Berechenbarkeit und Komplexität (BK)

Lecturer:
Assistants:
Lecture number: 2404-FS2017-0
ECTS: 5
Start: 2017-02-22
End: 2017-05-31
Venue: Hörsaal B007, ExWi, Sidlerstrasse 5
Repetition: Jährlich
Lectures take place on:
  • Wednesday from 14:15 to 17:00

Description:

Im Zentrum des ersten Teils der Vorlesung stehen verschiedene Formalisierungen des intuitiven Algorithmusbegriffs und die These von Church. Die Konzepte der algorithmischen Entscheidbarkeit und Semi-Entscheidbarkeit sowie die Grenzen der theoretischen Berechenbarkeit werden eingehend untersucht. Im zweiten Teil der Vorlesung wird eine kurze Einführung in die Komplexitätstheorie gegeben; dabei werden die Grenzen der praktischen Berechenbarkeit besprochen. Im Vordergrund stehen die Klassen P und NP, die Theorie der NP-Vollständigkeit und die P != NP Vermutung.

KSL-Link: https://www.ksl.unibe.ch/KSL/kurzansicht?...

References:

Wird in der Vorlesung bekannt gegeben.