|
Посредники в неравенствах |
4 июля |
Чтобы доказать неравенство A < B можно выбрать посредник P и доказать, например, A < P и P < B. Искусство состоит в выборе P. |
|
|
Жадный алгоритм |
5 июля |
Если цель – максимум какой-то величины, то ее часто достигают с помощью «жадного алгоритма», то есть, добиваясь максимально возможного приращения на каждом шаге. |
|
|
Периодичность и непериодичность |
9 июля |
«Плохое свойство» (например, непериодичность) удобно доказывать «от противного»: ведь противное в этом случае – хорошее! |
|
|
Зацикливание вперед и назад |
10 июля |
Если система может находиться лишь в конечном числе состояний, и каждое следующее состояние зависит лишь от фиксированного числа предшествующих состояний, она с некоторого момента зациклится. |
|
|
Индукция |
11 июля |
Наиболее оправдано применение индукции при построении сложных конструкций, когда очередной этаж строится на основе уже построенных нижних этажей. Такое построение может быть при необходимости преобразовано в явный алгоритм. |
|
|
Неоднозначные данные |
12 июля |
Чтобы доказать, что информации недостаточно для получения однозначного ответа, можно построить два примера, которые удовлетворяют всем условиям, но дают разные ответы. |
|
|
Свяжитесь с графом |
14 июля |
Увидеть граф за условием задачи помогают выделенные пары объектов, в частности, соседние объекты или клетки с общей границей. Выписывая для таких графов уравнения и неравенства для В, Р, С, можно получать нетривиальные оценки |
|
|
Бесконечные алгоритмы |
15 июля |
В бесконечных алгоритмах часто можно не заботиться о любом конечном числе начальных ходов: за оставшееся бесконечное число ходов все удастся исправить! |