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

Бакалавриат 2020/2021

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»

Лучший по критерию «Новизна полученных знаний»

Статус: Курс по выбору (Прикладная математика и информатика)

Направление: 01.03.02. Прикладная математика и информатика

Кто читает: Департамент информатики

Где читается: Санкт-Петербургская школа физико-математических и компьютерных наук

Когда читается: 4-й курс, 3 модуль

Формат изучения: без онлайн-курса

Преподаватели: Булычев Дмитрий Юрьевич

Язык: русский

Кредиты: 4

Контактные часы: 66

Полная версия программы учебной дисциплины

Аннотация

Является дисциплиной по выбору. Целью курса является обеспечение базовой подготовки студентов в области декларативного программирования, знакомство с основными понятиями и техникой логического и реляционного программирования В результате освоения дисциплины студент должен:  знать основные методы логического и реляционного программирования;  уметь создавать программы на языках Prolog, Datalog и miniKanren;  владеть математическим аппаратом и инструментальными средствами для написания программа в парадигме программирования “логическое и реляционное программирование”.

Цель освоения дисциплины

Целями освоения дисциплины «Логическое и реляционное программирование» являются формирование у студентов теоретических знаний и практических навыков по основам логического и реляционного программирования, основным алгоритмам поиска решений для декларативно специфицированных задач и реализации декларативных языков.

Планируемые результаты обучения

Знает пропозициональный метод резолюций. Знает конъюктивные и дизъюктивные нормальные формы (КНФ, ДНФ), способ Цейтина. DPP, DPLL, CDCL.
Владеет понятиями термы, подстановки, применение подстановки к терму, композиция подстановок. Владеет понятиями унификация, наиболее общий унификатор. «Occurs check». Знает метод резолюций для формул первого порядка. Хорновские дизъюнкты. SLD-резолюция, Prolog и его операционная семантика в простейшем случае. Отсечение («cut»), «green cut», «red cut». Операционная семантика отсечения. Incremental deepening, NAF, predicate completion.
Проводит монадический поиск. Знает Disequality constraint. Refutational completeness. Числа, списки и пр. Реляционные интерпретаторы и пр. применения.
Использует операционную и декларативную семантику. Знает Term rewriting: основные понятия. (Semi, strong, local)-confluence, свойство Черча-Россера, diamond property. Well-founded induction, её использование. Datalog, стратифицированное отрицание, применение для анализа программ. (RO)BDD.