Нижняя граница сложности класса алгоритмов определяется не един­ственным образом. Например, f (n ) = 0 всегда является нижней гра­ницей, равно как и любая отрицательная функция. Чем больше най­денная нижняя граница, тем она нетривиальнее и ценнее. Сигналом о том, что мы не сможем построить нижнюю границу большую, чем

ПО Глава 4. Нижняя граница сложности. Оптимальные алгоритмы

уже имеющаяся у нас нижняя граница f (n ), может служить, напри­мер, наличие A е .s4, для которого T A (n) = f(n). С такой ситуацией мы сталкиваемся в предыдущем параграфе в примерах 14.1 и 14.3. Извест­ный нам алгоритм поиска наименьшего элемента и алгоритм бинар­ного поиска места элемента в упорядоченном массиве имеет каждый сложность, совпадающую с найденной нижней границей. Эти алго­ритмы являются оптимальными в смысле следующего определения.

Определение 15.1. Пусть .s4 - класс алгоритмов решения неко­торой задачи. Пусть принято соглашение о том, в чем измеряются затраты алгоритмов и что считается размером входа, и пусть n -обо­значение размера входа. Алгоритм A е .s4 называется оптимальным в j4, если T A (n) является нижней границей сложности алгоритмов из j4.

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

Предложение 15.1. Функция f (n ) = Г 2 n 1 - 2 является нижней границей сложности алгоритмов одновременного выбора наибольшего и наименьшего элементов массива длины n c помощью сравнений.

Доказательство. Каждый этап выполнения произвольного алго­ритма V, основанного на сравнениях и предназначенного для поиска наибольшего и наименьшего элементов массива, может быть охарак­теризован четверкой (A, B, C, D) подмножеств множества исходных элементов {x г, x 2 , ■ ■ ■, x n }, где

A состоит из всех тех элементов, которые вообще не сравнива­лись;

B состоит из всех тех элементов, которые участвовали в некоторых сравнениях и всегда оказывались большими;

C состоит из всех тех элементов, которые участвовали в некото­рых сравнениях и всегда оказывались меньшими;

D состоит из всех тех элементов, которые участвовали в некото­рых сравнениях, иногда оказываясь большими, а иногда - мень­шими.

Пусть a, b,c,d - количества элементов множеств A, B, C, D соответ­ственно. Исходная ситуация характеризуется равенствами a = n, b = = c = d = 0. После завершения алгоритма должны выполняться равен-

§ 15 . Оптимальные алгоритмы

ства а = 0, b = c = 1, d = n-2. После первого сравнения на протяже­нии всего выполнения алгоритма постоянно будут иметь место нера­венства Ъ^1,с^1.

Все сравнения, совершаемые при выполнении алгоритма V, мож­но разбить на типы, обозначаемые AA,AB,AC,AD, BB,BC,BD,CC, CD,DD, например: сравнение принадлежит типу АВ , если один из сравниваемых элементов берется из А , другой-из В , и т. д. Исходя из этого, можно выписать все возможные изменения четверки (а, Ь , с , d ) под действием сравнений разных типов.

На собеседованиях часто спрашивают, какая сортировка самая быстрая. Вопрос с подвохом. Объясняем, почему, и ищем оптимальный вариант.

В ответ вы должны спросить: «А для какого случая выбирается оптимальная по времени сортировка?» И лишь тогда, когда будут озвучены условия, можно смело перебирать имеющиеся варианты.

Существуют:

• алгоритмы сортировки O(n 2) вроде сортировки вставками, пузырьком и выбором, которые используются в особых случаях;
• быстрая сортировка (общего назначения): в среднем O(n log n) обменов, но худшее время – O(n 2) , если массив уже отсортирован, или элементы равны;
• алгоритмы O(n log n) , такие как сортировка слиянием и кучей (пирамидальная сортировка), которые также являются хорошими алгоритмами сортировки общего назначения;
• O(n) или линейные алгоритмы сортировки (выбор, выбор с обменом, выбор с подсчетом) для списков целых чисел, которые могут быть подходящими в зависимости от характера целых чисел в ваших списках.

Если все, что вы знаете, – это отношение общего порядка между элементами, то оптимальные алгоритмы будут иметь сложность О(n log n) . Для линейных алгоритмов нужна дополнительная информация о структуре элементов.

Оптимальность алгоритма тесно зависит от типа списков/массивов, которые вы собираетесь сортировать, и даже от модели ЭВМ. Чем больше информации в вашем распоряжении, тем более точным будет выбор. При очень слабых предположениях о факторах оптимальной сложностью худшего случая может быть О(n!) .

Данный ответ касается только сложностей. Фактическое время выполнения алгоритмов зависит от огромного количества факторов.

Тестирование

Итак, какая же сортировка самая быстрая?

Визуализация

Неплохая визуализация сортировок продемонстрирована в этом видео:

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

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего профессионального образования "Воронежский государственный технический университет"

Радиотехнический факультет

Кафедра радиотехники

Специальность 210302 "Радиотехника"

Оптимизация алгоритмов поиска

Выполнил студент гр. РТ-041 Д.С. Чёткин

Проверил доцент кафедры В.П. Литвиненко

Введение. 4

1. Разработка оптимального дихотомического алгоритма поиска при равновероятном распределении вероятностей и числе событий М=16. 5

2. Разработка оптимального алгоритма поиска для экспоненциального закона распределения вероятностей при М=16. 7

3. Разработка оптимального алгоритма поиска экспоненциального закона распределения при числе измерений от N=15 до N=log2M.. 9

4. Разработка оптимального алгоритма поиска для 9-го варианта распределения при числе измерений от N=1 до 15. 12

Заключение. 19

Список литературы.. 20

Введение

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

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

Множество Х с соответствующим законом распределения вероятностей разбивается на два подмножества и (верхний индекс - номер разбиения). Двоичный измеритель проводит двоичное измерение, выявляя, в каком подмножестве находится реасобытие (его след). Затем подмножество, в котором обнаружено реасобытие (на рис.2.1. это ), вновь разбивается на два подмножества и и выявляется след реасобытия в одном из них. Процедура заканчивается, когда в выделенном подмножестве оказывается одно событие. Поиск может быть последовательным и дихотомическим. В первом алгоритме () производится последовательный перебор состояний от первого до последнего, пока не встретится реасобытие.

Второй алгоритм поиска () предполагает разделение всего множества состояний пополам, проверку наличия реасобытия в каждой из этих частей, затем разделение выбранной половины множества X на две равные части с проверкой наличия в них реасобытия и так далее. Поиск заканчивается, когда в выделенном подмножестве оказывается одно событие.

Существует несколько способов минимизации двоичных поисковых процедур. Примерами могут служить методы Циммермана-Хафмена и Шеннона-Фоно. Оптимизировать алгоритм можно по различным параметрам с учетом стоимости измерения и без. В данной лабораторной работе исследовали оптимизацию дихотомического алгоритма поиска по наименьшей величине средней скрытности.

1. Разработка оптимального дихотомического алгоритма поиска при равновероятном распределении вероятностей и числе событий М=16

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

В данном случае наиболее оптимальным алгоритмом поиска является алгоритм разработанный по принципу Шеннона-Фано. Данный метод предполагает исходное множество элементов с заданным распределением разбить на два подмножества с номерами 0 и 1 так, чтобы вероятности попадания в них были максимальны близки (в идеале пополам). Затем каждое из полученных подмножеств отдельно разбивается на два подмножества с тем же условием и номерами с 00,01,10,11. Разбиение заканчивается когда все элементы подмножества будут иметь только по одному элементу.

В результате разработан оптимальный алгоритм поиска для равновероятного закона распределения вероятностей.

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

(1)

В результате для данного случая:

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

Разработка оптимального алгоритма поиска для экспоненциального закона распределения вероятностей при М=16

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

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

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

Доказательство использования последовательного алгоритма поиска. Для этого используется метод Циммермана-Хаффмена. Данный метод оптимизации состоит из двух этапов: «Заготовительные операции» и «Считывание». Более подробно про это говорится в книге .

Так как показатель степени больше 1, а это удовлетворяет неравенству:

Где λ – показатель степени распределения вероятностей, равный 1, то для данного случая оптимальным является последовательный алгоритм поиска.

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

Разработка оптимального алгоритма поиска экспоненциального закона распределения при числе измерений от N=15 до N=log2M

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

При N=15 из предыдущего пункта оптимальным является последовательный алгоритм поиска и для него значение среднее значение двоичных измерений определяется так же как и для потенциальной скрытности. Значение Rcpпредставлено в таблице 1.

Таблица 1 – Зависимость среднего числа измерений

от числа измерений при оптимальных алгоритмах поиска

Проведем расчет потенциальной скрытности для каждого случая по формуле 1:

При числе измерений равному 3-м, разработать алгоритм поиска невозможно, так это не удовлетворяет условию реализуемости поиска, а именно:

В результате построен график зависимости среднего числа измерений от числа измерений представленный на рисунке 8.

Рисунок 8 – Зависимость среднего числа измерений от числа измерений для экспоненциального закона распределения вероятности

4. Разработка оптимального алгоритма поиска для 9-го варианта распределения при числе измерений от N=1 до 15

Для своего варианта распределения вероятностей при числе событий разработайте оптимальный алгоритм поиска, постройте дерево поиска, объясните его форму, чем она обусловлена?

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

Таблица 2 – Зависимость среднего числа измерений,

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

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
R	4	3.775	4.325	4.725	5.1625	5.375	5.5	5.65	5.7	5.7625	5.8	5.8
Pнеоп	0.55	0.7625	0.875	0	0	0	0	0	0	0	0	0	0	0	0
Sост	0.801	0.785	0.791	0.802	0.814	0.826	0.837	0.848	0.858	0.868	0.877	0.885	0.893	0.901

В данной таблице Sост считалось при доверительной вероятности 0.9. «PrintScreen» программы «Poisk» при различных значениях числа измерений представлен на рисунках 8-11.

При числе измерений меньше 4-х появляется вероятность неполного решения, связанная с тем, что невозможно проверить все события. В результате приходится проверять не все, оптимальным вариантом будет проверка наиболее вероятных событий. «PrintScreen» программы «Poisk» при числе измерения меньше 3-х представлена на рисунке 12.

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

Рисунок 13 – Зависимость среднего числа измерений от числа измерений для 9-го закона распределения вероятности

Рисунок 14 – Зависимость вероятности неполного решения от числа измерений для 9-го закона распределения вероятности

(3)

(4)

Доверительную вероятность будем менять в пределах 0.7÷0.9. В результате получен график зависимости остаточной скрытности от числа измерений, который представлен на рисунке 15.

Ност(Pдов) Pдов=0.9

Рисунок 15 – Зависимость остаточной скрытости при значениях доверительной вероятности 0.7÷0.9

Из представленного выше графика можно сделать вывод, что Pдов следует выбирать близким к единице, это приведет к уменьшению остаточной скрытности, однако не всегда такое возможно.

Рисунок 16 – Зависимость остаточной скрытости при значениях числа измерений 4,8,16

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

Заключение

В данной работе были проведены исследования оптимизации дихотомического алгоритма поиска с помощью программы Poick. Проведено сравнение с последовательным алгоритмом. Исследован вид КСН при равномерном, экспоненциальном и заданном по варианту распределении событий. Наработаны навыки в обращении с программой Poick.

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

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

Правильность работы программы Poisk потверждена с помощью расчётов проведённых в пакете программ Matcard 2001.

Список литературы

1. Основы теории скрытности: учебное пособие для студентов специальности 200700 «Радиотехника» дневной формы обучения / Воронежский государственный технический университет; Сост.З.М. Каневский, В.П. Литвиненко, Г.В. Макаров, Д.А. Максимов; под редакцией З.М. Каневского. Воронеж, 2006. 202с.

2. Методические указания к лабораторным работам «Исследование алгоритмов поиска» по дисциплине «Основы теории скрытности» для студентов специальности 200700 «Радиотехника» дневной форм7 обучения / Воронежский государственный технический университет; сост.З.М. Каневский, В.П. Литвиненко. Воронеж, 2007.54с.

3. СТП ВГТУ 005-2007. Курсовое проектирование. Организация, порядок, оформление расчетно-пояснительной записки и графической части.

Предположим, что все искажения в канале строго детерминированы и случайным является только гауссовский аддитивный шум n(t), который вначале полагаем белым, со спектральной плотностью N 0 . Это значит, что при передаче сигнала u i (t) (символа b i (i = 0,1,...,m-1) приходящий сигнал можно описать моделью (3.38):

z(t) = s i (t) + n(t), (0≤t≤T), (6.17)

где все s i (t) = ku i (t-τ) (i = 0, 1,..., m-1) известны. Неизвестны лишь реализация помехи и индекс i действительно переданного сигнала, который и должна определить решающая схема.

Будем также считать, что все s i (t) являются финитными сигналами, длительность которых Т. Это имеет место, если передаваемые сигналы u i (t) финитны и имеют одинаковую длительность (система синхронная), а в канале нет ни многолучевого распространения, ни линейных искажений, вызывающих увеличение длительности сигнала (либо они скорректированы).

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

Определим в этих условиях алгоритм работы оптимального (т. е. основанного на правиле максимального правдоподобия) демодулятора, анализирующего сигнал на тактовом интервале 0-Т. Для этого необходимо найти отношения правдоподобия для всех m возможных сигналов относительно нулевой гипотезы (s(t)=0; z(t) = n(t)).

Задача затрудняется тем, что ширина спектра сигнала бесконечна (поскольку он финитный), а поэтому пространство сигналов бесконечномерное L 2 (Т). Для таких сигналов (или бесконечномерных векторов), как отмечалось, не существует плотности вероятностей. Однако существуют "-мерные плотности вероятностей для любых n сечений сигнала (см. § 2.1).

Заменим вначале белый шум квазибелым, имеющим ту же одностороннюю спектральную плотность мощности N 0 , но только в некоторой полосе частот F = n/2T, где n>>1. Рассмотрим вначале дополнительную гипотезу, т. е. будем считать что Z(t) - шум. Возьмем на тактовом интервале n равноотстоящих сечений через Δt = 1/2F = T/n. Отсчеты Z 1 ,...., Z n в этих сечениях для квазибелого гауссовского шума независимы в соответствии с (2.49). Поэтому n-мерная плотность вероятностей для взятых отсчетов

где σ 2 = N 0 F - дисперсия (мощность) квазибелого шума.

При гипотезе, что передавался символ b i , согласно (6.17) n(t) = z(t) - s i (t). Следовательно, условная n-мерная плотность вероятности сечений Z(t) определится такой же формулой, как и (6.18), если z(t k) заменить разностью z(t k)-s i (t k), представляющей при этой гипотезе шум:

Отношение правдоподобия для сигнала s i (относительно дополнительной гипотезы), вычисленное для n сечений:

Заменим дисперсию σ 2 ее выражением: σ 2 = N 0 F = N 0 /(2Δt). Тогда

По правилу максимума правдоподобия в случае квазибелого шума решающая схема должна выбирать значение i, обеспечивающее максимум Λ i [n] . Вместо максимума Λ i можно отыскивать максимум его логарифма:

Второй член в (6.22) не зависит от t и его можно при сравнении гипотез не учитывать. Тогда правило решения о том, что передавался символ b i , согласно (6.10) можно выразить системой неравенств

Вернемся теперь к исходной задаче для белого шума. Для этого будем расширять полосу F, тогда число сечений п стремится к бесконечности, а Δt - к нулю. Суммы в (6.22) обратятся в интегралы, и травило решения определится так:

Выражение (6.24) определяет те операции (алгоритм работы), которые должен совершать оптимальный приемник над входным колебанием z(t).

На рис. 6.2 для m = 2 показана структурная схема приемного устройства, работающего в соответствии с алгоритмом (6.24).

Здесь "-" - вычитающие устройства; Γ 0 , Γ 1 - генераторы опорных сигналов s 0 (t), s 1 (t); "KB" - квадраторы; ∫ - интеграторы; РУ - решающее устройство, определяющее в моменты времени, кратные Т (при замыкании ключей), номер ветви с минимальным сигналом.

При m>2 в схеме рис. 6.2 и других нижеприведенных схемах растет соответственно число ветвей обработки сигнала, попадающих на РУ.

В пространстве Гильберта

определяет норму разности векторов z и s или расстояние между ними * . Поэтому алгоритм (6.24) можно записать в виде

||z - s i ||

и придать ему простую геометрическую интерпретацию: оптимальный демодулятор должен регистрировать тот из сигналов s i (t) (соответствующий символу b i), который "ближе" к принятому колебанию z(t). В качестве примера на рис. 6.3 показано оптимальное разбиение двумерного пространства принимаемых сигналов z(t) при передаче сигналов s 1 (t) и s 0 (t). Области принятия решения в пользу символов 0 или 1 расположены по обе стороны от прямой 0-0, перпендикулярной отрезку, соединяющему точки сигналов и делящих его пополам.

Наличие в схеме рис. 6.2 квадраторов, призванных обеспечить квадратичное преобразование мгновенных значений входных сигналов во всем их динамическом диапазоне, часто затрудняет ее реализацию. Поэтому на основе (6.24) получим эквивалентный алгоритм приема, не требующий устройств возведения в квадрат.

Раскрыв скобки под знаком интеграла и сократив в обеих частях неравенств (6.24) слагаемое

приходим к алгоритму приема:

где E j - энергия ожидаемого сигнала s j (t) :

Для двоичной системы алгоритм (6.25) сводится к проверке одного неравенства

Устройство, непосредственно вычисляющее скалярное произведение

называют активным фильтром, или коррелятором, поэтому приемник, реализующий алгоритм (6.25), называют корреляционным.

* (Для n-мерного пространства Евклида эта норма равна )

На рис. 6.4 показана структурная схема приемного устройства, работающего в соответствии с (6.27). Здесь блоки × - перемножители; Γ 0 , Γ 1 - генераторы опорных сигналов s 0 (t) s 1 (t); ∫ - интеграторы; "-" - вычитающие устройства; РУ - решающее устройство, определяющее в моменты времени, кратные Т (при замыкании ключа), i = 0, 1 - номер ветви с максимальным сигналом.

Если сигналы u i (t) выбраны таким образом, что все их реализации (а следовательно, и все реализации s i (t) имеют одинаковые энергии (E i = const), алгоритм приема (6.25) (и соответственно его реализация) упрощается (отпадает необходимость в вычитающих устройствах) и принимает вид

Из (6.29) видно, что правило решения не изменится, если сигнал z(t), поступающий на вход демодулятора, умножить на любое число. Поэтому система, в которой все реализации сигнала имеют равную энергию, отличается тем, что оптимальный алгоритм приема в ней не требует знания "масштаба" приходящего сигнала или, другими словами, знания коэффициента передачи k канала. Эта важная особенность обусловила широкое распространение систем сигналов с равной энергией, которые обычно называют системами с активной паузой. Это особенно важно для каналов с замираниями, в которых коэффициент передачи флуктуирует (см. §6.7).

Заметим, что для двоичной системы неравенство (6.27) можно представить в более простом виде:

где s Δ (0 = s 1 (t) - s 0 (t) - разностный сигнал; λ = 0,5(E 1 -Е 0) - пороговый уровень. Для системы с активной паузой Х=0, что значительно облегчает реализацию оптимальной схемы.

При выполнении неравенства (6.30) регистрируется символ 1, в противном случае - 0. Для реализации (6.30) в схеме рис. 6.4 требуется лишь одна ветвь.

На рис. 6.5,а показана схема, реализующая алгоритм (6.30) для двоичной системы передачи однополярными импульсами (с пассивной паузой): s 1 (t) = a, s 0 (t) = 0. При этих сигналах s Δ (t) = s 1 (t) = a, Е 1 = а 2 Т, E 0 = 0, λ = а 2 T/2 и (6.30) примет следующий, вид:

Рассмотренную систему двоичных сигналов используют в простейших устройствах проводной связи. В радиоканалах, а также в современных кабельных каналах применяют высокочастотные сигналы. Наиболее простыми двоичными системами с гармоническими сигналами являются системы с амплитудной (AM), фазовой (ФМ) и частотной (ЧМ) манипуляцией.

В двоичной AM s 1 (t) = acos(ω 0 t + φ), s 0 (t) = 0. Все входящие сюда постоянные (а, ω 0 , φ) в этом параграфе полагаем известными. Поскольку здесь s Δ (t) = s 1 (t), Е 1 = а 2 Т/2 и E 0 = 0, правило (6.30) запишется так:

Оно реализуется схемой рис. 6.5,6, которая отличается от рис. 6.5,a блоком перемножения приходящего сигнала с опорным сигналом cos(ω 0 t + φ). Пороговый уровень λ̇ в этом случае равен aT/(4RC).

При двоичной ФМ системе s 0 (t) = a cos(tω 0 + φ), s 0 (t) = а cos (tω 0 + φ + π) = -s 1 (t). Это - система с активной паузой, и поэтому в (6.30) λ = 0. Легко убедиться, что правило решения сводится при этом к следующему:

и реализуется той же схемой рис. 6.5,6 при λ̇ = 0. В этом случае РУ играет роль дискриминатора полярностей.

Рис. 6.6. Оптимальный демодулятор с обеляющим фильтром при гауссовском "окрашенном" шуме

Рассмотрим вкратце случай, когда гауссовский шум в канале не белый и не квазибелый, а "окрашенный", т. е. имеет неравномерную плотность мощности G(f) в полосе спектра сигнала. Пропустим приходящую на вход демодулятора сумму сигнала и шума через фильтр с передаточной функцией k(i2πf), такой чтобы в полосе спектра сигнала произведение G(f) |k(i2πf)| 2 было постоянной величиной N 0 . Из всех возможных фильтров с k(i2πf), удовлетворяющих этому условию и различающихся только фазо-частотной характеристикой, можно выбрать минимально фазовый, который является обратимым. Очевидно, что на выходе фильтра шум окажется квазибелым: G вых (f)=N 0 . Поэтому такой фильтр называется обеляющим.

Сигнал s i (t) после прохождения через обеляющий фильтр превратится в некоторый другой сигнал, который обозначим s" i (t). Вид его можно определить, зная s i (t) и k(i2πf). Если теперь подать колебания с выхода обеляющего фильтра на демодулятор, являющийся оптимальным для приема сигналов s" i (t) (i = 0, 1, ..., m-1), то получим схему рис. 6.6, которая, очевидно, является оптимальной для сигналов s i (t) при окрашенном шуме.

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

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

Оценка сложности алгоритмов

6. Оптимизация алгоритмов

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

Во-первых, сложно сформулировать критерий оптимизации, имеющий одновременно и бесспорное практическое значение и однозначно определенный в математическом плане. Например, можно поставить задачу минимизации числа команд машины Тьюринга - критерий, хорошо определенный математически; но совсем неясно его практическое значение, поскольку вряд ли реальная программа на реальном компьютере будет моделировать машину Тьюринга. Можно поставить задачу минимизации времени выполнения программы на реальной машине - ясный с практической точки зрения критерий. Однако невозможно будет решить задачу оптимизации математическими методами, так как время выполнения зависит (иногда значительно) от архитектуры ЭВМ, а архитектуру современных компьютеров не опишешь небольшим числом параметров. Важно также, что программа, работающая быстрее других на одном компьютере, может оказаться не самой быстрой на другом. Существуют даже специальные программы с общим названием benchmark, предназначенные для оценки архитектур.

Во-вторых, не совсем ясно, что такое сложность задачи. Ее можно было бы определить как минимальную из сложностей алгоритмов, решающих эту задачу. Но существует ли алгоритм минимальной сложности (как убедиться, что найденный алгоритм действительно минимальный или, напротив, не минимальный)? Есть ли к чему стремиться? И насколько труден поиск этого минимума? Эти вопросы связаны с нижней оценкой сложности алгоритмов (а не верхней, как в предыдущих шагах) (5, стр. 89-92).

Можно ли для рассматриваемой задачи доказать, что никакой решающий ее алгоритм не может быть проще этой нижней оценки? Возьмем известную задачу перемножения квадратных матриц. Приведен алгоритм сложности Т(n) = 3n3 + n2. (8, стр. 199-203) Вероятно, это не лучший алгоритм, но какова оценка снизу? Результирующая матрица имеет n2 элементов. Для вычисления любого элемента нужна хотя бы одна операция однопроцессорной машины - два элемента за одну операцию найти нельзя. Для минимального алгоритма мы получаем неравенства n2 <= T, min(n) <= 3n3+n2 . Вряд ли n2 - хорошая нижняя оценка, но уже известно, что n3 нижней оценкой не является, так как найдены более быстрые алгоритмы (в частности, алгоритм Штрассена). (8, стр. 211)

Существует несколько самостоятельных аспектов оптимизации программ, из которых выделим два:

Оптимизация, связанная с выбором метода построения алгоритма;

Оптимизация, связанная с выбором методов представления данных в программе.

Первый вид оптимизации имеет глобальный характер и ведет к уменьшению порядка функции сложности - например, замена алгоритма с Т(V) = O(FS) на алгоритм с T(V) = O(V4). Он зависит от того, как задача разбивается на подзадачи, насколько это разбиение свойственно самой задаче или является только искусственным приемом. Общим руководящим подходом здесь может быть последовательность действий, обратная анализу алгоритмов. При анализе по рекурсивному алгоритму строится уравнение, которое затем решается. При оптимизации реализуется цепочка:

Формула, задающая желаемую сложность ->

Соответствующее уравнение (одно из возможных) ->

Метод разбиения задачи на подзадачи.

Второй вид оптимизации, не меняя структуры программы в целом, ведет к экономии памяти и/или упрощению работы со структурами данных, повышению эффективности вспомогательных процедур, обеспечивающих "интерфейс" между прикладным уровнем (на котором мыслим в терминах высокоуровневых объектов - графов, матриц, текстов и т. д.) и машинным уровнем, поддерживающим простейшие типы данных (числа, символы, указатели). Результатом этого обычно является уменьшение коэффициентов при некоторых слагаемых в функции сложности (при удачной оптимизации - при наиболее значимом слагаемом), но порядок функции сложности остается тем же. (7, стр. 204)

Оба вида оптимизации дополняют друг друга и могут применяться совместно.

Алгоритмы решения задач выбора. Алгоритм отжига

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

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

Одной из ключевых проблем при проектировании АСУ ТП является проблема оптимизации, от обоснованной постановки и успешного решения которой во многом зависит эффективность АСУ ТП...

Компьютерное моделирование беспроводных AD-HOC сетей для целей расчета времени связи мобильных абонентов

Оптимизация - это процесс изменения программы по определенным критериям с целью повышения ее качества при сохранении смысла исходной программы. Для сокращения объёма кода программы он разбивается на части - подпрограммы...

Моделирование и оптимизация автомобильных дорог

Введем следующие обозначения: Xi - остаточные средства на начало iго этапа; Uj - количество средств, которые решено выделить i - предприятию; Пi - прибыль, получаемая этим предприятием...

Моделирование системы автоматического регулирования программным и имитационным методом

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

Оптимизация плана производства и поставок с использованием системы планирования IBM ILOG Plant PowerOps

IBM ILOG Plant PowerOps состоит из четырех модулей: планирования производства, определения размера партий, составления детальных графиков и закрепления за спросом. Каждый из модулей решает специфические задачи в процессе оптимизации...

Особенности работы в программном пакете MicroCAP-7

Параметрическая оптимизация выполняется в программе МС7 методом Пауэлла (Powell) в любом из видов анализа: анализ переходных процессов, малосигнальный АС-анализ и расчет характеристик на постоянном токе DC...

Особенности создания текстового контента для сайта ННГУ им. Н.И. Лобачевского

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

Проектирование и моделирование электрических схем в графической системе AutoCAD и пакете программ OrCAD 9.2

электрический цепь кинематический магнитофон Далее, мы добавляем параметры оптимизации в схему, устанавливая текущие «Current Value», начальные «Initial Value» значения компонентов, а так же допуск «Tolerance»...

Разработка конструкции двухместного компьютерного стола

Кроме возможности 3d-конструирования изделий, создания чертежей и спецификаций на детали, а также расчета материалов, необходимых для изготовления изделия, “bCAD Мебельщик” позволяет производить экономичный...

Разработка модели агентства недвижимости в соответствии со стандартом IDEF0

Данная модель относится к типу «to be», то есть модель построена по принципу «так как должно быть». В процессе создания модели мною были исправлены некоторые недостатки...

Разработка приложения для выбора покупки пары станков

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

Разработка программы "Определение оптимального срока замены оборудования"

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

Системный анализ информационной системы управления персоналом на предприятии

Создание виртуального 3D тура из серии виртуальных фотопанорам

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