E-Book Overview
М.: Институт системного программирования РАН, 2004. – 198 с.
Сборник посвящен разработке и анализу алгоритмов для различных задач дискретной математики и теоретического программирования. Представлены работы по приближенным алгоритмам для задачи упаковки прямоугольников в несколько полос, задачи положительного линейного программирования, задачи о покрытии и ее обобщениях, задачи поиска часто встречающихся комбинаций. Несколько статей посвящены алгоритмической сложности, анализу и преобразованиям программ в целях обеспечения компьютерной безопасности.Содержание: А. И. Поспелов. Анализ одного алгоритма упаковки прямоугольников, связанного с построением расписаний для кластеров. С. Н. Жук. Анализ некоторых эвристик в задаче упаковки прямоугольников в несколько полос. С. А. Фомин. Быстрый приближенный алгоритм для задачи положительного линейного программирования. Н.Н. Кузюрин, О. А. Прокопьев. О распознавании сложности аппроксимации булевых функций. М.Н. Вялый. Алгоритмические задачи с таблицами значений булевых полиномов. Т. В. Андреева. Об унимодальности декартовой степени звезд. Н. Н. Кузюрин. Обобщенные покрытия и их аппроксимации. N. N. Kuzjurin. Probabilistic analysis of the greedy algorithm. Н.Н. Кузюрин, С. А. Мартишин, М. В. Храпченко. Генетические алгоритмы в задаче поиска часто встречающихся комбинаций. N. P. Varnovsky. A note on the concept of obfuscation. K. S. Ivanov, V.A. Zakharov. Program obfuscation as obstruction of program static analysis. A. V. Shokurov. An approach to quantitative analysis of resistance of equivalent transformations of algebraic circuits. I. M. Zakharyaschev, V.A. Zakharov. On the equivalence-checking problem for polysemantic models of sequential programs.
E-Book Content
Российская Академия наук Институт Системного Программирования
Труды Института Системного Программирования Математические методы и алгоритмы Том 6 Под редакцией чл.-корр. РАН В.П.Иванникова
Москва 2004
УДК 51
Труды Института системного программирования: Том 6. /Под ред. В.П.Иванникова/ -М.:ИСП РАН, 2004. - 198 с.
Сборник посвящен разработке и анализу алгоритмов для различных задач дискретной математики и теоретического программирования. Представлены работы по приближенным алгоритмам для задачи упаковки прямоугольников в несколько полос, задачи положительного линейного программирования, задачи о покрытии и ее обобщениях, задачи поиска часто встречающихся комбинаций. Несколько статей посвящены алгоритмической сложности, анализу и преобразованиям программ в целях обеспечения компьютерной безопасности.
c Институт Системного Программирования РАН, 2004
Труды Института Системного Программирования
Содержание Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . А. И. Поспелов Анализ одного алгоритма упаковки прямоугольников, связанного с построением расписаний для кластеров . . . . . . . . . С. Н. Жук Анализ некоторых эвристик в задаче упаковки прямоугольников в несколько полос . . . . . . . . . . . . . . . . . . . . . . . С. А. Фомин Быстрый приближенный алгоритм для задачи положительного линейного программирования . . . . . . . . . . . . . . . . . . . Н. Н. Кузюрин, О. А. Прокопьев О распознавании сложности аппроксимации булевых функций М. Н. Вялый Алгоритмические задачи с таблицами значений булевых полиномов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Т. В. Андреева Об унимодальности декартовой степени звезд . . . . . . . . . Н. Н. Кузюрин Обобщенные покрытия и их аппроксимации . . . . . . . . . . N. N. Kuzjurin Probabilistic analysis of the greedy algorithm . . . . . . . . . . . Н. Н. Кузюрин, С. А. Мартишин, М. В. Храпченко Генетические алгоритмы в задаче поиска часто встречающихся комбинаций . . . . . . . . . . . . . . . . . . . .