Автор: Вадим Рублев | Ярославский Государственный Университет им. П.Г. Демидова
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
 
Уровень:
Специалист
Длительность:
10:47:00
Студентов:
839
Выпускников:
18
Качество курса:
4.50 | 4.00
Учебное пособие знакомит с языками типа модели Маркова, которые называют языками логического программирования или искусственного интеллекта.
Традиционные языки программирования, наиболее часто используемые на практике, относятся к модели языков фон Неймановского типа. Эта модель тесно связана с одной из моделей алгоритмов, называемой Машинами Тьюринга. Другая модель алгоритмов - нормальные алгоритмы Маркова - является основой языков программирования другого типа, которые называют языками логического программирования за направленность на решение задач логического типа. Эти языки иногда называют языками функционального программирования, поскольку программы, написанные на них, выражают явным образом функциональный подход к программированию, а также называют языками искусственного интеллекта за их использование в программировании сложных интеллектуальных задач. Настоящее учебное пособие посвящено этому направлению развития языков программирования.
 

План занятий

Занятие
Заголовок <<
Дата изучения
Лекция 1
24 минуты
Нормальные алгоритмы Маркова
Определение нормального алгоритма Маркова и его выполнение. Возможности нормальных алгоритмов Маркова и тезис Маркова. Методика разработки нормальных алгоритмов Маркова.
-
Лекция 2
36 минут
Язык РЕФАЛ: простейшие конструкции Рефала-2
Развитие модели Маркова и обзор языка Рефал: модификации языка нормальных алгоритмов Маркова, введенные в Рефал; версии Рефала. Рефал-выражения: скобки символьные, составные, структурные и функциональные; определение рефал-выражения и примеры. Определение терма. Рефал-функции: вызов и описание рефал-функции; рефал-предложение и интерпретация переменных; типы переменных; примеры описаний рефал-функций.
-
Лекция 3
23 минуты
Язык РЕФАЛ: сложные конструкции Рефала-2
Спецификации переменных: синтаксис спецификации; спецификатор и его элементы; элементы-множества спецификатора; общий вид спецификатора; определение имени спецификатора и его использование. Структора рефал-программы и ее модулей: директива программы и ее части; директива комментария; ключевые слова директив; модульность и объявление входов и внешних имен; пример двухмодульной программы.
-
Лекция 4
33 минуты
Язык РЕФАЛ: первичные функции и примеры составления программ
Первичные функции Рефала-2: функции ввода/вывода; арифметические функции; функции лексического анализа; функции для работы с символами-метками. Синтаксический анализатор для языка арифметических выражений: описание синтаксиса языка формами Бэкуса-Наура; программа анализатора и ее близость к языку БНФ. Программа суммирования последовательности чисел и ее особенности.
-
Лекция 5
49 минут
Язык РЕФАЛ: дополнительные виды памяти
Рекурсивные вычисления и функция порождения процесса: функция apply; пример вычислений на Рефале функции n!. Стековая память Рефала: копилка и вид ее содержимого; функции работы с копилкой; пример сортировки массива. Обменная статическая и динамическая память: ящики и обменные функции; статические и динамические ящики; функции работы с динамическими ящиками; пример программы, работающей с поисковым списком (инициализация списка, добавление элемента списка, поиск элемента по ключу, удаление элемента списка).
-
Лекция 6
37 минут
Язык РЕФАЛ: Рефал-5
Синтаксические отличия Рефала-5 от Рефала-2; пример программы n! на Рефале-5. Условие в рефал-предложении Рефала-5: пример проблемы недостаточной наглядности при организации взаимной рекурсии двух функций; синтаксис условия и его семантика; решение проблемы недостаточной наглядности введением условия в рефал-предложение; примеры использования условия в функции сложения Add и решении задачи о назначениях. Блок как структурирующая конструкция Рефала-5: улучшение наглядности программы; пример сортировки слиянием двух упорядоченных последовательностей; образцовый окончание и образцовый блок рефал-предложения; результатный блок и результатное окончание рефал-предложения; пример функции сравнения множеств.
-
Лекция 7
35 минут
Язык ПРОЛОГ: основные конструкции
Общая характеристика языка Пролог: базы знаний и экспертные системы. Объекты и термы Пролога: объекты Пролога - имена, переменные и списки; основные и неосновные термы; атомы. Факты Пролога: синтаксис фактов; универсальные факты. Правила Пролога: проблема недостаточности фактов для описания базы знаний; синтаксис правила - заголовок и тело правила; процедура как объединение правил с одним заголовком; программа Пролога как совокупность фактов и правил. Запросы Пролога: синтаксис запроса; ответ на запрос без переменных; запрос с переменными и интерпретация переменных при выполнении программы; примеры программ с запросами для них.
-
Лекция 8
30 минут
Язык Пролог: вычисления и процедурная семантика Пролога
Алгоритм вычислений программы на Прологе: порядок рассмотрения атомов в запросе; вызов процедуры для атома; интерпретация переменных и замена атома запроса; ветвление при невозможности интерпретации; правило остановки вычислений; примеры вычислений запросов для программы родства и программы соединения списков; сходство Пролога с языками нормальных алгоритмов Маркова и Рефалом.
-
Лекция 9
24 минуты
Язык Пролог: чистый недетерминированный Пролог и процедурная семантика
Синтаксис программ и запросов: формальные определения. Подстановки: определение подстановки и результата ее применения к разным выражениям Пролога; частный случай и вариант; унификатор выражений и наиболее общий унификатор и их примеры; интерпретация программы и модель программы; основная модель программы; ответ и правильный ответ; множество всех правильных ответов. Процедурная семантика: отношение выводимости запросов; пространство вычислений и его представление в виде дерева. Адекватность процедурной семантики.
-
Тест 9
21 минута
-
Лекция 10
20 минут
Язык Пролог: стратегии вычислений и встроенные отношения
Стратегии вычислений: последовательные вычисления; стратегия в глубину и слева направо; проблема бесконечных ветвей; проблема большого перебора; правило отсечения и пример программы для базы знаний библиотеки; добавление спецификаций; стратегия в ширину и ее преимущество при бесконечных ветвях; параллельные вычисления и стратегии "или"-параллельности и "и"-параллельности. Встроенные отношения: встроенные отношения и предикаты; дополнительные функторы для операций отрицания и дизъюнкции.
-
Лекция 11
21 минута
Модель Бэкуса алгебры программ: основные конструкции
Общая характеристика модели Бэкуса. Базис модели Бэкуса: атомы и примитивные функции как скалярные типы; объекты и формы как структурные типы; атомы и кортежи; неопределенность; примеры функций. Примитивные функции Пролога: условное выражение Маккарти и синтаксис описания функций; логические функции; арифметические операции и отношения; функции кортежей; функции логических операций.
-
Лекция 12
28 минут
Модель Бэкуса алгебры программ: фундаментальные формы и определение функций
Основные формы и примеры для них: композиция; конструкция; условие и форма Бэкуса для условия; генератор постоянных; редукция; общая аппликация; итерация; специализатор. Функции: определение функции; примеры создания функций pair (пара ли кортеж), last (последний элемент кортежа), long (длина кортежа), trans (транспонирование матрицы), !n (факториал), IP (скалярное произведение); особенности стиля программирования в модели Бэкуса.
-
Лекция 13
9 минут
Модель Бэкуса алгебры программ: алгебра программ
Алгебра программ: класс функций как область значений алгебры; формы как операции алгебры; аксиомы алгебры программ и их обоснование; пример доказательства теорем при помощи алгебры программ.
-
Лекция 14
23 минуты
Модель Бэкуса алгебры программ: умножение матриц и алгебраическое преобразование программы
Программа умножения матриц: пошаговая разработка программы; анализ программы с целью оптимизации; оптимизация программы и доказательство ее корректности с помощью алгебры программ.
-
1 час 40 минут
-
Сергей Шумихин
Сергей Шумихин
Украина
Александр Петухов
Александр Петухов
Россия, Екатеринбург