Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/03358.jsonl.gz/1709

Berechenbarkeit und Komplexität (BK)
- 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.
References:
Wird in der Vorlesung bekannt gegeben.