Если вас попросят загадать случайное число, то ваш мозг легко справится с задачей. Он за считанные мгновения придумает что-то. Компьютеру тоже иногда надо выполнить эту задачу. Вот беда: он мыслит исключительно алгоритмами. Но если есть инструкция для выполнения, то значит, следующее число можно предсказать? Какое же это тогда случайное число?
Наверное, каждый начинающий программист при использовании генератора рандомных чисел допускал ошибку: кажется, что последовательность чисел случайная, но если программу перезапустить, то она ровно такая же...
На самом деле такая простая, казалось бы, задача — придумать числа для программирования — сложная. Хороший рандомизатор — на вес золота.
Генератор случайных чисел в программировании — это квазислучайный алгоритм. На выходе последовательность выглядит случайной, но под ней есть определенный алгоритм. Для работы со случайными числами такого положения дел достаточно.
От чисел перейдём к более сложным структурам. На прошлой неделе поговорили о случайных графах, сегодня — о квазислучайных, то есть они будут выглядеть как случайные, но на самом деле их будет создавать конкретная инструкция. Точно так же, как и с числами.
Важное пояснение: «выглядеть как случайные» = вы НЕ можете из двух графов определить, который нарисовали случайно «с монеткой», а какой — по специальному алгоритму.
Зачем может быть такое надо?
Например, для стабильного тестирования алгоритмов на случайных графах. Чтобы не было ситуации, когда система говорит «тест упал», вы хотите увидеть пример, на котором не работает, а его нет. И повторить нельзя. Можно сделать шаг в сторону от тестов и сказать тут одно слово — «воспроизводимость». Если нам где-то такое нужно, то настоящая случайность не подходит.
Другой пример, который даст подсказку, а зачем мы вообще всё это смотрим, связан с сетями. Мы обсуждали на примере fat-tree, что вместо одной толстой трубы можно сделать сеть из мелких дешёвых трубок. Сеть — это, конечно, граф.
Чтобы сеть получилась хорошей, она должна быть связной, устойчивой (= выпадение одного узла не ломает связность), экономной на рёбрах (= строить связи всех узлов со всеми — это дорого). Выяснилось, что случайные графы оказались примерами ХОРОШИХ сетей. Но, конечно, при строительстве ДЦ мы не можем генерить что-то случайное. Поэтому надо взять что-то определяемое алгоритмом, которое будет обладать свойствами случайного графа.
Ещё один интересный момент — это утверждение, что если взять огромный граф, порезать его на куски, то почти каждый кусок будет вести себя случайно. Это значит, что квазислучайность — это не редкость, а чуть ли не универсальный кирпич, из которого строятся большие графы. Понял, как ведёт себя кирпич? Значит, понял, как ведёт себя огромная сеть. Этим свойством пользуются в математике для доказательства теорем.
Давайте разберём, что значит фраза «граф ведёт себя квазислучайно».
Начнём с фантазии на тему «что мы ожидаем от настоящего случайного графа». Первая мысль — рёбра будут размазаны равномерно. Нет каких-то откровенных «пучков» или «пустот». Значит, первая проверка, какую можно сделать, — возьми любое подмножество вершин и проверь, что рёбер там столько же, сколько ждём от монетки.
Спасибо, конечно, но подмножеств вершин великое множество. Если в графе, скажем, 100 вершин — способов выбрать «кусок» получается больше, чем атомов в комнате. Проверять каждый кусок вручную — нереально. Жизни не хватит. Нужен какой-то простой способ.
Он есть, он математически доказан и он до безумия забавный. Нужно посчитать «квадратики».
Квадрат (или «4-цикл») — это четыре вершины, замкнутые в колечко:
A --- B
| |
D --- C
Весь трюк: надо просто посчитать, сколько в графе таких квадратиков. И сравнить с тем, сколько их было бы у случайного графа, для которого это число считается по математической формуле. В качестве домашнего задания попробуйте вывести (np)^4/8, где n — число вершин, а p — вероятность нашей монетки. Погрешность допускается.
А есть ли алгоритмы построения квазислучайных графов? Узнаем завтра!
#бабанюра_программирует