|
Много не мало, или Мнимые противоречия |
3 июля |
Много и мало ‐ понятия относительные. Если надо выигрывать чаще, а силы равны, то надо много раз выиграть по чуть-чуть, а проиграть много, но один раз. |
|
|
Свяжитесь с графом |
7 июля |
Выкинем из графа все ребра, будем восстанавливать их по одному и следить за числом компонент. Так получим неравенство, связывающее число вершин, ребер и компонент. Это неравенство позволяет получать оценки в ситуации, когда удается ситуацию описать с помощью графа (порой, весьма неожиданно). |
|
|
Одинаковые графы |
8 июля |
Понимание того, что два графа разной природы на самом деле одинаковы (изоморфны) поможет перенести знания от одного графа к другому. |
|
|
Двудольный граф |
9 июля |
Граф – двудольный, если его вершины можно раскрасить в два цвета так, что не будет ребер с концами одинакового цвета. При движении по двудольному графу цвета вершин строго чередуются, поэтому вернуться в исходную вершину можно только за чётное число ходов. |
|
|
Подсчет двумя способами в графах |
10 июля |
Двумя способами чаще всего считают рёбра. Если следят только за четностью, получается лемма о рукопожатиях. |
|
|
Эйлеровы пути и обходы |
12 июля |
Доказан критерий обхода всех рёбер ровно по разу. Указано, как строить кратчайшую последовательность цифр, наверняка открывающую кодовый замок. |
|
|
Испытания и оценки |
13 июля |
Пусть надо выявить один предмет из многих, и каждый вопрос делит все предметы на несколько групп, выясняя, в какую из групп попал искомый случай. Жадный алгоритм рекомендует делить на равные группы или делать максимальный размер группы как можно меньше. |
|
|
Пространство вариантов |
14 июля |
Ответом к задаче на испытания может быть не один предмет, а пара или группа предметов. Полезно все возможные ответы закодировать и посчитать. Полученное множество и называется пространством вариантов. Каждое испытание делит это пространство на подмножества. Полезно выписать все возможные варианты и делать такие испытания, чтобы количество подозрительных вариантов в наихудшем случае было как можно меньше. |
|
|
Неоднозначные данные |
15 июля |
Чтобы доказать, что информации недостаточно для получения однозначного ответа, можно построить два примера, которые удовлетворяют всем условиям, но дают разные ответы. |