Методика преподавания информатики (стр. 115 )

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

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

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

Эта тема имеет практический характер. В ней рассматриваются два известных метода решения логических задач: на установление соответствия между несколькими множествами и на упорядочивание между объектами. На практических примерах покажите, как эти методы реализуются на Прологе. Методы, их реализации и список некоторых задач, который может быть расширен, приводятся в литературе [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).

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

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

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

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

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

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

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

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

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

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

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

15.8. Требования к знаниям и умениям

учащихся

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

Учащиеся должны знать:

• в чем состоит принципиальное отличие операторного языка от логического.

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

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