Логич-кое и функ-ное программ-ние_УМП. Учебные пособия по логическому и функциональ ному программированию В. М. Зюзькова. В пособие внесены изменения в 2020 г
 Скачать 2.34 Mb.
|
|
10. Определение эйлерова пути на Лиспе Напишите программу на языке XLisp, определяющую эйлеров путь, начина- ющийся с заданной вершины в неориентированном графе (см. предыдущую тему). 11. Определение компонент связности на Прологе Напишите программу на SWI-Prologе, определяющую компоненты связности данного неориентированного графа. Каждая компонента связности - список вершин, следовательно, решением задачи должен быть список списков. Указание: запрограммируйте предварительно предикат path(+X,+Y), прове- ряющий, существует ли путь из вершины X в вершину Y. 36 12. Определение компонент связности на Лиспе Напишите программу на языке XLisp, определяющую компоненты связности данного неориентированного графа. Каждая компонента связности - список вершин, следовательно, решением задачи должен быть список списков. Указание: запрограммируйте предварительно предикат (path X Y), проверя- ющий, существует ли путь из вершины X в вершину Y. 5. КАК ВЫПОЛНЯТЬ КУРСОВУЮ РАБОТУ И ОФОРМЛЯТЬ ПОЯСНИТЕЛЬНУЮ ЗАПИСКУ Общие положения Основные задачи и цели курсового проектирования: 1) приобретение навыков и методов программирования достаточно сложных задач на языках логического программирования; 2) подготовка к выполнению дипломного проекта. В курсовой работе должна быть разработана тема в соответствии с заданием, одобренным кафедрой. Общие требования к построению пояснительной записки (ПЗ) Структура построения ПЗ ПЗ к работе должна содержать следующие разделы: 1) титульный лист; 2) аннотацию; 3) задание на проектирование; 4) содержание; 5) введение; 6) основная часть работы; 7) заключение; 8) список литературы; 9) приложения. Титульный лист Титульный лист оформляется согласно ОС ТУСУР 01–2013 (https://regulations.tusur.ru/documents/70), форма титульного листа приведена в приложении 1. Реферат Реферат - краткая характеристика работы с точки зрения содержания, назначения, формы и других особенностей. Перечисляются ключевые слова 37 работы, указывается количество страниц и приложений. Реферат размещают на отдельной странице. Заголовком служит слово "Реферат", написанное про- писными буквами. Задание на проектирование Форма задания заполняется студентом в соответствии с полученным заданием. Форма задания приведена в приложении 2. Содержание Содержание включает наименования всех разделов, подразделов и пунктов, если они имеют наименование, а также список литературы и приложения с указанием номера страниц, на которых они начинаются. Слово "Содержание" записывается в виде заголовка, симметрично тексту, прописными буквами. Пример оформления содержания приведен в приложе- нии 3. Введение Введение содержит основную цель курсовой работы, область примене- ния разрабатываемой темы. Заключение Заключение должно содержать краткие выводы по выполненной рабо- те. Также следует указать, чему программист научился на примере этой зада- чи (на этот вопрос легко ответить, если сформулировать его в виде: "Что я в следующий раз сделаю иначе?"). Список литературы В список литературы входят все те и только те источники литературы, на которые имеются ссылки в ПЗ. Примеры библиографических описаний ис- точников, помещаемых в список литературы, приведены в приложении 4. Приложения Приложения содержат вспомогательный материал: листинг программы и листинг тестов. Программа должна быть самодокументированная, т.е. - программа должна иметь простую и понятную структуру, - в программе должны быть прокомментированы используемые структуры данных, - для каждой функции должно быть указано, что она делает, что является входными данными и результатом, - должен быть прокомментирован используемый алгоритм. 38 Основная часть курсовой работы В основной части должно быть решение поставленной задачи, в част- ности: - анализ задачи; - обоснование выбора алгоритма; - обоснование выбора структур данных; - описание алгоритма; - обоснование набора тестов. Об анализе задачи Разработка алгоритма представляет собой задачу на построение. По- этому, как обычно в таких случаях (можно, например вспомнить о методе решения геометрических задач на построение), необходим этап анализа зада- чи. Он позволяет установить, что является входом и выходом будущего алго- ритма, выделить основные необходимые отношения между входными и вы- ходными объектами и их компонентами, выделить подцели, которые нужно достичь для решения задачи, и как следствие этого, выработать подход к по- строению алгоритма. Результатом этапа анализа задачи должна быть специ- фикация алгоритма, т. е. формулировка в самом общем виде того, что (в рам- ках выбранного подхода) должен делать алгоритм, чтобы переработать вход- ные данные в выходные. Об описании алгоритма Прежде всего, нужно иметь в виду, что такое описание предназначено не для машины, а для человека. Другими словами, речь идет не о программе, а о некотором тексте (т. е. о словесном описании), по которому можно полу- чить представление об общей структуре разрабатываемого алгоритма, о смысле его отдельных шагов и их логической взаимосвязи. Сохранение достаточно высокого уровня описания алгоритма также облегчает его обос- нование. Поэтому шаги алгоритма должны описываться в терминах тех объ- ектов и отношений между ними, о которых идет речь в формулировке задачи. Например, для "геометрической" задачи шаги алгоритма следует описывать как действия над точками, прямыми и т. п., как проверки свойств типа при- надлежности трех точек одной прямой и т. п. Но не должно быть работы с ко- дами этих объектов, например с матрицей координат точек некоторого мно- жества. При программировании на Прологе описание предикатов должно за- ключаться в указании, для каких отношений между сущностями (объектами предметной области) они введены. Какие аргументы предиката являются входными, а какие выходными? При программировании на Лиспе для описа- ния функций должно быть указано, что функция вычисляет, а не как она это делает. 39 Нужно подобрать набор тестов, достаточный для демонстрации работы программы и ее реакции на экстремальные ситуации и неправильное обраще- ние. Правила оформления ПЗ к курсовой работе ПЗ пишется в редакторе MS Word шрифтом Times New Roman, разме- ром 12, на формате A4. Нумерация страниц должна быть сквозной, первой страницей является титульный лист. Номер страницы проставляется вверху посередине. Заголовки разделов пишутся прописными буквами по середине текста. Заголовки подразделов пишутся с абзаца строчными буквами, кроме первой прописной. В заголовке не допускаются переносы слов. Точку в конце заголовка не ставят. Если заголовок состоит из двух предложений, то их раз- деляют точкой. 40 6. ЭКЗАМЕНАЦИОННЫЕ ВОПРОСЫ Данные вопросы предлагаются для компьютерной автоматизированной проверки знаний студентов по дисциплинам "Логическое программирова- ние" и "Функциональное программирование". Вопрос 1 Дана цель для интерпретатора Пролога ?- parent(X,pat). Какое из следующих двух предложений правильно передает логический смысл этого запроса: 1) "Все ли X являются родителями Pat?" 2) "Существует ли X, который является родителем Pat?" Варианты ответов: 1) первое предложение; 2) второе предложение; 3) оба предложения не передают логический смысл запроса; 4) оба предложения правильны. Введите номер правильного ответа. Вопрос 2 Дана цель для интерпретатора Пролога ?- not parent(X,pat). на которую был получен отрицательный ответ. Какое из следующих трех предложений правильно передает логический смысл этого ответа: 1) "Не существует родитель у Pat." 2) "Не все X являются родителями Pat." 3) "Есть родители, но не у Pat." Варианты ответов: 1) первое предложение; 2) второе предложение; 3) третье предложение; 4) все три предложения не передают логический смысл ответа. Введите номер правильного ответа. Вопрос 3 Пусть имеется правило на Прологе 'имеет ребенка'(X):-'родитель'(X, Y). Какое из следующих двух предложений правильно передает логический смысл этого правила: 1) "Для всех X и Y, если X - родитель Y, то X имеет ребенка." 41 2) "Для всех X, X имеет ребенка, если существует некоторый Y, такой, что X - родитель Y." Варианты ответов: 1) первое предложение; 2) второе предложение; 3) оба эти предложения передают логический смысл правила; 4) оба эти предложения не передают логический смысл правила. Введите номер правильного ответа. Вопрос 4 Пусть имеются следующие два варианта правила для предиката 'сестра'(X,Y) - "X есть сестра Y" на Прологе (мы вкладываем естественный смысл для ис- пользуемых в правиле предикатов): 1) 'сестра'(X,Y):-'родитель'(Z,X),'родитель'(Z,Y),'женщина'(X). 2) 'сестра'(X,Y):- 'родитель'(Z,X),'родитель'(Z,Y),'женщина'(X),'различны'(X,Y). Какое из этих правил более правильно с точки зрения логики? Варианты ответов: 1) первое; 2) второе; 3) оба неправильны; 4) правила логически эквивалентны. Введите номер правильного ответа. Вопрос 5 Пусть дано отношение 'родитель' на Прологе. Определим отношение "X - родственник Y" следующим образом : 'родственник'(X,Y):-'родитель'(X,Y). 'родственник'(X,Y): - 'родитель'(Y,X). 'родственник'(X,Y):-'родственник'(X,Z),'родственник'(Z,Y). Какие из следующих утверждений верны? 1. Одно из первых двух правил лишнее. 2. Третье правило потенциально опасное - оно может привести в некоторых запросах к бесконечной рекурсии. 3. Любой запрос к данной программе приводит к конечной работе интерпре- татора Пролога. 4. Правила неправильно задают отношение 'родственник'. Введите через пробел номера утверждений (в порядке возрастания), которые вы считаете истинными. Вопрос 6 Пусть, используя отношение 'предок' (см. курс лекций), введено отношение 'родственник': 42 'родственник'(X,Y):-'предок'(X,Y). 'родственник'(X,Y):-'предок'(Y,X). 'родственник'(X,Y):-'предок'(Z,X),'предок'(Z,Y). 'родственник'(X,Y):-'предок'(X,Z),'предок'(Y,Z). Правильно ли определено отношение? Варианты ответов: 1) да; 2) нет; 3) правильно, но при положительном ответе на некоторые ваши запросы ин- терпретатор будет повторять одинаковые ответы. Введите номер правильного ответа. Вопрос 7 Пусть дана программа на Прологе: 'родитель'('пам', 'боб'). 'родитель'('том', 'боб'). 'родитель'('том', 'лиз'). 'родитель'('боб', 'энн'). 'родитель'('боб', 'пат'). 'родитель'('пат', 'джим'). 'женщина'('пам'). 'женщина'('лиз'). 'женщина'('энн'). 'женщина'('пат'). 'мать'(X, Y):- 'родитель'(X, Y), 'женщина'(X). 'родитель родителя'(X, Y):- 'родитель'(X, Z), 'родитель'(Z, Y). Постарайтесь понять, как Пролог выводит ответы на указанные ниже вопро- сы. Будут ли встречаться возвраты при выводе ответов на какие-либо из этих вопросов? 1) ?-'родитель'('пам', 'боб'). 2) ?-'мать'('пам ', 'боб'). 3) ?-'родитель родителя'('пам', 'энн'). 4) ?-'родитель родителя'('боб', 'джим'). Введите последовательность из четырех ответов через пробелы в порядке ну- мерации (варианты ответов: да, нет). Вопрос 8 Следующие выражения представляют собой правильные объекты в смысле Пролога: 1) Diana; 2) diana; 3) 'Diana'; 4) 'Диана едет на юг'; 5) 'едет'('диана', 'юг'); 6) 45; 7) +(X,Y); 8) three(black (Kat)). Что это за объекты (атомы, числа, переменные, структуры)? 43 Введите последовательность из 8 ответов через пробелы (ответы кодируйте числами: атом -1, число - 2, переменная- 3, структура - 4). Вопрос 9 Пролог. Будут ли следующие операции унификации успешными или не- успешными? 1) point(A, B) = point(1, 2) 2) point(A, B) = point(X, Y, Z) 3) plus(2, 2) = X 4) +(2, D) = +(E, 2) 5) t(point(-1, 0), P2, P3) =t(point(P1, point(1, 0), point(0, Y)) Введите последовательность из пяти ответов через пробелы в порядке нуме- рации (варианты ответов: да, нет). Вопрос 10 Пролог. При выполнении цели ?- P = point(2, X). система унифицирует X = G692, P = point(2, G692). Имя G692 - законное имя прологовской переменной, которое система построила сама во время вычис- лений. Ей приходится генерировать новые имена, для того чтобы переимено- вывать введенные пользователем переменные в программе. В качестве объяснения этому можно предложить: 1) одинаковые имена обозначают в разных предложениях разные перемен- ные; 2) при последовательном применении одного и того же предложения исполь- зуется каждый раз его "копия" с новым набором переменных. Вам требуется выбрать верное объяснение. Варианты ответов: 1) первая причина правильная; 2) вторая причина правильная; 3) верны обе причины; 4) обе причины неправильны. Введите номер правильного ответа. Вопрос 11 Пролог. Рассмотрим следующую программу: f(1, one). f( s(1), two). f(s(s(1)), three). f(s(s(s(X))), N):- f(X, N). Сколько ответов пролог-система даст на каждый из следующих вопросов? 1) ?- f(s(1), A). 2) ?- f(s(s(1)), two). 44 3) ?- f(s(s(s(s(s(s(1)))))), C). 4) ?- f(D, three). Введите последовательность из четырех ваших ответов через пробелы в по- рядке нумерации (каждый ваш ответ - натуральное число, представляющее количество ответов пролог-системы на вопрос). Вопрос 12 Дана программа на Прологе. 'большой'('медведь'). 'большой'('слон'). 'маленький'('кот'). 'коричневый'('медведь'). 'черный'('кот'). 'серый'('слон'). 'темный'(Z):-'черный'(Z). 'темный'(Z):-'коричневый'(Z). В каком из следующих двух случаев системе приходится производить боль- шую работу для нахождения ответа? 1) ?- 'большой'(X), 'темный'(X). 2) ?- 'темный'(X), 'большой'(X). Указание. Время работы оценивайте в количестве шагов; на каждом шаге вы- числяется новый список целей, список целей меняется после каждой успеш- ной унификации или возврата. Введите номер запроса. Вопрос 13 В Прологе функтор ''.'' с двумя аргументами можно использовать для пред- ставления списков наряду с более удобным представлением с квадратными скобками. Представьте список [1,2,3,4] с помощью функтора ".". Введите от- вет - строку символов без пробелов. Вопрос 14 Пролог. Какое из следующих представлений списка эквивалентно представ- лению [a, b, c]? 1) [a|[b, c]] 2) [a, b| [c]] 3) [a, b, c|[]] 4) [a, .(b|[c])] Введите последовательность из четырех ответов через пробелы в порядке ну- мерации (варианты ответов: да, нет). 45 Вопрос 15 Пролог. Какую конкретизацию получит переменная L в результате вычисле- ния цели ?- L1 = [a,b,z,z,c,z,z,z,d,e], append(L, [z,z,z|_],L1). Введите ответ - строку символов без пробелов. Вопрос 16 Пролог. Какую конкретизацию получит переменная L в результате вычисле- ния следующей цели? ?- append(L, [_,_,_],[a,b,c,d]). Введите ответ - строку символов без пробелов. Вопрос 17 Пролог. Какую конкретизацию получит переменная L в результате вычисле- ния следующей цели? ?- append([_,_,_|L], [_,_,_],[0,1,2,3,4,5,6,7]). Введите ответ - строку символов без пробелов. Вопрос 18 Определен следующий прологовский предикат p(X, [X]). p(X, [H|T]):- p(X, T). Какую конкретизацию получит переменная L в результате вычисления сле- дующей цели? ?- p(L, [1,2,3,4,5]). Введите ответ - строку символов без пробелов. Вопрос 19 Определен следующий прологовский предикат p([], []). p([H|T], L):- p(T, L1), append(L1, [H], L). Какую конкретизацию получит переменная L в результате вычисления сле- дующей цели? ?- p([1,2,3], L). Введите ответ - строку символов без пробелов. Вопрос 20 Определен следующий прологовский предикат p([H|T], L):- append(T, [H], L). Какую конкретизацию получит переменная L в результате вычисления сле- дующей цели? ?- p([1,2,3], L). 46 Введите ответ - строку символов без пробелов. Вопрос 21 Дана прологовская программа t(zero, 0). t(one, 1). t(two, 2). p([],[]). p([H|T], [H1|L]) :- t(H, H1), p(T, L). Какую конкретизацию получит переменная L в результате вычисления сле- дующей цели? ?- p([one, zero, two], L). Введите ответ - строку символов без пробелов. Вопрос 22 Пролог. Дано определение предиката 'разбиение списка'([], [], []). 'разбиение списка'([X], [X], []). 'разбиение списка'([X, Y|T], [X| T1], [Y| T2]):- 'разбиение списка'(T, T1, T2). Какой список получится длиннее при выполнении цели ?- 'разбиение списка'([1,2,3,4,5], L1, L2). L1 или L2? Варианты ответов: 1) список L1; 2) список L2; 3) списки равны по длине. Введите номер правильного ответа. Вопрос 23 Пролог. Определим предикат length для вычисления длины списка: length([], 0). length([_|T], N) :- length(T, N1), N is 1+N1. Если во втором правиле в его теле поменять две цели местами, то при вызове ?- length([1, 2, 3], N). произойдет следующее: 1) интерпретатор не сможет вычислить цель, а сообщит об ошибке; 2) N получит значение равное 3; 3) цель успешно вычислится, но N в качестве значения получит не число; 4) интерпретатор ответит: No. Введите номер правильного ответа. 47 Вопрос 24 Пролог. Определим предикат length для вычисления длины списка: length([], 0). length([_|T], N) :- length(T, N1), N = 1+N1. При вызове ?- length([1, 2, 3], N). произойдет следующее: 1) интерпретатор не сможет вычислить цель, а сообщит об ошибке; 2) N получит значение равное 3; 3) цель успешно вычислится, но N в качестве значения получит не число; 4) интерпретатор ответит: No. Введите номер правильного ответа. Вопрос 25 Пролог. Определим предикат length для вычисления длины списка: length([], 0). length([_|T], N) :- N = 1+N1, length(T, N1), При вызове ?- length([1, 2, 3], N). произойдет следующее: 1) интерпретатор не сможет вычислить цель, а выдает сообщение об ошибке; 2) N получит значение равное 3; 3) цель успешно вычислится, но N в качестве значения получит не число; 4) интерпретатор ответит: No. Введите номер правильного ответа. |