ЛАБОРАТОРНАЯ РАБОТА No. 1
.pdf
ЛАБОРАТОРНАЯ РАБОТА № 1
«ПРОСАЧИВАНИЕ»
Просачивание (перколяция). Рассмотрим примеры задач на просачивание.
-Дана составная система, состоящая из случайно распределенных участков являющихся либо изоляторами, либо металлами: какая часть материала должна быть металлической, чтобы вся составная система являлась проводником?
-Имеем пористый участок ландшафта с водой на поверхности (или, аналогично, с нефтью на дне), при каких условиях вода на поверхности будет способна протечь сквозь участок почвы в низ, на дно (или нефть, аналогично, сможет подняться на поверхность участка почвы)?
Ученые определили абстрактный класс задач, названный просачиванием (или перколяцией) для моделирования подобных ситуаций.
Модель системы. Мы моделируем просачивающуюся систему, используя N-by-N сетку узлов. Каждый узел данной системы либо открыт, либо заблокирован. Полный узел – это открытый узел, который может быть соединен с каким-либо открытым узлом в верхнем ряду сетки модели системы при помощи цепочки соседей (слева, справа, сверху, снизу) также являющихся открытыми узлами. Система является просачивающейся, если в ней есть полный узел в нижнем ряду сетки. Другими словами, система является просачивающейся, если, при наполнении жидкостью всех открытых узлов в верхнем ряду сетки, жидкость протечет по открытым узлам до нижнего ряда сетки моделирующей систему.
Проблематика. В данной алгоритмической проблеме, исследователи заинтересованы в поиске ответа на следующий вопрос: если узлы являются независимыми элементами, открытыми с вероятностью p (и, следовательно, заблокированными с вероятностью 1 − p), какова вероятность того, что система является просачивающейся? Когда p равна 0, система не просачивается; когда p равна 1, система просачивается. График ниже показывает зависимость вероятности просачивания (percolation probability) системы от вероятности того, что узел сетки является открытым (site vacancy probability). Для вычисления использовались случайные значения на моделирующих сетках размерности
20-by-20 (слева) и 100-by-100 (справа).
Когда число N достаточно велико, можно заметить некоторое пороговое значение p*, такое, что когда p < p* случайная сетка N-by-N почти никогда не просачивается, а когда p > p*, случайная сетка N-by-N почти всегда просачивается. На данный момент не существует математического решения для определения порогового значения вероятности просачивания p*, однако оно может быть выявлено в ходе моделирования на ЭВМ.
Вашей задачей является написание программы вычисляющей p*.
Класс Percolation. Для моделирования просачивающейся системы, создайте структуру данных Percolation со следующим API:
public class Percolation { public Percolation(int N)
public void open(int i, int j) public boolean isOpen(int i, int j) public boolean isFull(int i, int j)
public boolean percolates()
}
//конструктор,создает N-by-N
//сетку,все узлызаблокированы
//открывает узел (строка i, столбец j)
//если он еще не открыт
//открыт ли узел
//(строка i,столбец j)?
//является ли узел
//(row i, column j) полным?
//является ли система просачивающейся?
По условию, договоримся, что индексы i и j представлены целыми числами, лежащими в промежутке от 1 до N, где (1,1) – верхний левый узел: выбрасывайте java.lang.IndexOutOfBoundsException , если i или j находится вне данного диапазона.
Конструктор должен занимать время выполнения пропорциональное сложности О(N^2); все методы должны занимать константное время O(1), плюс константное количество вызовов “union-find” методов union(), find(), connected(), и count().
Моделирование методом Монте-Карло. Для оценки порогового значения вероятности просачивания p*, рассмотрим следующий вычислительный эксперимент:
Инициализируем все узлы сетки заблокированными.
Повторим следующие шаги до выполнения условия просачивания системы: o Выбираем случайный узел среди всех заблокированных узлов.
o Открываем выбранный узел (строка i, столбец j).
Доля числа открытых узлов от общего числа узлов в сетке, в момент просачивания
системы дает оценку порогового значения вероятности просачивания.
Например, если узлы на сетке 20-by-20 открываются последовательно, в соответствии со скриншотами ниже (белым цветом показаны открытые узлы, синим - полные), то оценка порога перколяции равна 204/400 = 0.51, потому что система начинает просачиваться, когда открывается 204-ый узел. Таким образом, для данного примера p* = 0.51.
50 открытых узлов |
100 открытых узлов |
150 открытых узлов |
204 открытых узла |
Повторяя данный вычислительный эксперимент T раз и усредняя результаты, мы получим более точную оценку порога вероятности просачивания. Пусть xt будет долей открытых участков в вычислительном эксперименте t. Эмпирическое среднее - μ, обеспечивает оценку порога просачивания; дисперсия случайной величины σ измеряет показатель рассеивания значений случайной величины относительно еѐ математического ожидания.
Предположив, что T достаточно большое число (скажем, не меньше 30), следующая формула обеспечивает 95% доверительный интервал для порога просачивания:
Для выполнения серии вычислительных экспериментов, создайте структуру данных PercolationStats со следующим API.
public class PercolationStats { |
|
public PercolationStats(int N, int T) |
// конструктор, выолняющий T |
//независимых вычислительных экспериментов на сетке N-by-N |
|
public double mean() |
// расчет эмпирического среднего |
public double stddev() |
// расчет дисперсии порогового значения |
public double confidenceLo() |
//возвращает нижнюю границу 95% |
|
//доверительного интервала |
public double confidenceHi() |
//возвращает верхнюю границу 95% |
//доверительного интервала // тестовый клиент,описан ниже
Конструктор должен выбрасывать java.lang.IllegalArgumentException если N ≤ 0
или T ≤ 0.
Также, реализуйте метод main(), который принимает два аргумента командной строки N и T, выполняет T независимых вычислительных экспериментов (описано выше) на сетке из N-by-N узлов, и выводит среднее значение (mean), стандартное отклонение, и 95% доверительный интервал для порога просачивания. Используйте standard random (StdRandom) из библиотеки stdlib для генерации случайных чисел. Пример вывода в консоль представлен ниже.
% java PercolationStats |
200 100 |
|
mean |
= 0.5929934999999997 |
|
stddev |
= |
0.00876990421552567 |
95% confidence interval |
= |
0.5912745987737567, 0.5947124012262428 |
% java PercolationStats |
200 100 |
|
mean |
= 0.592877 |
|
stddev |
= |
0.009990523717073799 |
95% confidence interval |
= |
0.5909188573514536, 0.5948351426485464 |
% java PercolationStats 2 10000
mean |
= |
0.666925 |
stddev |
= |
0.11776536521033558 |
95% |
confidence |
interval = 0.6646167988418774, 0.6692332011581226 |
|||
% java |
PercolationStats |
2 |
100000 |
||
mean |
|
|
|
= 0.6669475 |
|
stddev |
|
|
= 0.11775205263262094 |
||
95% |
confidence |
interval |
= |
0.666217665216461, 0.6676773347835391 |
|
Анализ времени выполнения и расхода памяти. Реализуйте структуру данных
Percolation , используя предоставленную реализацию алгоритма quick-find QuickFindUF.java.
Используйте структуру данных stopwatch из библиотеки Stdlib для измерения общего времени выполнения эксперимента PercolationStats. Как на времени выполнения алгоритма сказывается увеличение числа N в два раза? Как на времени выполнения алгоритма сказывается увеличение числа T в два раза? Определите формулу зависимости общего времени выполнения на вашем компьютере (в секундах) двумя отдельными функциями от N и T.
Используя 64-битную модель стоимости памяти из лекции, дайте общую оценку расхода памяти в байтах, которую потребляет сетка перколяционной систему размерности N-by-N. Подсчитайте всю используемую память, включая ту, что расходуется на структуру данных “Union find”.
Теперь, реализуйте класс Percolation , используя предоставленную реализацию взвешенного алгоритма “quick-union” WeightedQuickUnionUF.java. Теперь снова, ответьте на вопросы перечисленные выше.
Ответы на данные вопросы должны также быть оформлены и предоставлены для защиты лабораторной работы.
Результаты выполнения. Должны быть предоставлены только классы Percolation.java (использующий взвешенный quick-union алгоритм, реализованный в предоставленном файле класса WeightedQuickUnionUF) и PercolationStats.java. В реализации классов не должно быть вызовов, каких бы то ни было, дополнительных библиотек или внешних классов, кроме java.lang, stdlib.jar, и WeightedQuickUnionUF. Публичный API классов должен полностью соответствовать описанным в данном задании, без исключений.