- •Эзотерические языки
- •Программа «Hello, world»:
- •Программа «Hello, world»:
- •Введение в функциональное программирование
- •Развитие функциональных языков
- •Функционально-аппликативное программирование.
- •Функции высших порядков
- •Сортировка:
- •Логическое программирование
- •Основы логических исчислений
- •Рекурсивные правила
- •Логические программы
- •Бинарные (двоичные) деревья
- •Примеры программ:
- •Работа с символьными выражениями
- •Программа, распознающая многочлены от переменной х
- •Дифференцирование
- •Истинность булевских формул
- •Семантика логических программ
- •Сравнение с другими языками программирования
- •Недетерминированное программирование
- •Задача о ферзях
- •Визуальные языки программирования. Графическое программирование.
- •Псевдографика
- •Диаграмма «сущность-связь»
- •Языки потоков данных
- •Жизненный цикл по
- •Заказное по
- •Оценка реализуемости
- •Анализ и постановка задачи
Бинарные (двоичные) деревья
Рекурсивный тип данных, сложнее чем одномерные списки.
Задать с помощью функтора:
дерево(Элемент, Левое, Правое).
а
/ \
b d пусто
дерево(а, дерево(b, пусто, пусто), дерево(d, пусто, пусто)).
Логические программы эквивалентны логическим программам списков.
дерево(пусто).
дерево(дерево(Элемент, Лево, Право), дерево(Лево), дерево(Право)).
Примеры программ:
- Проверка на наличие элемента
часть_дерева(Х, дерево(Х, Лево, Право)).
часть_дерева(Х, дерево(Y, Лево, Право)):-часть_дерева(Х, Лево).
часть_дерева(Х, дерево(Y, Лево, Право)):-часть_дерева(Х, Право).
2 ветви дерева различны, но во многих приложениях это различие несущественно.
Изоморфизм деревьев: 2 двоичных дерева называются изоморфными, если D2 может быть получено из D1 изменением порядка ветвей поддеревьев.
- Замена
замена(Х,Y,пусто, пусто).
замена(X,Y,дерево(X,Лево,Право), дерево(Y,Лев1,Прав1):-замена(Х,Y,Лево,Лев1), замена(Х,Y,Право,Прав1).
замена(Х,Y,дерево(Z,Лево,Право), замена(Z,Лев1,Прав1):-Х≠Z, замена(X,Y,Лев,Лев1), замена(X,Y,Прав,Прав1).
- Обход дерева
Несколько вариантов:
*Обход дерева сверху-вниз: Сначала идет значение, находящееся на вершине, затем вершины Левого поддерева, а затем вершины правого поддерева.
*Обход дерева слева-направо: Сначала вершины Левого поддерева, потом вершина дерева, далее вершины правого поддерева.
снизу_вверх(дерево(Х,Л,П),Хs):-снизу_вверх(Л,Левые), снизу_вверх(П,Правые), append(Правые,[Х],П1), append(Левые,П1,Хs).
снизу_вверх(пусто,[ ]).
Работа с символьными выражениями
Полином от Х определяется индуктивно.
Сумма, разность и произведение полиномов от Х, результат возведения полинома в целую степень и деление полинома на const≠0 дают полином.
х-32 – полином.
Программа, распознающая многочлены от переменной х
ПОЛИНОМ(Х,Х).
ПОЛИНОМ(выражение,Х):-constant(выражение).
ПОЛИНОМ(выраж1+выраж2,Х):-ПОЛИНОМ(выраж1,Х), ПОЛИНОМ(выраж2,Х).
ПОЛИНОМ(выраж1-выраж2,Х):-ПОЛИНОМ(выраж1,Х), ПОЛИНОМ(выраж2,Х).
и т.д.
Дифференцирование
diff(sin(X),X,cos(X)). – пример
diff(X,X,1).
diff(X↑(N+1),X,(N+1)*X↑N).
diff(sin(X),X,cos(X)).
diff(cos(X),X,-sin(X)).
diff(e↑X,X,e↑X).
diff(log(X),X,e(X)).
diff(F+G,X,DF+DG):-diff(F,X,DF), diff(G,X,DG).
diff(F-G,X,DF-DG):-diff(F,X,DF), diff(G,X,DG).
diff(F*G,X,F*DG+DF*G):=diff(F,X,DF), diff(G,X,DG).
diff(1/F,X,-DF/(F*F)):-diff(F,X,DF).
diff(F/G,X,(G*DF-F*DG)/(G*G)):-diff(F,X,DF), diff(G,X,DG).
diff(U↑(N+1),X,(N+1)*U↑N*DU):-diff(U,X,DU).
diff(sin(U),X,cos(U)*DU):-diff(U,X,DU).
Булевские формулы – выражения, определяемые следующим образом: const – истина или ложь. Если Х,Y – булевские формулы, то XorY, X&Y,~X – булевские формулы.
Булевской формуле можно приписать истинность.
Х&Y=U (X=U, Y=U).
XorY=U (X or Y=U).
Истинность булевских формул
Булевская формула с переменными выполнима, если существует такие подстановки переменных, при которых формула истинна. Булевская формула опровержима, если существует ложный пример.
выполнима(Formula).
выполнима(истина).
выполнима(Х&Y):-выполнима(Х), выполнима(Y).
выполнима(ХorY):-выполнима(Х).
выполнима(XorY):-выполнима(Y).
выполнима(~Х):-опровержима(Х).
опровержима(ложь).
опровержима(ХorY):-опровержима(Х), опровержима(Y).
опровержима(Х&Y):-опровержима(Х).
опровержима(X&Y):-опровержима(Y).
опровержима(~Y):-выполнима(Y).