Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Топ:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Оснащения врачебно-сестринской бригады.
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Интересное:
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Дисциплины:
2023-02-03 | 26 |
5.00
из
|
Заказать работу |
26Вычислимые функции и их алгоритмы
вычислимой называется функция от одного или нескольких натуральных аргументов, натуральные значения которой получаются в результате выполнения некоторого алгоритма. Определить термин "алгоритм" без синонимичных ссылок на себя же самого сложно. Фразы типа "дискретные, однозначные последовательные действия..." не являются полностью удовлетворительными. Поэтому считается, что "алгоритм", как и "множество" — это понятие первичное. Для определённости будем считать, что алгоритм это математическая модель уже существующего физического устройства — цифрового компьютера. У него идеализируется память, которая может быть сколь угодно большой. Естественно, исключаются и форс-мажорные ситуации - перегрев, блондинки, чашки с кофе и т.п. Поэтому вычислимой будет функция, для которой можно составить программу, т.е. дать конечное определение, позволяющее вычислить функцию при помощи этого идеального устройства.
Программа — это конечная строка символов из некоторого, опять же конечного алфавита. Компьютер имеет вычислитель (маркер), который однозначным образом перемещается по строке (тексту программы). Это перемещение не обязательно линейно, и при достижении некоторого символа возможен переход на несколько символов вперёд или назад.
Таким образом есть программа (строка " ") и вычислитель (маркер), который на данном шаге выполнения алгоритма указывает на один символ — инструкцию для компьютера (на рисунке выше это треугольник, стоящий на инструкции " ").
Программы записываются на некотором формальном языке программирования. Это может быть язык машины Тьюринга, ассемблер для процессоров с бесконечной разрядностью, или С++, в котором нет ограничения на размер целочисленных переменных. Формальный язык определяется при помощи синтаксических правил. Это означает, что всегда можно отличить "бессмысленную" последовательности символов от тех, по которым может перемещаться вычислитель. Ситуация полностью аналогична, например, арифметике, где правильно построенная формула " " отличима от неправильной: " ".
Одна и та же функция может быть описана при помощи различных алгоритмов, каждый из которых может быть представлен различными программами (использующими различный алфавит и синтаксис).
Кроме программы и вычислителя существует память, в которую могут помещаться натуральные числа, вычисляющиеся по мере выполнения алгоритма. Память можно считать некоторым бесконечным упорядоченным множеством . Величины называются "ячейками памяти". Перед началом работы алгоритма, все , для определённости, равны нулю. В момент "запуска" алгоритма на выполнение, в первые элементы памяти помещаются значения входных аргументов функции . Порядок перемещения вычислителя по тексту программы зависит как от символов программы, так и от значений чисел в памяти (начальных или "промежуточных").
Таким образом, компьютер состоит из конечной программы , вычислителя , указывающего на выполняемую инструкцию, и неограниченной памяти , в которую могут помещаться и считываться натуральные числа. Ниже приведен пример трёх последовательных шагов некоторого алгоритма, вычисляющего функцию одной переменной при :
При вычислении значения любой функции, компьютер получает на вход значение аргументов этой функции и помещает их в память . Затем он начинает перемещать вычислитель по тексту программы, изменяя значения чисел в памяти. При достижении некоторого символа происходит остановка вычислителя и выдача значения функции. Вообще говоря, возможна ситуация, когда перемещение по строке программы никогда не заканчивается, или вычислитель дошёл до конца строки не встретив символа остановки. В этих случаях считается, что значение функции не определено. Другими словами, вычислимая функция не является обязательно всюду определённой функцией.
Функция — это "ящик" с несколькими входами , и одним выходом :
Фразы "один вход" или "один выход" не являются принципиальными. Понятно, что упорядоченных целых чисел всегда можно представить как одно, и наоборот. Для этого достаточно взять первых простых чисел и вычислить . Обратная операция разложения на простые множители одного числа позволяет восстановить значения всех . Тем не менее, будем считать, что может быть несколько входов, но выход всегда один.
Понятие конструктивного объекта
Сложилось представление, что в качестве исходных данных и результатов алгоритма могут выступать не любые объекты. Алгоритмы могут иметь дело только с комбинациями знаков. Объекты, над которыми "работает" алгоритм, обычно называют конструктивными. Понятие "конструктивный объект" - это неформализованное, интуитивное понятие, его формирование связано с различением конструктивного и неконструктивного в математическом мышлении. Пояснение того, что следует понимать под конструктивным объектом дали В.А.Успенский и А.Л.Семёнов [1987]: это "такой объект, который может быть набран весь целиком и представлен нам для рассмотрения". Конструктивный объект должен быть конечным (в интуитивном понимании этого слова) и составленным из конечного числа отдельных элементов, каждый из которых принадлежит одному из конечного числа типов. Однако, конструктивный объект - это не просто конечное множество элементов. Конструктивный объект должен иметь, кроме того, некоторую внутреннюю систему координат, позволяющую однозначно локализовать любой его элемент (второй элемент справа, элемент пятой строки и третьего столбца и т.д.).
Примерами конструктивных объектов служат слова в алфавите. Частными видами слов, очевидно, являются формулы формальных языков, записи натуральных, целых чисел в g-ичной системе счисления, записи рациональных чисел в виде обыкновенных дробей, конечные десятичные дроби, многочлены с рациональными коэффициентами (в том случае, если их коэффициенты записаны в виде слов). Конструктивными объектами являются также конечные матрицы слов и булевы функции.
Слова в алфавите (конечные последовательности символов) - удачный вид конструктивных объектов, поскольку современные компьютеры читают и обрабатывают информацию, вообще говоря, посимвольно и последовательно. Последовательные одномерные записи привычны и для человека. Кроме того, интуитивно ясно, что всякий конструктивный объект можно однозначно и полностью описать или закодировать в виде слова, и на практике это всегда удается. В силу этого, именно слова в алфавите являются главным видом конструктивных объектов. Поэтому обычно ограничиваются изучением алгоритмов, у которых исходные данные и результаты являются непустыми словами. Разумно также соображение о том, что исполнитель алгоритма может различать лишь конечное число исходных символов, поэтому в качестве множества допустимых данных алгоритма и областей результатов рассматривают лишь множества слов в конечных алфавитах.
Впрочем, следующее утверждение показывает, что в некотором смысле достаточно исследовать только те алгоритмы и соответствующие вычислимые функции, у которых в качестве исходных данных и результатов используются только натуральные числа (точнее, их записи).
Занумеруем элементы произвольного конечного алфавита A«{a0,a1,...,ap-1}.
Пусть A+ - множество всех непустых слов в алфавите A, wÎA+. Тогда для некоторых k0,k1,...ksÎ{0,1,...,p-1}
w=ak ak ...ak (*)
0 1 s
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!