50858

Рекурсия и итерация в языке Пролог

Лабораторная работа

Информатика, кибернетика и программирование

Что обеспечивает предикат repet Предикат repet обеспечивает дополнительную возможность для порождения множественных решений в процессе возврата. Этот предикат можно определить следующим образом...

Русский

2014-01-31

38 KB

24 чел.

Министерство образования и науки молодежи и спорта Украины

ОДЕССКИЙ НАЦИОНАЛЬНЫЙ МОРСКОЙ УНИВЕРСИТЕТ

Кафедра «Информационные технологии»

ОТЧЕТ ПО

ЛАБОРАТОРНОЙ РАБОТЕ №2

 

«Рекурсия и итерация в языке Пролог»

Выполнил:

студент 4к., 4гр. КСФ

Мельников В.Е.

Проверил:

Бодарев А.Д.


Одесса - 2013

Цель работы

Изучить возможности использования рекурсивных и итерационных алгоритмов в языке Пролог.

Контрольные вопросы

  1.  Что такое рекурсивная процедура?

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

  1.  Отличие итерации от рекурсии?

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

  1.  Принцип работы управления поиском с возвратом?

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

- fail (неудача) – осуществляет вынужденное неудачное завершение выполнение предиката и, таким образом, инициирует процесс возврата.

- Cut или ! (отсечение) – используется для предотвращения поиска с возвратом.

  1.  Что обеспечивает предикат repeat ?

Предикат repeat обеспечивает дополнительную возможность для порождения множественных решений в процессе возврата. Этот предикат можно определить следующим образом:

repeat.

repeat :- repeat.

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

5. Условия оптимизацией остатка рекурсии.

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

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

-   Ранее в предложении не должно быть точек возврата


 

А также другие работы, которые могут Вас заинтересовать

78976. КОНЦЕПЦИЯ НАУЧНЫХ РЕВОЛЮЦИЙ Т.КУНА 40 KB
  История науки по Куну: Согласно книге Структура научных революций Т.Куна историю науки можно представить следующей схемой: 1 При переходе к зрелой науке на основе идей одной или нескольких научных школ возникает общепринятая парадигма; 2 одно из главных направлений деятельности нормальной науки – обнаружение и объяснение фактов как фактов подтверждающих парадигму; 3 при таком исследовании часть фактов трактуется как аномалии – факты противоречащие парадигме; 4 в период кризиса доверие к парадигме в известной степени подорвано но...
78978. Особенности становления и основные принципы неклассической науки 43 KB
  Планк квантавая теория Резенфорд планетарная модель атома Ренген ренгеновские лучи Все эти открытия разрушили картину мира. Основные принципы: Установка на невозможность описать мир сам по себе Установлено различие в организации и развитии 3х уровней мира: макро микро мега. Нет качественной однородности в мега микро и макромирах Вероятностный детерменизм Признавалась роль случайностей. Случайность – равноценный фактор необходимости Объект исследования не вещи а процессы Принципиально невозможно найти первокирпичик мира т.
78979. Понятие рациональности, научной рациональности. Виды и типы научной рациональности 48 KB
  Понятие рациональности научной рациональности. Виды и типы научной рациональности. В самой идее рациональности можно увидеть символ современной научно-технической цивилизации со всеми ее особенностями и противоречиями. Ее началом является некоторый тип активно-преобразовательного отношения человека к миру с которым и связывается как правило сама идея рациональности.
78980. Пространство и время в современной и классической картине мира 35 KB
  Пространство и время в современной и классической картине мира. Пространство есть форма координации сосуществующих объектов состояний материи. Пространство и время это всеобщие формы существования координации объектов. Пространство и время в классической картине мира.
78981. Философское значение синергетики 41 KB
  В своей классической работе Синергетика он отмечал что во многих дисциплинах от астрофизики до социологии мы часто наблюдаем как кооперация отдельных частей системы приводит к макроскопическим структурам или функциям. Синергетика в ее нынешнем состоянии фокусирует внимание на таких ситуациях в которых структуры или функции систем переживают драматические изменения на уровне макромасштабов. По мнению ученого существуют одни и те же принципы самоорганизации различных по своей природе систем от электронов до людей а значит речь должна...
78982. Этос науки и императивы, регулирующие поведение ученого 32.5 KB
  Понятие Императив и Этос науки Императив лат. Этос науки набор внутренних социальных норм которых придерживаются ученые в научной деятельности и которые обеспечивают функционирование социального института науки. Нормы этоса науки Попытка кодификации социальных норм науки была предпринята Р.
78983. Научная специальность и основные этапы ее становления 40.5 KB
  С этой характеристикой тесно связана потребность в такого рода вознаграждении которое служило бы достаточным стимулом для профессионалов будучи в то же время подконтрольно не столько посторонним сколько самой профессии. Внутренний мотив – это познавательная потребность – информация заключенная в объекте на который направлено внимание человека. Познавательная потребность характеризуется следующими основными критериями: интенсивное стремление субъекта к знанию и к познавательной деятельности на основании чего избирается его...