Реферат: Эмпирический алгоритм решения задачи сегментации. Степень сложности алгоритма решения

Эмпирический алгоритм решения задачасегментации. Степень сложности алгоритма решения

Рамазанов Е.Т.

            За последнее время  в области компьютерных технологии большеевнимание исследователей занимает не инженерные решении различных устройств, а самипрограммы. Иными словами именно программы выступают в качестве основныхобъектов исследования. Эта направление исследований не является новым, еще всоветское время благодаря фундаментальным работам Ляпунова А. А., Ю.Н. Янова  С.С. Лаврова давши основутакой области знания как теоретическое программирование, уделялось вниманиеисследованию программ. Было определено ряд проблем и задач теоретическогопрограммирования, которые в связи с повышением интереса к исследованию программнаходят новое свое рождение и становятся одним из многих актуальных проблемсовременной науки. Одним из таких задач является задача сегментации. Задачасегментации связана с проблемами оценки производительности и управлениемвычислительными процессами ЭВМ с виртуальной памятью. Под задачей сегментации обычно принято пониматьзадачу разбиение последовательной программы на взаимозависимые по управлению иинформационно части (блоки, секции, сегменты и. т.д) в соответствии с той илииной целью[1. 9-11]. В случае рассмотренном в данной статье задача сегментацииопределяется  как задача разбиениепрограммы на части по сегментам или страницам виртуальной памяти.

          Проблема заключается в том, что приразмещении программы  по сегментамвиртуальной памяти каждый элемент программы получает свой адрес. Операционнаясистема выделяет каждой программе некоторый участок основной памяти. Причемобъем выделенной памяти меньше чем сама программа. По мере выполнения программыв памяти находятся копии страниц программ. Обмен между вспомогательной памятьюи основной  осуществляется целымистраницами, во время обмена центральный процессор переключается на выполнениекоманд  другого сегмента, если во времявыполнения программы происходит ссылка на сегмент программы, котораяотсутствует в основной памяти, то происходит страничное прерывание. Выполнениепрограммы прерывается. Из-за программ, в которых происходит страничныепрерывание, снижается производительность самой операционной системы. Существуютразличные алгоритмы разрешение данной проблемы[1,16-20]. Такие алгоритмыобеспечивают как можно меньшее числостраничных отказов. Интересен теоретическии подход решение данной проблемы какзадачи сегментации. Известны различные подходы решения задачи сегментации однимиз которых является графовый подход.

          Идея графового подходазаключается в определении  графа.Вершинам графа соответствует блоки программ, ребрам- передачи управления междублоками программы. Вес вершины определяет размер блока программы.а вес ребрачисло передач управления между блоками. Задача состоит в разбиении  вершин на множества так чтобы сумммарный весвершин попавших в одно множество не превосходил веса множества т.е. страницы. Асуммарный вес ребер между разбитыми  множествам вершин был бы минимален. На основе  графового определение задачи сегментации былапостроена модель решения задачи сегментации дающию возможность испольоватьметоды кластерного анализа. Принципиальную возможность применение кластерногоалгоритма и условия при котором алгоритм находил бы найболее точное решение  обосновал в своем фундаментальном трудепрофессора Каз НУим. аль-Фараби Дюсембаев А.Е. [1]. Следуя идеям Журавлева Ю.И.,операторный алгоритм решения задачи имеет степень сложности, зависящий отисходных данных  задачи.   По определению степень сложностиимеет вид

<img src="/cache/referats/24060/image002.gif" v:shapes="_x0000_i1025"> ;   где    <img src="/cache/referats/24060/image004.gif" v:shapes="_x0000_i1026"> максимальное значениематрицы оценок. <img src="/cache/referats/24060/image006.gif" v:shapes="_x0000_i1027"><img src="/cache/referats/24060/image008.gif" v:shapes="_x0000_i1028"><img src="/cache/referats/24060/image010.gif" v:shapes="_x0000_i1029"> [1]причем обладаютсвойствам <img src="/cache/referats/24060/image012.gif" v:shapes="_x0000_i1030"> степеньсложности определяет что, для заданной задачи существует различные информационные матрицы, т.е. по Журавлевусуществует различные корректные алгоритмы решения. Определение степенисложности алгоритма приводит к решению вопроса точности алгоритма. Одним изпутей разрешения токого вопроса состоит в определении условии при которыхалгоритм был бы заданной степени сложности. Естественно возникает вопросы,можно ли понизить степень и как выбор степени влияет на решающее правило. Степеньсложности операторного алгоритма для задачи сегментацииописанного в работе[1]можно понизить до второго порядка если задатьпороговые значения <img src="/cache/referats/24060/image010.gif" v:shapes="_x0000_i1031"> зависимостью имеющиивид :

<img src="/cache/referats/24060/image015.gif" v:shapes="_x0000_i1032">   

Доказательство: представим задачу на нахождение экстремума функции. Так какстепен сложности <img src="/cache/referats/24060/image017.gif" v:shapes="_x0000_i1033"><img src="/cache/referats/24060/image019.gif" v:shapes="_x0000_i1034">  <img src="/cache/referats/24060/image021.gif" v:shapes="_x0000_i1035">  будет <img src="/cache/referats/24060/image023.gif" v:shapes="_x0000_i1036">  Это будет справедливои для соотношения <img src="/cache/referats/24060/image025.gif" v:shapes="_x0000_i1037"> так как <img src="/cache/referats/24060/image027.gif" v:shapes="_x0000_i1038">нно:  

<img src="/cache/referats/24060/image029.gif" v:shapes="_x0000_i1039">           

Построим задачу поиска экстремума функции <img src="/cache/referats/24060/image031.gif" v:shapes="_x0000_i1040">   <img src="/cache/referats/24060/image033.gif" v:shapes="_x0000_i1041"> 

Предполагается, что значение функции <img src="/cache/referats/24060/image035.gif" v:shapes="_x0000_i1042"> доставляющие локальныйэкстреммум этой функции будет точкой экстремума и функции <img src="/cache/referats/24060/image037.gif" v:shapes="_x0000_i1043"><img src="/cache/referats/24060/image010.gif" v:shapes="_x0000_i1044"> выполняется условияможеранты. следуя правилам высшей матиматики заключим что, решение поставленнойзадачи понижает степень до второго порядка.

 Представим эмпирический алгоритм решениезадачи сегментации использующий принцип оптимальности Беллмана. Пусть задана <img src="/cache/referats/24060/image039.gif" v:shapes="_x0000_i1045"> блоков. И размерызаданных блоков <img src="/cache/referats/24060/image041.gif" v:shapes="_x0000_i1046">  соответственно.Память выделенной операционной системой разбита на <img src="/cache/referats/24060/image006.gif" v:shapes="_x0000_i1047"> сегментов. Допустим, что число блоков программы больше числа сегментов <img src="/cache/referats/24060/image044.gif" v:shapes="_x0000_i1048">  <img src="/cache/referats/24060/image046.gif" v:shapes="_x0000_i1049"> где <img src="/cache/referats/24060/image048.gif" v:shapes="_x0000_i1050"><img src="/cache/referats/24060/image050.gif" v:shapes="_x0000_i1051"><img src="/cache/referats/24060/image052.gif" v:shapes="_x0000_i1052"> число передач междублоками <img src="/cache/referats/24060/image054.gif" v:shapes="_x0000_i1053"> и <img src="/cache/referats/24060/image056.gif" v:shapes="_x0000_i1054"><img src="/cache/referats/24060/image058.gif" v:shapes="_x0000_i1055">  суммарное число передач между сегментами быломинимально. Сегменты обладают свойством <img src="/cache/referats/24060/image060.gif" v:shapes="_x0000_i1056">  заданногосвойства гарантирует тот факт, что при разбиении блоков по сегментам каждыйблок программы может принадлежать только одному сегменту. Алгоритм являетсяпоследовательным и выполняет шаги до тех пор, пока все блоки не будут разбитыпо сегментам. Представим  таблицу передач(таблица 1). В таблице по главной диагонали, все ячейки сделаем  нулевыми. Идея алгоритма заключается вследующем: На первом шаге выбираем произвольный блок  пусть выбран <img src="/cache/referats/24060/image062.gif" v:shapes="_x0000_i1057"> определим его впроизвольно выбранный блок, пусть <img src="/cache/referats/24060/image064.gif" v:shapes="_x0000_i1058">  алгоритм определяет блок  с которым определенный в сегмент <img src="/cache/referats/24060/image066.gif" v:shapes="_x0000_i1059"> блок <img src="/cache/referats/24060/image062.gif" v:shapes="_x0000_i1060"> имеет максимальноечисло передач. Далее алгоритм проверяет, может ли найденный блок быть определенв сегмент <img src="/cache/referats/24060/image066.gif" v:shapes="_x0000_i1061"><img src="/cache/referats/24060/image069.gif" v:shapes="_x0000_i1062"><img src="/cache/referats/24060/image071.gif" v:shapes="_x0000_i1063"> и на следующем шагерассматривается этот блок. Если «нет», то блок <img src="/cache/referats/24060/image073.gif" v:shapes="_x0000_i1064"> присваивают следующемусегменту. Суть алгоритма заключается в рассмотрении каждого блока по егопризнакам. Каждый блок обладает <img src="/cache/referats/24060/image006.gif" v:shapes="_x0000_i1065">  признаками <img src="/cache/referats/24060/image076.gif" v:shapes="_x0000_i1066"> при <img src="/cache/referats/24060/image078.gif" v:shapes="_x0000_i1067">  является более оптимальным сточки зрения цели задачи. Алгоритм продолжает свою работу до тех пор пока небудут рассмотрены все блоки.

Литература

1.<span Times New Roman"">       

ДюсембаевА.Е. Математические модели сегментации программ:-М. Физматлит. 2001г.

2.<span Times New Roman"">       

ЖуравлевЮ.И. Корректные алгебры над множествами эвристических алгоритмов/ Кибернетика1978г № 2.
еще рефераты
Еще работы по программированию, базе данных