НАЗАД

Программирование в ограничениях: ставим задачу компьютеру правильно

В данном разделе представлены массовые открытые онлайн-курсы (МООК). МООК является дополнительным учебным материалом. 

Обращаем Ваше внимание, что изучение МООК доступно любому зарегистрированному пользователю, однако МООК не является частью образовательных программ повышения квалификации. 

Изучение материалов МООК не предполагает выдачу удостоверений, сертификатов или иных документов, подтверждающих их изучение.

Подавляющее большинство языков программирования являются императивными: программист описывает компьютеру последовательность шагов, приводящую к решению задачи. Но есть и другие парадигмы программирования, набирающие популярность, например, функциональная. Мы же рассмотрим ещё одну парадигму: программирование в ограничениях. В ней программист описывает компьютеру не как решать задачу, а что подразумевается под итоговым решением. А специальная программа — солвер — решает задачу под наши требования. Мы разберём основные элементы программирования в ограничениях, знание которых будет полезно будущим или уже состоявшимся программистам, независимо от используемого ими основного языка.

Результаты обучения:

  • Знать типичные подходы к решению классических задач выполнимости и оптимизации, разработанные в рамках программирования в ограничениях.
  • Знать методы поиска решений в различных типах пространств поиска.
  • Уметь выполнять сравнительный анализ и обосновывать выбор модели и средства формализации решений.
  • Уметь построить модель заданной предметной области с использованием изученных средств представления знаний.
  • Уметь применить методы решения задач, разработанные в рамках программирования в ограничениях в своей проблемной области.
  • Уметь находить адекватную формализацию задач оптимизации с учетом механизмов и концепций, изученных в процессе освоения курса.
МООК
Программа
1
Программирование в ограничениях: ставим задачу компьютеру правильно

a.
Трейлер
2
Императивное программирование vs. программирование в ограничениях. Основные понятия и первые модели

a.
Вводное слово

b.
Отличие ПвО от ИП (на примере вычисления чисел Фибоначчи)

c.
Задача о ферзях I — модель с булевскими переменными («досочные» переменные). Конструкции if-then, forall, exists

d.
Задача о ферзях I. Именованные диапазоны. Условия на диагонали

e.
Задача о ферзях I. Вложенные кванторные конструкции и масштабируемость

f.
Задача о ферзях I. Объединяем кванторные конструкции

g.
Задача о ферзях I. Оператор вывода

h.
Задача о ферзях I. Разница между солверами. Вывод статистики

i.
Разбор задачи Криптарифмы

j.
Тестирование
3
Взгляд под разными углами на одну задачу

a.
Задача о ферзях II — модель с целочисленными переменными («ферзевые переменные»). Начало

b.
Задача о ферзях II. Завершение

c.
Задача о ферзях II. Глобальное ограничение alldifferent

d.
Задача о ферзях II. Снятие симметрии

e.
Задача о ферзях III — линейная модель с целочисленными 0,1-переменными. Начало

f.
Задача о ферзях III. Завершение

g.
Линейные модели на Python с библиотекой PuLP

h.
Тестирование
4
Специальные ограничения: глобальные, избыточные, снимающие симметрию

a.
Задача коммивояжера. Постановка и первая модель

b.
Задача коммивояжера. Доводка модели

c.
Задача коммивояжера. Снятие симметрии в первой модели и вторая модель

d.
Задача коммивояжера. Построение линейной модели

e.
Задача коммивояжера. Окончательная линейная модель

f.
Тестирование
5
Как работает типичный солвер и как мы можем повлиять на его стратегию

a.
Обработка ограничений солвером

b.
Избыточные ограничения и ограничения снятия симметрии

c.
Поиск симметрии

d.
Дерево разбора случаев

e.
Задача о магическом квадрате. 1 часть

f.
Задача о магическом квадрате. 2 часть

g.
Модели на Python с библиотекой Google OR tools

h.
Тестирование
6
Практикуемся в решении задач

a.
Задачи об упаковке. Рюкзак

b.
Задачи об упаковке. Упаковка в контейнеры

c.
Задачи об упаковке. Конфигурационная модель

d.
Задачи об упаковке. Геометрическая упаковка

e.
Задачи о покрытии

f.
Задачи о раскрасках

g.
Заключение

h.
Тестирование

i.
Итоговое тестирование
Преподаватели