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. Условия оптимизацией остатка рекурсии.

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

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

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


 

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

80278. Палітра Функції - Functions 72 KB
  Палітра Функції Functions За допомогою палітри Функції – Functions. Якщо палітра Функції Functions не відображена на екрані необхідно викликати палітру вибравши рядок Показати палітру Функції Show Functions Plette у меню Вікна Windows. Палітра Функції Functions може бути пришпилена до робочого стола за допомогою кнопки в лівому куті палітри або прибрана кнопкою хрестик . Палітра Функції Functions доступна тільки якщо активно вікно Діаграма Digrm.
80281. ПРОЕКТУВАННЯ ВІРТУАЛЬНОГО ПРИЛАДУ ДОСДІДЖЕННЯ ТЕМПЕРАТУРИ 395 KB
  Усі середовища складаються з атомів і молекул. Молекули знаходяться у хаотичному русі. При великій кількості часток у системі (вуглеводневі енергоносії, гірські породи, водні середовища) нема змоги детально описати поведінку кожної окремої часточки. Однак загальні риси поведінки системи в цілому є опосередкованим відображенням руху окремих часточок
80282. Методи оцінки і аналізу тіньової економічної діяльності в сфері підприємництва 123.5 KB
  Однією з причин перманентної економічної кризи в якій перебуває Україна є безпрецедентні розміри тінізації та криміналізації її економіки. Необхідно виробити нові підходи у протидії тонізації та криміналізації економіки. Безпосередні фрагментарні дослідження іллегального сектору полягають у визначенні розмірів тіньової економіки у конкретному секторі наприклад у виробництві товарів і послуг у розрізі асортиментних позицій у обміні валюти з урахуванням кількості офіційних пунктів обміну банків туристичних агентств реального курсу...
80283. Удосконалення управління процесами детінізації економічної діяльності 140.5 KB
  Роль і функції держави у зниженні тіньової економічної діяльності в Україні. Механізми запобігання розвитку тіньової економічної діяльності у сфері фінансово грошових відносин. Основні принципи розроблення комплексу заходів запобіжного характеру спрямованих на зниження рівня тіньової економічної діяльності. Методологічні підходи до визначення послідовності реалізації заходів спрямованих на запобігання розвитку тіньової економіки.
80284. Особливості розвитку тіньової економіки в України 65.5 KB
  Тіньовий ринок тіньова економіка істотно впливають на всі сторони економічної діяльності на політичне і суспільне життя кожної країни. Вже на такому рівні вплив державно нерегульованих факторів стає настільки відчутним що суперечності між легальним і тіньовим секторами спостерігаються практично в усіх сферах життєдіяльності суспільства. Труднощі які виникають в результаті внутрішньої неузгодженості регуляторноправового механізму та безсистемної беззмістовної зміни концептуальних орієнтирів розвитку економіки створюють необґрунтовані...
80285. Соціально-економічна сутність тіньової економічної діяльності 86.5 KB
  Соціальноекономічні причини виникнення та джерела походження тіньової економіки. Основні складові тіньової економіки. Класифікація форм і видів прояву тіньової економіки. Тому кожна держава розробляє стратегію форми і методи протистояння тіньовій економічній діяльності упроваджує механізми зниження її негативного впливу на розвиток національної економіки.
80286. Міжнародні організації з боротьби з легалізацією тіньових доходів 128.5 KB
  Створення структура і основні принципи діяльності Групи з розробки фінансових заходів з боротьби з відмиванням грошей FTF. Група з розробки фінансових заходів з боротьби з відмиванням грошей FTF застосувала до України контрзаходи і в кінці року ми були занесені в чорний список країн де відмиваються злочинні кошти. Основні міжнародні вимоги які необхідно враховувати при побудові національно системи боротьби з відмиванням грошей є такі: Адаптація Сорока рекомендацій FTF; Адаптація рекомендацій Базельського комітету Знай...