С задачей о перколяции можно встретить в разных областях науки: при анализе зависимости проводимости тонких композитных пленок от соотношения концентраций металла и диэлектрика в составе пленок; при определение связности компьютерных сетей; при определении условий просачивания жидкостей через пористую поверхность. Чтобы формально описать задачу перколяции рассматривают модель на основе квадратной решетки.
Рассмотрим решетку n клеток на n клеток. Каждая клетка решетки может быть открыта или заблокирована. Полной клеткой называется клетка, которая соединена с открытой клеткой, находящейся в верхнем ряду клеток через цеполчку соседей, которые являются открытыми клетками и находятся сверху, снизу, слева и справа (т.е. соседние клетки имеют общую границу). Говорят, что в решетке есть перколяционный кластер, если есть полная клетка в нижнем ряду решетки. Если говорить менее формально, то система будет протекать если существует полная клетка в нижнем ряду решетки.
Давайте считать, что каждая клетка с некоторой вероятностью p открыта или занята (независимо от клеток соседей). С какой вероятностью система будет протекать? Очевидно, что если p = 0, то система точно не протекает, если p = 1, то система протекает. Вот пример того, как изменяется вероятность протекания системы в зависимоти от выбранного значения p для решеток 20x20 (слева) и 100x100 (справа):
Если мы будем смотреть на достаточно больше решетки, то найдем такое значение p* что при p < p* произвольная система, почти всегда, не протекает и при p > p* почти всегда протекает. Вам требуется написать программу, которая поможет найти значение p* которое является порогом перколяции.
Вам потребуется реализовать класс Percolation.
Чтобы найти порог перколяции p* выполните следующие шаги:
- Создайте решетку, где все клетки заблокированы
- Повторяйте шаги из этого пункта до тех пор, пока система не начнет протекать
- Среди всех заблокированных ячеев выирайте случайную ячейку (используйте равномерное распределение)
- Сделайте эту ячейку открытой
- Соотношение открытых и заблокированных ячеек дает оценку для порога перколяции.
Для того, чтобы точнее понять, каким может быть значение порога перколяции потребуется построить доверительных интервал. Для этого проведем эксперимент T раз и сохраним результат 3-го шага x_t. На основе полученных значений вычилим величины x¯ и s^2:
При достаточно больших значений T доверительный интервал для порога перколяции это:
Вам потребуется реализовать класс PercolationStats.