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

Скачать 260.62 Kb.

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

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

1 2 3 4 5 6 7 8 9

20. Проблема остановки

Невозможно создать программу, которая по данному алгоритму Р и аргументу x определяет, зациклится ли P(x).
<�Доказательство>

Пп. Существует g(x,y) =

1, если P_x(y) не зацикливается
0, если P_x(y) зацикливается

f(x)=g(x,x) По предыдущему, предположение неверно.

</Доказательство>

21. Необходимость частично-рекурсивной функции

Существует частично-рекурсивная (т.е. зацикливающаяся при некоторых х) функция f(x), такая, что любая общерекурсивная функция g(x) тождественно не равна f(x).

g(x) никогда не зацикливается. Но для x, при которых f(x) не зацикливается, g(x) возвращает f(x).
<�Доказательство>

Предположим, что g(x)≡f(x). Если f(x) не зацикливается, то

f(g)=U(g,g)+1=g(g)+1.

</Доказательство>
Итоги

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

22. Теорема Райса (классификация алгоритмов)

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

23. Проблема соответствий Поста (поиск конкатенации)

Пусть даны два набора строк:

a₁, a₂, …, a_n
b₁, b₂, …, b_n

Из строк первого набора конкатенацией элементов с индексами i₁, i₂, … i_K строится строка A, из строк второго набора с теми же индексами строится строка B. Требуется определить, существует ли такой набор индексов, при котором А=B.
Такую программу написать нельзя. (Потому что если такого набора индексов не существует, программа не сможет этого понять и будет пытаться найти последовательность всё длиннее и длиннее - прим. ред.)
Всё до этого было связано с анализом программ, а это - анализ данных. Но написать такую программу мы тоже не можем. Если требуется доказать, что некоторая проблема неразрешима, то надо её свести к существующей неразрешимой проблеме.
Механизмы абстракций

Механизмы абстракций — отделение логики использования от логики реализации.

Использование абстракций должно быть проще реализации. Нет функциям с 50-ю параметрами!

Абстракции 2-х типов:

Абстракции функций. Например, блочная структура, особые формы lambda, let.
Абстракция данных (как устроено внутри не волнует). Например, пара значений.

24. Труднорешаемые проблемы

Труднорешаемые проблемы - это проблемы, которые имеют экспоненциальный рост (NP сложные). К ним относятся разнообразные переборы. Для того, чтобы доказать, что задача является труднорешаемой, её нужно свести к уже известной труднорешаемой проблеме.

25. Особая форма лямбда (lambda)

(lambda (аргументы) выражение) — результатом является функция, которая принимает аргументы и вычисляется по указанному выражению.
(define (f x) (+ x 10)) ≡ (define f (lambda (x) (+ x 10)))
передаем функцию
(sum (lambda (x) (+ x 20)) 30)
Лямбда позволяет создавать функции, которые в качестве результата возвращают другие функции.
(define (multiplier n) (lambda (x) (* x n)))
Вызывем. Умножает один аргумент на 10
(sum (multiplier 20) 10)
(define (multiplier n)

(define (mul x) (* x n))

mul)

((multiplier 2) 3)

1 2 3 4 5 6 7 8 9

Похожие:

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

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