Введение к работе
Актуальность темы.
Работа посвящена изучению сложности ряда задач группового тестирования и доказательству теорем существования оптимальных алгоритмов решения этих задач.
Групповое тестирование является областью вычислительной математики, имеющей дело с построением экономных алгоритмов уменьшения числа переменных в задачах, когда общее число переменных велико, а число существенных переменных мало. Задачи группового тестирования впервые сформулировал R.Dorfman в связи с проведением медицинских обследований больших групп людей. В развитие данной области математики большой вклад внесли такие ученые как P.Erdos, A.Renyi, M.Sobel, J.N.Srivastava, А.Г.Дьячков, М.Б.Малютов, Л.Д.Мешалкин, В.В.Рыков.
В работе рассматриваются только статические (неадаптивные) алгоритмы. Последовательные алгоритмы группового тестирования (то есть алгоритмы, в которых выбор следующей тестовой группы зависит от результатов предыдущего теста) часто требуют меньшего числа итераций. Однако в некоторых моделях статические алгоритмы более удобны. С развитием параллельных вычислений исследование статических алгоритмов стало особенно актуальным, так как именно параллельные вычисления позволяют проводить большое количество тестов одновременно.
Цель работы. Целью работы является получение оценок сложности задач группового тестирования, вычисление верхних границ оптимальных алгоритмов и их обоснование.
Методы исследования. В работе применяются методы теории вероятностей и комбинаторики, математического анализа и теории дискретного поиска.
Научная новизна. В работе предложено применить методы теории поиска для оценки сложности ряда задач группового тестирования. Получены теоремы существования статических алгоритмов и верхние границы длин оптимальных алгоритмов. Решены задачи оптимального выбора размера тестовых множеств для получения наилучших верхних границ. Кроме классических задач группового тестирования, исследова-
ны некоторые другие задачи, рассматриваемые как задачи дискретного поиска. Для них также получены теоремы существования статических алгоритмов и верхние границы этих алгоритмов.
Практическое значение. Модели группового тестирования имеют широкие приложения в технике, медицине, применяются в теории сложности, теории графов, а также при создании обучающих моделей. ^^Апробация работы. Результаты -исследований -докладывалисьпа" международном семинаре "Mathematical Methods and Tools in Computer Simulation1'(Санкт-Петербург, 1994); Всероссийской конференции "Параметры перспективных транспортных систем" (Москва, 1994); на научных семинарах кафедр статистического моделирования и теоретической кибернетики.
Публикации. По теме диссертации опубликовано четыре работы.
Объем работы. Диссертация состоит из введения, четырех глав и заключения, изложена на 85 страницах. Список литературы - 55 наименований.
