Материалы VII Международного семинара "Дискретная математика и ее приложения" (29 января - 2 февраля 2001 г.). Часть I,II,III - М.: Изд-во центра прикладных исследований при механико-математическом факультете МГУ, 2001.

С О Д Е Р Ж А Н И Е

ЧАСТЬ I

Пленарные доклады

Д. Н. Бабин	Классификация автоматных базисов Поста по разрешимости свойства полноты	4
Э. Э. Гасанов	Информационно-графовая модель данных	6
Н. П. Долбилин	Локальный метод в теории правильных разбиений	10
А. А. Махнев	О некоторых свойствах реберно регулярных графов	16
М. Ю. Мошков	О преобразовании систем решающих правил в деревья решений	21
А. Я. Петренюк	Древесные факторизации полных графов: существование, построение, перечисление	26
С. В. Севастьянов	Многопараметрический анализ сложности дискретных задач	30
А. В. Чашкин	О локальной сложности булевых функций	36

Секция "Синтез и сложность управляющих систем"

Ф. М. Аблаев, А. Ф. Гайнутдинова, М. Карпинский	Вычислительные свойства квантовых бинарных программ	43
В. Б. Алексеев	О нижних оценках в методе полилинейных форм	46
М. А. Алехина	Верхние оценки ненадежности схем при однотипных константных неисправностях на входах элементов	49
Т. Бергер, В. И. Левенштейн	Восстановление двоичных векторов с помощью двухэтапного дизъюнктивного тестирования	53
И. А. Бугаков	Концепция построения сложных технических систем, подвергающихся экстремальным воздействиям в процессе функционирования	56
А. А. Гришкевич	Формирование трехэлементных сечений из элементов с тремя состояниями	59
В. М. Захаров, Ш. Р. Нурутдинов, С. В. Шалагин	Построение модели умножителя в поле Галуа на базе программируемых матриц логических элементов	62
Н. К. Косовский, М. А. Опара.	Сложность разрешения многоагентных логик с ограниченным числом ранжированных объектов	65
Р. Х. Латыпов.	Задача сбережения энергии при тестировании схем	68
А. М. Мошкова	О диагностике расширений класса константных неисправностей схем из функциональных элементов	70
В. А. Мощенский	Алгоритм учета в методе нитей	73
В. А. Орлов	О сложности схем в многозначных базисах	75
М. А. Федоткин	Профилактика и надежность управляющей системы	78
И. Ф. Чебурахин	О некоторых классах булевых функций одной глубины	83
О. В. Черемисин	Об активности схем из клеточных элементов, реализующих систему всех конъюнкций	86
Д. Ю. Черухин	Нижние оценки сложности коммутационных сетей	89
Я. А. Шарифов	Оптимальное управление нелинейными импульсными системами	90
В. И. Шевченко	О сложности поиска элементарных немонотонных замыканий в схемах из функциональных элементов	93
Л. А. Шоломов	Разделительная декомпозиция порядковых отношений в задачах выбора	97

Секция "Теория функциональных систем"

А. С. Балюк, С. Ф. Винокуров	О полиномиальных представлениях булевых функций	100
В. А. Захаров	О проблеме эквивалентности операторных программ на одном классе уравновешенных шкал	102
Т. М. Косовская	Двумерная геометрия на экране дисплея	105
А. В. Макаров	Алгоритм распознавания гомоморфности функциональных систем	107
Д. Г. Мещанинов	Бесконечные цепи замкнутых классов в Pk, содержащих все линейные функции	110
Е. А. Михеева	К вопросу функциональной полноты в P3	112
Н. Г. Парватов	О полноте в классе квазимонотонных функций на конечных полурешетках	114
И. Г. Перфильева	Нечеткая логика и теория аппроксимации	117
С. Н. Селезнева	О некоторых свойствах многочленов над конечными полями	120
В. Д. Соловьев	Автоморфизмы структуры замкнутых классов k-значной логики	122
В. В. Тарасов	О расширении класса Поста F8\infty в вероятностной алгебре логики	123
В. П. Тарасова	Оптимальный поиск для специального расширения классов функций	126
Р. В. Хелемендик	О синтезе игровых программ	127
А. В. Черемушкин	Декомпозиция сильнозависимых функций	130
А. Н. Черепов	Предполные классы в Pk как классы сохранения оснований	132
И. А. Черепов	Классы решетки Поста как классы сохранения основания	135

ЧАСТЬ II

Секция "Математическая теория интеллектуальных систем"

А. К. Бакиров, А. И. Белоусов, А. А. Кирильченко, М. А. Колганов	Теоретические основы и численное моделирование алгоритмов управления распределенными мобильными системами	141
А. Г. Бросалина	Эвристические алгоритмы построения регулярного выражения по заданному конечному автомату	145
А. В. Будин	Применение теории автоматов для анализа нейронных сетей	146
Д. Б. Буй	Теорема о неподвижной точке: решение систем уравнений в индуктивных множествах	148
С. И. Веселов, Н. Ю. Золотых	Идентификация геметрических образов на целочисленной решетке	151
А. В. Голованов	Об обходе лабиринтов красящими автоматами	153
Н. В. Евтушенко	Решение автоматных неравенств и уравнений	156
В. М. Захаров, Н. Н. Нурмеев, Ф. И. Салимов, С. В. Шалагин	Анализ стохастических матриц методами многомерной классификации	156
Я. В. Калинин	О порядке группового автомата	159
И. Б. Куфарева	Исследование отношений в алгебре конечных автоматов	160
Е. Е. Лазарева	Алгоритмы поиска ответов на вопросы о временных соотношениях, базирующиеся на подходе Аллена - Плесневича	163
М. М. Мельников	Проблемы проектирования систем инвариантного распознавания изображений	166
А. А. Мельникова	Базисные конечные автоматы Рабина - Скотта	170
А. А. Морозов, Ю. В. Обухов	О логическом подходе к поиску и распознаванию информации в Интернет	172
М. В. Носов	Оценка числа полиномиально задаваемых функций	174
А. Е. Панкратьев	О свойствах графа гиперболического произведения групп	175
С. А. Прокопенко	Минимизация проверяющих тестов для компоненты автоматной сети	179
С. Б. Родин	Переходные системы с максимальной вариативностью относительно кодирования состояний	181
М. И. Рожков	К задаче оптимального выбора функции выхода конечного автомата	183
В. С. Рублев	Потоковый алгоритм целочисленного сбалансирования матрицы	185
С. И. Сергеев	Новые нижние границы для трипланарной задачи назначения	187
Д. А. Силаев, А. Л. Васнев, Г. Я. Лоpан	Численные методы решения неклассической системы уравнений пограничного слоя на сфере	190
А. К. Смирнов	Разработка алгоритмов управления дискретной вероятностью	193
А. А. Сытник, Т. Э. Шульга	Задачи анализа и синтеза универсального автомата-перечислителя	195
В. А. Твердохлебов	Универсальные тесты в техническом диагностировании	199
В. А. Фомичев	Теория K-исчислений как универсальная формальная метаграмматика для описания содержания посланий компьютерных интеллектуальных агентов	203
И. А. Чижова	Принцип функционирования блоков в программной среде SPRING	207
С. Ю. Шацких	Разработка средств защиты от программных закладок на основе аутентификации клавиатурного почерка	209

Секция "Теория графов"

В. А. Воблый	О перечислении помеченных (2,4)-бирегулярных графов	212
А. А. Вороненко	Раскраски и нижние оценки количества функций, сохраняющих близость	212
И. И. Иванчик	Параметризация корневых помеченных деревьев и связных графов Калмыкова	215
М. А. Иорданский	Структура и способы порождения замкнутых классов графов	218
Г. И. Калмыков	Каркасная классификация помеченных блоков	221
Д. В. Карпов	Оценки на количество висячих вершин в остовном дереве связного графа	224
В. П. Козырев	Нахождение остовных деревьев в графах, имеющих два веса на ребрах	226
К. В. Малиновский, А. В. Панюков	Целочисленность оптимального решения релаксированной задачи Вебера для дерева	228
В. Л. Миронов	Хроматическая единственность графов	233
Т. А. Панюкова	Построение эйлеровых циклов специального вида в планарном графе	235
А. В. Пастор	Об удалении ребер из k-связного графа без потери k-связности	237
А. Л. Пережогин, В. Н. Потапов	О числе гамильтоновых циклов в гиперкубе	240
Л. П. Петренюк	О барвинках в полном графе	242
В. К. Титов	Аксиоматический подход в теории графов	244
А. В. Угланов	Об асимптотической длине одного случайного графа	246

Секция "Дискретная геометрия"

М. М. Анзин, А. И. Каишев	Вычисление окрестности Г. Ф. Вороного для второй совершенной формы	248
М. Б. Банару, Г. А. Банару	О спектрах некоторых тензоров уплощающихся 6-мерных эрмитовых подмногообразий алгебры Кэли	250
Р. Г. Барыкинский	W-разбиение, его связь со строением совершенного полиэдра Рышкова и образованием совершенных форм	253
Н. М. Глазунов	Об алгебраических кривых над конечными полями, простарнствах модулей и дзета-функциях	256
В. П. Гришухин	Область L-типа двойственной корневой решетки DN*	259
Д. В. Груздев	Описание множеств f-векторов триангуляций 4-мерного куба, распределений объема 4-мерного куба по симплексам его триангуляций и их взаимосвязи	260
Г. А. Карпунин	Минимальные сети на правильном d-мерном симплексе	261
О. М. Касим-Заде	О минимальных разбиениях плоских прямоугольников на квадраты	263
М. Д. Ковалев	Ядерные многообразия изостатических отображений	265
Я. В. Кучериненко	О взаимной ориентации двух фигур в R3	268
В. С. Макаров, Ф. Л. Дамиан	О линзовых многогранниках	271
П. В. Макаров	Об одной счетной серии кристаллографических разбиений пятимерного пространства Лобачевского	274
А. А. Ордин	Обобщенное барицентрическое разбиение треугольника и полугруппы мебиусовых преобразований	278
С. C. Рышков	Коренные параллелоэдры и вершины областей типа N-мерных параллелоэдров	279
В. Н. Шевченко	Жорданова форма матрицы инциденций булеана	281
Р. М. Эрдал	Дайсинги и параллелоэдры	283
Е. И. Яковлев, П. А. Гордиенко	Быстрые алгоритмы вычисления групп гомологий и их базисов	284

ЧАСТЬ III

Секция "Теория кодирования и математические вопросы криптографии"

В. М. Амербаев, Ю. И. Кожухова	Китайская теорема об остатках и ранцевая система шифрования	291
И. М. Арбеков	Применение кодов, корректирующих ошибки, в квантовых криптографических схемах	292
В. С. Бельский, А. А. Сальников	Построение кубических бент-функций	297
А. Н. Велигура	Системы линейных неравенств, задающих выпуклые оболочки некоторых кодов }	300
М. М. Глухов-мл.	О кодах Гоппы на кривой y^2=x+x^{q^{n/2}}	303
А. Я. Дорофеев	Оценка количества целых чисел без больших простых и примарных делителей	305
Л. П. Жильцова	О возможностях обобщения результатов Шеннона на кодирование стохастических контекстно-свободных языков	308
Д. О. Киселев	Факторизация и дискретное логарифмирование	312
О. А. Логачев, А. А. Сальников, В. В. Ященко	Нормальная форма отображений конечных абелевых групп	315
О. А. Логачев, А. А. Сальников, В. В. Ященко	Оценки некоторых параметров отображений конечных абелевых групп	318
О. А. Логачев, А. А. Сальников, В. В. Ященко	Эквивалентности многочленов и оценки тригонометрических сумм	321
М. А. Пудовкина	Свойства алгоритма поточного шифрования IA	323
А. Ю. Серебряков	О тождествах МакВильямс для орбитных кодов	325
В. М. Сидельников	Об одном классе ортогональных многочленов, связанных с символами Лежандра	328
Ю. В. Таранников	Об автокорреляционных свойствах корреляционно-иммунных функций	331

Секция "Комбинаторный анализ"

С. Л. Бердов, В. Л. Дольников, Д. В. Карпов	Об одном обобщении теорем Кенига и Вильфа - Секереш	334
Л. Н. Бондаренко	Перманенты и "аддитивные" задачи перечисления перестановок	335
Т. А. Бурдюк	Упорядочение транспортных потоков	338
А. О. Воробьев, О. Ю. Воробьев	Генерирование случайного конечного множества	339
Э. Гирлих, М. М. Ковалев, В. М. Котов	Semi on-line алгоритм для задачи разбиения	343
Н. С. Григорьева	Алгоритм построения расписаний для многопроцессорной системы	346
С. И. Дзюбко	Обобщенные конструкции приращений и некоторые их приложения	348
В. А. Емеличев, В. Г. Похилько	О радиусе сильной квазиустойчивости векторной задачи на подстановках	350
В. А. Емеличев, Ю. В. Степанишина	О квазиустойчивости векторных комбинаторных задач с мажоритарным принципом оптимальности	353
А. В. Ефимов	К решению полудискретных экстремальных задач	355
Д. И. Коган	Синтез экстремальных коалиционно устойчивых решений в задаче простого обмена групповой структуры	357
Д. И. Коган, Ю. С. Федосенко	Экстремальные задачи однофазного обслуживания детерминированного потока заявок	360
Л. М. Коганов	Об одном вопросе Р. И. Григорчука и связанных с ним задачах	363
Н. А. Колокольникова	Цепи Маркова с двумя состояниями и комбинаторные числа	364
М. К. Кравцов, Е. В. Лукшин, В. М. Кравцов	Характеризация нецелочисленных вершин многогранника трехиндексной аксиальной задачи о назначениях	367
О. В. Кузьмин	Полиномы разбиений в обобщенной пирамиде Паскаля	370
О. В. Кузьмин, О. В. Леонова	Некоторые свойства полиномов Тушара	376
А. А. Лазарев, А. Г. Кварацхелия	Стохастическое исследование методов ветвей и границ для NP-трудной задачи теории расписаний минимизации суммарного запаздывания для одного прибора 1|| S Tj	379
А. А. Лазарев, Р. Р. Садыков	Эффективность полиномиального алгоритма O(n3log n) для решения NP-трудной проблемы теории расписаний минимизации максимального временного смещения 1| rj| Lmax	381
В. Е. Маренич	Свойства отношения сопряжения функций инцидентности	384
Е. Е. Маренич	Максимальные антицепи в дистрибутивных решетках	387
Ю. В. Никулин	Анализ чувствительности векторных лексикографических задач квадратичного булева программирования	393
Р. А. Оганян	Линейные диофантовы уравнения с двухсторонними ограничениями	395
А. В. Пашкевич	Векторные дискретные задачи: параметризация принципа оптимальности и условия разрешимости в классе алгоритмов линейной свертки критериев	398
А. М. Ревякин	Характеризация геометрических (матроидных) решеток с помощью функций Мебиуса	401
С. В. Попов	Операционные семантики логических формул	405
А. Н. Черепов, И. А. Черепов	Классы сохранения оснований и соответствие Галуа в многозначных логиках	410