Читать курсовая по математике: "Рекурсивные функции" Страница 1

(Назад) (Cкачать работу)

Курсовая работа

по дисциплине: Математическая логика и теория алгоритмов

на тему: Рекурсивные функции

Содержание

Введение

1. Цели и задачи курсовой работы

2. Алгоритмическая неразрешимость

3. Суперпозиция функций

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

3.1 Примитивно рекурсивная функция

3.2 Общерекурсивные функции

3.3 Расширенный базис клини. Частичная рекурсивность разности

3.4 Геделева нумерация и эффективная перечислимость частично-рекурсивных функций

Заключение

Список использованной литературы Введение Важным элементом математики является доказательство существования или отсутствия алгоритма для решения поставленной задачи.

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

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

Существует несколько подходов к определению понятия алгоритма. Одним из них связано с уточнением понятия эффективно вычислимой функции. Его вывели математики А. Черч, К. Гендель, С. Клини. В результате был выведен класс частично-рекурсивных функций, имеющих строгое математическое определение. 1. Цели и задачи курсовой работы В данной курсовой работе рассматриваются: определение алгоритмической неразрешимости задачи; понятия суперпозиции функций, рекурсивных функций; схема примитивной рекурсии; операция минимизации.

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

Задачами курсовой работы являются:

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

. раскрытие понятия суперпозиции функций;

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

алгоритм задача рекурсия суперпозиция

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

Алгоритмически неразрешимыми являются, напр., проблема распознавания: закончит ли свою работу (остановится ли) или же «зависнет» в бесконечном цикле произвольно выбранная программа действий алгоритмического типа (не только компьютерная, но и реализуемая человеком по алгоритмическому типу); проблема эквивалентности программ (нет

Похожие работы