Условия совместимы, но единственен ли ответ
Различать отсутствие решений, несколько решений и единственное решение · Проверять все ограничения одновременно
В этом занятии
- Различать отсутствие решений, несколько решений и единственное решение
- Проверять все ограничения одновременно
- Отделять возможное от необходимого
Пригодится: Рекомендуем сначала пройти «Небольшой эксперимент вместо большой догадки».
Разберёмся перед практикой+
Условия совместимы, но единственен ли ответ
Система условий непротиворечива, если существует хотя бы один случай, в котором все условия выполнены одновременно. Найденный пример доказывает возможность, но не единственность. Чтобы доказать единственность, нужно исключить все другие варианты подходящим рассуждением или полным перебором конечного набора. Если ни один вариант не подходит, проверь, не конфликтуют ли требования или не ошибочно ли записано одно из них.
В задачах на расписание удобно сначала назвать объекты, допустимые позиции и правило различия: например, три выступления занимают разные места с первого по третье. Затем каждое словесное условие превращают в ограничение. «А раньше Б» допускает соседние и несоседние места; «А непосредственно перед Б» уже требует соседства. Маленькое слово может существенно изменить число решений.
Высказывание возможно, если истинно хотя бы в одном допустимом варианте; необходимо, если истинно во всех. Подходящий единичный пример подтверждает возможность, а контрпример среди допустимых вариантов опровергает необходимость. Нельзя использовать для возражения вариант, нарушающий исходные условия: тогда он относится к другой задаче. Важно сохранять весь набор ограничений на каждом шаге.
В реальном проекте несколько решений часто являются преимуществом: можно выбрать удобное по дополнительным критериям. Если нужна единственность, добавляют ясное правило, а не скрыто угадывают намерение автора. Если условия несовместимы, полезно найти небольшой конфликтующий набор и пересмотреть требование совместно с тем, кто его задал. Подмена неудобного условия молчаливым исключением не решает исходную задачу.
Три выступления А, Б и В занимают разные места 1, 2, 3. А раньше Б. В не последнее. Условия не требуют, чтобы А и Б стояли рядом.
- Если В первое, оставшиеся А и Б обязаны идти в порядке А, Б: получаем В–А–Б.
- Если В второе, для А раньше Б остаётся А–В–Б.
- В третье запрещено, значит перечислены все случаи: решений ровно два.
- Б последнее в обоих решениях, поэтому это необходимо. А первое лишь в одном, поэтому возможно, но не обязательно.
Загружаем интерактивную модель…
Попробуй самостоятельно
Запиши рассуждения в черновик или сделай построение на бумаге. Эти задания для самостоятельной работы: автоматической проверки и XP за них пока нет.
- Объясни различие между «я нашёл подходящее расписание» и «другого подходящего расписания не существует».
- Составь три ограничения для небольшого совместного плана: времени встречи, порядка задач или распределения ролей. Найди два разных решения либо покажи, почему решение единственно или отсутствует.
Читай и разбирай пример в своём темпе. К практике можно перейти, когда будешь готов.