Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 70
Текст из файла (страница 70)
4.19. Сннтеаировать логические схемы, реалнауюшие булеву функцию у(хм ха, хз, ха))а = У(0, 1, 2, 12, 13, 14), в базисах Вебба и Шеффера. Сравнить слоиности полученных схем. 4.20. Синтеаировать логическую схему, реалаюуюшуао булеву функцию ~(хм хв, хв, ха))а м и(0, 1, 2, 4, 7, 9), в бааисе УСЭППА. 4.21. Монет лн иметь автомат эквивалентные состояния, если его граф переходов представляет собой взвешенный путь? 4.22. Синтезировать нейрон, реалаюуюший булеву функкию вкда ~(хо ха, хз, ха))а = и(0, 2, 3, 5, 12, 14).
3 4.13. Комментарнн Создание систем автоматизация вроектирования, гибкого автоматизированного производства, локальных вычислптелыпвх сетей, интеллеатуальных систем знаний — решение этих и других проблем иевоамоино бее формалиаацни, основу которой составляет теория формальных грамматик и автоматов. В развитие этой теории большой вклад внесли умные — члены академий: Меидунеродиой Академии ннформатнзвкня, Российской вкадемпи наук, Росснйской академии естественных наук — В.М.Глушков, М.А.Гаврилов В.А.Горбатов, Э.В.Евреинов, А.В.
Каляев, В.Г. Лазарев, П.П. Пархоменко, П.А. Йоспелов, В.П, Чистов, И.И. Ю апишни, Э.А. Якубайтис и др. Для углубления знаний по теории'формальных грамматик и автоматов ре, комендуем (1, б, 7, 1О, 13, 21, 27). 15.1. Примииом ларакшеризаииоммаго амализа 389 Где круга этого какала, где камеи, откуда мы пришли, куда уйдем лтселеу Омар Хавлм Глава 5 ПРИКЛАДНАЯ ТЕОРИЯ АЛГОРИТМОВ. ХАРАКТЕРИЗАПИОННЫИ АНАЛИЗ 95.1.
Принципы характеризацнонного анализа. Построение комбннаториых алгоритмов Характерной чертой современной научно-технической революции является возрастающая роль вычислений комбинаторного (переборного) характера в прикладных задачах. Актуальной проблемой дискретной математики является построение эффективных как по объему необходимой памяти, так и по быстродействию комбинаторных алгоритмов. Прикладные задачи можно подразделить на задачи анализа и задачи синтеза дискретных систем. Под решением задачи анализа подразумевается опрелеленне того, обладает ли модель Ф, представляющая дискретную систему, требуемыми свойствами.
Решение задачи синтеза предполагает проведение преобразования модели Ф, в модель Фь, при котором достигается экстремум заданного функционала качества ~р(Фь). В обоих случаях можно говорить об эквивалентироввнин. В задачах анализа по модели Ф, строится ее эквивалент, раскрывающий свойства модели. В задачах синтеза модель Ф, эквивалентируется синтезируемой моделью Фэ. Как анализ, так и синтез осуществляют с помощью комбинированных алгоритмов.
Примитивным классом комбинаторных алгоритмов являются ГСН-алгоритмы (ГСН вЂ” грубая сила и невежество). Это алгоритмы, лишенные какой-либо "искусности", они решают задачи "вслепую", проводя полный перебор возможных преобразований. В этом случае отсутствуют теоретические предпосылки, на основании которых можно было бы предложить "утонченный" алгоритм решения. В алгоритмах этого класса реализуется синтаксическое эквивалентирование.
Синтаксическое эквивалентирование, называемое эквивалемо1мым преобразованием, соответствует уровню знаний, при котором известна полная система аксиом. Оно заключается в построении очередного варианта для задач анализа и в замене модели Ф, моделью Фь для задачи синтеза на основании той или иной аксиомы или закона, полученного из системы аксиом.
Дерево решений при синтаксическом эквивалентировании изображено на рис. 5.1, а, Каждая висячая вершина дерева соответствует тупиковому рещению. Характерными свойствами этого дерева являются: 1) комбинаторный рост числа висячих вершин при линейном росте размерности аадачи. 2) необходимость возврата на предыдущий, (э — 1)-й уровень дри вычислении информации, соответствующей соседней вершине ц з-м уровне. Следствием этого свойства является принципиальная необходимость обхода всего дерева при поиске минимального решения.
Эти свойства определяют явление, называемое "проклятием размерности" или "информационным взрывом". При разработке математического и программного обеспечения ЗВМ, особенно при работе в реальном масштабе времени, при создании систем автоматизации проектирования (проблема САПР) и т. д. актуальным является проектирование быстродействующих пакетов прикладных программ. Для повышения быстродействия адгоритмов используют эвристики в виде соответствующих функ- 6 Рис.
Зд ционалов, найденных на основании опыта, аналогий, здравых соображений. В результате получают класс эвристических алгоритуввв. Примерами эвристических алгоритмов являются генетические, технологические (типа отжига), жадные, хитрые н другие алгоритмы. При построении этих алгоритмов используется яримЦия аналогий на основе дескриптивной семантики. Алгоритмы этого класса реализуют эвристическое эквивалентирование. При эвристическом эквивалентировании быстродействие алгоритма повышается, но оценить качество полученного решения невозможно; нельзя даже сказать, является ли оно тупиковым, т.
е. далее не зпрошаемым. Дерево решений, каждая вершина которого соотВптствует исходному заданию, а дуга — варианту перебора или цреобразаванию, изображено на рис. 5.1, б. Гл.5. Прокладкам теория алгоритмов 390 8 5.1. Принципы характегзизациоимого а»ализа 391 Рассмотрим, например, задачу синтеза диверсифицированного портфеля. Эта задача возникла при оценке риска в проводимой фирмой инвестиционной политике. Финансовый риск связан с неопределенностью эффективности операций в момент заключения сделки, обусловленной трудностью прогноза цены в будущем, а для акций — и будущих дивидендов.
Вложив деньги в акции одной компании, инвестор оказывается зависящим от колебаний ее курсовой стоимости. Если он вложит свой капитал в акции нескольких компаний, то эффективность будет определяться уже усреднекиым значением курсовых стоимостей нескольких компаний. Средний же курс, как правило, колеблется меньше, поскольку при понижении курса одной из ценных бумаг курс другой может повыситься, что приведет к меньшим колебаниям усредненного курса.
Именно этим объясняется, что инвестор часто является держателем не одного вида ценных бумаг, а нескольких, именуемых портфелем инвестора. При росте числа Ж видов ценных бумаг, включенных в портфель, риск ограничен и стремится к нулю при Аà — ь оо, Этот факт известен в теории финансового риска как эффект диверсификации (разнообразия) портфеля. Эвристика, применяемая при решении задачи синтеза диверсифицированного портфеля, основана на принципе аналогий. Вспомнив житейскую мудрость: никогда не клади все яйца в одну корзину, формулируем эвристику решения этой задачи: заданшись мощностью диверсифицированного портфеля, приобретаем слабо связанные между собой виды ценных бумаг.
Здесь под мощностью портфеля понимается количество видов ценных бумаг. Анализ западных финансовых рынков показал, что оптимальная мощность портфеля инвестора не меньше 15. Для России, в которой финансовьгй рынок только формируется, это число должно быть гораздо большим. Рассмотрим реализацию выбранной эвристики. Имеем множество ценных бумаг М = (Ь;/ Ь; — ценная бумага). На основе анализа временных рядов изменения их курсовой стоимости строим корреляционный граф С„врр — — (У, (1з', К)), каждая вершина а; б У которого взаимно одйозначно соответствует ценной бумаге, а ребро (аи о ) б Сг взвешено корреляционным коэффициентом К(Ь;, Ь ) между ценными бумагами Ь;, Ь (рис. 5.2, а).
Установим порог существенной корреляции: К(6;, 6 ) > 0,5. Тогда корреляционный граф С, рр преобразуется в граф связности ценных бумаг С,в = (У, зз'), аг с+ 6;, (о;, оД б сз' ~-) К(6;, 6.) > 5. Если мощность ~п~ диверсифицированного портфеля я равна 2, то, очевидно, его содержимое будут представлять ценные бумаги 6, Ьд, расстояние р(6, Ьд) между которыми равно диаметру а(С„) графа С„: Если мощность портфеля 2 ( ~я! < го(С ), где ео(Сев) число ннутренней устойчивости или вершинное число независи- ьс ь, Рис. 8.2 мости графа связности С„, то порождаем пустые подграфы и выбираем из них подграф, вершины которого попарно максимально удалены друг от друга.
Если мощность портфеля ф > ео(С„), то к максимально пробтому падграфу Е,„„добавляем ф — еа(С,») вершин так, чтобы рбразовавшийся подграф С = (У, сг) имел минимальную мощность сигнатуры ~О! зв при )У~ = ~я~. Рассмотрим синтез диверсифицированного портфеля я.
Множество ценных бумаг М = (Ь;/ 1 = 1, ..., 8), и соответствующий корреляционный граф С„представлен на рис. 5.2, а. После учета порога корреляции граф гзГ» рр преобразуется в граф снязнооти С (рис. 5.2, б). Для случая, когда ~к~ = 2, строим матрицу расстояний В(С„) между вершинами: 1 Э 3 4 8 6 Т 8 1 2 з 4. $ 8 8 лс(Сев) св Диаметр Ы(С„) равен 3. Следовательно, получаем восемь эквиваьгентных в смысле мощности дкверсифицированных портфелей: (аз) = ((1з2)з (1з3)з (2зб)з (2з7)з (2!8)з (Ззб)з (Зз7)з (Зз8)). Синтезируем портфели мощности 3. Порождаем пустые под»рафы графа связности С, .
На рис. 5.3 дерево естественным абра,'зам преобразовано в эквивалентную в смысле включения путей 1 5.1. Примциоы зарактеризациоммого анализа 393 Гл.б. Прикладнал теория алгориа>лгое 392 диаграмму Хассе. Вершинное число независимости ео(Соя) графа связности равно 3. Оцениваем каждый пустой подграф Ег суммой попарных расстояний между вершинами подграфа Еь Выбираем ь ь ь ь, Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
