textarchive.ru

Главная > Документ


Рис. 1. Блок-схема алгоритма СО

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

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

1) Построение инициализирующих последовательностей (ИП).

Пусть – множество всех состояний последовательностной схемы в трёхзначном алфавите моделирования ; пусть – множество всех возможных определённых состояний схемы, а – множество всех возможных входных последовательностей . Для выбранного трёхзначного моделирования . Пусть начальное неопределённое состояние. Функция обозначает все состояния, достижимые схемой при поступлении на её вход последовательностей из при использовании трёхзначного алфавита моделирования.

Определение 1. Последовательность называется инициализирующей для заданной схемы, если в финальном состоянии все состояния определены, т.е. .

2) При построении последовательностей, проверяющих эквивалентность двух заданных схем, задача, по существу, сводится к доказательству несуществования входной последовательности, различающей две заданные схемы, т.е. ищется контрпример, показывающий, что схемы различны.

Определение 2. Входная последовательность называется различающей для цифровых схем и , когда выходные реакции схем и различны: .

3) Задача построения тестов. Пусть задано исправное устройство и конечное множество его неисправных модификаций , и для . Традиционно, мы используем множество одиночных константных неисправностей.

Определение 3. Тестом, проверяющим все неисправности модификаций , называется такая входная последовательность, которая является проверяющей для всех , .

Исходя из целей указанных задач – построение входных последовательностей – выбирается кодирование конфигураций и возмущающие операции (рис. 2). Отметим, что такое кодирование полностью соответствует кодированию особей в ГА, а возмущающие операции соответствуют операциям мутации в ГА.

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

,

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

Для задачи верификации эквивалентности оценка вычисляется следующим образом:

,

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

а) конфигурация

б) возмущающие операции

Рис. 2. Представление решений и операции над ними

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

,

где Hi – близкие к 1 константы, определяет качество отдельного входного вектора :

,

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

Алгоритмы СО оптимизации рассеивания тепла тестовых последовательностей. Алгоритмы СО могут быть применены не только к задачам построения идентифицирующих последовательностей, но и к их оптимизации. В [15] авторами разработана стратегия генерации энергоэффективных тестов. Она основана на понятии избыточного тестирования и состоит из трёх этапов.

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

На втором этапе для каждой из построенных последовательностей оценивается рассеивание тепловой энергии:

,

где: – напряжение работы схемы; – физическая ёмкость на выходе вентиля; – частота работы схемы; – число событий при моделировании на заданной входной последовательности.

Третий этап заключается в выборе такого подмножества последовательностей , чтобы полнота теста была не хуже начальной , а рассеивание тепла минимальным . Очевидно, что выбор различных подмножеств последовательностей будет влиять и на полноту теста и на параметр рассеивания тепла. Задача выбора такого подмножества является NP-полной и её решение строится на основании алгоритма СО. В отличие от предыдущих задач, в данной в качестве конфигурации выступает множество номеров подпоследовательностей из , которые фактически задают входную последовательность. Список номеров в разных конфигурациях изменяется в ходе эволюции, также как и число номеров в списке. Используются три классические операции возмущения для множеств: обмен элементами, удаление элемента и добавление случайного элемента.

Алгоритм делится на две фазы, в каждой из которых применяется свой вид функции оценки. В фазе 1 из множества выбираются такие подмножества, для каждого из которых выполнено первое условие. Функция оценки при этом имеет вид

.

При обнаружении набора подпоследовательностей, для которого условие выполнено, алгоритм СО переходит к фазе 2 оптимизации данного набора. Здесь развитие конфигурации идёт таким образом, чтобы уменьшить рассеивание тепла для подмножества последовательностей, и оценка имеет вид , где .

Эффективность алгоритма СО измеряется уменьшением рассеивания тепла для конфигураций на входе и выходе фазы 2.

Сравнение алгоритмов СО и ГА. Разработка алгоритмов, рассмотренных выше, даёт разработчикам возможность выбора между алгоритмами СО и ГА. Близость данных стратегий позволяет ставить вопрос о сравнительной эффективности их поисковых свойств. В работе [16] проводился практический сравнительный анализ ГА и СО, из которого следует, что метод СО на большинстве задач не проигрывает ГА, а на многих – выигрывает. Для сравнения практической эффективности алгоритмов СО и ГА изучались результаты численных экспериментов на схемах из контрольного каталога ISCAS-89 [17]. Аккуратное сравнение различных алгоритмов является сложной проблемой [18] и определить абсолютно лучший алгоритм не представляется возможным, поскольку сравнение производится сразу по нескольким критериям.

Результаты сравнительного анализа алгоритмов СО и ГА [7] построения ИП приведены в табл. 1. Видно, что оба подхода показывают приблизительно равные результаты.

Frame3

При проведении экспериментов верификации эквивалентности применялась следующая стратегия. В исходную схему вносились миноритарные изменения (заменялся тип одного случайно выбранного логического вентиля) и для двух схем строилась различающая последовательность. Эксперимент с каждой схемой проводился 25 раз. В среднем алгоритм СО построил различающую последовательность в 96.71% экспериментов, алгоритм ГА [8] – в 94.7%, алгоритм VEGA – 88,35% [19], алгоритм AQUILA – 65,00% [20]. Последние два алгоритма являются структурными и для них не приводятся результаты работы с большими схемами.

При сравнении эффективности алгоритмов построения энергоэффективных тестов СО и ГА [9] для третьего этапа использовались одинаковые результаты, полученные на этапах 1 и 2. Результаты сравнения приведены в табл. 2.

Frame4

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

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

Списоклитературы: 1.Goldberg D.E. Genetic Algorithm in Search, Optimization, and Machine Learning / D.E. Goldberg. – Addison-Wesley, 1989. – 432 p. 2.Скобцов Ю.А. Основы эволюционных вычислений / Ю.А. Скобцов. – Донецк: ДонНТУ, 2008. – 326 с. 3. Неітеративні, еволюційні та мультиагентні методи синтезу нечітко логічних і нейромережних моделей: Монографія / Під. заг. ред. С.О. Суботіна. – Запоріжжя: ЗНТУ, 2009. – 375 с. 4.Corno F. GATTO: a Genetic Algorithm for Automatic Test Pattern Generation for Large Synchronous Sequential Circuits / F. Corno, P. Prinetto, M. Rebaudengo, M. Sonza Reorda // IEEE Transactions on Computer-Aided Design, August 1996. – Vol. 15. – № 8. – P. 943-951. 5.Skobtsov А. Genetic algorithms in test generation for digital circuits / Y.A. Skobtsov, D.E. Ivanov, V.Y. Skobtsov // Proceedings of the 8th Biennial Baltic Electronics Conference. – Tallinn Technical University, 2002. – Р. 291-294. 6.Corno F. A Genetic Algorithm for the Computation of Initialization Sequences for Synchronous Sequential Circuits / F. Corno, P. Prinetto, M. Rebaudengo, M. Sonza Reorda, G. Squillero // ATS97: The Sixth IEEE Asian Test Symposium, Akita (JP). – 1997. – P. 56–61. 7.Иванов Д.Е. Построение инициализирующих последовательностей синхронных цифровых схем с помощью генетических алгоритмов / Д.Е. Иванов, Ю.А. Скобцов, А.И. Эль-Хатиб // Проблеми інформаційних технологій. – Херсон: ХНТУ. – 2007. – № 1. – С. 158–164. 8.Иванов Д.Е. Генетический подход проверки эквивалентности последовательностных схем / Д.Е. Иванов // "Радіоелектроніка. Інформатика. Управління". – Запоріжжя: ЗНТУ. – 2009. – № 1 (20). – С. 118–123. 9. Иванов Д.Е. Генетический алгоритм оптимизации рассеивания тепловой энергии входных тестовых последовательностей / Д.Е. Иванов // Наукові праці Донецького національного технічного університету. Серія: "Обчислювальна техніка та автоматизація". – Випуск 18 (169). – Донецьк: ДонНТУ, 2010. – С. 206–215. 10.Krishnamurthy B. On the Complexity of Estimating the Size of a Test Set / B. Krishnamurthy, S. B. Akers // IEEE Trans. on Computers. – August 1984. – P. 750–753. 11.Metropolis N. Equation of State Calculation by Fast Computing Mashines / N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller, E. Teller // Journal of Chem.Phys. – 1953. – Vol. 21. – № .6. – P. 1087–1092. 12.Kirkpatrick S. Optimization by simulating annealing / S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi // Science. – 1983. – Vol. 220. – P. 671–680. 13.Иванов Д.Е. Алгоритм построения инициализирующих последовательностей цифровых схем, основанный на стратегии симуляции отжига / Д.Е. Иванов, Р. Зуауи // Искусственный интеллект, 2009. – № 4. – С. 415–424. 14. Иванов Д.Е. Верификация эквивалентности цифровых схем с использованием стратегии симуляции отжига / Д.Е. Иванов, Р. Зуауи // "Науковий вісник Чернівецького університету". – Вип. 479. – "Комп’ютерні системи та компоненті", 2009. – С. 33–41. 15.Иванов Д.Е Алгоритм симуляции отжига оптимизации рассеивания тепла диагностических тестов / Д.Е. Иванов, Р. Зуауи // "Радіоелектронні і комп’ютерні системи", 2010. – № 7 (48). – С. 170–175. 16. Inberg L. Simulated Annealing: Practice versus Theory / L. Inberg // Journal of Mathematical Computer Modelling. – 1993. – Vol. 18. – № 1. – P. 29–57. 17. Brgles F. Combinational profiles of sequential benchmark circuits / F. Brgles, D. Bryan, K. Kozminski // International symposium of circuits and systems, ISCAS-89. – 1989. – P. 1929–1934. 18. Corno F. Comparing topological, symbolic and GA-based ATPGs: an experimental approach / F. Corno, P. Prinetto, M. Rebaudengo, M. Sonza Reorda // Proceedings of the IEEE International Test Conference on Test and Design Validity, Washington (USA). – 1996. – P. 39–47. 19. Corno F. VEGA: A Verification Tool Based on Genetic Algorithms / F. Corno, M. Sonza Reorda, G. Squillero // ICCD98, International Conference on Circuit Design, Austin, Texas (USA). – 1998. – P. 321–326. 20.Cheng K.-T. AQUILA: An Equivalence Checking System for Large Sequential Designs / K.-T. Cheng, S.-Yu. Huang, K.-Ch. Chen, F. Brewer, C.-Y. Huang // IEEE Transactions on Computers. – 2000. – Vol. 49. – № 5. – P. 443–464.

Статья представлена д.т.н., проф., зав. каф. АСУ ДонНТУ Скобцовым Ю.А.

УДК 681.518:681.326.7

Застосування алгоритмів симуляції відпалювання в задачах ідентифікації цифрових схем/ Іванов Д.Є. // Вісник НТУ "ХПІ". Тематичний випуск: Інформатика і моделювання. – Харків: НТУ "ХПІ". – 2011. – № 17. – С. 60 – 69.

У статті розглянуто досвід застосування еволюційного алгоритму симуляції відпалювання до вирішення задач ідентифікації, що виникають при проектуванні цифрових схем. Описано загальну структуру алгоритму симуляції відпалювання, його компоненти рішення задач побудови ідентифікуючих послідовностей та їх оптимізації. Проведено порівняльний аналіз ефективності з генетичними алгоритмами. Іл.: 2. Табл.: 2. Бібліогр.: 20 назв.

Ключові слова: еволюційні алгоритми, ідентифікація, цифрова схема, симуляція відпалювання, генетичний алгоритм.

UDC 681.518:681.326.7

The use of simulation annealing algorithms in problems of identification of digital circuits / Ivanov D.E. / Herald of the National Technical University "KhPI". Subject issue: Information Science and Modelling. – Kharkov: NTU "KhPI". – 2011. – №. 17. – P. 60 – 69.

The article describes the experience of use of evolutionary algorithm of the simulated annealing to solve the identification problems in the design of digital circuits. It is described the overall structure of the simulated annealing algorithm and its components for algorithm of constructing of the identifying sequences and to optimize them. A comparative analysis of the effectiveness with genetic algorithms is performed. Figs.: 2. Tabl.: 2. Refs.: 20 titles.

Кey words: evolutionary algorithm, identification, digital circuit, simulated annealing, genetic algorithm.

Поступила в редакцию 11.02.2011

УДК 681.31+519.8

А.С. КУИМОВА, аспирантка Волжской государственной академии водного транспорта, Нижний Новгород,

Ю.С. ФЕДОСЕНКО, д.т.н., проф., зав. каф. ИСУиТ Волжской государственной академии водного транспорта, Нижний Новгород

СИНТЕЗ ОГРАНИЧЕННЫХ ПО СТРУКТУРЕ ОПТИМАЛЬНО-КОМПРОМИССНЫХ СТРАТЕГИЙ ОБСЛУЖИВАНИЯ ПОТОКА ОБЪЕКТОВ

Вводится модель однофазного обслуживания детерминированного потока объектов. Формулируется бикритериальная задача синтеза стратегий обслуживания. Показано, что учет ограничений на структуру стратегий обслуживания выводит задачу из класса NP-трудных и позволяет построить полиномиальный алгоритм синтеза стратегий, оптимальных по Парето. Приводится пример. Библиогр.: 8 назв.

Ключевые слова: стратегии обслуживания, NP-трудность, оптимальность по Парето.

Постановка проблемы и анализ литературы. В работе [1] рассмотрена каноническая модель обслуживания потока объектов стационарным процессором, описывающая практически важную проблему оптимизации использования дискретных ресурсов. Весте с тем, естественное требование адекватности математического описания реальным ситуациям, возникающим в технических, экономических и организационных системах, нередко предопределяет необходимость различных усложнений канонической модели. Так, в данной работе формулируется значимая для приложений (в частности, в автоматизированных производственных системах и на внутреннем водном транспорте [2]) модель, в которой стратегии обслуживания оцениваются по значениям не одного, а двух независимых критериев. При этом в качестве парадигмы решения сформулированной экстремальной задачи принята концепция Парето [3, 4], предполагающая выявление и предъявление лицу, принимающему решения, всего множества оптимально-компромиссных стратегий обслуживания. Данная оптимизационная задача относится к числу NP-трудных [5]. Поэтому актуальной является проблема построения таких модификаций бикритериальной модели обслуживания, которые при сохранении адекватности описания порождают полиноминально разрешимые подклассы задачи синтеза стратегий обслуживания. Одна из таких модификаций формализует ограничение на допустимую величину опережений в обслуживании.

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

Математическая модель и постановка задачи. Задан конечный детерминированный поток объектов On = {о1, о2, …, оn}, которые подлежат однофазному обслуживанию на стационарном процессоре P. Для каждого объекта определены целочисленные характеристики: ti момент поступления в очередь на обслуживание (0 ≤ t1 ≤ t2 ≤ … ≤ tn); i  норма длительности обслуживания; ai  штраф за единицу времени простоя в ожидании обслуживания; di  мягкий директивный срок завершения обслуживания (di ≥ ti + τi). Если обслуживание объекта оi начинается в момент времени то величина индивидуального штрафа по этому объекту определяется значением линейной функции вида . Обслуживание объекта может быть начато свободным процессором в любой момент времени (t ≥ ti) и осуществляется без прерываний; одновременное обслуживание двух и более объектов и неоправданные простои процессора запрещены; процессор готов к обслуживанию объектов потока On в момент времени = 0.

Очевидно, любая стратегия S обслуживания потока On представляет собой перестановку {i1, i2, …, in} совокупности индексов N = {1, 2, …, n}; при этом объект с индексом ik в стратегии S обслуживается k-м по очереди (k = ). Введем следующее определение: стратегию Sq назовем q-стратегией, если не существует объекта, который при реализации стратегии Sq допускает пропуск вперед на обслуживание более q других объектов. Множество таких стратегий будем обозначать как Z(q). Пусть t*(ik, Sq) и (ik, Sq) соответственно моменты начала и завершения обслуживания объекта с индексом ik при реализации стратегии Sq. Считаем, что реализация компактна, т.е. выполняются соотношения

Качество каждой стратегии будем оценивать по значениям пары критериев K1() и K2(), первый из которых представляет собой суммарный штраф за простои объектов в ожидании обслуживания, а второй – оценивает максимальное по продолжительности нарушение директивного срока завершения обслуживания среди всех объектов потока On. С учетом введенных выше обозначений имеем

Формализация парадигмы Парето на множестве Z(q) приводит к следующей задаче выделения в плоскости (K1(), K2()) полной совокупности эффективных точек и формирования им соответствующих оптимально-компромиссные стратегии обслуживания

(1)

Синтез стратегий обслуживания. Алгоритм решения задачи (1) построим на основе идеологии динамического программирования [6, 7]. С этой целью введём операцию  между произвольным вектором x = (x1, x2) и множествомY векторовy = (y1y2) той же размерности: через Yxобозначим совокупность всех векторов v = (v1v2), где первая компонента представима в виде v1 = y1 + x1, а вторая определяется по правилу v2 = max(y2x2). Будем обозначать: для произвольного множества двумерных векторов-оценок M через eff[M] максимальное по включению подмножество недоминируемых в M векторов; через F(t) подмножество индексов объектов, которые поступают в систему обслуживания в момент времени t. При обслуживании объектов потока On, решения принимаются в те моменты времени, когда процессор свободен и необходимо выбрать следующий объект. Очевидно, что набор (tjMjt, Q) определяет текущее состояние системы в момент t принятия решения, где j – наименьший из индексов в множестве индексов необслуженных объектов, а Mjt – множество индексов обслуженных объектов, обошедших на момент времени tобъект с индексом j (|Mjt| ≤ q), Q – множество индексов объектов, ожидающих обслуживания в этот момент времени. Введем обозначения: {M}r – совокупность индексов объектов из множества M с индексами большими r; D(tΔ) – совокупность индексов объектов, прибывающих в систему на интервале [t + 1, t + Δ], Δ ≥ 1, т.е. .

В множество Qсчитается включенным индекс 0 фиктивного объекта с параметрами t0 = t, , a0 = 0, d0 = . Выбор такого объекта на обслуживание означает простой процессора с момента времени t до момента поступления в систему очередного объекта. Если в текущем состоянии фиктивный объект не был выбран на обслуживание, то он исключается из множества Q и в дальнейшем не рассматривается.

Введем оператор R раскрытия состояния системы обслуживания: если(tjMjt, Q) является некоторым произвольным состоянием, то R(tjMjt, Q) – множество порождаемых им состояний, т.е. непосредственно следующих за состоянием (tjMjt, Q). Последовательно раскрывая все состояния, начиная от начального, получим в итоге совокупность финальных состояний. Заметим, что одно и то же состояние может сформироваться при раскрытии различных состояний. Присвоим начальному состоянию номер 0 и последовательно пронумеруем все состояния в порядке их порождения оператором R. Для одного и того же состояния, если его можно получить несколькими способами, используется только один номер, присвоенный первоначально; каждое рассматриваемое состояние может характеризоваться несколькими оценками.

Пусть Wq(tjMjt, Q) – задача, получаемая из исходной задачи (1) при условии, что обслуживание начинается в момент времени t; при этом надо обслужить объекты с индексами из множества Q и все объекты, поступающие в систему позднее момента времени t. Через Eq(tjMjt, Q) обозначим совокупность эффективных по Парето двумерных оценок, получаемую при решении задачи Wq(tjMjt, Q). Тогда полная совокупность эффективных оценок задачи (1) будет представлять множество.

Ведем обозначения: Qt – совокупность индексов всех необслуженных к моменту t объектов, т.е. ; ξ[W] – минимальный из положительных индексов объектов множества W. Очевидно, что для любого θ ≥ 0, j = α и = {α}, где α – произвольный индекс объекта из потока On, имеет место соотношение

(2)

Если в состоянии (tjMjtQ) в качестве следующего обслуживаемого выбран объект с индексом α  Q (α ≠ j) и при этом |Mjt| < q, то очередным моментом принятия решения будет t + τα и выбор индекса следующего объекта для обслуживания будет осуществляться из множества (Q \{α})D(tτα); при этом Mjt{α} – множество объектов, опередивших объект с индексом j. Если на обслуживание выбран объект с индексом j, то в следующий момент принятия решения t + τj, наименьшим индексом объекта будет являться j* = ξ[Qt\{j}], множеством его опередивших объектов будет {Mjt}j*, а множество ожидающих обслуживания объектов определяется как (Q \{j})D(tτj). Следовательно, имеет место соотношение

(3)

Если в состоянии (tjMjtQ) имеет место равенство |Mjt| = q, то следующим можно обслуживать лишь объект с индексом j. Поэтому

(4)

Выражения (2) – (4) суть решающие рекуррентные соотношения. Непосредственным анализом [8] устанавливается, что вычислительная сложность описанного алгоритма оценивается величиной O(n4).

Результаты вычислительных исследований и выводы. Целью вычислительных экспериментов являлось определение скоростных и объёмных характеристик разработанного алгоритма. Для значений параметров потока On были установлены следующие диапазоны изменения: ti-1 ≤ ti ≤ ti-1 + 5, 1 ≤ ai ≤ 11, 1 ≤ τi ≤ 15, ti + τi ≤ di ≤ ti + τi + 4, i = . Таким образом была обеспечена достаточно высокая плотность потока и гарантировалось получение заведомо пессимистических оценок характеристик алгоритма. Размерность потока изменялась от 6 до 13 с единичным шагом; аналогично параметр q принимал значения от 1 до [n/2]. В соответствующих узлах решетки (n, q) генерировались по равномерному распределению данные для серии из 100 частных задач типа (1).



Скачать документ

Похожие документы:

  1. Государственное бюджетное города москвы «центральная универсальная

    Документ
    ... Р. С. Тенденции роста и развития электронных периодических изданий / Р. С. Гиляревский, И. А. Черный // Современное ... новых информационных технологий в деятельности Нижегородской государственной областной детской библиотеки. Свергунова Н. М. ...
  2. Государственное образовательное профессионального образования

    Документ
    ... деятельности ЗабКИПКРО………………………………………………………… 17 V. Периодические издания:…………………………………………… Научно-методический журнал «Педагогическое ... и методическим работникам.  Статистика результатов государственной (итоговой) аттестации выпускников (9-х классов в ...
  3. Государственное и муниципальное управление (3)

    Ученые записки
    ... государственных экономических, социальных, и других программ, издание и продвижение нормативно-правовых актов, реклама государственных учреждений и государственных ... ра­бот свидетельствует 5-е издание учебного пособия «Государственная и муниципаль­ная ...
  4. Государственная центральная ХАНТЫ-МАНСИЙСК

    Библиографический указатель
    ... с 1941 г. - «Ханты-Мансийск». Справочный аппарат издания включает «Указатель предприятий, учреждений и организаций ... Институт природопользования Севера (Филиал Тюменской Государственной сельскохозяйственной академии) Факультет экономики и ...
  5. Государственная центральная ХАНТЫ-МАНСИЙСК

    Библиографический указатель
    ... с 1941 г. - «Ханты-Мансийск». Справочный аппарат издания включает «Указатель предприятий, учреждений и организаций ... Институт природопользования Севера (Филиал Тюменской Государственной сельскохозяйственной академии) Факультет экономики и ...

Другие похожие документы..