Карта связей: от стрелки до маршрутаЛогика / Отличать частичный порядок от полного Пробное занятие
Логика · шаг 35 из 64

Порядок без единственной очереди

Отличать частичный порядок от полного · Считать допустимые очереди

Около 20 минут 5 задач Подсказки рядом

В этом занятии

  • Отличать частичный порядок от полного
  • Считать допустимые очереди
  • Находить цикл зависимостей

Пригодится: Рекомендуем сначала пройти «Когда разные записи обозначают одно».

Ваш путь начинается с личного кабинета

Взрослый создаёт аккаунт для себя и отдельные кабинеты для школьников. У каждого — свой прогресс. Общие 48 часов знакомства начинаются с регистрации взрослого; школьники получают оставшееся время.

Войти или начать бесплатно
Учебное время начнёт считаться после нажатия
Понять — интереснее, чем запомнить.
Разберёмся перед практикой+

Порядок без единственной очереди

У задач проекта бывают зависимости: обложку можно выбрать независимо от расчёта, но публикация требует обоих результатов. Отношение «должно завершиться не позже» задаёт частичный порядок, когда оно рефлексивно, антисимметрично и транзитивно. Некоторые пары остаются несравнимыми.

Для планирования часто рисуют строгие зависимости А раньше Б без петель. Допустимая очередь должна сохранить каждую такую стрелку. Несравнимые задачи разрешено менять местами, поэтому одна найденная очередь не доказывает единственности и не превращает частичный порядок в полный.

Цикл строгих зависимостей А раньше Б, Б раньше В, В раньше А делает очередь невозможной. Не следует чинить модель случайной перестановкой: надо пересмотреть хотя бы одно требование. Петля «А раньше А» тоже противоречит строгому смыслу слова «раньше».

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

НА ПРИМЕРЕ

Три дела А, Б, В выполняются по одному. Единственное требование — А раньше В. Нужно ли ставить Б обязательно вторым?

  1. Перебираем шесть очередей из трёх различных дел.
  2. Оставляем АБВ, АВБ и БАВ: в каждой А стоит раньше В.
  3. Позиция Б различается; допустимых очередей три.

Загружаем интерактивную модель…

Попробуйте самостоятельно

Запишите рассуждения в черновик или сделайте построение на бумаге. Эти задания для самостоятельной работы: автоматической проверки и XP за них пока нет.

  1. В модели добавь условие, которое уменьшает число очередей, но не делает очередь единственной.
  2. Для своего минипроекта отдели настоящую зависимость от предпочтения «мне так удобнее».

Читайте и разбирайте пример в своём темпе. К практике можно перейти, когда будете готовы.