Автор: Кабедева Изабелла Геннадьевна

Рубрика: Информатика

Опубликовано в Молодой учёный №1 (24) январь 2011 г.

Статья просмотрена: 407 раз

Библиографическое описание:

Кабедева И. Г. Метод обобщённого правила рекурсии как средство развития логического мышления при изучении декларативного языка программирования Пролог // Молодой ученый. — 2011. — №1. — С. 59-63.

Исследования учёных в области дидактики и педагогической психологии показывают, что «трудности, возникающие обычно у студентов при изучении многих вузовских курсов, в частности, информатики, высшей математики, физики обусловлены не только специфической сложностью самого предмета, сколько недостаточной сформированностью у них общих логических приемов мышления, низким уровнем развития логической культуры мышления» [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

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

Обсуждение

Социальные комментарии Cackle
Задать вопрос