6Berechenbarkeitstheorie
Berechenbarkeits- und Komplexitätstheorie (vgl. Kapitel 7) heißen die Teildisziplinen der theoretischen Informatik, die versuchen, eine Ordnung der Probleme im Hinblick auf die Schwierigkeit ihrer Berechnung herzustellen. Tabelle 6.1 vermittelt einen ersten unformalen Einblick in das, womit wir uns in diesem und dem nächsten Kapitel beschäftigen werden. Ein wichtiges Ziel dieser beiden Kapitel ist, Probleme in eine der dort gelisteten fünf Hauptstufen der „Lösbarkeit“ einordnen zu können.
Um dieses Ziel überhaupt fassen zu können, müssen wir ein paar grundsätzliche Begriffe wiederholen. Zunächst einmal sind Probleme mathematische Objekte, wie wir sie in Kapitel 1 definiert haben. Sie bestehen aus einer Menge von Fragestellungen ...
Get Theoretische Informatik - ganz praktisch now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
