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

Скачать 260.62 Kb.

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

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

1 2 3 4 5 6 7 8 9

5. Понятие вычислительного процесса. Итерация, линейная рекурсия, древовидная рекурсия

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

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

6. Оценивание вычислительного процесса. Порядки роста

Оценка программы:

Количество операций
Максимальная глубина используемого стека.

Эти характеристики сильно зависят от исходных данных. Поэтому для оценки используется порядок роста — показатель, определяющий, как увеличивается количество операций и объём необходимой памяти по мере увеличения размеров данных, например:

Логарифмический порядок
Линейный порядок
Полиномиальный (обозначается Р) порядок — такие задачи могут быть распараллелены.
Экспоненциальный (обозначается NP) порядок

Существует также известная проблема P=NP.
Пример. Итеративное нахождение факториала. Расход памяти не зависит от глубины рекурсии.

(define (f n) (fiter 1 1 n))

(define (fiter p c m)

(if (> c m) p

(fiter (* c p) (+ c 1) m))

)

Интерпретатор идентифицирует рекурсивную операцию как последнюю и не сохраняет точку возврата.

7. Понятие вычислительной модели. Требования к модели

Вычислительная модель – набор правил (соглашений, стандартов, формализмов) выполнения алгоритма.

Свойства математической модели:

Дискретность шагов
Детерминированность промежуточных и конечных результатов
Элементарность шагов
Результативность (в результате шага что-то меняется)
Массовость (алгоритм работает с разными входными данными)

8. Детерминированная машина Тьюринга. Вычислимость по Тьюрингу. Тезис Тьюринга

Детерминированная машина Тьюринга (ДМТ) — имеет конечное число состояний и бесконечную ленту.

Программа для ДМТ — набор правил вида: q₁a₁ → q₂a₂D, где

q₁ – текущее состояние

a₁ – значение под головкой

q₂ – новое состояние

a₂ – новое значение под головкой

D – перемещение после выполнения операции

Остановка происходит, когда нет ни одного выполнимого правила.

Функция вычислима по Тьюрингу, если существует ДМТ, правильно считающая её значение.

Вход X допустИм, если ДМТ, получая этот вход, рано или поздно останавливается.

Сильный тезис Чёрча — Тьюринга (тезис Чёрча — Тьюринга — Дойча): любой конечный физический процесс, не использующий аппарат, связанный с непрерывностью и бесконечностью, может быть вычислен физическим устройством.	Конечный процесс → Устройство
Физический тезис Чёрча — Тьюринга: любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга.	Устройство → МТ
Тезис Тьюринга: всякий алгоритм может быть реализован с помощью машины Тьюринга. Вычислительные возможности ДМТ и CPU эквивалентны: на CPU можно написать эмулятор ДМТ, и наоборот, на ДМТ можно записать все состояния CPU. Любую математическую функцию можно запрограммировать.	Алгоритм → МТ

1 2 3 4 5 6 7 8 9

Похожие:

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

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