1. Синтаксис языка лисп. Списки. Атомы. Виды атомов. Комментарии

Скачать 260.62 Kb.

Название	1. Синтаксис языка лисп. Списки. Атомы. Виды атомов. Комментарии
страница	5/9
Тип	Документы

rykovodstvo.ru > Руководство эксплуатация > Документы

1 2 3 4 5 6 7 8 9

11. Примитивно-рекурсивные операторы

См. билет 10 (суперпозиция, примитивная рекурсия)

12. Функция Аккермана и её смысл

P_n(a, x) — действие n-ной степени над а,х

P₀(a, x) = a + x

P₁(a, x) = a*x

P₂(a, x) = a^x

Рассмотрим B(n, x) = P_n(2, x)

B(0, x) = 2 + x

B(1, x) = 2∙x

B(n+1, 0) = sg(n)

B(n+1, x+1) = B(n, B(n+1, x))
Функция Аккермана: A(x) = B(x, x). Растёт быстрее любой рекурсивной функции. Нельзя вычислить через три базисные функции. Невычислима с помощью примитивно-рекурсивных операций => эта модель не полная.

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

. Эта функция растёт очень быстро, например, число

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

Функция Аккермана в силу своего определения имеет очень глубокий уровень рекурсии, что можно использовать для проверки способности компилятора оптимизировать рекурсию. Например, компилятор, который анализируя вычисление A(3, 30) способен сохранять промежуточные значения вроде A(3, n) и A(2, n), может ускорить вычисление A(3, 30) в сотни и тысячи раз. Также вычисление A(2, n) напрямую вместо рекурсивного раскрытия в A(1, A(1, A(1,...A(1, 0)...))) прилично ускорит вычисление. Вычисление A(1, n) занимает линейное время n. Вычисленние A(2, n) требует квадратичное время, т.к. оно раскрывается в O(n) вложенных вызовов A(1, i) для различных i. Вычисление A(3, n) требует времени пропорционально 4ⁿ⁺¹.

A(4, 2) невозможно посчитать с помощью простого рекурсивного применения за разумное время. Вместо этого для оптимизации рекурсивных вызовов используются сокращенные формулы.

13. Частично-рекурсивные функции. Тезис Чёрча

Ограниченный оператор наименьшего числа даёт такую функцию, которая на входе принимает

P(x₁, …, x_n) и Z а на выходе даёт

такое Y, при котором P(x₁, …, x_n, Y) = 0, или
число Z, если такого Y не существует.

Неограниченный оператор наименьшего числа

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

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

, при условии

«То есть функция

возвращает минимальное значение последнего аргумента функции

, при котором её значение равно 0. В терминах императивного программирования — примитивно рекурсивные функции соответствуют программным блокам, в которых используется только арифметические операции, а также условный оператор и оператор арифметического цикла (оператор цикла, в котором число итераций известно на момент начала цикла). Если же программист начинает использовать оператор цикла while, в котором число итераций заранее неизвестно и, в принципе, может быть бесконечным, то он переходит в класс частично рекурсивных функций.» ВП
Частично рекурсивные функции для некоторых значений аргумента могут быть не определены, так как оператор минимизации аргумента не всегда корректно определён, поскольку функция

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

Частично-рекурсивные функции вычислительно эквивалентны машине Тьюринга.

1 2 3 4 5 6 7 8 9

Похожие:

	Дмитриев Михаил Николаевич гбоу школа №1586 \| Москва, Улица Дружбы... Проектная работа представляет собой программное приложение, разработанное как для уроков физики и химии, так и для индивидуальных...		1. Если атомы растворимого компонента в замещают в узлах решетки... Диаграмма состояния сплавов, образующих с ограниченной растворимостью в твердом состоянии с перитектикой, изображена на рис
	Семантика Синтаксис Морфология К 28 Семантика. Синтаксис. Морфология. — М.: Главная редакция восточной литературы издательства «Наука», 1988. — 309 с		Учебное пособие включает в себя материалы к 9 практическим занятиям... Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
	Методическое руководство к выполнению лабораторных работ по биоорганической... Скелет их молекул построен только из атомов углерода. В зависимости от последовательности соединения атомов углерода в углеродном...		Инструкция по составлению финансового отчета (краткие комментарии) № Основные требования к форме и составу документации, подтверждающей расход (Комментарии)
	Основная образовательная программа высшего образования Направление... Целью курса синтаксиса современного русского литературного языка является знакомство студентов с синтаксисом как центральной лингвистической...		Издание третье Панин, его стилистической системы, описана роль писателей, публицистов, общественных деятелей в развитии норм литературного языка....
	6. Злаки специального назначения Особую группу газонных злаков составляют виды, отличающиеся хорошей приспособленностью к специфическим условиям. Они могут быть использованы...		Урока: Образовательные Развить понятие о взаимном влиянии атомов, зависимости применения от свойств веществ
	Учебно-методическое пособие по английскому языку для студентов первого... Введение. Своеобразие английского языка. Его роль в современном мире как языка международного и межкультурного общения		Методическая разработка «Рекомендации по переводу научного текста» Деловой иностранный язык играет большую роль в процессе изучения иностранного языка в колледже. Деловой язык делает акцент на конкретные...
	Проблемная технология на уроках английского языка в 9 классе Автор: Закирова Татьяна Валерьевна Маоу «сош №7 с углубленным изучением английского языка» г. Перми, учитель английского языка высшей квалификационной категории		Сведения о чу дпо «Чувашский учебно-курсовой комбинат» Предмет и виды деятельности Учреждения, виды реализуемых образовательных программ
	Курсовая работа На тему: «клиника и лечение трихинеллеза» Экспериментально трихинеллезом заражаются все виды млекопитающих животных и многие виды птиц		«Углубленное изучение английского языка» по направлению подготовки... Повышение уровня культуры образования, а также культуры общения, мышления и речи. 3 Знакомство с культурой стран изучаемого языка...

Руководство, инструкция по применению