Помехоустойчивые и линейные коды Код ы Хэмминга БЧХ Способы декодирования Математическая модель Моделирование Сложные системы Метод суперпозиции Метод Неймана Уравнения Колмогорова Вычисление интегралов Варианты курсовых работ Цифровые сети для передачи речи и данных
Что такое NP-трудная задача, и приведен ряд алгоритмов для решения NP-трудных задач. Мы пробежим путь от примитивных до довольно хитрых идей для решения двух задач (выполнимость формул и раскрашиваемость графа в три цвета).

Вычисление интегралов методом Монте-Карло

Пример. Пусть надо вычислить интеграл

  где k>0.

Выберем плотность p(x)=ke-kx и функцию f1=k-1f(x). Если xi- значение случайной величины x с плотностью p(x), то оценка интеграла I

,

случайная величина x может быть смоделирована по плотности p(x) по формуле xi= (-1/k)lngi , тогда

, где g1, g2, …, gN- независимые сл. числа.

Алгоритм вычисления интеграла может быть задан так:

1) формула для оценки I,

2) формула для получения случайной величины x.

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

Трудоемкостью алгоритма Монте-Карло назовем произведение t*Dx дисперсии усредняемой случайной величины x на время t расчета одного значения x. Тогда ясно, что из двух алгоритмов более эффективен менее трудоемкий.

Важнейшие способы построения хороших оценок

(способы уменьшения дисперсии)

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

Информатика Помехоустойчивые коды и их основные параметры Цифровые сети для передачи речи и данных
История информатики начиналась с четко определенных задач. Для каждой постановки можно было явно убедиться, решает ли предложенный алгоритм данную задачу. Однако в последние годы все большее внимание уделяется так называемым задачам искусственного интеллекта