Метод обобщённого правила рекурсии как средство развития логического мышления при изучении декларативного языка программирования Пролог

Исследования учёных в области дидактики и педагогической психологии показывают, что «трудности, возникающие обычно у студентов при изучении многих вузовских курсов, в частности, информатики, высшей математики, физики обусловлены не только специфической сложностью самого предмета, сколько недостаточной сформированностью у них общих логических приемов мышления, низким уровнем развития логической культуры мышления» [12].

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

Учёные утверждают, что очень трудно объяснить, как умственная логика усваивается людьми. Известно, что левое полушарие мозга отвечает за развитие речи и логическое мышление, правое – за интуицию и образное мышление. Существует мнение, что логика является врождённой. Есть противники этой теории, есть сомневающиеся.

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

Опыт обучения студентов программированию на языке Пролог показал, что Пролог является удобной учебно-ориентированной средой, позволяющей использовать его как практический инструмент познавательной деятельности при создании информационно – логических моделей мышления человека. Одно из основных преимуществ языка Пролог — возможность создания программы в терминах решаемой задачи. Таким образом, использование логического программирования позволяет лучше понять логику предложенной проблемы и с помощью неё решить эту проблему.

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

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

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

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

1. Объявить о решении самой простой версии задачи (граничное условие рекурсии), т.е. объявить о непосредственном решении задачи.

2. Упростить задачу с целью сведения решения задачи к решению более простой версии этой же самой задачи.

3. Объявить о решении упрощённой версии задачи.

4. Связать промежуточные решения упрощённой версии задачи с искомыми результатами.

Если задача сформулирована рекурсивным образом, то выполнение этих этапов очевидно. Например, нахождение наибольшего общего делителя (НОД) двух натуральных чисел сводится к нахождению наибольшего общего делителя меньшего из этих чисел и остатка от деления большего числа на меньшее. Процесс продолжается до тех пор, пока остаток не станет равным нулю, т.е. nod(m,n)=nod(r,n), где m>n, r – остаток от деления m на n.

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

Так например, при обработке списков метод ОПР используется совместно с методом деления списка на голову и хвост.

Пример 1. Найти в непустом целочисленном списке элемент под номером N (N – натуральное число).

Sp: [5, | 9, -4, 0, 11, -6], N= 3 X= -4 (*)

H T N-1=2 X1= -4

H – первый элемент списка, называемый головой списка. T – список, состоящий из остальных элементов списка, называемый хвостом списка. X – искомый элемент списка под номером N. Нетрудно заметить, что элемент списка под номером 3 находится в хвосте этого списка под номером 2.

На первом этапе необходимо сформулировать утверждение о непосредственном решении задачи, т.е. о решении самой простой версии этой же задачи. Для этого надо провести анализ условия задачи: выяснить, какие аргументы будет иметь наш предикат poisk(номер элемента, исходный список, искомый элемент), и какие аргументы имеет смысл упрощать. Часто самое простое решение задачи сводится к решению задачи над пустым списком. Как правило, этот вариант и предлагается студентами. В данном случае этот вариант не подходит, так как невозможно найти элемент под каким-либо номером в пустом списке, т.е. для пустого списка решение не определено. Проведённый анализ позволяет прийти к выводу, что упрощать надо значение номера. Самая простая версия этой же задачи – нахождение первого элемента в непустом списке. И решение очевидно: под первым номером в списке находится голова этого списка, что записывается следующим образом:

poisk(1,[H|_],H):-!.

Для выполнения следующего этапа – упрощение задачи, нужно опять проанализировать условие задачи. Поскольку в самой простой версии задачи фигурирует самый маленький номер элемента 1, то, очевидно, что упрощение задачи сведётся не только к отделению от списка головы (тем самым уменьшается количество элементов списка), но и к уменьшению номера искомого элемента на 1. Третий этап требует объявить о решении этой более простой версии задачи, т.е. о том, что элемент под номером N-1 в хвосте списка найден. Четвёртый этап требует умения выполнять операции сопоставления и связывания: нужно сопоставить и связать элемент, находящийся под номером N-1 в хвосте с искомым элементом, находящимся в списке под номером N: это один и тот же элемент. Тогда рекурсивное правило может иметь следующий вид:

poisk (N, Sp, X):-Sp=[_|T], N1=N-1, poisk (N1, T, X1), X=X1.

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

poisk (N, [_|T], X):-N1=N-1, poisk (N1, T, X).

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

Метод ОПР позволяет запрограммировать перестановку, пошагово выполняя перечисленные выше этапы метода. Сортировка выполняется с помощью двух предикатов: первый описывает отношения между исходным списком и отсортированным, второй позволяет в случае необходимости поменять местами элементы списка.

Пример 2. Упорядочить числовой список по возрастанию методом перестановки.

domains

x=integer*

predicates

sort(x,x) /* модуль, осуществляющий сортировку списка */

peres(x,x) /* модуль, осуществляющий перестановку элементов списка */

clauses

sort([],[]). /* граничное условие*/

sort([H|T],Q):-sort(T,Q1), peres([H|Q1],Q).

peres([X],[X]). /* граничное условие*/

peres([H|T],[H1|M]):-T=[H1|T1], H>H1, peres([H|T1],M).

peres([H|T],[H|T]):-T=[H1|_], H<=H1.

goal sort([5,-3,23,16],S).

Ответ: S=[-3,5,16,23]

Анализ условия задачи позволяет выяснить, что в данном случае самое простое решение задачи сортировки списка сводится к решению задачи над пустым списком. Декларативный смысл граничного утверждения рекурсии для процедуры sort(): результатом сортировки пустого списка будет пустой список.

Упрощение задачи сводится к уменьшению количества элементов списка путём отделения головы списка от хвоста. Связь промежуточного результата сортировки (списка, с головой исходного списка и отсортированным хвостом) с окончательным результатом (полностью отсортированным по возрастанию списком) осуществляется с помощью процедуры peres(), которая позволяет переставить голову исходного списка с элементами уже отсортированного хвоста так, чтобы голова оказалась на своём месте.

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

Для того, чтобы поставить первый элемент списка (голову) на своё место, надо сравнить его с соседним – с головой хвоста; если голова хвоста окажется меньше головы исходного списка, то именно она станет головой результирующего списка, а голову исходного списка нужно будет тем же методом перестановки поставить на своё место в «хвосте хвоста» исходного списка. Если же голова исходного списка окажется меньше головы хвоста, то она останется первым элементом списка. Иначе говоря, перестановка осуществляется сравнением первых двух соседних элементов текущего списка, в результате чего меньший оказывается впереди, а больший, в случае необходимости, продолжает свой путь в перестановке.

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

peres([X],[X]). /* граничное условие*/

peres([H|T],[H1|M]):-T=[H1|T1], H>H1, !, peres([H|T1],M).

peres([H|T],[H|T]).

Данный пример показывает, что выполнение всех четырёх этапов построения рекурсивного правила методом ОПР несомненно требует владения операциями анализа, сопоставления и связывания, обобщения.

Метод ОПР успешно применяется и при обработке таких распространённых объектов программирования как строки. Реализацию четырёх этапов построения рекурсивного правила можно проследить на традиционной задаче обращения строки.

Пример 3. Обратить строку. Фрагмент программы:

obr( “”,””). /* граничное условие рекурсии*/

obr(Str,New):- frontstr(1,Str, C, Ost), obr(Ost, New1), concat(New1, C, New).

Декларативный смыл граничного условия рекурсии: при обращении пустой строки будет получена пустая строка. Упрощение задачи сводится к уменьшению количества символов в строке путём отделения первого символа с помощью стандартного предиката frontstr(). Связь промежуточного результата (обращённой строки без первого элемента) с окончательным осуществляется путём конкатенации этого результата с первым символом строки, который присоединяется справа.

В простейших программах – классификаторах часто требуется из введённого произвольного текста построить список из слов с целью проверки на вхождение элементов построенного списка в эталонные списки. Для решения этой задачи можно применить метод ОПР.

Пример 4. Построить список из лексем введённого текста.

Фрагмент программы.

do: - write(“Введите текст ”), readln(Text), spisok_leksem(Text, Spisok), write (“Список: ”, Spisok),nl.

spisok_leksem(“”,[]).

spisok_leksem(Text, [H|T]):- fronttoken(Text, H, Ost), spisok_leksem(Ost, T).

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

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

Пример 5. Построить список из строк файла.

Фрагмент программы.

spisok_strok([]):-eof(file1). /* граничное условие*/

spisok_strok([H|T]):- not(eof(file1)), readln(H), spisok_strok(T).

Успешное овладение студентами методом ОПР несомненно позволяет не только успешно овладеть основами логического программирования на языке Пролог, но и повысить уровень развития культуры логического мышления.

Литература:

1. Адаменко А., Кучуков А. Логическое программирование и Visual Prolog. – С-Птб, “БХВ-Петербург”, 2003.

2. Братко И. Программирование на языке Пролог для искусственного

3. интеллекта. -М., "Мир", 1990.

4. Википедия. Свободная энциклопедия. – http://ru.wikipedia.org/wiki

5. Доорс Дж. и др. Пролог - язык программирования будущего.- М.,1990.

6. Ин С., Соломон Д. Использование Турбо Пролога.-М., "Мир", 1993.

7. Клоксин, Меллиш. Программирование на языке Пролог. 1987.

8. Марселлус Д. Программирование экспертных систем на Турбо - Прологе. - М., "Финансы и статистика", 1994.

9. Могилев А.В. И др. Информатика: Учебное пособие для студ. высш. учеб. заведений. – 2-е изд., стер. – М.: Изд. Центр «Академия», 2001.

10. Могилев А.В. И др. Практикум по информатике: Учебное пособие для студ. пед. вузов. – 2-е изд., стер. – М.: Изд. Центр «Академия», 2001.

11. Марселлус Д. Программирование экспертных систем на Турбо - Прологе. - М., "Финансы и статистика", 1994.

12. http://revolution.allbest.ru/pedagogics/00168579_0.html