Функциональное и логическое программирование (курсовой проект)

ВАРИАНТЫ ТЕМ ДЛЯ КУРСОВЫХ РАБОТ 1. Упрощение электрических цепей
Постановка задачи.
Цепь состоит из компонентов только трех видов: резисторов, емкостей и индуктивностей. Преобразовать цепь в более простую, используя упрощающие правила при параллельном и последовательном соединении компонент одного вида. Треугольники преобразовывать в звезды. Язык программирования: SWI-prolog.
Используйте следующее представление предметной области. Структуры r(Номинал), l(Номинал) и c(Номинал) изображают соответственно резистор, индуктивность и емкость с номиналами. Вся цепь представляется в базе данных фактами вида
comp(<метка элемента>,
<элемент: резистор, индуктивность или емкость>,
<список узлов элемента>).
Упрощение цепи сводится к изменению базы данных.

2. Программа для алгебраических вычислений
Объекты, с которыми вы будете работать, - это многочлены от одной переменной, представленные в символьном виде с вещественными коэффициентами. Многочлены должны изображаться как арифметические выражения, так умножение изображается знаком ‘*’, а возведение в степень - знаком ‘^’. Язык реализации - SWI-Prolog.
Для манипуляций с многочленами нужны некоторые предикаты, чтобы пользователь мог получать ответы на вопросы, на которые не удается ответить с помощью традиционных языков программирования. Для этого вам понадобится обозначать многочлены идентификаторами и хранить в базе данных пару (имя многочлена, сам многочлен). Предикаты выполняют некоторые операции над своими операндами и помещают результат в качестве значения некоторого имени многочлена.
Список предикатов.
1. Ввести многочлен и записать его под некоторым именем.
2. Образовать алгебраическую сумму (разность, произведение) двух многочленов и записать полученный многочлен под некоторым именем.
3. Возвести данный многочлен в целую степень и результат записать под некоторым именем.
4. Заменить каждое вхождение переменной в многочлене на данный многочлен и результат записать под некоторым именем.
5. Вычислить производную многочлена по переменной и результат записать под некоторым именем.
6. Напечатать данный многочлен.
Многочлен представлять в виде суммы членов, включающих только операции умножения и возведения в степень. В каждом таком одночлене все константы перемножены и образуют числовой коэффициент (первый сомножитель), далее идет переменная в некоторой степени. Следует приводить подобные члены, т. е. объединять одночлены, имеющие одинаковые степени переменной, с соответствующим изменением коэффициентов.
Литература (полезная, но можно без нее обойтись)
1. Уэзерелл Ч. Этюды для программистов: Пер. с англ.-М.: Мир,1982.- С. 114-120.
2. Стерлинг Л., Шапиро Э. Искусство программирования на языке ПРОЛОГ.- М.: Мир.- С. 57-61.
Указания. Некоторые фрагменты программы:

% Полиномы хранятся в виде фактов
% pol(+Name, -<список одночленов>).

% Ввод полинома: enter(+Name)

enter(X):-
write('Введите полином с именем '),write_ln(X),
enter(X,[],_).

enter(X,S,P):-
write_ln('Введите очередной одночлен или end'),
read(T),
((T=end,place(X,S,P));
(T \= end,
enter(X,[T|S],P))).

% привести подобные во введенном полиноме, упорядочить члены
% загрузить в базу данных

place(X,S,P):-
merge(S,[],P),
retractall(pol(X,_)),
assert(pol(X,P)).

% сложение полиномов, представленных списками одночленов
merge([],L,L).
merge([X|L1],L2,L):-
insert(X,L2,L3),
merge(L1,L3,L).

insert(X,[],[X]).
insert(X,[Y|T],[Z|T]):-
equal(X,Y,Z),Z \= 0,!.
insert(X,[Y|T],T):-
equal(X,Y,0),!.
insert(X,[Y|T],[X,Y|T]):-
low(X,Y).
insert(X,[Y|T],[Y|T1]):-
not(low(X,Y)),
insert(X,T,T1).

/* equal(X,Y,Z) - из двух мономов X, Y при приведении подобных получаем Z
low(X,Y) - моном X предшествует моному Y */

% приведение полинома к более "читабельному" виду
canon([],0).
canon([X],X).
canon([X,Y],Y+X).
canon([X,Y|T],Z+Y+X):-
length(T,M),M>0,
canon(T,Z).

% показать полином
show(X):-
pol(X,P),
canon(P,P1),
write('Полином с именем '),write_ln(X),write_ln(P1).

% сложение полиномов
plus_pol(X,Y,Z):-
pol(X,P1),
pol(Y,P2),
merge(P1,P2,P),
retractall(pol(Z,_)),
assert(pol(Z,P)),
show(Z).

Протокол:
?- enter(a).
Введите полином с именем a
Введите очередной одночлен или end
-8*x^5.
Введите очередной одночлен или end
9.
Введите очередной одночлен или end
10*x^5.
Введите очередной одночлен или end
x^3.
Введите очередной одночлен или end
-7*x^3.
Введите очередной одночлен или end
end.
Yes

?- show(a).
Полином с именем a
2 * x ^ 5 + -6 * x ^ 3 + 9
Yes

?-plus_pol(a,a,b).
Полином с именем b
4 * x ^ 5 + -12 * x ^ 3 + 18
Yes

3. Игра "Суммируйте до 20"
Два игрока по очереди называют какое-либо число в интервале от 1 до 3 включительно. Названные числа суммируются, выигрывает тот игрок, сумма чисел после хода которого равна 20. Напишите программу на SWI-Prologе, выигрывающую данную игру на стороне компьютера.
Указания. Используйте запоминающие функции (см. "Курс лекций по логическому программированию"). Напишите программу в таком виде, чтобы ее можно было легко модернизировать для решения более общей задачи. Более общая задача: перед началом игры компьютер спрашивает "Какой список допустимых ходов (какие числа можно называть) и какая предельная (выигрышная) сумма?"

4. Задача Прима-Краскала (“жадный” алгоритм) на Прологе
Дана плоская страна и в ней n городов. Нужно соединить все города телефонной связью так, чтобы общая длина телефонных линий была минимальной.
Уточнение задачи. В задаче речь идет о телефонной связи, т. е. подразумевается транзитивность связи: если i-й город связан с j-ым, а j-ый с k-ым, то i-й связан с k-ым. Подразумевается также, что телефонные линии могут разветвляться только на телефонной станции, а не в чистом поле. Наконец, требование минимальности (вместе с транзитивностью) означает, что в искомом решении не будет циклов. В терминах теории графов задача Прима-Краскала выглядит следующим образом:
Дан граф с n вершинами; заданы длины ребер. Найти остовное дерево минимальной длины.
Как известно, дерево с n вершинами имеет n-1 ребер. Оказывается, каждое ребро надо выбирать жадно (лишь бы ни возникали циклы).
Алгоритм Прима-Краскала
(краткое описание)
В цикле n-1 раз делай:
"выбрать самое короткое еще не выбранное ребро при условии, что оно не образует цикл с уже выбранными".
Выбранные таким образом ребра образуют искомое остовное дерево. Напишите программу для решения задачи Прима-Краскала на SWI-Prologе.

5. Задача Прима-Краскала (“жадный” алгоритм) на Лиспе
Решите задачу Прима-Краскала (см. предыдущую тему) на языке XLisp.

6. Упрощение арифметических выражений
Назовем арифметическим выражением терм, при конструировании которого используются только атомы, числа, скобки и знаки арифметических операций. Напишите программу для упрощения арифметических выражений на SWI-Prologе.
В целом, задача упрощения выражений является достаточно сложной и в каком-то смысле неконкретизованной, т. к. единого верного решения для этой задачи нет. Если арифметическое выражение имеет несколько вариантов более простого представления, то какой из них выбрать в качестве решения? Это зависит от того, для каких целей нам необходимо упрощение.
Задачу упрощения выражения поставим следующим образом. Необходимо найти эквивалентное выражение, форма записи которого является более короткой, чем форма записи исходного выражения. Для упрощения выражений используйте различные рекурсивные "правила переписывания", каждое из которых "упрощает" какое-нибудь подвыражение в исходном выражении. Правила переписывания должны соответствовать обычным математическим преобразованиям, как-то: приведению подобных и т. п., и представляются правилами Пролога (см. программу "дифференцирование выражений" из курса лекций).
Ваша программа должна быть некоторым компромиссом между желательной простотой написания и той сложностью, которой от нее требует поставленная задача.

Литература (не обязательная): Лорьер Ж.-Л. Системы искусственного интеллекта. - М., Мир, 1991.- С. 129-131, 471.

7. Определение связности графа на Прологе
Напишите программу на SWI-Prologе, определяющую является ли данный неориентированный граф связным.
Указание: запрограммируйте предварительно предикат path(+X,+Y), проверяющий, существует ли путь из вершины X в вершину Y.

8. Определение связности графа на Лиспе
Напишите программу на языке XLisp, определяющую, является ли данный неориентированный граф связным.
Указание: запрограммируйте предварительно предикат (path X Y), проверяющий, существует ли путь из вершины X в вершину Y.

9. Определение эйлерова пути на Прологе
Напишите программу на SWI-Prologе, определяющую эйлеровый путь, начинающийся с заданной вершины в неориентированном графе. Путь называется эйлеровым, если проходит через все ребра графа по одному разу. Теорема Эйлера утверждает, что такой путь всегда существует, если количество вершин в графе с нечетной степенью равно 0 или 2. Степень вершины - это количество ребер, которые инцидентны данной вершине. Если количество вершин с нечетной степенью равно 2, то эйлеровый путь всегда начинается в одной из таких вершин.

10. Определение эйлерова пути на Лиспе
Напишите программу на языке XLisp, определяющую эйлеровый путь, начинающийся с заданной вершины в неориентированном графе (см. предыдущую тему).

11. Определение компонент связности на Прологе
Напишите программу на SWI-Prologе, определяющую компоненты связности данного неориентированного графа. Каждая компонента связности - список вершин, следовательно, решением задачи должен быть список списков.
Указание: запрограммируйте предварительно предикат path(+X,+Y), проверяющий, существует ли путь из вершины X в вершину Y.





12. Определение компонент связности на Лиспе
Напишите программу на языке XLisp, определяющую компоненты связности данного неориентированного графа. Каждая компонента связности - список вершин, следовательно, решением задачи должен быть список списков.
Указание: запрограммируйте предварительно предикат (path X Y), проверяющий, существует ли путь из вершины X в вершину Y.

5. КАК ВЫПОЛНЯТЬ КУРСОВУЮ РАБОТУ И ОФОРМЛЯТЬ
ПОЯСНИТЕЛЬНУЮ ЗАПИСКУ

Общие положения

Основные задачи и цели курсового проектирования:
1) приобретение навыков и методов программирования достаточно
сложных задач на языках логического программирования;
2) подготовка к выполнению дипломного проекта.
В курсовой работе должна быть разработана тема в соответствии с заданием, одобренным кафедрой.

Общие требования к построению пояснительной записки (ПЗ)

Структура построения ПЗ

ПЗ к работе должна содержать следующие разделы:
1) титульный лист;
2) аннотацию;
3) задание на проектирование;
4) содержание;
5) введение;
6) основная часть работы;
7) заключение;
8) список литературы;
9) приложения.

Титульный лист
Титульный лист оформляется согласно ГОСТ 2.105-79, форма титульного листа приведена в приложении 1.

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

Задание на проектирование
Форма задания заполняется студентом в соответствии с полученным заданием. Форма задания приведена в приложении 2.

Содержание
Содержание включает наименования всех разделов, подразделов
и пунктов, если они имеют наименование, а также список литературы
и приложения с указанием номера страниц, на которых они начинаются. Слово "Содержание" записывается в виде заголовка, симметрично тексту, прописными буквами. Пример оформления содержания приведен в приложении 3.

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

Заключение
Заключение должно содержать краткие выводы по выполненной работе. Также следует указать, чему программист научился на примере этой задачи (на этот вопрос легко ответить, если сформулировать его в виде: "Что я в следующий раз сделаю иначе?").

Список литературы
В список литературы входят все те и только те источники литературы, на которые имеются ссылки в ПЗ. Примеры библиографических описаний источников, помещаемых в список литературы, приведены в приложении 4.

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


Основная часть курсовой работы

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

Об описании алгоритма
Прежде всего, нужно иметь в виду, что такое описание предназначено не для машины, а для человека. Другими словами, речь идет не о программе, а о некотором тексте (т. е. о словесном описании), по которому можно получить представление об общей структуре разрабатываемого алгоритма, о смысле его отдельных шагов и их логической взаимосвязи. Сохранение
достаточно высокого уровня описания алгоритма также облегчает его обоснование. Поэтому шаги алгоритма должны описываться в терминах тех объектов и отношений между ними, о которых идет речь в формулировке задачи. Например, для "геометрической" задачи шаги алгоритма следует описывать как действия над точками, прямыми и т. п., как проверки свойств типа принадлежности трех точек одной прямой и т. п. Но не должно быть работы с кодами этих объектов, например с матрицей координат точек некоторого множества.
При программировании на Прологе описание предикатов должно заключаться в указании, для каких отношений между сущностями (объектами предметной области) они введены. Какие аргументы предиката являются входными, а какие выходными? При программировании на Лиспе для описания функций должно быть указано, что функция вычисляет, а не как она это делает.
Нужно подобрать набор тестов, достаточный для демонстрации работы программы и ее реакции на экстремальные ситуации и неправильное обращение.

Правила оформления ПЗ к курсовой работе

ПЗ пишется в редакторе MS Word шрифтом Times New Roman, размером 12, на формате A4. Нумерация страниц должна быть сквозной, первой страницей является титульный лист. Номер страницы проставляется вверху посередине. Заголовки разделов пишутся прописными буквами по середине текста. Заголовки подразделов пишутся с абзаца строчными буквами, кроме первой прописной. В заголовке не допускаются переносы слов. Точку в конце заголовка не ставят. Если заголовок состоит из двух предложений, то их разделяют точкой.