Автор: Пользователь скрыл имя, 14 Мая 2012 в 04:04, реферат
Теория вычислимости — это раздел современной математики и теории вычислений, возникший в результате изучения понятий вычислимости и не вычислимости. Изначально теория была посвящена вычислимым и невычислимым функциям и сравнению различных моделей вычислений. Сейчас поле исследования теории вычислимости расширилось — появляются новые определения понятия вычислимости, и идёт слияние с математической логикой, где вместо вычислимости и не вычислимости идёт речь о доказуемости и недоказуемости (выводимости и не выводимости) утверждений в рамках каких-либо теорий.
Глава 1 Ведение 1-3
Временная и пространственная сложности 1-4
Асимптотическая сложность 1-5
Классы сложности 1-6
Отношения между классами 1-8
Глава 2 Заключение. 2-10
Глава 3 Список использованной литературы. 3-11