Введение к работе
Актуальность темы. Проблема поиска занимает важное место в информационном обществе. В большом потоке информации, циркулирущем по информационным каналам, необходимо выделять требуемые сведения. При этом принципиально важно оптимизировать время поиска и затраты ресурсов. Важнейшими примерами являются поиск неисправностей в больших технических системах, данных в больших архивах хранения информации, поиск ошибок при передаче сообщений в системах связи и ЭВМ.
С другой стороны, во многих явлениях, зависящих от большого числа факторов, существенными или значимыми является относительно небольшая часть из них, влияние кэ остальных незначительно и ими можно пренебречь. В таких случаях возникает задача поиска этих существенных факторов.
Разработкой методов, теории и практики поиска занимается математическая теория поиска, являщаяся составной частью теоретической информатики. При этом теория поиска использует методы и идеи дискретной математики, теории информации, математической статистики, алгебры и теории чисел.
Большой вклад в разработку теории решения задач поиска внесли А.Г.Дьячков, Г.Катона, М.Б.Малготов,- Л.Д.Мешалкин, А.Реньи.
Для решения ряда задач поиска проводятся эксперименты, которые называются отсеивающими. При этом желательно минимизировать экспериментальные и вычислительные затраты. Разработкой методов отсеивания существенных факторов занимается раздел математической теории поиска, называемый планированием отсеивающих экспериментов.
Диссертационная работа посвящена одному из направлений в теории планирования отсеивавдих экспериментов. Это направление связано с поиском существенных факторов в линейной модели. В данной модели рассматривается линейная функция вида
у = 9^ +...+ 9n^n , (1)
в которой з<п коэффициентов из 8.J,..., 6п отличны от нуля.
Необходимо найти номера этих существенных или значимых коэф-
-2~
фициентов и их значения.
Для решения этой задачи поиска проводятся mm тестов. В каждом тесте переменные х^, ,/=1,...,п принимают значения из фиксированного множества {0,1,...,д-П, называемого алфавитом. В практических приложениях также используются алфавиты
вида {-1,...,-1,0,1 1), либо {-1,...,-1,1,...,1). В этом
случае полагают д=21+1, либо q=2l соответственно. В результате получают систему линейных уравнений вида
У(Э)=Х-В, (2)
где X=|z j, zt С0,1 q-U, 6=(8.,,...,9^, =1,...,m,
J=1 п, причем только а<п компонент вещественного вектора
8 отличны от нуля.
Матрицу X называют матрицей плана эксперимента и она для решения системы (2) должна обладать свойством разделения: для любых векторов G{1V 0(2-', у которых не более чем а ненулевых координат и у которых координаты принадлежат, возможно, некоторому подмножеству множества вещественных чисел, имеет место Х'8(1V І-Є(2).
Первоначально были предложены эвристические алгоритмы поиска существенных факторов в (1), основанные на методе случайного баланса1, который является сочетанием метода случайного конструирования матрицы плана X и упрощенного метода пофакторного анализа.
Л.Д.Мешалкин обнаружил2, что при выборе существенных
коэффициентов линейной функции вида (1) из абсолютно непре
рывного s-мерного распределения возможно построение матрицы
вида X для решения системы (2), обладающей свойством разде
ления для одного подмножества множества индексов {1 п).
При этом матрица плана X должна обладать следующим алгебраическим свойством: столбцы матрицы с номераьш, совпадающими с номерами существенных факторов, должны быть линейно неза-
1Satterthwaite Р.Е. Random Balance Experimentation // Technometries. 1959. Ш.
2Мешалкин Л.Д. К обоснованию метода случайного баланса // Заводская лаборатория. 1970. Вып.З. С.316-318.
висимы, а каждый из оставшихся столбцов лшейно не зависит от указанных столбцов. При
т > з + log^n-a+l) - Ю^р (3)
возможно построение двоичной матрицы с вышеуказанным свойством, причем доля соответствующих матриц в общем ансамбле тхп двоичных матриц не меньше 1-р, G
В общем случае для решения системы (2) необходимо и достаточно., чтобы матрица X обладала следующим свойством: любые 2з ее столбцов должны быть линейно независимы3. Матрицы g таким свойством называют Зз-невырожденнымл. Построе-ение таких матриц является сложной задачей. Необходимо также знать, при каких параметрах т,п и з существуют 2а-невырон-денше матрица.
М.Б.Малютов показал4', что при
т > 23+10^] (4)
существуют цып 2з-невырозденные двоичные матрицы. При этом доля таких матриц в общем ансвмбле двоичных матриц не меньше
Приведенные выше оценки (3)-(5) справедливы для любого поля, имеющего характеристику ноль либо простое число, однако они мало учитывают специфику вещественных матриц.
3Srlvaatava J.N. Designs for searching nonnegllgable effects / In: A survey of statistical designs and linear models. Amsterdam: North-Holland Publ., 1975. P. 249-256.
4Малютов М.Б. Математические модели и результаты в теории отсеивающих экспериментов / Вопросы кибернетики. М.: Сов. радио. 19Т7. Вып. 35.
28-Н8Выровденные целочисленные матрицы применяются также в сетях ЭВМ для помехоустойчивой передачи информации, в частности, в многотерминальных системах для защиты от ошибок оператора5. В этом случав они порождают коды над полем рациональных чисел. Алгоритмы кодирования и декодирования передаваемой информации могут быть реализованы программным путем с помощью быстрой целочисленной арифметики.
Цель работы - изучение свойств линейных комбинаций векторов с компонентами из конечного целочисленного множества и получение ноеых оценок параметров существования матриц планов отсеиващих экспериментов с определенными алгебраическими свойствами.
Научная новизна. В работе получены новые оценки параметров матриц планов отсеиващих экспериментов с учетом специфики вещественных матриц с компонентами из конечного множества, которые улучшают некоторые полученные ранее результаты. Получены также оценки максимального числа решений одного целочисленного уравнения, связанного с комбинаторными и алгебраическими свойствами матриц планов экспериментов.
Методологическую основу работы составляют современные методы комбинаторного анализа, теории кодирования, целочисленного программирования.
Практическая значимость работы. Результаты диссертации вносят вклад в теорию планирования отсеивающих экспериментов и могут быть применены на практике при решении ряда задач поиска, которые возникают в технике, экономике, экологии.
Апробация работы. Результаты исследования докладывались на научно-методическом семинаре кафедры информатики и дискретной математики МИГУ им.В.И.Ленина, на международной конференции "Современные проблемы теории чисел" в г.Туле (сентябрь 1993 г.).
Структура и обьем диссертации. Работа состоит из введения, двух глав, заключения и списка использованной литерату-
Вычислительные сети (адаптивность, помехоустойчивость, надежность) / Самойленко СМ., Давыдов А.А., Золотарев В.В., Третьякова Е.И. М.: Наука. 1981.
-5-ры. Она содержит 102 страницы основного текста, 53 наименований использованной литературы.
