Введение в схемы, автоматы и алгоритмы



             

Что такое алгоритм? - часть 2


А затем сравним их с двумя другими моделями алгоритмов: описаниями частично рекурсивных функций и машинами Тьюринга.

Хотя алгоритмы в разных прикладных областях имеют дело с дискретными объектами различных видов: целыми и рациональными числами, строками, формулами, разного рода выражениями, графами, матрицами, таблицами, точечными изображениями и др., мы в этой части курса будем рассматривать только задачи вычисления функций от натуральных аргументов, принимающих натуральные значения. Такие функции часто называют арифметическими. Дело в том, что для любого естественного множества дискретных объектов (в частности, для всех перечисленных выше) имеется простое кодирование его элементов целыми числами. Поэтому задачи вычисления функций на этих множествах превращаются в задачи вычисления арифметических функций.

Напомним, что через N обозначается множество натуральных чисел, т.е. N={0,1,2,…}. Для частичной n- местной арифметической функции f: Nn

N через ?f обозначим область ее определения. Чтобы указать, что f не определена на некотором наборе чисел a1,…, an будем писать f(a1,…, an)=?, а если f на этом наборе определена, то будем писать f(a1,…, an) < ?. Таким образом,
f ={ (a1,…, an) | f(a1,…, an) < ? }.




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