Теоремы существования статических алгоритмов группового тестирования тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

Карасева ЛюТйШз "Эдуардовна

ТЕОРЕМЫ СУЩЕСТВОВАНИЯ СТАТИЧЕСКИХ АЛГОРИТМОВ ГРУППОВОГО ТЕСТИРОВАНИЯ

Специальность: 01.01.07 - вычислительная математика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

САНКТ-ПЕТЕРБУРГ

1997 г. . „ „

О

Работа выполнена в Санкт-Петербургском государственном университете

Научный руководитель:

доктор физико-математических наук, профессор А.А.Жиглявский Официальные оппоненты:

доктор физико-математических наук, профессор И.В.Романовский кандидат физико-математических наук Д.Ф.Кузнецов

Ведущая организация: Санкт-Петербургский институт кино и телевидения

седании диссертационного совета Д 063.57.30 по защите диссертаций на соискание ученой степени доктора физико-математических наук в Санкт-Петербургском государственном университете по адресу: 198904, г.Санкт-Петербург, Петродворец, Библиотечная площадь, дом 2, математико-механический факультет СПбГУ.

С диссертацией можно ознакомиться в Научной библиотеке Санкт-Петербургского государственного университета по адресу: 199034, г.Санк Петербург, Университетская набережная, дом 7/9.

Автореферат разослан

Ученый секретарь

диссертационного совета Д 063.57.30

кандидат тех. наук, доцент Ю.А.Сушков

Защита состоится

года в

часов на за-

/у

Общая характеристика работы.

Актуальность темы.

Работа посвящена изучению сложности ряда задач группового тестирования и доказательству теорем существования оптимальных алгоритмов решения этих задач.

Групповое тестирование является областью вычислительной математики, имеющей дело с построением экономных алгоритмов уменьшения числа переменных в,задачах, когда общее число переменных велико, а число существенных переменных мало. Задачи группового тестирования впервые сформулировал П.Вогйпап в связи с проведением медицинских обследований больших групп людей. В развитие данной области математики большой вклад внесли такие ученые как Р.Ег(16й, А.Непу!, М.ЗоЬе1, Л.К.Бгт^ауа, А.Г.Дьячков, М.Б.Малютов, Л.Д.Мешалкин, В.В.Ркков.

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

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

Методы исследования. В работе применяются методы теории вероятностей и комбинаторики, математического анализа и теории дискретного поиска.

Научная новизна. В работе предложено применить методы теории поиска для оценки сложности ряда задач группового тестирования. Получены теоремы существования статических алгоритмов и верхние границы длин оптимальных алгоритмов. Решены задачи оптимального выбора размера тестовых множеств для получения наилучших верхних границ. Кроме классических задач группового тестирования, исследова-

ны некоторые другие задачи, рассматриваемые как задачи дискретного поиска. Для них также получены теоремы существования статических алгоритмов и верхние границы этих алгоритмов.

Практическое значение. Модели группового тестирования имеют широкие приложения в технике, медицине, применяются в теории сложности, теории графов, а также при создании обучающих моделей.

Апробация работы. Результаты исследований докладывались на международном семинаре "Mathematical Methods and Tools in Computer Simulation"(Санкт-Петербург, 1994); Всероссийской конференции "Параметры перспективных транспортных систем" (Москва, 1994); на научных семинарах кафедр статистического моделирования и теоретической кибернетики.

Публикации. По теме диссертации опубликовано четыре работы.

Объем работы. Диссертация состоит из введения, четырех глав и заключения, изложена на 85 страницах. Список литературы - 55 наименований.

Содержание работы

Во Введении кратко изложена актуальность темы исследования и дано описание решаемых задач.

В Главе 1 в разделе 1.1 сформулирована задача группового тестирования в общем виде. Предположим, что у нас есть п переменных (элементов) xi,...,xn с несколькими фиксированными переменными х,м обладающими некоторым свойством, отличающим их от всех других, (существенными переменными), количество которых к и номера ..., ¿¿, вообще говоря, неизвестны. Набор существенных переменных будем называть целевой группой. Для их поиска проводятся N тестов, каждый из которых состоит в следующем: выбирается некоторое подмножество элементов множества Х_ --- {zi,... ,£„}, которое называется тестовой группой и на этой группе производится некоторая проверка.

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

Поскольку все задачи будут рассматриваться как задачи поиска, в разделе 1.1 даны некоторые определения из теории дискретного поиска.

Задачей дискретного поиска называется тройка {Т, X, /}, где Т={Т}

— множество целевых групп, то есть набор всех возможных целей Т, X = {X} — множество тестовых множеств, то есть набор всех возможных тестовых групп, и / : X х Т —V У — тестовая функция, отображающая X х Т в некоторое пространство у.

Значение /(Х,Т) для фиксированных X 6 X и Т 6 Т есть результат проверки, в которой тестируется группа X, в задаче поиска целевой группы Т. Поскольку в задачах группового тестирования X \\ Т являются некоторыми наборами групп переменных, далее целевое множество называется целевой группой, а тестовое множество — тестовой группой. Рассмотрены задачи, в которых Т есть <?( или Я<л и аналогично X — это

или (?<5. Здесь \ < Ь < п, 1 < з < тг, п — общее число переменных,

к

&к={{х,\,...,х,-к}, 1 < ¿1 < ...гц.<п) д<к=ид3- (1)

у=0

— множества всех групп переменных, содержащих ровно к элементов и не более к элементов, соответственно. Обозначим М = \Т\,Я = \Х\, где |.А| обозначает количество элементов в множестве А.

Для нахождения целевой группы необходимо, чтобы ее можно было отличить от всех других элементов множества Т. Целевая группа (цель) Т € Т называется различимой с любой другой целевой группой Т" € Т, если существует тестовая группа X £Х, такая что /(X, Т) ф /(Х,Т). Задача поиска {Т, X./} называется разрешимой, если каждое целевое множество Т £ Т является различимым с любым другим целевым множеством.

В разделе 1.2 ведено определение статического алгоритма и сформулированы теоремы существования алгоритмов однозначного восстановления (строго разделяющих алгоритмов) и алгоритмов восстановления с вероятностью 1-7 (7—разделяющих алгоритмов) в задачах дискретного поиска.

Статическим алгоритмом длины N называется набор тестовых групп Х\[ — ..., Х-,-}, которые выбираются до начала наблюдений.

Для того, чтобы алгоритм Хы находил неизвестную нам цель Т, принадлежащую множеству целей, он должен быть алгоритмом однозначного восстановления. Алгоритм Хц={Х\,... называется разделяющим Т в Т, если для любого Т £ Т, Т'фТ существует тестовая группа X € A'jv, которая разделяет пары (Т,Т'), то есть f(X,T)^f(X,Tl). Алгоритм Хц называется алгоритмом однозначного восстановления, если он разделяет все целевые группы Т из Т-

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

Теорема 1.3.1 (Теорема существования алгоритмов однозначного восстановления.) Пусть (T,X,f) —разрешимая задача поиска, и пусть для фиксированных Ti,Tj 6 Т (1 < j < i < М), k{j=k(Ti,Tj) — количество X 6 X, таких что f(X,Ti)=f(X,Tj), то есть

ktj = \{ХеХ : f(X, Ti) = f(X, Tj)}\ для ThTj er. (2)

Тогда существует статический алгоритм однозначного восстановления, число шагов которого

( М i-l fh..\l 1

N < N* = min = 1,2,... ЕЕ < l} • (3)

Вычисляя (2) для конкретных задач поиска и подставляя их в формулу(З), во второй, третьей и четвертой главе получены доказательства существования алгоритмов однозначного восстановления Хм длины N < N*.

Алгоритм Хм называется алгоритмом восстановления с вероятностью 1—7, если

I {Г € Т : алгоритм X¿v разделяет Т в Т} I

-m->1-7,

где 7 — фиксированное вещественное число, 0 < 7 < 1. В тех случаях, когда можно удовлетвориться алгоритмом, который разделяет цели в большинстве случаев, используются алгоритмы восстановления с вероятностью 1 — 7.

Теорема 1.3.2 (Теорема существования алгоритмов восстановления с вероятностью 1—7.) Пусть (Т, X, /) —разрешимая задача поиска, ку (г,1,2,... , М) определены выражением (2). Тогда существует, статический алгоритм восстановления с вероятностью 1—7 длины

Далее алгоритмы однозначного восстановления будем называть строго разделяющими, а алгоритмы восстановления с вероятностью 1 — 7 — 7—разделяющими. В разделе 1.3 приведены некоторые нижние границы статических алгоритмов решения задач поиска. Далее сформулированы и доказаны теоремы, описывающие свойства множества целевых групп.

Пусть 0 <р<т<1<п, р<1. Возьмем € 0<п х &<п-

Обозначим

В Теореме 1.5.1 число различных неупорядоченных пар в множестве Т{п,1,т,р) выражено через мультиномиальные коэффициенты.

В разделе 1.6 приведена общая теорема, которая далее применяется для нахождения асимптотических границ алгоритмов.

Теорема 1.6.1 Пусть I некоторое целое число, (г=1,...,/)

— некоторые вещественные числа, с;>0, 0<г,<1, по крайней мере одно из значений а,- положительно, {д^п}» {г>'.п} — семейства положительных чисел (1=1, ••■,/, п=1,2,...), таких что

N < ют

(4)

7>, /, т,р) = {(Т{, Т5) :Щ\ = 1к |1}| =тп & Щ П Г3 | = р}.

?(,П = С{Па'( 1 + 0(1)), = г,- + о

1

к^п

П —> СО ,

I

N = N(71) — В1Ш <¿=1,2,... Е?.>г£„ <1[,

(5)

1=1

Ь — £<(п) — решение уравнения

=1, С —

(6)

с — решение уравнения "Е,^ с;г| = 1} где 3 — то подмножество множества {1,...,/}, на котором достигается максимум в (6). Тогда Щп) ~ \_£>(п)\ +1 для есез; п и Ь{п) — С1о§п + с + о(1), при п —» оо.

В Главе 2 подробно рассматривается аддитивная количественная модель группового тестирования, в которой }{Х,Т) = ¡ХпТ|. В этой главе вычислены верхние границы длин оптимальных алгоритмов и получены их асимптотические выражения.

В разделах 2.1 - 2.3 рассмотрены некоторые частные случаи аддитивных задач, в которых на конкретных примерах показан метод получения аналитических выражений для коэффициентов Реньи.

В разделе 2.4 введено понятие а—сбалансированных тестовых множеств. Пусть (Т,Т') е Т(п,1,гп,р), и X 6 Xгг(Т,Т'), где

Хдг{Т,Т')={Х : |ХПГ)=|ХПГ'Н>0 & \ХП{ТПТ')\=г>д}

где qn г - некоторые целые числа, такие что

0<р<гп<1<п, р <1, 0 < г < <? < тп.

Будем называть тестовое множество X а—сбалансированным, если число |Л^Г(Т,Т")|, которое мы обозначим 11(п,1,т,р,д,г), не зависит от выбора конкретной пары (Т,Т") € Т(п,1,т,р).

Теорема 2.4.1 Пусть 0<р<т<1<п, р<1, X - а—сбалансированное тестовое множество и выберем пару целевых групп Т{,Т^£Т(п,1,т,р). Тогда

р. т—р+г г=0 Ч~г

и значение коэффициента к^ одинаково для всех пар целевых групп

Используя этот результат можно представить верхнюю границу Лг* в следующем виде:

Аг* = пип4:£ £ д(щ1,т,р)(^ЕЛ(п,1,т,Р>д,г)) <1}

V {,тр<т,р<1 \П г=0 <?=г / >

где первое суммирование ведется по 0<т<1<Ь для случая Т—9<г, и его следует опустить для Т= положив тп~1 — Аналогичная формула имеет место для границ 7—разделяющих алгоритмов.

В разделе 2.5 показано, что тестовые множества Х=де и Х=0<а являются а—сбалансированными и даны формулы для П(п,I, тп,р, <7, г).

В разделе 2.6 приведены теоремы существования алгоритмов аддитивного группового тестирования для некоторых конкретных задач. .

Следствие 2.6.1 Пусть Т—Яь и Х—<5е, где п>2, 1 <1<п, 1 <8<п. То-

1

гда существует статический алгоритм аддитивного группового тестирования, длина которого N < Аг* = £, в), где

и существует статический 7—разделяюищй алгоритм длины N < N* = iV-Дп, t, s), где

Аналогичные результаты сформулированы для случаев T~Q<t и X—Qs, п>2, 1 < t < п, 1 < s <п, а также Т = (?< п X = Q<s,

В разделе 2.7 рассмотрено асимптотическое поведение N* при большом общем числе факторов п и решена задача оптимального выбора размера тестовых групп.

Теорема 2.7.1 Предположим, что X — Qs, T==Gi, t> 2 - фиксировано, п —> оо, 5 = з(п) — \п + 0(1) при п —»оо, 0 < А < 0 < 7 < 1. Тогда N(n, t, s) = А) + o{l)"j, при n oo, где

1Г(щf, An) = t, A) ~ fiA((i +1) log2n-log2(i - 1)!—l)] , (9)

N^(n,t,n/ 2) =

t log2n-log2i7

+ o(l)

(10)

2i-log2(2i)'.+21og2i!

где g\ = l/(—log2(A2+(l—А)2)) и минимальная величина константы g\

Формулы (8) и (10) при А = 1/2 дают верхние оценки асимптотической сложности задачи аддитивного группового тестирования.

В Главе 3 рассмотрена бинарная модель группового тестирования, для которой f(X, Т) = min{l, \Х П Т|} и вычислены верхние границы длин оптимальных статических планов.

В разделе 3.1 приведены простейшие нижние границы для задач бинарного группового тестирования. В разделе 3.2 введено понятие Ь—сбалансированного множества тестовых групп и выведены формулы для верхних границ оптимального алгоритма бинарного тестирования для множеств целевых групп (1). Пусть (Т, Т') G T{n,l,m,p), и определим множество X € Л«,;г(Т,Т') следующим образом

Xuvr^{X :\ХП(Т\{ТПТ')\=и к \ХП{Т'\(ТПТ')|=w к |ХП(ТПТ')|=г},

где и, ь и г некоторые целые числа, такие что

г<р<т<1<п, р<1; 0<и<1—р, 0<и<т—р, 0<г<р.

Будем говорить, что тестовое множество X является Ь—с балансированным. если количество элементов \ХтТ(^Г,Т")|, которое обозначим Д(гг,/, т,р, и, V, г), не зависит от выбора (Т,7ч) € Т{п,1,тп,р).

Теорема 3.3.1 Пусть 0<р<т<1<п, р<1, X - Ь—сбалансированное тестовое множество и Т;,7) £ Т(п,1,т,р) - фиксированная пара ■целевых групп. Тогда

hj = й — R(n,l,m,p,u,Q,Q) + £ R{n,l,m,p,Q,v, 0) j (11)

и значение коэффициента к^ одинаково для всех (Г,-,7)) € Т{п,1,т,р).

В соответствии с полученными результатами можно записать формулу для ЛГ*:

равна 1 и достигается при А—I.

Я* =тшЬ = 1,2,...: £ £ Я{п,1,т,р):

* 1,т 0<р<т

к'

X

/ '-Р "1-р \к

Е Д(п,/,т,р,и,0,0) + Е

^ _ ц=1__________

я

<1 (12)

/

где первое суммирование ведется по 0 < т < / < £ в случае Т = £?<( и / = тп = £ (то есть первое суммирование в (12) опускается) для случая Т=бс Аналогичная формула имеет место для Лг7.

В разделе 3.4 рассмотрены примеры 6—сбалансированных тестовых множеств и получены выражения для В.(п,1,т,р,и,у,г).

В разделе 3.5 приведены теоремы существования для некоторых алгоритмов бинарного тестирования, которые являются следствиями из полученных в предыдущих разделах результатов.

Следствие 3.5.1 Пусть Т = и Х — 0В, где п> 2, 1< £<п, 1<з<п. Тогда существует статический алгоритм бинарного группового тестирования, длина которого N < М* = ¿У*(п,£, й), где

} 2 ¿Го г-р ь-р п-к+р) \ (") / 1

Приведены также аналогичные результаты для строго и 7—разделяющих алгоритмов для случаев Т — £<( и X = £?5, Т = и X — а также Т = и X — Я<п.

В разделе З.б получены асимптотические формулы для коэффициентов Реньи при фиксированном I и п оо.

В разделе 3.7 рассмотрен асимптотический вид верхних границ статических алгоритмов. Рассмотрены случаи Т = й и Т = где £ > 2 является фиксированным целым числом, при этом предполагается, что X — 05, общее число факторов п стремится к бесконечности, в = й(п) = Ап + 0(1), при п —> оо, А - некоторое фиксированное число из (0,1). Для различных соотношений между А и £ можно записать

а

различные формулы для верхних границ, но рассматриваются только те значения Л, которые дают наименьшую асимптотическую верхнюю границу ЛГ(п, t, в) и N(n, < Ь, в).

Теорема 3.7.1 Предположим, что X = 0„ Т — Яц t >2 - фиксировано, п —> оо, я — я(п) = Ап + 0(1) при п —> оо, О < Л < \. Тогда N(71, в) = + о(1)] при 72 —^ оо, гс>е

* (П'4'А) ---1о6(1-2А(1-А)<)-• {13)

Теорема 3.7.2 Предположим что X = 0г, Т — Ь > 2 - фиксировано, п —> оо, 5 = 5(гс) = Атг +0(1) при п —} оо,

О < А < Тогда = ^А)+о(1)"|, когда п оо, где

дК®3)(п <t X) —_ljogn-Iog(t-l)j_

(14)

Следствием этих теорем являются хорошо известные асимптотические формулы, полученные А.Г.Дьячковым и В.В.Рыковым ("Проблемы передачи информации", 1982 вып. 3 с.7-13).

В разделе 3.8 получена асимптотическая верхняя граница для 7—разделяющих статических алгоритмов при оптимальном выборе размера тестовых множеств.

Теорема 3.8.1 Пусть Т = Qt или Т = G<t, t > 2 - фиксировано, X —Gs, - фиксировано, 0<7<1, A( = l- s ~ s(n) = A tn + 0( 1) при п оо. Тогда N7(n,t,s) = [Л^ (71, f) + о(1)] и Щ(п,< t,s) -\N^(n,t) + о(1)] при п-+со, где

iVf)(n,i)=ilog2n-log27+c, (15)

где с — решение уравнения £р=о = 1, и такой выбор размеров

тестовых множеств является оптимальным.

В Главе 4 вычислены верхние границы длин оптимальных алгоритмов для некоторых других задач, которые можно сформулировать как задачи группового тестирования.

В первом разделе рассматривается задача о канале с множественным доступом, где тестовой функцией является f{X,T)~ min{2, |ХЛТ|}. Множества целевых и тестовых групп в данной модели имеют тот же вид, что и в задачах бинарного и аддитивного количественного тестирования. Приведены формулы для коэффициентов % и сформулирована теорема существования.

Следствие 4.1.1 Пусть T=Gt и X=GS, где п>2, 1 <t<n, 1 <s<n. Тогда существует статический алгоритм группового тестирования, число шагов которого 'N < N* — N*(n, t, s), где

{ 2 P=0\p t - p t - p n - 2t + p

l (!) " (!) I J

Далее рассмотрено асимптотическое поведение N* в том случае, когда общее число факторов п велико.

Теорема 4.1.3 Предположгш, что X — Qs, T—Gt, t>2 -фиксировано, n —> со, s = s(n) = An+0(1) при n —» oo, O < A < 1. Тогда N{n,t,s) = |7V(as)(n, í, A) + о(1)] при тг со, где

ЛГМГ„ f ^ (t + l)logn-log(f-l)!-Iog2 N (n'a)==-bg(l-2A(l-A)^)(i + A(t-2))- (16)

Оптимальным размером тестовых множеств в этом случае будет s=A*n, где А*—(—í+4—\/5¿2—12í+8)/(—2¿2+2í+4).

Теорема 4.1.4 Предположим, что X — Gs, Т = G<t, t > 3 - фиксировано, п -4 оо, s — s(n) = Ап + 0(1) при п —> оо, 0 < А < 1. Тогда N(n,t,s) - \N^{n,t,X) +о(1)] когда поо, где

МЫ(„ , \\__¿logn — log(¿ - 1)!

В данном случае, оптимальное значение параметра А = А* равно A*=(3-t-V5t2-14t+9)/(4t-2i2).

В разделе 4.2 главы 4 рассмотрена задача о поиске фальшивых монет при взвешивании на весах без стрелки. При этом введено более общее, чем в первой главе, определение задачи поиска. Приведены теоремы существования для двух частных случаев задачи о взвешивании. Рассмотрена задача о фальшивой монете в случае, если известно, что фальшивая монета легче остальных. Далее исследовано асимптотическое поведение коэффициентов Реньи и найден оптимальный размер тестовой группы.

В разделе 4.3 изучена игра, известная под названием "Mastermind" или "Быки и коровы". Цель этой игры - найти упорядоченный набор d символов, <i > 2, выбранных из некоторых набора п символов, которые занумерованы 0,1,..., п — 1. В этой задаче

Д-=Г = {0 = (0h...,ed): MjG{ 0,...,n-l}, 0,- ф Oj при i ^ j} ,

R = |A'| — n(n — 1)... (n — d + 1). Значением тестовой функции f(X,T) для данного тестового множества X = {х\,... ,х/) и целевого множества Т — (ij,..., td) является упорядоченная пара f{X,T) — (Ь,с), где

Ь— | {г : T,i—ti} |, с— | {г: Xi=tj для некоторого j, l<j<ri,}фг\|

Верхняя граница статических алгоритмов выглядит следующим образом:

Коэффициенты {гпи, ки}^=1 вычислены аналитически для двух частных случаев: d = 2,3.

В Заключении кратко сформулированы основные результаты работы.

Основные результаты работы

1) Доказаны теоремы существования статических алгоритмов однозначного восстановления и восстановления с вероятностью 1 — 7 в классических задачах аддитивного и бинарного тестирования.

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

3) Вычислены верхние границы оптимальных алгоритмов в задачах о канале с множественным доступом, о фальшивой монете и "Mastermind".

4) Решены задачи выбора оптимального размера тестовых множеств для получения наилучших верхних границ в задачах аддитивного и бинарного тестирования, задаче о фальшивой монете и задаче о канале с множественным доступом.

Список публикаций

1. Zabalkanskaya L.E. Existence theorems for additive group testing strategies // Proc. of the MMTCS-94 (Ed. S.M.Ermakov). SPbGU, 1994. C. 26.

2. Zhigljavsky A.A., Zabalkanskaya L. Existence theorems for some group testing strategies // Journal of Statistical Planning and Inference. 1996. V.55, No 2. P. 151-173.

3. Забалканская Н.Э. Оценка числа шагов алгоритмов аддитивного группового тестирования // Математическое моделирование дискретных систем (Выч. техника и вопросы кибернетики; вып.28) Под ред. М.К.Чиркова 1995. С. 139-146.

4. Забалканская Л.Э. Оптимальная стратегия группового тестирования // Всеросс. конф. "Параметры перспективных транспортных систем." Москва, 1994. С. 69.

Подписано к печати 07.02.1997. Заказ ЯРЛ Тираж 100 экз. Обьем 1 п.л. Печ-множ. лаб. НИИХ СПбГУ. 198904 Санкт-Петербург, Ст.Петергоф, Университетский пр.2