1

Испытания и оценки

13 сентября 2014 г.

Листок

 Пусть надо выявить один предмет из многих. Каждый вопрос делит все предметы на несколько групп, выясняя, в какую из групп попал искомый случай. Жадный алгоритм рекомендует делить на равные группы или делать максимальный размер группы как можно меньше.

2

Кодировка

13 сентября 2014 г.

Листок

 Кодировка устанавливается взаимно-однозначное соответствие между объектами (состояниями) из задачи и комбинаторными комбинациями (сочетаниями, размещениями, перестановками). Например, соответствие последовательностям из 0 и 1 называют двоичной кодировкой.

3

Пространство вариантов

14 сентября 2014 г.

Листок

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

4

Формула включения-исключения

14 сентября 2014 г.

Листок

 Пусть для каждого набора свойств известно число объектов с таким набором. Ищем количество объектов, удовлетворяющих хотя бы одному свойству. Оно равно сумме чисел для нечетных наборов минус сумма по всем четным наборам.

5

Соответствие и исключение

15 сентября 2014 г.

Листок

 Число объектов вычислем с помощью арифметических действий с размерами частей. А эти размеры вычисляем через однозначное соответствие с более удобными множествами.

6

Неоднозначные данные

15 сентября 2014 г.

Листок

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