Логическое программирование

Сентябрь 7, 2022

Главная
Алгебра
Логическое программирование

Содержание

2. Обо мне Майкрософт Россия, академический евангелист Кандидат физ.-мат. наук Распределенные интеллектуальные системы с явным представлением знаний
3. Лекция 1 Что такое логическое программирование?
4. Мечта человечества
5. Возможно ли это? Тест Тьюринга – подробнее в курсе ИИ Проблемы: Неоднозначность человеческого языка При коммуникации
6. Потенциальный способ реализации  Формальный язык
7. Какие языки программирования вы знаете? Assembler (x86, …) C, C++, C#, Java Pascal … Brainfuck? FORTH?
8. Языки программирования
9. Программирование вчера и сегодня
10. Обратимся к истории Первый язык программирования высокого уровня – ФОРТРАН – был создан Дж.Бэкусом, чтобы математики
11. Программирования для математиков Позже Дж.Бэкус пошел дальше и предложил язык FP, в котором формулы более соответствовали
12. Что делать, чтобы приблизиться к человеческому языку? Надо пытаться формализовать человеческий язык! Основной инструмент формализации: Формальные
13. Языки логического программирования • программирование переключателей • машинные коды • язык ассемблера • FORTRAN 1950 1960
14. Как это выглядит на практике? Вычисление факториала: function fact(x:integer):integer; var i, r : integer; begin r:=1;
15. Декларативное программирование При декларативном программировании мы (на некотором формальном языке) описываем результат (его свойства), а не
16. Императивное программирование Императивное – мы говорим компьютеру, как решать задачу (что делать) Основной акцент – манипулирование
17. Декларативный стиль Это не «чистая» императивная программа. В «чистых» императивных языках (ФОРТРАН) нет рекурсии Нет операторов
18. Логическое программирование Парадигма декларативного программирования, в которой программа представляет собой описание требуемого решения в терминах определенной
19. С практической стороны: Найдем все комбинации чисел от 1 до 10, что a2+b2=c2 for a:=1 to
20. Практические преимущества Функциональные языки Компактный синтаксис для списков, n-ок (tuples), вариантных типов Логические языки Компактный синтаксис
21. Ещё пример studied(petya,mathematics). studied(vasya,german). studied(petya,compscience). studied(vasya,literature). studied(petya,english). studied_technical(X) :- studied(X,mathematics). studied_technical(X) :- studied(X,compscience). studied_languages(X) :- studied(X,english).
22. Что особенного? Определения на логическом языке похожи на предложения математической логики Логическое программирование имеет очень четкую
23. Парадигмы программирования
24. Парадигмы программирования
25. Семантика языков
26. Мультипарадигмальные языки C# - императивный (ОО) + элементы функциональности F# - функциональный с элементами императивности Mercury
27. Почему важно изучать логическое программирование?
28. Главный вопрос Придется ли нам программировать на Прологе в реальной жизни? В лучшем случае – 1
29. Какие задачи хорошо решаются на логических языках? Задачи искусственного интеллекта Экспертные системы Лингвистика, обработка естественного языка
31. Скачать презентацию

Слайд 2

Обо мне
Майкрософт Россия, академический евангелист
Кандидат физ.-мат. наук
Распределенные интеллектуальные системы с явным

представлением знаний
Интеллектуальная реструктуризация социальных сетей на основе онтологий
Семантически-ориентированые системы (Semantic Wiki)
Кафедра Вычислительной математики и программирования МАИ (доцент)
Логическое программирование
Искусственный интеллект
Студенческая лаборатория MAILabs (www.mailabs.ru)
ФИВТ

http://blogs.gotdotnet.ru/personal/sos

Слайд 3

Лекция 1
Что такое логическое программирование?

Слайд 4

Мечта человечества

Слайд 5

Возможно ли это?
Тест Тьюринга – подробнее в курсе ИИ
Проблемы:
Неоднозначность человеческого языка
При

коммуникации мы полагаемся на картину мира, которая есть у нас в голове (common knowledge)

Слайд 6

Потенциальный способ реализации

Формальный язык

Слайд 7

Какие языки программирования вы знаете?
Assembler (x86, …)
C, C++, C#, Java
Pascal
…
Brainfuck?
FORTH?
LISP, FP,

ML, Haskell, OCaml, F#, …
Prolog, Mercury, Datalog, …

Слайд 8

Языки программирования

Слайд 9

Программирование вчера и сегодня

Слайд 10

Обратимся к истории
Первый язык программирования высокого уровня – ФОРТРАН – был

создан Дж.Бэкусом, чтобы математики могли программировать на уровне формул.

• программирование переключателей

• машинные коды

• язык ассемблера

• FORTRAN

1954-57 г., Дж.Бэкус

0000 0A 12 1F 4B C3 E0 EE F1
0008 C3 1D 23 17 F2 00 0C 0D
0010 …

MOV AX, [ARG1]
ADD AX, [ARG2]
MOV [RES], AX
JMP NEXT
ARG1: DB 10
ARG2: DB 20
RES: DB 0
NEXT: …

S = 0
DO 10 I=1,10
S = S + I*I
10 CONTINUE

Слайд 11

Программирования для математиков
Позже Дж.Бэкус пошел дальше и предложил язык FP, в

котором формулы более соответствовали математическому понятию функции

• программирование переключателей

• машинные коды

• язык ассемблера

• FORTRAN

1977 г., Дж.Бэкус

def fac = eq 0 → 1;
*○[id,fac○(-○ [id,1])]

(defun factorial (n)
(if (<= n 1) 1
(* n (factorial (- n 1)))))

1950

1960

1970

1980

1990

2000

2010

♦ FP

♦ LISP

1958 г., Дж.Маккарти

Слайд 12

Что делать, чтобы приблизиться к человеческому языку?
Надо пытаться формализовать человеческий язык!
Основной

инструмент формализации:
Формальные аксиоматические системы
Логика!

Слайд 13

Языки логического программирования
• программирование переключателей
• машинные коды
• язык ассемблера
• FORTRAN
1950
1960
1970
1980
1990
2000
2010
♦ FP
♦

LISP

• С, Pascal

○ С++

○ Java

○ C#

♦ Haskell

♥ Prolog

♥ Mercury

♦ F#

♦ OCaml

♦ ML

♦ Miranda

○ Python

♥ Datalog

♥ Oz

Слайд 14

Как это выглядит на практике?
Вычисление факториала:
function fact(x:integer):integer;
var i, r : integer;
begin

r:=1;
for i:=1 to x do r:=r*i;
fact:=r
end;

Императивное программирование
(Pascal)

Слайд 15

Декларативное программирование
При декларативном программировании мы (на некотором формальном языке) описываем результат

(его свойства), а не способ его достижения
Описание факториала
HTML – описание расположения объектов
SQL
LINQ
Функциональные, логические языки

Слайд 16

Императивное программирование
Императивное – мы говорим компьютеру, как решать задачу (что делать)
Основной

акцент – манипулирование ячейками памяти
Оператор присваивания
Явные операторы передачи управления
Циклы, условный оператор

Слайд 17

Декларативный стиль
Это не «чистая» императивная программа.
В «чистых» императивных языках (ФОРТРАН) нет

рекурсии
Нет операторов присваивания
«:= » -это возврат результата из функции, а не присваивание

function fact(x:integer):integer;
begin
if x=1 then fact:=1
else fact:=x*fact(x-1)
end;

Слайд 18

Логическое программирование
Парадигма декларативного программирования, в которой
программа представляет собой описание требуемого решения

в терминах определенной логики
решение задачи строится в процессе логического вывода по заданному описанию
Различные разновидности логического программирования: индуктивное, в ограничениях, ...
Подход к программированию
Языки программирования Prolog, Datalog, Mercury, Oz, …

Слайд 19

С практической стороны:
Найдем все комбинации чисел от 1 до 10,

что a2+b2=c2

for a:=1 to 10 do
for b:=1 to 10 do
for c:=1 to 10 do
if a*a+b*b=c*c then
write(a,b,c);;

[ for a in 1..10
for b in 1..10
for c in 1..10
when a*a+b*b=c*c ->
(a,b,c)
];;

solve(A,B,C) :-
for(A,1,10),
for(B,1,10),
for(C,1,10),
A*A+B*B =:= C*C.

zip3 [1..10] [1..10] [1..10] |>
filter (
fun (a,b,c)->a*a+b*b=c*c );;

Слайд 20

Практические преимущества
Функциональные языки
Компактный синтаксис для списков, n-ок (tuples), вариантных типов
Логические языки
Компактный

синтаксис для списков, n-ок (tuples), вариантных типов
Возможность перебора и поиска различных решений, заложенная в язык

Слайд 21

Ещё пример
studied(petya,mathematics). studied(vasya,german).
studied(petya,compscience). studied(vasya,literature).
studied(petya,english).
studied_technical(X) :- studied(X,mathematics).
studied_technical(X) :- studied(X,compscience). studied_languages(X) :- studied(X,english).
studied_languages(X) :- studied(X,german).
speciality(X,tech_translator)

:- studied_languages(X),studied_technical(X).
speciality(X,programmer) :-
studied(X,mathematics),studied(X, compscience).
speciality(X,lit_translator) :- studied_languages(X),studied(X,literature).
?-specialty(vasya,X).
?- specialty(X,lit_translator).

Слайд 22

Что особенного?
Определения на логическом языке похожи на предложения математической логики
Логическое программирование

имеет очень четкую математическую основу
Возможны рассуждения о программах: доказательство корректности, …
Отсутствует оператор присваивания
Есть знак = , но он имеет другую семантику – унификация, связывание имен
Переменные связываются неявно, в процессе логического вывода
Будучи один раз связанным, имя может менять свое значение только в процессе пересмотра решения (возврата)
А это значит – нет побочных эффектов!

Слайд 23

Парадигмы программирования

Слайд 24

Парадигмы программирования

Слайд 25

Семантика языков

Слайд 26

Мультипарадигмальные языки
C# - императивный (ОО) + элементы функциональности
F# - функциональный с

элементами императивности
Mercury – функционально-логический
Oz
Python
…

Слайд 27

Почему важно изучать логическое программирование?

Слайд 28

Главный вопрос
Придется ли нам программировать на Прологе в реальной жизни?
В лучшем

случае – 1 человеку из группы

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

Слайд 29

Какие задачи хорошо решаются на логических языках?
Задачи искусственного интеллекта
Экспертные системы
Лингвистика, обработка

естественного языка
Задачи с неопределенностью
Задачи, связанные с поиском решений
Мета-программирование, построение специализированных языков

Логическое программирование

Содержание

Обо мнеМайкрософт Россия, академический евангелистКандидат физ.-мат. наукРаспределенные интеллектуальные системы с явным

Лекция 1Что такое логическое программирование?

Мечта человечества

Возможно ли это?Тест Тьюринга – подробнее в курсе ИИПроблемы:Неоднозначность человеческого языкаПри

Потенциальный способ реализацииФормальный язык

Какие языки программирования вы знаете?Assembler (x86, …)C, C++, C#, JavaPascal…Brainfuck?FORTH?LISP, FP,

Языки программирования

Программирование вчера и сегодня

Обратимся к историиПервый язык программирования высокого уровня – ФОРТРАН – был

Программирования для математиковПозже Дж.Бэкус пошел дальше и предложил язык FP, в

Что делать, чтобы приблизиться к человеческому языку?Надо пытаться формализовать человеческий язык!Основной

Языки логического программирования• программирование переключателей• машинные коды• язык ассемблера• FORTRAN1950196019701980199020002010♦ FP♦

Как это выглядит на практике?Вычисление факториала:function fact(x:integer):integer;var i, r : integer;begin

Декларативное программированиеПри декларативном программировании мы (на некотором формальном языке) описываем результат

Императивное программированиеИмперативное – мы говорим компьютеру, как решать задачу (что делать)Основной

Декларативный стильЭто не «чистая» императивная программа.В «чистых» императивных языках (ФОРТРАН) нет

Логическое программированиеПарадигма декларативного программирования, в которойпрограмма представляет собой описание требуемого решения

С практической стороны:Найдем все комбинации чисел от 1 до 10,

Практические преимуществаФункциональные языкиКомпактный синтаксис для списков, n-ок (tuples), вариантных типовЛогические языкиКомпактный

Что особенного?Определения на логическом языке похожи на предложения математической логикиЛогическое программирование

Парадигмы программирования

Парадигмы программирования

Семантика языков

Мультипарадигмальные языкиC# - императивный (ОО) + элементы функциональностиF# - функциональный с

Почему важно изучать логическое программирование?

Главный вопросПридется ли нам программировать на Прологе в реальной жизни?В лучшем

Какие задачи хорошо решаются на логических языках?Задачи искусственного интеллектаЭкспертные системыЛингвистика, обработка

Похожие презентации

Обо мне
Майкрософт Россия, академический евангелист
Кандидат физ.-мат. наук
Распределенные интеллектуальные системы с явным

Лекция 1
Что такое логическое программирование?

Возможно ли это?
Тест Тьюринга – подробнее в курсе ИИ
Проблемы:
Неоднозначность человеческого языка
При

Потенциальный способ реализации

Формальный язык

Какие языки программирования вы знаете?
Assembler (x86, …)
C, C++, C#, Java
Pascal
…
Brainfuck?
FORTH?
LISP, FP,

Обратимся к истории
Первый язык программирования высокого уровня – ФОРТРАН – был

Программирования для математиков
Позже Дж.Бэкус пошел дальше и предложил язык FP, в

Что делать, чтобы приблизиться к человеческому языку?
Надо пытаться формализовать человеческий язык!
Основной

Языки логического программирования
• программирование переключателей
• машинные коды
• язык ассемблера
• FORTRAN
1950
1960
1970
1980
1990
2000
2010
♦ FP
♦

Как это выглядит на практике?
Вычисление факториала:
function fact(x:integer):integer;
var i, r : integer;
begin

Декларативное программирование
При декларативном программировании мы (на некотором формальном языке) описываем результат

Императивное программирование
Императивное – мы говорим компьютеру, как решать задачу (что делать)
Основной

Декларативный стиль
Это не «чистая» императивная программа.
В «чистых» императивных языках (ФОРТРАН) нет

Логическое программирование
Парадигма декларативного программирования, в которой
программа представляет собой описание требуемого решения

С практической стороны:
Найдем все комбинации чисел от 1 до 10,

Практические преимущества
Функциональные языки
Компактный синтаксис для списков, n-ок (tuples), вариантных типов
Логические языки
Компактный

Что особенного?
Определения на логическом языке похожи на предложения математической логики
Логическое программирование

Мультипарадигмальные языки
C# - императивный (ОО) + элементы функциональности
F# - функциональный с

Главный вопрос
Придется ли нам программировать на Прологе в реальной жизни?
В лучшем

Какие задачи хорошо решаются на логических языках?
Задачи искусственного интеллекта
Экспертные системы
Лингвистика, обработка