Теория алгоритмов. Основные результаты, Программы как данные - Рекурсивные функции

Вместо предисловия. Сверх-идеей любой научной теории можно считать перевод знания из сферы подсознательного, интуитивногов осознанную, точную и логически завершенную, а потому - практически применимую форму. Многие важнейшие математические теории (например, топология или теория меры) родились из попытки осознать интуитивно очевидные, но формально почти неуловимые, ускользающие понятия (непрерывного, гладкого, измеримого и пр.) При чтении обратите внимание, сколь широкий круг содержательных общематематических и даже общелогических понятий - перечисление, сводимость, контрпример и конечно, само понятие правила (алгоритма) - охватывает, формулируяпри этом в предельно конструктивном духе, теория алгоритмов. Последнее, очевидно, и обеспечивает необычайную широту ее применения - от сложнейших вопросов оснований математики доприкладных разработок в таких сферах, как искусственный интеллект.

Программы как данные

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

Так или иначе, определимся в некоторой конкретной и удобной для наших задач трактовке программ в качестве данных.

Естественное и наиболее привычное для нас представление программ - Текст (последовательность символов некоторого алфавита), но в качественной теории алгоритмов выбор типа данных - явно, второстепенная задача. Для наших целей подойдет любой Универсальный тип данных U, т. е. тип данных такой, чтодля любого другого типа T найдется подходящее эффективное кодирование значений типа T значениями типа U. Действительно, в качестве универсального типа можно выбрать Текст, Т. к. значениям любого типа можно поставить в соответствие текст их записи в некоторой фиксированной системе обозначений. В последующих лекциях мы познакомимся с моделями вычислений, в которых именно текст является основным типом данных.

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

Похожие статьи

• Теорема о параметризации., Универсальные функции - Рекурсивные функции

  Любую часть x1,x2,...,xn входных значений можно породить программно, более того - существует алгоритм, который генерирует по x1,x2,...,xn текст...

• ФУНКЦИИ, Основные понятия - Свойства функций

  Основные понятия При изучении различного рода явлений приходится иметь дело с совокупностью переменных величин, которые связаны между собой таким...

• Лемма (о декартовом произведении)., Замечания и упражнения - Рекурсивные функции

  Если А - эффективное множество, то Для любого эффективного множества B AB эффективно (и, следовательно, любое декартово произведение A1A2...Аn...

• Рекурсивные функции

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

• Сходимость итерационных алгоритмов кластер-анализа - Базовые результаты математической теории классификации

  Сначала обсудим один из широко применяемых методов кластер-анализа - с метода k-средних. Он предназначен для разбиения исходного множества элементов...

• Прогностическая сила - адекватный показатель качества алгоритма диагностики - Базовые результаты математической теории классификации

  Часто используют такой показатель качества алгоритма диагностики, как "вероятность (или доля) правильной классификации (диагностики)" [12, 13] - чем этот...

• Кодирование программ - Рекурсивные функции

  (Эффективной) Нумерацией , или Перечислением множества А назовем Произвольное эффективное отображение f :N A, f(N)=A; таким образом, мы допускаем, что в...

• Перечислимость. - Рекурсивные функции

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

• Дискретные случайные величины. Распределение случайных величин. Примеры, Функция распределения случайной величины. Свойства. Примеры - Теория вероятности

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

• Теорема Клини о нормальной форме - Рекурсивные функции

  Существуютпримитивнорекурсивныефункция u и примитивно разрешимый предикат T такие, что e, x ( E(x)=p ( k [T(e, x,k)])). В частности, e, x ( E(x) k T(e,...

• Нормальные алгоритмы Маркова

  1. Нормальные алгоритмы Маркова Для формализации понятия алгоритма российский математик А. А. Марков предложил использовать ассоциативные исчисления....

• Теорема о параметризации - Рекурсивные функции

  Одно и то же выражение может порождать несколько разных функций, от разного числа аргументов. Так, обычное арифметическое выражение xK можно считать...

• Принципы построения программ с автоматическим выбором шага, Решение задачи, Блок-схема программы, Результаты решения - Вычисление кратных интегралов методом ячеек с автоматическим выбором шага

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

• Результаты исследования, Вычисления для следующих входных данных, Сравнение результатов - Численное нахождение корня уравнения методом Рунге-Кутта

  Вычисления для следующих входных данных F=1000H m=200 кг m'=1 кг/сек k=2 t0=0 сек V0=0 м/сек B=50 n=50 V1 (t) - результаты, полученные с помощью...

• Сходящиеся последовательности, Основные свойства сходящихся последовательностей: - Свойства функций

  Говорят, что Последовательность сходится, если существует число такое, что для любого существует такое , что для любого , выполняется неравенство: ....

• Введение, Оптимальный метод диагностики основан на непараметрических оценках плотности - Базовые результаты математической теории классификации

  Методы классификации - неотъемлемая часть математических методов исследования, интересная теоретически и важная практически. Обзоры этой научной области...

• Теорема об универсальной функции - Рекурсивные функции

  Для любого n, nN, универсальная функция u(n) вычислима. Доказательство. При доказательстве мы можем ограничиться случаем N=1. Действительно, программу,...

• Неразрешимость - Рекурсивные функции

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

• Основная теория сезонности временного ряда - Методы изучения сезонных колебаний. Примеры расчетов

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

• Результаты применения МГА для оптимизации ИП - Возможности генетических алгоритмов для решения задачи многокритериальной оптимизации инвестиционного портфеля

  Все генетические алгоритмы участвовали в двух группах тестов. В каждой группе исследовались различные наборы значений управляющих параметров МГА:...

• Функции и ее свойства - Методы решения системы линейных уравнений

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

• ТЕМПЕРАТУРА - Основные положения молекулярно-кинетической теории, ее опытные обоснования

  Любое макроскопическое тело или группа макроскопических тел называется термодинамической системой. Тепловое или термодинамическое равновесие - такое...

• Корреляционно-регрессионный анализ, Сущность и основные условия применения корреляционного анализа - Статистико-экономический анализ финансовых результатов деятельности предприятий

  Сущность и основные условия применения корреляционного анализа В соответствии с сущностью корреляционной связи ее изучение имеет две цели: 1) измерение...

• Решение задачи с помощью прикладных программ, Технология разработки формы для ввода исходных данных средствами VBA - Формирование оптимального штата фирмы

  Технология разработки формы для ввода исходных данных средствами VBA Для разработки формы ввода исходных данных необходимо отобразить вкладку...

• Применение теории линейного программирования для КУП "СПЕЦКОММУНТРАНС", Модели линейного программирования. Основные определения - Применение экономико-математических методов и моделей в управлении производством (на примере КУП "Спецкоммунтранс")

  Модели линейного программирования. Основные определения Еще одним классом задач экономико-математического моделирования являются задачи линейного...

• Синтаксис и семантика. Теорема Райса - Рекурсивные функции

  Попробуем теперь проанализировать круг проблем, неразрешимость которых доказана в предыдущем пункте. Общим для них является то, что по кодам, т. е....

• Введение - Основные понятия теории вероятностей

  Каждая наука, развивающая общую теорию какого-либо круга явлений, содержит ряд основных понятий, на которых она базируется. Таковы, например, в геометрии...

• Введение, Основные понятия теории управления - Методология моделирования процессов управления в социально-экономических системах

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

• Прогностическая сила - Базовые результаты математической теории классификации

  С целью поиска приемлемого показателя качества диагностики рассмотрим восходящую к Р. Фишеру [20] широко известную параметрическую вероятностную модель...

• Классификация экономико-математических методов и моделей в управлении предприятием и их задачи в повышении экономической эффективности производства, Основные понятия теории экономико-математического моделирования, Кибернетический подход к исследованию экономико-математических систем - Применение экономико-математических методов и моделей в управлении производством (на примере КУП "Спецкоммунтранс")

  Основные понятия теории экономико-математического моделирования Кибернетический подход к исследованию экономико-математических систем Обычно...

• Тестовые данные для задачи оптимизации ИП - Возможности генетических алгоритмов для решения задачи многокритериальной оптимизации инвестиционного портфеля

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

• Аннотация - Базовые результаты математической теории классификации

  Математическая теория классификации содержит большое число подходов, моделей, методов, алгоритмов. Эта теория весьма многообразна. Выделим в ней три...

• Разработка алгоритма нахождения входного потока заявок в имитационной модели контрольно-пропускной системы на основе статистических данных

  Разработка алгоритма нахождения входного потока заявок в имитационной модели контрольно-пропускной системы на основе статистических данных В наши дни...

• Действия над комплексными числами в алгебраической форме, Четность и нечетность функции, Монотонность и периодичность функции, Предел функции в точке - Действительные числа. Тригонометрические функции числового аргумента. Логарифмы. Частные случаи решения тригонометрических уравнений

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

• Научная теория и ее структура - Основы научных исследований

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

• 7. ПРЕДЕЛ ФУНКЦИИ, ПОНЯТИЕ ФУНКЦИИ, ЧИСЛОВАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ. ПРЕДЕЛ ЧИСЛОВОЙ ПОСЛЕДОВАТЕЛЬНОСТИ. ПРЕДЕЛ ФУНКЦИИ - Скалярные и векторные величины, матрицы и функции

  ПОНЯТИЕ ФУНКЦИИ Если некоторому множеству значений поставлено по определенному правилу F во взаимнооднозначное соответствие некоторое множество, то тогда...

• Необходимое и достаточное условие интегрируемости, Равномерно непрерывные функции - Определенные интегралы

  Теорема: Для того, чтобы ограниченная на сегменте функция была интегрируемой на этом сегменте, необходимо и достаточно, чтобы для любого нашлось такое...

• Алгоритм принятия решений на основе анализа иерархии целей - Формализация решения многоцелевых задач при управлении научной деятельностью

  Алгоритм использует в качестве исходных данных документы, содержащие следующие сведения: X A, k,j, i - измеряемые показатели научной работы; X A, TG,...

• Анализ инвестиционной деятельности в основной капитал ПМР, Первичный статистический анализ данных - Статистическое исследование инвестиционной деятельности в регионе

  Первичный статистический анализ данных Для анализа инвестиционной деятельности в основной капитал был использован статистический ежегодник...

• Влияние игровых моделей операций на повышение эффективности производства КУП "СПЕЦКОММУНТРАНС", Модели теории игр. Основные определения и термины - Применение экономико-математических методов и моделей в управлении производством (на примере КУП "Спецкоммунтранс")

  Модели теории игр. Основные определения и термины В разных областях целенаправленной деятельности, например при разработке и эксплуатации АСУ, часто...

Теория алгоритмов. Основные результаты, Программы как данные - Рекурсивные функции

Предыдущая | Следующая