- •Эзотерические языки
- •Программа «Hello, world»:
- •Программа «Hello, world»:
- •Введение в функциональное программирование
- •Развитие функциональных языков
- •Функционально-аппликативное программирование.
- •Функции высших порядков
- •Сортировка:
- •Логическое программирование
- •Основы логических исчислений
- •Рекурсивные правила
- •Логические программы
- •Бинарные (двоичные) деревья
- •Примеры программ:
- •Работа с символьными выражениями
- •Программа, распознающая многочлены от переменной х
- •Дифференцирование
- •Истинность булевских формул
- •Семантика логических программ
- •Сравнение с другими языками программирования
- •Недетерминированное программирование
- •Задача о ферзях
- •Визуальные языки программирования. Графическое программирование.
- •Псевдографика
- •Диаграмма «сущность-связь»
- •Языки потоков данных
- •Жизненный цикл по
- •Заказное по
- •Оценка реализуемости
- •Анализ и постановка задачи
Недетерминированное программирование
В силу недетерминированного характера программ, отсутствует единственным образом последовательность действий, если программы немысленно писать на другом языке программирования, то здесь это возможно.
При написании используется методика – «образовать и проверить». На современных ЭВМ можно построить аппроксимацию. В частности Пролог – интерпретатор, аппроксимирующий недетерминированное поведение с помощью механизма поиска с возвратом. При этом факт, что недетерминизм не отсутствует, а моделируется, для недетерминированного мышления не существенен. Следовательно, мы можем писать и недетерминированные программы.
Легко создавать логические программы, метод которых «образовать и проверить».
2 посылки …. , …..
/ \
генератор проверяет,
предполагаемых является ли решение
решений приемлемым
find(x)^-generate(x), prover(x).
В качестве генератора – предикат наподобие chlen.
?chlen(x, [a,b,c]).
x=a.
x=b.
x=c.
chlen можно использовать в программах, применяющих этот метод, для недетерминированного выбора элемента из списка.
sort(Xs,Ys):-perest(Xs,Ys), upor(Ys). (perest - генератор, upor - проверочный).
Задача о ферзях
Поле N*N, N ферзей, надо, чтобы ферзи не били друг друга.
Порядковый номер элемента списка Qs определяет N вертикали. Элементы – натуральные числа, и сам элеиент – N горизонтали, на которой находится ферзь.
queen(N,Qs).
queens(N,Qs):-perest(Ns,Qs), safe(Qs), range(1,N,Ns).
safe([Q|Qs]):-safe(Qs), not_attack(Q,Qs).
safe([ ]).
attack(X,Xs):-attack(X,1,Xs).
attack(X,N,[Y|Ys]):-X:=Y+N, X:=Y-N.
attack(X,N,[Y|Ys]):-N1:=N+1, attack(X,N1,Ys).
Отрицание:
not X:-X,!,fail.
not X.
range – генерирунет элементы в диапазоне от 1 до N, записывает в список Ns.
range(M,N,[M|Ns]):-M<N, M1:=M+1, range(M1,N,Ns).
range(N,N,[N]).
- Сначала обрабатывается Ns (от 1 до N).
- Генерируется перестановка Ns, проверяется safe (safe=U (список является решением поставленной задачи)).
Так как на одной и той же вертикали и горизонтали не могут находиться 2 ферзя, safe должен обеспечивать проверку, не угрожают ли друг другу королевы, находящиеся на одной горизонтали.
Положение правильно, если Qs не бьют друг друга и ферзь, находящийся во главе, не атакует ни одну королеву в хвосте.
- attack – пример изящного программирования (взаимосвязь диагоналей).
2 ферзя, находящиеся на одной диагонали на расстоянии М вертикали друг от друга, если N горизонталь 1 ферзя на М больше (меньше), чем N горизонтали другого.
Весьма неэффективно ( - не способна распознать симметричное решение;
- генерируются все возможные перестановки, которые не могут быть решением.)
2 вариант задачи:
range ……
range ……
queens(N,Qs):-range(1,N,Ns), queens(Ns,[ ],Qs).
queens(UnlQs,SafeQs,Qs):-vyrez(Q,UnlQs,UnlQs1), not attack(Q,SafeQs), queens(UnlQs1,[Q|SafeQs],Qs).
queens([ ],Qs,Qs).