15.7. методика обучения логическому программированию

15.7. методика обучения логическому программированию

Логическое программирование в качестве объекта изучения пришло в нашу школу гораздо раньше объектного. В период с 1987 по 1995 г. С.Г.Григорьевым, Е.А.Ерохиной, В.А.Кайминьгм, Н.Д.Угриновичем, А. Г. Щеголевым и другими авторами были разработаны многочисленные методические материалы по логическому программированию. Тем не менее специального пособия по организации курса логического программирования, продолжающего базовый курс информатики, пока не существует.

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

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

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

При планировании курса учитель должен исходить из отпущенных на него часов. Возможно несколько вариантов: ознакомительный 34-часовой курс, более полный 68-часовой или еще больший, носящий характер интегрированного курса (например, с классической логикой и/или математической логикой). Ниже представлены варианты такого планирования.

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

Тема «Введение в Пролог»

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

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

Материалы для этой темы можно найти в предисловии к большинству учебников по Прологу, а также в журнальных статьях, указанных в списке литературы. Если учащиеся уже изучали элементарное введение в Пролог в базовом курсе, то беседа эта может быть сведена к напоминанию основных принципиальных позиций и показу нескольких программ на Прологе. Если нет, то после общего разговора приводим элементарные программы на Прологе, не упоминая ни о каких формальных правилах их построения. Такие программы включают два-три факта и один вопрос, ответ на который, с точки зрения учащихся, очевиден. При этом подчеркните: очевидность ответа для человека означает, что его мозг выполнил некую (пусть и очень простую) программу. Если решать задачу на Паскале, то эту программу придется написать человеку, если же решать ее на Прологе, то сопровождающая его системная программа эту прикладную программу напишет сама. Как она это сделает — вопрос «на потом».

Еще одна важная мысль, которая прозвучит в этой теме, такова: чтобы система могла сама делать логические выводы, исходная информация должна быть чем-то большим, чем совокупность Данных. Эта информация включает связи между входящими в нее элементами. Такая информация — уже не просто данные, а элементарные знания. В связи с этим необходимо ввести элементарные представления о базе знаний, отталкиваясь от противопоставления с хорошо известным учащимся понятием базы данных. База знаний включает информацию о связях между объектами и состоит из фактов и правил, в то время как база данных ограничивается только фактами. Примеры элементарных баз знаний легко найти в Указанных в списке литературы пособиях.

Тема «Факты. Предикатная форма представления фактов.

 Базы данных Пролога. Простые запросы»

Эту тему уместно начать с изучения основ логики, на которой базируется Пролог. На примерах покажите, что такое высказывание (суждение) и то, что всякое высказывание может быть истинным или ложным. Следует дать понятие «утверждение» — суждение, которое требуется доказа/ь или опровергнуть. Другие вопросы математической логики в рамках темы не рассматриваются.

При работе над понятием «факт» следует обратить внимание на то, что в программах на Прологе под фактами понимаются утверждения, истинность которых подразумевается. Принятую в языке предикатную форму записи следует отработать на прямых и обратных примерах, начиная переводом с Пролога на естественный язык. Рекомендуется на примере определенного сюжета (небольшого рассказа, стихотворения) построить базу данных и задать соответствующие вопросы (запросы). В зависимости от поставленного вопроса в сюжете необходимо научиться определять имена фактов, количество и назначение его аргументов. Считается, что базы данных с разными именами предикатов у фактов являются предпочтительными на первоначальном этапе изучения материала. Например, составив базу данных по известному стихотворению «Дом, который построил Джек» [3, т. 2, с. 227], можно определить наличие в ней тех или иных фактов. Достаточно быстро информация, получаемая от системы только такого рода, перестает быть интересной и для получения более разнообразной информации потребуется ввести понятие переменной.

Базы знаний, факты которых содержат одинаковые имена предикатов, рекомендуется использовать позднее, — например, при рассмотрении вопросов, связанных с организацией поиска на запрос. Ситуацию, когда этот поиск завершился удачно, можно прокомментировать как работу логической связки ИЛИ, напомнив соответствующую таблицу истинности.

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

Тема «Составные запросы. Правила.

Базы знаний Пролога»

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

летает(самолет).

летает(лебедь).

летает(воробей).

имеет_перья(лебедь).

имеет_перья(воробей).

Используя переменную, можно задать такой вопрос: «Кто (что) летает и имеет перья?» На Прологе это будет составной запрос:

?летает(X),имеет_перья(X).

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

птица(X):летает(X),имеет_перья(X).

Добавление этого правила к базе данных позволит задавать не составные, а простые вопросы, типа «Птица ли самолет?» или «Кто является птицей?».

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

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

Тема «Термы Пролога (данные): константы, переменные, составные термы (структуры). Работа Пролога: сопоставление, поиск в базе знаний, механизм возврата. Управление работой Пролога.

 Встроенные предикаты»

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

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

Рис. 15.13. Схема данных Пролога

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

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

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

Тема «Решение логических задач на Прологе»

Эта тема имеет практический характер. В ней рассматриваются два известных метода решения логических задач: на установление соответствия между несколькими множествами и на упорядочивание между объектами. На практических примерах покажите, как эти методы реализуются на Прологе. Методы, их реализации и список некоторых задач, который может быть расширен, приводятся в литературе [3, т. 2, с. 241 — 245].

Тема «Операторы сравнения. Арифметические операторы.

Предикаты ввода-вывода. Организация диалоговых программ. Решение задач на поиск в базах знаний с использованием

операторов сравнения и арифметических операторов»

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

Тема «Рекурсия на Прологе (нисходящая стратегия). Ручная трассировка рекурсивных программ. Решение задач на символьную арифметику. Рекурсия: восходящая стратегия»

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

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

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

Из этого объяснения следует, что для того чтобы решить зада-ЧУ рекурсивно, необходимо:

а) определить связь между исходной и вспомогательной задачей;

б) определить граничное условие.

Пример. Найти сумму первых N натуральных чисел рекурсивным методом.

Заметим, что результат есть функция, зависящая от количества натуральных чисел S(N), которая выражается так:

Первые (N — 1) слагаемых есть результат такой же функции от (N 1) членов. Значит, это — вспомогательная задача, которая удовлетворяет условиям рекурсивного метода. Граничное условие запишется так: S(1) = 1. Таким образом, математическая формулировка задачи имеет вид:

Теперь решение задачи нетрудно записать на Прологе:

сумма(1,1):-!. /* Граничное условие, S(N)=1 */

сумма(N,S):-M is N-l, /* M=N-1 */

сумма(M,S), /* Вспомогательная задача */

S is C+N. /* Связь между задачами */

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

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

Тема «Структуры данных: списки. Основные предикаты

работы со списками. Решение задач с помощью списков.

Задачи, решаемые с помощью перебора»

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

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

Задание. Сдвинуть циклически элементы списка вправо.

Эта задача является обратной к более простой (на Прологе) задаче о циклическом сдвиге элементов списка влево и занимает одну строчку:

сдвиг_вправо(L,R) :сдвиг_влево(R,L).

В рамках темы рекомендуется решить такие классические задачи, как «Ханойские башни», «Задача о восьми ферзях», «Задача о перестановках», которые есть в ряде руководств.

Тема «Структуры данных: бинарные деревья. Основные

предикаты. Решение задач с помощью бинарных деревьев»

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

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

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

Выбор задач определяется главным достоинством бинарных Деревьев — эффективностью поиска, но результаты решения на прологе нагляднее в виде списков.

Тема «Применение Пролога: понимание естественного

языка (КС-грамматики)»

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

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