Информатика и вычислительная техника
  • формат doc
  • размер 534,71 КБ
  • добавлен 09 июня 2011 г.
Теория алгоритмов
Понятие алгоритма. Примеры. Способы задания. Общие свойства.
Необходимость математического уточнения понятия алгоритма.
Нормальный алгоритм Маркова.
Машины Тьюринга.
Сведение любого алгоритма к вычислению числовой функции.
Геделевская нумерация объектов.
Примитивно рекурсивные функ-ции.
Универсальная функция. Существование вычислимых, но не примитивно рекурсивных функций.
Частично рекурсивные функции. Тезис Чёрча.
Рекурсивные и рекурсивно перечислимые множества.
Примеры неразрешимых и нерешенных про-блем.
Похожие разделы