Методы сортировки списков и их Пролог программы

Название	Методы сортировки списков и их Пролог программы
Дата	04.10.2021
Размер	0.64 Mb.
Формат файла
Имя файла	KR_Naumenko.docx
Тип	Курсовая #241209

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ФГБОУ ВО «НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ «МЭИ»»
ИНЖЕНЕРНО-ЭКОНОМИЧЕСКИЙ ИНСТИТУТ

КУРСОВАЯ РАБОТА
по дисциплине «Интеллектуальные информационные системы»
Тема: «Методы сортировки списков и их Пролог - программы»

Студент группы ИЭ-65-17 Науменко В.И.

(Ф.И.О.)
Руководитель к.т.н., доцент Карпович Е.Е.

(уч. степень, звание, Ф.И.О.)

Сдана на проверку

Возвращена на доработку

Допущена к защите

Оценка

Москва-2020

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 3

2.Цель курсовой работы 3

3.Задачи курсовой работы 3

4.Списки как структура данных языка Prolog 4

5.Понятие рекурсии в Prolog. Рекурсивная обработка списков. 4

6.Алгоритмы сортировки списков на языке Prolog 6

6.1.Сортировка пузырьком (Bubble sort) 6

6.2.Сортировка вставками (Insertion sort) 9

6.3.Сортировка выбором (Selection sort) 11

6.4.Быстрая сортировка (Quicksort) 14

6.5.Сортировка слиянием (Merge sort) 17

1.1.Встроенный предикат sort/msort реализации SWI-Prolog 21

7.Эффективность алгоритмов сортировки 22

ЗАКЛЮЧЕНИЕ 24

Список литературы 25

ВВЕДЕНИЕ

В языках, предназначенных для программирования задач искусственного интеллекта, важную роль играют динамические структуры данных, называемые списками. Главное достоинство списков состоит в том, что при их обработке операции вставки, замены и удаления элементов выполняются весьма просто. Наиболее часто используемыми алгоритмами работы со списками являются алгоритмы сортировки списков. Так как список может содержать большое количество элементов, алгоритмы сортировки должны быть эффективными, то есть процесс сортировки должен происходить за минимальной количество времени.

Цель курсовой работы

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

Задачи курсовой работы

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

Изучить принципы работы основных алгоритмов сортировки;
Рассмотреть основную структуру данных языка Prolog – список;
Изучить основные инструменты работы со списками в реализации SWI-Prolog;
Разработать программные реализации изученных алгоритмов сортировки на языке Prolog;
Выполнить тестирование и анализ эффективности разработанных алгоритмов.

Списки как структура данных языка Prolog

Список в языке Пролог представляет собой заключенную в квадратные скобки [ ] последовательность термов, разделенных запятыми:
[<терм₁>, <терм₂>,…<терм_n>].

Структура Список может быть представлена в виде так называемой точечной пары (H, T), где Н  первый элемент списка, называемый головой списка, а Т  все остальные элементы списка, называемые хвостом списка. Голова списка является термом, а хвост  списком.

В языке Пролог список, разделенный на головы и хвост, обозначается следующим образом: [H|T], например [a|[b,c,d,e]]. Возможность разделения списка на голову и хвост играет важную роль в программировании рекурсивных процедур обработки списков, в частности в реализации алгоритмов сортировки.

Число элементов в списке называется длиной списка. Длина списка может динамически изменяться в процессе выполнения запроса. Список, не имеющий ни одного элемента, обозначается [ ] и называется пустым списком. Длина пустого списка равно нулю. Пустой список нельзя разделить на голову и хвост.

Понятие рекурсии в Prolog. Рекурсивная обработка списков.

Рекурсия – одна из основных особенностей языка Prolog. Наиболее часто рекурсия применяется для обработки списков в сочетании с возможностью разделять список на голову и хвост.

Правило, содержащее свой заголовок в качестве предиката в правой части этого правила, называется рекурсивным. Рекурсивное правило реализует повторяющиеся действия.

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

В общем случае рекурсивная процедура имеет следующий вид:

<заголовок рекурсивного правила>:<предикат условия выхода>, <предикаты>.

<заголовок рекурсивного правила >:<предикаты>,

<заголовок рекурсивного правила >,<предикаты>.

<заголовок рекурсивного правила >:<предикаты>,

<заголовок рекурсивного правила >,<предикаты>.

…………………………………………..

<заголовок рекурсивного правила >:<предикаты>,

<заголовок рекурсивного правила >,<предикаты>.

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

Чтобы обеспечить проверку условий завершения рекурсивных вызовов, рекомендуется не рекурсивное правило с условием выхода записывать перед рекурсивными правилами.
Пример рекурсивной обработки списков на основе встроенных рекурсивных правил реализации SWI-Prolog:

Предикат Length(L, N). Определение длинны списка.

Процедура Length(L, N) состоит из двух правил:

length([],0).

length([_|T], N):length(T, N1),N is N1+1.

Декларативное описание предиката length(L, N) формулируется следующим образом:

Предикат length(X, 0) будет истинным, если X пустой список, т.е. длина пустого списка равна нулю. Если список можно разделить на голову и хвост, то длина списка равна длине хвоста списка плюс 1.

Предикат Member(X, Y). Определение принадлежности элемента Х списку Y.

Процедура Member(X, Y) состоит из двух правил:

member(X,[X|_]).

member(X,[_|T]): member(X,T).

Декларативное описание предиката Member(X, Y) формулируется следующим образом:

Любой терм X принадлежит списку Y, если терм Х является головой списка Y или Х принадлежит хвосту списка Y. В этих двух случаях значение предиката member(X, Y) будет истинным.

Как можно заметить, при обработке списков в основном используются рекурсивные правила. Список разделяют на голову и хвост, затем рекурсивно вызывают правило от хвоста списка, тем самым повторяя те же действия разделения, параллельно выполняя необходимые вычисления с головным элементом списка.

Так как в большинстве алгоритмов сортировки списков необходимо сравнивать элементы, проходя по списку, в процедурах сортировки также применяются рекурсивные правила.

Алгоритмы сортировки списков на языке Prolog
1. Сортировка пузырьком (Bubble sort)

Алгоритм состоит из повторяющихся проходов по сортируемому списку. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов.

Проходы по списку повторяются N-1{\displaystyle N-1} раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — список отсортирован. Пример сортировки методом пузырька представлен ниже (см. Рис. 3 .1).

Рис. 3.1. Визуализация сортировки пузырьком
Реализация алгоритма сортировки пузырьком на языке Prolog выглядит следующим образом:

Чтобы упорядочить непустой список L = [X,Y|T], необходимо:

Сравнить элементы Х и Y, меньший элемент записать в новый список, больший обработать рекурсивно, сравнив с элементами хвоста T, тем самым максимальный элемент будет перенесен в конец списка L. Затем рекурсивно повторить те же действия;
Если при очередном переносе максимального элемента в конец списка L, исходный список L не изменился, то список отсортирован.

Процедура sort_bubble(L1, L2) выглядит следующим образом:

bubble([],[]):-!.

bubble([EL],[EL]):-!.

bubble([X,Y|T],[Y|T1]):-X>Y,!,

bubble([X|T],T1).

bubble([X, Y|T],[X|T1]):-

bubble([Y|T],T1).
sort_bubble(LS,LS):-bubble(LS, LDS),

LS=LDS,!.

sort_bubble(L,LS):-bubble(L,L1),

sort_bubble(L1,LS).

Предикат bubble(L1, L2) истинен, если список L2 получается из списка L1 переносом максимального элемента списка L1 в конец. Данный предикат сравнивает попарно элементы L1, наибольший элемент передается для рекурсивной обработки, меньший элемент записывается в начало списка L2.

Предикат sort_bubble(L1,LS) истинен, если список LS получен из списка L1 путем упорядочения списка L1 по возрастанию пузырьком. Первое правило sort_bubble вызывает процедуру bubble, если полученный в результате список совпал с исходным — сортировать уже нечего, надо вернуть результат. В противном случае, результат работы функции обрабатывается рекурсивно.

Сортировка пузырьком является малоэффективным алгоритмом со сложностью O(n²).

Результат работы Prolog - программы сортировки списка методом пузырька представлен на рисунке ниже (см. Рис. 3 .2).

Рис. 3.2. Результат выполнения сортировки пузырьком

Сортировка вставками (Insertion sort)

Алгоритм, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.

Пример сортировки методом пузырька представлен ниже (см. Рис. 3 .3).

Рис. 3.3. Визуализация сортировки вставками

Реализация алгоритма сортировки вставками на языке Prolog выглядит следующим образом:

Чтобы упорядочить непустой список L = [X|T], необходимо:

Упорядочить хвост списка, получив список OT;
Вставить голову X списка L в упорядоченный список OT, поместив X в такое место списка OT, что список OT остался бы упорядоченным.

Процедура sort_insert(L1, LS) выглядит следующим образом:

sort_insert([],[]).

sort_insert([X|T],OL):-

sort_insert(T,OT),insert(X,OT,OL).
insert(X,[],[X]).

insert(X,[Y|T],[X,Y|T]):- X=
insert(X,[Y|T],[Y|T1]):- insert(X,T,T1).

Процедура sort_insert использует процедуру insert, которая вставляет терм в упорядоченный список, не нарушая упорядочивания.

Предикат insert(X,L1,L2) истинен, если список L2 получается из упорядоченного списка L1 путем вставки терма X без нарушения порядка.

В процедуре insert сравниваются числовые термы с помощью операций сравнения чисел: >, <, >=, =< или символьные термы с помощью операций сравнения символов: @>, @<, @>=,@=<.

Предикат sort_insert(L1,LS) истинен, если список LS получен из списка L1 путем упорядочения списка L1 по возрастанию методом вставки.

Сортировка вставками является малоэффективным алгоритмом со сложностью O(n²).

Результат работы Prolog - программы сортировки списка методом вставок представлен на рисунке ниже (см. Рис. 3 .4).

Рис. 3.4. Результат выполнения сортировки вставками

Сортировка выбором (Selection sort)

В общем виде алгоритм сортировки выбором содержит следующие шаги:

Находим номер минимального значения в текущем списке;
Производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции);
Теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы.

Пример сортировки методом выбора представлен на рисунке ниже (см. Рис. 3 .5).

Рис. 3.5. Визуализация сортировки выбором
Реализация алгоритма сортировки списка методом выбора в языке Prolog включает в себя следующие шаги:

В исходном списке L находится минимальный элемент Min и помещается в результирующий список L1.
Этот элемент удаляется из списка L, и процедура поиска повторяется. С каждым шагом список L уменьшается.
Когда список L станет пустым, список L1 станет результирующим, упорядоченным по возрастанию списком.

Процедура sort_selection использует следующие процедуры:

sort_selection(<исходный список>, <накапливающийся список>,
<результирующий список>)  процедура накопления списка;
delete_element(<терм>, <список>, <список>)  процедура удаления элемента из списка;
append(<список>, <список>, <список>)  встроенная процедура объединения списков;
min_lst(<список>, <терм>)  процедура определения минимального элемента в списке;
min(<терм>, <терм>, <терм>)  процедура определения меньшего из двух термов.

В процедуре min сравниваются числовые термы с помощью операций сравнения чисел >, <, >=, =< или символьные термы с помощью операций сравнения символов @>, @<, @>=,@=<.

Предикат sort_selection(L, LS)истинен, если список LS получен из списка L путем упорядочения списка L по возрастанию методом прямого выбора. Списки L и LS являются списками числовых термов.

Процедура sort_selection(L, LS) выглядит следующим образом:

%Минимум из двух термов

min(X,Y,X):-X=
min(_,Y,Y).
%Минимальный элемент списка

min_lst([MIN],MIN):-!.

min_lst([H|T],MIN):-min_lst(T,MIN1), min(H,MIN1,MIN).
%Удаление элемента из списка

delete_element(EL,[EL|T],T):-!.

delete_element(EL,[H|T],[H|T1]):- delete_element(EL,T,T1).
%Сортировка выбором

sort_selection(L,LS):-sort_selection(L,[],LS).
sort_selection([],LS,LS):-!.

sort_selection(L,L1,LS):-min_lst(L,MIN),

delete_element(MIN,L,L2),

append(L1,[MIN],L3),

sort_selection(L2,L3,LS).

Сортировка выбором является малоэффективным алгоритмом со сложностью O(n²).

Результат работы Prolog - программы сортировки списка методом выбора представлен на рисунке ниже (см. Рис. 3 .6).

Рис. 3.6. Результат выполнения сортировки выбором

Быстрая сортировка (Quicksort)

QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его вариант известен как «Пузырьковая сортировка») известного в том числе своей низкой эффективностью.

Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы. (Таким образом улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных улучшенных методов.)

Общая идея алгоритма состоит в следующем:

Выбрать из списка элемент, называемый опорным. Это может быть любой из элементов списка. От выбора опорного элемента не зависит корректность алгоритма, но в отдельных случаях может сильно зависеть его эффективность.
Сравнить все остальные элементы с опорным и переставить их в списке так, чтобы разбить список на три непрерывных отрезка, следующих друг за другом: «элементы меньшие опорного», «равные» и «большие».
Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.

На практике список обычно делят не на три, а на две части: например, «меньшие опорного» и «равные и большие»; такой подход в общем случае эффективнее, так как упрощает алгоритм разделения.

Пример применения быстрой сортировки представлен на рисунке ниже (см. Рис. 3 .7).

Рис. 3.7. Визуализация быстрой сортировки

Реализация алгоритма быстрой сортировки в языке Prolog выглядит следующим образом:

В качестве опорного элемента P выбирается голова исходного списка L;
Исходный список L делится на список LT, содержащий элементы списка L, меньшие P и список GT, содержащий элементы списка L, большие или равные P;
Для полученных списков рекурсивно применяется повторная процедура сортировки;
Полученные отсортированные списки соединяются в результирующий.

Процедура sort_quick(L, LS) выглядит следующим образом:

cut_list([],_,[],[]):-!.

cut_list([H|T],P,LT,[H|GT]):-H>=P,!,

cut_list(T,P,LT,GT).

cut_list([H|T],P,[H|LT],GT):-

cut_list(T,P,LT,GT).
sort_quick([],[]).

sort_quick([EL],[EL]).

sort_quick([P|T],LS):-

cut_list(T,P,LT,GT),

sort_quick(LT,LTS),

sort_quick(GT,GTS),!,

append(LTS,[P|GTS],LS).

В процедуре cut_list(L,P,LT,GT) формируются списки LT и GT, содержащие элементы списка L, меньшие или большие опорного элемента P. Если голова H списка L больше или равна P, тогда H добавляется в список GT, иначе H добавляется в список LT.

Процедура append(L1,L2,L3) является встроенной процедурой SWI-Prolog. Данный предикат истинен, если список L3 получен путем присоединения всех элементов списка L2 в конец списка L1.

Процедура sort_quick(L,LS) истинна, если список LS получен из списка L, путем применения алгоритма быстрой сортировки.

Сортировка выбором является одной из самых быстрых известных алгоритмов сортировки списков. Имеет среднюю сложность O(n*logn).

Результат работы Prolog - программы сортировки списка методом быстрой сортировки представлен на рисунке ниже (см. Рис. 3 .8).

Рис. 3.8. Результат выполнения быстрой сортировки

Сортировка слиянием (Merge sort)

Сортировка слиянием – один из алгоритмов сортировки, использующий принцип «разделяй и властвуй», когда исходный список разделяется на более мелкие части, которые рекурсивно обрабатываются и комбинируются, получая отсортированный итоговый список.

Алгоритм сортировки слиянием схож с алгоритмом быстрой сортировки и включает в себя следующие этапы:

Сортируемый список разбивается на две части примерно одинакового размера;
Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
Два упорядоченных списка половинного размера соединяются в один.

Пример применения сортировки слиянием представлен на рисунке ниже (см. Рис. 3 .9).

Рис. 3.9. Визуализация сортировки слиянием

Так как в Prolog используются списки, являющиеся динамической структурой данных, разделить их пополам проблематично, так как их длина заранее неизвестна, а применения встроенного предиката length на каждом этапе алгоритма неэффективно. Поэтому в реализованном алгоритме список будет разделяться на две части исходя из четности и нечетности индекса элемента.

Реализация алгоритма сортировки слиянием в языке Prolog выглядит следующим образом:

Исходный список L разделяется на список L1, содержащий элементы с нечетными индексами и список L2, содержащий элементы c четными индексами;
Для полученных списков рекурсивно применяется повторная процедура сортировки;
Полученные отсортированные списки LS1 и LS2 сливаются в результирующий список LS таким образом, что полученный список LS является отсортированным списком L.

Процедура sort_merge(L, LS) выглядит следующим образом:
split_into_half([],[],[]):-!.

split_into_half([EL],[EL],[]):-!.

split_into_half([OD,EV|T],[OD|ODT],[EV|EVT]):-

split_into_half(T,ODT,EVT).
merge([],L2,L2):-!.

merge(L1,[],L1):-!.

merge([H1|T1],[H2|T2],[H1|T3]):-H1

merge(T1,[H2|T2],T3).

merge(L1,[H2|T2],[H2|T3]):-

merge(L1,T2,T3).
sort_merge([],[]):-!.

sort_merge([EL],[EL]):-!.

sort_merge(L,LS):-

split_into_half(L,L1,L2),

sort_merge(L1,LS1),

sort_merge(L2,LS2),

merge(LS1,LS2,LS).
В процедуре split_into_half(L1,L2,L3) формируются списки L2 и L3, содержащие элементы списка L, имеющие нечетные и четные индексы соответственно.

Процедура merge(L1,L2,L3) обеспечивает слияние отсортированных списков L1 и L2 в L3 так, чтобы список L3 был отсортированным. Сравниваются головы списков L1 и L2 и голова с наименьшим значением добавляется в список L3.

Процедура sort_merge(L,LS) истинна, если список LS получен из списка L, путем применения алгоритма сортировки слиянием.

Сортировка выбором является достаточно быстрым алгоритмом сортировки. Имеет среднюю сложность O(n*logn).

Результат работы Prolog - программы сортировки списка методом слияния представлен на рисунке ниже (см. Рис. 3 .10).

Рис. 3.10. Результат выполнения сортировки слиянием

Встроенный предикат sort/msort реализации SWI-Prolog

Так же стоит отметить, что реализация языка Prolog SWI-Prolog имеет встроенные предикаты sort и msort, предназначенные для сортировки списков.

Оба предиката реализованы на языке C с использованием алгоритма сортировки «естественным слиянием» (Natural Merge sort).

Предикат sort(L,LS) истинен, если список LS получен путем сортировки списка L. При этом все повторяющиеся элементы в списке L, будут удалены, список LS будет содержать только уникальные элементы списка L.

Предикат msort(L,LS) аналогичен предикату sort, но сохраняет повторяющиеся элементы списка L.

Эффективность алгоритмов сортировки

Для более подробного сравнения всех разработанных алгоритмов сортировки были проведены три теста по сортировке списков различной длины.

Для наглядности алгоритмы были разделены на квадратичные (пузырьковая, вставками, выбором) и логарифмические (быстрая, слиянием, msort) в связи с тем, что квадратичные алгоритмы в Prolog имеют слишком большое время выполнения на списках длинной более 1000 элементов, в то время как логарифмические алгоритмы сортируют такие списки за слишком короткое время.

Для проведения тестов была разработана процедура rand_list(S,R,L), генерирующая список L, длины S, состоящий из случайных целых чисел в интервале от 0 до R.

Процедура rand_list(S,R,L) выглядит следующим образом:

rand_list(0,_,[]):-!.

rand_list(S,R,[H|T]):-

S>0,

NS is S - 1, random_between(0,R,H), !,

rand_list(NS,R,T).

Встроенный предикат random_between(S,E,EL) возвращает целое число EL, лежащее в интервале от S до E.

Для измерения времени работы алгоритма и вывода результата была описана процедура run, которая выглядит следующим образом:

run:-write('Введите длину списка'),nl,

read(N), integer(N), rand_list(N,L),

write('Base list:'),nl,write(L),nl,

get_time(T), sort_quick(L,LS),

get_time(T1),E is (T1-T)*1000,

write('Время сортировки: '),

write(E),write('ms')

,nl,write('Sorted list:'),nl,write(LS).

Встроенный предикат get_time(T), возвращает время в секундах, датой отсчета считается 01.01.1970г. Разница между временем до запуска алгоритма и после и есть время его работы.

Параметры тестов:

Квадратичные:

Тест 1: 100 случайных чисел от 0 до 10³;

Тест 2: 500 случайных чисел от 0 до 10³;

Тест 3: 1000 случайных чисел от 0 до 10³.

Логарифмические:

Тест 1: 10⁴ случайных чисел от 0 до 10⁵;

Тест 2: 5_*10⁴ случайных чисел от 0 до 10⁵;

Тест 3: 10⁵случайных чисел от 0 до 10⁵.

Каждый тест запускался 20 раз и средний результат был записан в таблицу. Таблица результатов тестирования эффективности алгоритмов приведена ниже (см. Таблица 4 .1).
Таблица 4.1. Сравнение эффективности алгоритмов сортировки

Алгоритм	Асимптотика	Тест 1, мс	Тест 2, мс	Тест 3, мс
Bubble sort		≈4	≈120	≈473
Insertion sort		≈1	≈12	≈51
Selection sort		≈1.5	≈39	≈158
Алгоритм	Асимптотика	Тест 1, мс	Тест 2, мс	Тест 3, мс
Quicksort		≈36	≈220	≈455
Merge sort		≈39	≈231	≈497
msort (Natural merge sort)		≈2.5	≈16	≈33.5

ЗАКЛЮЧЕНИЕ

В ходе написания курсовой работы были выполнены следующие задачи:

Подробно рассмотрены основные алгоритмы сортировок;
Изучены основные инструменты для работы со списками в языке Prolog, такие как рекурсия и разделение списка на голову и хвост;
Разработаны программы, реализующие сортировку списков c использованием базовых алгоритмов на языке Prolog;
Проанализирована эффективность реализованных алгоритмов.

Результаты проведенной работы показали, что реализация SWI-Prolog, будучи системой логического программирования, позволяет реализовывать базовые алгоритмы сортировки, благодаря наличию удобного взаимодействия со списками (разделения на голову и хвост), а также благодаря использованию рекурсии.

Список литературы

Документация по SWI-Prolog: [Электронный ресурс]. SWI-Prolog – реализация языка Prolog. URL: https://www.swi-prolog.org/pldoc/index.html. (Дата обращения: 07.03.2020).
Карпович Е.Е. Программирование на языке Пролог. Учебное пособие, часть 1.– М.: МГГУ, 2002 г. - 97 с.
Солдатова О.П., Лёзина И.В. Логическое программирование на языке Visual Prolog: учебное пособие – Самара: СНЦ РАН, 2010 г. –81 с.
П. А. Шрайнер. Основы программирования на языке Пролог: курс лекций: учеб. пособие для студентов вузов, обучающихся по специальностям в обл. информ. технологий. - М.: Интернет - Ун-т Информ. Технологий, 2005. - 176 с.