50858

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

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

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

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

Русский

2014-01-31

38 KB

26 чел.

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

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

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

ОТЧЕТ ПО

ЛАБОРАТОРНОЙ РАБОТЕ №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. Условия оптимизацией остатка рекурсии.

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

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

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


 

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

71596. ОСОБЕННОСТИ НОРМАТИВНО-ПРАВОВОГО РЕГУЛИРОВАНИЯ ПОРЯДКА ФУНКЦИОНИРОВАНИЯ ФОНДА СОЦИАЛЬНОГО СТРАХОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ 102 KB
  Денежные средства и иное имущество находящееся в оперативном управлении ФСС РФ а также имущество закрепленное за подведомственными фонду санаторно-курортными учреждениями являются федеральной собственностью. Денежные средства ФСС РФ не входят в состав бюджетов соответствующих уровней...
71597. КОНСТИТУЦИОННОЕ ПРАВОСОЗНАНИЕ, ПРАВОВАЯ КУЛЬТУРА И КУЛЬТУРА ПРАВ ЧЕЛОВЕКА: СООТНОШЕНИЕ ПОНЯТИЙ 139.5 KB
  Современное российское общество переживает кризис духовности сопровождающийся переоценкой ценностей сменой ориентиров и идеалов. Но каким бы ни был путь избранный Россией перед государством и обществом в качестве приоритетной задачи будет стоять утверждение демократических...
71598. СТАНОВЛЕНИЕ ЕДИНОГО НАЛОГА НА ВМЕНЕННЫЙ ДОХОД: ИСТОРИЧЕСКИЙ АСПЕКТ 142 KB
  Исторический аспект становления единого налога на вмененный доход представляет особый интерес в связи с реформой местного самоуправления проводящейся в соответствии с Федеральным законом от 6 октября 2003 г. 7 Федерального закона О финансовых основах местного...
71599. ГОСУДАРСТВО И ГОСУДАРСТВЕННАЯ ПОЛИТИКА В ОБЛАСТИ НАЦИОНАЛЬНОЙ БЕЗОПАСНОСТИ 53.5 KB
  Государственная политика в сфере безопасности формируется на основе Конституции законов и других нормативных правовых актов органов государственной власти и реализуется посредством целенаправленной и скоординированной деятельности всех органов государственной власти...
71600. ОСОБЕННОСТИ ПОРЯДКА ВЗАИМОДЕЙСТВИЯ ФИНАНСОВЫХ ОРГАНОВ РЕГУЛИРОВАНИЯ РЫНКА ЦЕННЫХ БУМАГ С ОТДЕЛЬНЫМИ СУБЪЕКТАМИ ФИНАНСОВОГО ПРАВА В ПРОЦЕССЕ ФИНАНСОВОЙ ДЕЯТЕЛЬНОСТИ 79.5 KB
  В процессе государственной финансовой деятельности при осуществлении полномочий по регулированию рынка ценных бумаг федеральные финансовые органы такого регулирования в частности Федеральная служба по финансовым рынкам далее ФСФР взаимодействует с другими субъектами...
71601. ОСОБЕННОСТИ НОРМАТИВНО-ПРАВОВОГО РЕГУЛИРОВАНИЯ ПОРЯДКА ФУНКЦИОНИРОВАНИЯ ФЕДЕРАЛЬНОГО ФОНДА ОБЯЗАТЕЛЬНОГО МЕДИЦИНСКОГО СТРАХОВАНИЯ 70 KB
  Особенности нормативно-правового регулирования порядка функционирования Федерального фонда обязательного медицинского страхования установлены положениями Закона РФ от 28 июня 1991 г. № 729 Вопросы Федерального Фонда обязательного медицинского страхования...
71602. РОЛЬ КОНСТИТУЦИИ РОССИЙСКОЙ ФЕДЕРАЦИИ В ПРОЦЕССЕ ФОРМИРОВАНИЯ И РЕАЛИЗАЦИИ ЗАКОНОДАТЕЛЬСТВА, РЕГЛАМЕНТИРУЮЩЕГО ПРЕДПРИНИМАТЕЛЬСКУЮ ДЕЯТЕЛЬНОСТЬ 186 KB
  Согласно статье 2 Конституции России человек его права и свободы являются высшей ценностью. С конституционным провозглашением прав и свобод человека как высшей ценности государство признало требования демократического международного сообщества выраженные в таких...
71603. ОБЪЕКТ И СУБЪЕКТ В СОДЕРЖАНИИ ПРАВООТНОШЕНИЯ ПО УСЫНОВЛЕНИЮ РЕБЕНКА 114.5 KB
  Как известно участниками правоотношений являются субъекты права под которыми понимаются лица и их объединения выступающие в качестве носителей предусмотренных законом прав и обязанностей. Таким образом рассматривая институт усыновления отметим что субъектом является...
71604. ПУТИ СОКРАЩЕНИЯ ФОРМ ЛИЦЕНЗИРУЕМОЙ ДЕЯТЕЛЬНОСТИ 154 KB
  Уменьшение лицензируемых видов деятельности следует связывать с пониманием ограничительной роли лицензионной системы и выявлением в ходе правоприменительной деятельности отсутствия необходимости в столь жестком регулятивном механизме в отношении большинства видов деятельности.