50858

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

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

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

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

Русский

2014-01-31

38 KB

27 чел.

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

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

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

ОТЧЕТ ПО

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

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

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

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


 

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

30748. Латинская Америка: что принесли неолиберальные преобразования (на опыте 1980 - 1990-х гг.) 27 KB
  стимулировал экономический рост Латинской Америки в начале 90х гг. Другая болевая точка современной Латинской Америки безработица принявшая беспрецедентные масштабы. Финансовоэкономическая стратегия Латинской Америки на 90е гг. В задачи консенсуса входило преодоление инфляции сокращение бюджетного дефицита укрепление национальных валют Латинской Америки.
30749. Причины и характер первой мировой войны, цели воюющих сторон. (28 июля 1914 — 11 ноября 1918) 23.5 KB
  28 июля 1914 11 ноября 1918 стремление к переделу мира в результате противостояния двух военных блоков: Тройственного Союза Германия АвстроВенгрия Италия и Антанты Англия Франция Россия борющихся за гегемонию на континенте. слабое рабочее движение в результате в ряде стран победили партии войны в правящих кругах ряда Западных стран Германия Великобритания АвстроВенгрия и Франция. Цели: Германия создать Новую Европу где влияния Англии Франции и России свелись бы к нулю. АвстроВенгрия как и Германия за...
30750. Бетонирование колонн, стен, перекрытий 14.54 KB
  При возведении стен в разборнопереставной опалубке смесь укладывают участками высотой не более 3 м. В стены толщиной более 05 м при слабом армировании подают бетонную смесь подвижностью 4. Бетонную смесь подают непосредственно в опалубку в нескольких точках по длине участка бадьями виброжелобами бетононасосами. При высоте стен более 3 м используют звеньевые хоботы при этом смесь укладывают горизонтальными слоями толщиной 03.
30751. Назначение и виды опалубок. Требования к опалубке. Оборачиваемость опалубных форм 16.57 KB
  Поверхность опалубки непосредственно примыкающая к бетону должна быть плотной иметь малую с бетоном адгезию и не иметь щелей чтобы не вытекало цементное молоко. Важнейшим показателем качества опалубки является ее оборачиваемость т. Применение инвентарной многооборачиваемой опалубки из унифицированных элементов с модульным изменением размеров и укрупненных блоков способствует снижению трудоемкости и стоимости опалубочных работ. Для изготовления опалубки используют доски из древесины II III и IV сортов хвойных пород допускается...
30752. Разборно-переставная опалубка. Область применения, конструкция 15.58 KB
  Технологический процесс устройства опалубки состоит в следующем. Щиты опалубки или собранные из них крупные опалубочные элементы устанавливают вручную или краном и закрепляют в проектном положении. Масса элемента этой опалубки до 70 кг. Щиты опалубки изготовляют из досок толщиной 19.
30753. Объёмно-переставная опалубка. Конструкция, область применения 17.24 KB
  Секции при соединении образуют туннели опалубки на квартиру или на всю ширину здания. Секции опалубки могут иметь переменную ширину в зависимости от принятого шага стен и различную длину. П и Гобразные секции опалубки устанавливают на перекрытии ранее забетонированного этажа выверяют и закрепляют между собой в продольном и поперечном направлениях. Общие конструктивные признаки опалубки: наличие системы механических домкратов для выверки и установки в проектное положение; катучие опоры для перемещения секций опалубки при монтаже и...
30754. Скользящая опалубка. Технология бетонирования стен в скользящей опалубке 14.52 KB
  При бетонировании следят за вертикальностью домкратного стержня и за бетонной поверхностью Применение скользящей опалубки особенно эффективно при строительстве высотных зданий и сооружений с минимальным количеством оконных и дверных проемов конструктивных швов и закладных элементов. К ним относятся силосы для хранилища материалов дымовые трубы и градирни ядра жесткости высотных зданий резервуары для воды радиотелевизионные башни. Другая потенциальная область использования скользящей опалубки строительство зданий атомных реакторов...
30755. Состав арматурных работ на строительной площадке. Классификация арматуры. Арматурные изделия. Устройство защитного слоя арматуры 17.79 KB
  Классификация арматуры. Устройство защитного слоя арматуры. При монтаже сборных железобетонных конструкций выполняются сварка выпусков арматуры и закладных деталей натяжение проволоки и канатов преднапряженных конструкциях а также создание каркаса или внешнего армирования при усилении конструкции реконструируемых зданий и сооружений. В состав арматурных работ на строительной площадке входят: разгрузка приемка и складирование поступающих арматурных изделий и товарной арматуры; изготовление нестандартных арматурных изделий; укрупнительная...
30756. Сущность зимнего бетонирования. Модуль поверхности конструкций, его влияние на выбор метода бетонирования. Понятие критической прочности 17.93 KB
  Продолжительность твердения и конечные свойства бетона в значительной степени зависят от температурного режима и состава бетона в том числе от вида цемента. Для твердения бетона наиболее благоприятной температурой является 1528гр. Кроме того вода образует вокруг крупного заполнителя обволакивающую ледяную пленку которая при оттаивании нарушает сцепление монолитность бетона. При раннем замораживании по тем же причинам резко снижается сцепление бетона с арматурой увеличивается пористость что влечёт за собой снижение прочности...