Конспект установочных лекций по комплексному курсу Информатика, Теория информации




Постановка вопроса


Не все постановки задач информационной обработки могут быть решены с помощью алгоритмов. Точнее говоря, существуют задачи, которые могут быть математически точно описаны («формализуемы»), но для решения, которых не существует алгоритмов. Здесь рассматривается задача вычисления некоторой определенной функции. Эта задача решается по алгоритму, который вычисляет функцию, описанную в постановке задачи. Если существует алгоритм для вычисления некоторой функции, то она вычислима. Итак, функция f (которая определена постановкой задачи) называется вычислимой, если существует алгоритм, который для любого аргумента х (в качестве входа для алгоритма) вычисляет значение f(x) (как выход алгоритма). Тем самым понятие вычислимости сводится к понятию алгоритма. В частности, высказывание о вычислимости функции зависит от выбора понятия алгоритма.

Существует несколько различных подходов к формализации понятия алгоритма. Некоторые выбранные из этих подходов обсуждаются в этой работе и в заключение показано, что предложенные до сих пор понятия алгоритма приводят к одинаковому понятию вычислимости.

Здесь вычисляются n-местные функций

f: N” -> N

над натуральными числами. Вводимые и исследуемые в дальнейшем понятия вычислимости распространяются на любые области определений и значений функций.

Можем производить вычисления только на представлениях элементов из N, а не на самих этих элементах, для представления чисел будут использоваться множества Т знаков и инъективное отображение

rep: N -> Т*,

которое устанавливает представление чисел в виде слов над Т.  Предполагается, что отображение rep обратимо на свой прообраз, поскольку только в этом случае  получается однозначное представление чисел. В соответствии с этим существует отображение

abs: {t Î Т*: $ nÎ N : гер(n) = t} -> N,

так что для отображений rep и abs справедливы равенства

abs . rep = id,

rep . abs = id.

Эта методика перевода конкретных представлений в множество абстрактных информаций с помощью функции абстракции abs типична для, образа действий специалиста по информатике. ,




Содержание  Назад  Вперед