Формирование навыков формализации и моделирования в процессе логического программирования

Размещено на http://www.allbest.ru/

Формирование навыков формализации и моделирования в процессе логического программирования

Ванькова Валентина Сергеевна



Аннотация

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

Ключевые слова: логическое программирование, Моделирование, формализация



Начало XXI века характеризуется не только бурным развитием и повсеместным проникновением информационно-коммуникационных технологий во все сферы деятельности человека, но и серьезной переоценкой ценностей и потребностей современного рынка труда. Образование, знания, инновации становятся полноправными элементами макросистемы, импульсы развитию которых задает феномен востребованности. Знания вместе с культурой являются тем единственным видом коллективной собственности, от использования которой ее объем и ценность только возрастают. В этой связи можно с уверенностью говорить о трансформации востребованной профессии программиста в еще более востребованную профессию прикладного программиста.

Одной из основных задач, обозначенных в одобренном Правительством Российской Федерации плане мероприятий по развитию ИТ-отрасли до 2018 года, является развитие системы подготовки профессиональных кадров. Данная система призвана обеспечить высокие показатели приема в высшие учебные заведения, а также снабдить ИТ-отрасль кадрами в необходимом количестве и с достаточным уровнем образования. Одним из структурных элементов данной системы выступает подготовка бакалавров по направлению 02.03.03 Математическое обеспечение и администрирование информационных систем, государственный образовательный стандарт по которому утвержден Приказом Министерства образования и науки РФ от 12 марта 2015 года № 222. Стандарт содержит, в том числе, и требование о необходимости формирования у выпускников бакалавриата «…способности использовать знания основных концептуальных положений функционального, логического, объектно-ориентированного и визуального направлений программирования, методов, способов и средств разработки программ в рамках этих направлений». Формирование знаний в области логического программирования в соответствии с учебным планом подготовки бакалавров происходит в процессе изучения дисциплин «Математическая логика и теория алгоритмов» и «Системы искусственного интеллекта».

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

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

Задача «Кто не запер дверь комнаты?»

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

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

A	1. Я не оставлял дверь открытой.
	2. Это сделал B.
B	1. Я не стоял в тот вечер на вахте.
	2. Это была смена А.
V	1. Это B стоял на вахте в тот вечер.
	2. Я надеялся, что Сократ совершит побег.
G	1. Я не оставлял дверь открытой.
	2. Меня не удивило, что Сократ не пытался бежать.

Определите, кто из стражников виновен, принимая во внимание, что, в общей сложности, три из приведенных высказываний истинны, а пять - ложны.[1, C.8]

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

Использовались предикаты:

человек(кто_виноват)

заявление(кто_говорит, кто_виноват, истина, номер)

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

Каждое из восьми согласований данного предиката связывает переменные вида РезA1, …, РезG2 со значением 1 или 0, что необходимо для формализации условия задачи, выраженного словами «…три из приведенных высказываний истинны». Именно на достижение данного условия направлены подцели

Сум=РезA1+РезA2+РезB1+РезB2+РезV1+РезV2+РезG1+РезG2, Сум=3,

и только их успешное согласование позволит достичь цели задачи и получить ответ. В данном случае виновником проступка оказался G.

Приведем полностью текст программы:

domains

кто_говорит, кто_виноват = char

истина, номер = integer

predicates

заявление(кто_говорит, кто_виноват, истина, номер)

человек(кто_виноват)

поиск

clauses

человек(`A'). человек(`B'). человек(`V'). человек(`G').

заявление(`A','A',0,1). заявление(`A','A',0,2). заявление(`A','B',1,1). заявление(`A','B',1,2).

заявление(`A','V',1,1). заявление(`A','V',0,2). заявление(`A','G',1,1). заявление(`A','G',0,2).

заявление(`B','A',1,1). заявление(`B','A',1,2). заявление(`B','B',0,1). заявление(`B','B',0,2).

заявление(`B','V',1,1). заявление(`B','V',0,2). заявление(`B','G',1,1). заявление(`B','G',0,2).

заявление(`V','A',0,1). заявление(`V','A',1,2). заявление(`V','B',1,1). заявление(`V','B',1,2).

заявление(`V','V',0,1). заявление(`V','V',1,2). заявление(`V','G',0,1). заявление(`V','G',1,2).

заявление(`G','A',1,1). заявление(`G','A',0,2). заявление(`G','B',1,1). заявление(`G','B',0,2).

заявление(`G','V',1,1). заявление(`G','V',0,2). заявление(`G','G',0,1). заявление(`G','G',0,2).

поиск:-

человек(Виноват),

заявление(`A',Виноват,РезA1,1), заявление(`A',Виноват,РезA2,2),

заявление(`B',Виноват,РезB1,1), заявление(`B',Виноват,РезB2,2),

заявление(`V',Виноват,РезV1,1), заявление(`V',Виноват,RezV2,2),

заявление(`G',Виноват,РезG1,1), заявление(`G',Виноват,РезG2,2),

Сум= РезA1+РезA2+РезB1+РезB2+РезV1+РезV2+РезG1+РезG2,

Сум=3, write(Виноват), nl, fail.

поиск.

goal поиск.

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

Задача «Кто должен отремонтировать статую?»

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

A	1. У меня нет всех необходимых инструментов.
	2. G - самый высококвалифицированный из нас.
	3. B опытен в такого рода работах.
B	1. Самый квалифицированный - A.
	2. G - никогда не работал со слоновой костью.
	3. Первое заявление A ложно.
V	1. Я опытен в таких работах.
	2. Самый квалифицированный - B.
	3. У A нет всех необходимых инструментов.
G	1. Самый квалифицированный - V.
	2. У A нет всех необходимых инструментов.
	3. Я никогда не работал со слоновой костью.

Которого из мастеров выбрал Сократ? [1, C.12]

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

автор высказывания (1),

кто из мастеров выбран Сократом (2),

истинность высказывания в зависимости от сочетания значений свойств (1,2,4),

порядковый номер высказывания автора (1).

Формализация данных заключалась в использовании предикатов:

человек(кто_выбран) (5)

заявление(кто_говорит, кто_выбран, истина, номер) (6)

на доменах пользователя кто_говорит, кто_выбран, истина, номер. В разделе предложений программы два первых предиката представлены совокупностью фактов. При этом особенностью формализации данных высказываний является невозможность однозначно определить истинность высказывания даже для конкретных значений автора высказывания и выбранного мастера. Например, если выбраны мастера A, B или V то два из трех высказываний G могут быть как истинными, так и ложными.

Особенностью данной задачи является условие «…все четверо сделали поровну правдивых и поровну лживых заявлений». Поровну! Но не известно соотношение количества правдивых и ложных высказываний. Для формализации данного условия был введен предикат

индекс_заявления(кто_говорит, кто_выбран, истина, истина, истина),

который вызывается в теле предиката поиска решения при условии, что переменная X связана конкретным значением выбранного мастера, и определяет для каждого мастера истинность каждого из трех высказываний через связывание соответствующих переменных R1,R2,R3 и возвращением в тело предиката поиска решения поочередно значений переменных R1,…,R12. Именно следующее согласование полученных связанных значений переменных: программирование математическая логика

R1+R2+R3=R4+R5+R6, R4+R5+R6=R7+R8+R9, R10+R11+R12=R7+R8+R9,

дает гарантию соблюдения условия, приведенного выше.

Если на данном этапе закончить моделирование предметной области задачи, написать программу и провести тестирование, то мы получим 14 решений. Такое тоже бывает. Но аналитически было получено ровно одно решение. Где же мы были невнимательны? Оказывается, ряд высказываний должен быть согласован между собой. Например, если будет выбран мастер A, то первое и третье высказывание B должны быть равными. Если же будет выбран мастер V, то второе высказывание A, первое высказывание B и второе высказывание V должны быть ложными; третье высказывание A, первые высказывания V и G должны быть истинными; первое высказывание A должно совпадать с третьим высказыванием V; второе высказывание B должно совпадать с третьим высказыванием G; третье высказывание B должно быть противоположно первому высказыванию A. Подобным образом должно пройти моделирование и в оставшихся случаях.

Формализацией данной модели служит предикат

тест(кто_выбран,истина,…,истина) % 12 аргументов на домене истина,

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

Приведем полностью текст программы:

domains

кто_говорит, кто_выбран =char

истина, номер = integer

predicates

человек(кто_выбран)

заявление(кто_говорит, кто_выбран,истина,номер)

индекс_заявления(кто_говорит, кто_выбран, истина, истина, истина)

тест(кто_выбран, истина, истина, истина, истина, истина , истина, истина, истина, истина, истина, истина, истина)

поиск

clauses

человек(`A').человек(`B'). человек(`V').человек(`G').

заявление(`A','A',0,1). заявление(`A','A',0,2). заявление(`A','A',0,3).

заявление(`B','A',1,1). заявление(`B','A',1,2). заявление(`B','A',0,2). заявление(`B','A',1,3).

заявление(`V','A',0,1). заявление(`V','A',1,1). заявление(`V','A',0,2). заявление(`V','A',0,3).

заявление(`G','A',0,1). заявление(`G','A',1,1). заявление(`G','A',0,2). заявление(`G','A',1,3). заявление(`G','A',0,3).

заявление(`A','B',1,1). заявление(`A','B',0,1). заявление(`A','B',0,2). заявление(`A','B',1,3). заявление(`A','B',0,3).

заявление(`B','B',0,1). заявление(`B','B',0,2). заявление(`B','B',1,2). заявление(`B','B',1,3). заявление(`B','B',0,3).

заявление(`V','B',1,1). заявление(`V','B',0,1). заявление(`V','B',1,2). заявление(`V','B',1,3). заявление(`V','B',0,3).

заявление(`G','B',1,1). заявление(`G','B',1,2). заявление(`G','B',0,2). заявление(`G','B',1,3). заявление(`G','B',0,3).

заявление(`A','V',1,1). заявление(`A','V',0,1). заявление(`A','V',0,2). заявление(`A','V',1,3).

заявление(`B','V',0,1). заявление(`B','V',0,2). заявление(`B','V',1,2). заявление(`B','V',1,3). заявление(`B','V',0,3).

заявление(`V','V',1,1). заявление(`V','V',0,2). заявление(`V','V',1,3). заявление(`V','V',0,3).

заявление(`G','V',1,1). заявление(`G','V',1,2). заявление(`G','V',0,2). заявление(`G','V',1,3). заявление(`G','V',0,3).

заявление(`A','G',1,1). заявление(`A','G',0,1). заявление(`A','G',1,2). заявление(`A','G',0,3). заявление(`A','G',1,3).

заявление(`B','G',0,1). заявление(`B','G',0,2). заявление(`B','G',0,3). заявление(`B','G',1,3).

заявление(`V','G',1,1). заявление(`V','G',0,1). заявление(`V','G',0,2). заявление(`V','G',0,3). заявление(`V','G',1,3).

заявление(`G','G',0,1). заявление(`G','G',1,2). заявление(`G','G',0,2). заявление(`G','G',0,3).

индекс_заявления(`A',X,R1,R2,R3):-

заявление(`A',X,R1,1), заявление(`A',X,R2,2), заявление(`A',X,R3,3).

индекс_заявления (`B',X,R1,R2,R3):-

заявление(`B',X,R1,1), заявление(`B',X,R2,2), заявление(`B',X,R3,3).

индекс_заявления(`V',X,R1,R2,R3):-

заявление(`V',X,R1,1), заявление(`V',X,R2,2), заявление (`V',X,R3,3).

индекс_заявления(`G',X,R1,R2,R3):-

заявление(`G',X,R1,1), заявление(`G',X,R2,2), заявление(`G',X,R3,3).

тест(`A',_,_,_,R4,_,R6,_,_,_,_,_,_):-R4=R6.

тест(`B',R1,_,R3,R4,_,R6,_,_,_,_,_,_):-R4=R6,R1=R3.

тест(`V',R1,R2,R3,R4,R5,R6,R7,R8,R9,R10,_,R12):- R1=R9,R2=0,R3=1,R4=0,R7=1,R8=0,R10=1,R6+R1=1,R5=R12.

тест(`G',R1,R2,_,_,_,_,_,_,_,R10,R11,R12):- R10=0,R12=0,R1=R11,R2=1.

поиск:-человек(Мастер),

индекс_заявления(`A',Мастер,R1,R2,R3), индекс_заявления(`B',Мастер,R4,R5,R6),

индекс_заявления(`V',Мастер,R7,R8,R9), индекс_заявления(`G',Мастер,R10,R11,R12),

R1+R2+R3=R4+R5+R6, R4+R5+R6=R7+R8+R9, R10+R11+R12=R7+R8+R9, тест(Мастер,R1,R2,R3,R4,R5,R6,R7,R8,R9,R10,R11,R12),

write(Мастер),nl, write(R1,' `,R2,' `,R3),nl, write(R4,' `,R5,' `,R6),nl, write(R7,' `,R8,' `,R9),nl, write(R10,' `,R11,' `,R12),nl, fail.

поиск.

goal поиск.

Сократ выбрал мастера V. Каждый из мастеров сделал по два правдивых и два ложных заявления.

Задача решена. И, по-прежнему, программа является объектом исследования, а модель может быть построена по-другому.

Задача «Предвыборная дискуссия»

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

Пьер	1. Если Жан проголосует за Дюбуа, я буду голосовать за Дюпона
	2. Но если он проголосует за Дюрана, я буду голосовать за Дюбуа.
	3. С другой стороны, если Жак проголосует за Дюпона, я буду голосовать за Дюрана
Жан	1. Если Пьер проголосует за Дюрана, я не буду голосовать за Дюпона
	2. Но если Жак проголосует за Дюбуа, то я проголосую за Дюпона
Жак	1. Если Пьер проголосует за Дюпона, я не буду голосовать за Дюрана

Подошел день выборов. Все три брата проголосовали за разных кандидатов. За кого именно? [2, С.33]

В процессе моделирования предметной области задачи выделены предикаты брат и кандидат. Каждый брат выбирает кандидата, делая при этом некие заявление, часто противоречащие одно другому.

Формализация данных заключалась в использовании предикатов:

брат(symbol)

кандидат(symbol)

голосование(symbol, symbol, symbol, symbol, symbol, symbol)

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

predicates

брат(symbol)

кандидат(symbol)

голосование(symbol, symbol, symbol, symbol, symbol, symbol)

итог(symbol, symbol, symbol, symbol, symbol, symbol)

clauses

брат(пьер). брат(жан). брат(жак).

кандидат(дюпон). кандидат(дюран). кандидат(дюбуа).

голосование(X1,Y1,X2,Y2,X3,Y3):-

брат(X1), X1=пьер, кандидат(Y1), Y1=дюпон,

брат(X2), X2= жан, кандидат(Y2),Y2=дюбуа,

брат(X3), X3=жак, кандидат(Y3),not(Y3=дюран).

голосование(X1,Y1,X2,Y2,X3,Y3):-

брат(X1), X1=пьер, кандидат(Y1), Y1=дюран,

брат(X2), X2=жан, кандидат(Y2), Y2=дюбуа,!,

брат(X3), X3=жак, кандидат(Y3).

голосование(X1,Y1,X2,Y2,X3,Y3):-

брат(X1), X1=пьер, кандидат(Y1), Y1=дюран,

брат(X2), X2=жан, кандидат(Y2),not(Y2=дюпон),

брат(X3), X3=жак, кандидат(Y3), Y3=дюпон.

голосование(X1,Y1,X2,Y2,X3,Y3):-

брат(X1), X1=пьер, кандидат(Y1), Y1=дюран,

брат(X2), X2=жан, кандидат(Y2), not(Y2=дюпон),!,

брат(X3), X3=жак, кандидат(Y3).

голосование(X1,Y1,X2,Y2,X3,Y3):-

брат(X1), X1=пьер, кандидат(Y1),

брат(X2), X2=жан, кандидат(Y2), Y2=дюпон,

брат(X3), X3=жак, кандидат(Y3), Y3=дюбуа.

голосование(X1,Y1,X2,Y2,X3,Y3):-

брат(X1), X1=пьер, кандидат(Y1),Y1=дюпон,

брат(X2), X2=жан, кандидат(Y2),

брат(X3), X3=жак, кандидат(Y3), not(Y3=дюран).

итог(X1,Y1,X2,Y2,X3,Y3) :-

X1=пьер, X2=жан, X3=жак, голосование(X1,Y1,X2,Y2,X3,Y3), Y1<>Y2, Y2<>Y3, Y1<>Y3,

write(“Пьер ->”, Y1, “ Жан ->”, Y2, “ Жак ->”, Y3), nl.

goal итог(X1,Y1,X2,Y2,X3,Y3).

В итоге мы получаем следующее решение: Пьер проголосовал за Дюрана, Жан - за Дюбуа, Жак - за Дюпона.

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

не_голосование(X,Y):-брат(X), кандидат(Y), not(голосование(X,Y)).

В этом случае можно несколько упростить схему высказываний братьев:

голосование(пьер,Y):- кандидат(Y), Y=дюпон, голосование(жан, дюбуа),!.

голосование(пьер,Y):- кандидат(Y), Y=дюбуа, голосование(жан, дюран),!.

голосование(пьер,Y):- кандидат(Y), Y=дюран, голосование(жак, дюпон),!.

голосование(жан,Y):- кандидат(Y), Y=дюпон, голосование(жак, дюбуа),!.

голосование(жак,Y):- кандидат(Y).

не_голосование(X,Y):- брат(X), кандидат(Y), not(голосование(X,Y)).

не_голосование(жан, дюпон) :- голосование(пьер, дюран),!.

не_голосование(жак, дюран) :- голосование(пьер, дюпон),!.

С учетом сказанного задачу можно описать следующим образом:

predicates

брат(symbol)

кандидат(symbol)

голосование(symbol, symbol)

итог(symbol, symbol, symbol, symbol, symbol, symbol)

clauses

брат(пьер). брат(жан). брат(жак).

кандидат(дюпон). кандидат(дюран). кандидат(дюбуа).

голосование(пьер,Y):- кандидат(Y), Y=дюпон, голосование(жан, дюбуа),!.

голосование(пьер,Y):- кандидат(Y), Y=дюбуа, голосование(жан, дюран),!.

голосование(пьер,Y):- кандидат(Y), Y=дюран, голосование(жак, дюпон),!.

голосование(жан,Y):- кандидат(Y), Y=дюпон, голосование(жак, дюбуа),!.

голосование(жак,Y):- кандидат(Y).

не_голосование(X,Y):- брат(X), кандидат(Y), not(голосование(X,Y)).

не_голосование(жан, дюпон):-голосование(пьер, дюран),!.

не_голосование(жак, дюран):-голосование(пьер, дюпон),!.

итог(X1,Y1,X2,Y2,X3,Y3):-

X1=пьер, голосование(X1,Y1), X2=жан, голосование(X2,Y2), X3=жак, голосование(X3,Y3),

Y1<>Y2, Y2<>Y3, Y1<>Y3;

X1=пьер, голосование(X1,Y1), X2=жан, не_голосование(X2,Y2), X3=жак, голосование(X3,Y3),

Y1<>Y2, Y2<>Y3, Y1<>Y3;

X1=пьер, голосование(X1,Y1), X2=жан, не_голосование(X2,Y2), X3=жак, не_голосование(X3,Y3),

Y1<>Y2, Y2<>Y3, Y1<>Y3.

goal итог(X1,Y1,X2,Y2,X3,Y3).

В итоге мы получаем два решения:

1) Пьер проголосовал за Дюрана, Жан - за Дюбуа, Жак - за Дюпона;

или

2) Пьер проголосовал за Дюрана, Жан - за Дюпона, Жак - за Дюбуа.

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



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

Виллис, Н. Коварные головоломки / Норман Д.Виллис: пер. с англ. Е.М.Веселовой - М.: Астрель: АСТ, 2006. - 95с.

Беррондо, М. Занимательные задачи: Пер. с франц./ Мари Беррондо. Перевод Сударева Ю.Н. - М: Мир, 1983. - 230 с.

Размещено на Allbest.ru

...