Ростелеком ТВ 

Какая сортировка самая быстрая? Тестируем алгоритмы. Оптимальные алгоритмы. Разработка оптимального алгоритма поиска экспоненциального закона распределения при числе измерений от N=15 до N=log2M

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

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 тура из серии виртуальных фотопанорам

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

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

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

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

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

Специальность 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. Курсовое проектирование. Организация, порядок, оформление расчетно-пояснительной записки и графической части.

Наилучший алгоритм замещения страниц несложно описать, но совершенно невозможно реализовать. В нем все происходит следующим образом. На момент возникновения ошибки отсутствия страницы в памяти находится определенный набор страниц. К некоторым из этих страниц будет осуществляться обращение буквально из следующих команд (эти команды содержатся на странице). К другим страницам обращения может не быть и через 10, 100 или, возможно, даже 1000 команд. Каждая страница может быть помечена количеством команд, которые должны быть выполнены до первого обращения к странице.

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

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

Таким образом появляется возможность сравнить производительность осуществимых алгоритмов с наилучшим из возможных. Если операционная система достигает производительности, скажем, на 1 % хуже, чем у оптимального алгоритма, то усилия, затраченные на поиски более совершенного алгоритма, дадут не более 1 % улучшения.

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

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

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

Появление детерминированного сигнала приводит к изменению модели (2.1) лишь в области индексов (рис. 1) последнего из наблюдаемых кадров:

где - совокупность отсчетов полезного сигнала.

В рассмотренных условиях необходимо найти правило проверки гипотезы Н0 об отсутствии аномалии в области G при альтернативном предположении Н1 о справедливости модели (2.2).

При заданных вероятностных характеристиках компонент моделей (2.1), (2.2) могут быть определены соответствующие условные плотности распределения вероятностей (ПРВ) наблюдений W(Z|Н0) и W(Z|Н1). Поэтому для решения задачи обнаружения следует воспользоваться сравнением с пороговым уровнем отношения правдоподобия (ОП):

(2.3)

Для упрощения вычислений представим условные ПРВ в виде произведений: , где ZG - совокупность наблюдений по области G; Z0 - совокупность всех наблюдений, не принадлежащих области предполагаемого сигнала. Поскольку , ОП (2.3) перепишется в форме:

. (2.4)

Будем аппроксимировать условные ПРВ, входящие в ОП (2.4), гауссовскими распределениями:

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

С учетом моделей наблюдений (2.1), (2.2) нетрудно получить следующие формулы для условных средних , где - оптимальный прогноз значений СП , построенный на основе всех имеющихся наблюдений Z0 , не принадлежащих области сигнала. Пространственные матрицы V0 и V1 оказываются одинаковыми:, где - ковариационная матрица ошибок оптимального прогноза.

После подстановки приведенных соотношений в (2.4), (2.5) и логарифмирования находим следующий алгоритм обнаружения сигнала:

, (2.6)

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

Применяя формулу Фробениуса обращения блочных матриц, можно показать, что статистика приводиться к эквивалентному виду:

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

Еще одна форма записи оптимальной процедуры обнаружения может быть получена в предположении, что полезный сигнал может занимать все имеющиеся кадры изображения, т.е. область G включает все многомерные сетки . Тогда наилучший прогноз , и алгоритм (2.6) принимает вид:

, (2.8)

где ; - ковариационная матрица мешающего изображения.

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

(2.9)

соответствующий предварительному "выбеливанию" последовательности изображений , и последующему весовому суммированию с весами . Во многих случаях такой подход позволяет найти приемлемые для практики квазиоптимальные алгоритмы "выбеливания" . При этом самостоятельное рассмотрение адаптивных рекурсивных фильтров, близких по свойствам к выбеливающим, является важным направлением поиска возможностей относительно простой технической или программной реализации системы обработки последовательностей изображений. Новым качеством, которым обладают алгоритмы (2.7), (2.8) и (2.9) по отношению к (2.6), является разделение трудоемкой операции оптимального прогнозирования или выбеливания, не связанной с формой сигнала, и относительно простого весового суммирования, учитывающего вид полезного сигнала. Это позволяет достаточно просто решать как задачи обнаружения аномалий с неизвестными параметрами положения, так и более сложные проблемы многоальтернативного обнаружения (распознавания) нескольких видов сигналов .

Приведенные результаты позволяют уточнить условия, при которых справедлива предложенная замена условных ПРВ нормальными распределениями. Прежде всего, это широкий класс с гауссовскими моделями (2.1), (2.2). В этих случаях процедуры (2.6), (2.7), (2.9) строго оптимальны. При негауссовских компонентах моделей (2.1), (2.2) достаточным условием оптимальности служит возможность аппроксимации апостериорной ПРВ прогноза нормальным распределением. Заметим, что последнее условие выполняется и во многих прикладных задачах обработки СП со значительными пространственно-временными корреляционными связями и обычно эквивалентно условию высокой апостериорной точности прогнозирования.

Алгоритмы замещения страниц. FIFO. Вторая попытка. Алгоритм LRU.

Алгоритмы замещения страниц. Оптимальный алгоритм. Алгоритм NRU.

Алгоритмы замещения страниц

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

Оптимальный алгоритм

В момент страничного прерывания в памяти находится определенный набор страниц. Каждая страница может быть помечена числом команд, которые будут выполнены до первого обращения к ней. Оптимальный алгоритм удаляет страницу с наибольшей меткой. На практике такой алгоритм невыполним, так как ОС не может знать, когда произойдет обращение к той или иной странице. Осуществить оптимальный алгоритм можно в рамках эксперимента при повторном прогоне. Результаты оптимального алгоритма можно сравнивать с результатами других алгоритмов для определения их эффективности.

NRU (Not Recently Used) алгоритм (не использовавшаяся в последнее время страница)

В табличной записи для каждой страницы присутствуют 2 бита:

Бит R (бит обращения) устанавливается в единицу при каждом обращении к странице. Возможен сброс этого бита, например каждые n тиков таймера, чтобы отличить страницы, к которым давно не было обращения;

Бит M (бит модификации) устанавливается в единицу при изменении страницы. Сигнализирует о том, что при удалении надо страницу записать на диск.

При страничном прерывании, на основании значений битов R и M, ОС делит все страницы на 4 класса. Для удаления случайным образом выбирается страница из низшего класса. Алгоритм легок в реализации и может дать вполне достаточный результат.

FIFO алгоритм

ОС поддерживает список всех страниц, находящихся в памяти. Список отсортирован в порядке появления страниц. При страничном прерывании выгружается страница из начала списка. Алгоритм редко используется в чистом виде.

Алгоритм "вторая попытка"

Является модификацией алгоритма FIFO. При страничном прерывании, у первой страницы в списке изучается бит R. Если он равен единице, страница помещается в конец списка, а бит R сбрасывается, и проверяется следующая страница. Данный алгоритм ищет в списке страницу, к которой не было обращений за последние n тиков таймера. Если происходили ссылки на все страницы, алгоритм превращается в обычный FIFO.

Алгоритм "часы"

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


Алгоритм LRU (Last Recently Used), страница, не использовавшаяся больше всего

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

Для первого метода требуется оснащение компьютера специальным N-разрядным счетчиком, который автоматически возрастает после каждой команды. Кроме этого, каждая запись в таблице страниц должна иметь поле для хранения значения этого счетчика. После каждого обращения к памяти, значение счетчика запоминается в записи в таблице в соответствующей странице, к которой произошло обращение. Если возникает страничное прерывание, менеджер памяти проверяет значение счетчиков во всей таблице и ищет наименьшее. Эта страница и является неиспользуемой дольше всего.

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