Теория алгоритмов, Игошин

Теория алгоритмов Игошин это учебник для студентов технических ВУЗов. Рассматривается ещё одна формализация интуитивного понятия алгоритма — теория нормальных алгоритмов (или алгорифмов, как называл их создатель теории). Эта теория была разработана советским математиком А.А.Марковым (1903 — 1979) в конце 40-х — начале 50-х годов XX века. Эти алгоритмы представляют собой некоторые правила по переработке слов в каком-либо алфавите, так что исходные данные и искомые результаты для алгоритмов являются словами в некотором алфавите. В качестве элементарной операции, на базе которой будут строиться нормальные алгоритмы, А.А.Марков выделил подстановку в слово одного подслова вместо другого. Хотите знать больше? Начните Теория алгоритмов Игошин читать онлайн и 2016 год станет дл вас еще успешнее. В силу единственности разложения числа на простые множители, данное отображение будет взаимно однозначным, т.е. разные слова из А1* не могут получить один и тот же номер, т.е. отображение Nom действительно является нумерацией слов.

Но отображение Norn не является отображением НА N, т.е. не каждое натуральное число является номером некоторого слова из А1*. Тем не менее, нумерация Nom является эффективной в том смысле, что можно указать алгоритм, который для любого натурального числа п определяет, является ли п номером в данной нумерации какого-либо слова из ЛГ, и если да, то строит (восстанавливает) слово, имеющее номер п. Этот алгоритм также основан на свойстве единственности представления всякого натурального числа в виде произведения степеней простых чисел, и действует он следующим образом.

Идеи, применённые при построении рекурсивных функций и машин Тьюринга, могут быть использованы в общей теории вычислимости. Это можно понять, если Теория алгоритмов Игошин скачать и рассмотреть тезисы построчно. Ясно, что композиция (суперпозиция) вычислимых функций есть функция вычислимая (теорема 2.4.7). Далее, функция, возникающая примитивной рекурсией из вычислимых функций, сама вычислима (теорема 3.4.1). Наконец, функции, получающиеся с помощью операторов суммирования и мультиплицирования (теорема 3.2.15), а также с помощью оператора минимизации (теорема 3.5.3) из вычислимых функций, сами будут вычислимы. В силу тезисов Тьюринга и Чёрча, эти выводы справедливы для любых моделей алгоритмической вычислимости. Понятие нумерации или перечисления, или кодирования алгоритмов, и особенно эффективность этой процедуры, играет фундаментальную роль в теории вычислимости, значение которой невозможно переоценить. Особенно эффективна роль этой процедуры при доказательствах алгоритмической неразрешимости тех или иных массовых проблем, т.е. при доказательствах несуществования единого алгоритма для решения массовой проблемы. Теория алгоритмов Игошин раскрывает перед нами все тайны информатики.