Случайная функция –случайная величина, зависящая не только от случайного события ω, но и от какого-либо параметра. Если этот параметр – время, то случайная функция называется случайным процессом и обозначается ξ (t,ω).

Величина ξ может быть как скалярной (скалярный случайный процесс), так и векторной (векторный или многомерный случайный процесс). Она может принимать как дискретные значения (процесс с дискретными состояниями), так и пробегать непрерывный ряд значений

Метод Монте-Карло - общее название группы численных методов, основанных на получении большого числа реализаций стохастического (случайного) процесса, который формируется таким образом, чтобы его вероятностные характеристики совпадали с аналогичными величинами решаемой задачи.

Суть метода была в бросании иглы длиной L на плоскость, расчерченную параллельными прямыми, расположенными на расстоянии r друг от друга.

Ограничим функцию прямоугольником (n-мерным параллелепипедом в случае многих измерений), площадь которого S0 можно легко вычислить;

«набросаем» в этот прямоугольник (параллелепипед) некоторое количество точек (N штук), координаты которых будем выбирать случайным образом;

определим число точек (K штук), которые попадут под график функции;

площадь области, ограниченной функцией и осями координат, S даётся следующим выражением S = S0 K / N

Взаимодействие нейтронов с веществом характеризуется в рассматриваемом случае двумя постоянными Σc и Σs , которые называются сечением поглощения и сечением рассеяния (индексы с и s—это первые буквы английских слов capture -- захват и scattering -- рассеяние). Сумма этих сечений Σ = Σc + Σs называется полным сечением.

Пусть есть прямоугольная решетка, состоящая из N*N свободных и занятых узлов.
Пусть вероятность того, что узел занят – p, и, соответственно, вероятность того, что узел свободен (1-p).

Будем называть кластером соседние занятые узлы и стягивающим кластером (перколяционным кластером) такой кластер, который начинается на одной границе и заканчивается на противоположной границе решетки.

Образование стягивающего кластера называется перколяцией.

1. Задать значение вероятности занятости узла p.

2. Разыграть состояние каждого узла при заданном значении p, тем самым построив конкретную реализацию решетки.

3. Определить, есть ли в этой реализации хотя бы один стягивающий кластер. Если есть, то увеличить счетчик числа стягивающих кластеров Mc на единицу.

5. Получить оценку вероятности образования стягивающего кластера

6. Повторить 1-5 для ряда значений вероятности p в интервале от 0 до 1.

Физика (исторически первый источник) – задачи просачивания жидкостей в пористой среде; некоторые задачи, связанные с проводимостью.

Другие области - для описания возникновения связных структур в случайных средах (кластеров), состоящих из отдельных элементов.

Порог pᶜ перколяции – доля занятых узлов, при которой возникает перколяционный кластер.

Лавинная маршрутизация на основе перколяции для сенсорных сетей

Перколяционная маршрутизация для оптической кластерной сети

Перколяционный поиск в сетях со степенным распределением связности

мобильных сетях, уровень изменений топологии в которых настолько высок, что лавинная доставка данных является единственным способом маршрутизации.

Применение теории перколяции для оценки общей устойчивости и уязвимостей транспортных сетей

Явления макромира - математические модели (бесконечные и непрерывные).

Основная особенность: возможность одновременного (параллельного) изменения состояния всей системы, в то время как каждый участок системы взаимодействует только со своими непосредственными соседями. Это свойство позволяет при моделировании связать события, происходящие на микроуровне, с изменениями макроуровневого моделируемого объекта.

Если состояние системы в произвольный момент времени характеризуется лишь ее предыдущим состоянием и набором правил, регламентирующих ее переход, то она называется автоматом.

Клеточные автоматы широко применяются для моделирования систем, в которых важную роль играет пространственное взаимодействие между элементами.

В физике, например, клеточные автоматы применяются для анализа явлений переноса (теплопроводности, диффузии и вязкости) и моделирования твердого тела.

Классической системой с мелкозернистым параллелизмом является клеточный автомат.

Класс 1: Результатом эволюции начальных условий является быстрый переход к гомогенной стабильности. Любые негомогенные конструкции быстро исчезают.

Класс 2: Результатом эволюции начальных условий является быстрый переход в неизменяемое негомогенное состояние либо возникновение циклической последовательности. Большинство структур начальных условий быстро исчезает, но некоторые остаются. Локальные изменения в начальных условиях оказывают локальный характер на дальнейший ход эволюции системы.

Класс 3: Результатом эволюции почти всех начальных условий являются псевдо-случайные, хаотические последовательности. Любые стабильные структуры, которые возникают почти сразу же уничтожаются окружающим их шумом. Локальные изменения в начальных условиях оказывают неопределяемое влияние на ход эволюции системы.

Класс 4: Результатом эволюции являются структуры, которые взаимодействуют сложным образом с формированием локальных, устойчивых структур. В результате эволюции могут получаться некоторые последовательности Класса 2, описанного выше. Локальные изменения в начальных условиях оказывают неопределяемое влияние на ход эволюции системы. Некоторые клеточные автоматы этого класса обладают свойством универсальности по Тьюрингу.

Такие клеточные автоматы называются стохастическими. В таких системах задается вероятность, что на следующем шаге клетка сменит свой цвет на другой.

Двумерные клеточные автоматы используются для генерации случайных чисел.

Клеточные автоматы предложены для использования в криптосистемах с открытым ключом.

В этом случае односторонняя функция является результатом эволюции конечного клеточного автомата, первоначальное состояние которого сложно найти.

По заданному правилу легко найти результат эволюции клеточного автомата, но очень сложно вычислить его предыдущие состояния.

В настоящее время для сборки устройств из отдельных молекул используют атомно-силовой микроскоп, но это ручная и очень непроизводительная работа. Если же удастся создать молекулярный аппарат типа тьюрмита, он сможет по командам своего "мозга" быстро строить нужные молекулярные структуры.

среди генетически различающихся особей одной и той же популяции выживают и оставляют потомство только наиболее приспособленные к окружающей среде.

Эволюционируют не сами живые организмы, а их хромосомы (концентрированно содержат в себе все свойства организма). Эволюция совершенствует хромосомы

Выживаемость организма определяется свойствами хромосом

Требуется оценка каждой хромосомы, отражающая и свойство приспособляемости

Ген (свойство, знак, детектор) – атомарный элемент генотипа (набор хромосом, характеризует особь)

Хромосома – упорядоченная последовательность генов (цепочка генов)

Локус (лок) – позиция данного гена в хромосоме

Аллель – значение конкретного гена, определяющее свойство организма

Генотип - набор хромосом, характеризует особь

Фенотип – набор внешних свойств, соответствующих данному генотипу. В формализме ГА фенотип – декодированная из хромосом структура, описывающая реальные параметры задачи.

Популяция - конечное множество особей с одинаковым генотипом

А. Имеется некоторая задача, ее решение – новое знание, которое является логическим следствием значений параметров, описывающих данную задачу.

Б. В ГА обрабатываются не сами параметры задачи, а их закодированная форма в виде хромосом.

В. На множестве хромосом определяется целевая функция приспособляемости, оценивающая уровень приспособленности д/каждой хромосомы.

Г. Решение задачи ищется в закодированном виде, обладающих наиболее высокими значениями целевой функции приспособляемости.

Д. При поиске решения используется только целевая функция без ее производных и какой-либо другой дополнительной информации.

Е. Поиск решения происходит не из одной точки (хромосомы), а из некого их множества.

Ё. Порождение нового поколения хромосом осуществляется на основе вероятностных механизмов выбора, а не детерминированности.

Стандартный ГА

Селекция – метод рулетки

Оператор скрещивания – одноточечное

Оператор мутации - для каждой хромосомы определяется вероятность её мутации

переборные методы

локальные методы – метод Ньютона, градиентного спуска, алгоритм Гаусса

генетические алгоритмы

Разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний)

Настройка и обучение искусственной нейронной сети

Модель Изинга - математическая модель статистической физики, предназначенная для описания намагничивания материала.

Каждый спин взаимодействует с внешним полем H:

Спины, ближайшие друг к другу также взаимодействуют

Параллельно выстраиваться спинам "выгодно" - этому соответствует энергия -J, J>0(b)

Антипараллельные спины энергетически невыгодны - на образование каждой такой пары требуется положительная энергия +J

Энергия

Статсумма - сумма по всем микроскопическим состояниям системы:

Пусть H=0 (нет выделенного направления в пространстве - симметричный случай). Энтропия пытается разупорядочить спины, но параллельные состояния более энергетически выгодны.

При малых T перебарывает энергия:

В пограничной точке - точке Кюри Tc - имеет место фазовый переход.

Кабельная теория Ролла - множество предположений и результатов, которые относятся к распространению и взаимодействия электрических сигналов в дендритных деревьях.

Основы кабельной теории - математический анализ затухания сигнала в трансатлантическом телефонном кабеле между Америкой и Англией

два морфологически идентичных дендритных дерева, но с различными электрическими свойствами, могут иметь совершенно разные вычислительные характеристики.