분리 행렬

수학에서 논리 행렬은 d-분산 및/또는 d-분리 가능한 것으로 설명할 수 있다.이러한 개념은 비적응 집단 시험의 수학 영역에서 중추적인 역할을 한다.

수학 문헌에서 d-분열 행렬은 겹침 코드^{[citation needed]} 또는 d-덮개가 없는 가족이라고도 할 수 있다.^[1]

첸과 황(2006)^[2]에 따르면

• 두 개의 d 열 집합이 동일한 부울 합을 가지지 않을 경우 행렬은 d-분리할 수 있다고 한다.
• 두 세트의 d-or-feer 컬럼이 동일한 부울 합을 가지지 않을 경우 $행렬$은 d$'{\$ - 구분$$(overline이 있는 d)이라고 한다.
• d 열 집합이 다른 단일 열의 상위 집합인 부울 합을 포함하지 않을 경우 행렬은 d-분산이라고 한다.

다음과 같은 관계가 "잘 알려진"^[2] 것이다.

• $d{\displaystyle \stackrel{}{}}$+ $'{\$ -분리$$ 가능한 매트릭스도 $d{\displaystyle }$ ${\displaystyle d}$ -disjunct$$.^[2]
• 모든 $d{\displaystyle }$ ${\displaystyle d}$ -disjunct$$ 매트릭스 역시 $d$의$$d $daystyle {\overline {d}$ -d}은(는) 분리할$$ 수 있다.^[2]
• 모든 ${{\$ -분리$$ 가능한 매트릭스도 $d{\displaystyle }$ ${\displaystyled}$ -분리$$(정의에 따라)이다.

구체적인 예

다음 $6{\displaystyle \mathrm{}}$ ${\displaystyle \times }$ ${\displaystyle 8}$ ${\displaystyle 6\time 8}$ 행렬은$$ 각 열 쌍의 합이 다르기 때문에 2-분리할 수 있다.예를 들어, 처음 두 열의 부울 합(즉, 비트 와이즈 OR)은 ${\displaystyle 110000}$00 ${\displaystyle 001100}$ = ${\displaystyle 111100}${ 111100 ${\displaystyle 1100\lor 001100=111100}$이다$.$ 이 합은 행렬의 다른 열 쌍의 합으로 얻을 수 없다.

그러나 열 1, 2 및 3(이름: ${\displaystyle 111111}${\$displaystyle 1111$의 합은 열 1, 4, 5의 합과 같기 때문에 이 행렬은 3으로 구분할 수 없다.

또한 1열과 8열(명칭 ${\displaystyle 110000}$ ${\displaystyle 110000$의 합이 1열의 합과 같기 때문에 이 행렬은 ${\$ 분리할$$ 수 없다.실제로 열이 0인 행렬은 $'{\$ $-d{\displaystyle }$ } -d ${\displaystyle \ge }$ ${\displaystyle 1}$ ${\displaystyle d\geq 1}$에 대해 분리할$$ 수 없다$.$

${\displaystyle \quad \left[{\begin{array}{cccccccc}1&0&0&1&1&0&0&0\\1&0&0&0&0&1&1&0\\0&1&0&1&0&1&0&0\\0&1&0&0&1&0&1&0\\0&0&1&0&1&1&0&0\\0&0&1&1&0&0&1&0\\\end{array}}\right]}$

다음 $6{\displaystyle \mathrm{}}$ ${\displaystyle \times }$ ${\displaystyle 4}$ ${\displaystyle 6\time 4}$ 행렬은$$ $3{\displaystyle \stackrel{}{\mathrm{}}}$ ${\displaystyle \stackrel{}{\times }}$ 4 ${\$ - 분리할$$ 수 있지만 3 분리할 수는 없다.

${\displaystyle \eft[{\put{array}{cccc}1&0&1&1&1&0\\0&0&0\0&0\0&0&0\0&0&0&0\nd{array}\right}}}}$

이 행렬에서 세 개 또는 더 적은 열을 선택하는 15가지 방법이 있으며, 각 선택은 다른 부울 합으로 이어진다.

기둥	부울 합		기둥	부울 합
없는	000000		2,3	011110
1	110000		2,4	101101
2	001100		3,4	111011
3	011010		1,2,3	111110
4	100001		1,2,4	111101
1,2	111100		1,3,4	111011
1,3	111010		2,3,4	111111
1,4	110001

그러나 2, 3, 4열(이름: ${\displaystyle 111111}$ ${\displaystyle 1111$의 합은 1열(이름: ${\displaystyle 110000}$ ${\displaystyle 110000})$의 상위 집합이며, 이는 이 행렬이 3분위가 아님을 의미한다.

그룹 테스트에 d-분리성 적용

비적응 집단 시험 문제는 우리가 어떤 품목에 대해 그 세트에 결함이 있는 품목이 포함되어 있는지 여부를 알려줄 수 있는 시험을 가지고 있다고 가정한다.우리는 n개의 총품목 묶음에서 모든 불량품목을 정확히 식별할 수 있는 일련의 그룹화 작업을 요청받았는데, 그 중 일부 품목은 불량품이다.

$t{\displaystyle }$ ${\displaystyle t}$ 행과$$ $n{\displaystyle }$ ${\displaystyle n}$ 열이$$ 있는 d ${\displaystyle d}$ -분리$$ 가능한 행렬은 t 검정을 사용하여 불량품 수를 정확히 d로 알려진 n 배치에서 찾는 방법을 간결하게 설명한다.

$t{\displaystyle }$ ${\displaystyle t}$ 행과$$ $n{\displaystyle }$ ${\displaystyle n}$ 열이$$ 있는 $d{\displaystyle }$ ${\$$d}$ -분리 가능한$$ 모든 $d{\displaystyle \stackrel{}{}}$ ${\displaystyle \stackrel{}{\text{'}}}$d$$''의 분리 행렬(또는 보다 일반적으로는 d'd'$style {d}$ -d} 행렬)은 t 검정을 사용하여 불량품목을 찾는 방법을 간략하게 설명하며, 여기서 불량품목의 수는 n 배치에서 알 수 있다.D에 지나지 않다

실제적인 우려 및 발표된 결과

제한에서, 주어진 n과 d의 경우, 가장 작은 d-분리 $t{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle n}$ ${\displaystyle t\times$ n$}$ 행렬의$$ t 행 수가 가장 작은 d-분산 t ${\displaystyle \times }$ ${\displaystyt time n}$ 행렬의$$ t 행 수보다 작은 경향이 있다.^{[citation needed]}그러나 행렬을 실제 시험에 사용하려면, 시험 결과(즉, $[\displaystyle 111100$와 같은 부울 합을 불량품(즉, 해당 부울 합을 생성하는 고유 열 집합)의 지수로 "디코딩"할 수 있는 일부 알고리즘이 필요하다.임의 d-분산 행렬의 경우 다항식 시간 디코딩 알고리즘이 알려져 있다. nauve 알고리즘은 $O{\displaystyle }$( ${\displaystyle n}$ ${\displaystyle t}$) ${\displaystyle O(nt)}$이다$.$^[3] 임의 d-분산 행렬의 경우, 가장 잘 알려진 디코딩 알고리즘은 지수 시간이다.^{[citation needed]}

Porat 및 Rothchild(2008)는 n열과${\displaystyle }$$\theta {\displaystyle \mathrm{}}$(${\displaystyle {}^{}}$ 2 ${\displaystyle \ln }$ ${\displaystyle }$ ${\displaystyle n}$) ${\$$displaystyle$ $O(nt)}$ -시간$$ 알고리즘을 제시하여 \(d ${\displaystyle {2\mathrm{}}^{}}$ ln ⁡ n ) {\$displaystyle \Tetta (d^{2}\ln)}$ 행을$$ 구성한다${\displaystyle .}$^[4]

참고 항목

• 그룹 테스트
• 연결 코드
• 압축 감지

참조

추가 읽기

• 아트리 루드라의 오류 수정 코드에 관한 책: 결합기, 알고리즘 및 응용 프로그램(201년 봄), 17장
• Djachkov, A. G. & Rykov, V. V. (1982)이항 코드의 길이에 대한 범위.Peremy Peredachi Informatsii [정보 전송 문제], 18(3), 7–13.
• Djachkov, A. G., Rashad, A. M. & Rykov, V. V. (1989년)중복된 거리 코드. 문제성 Upravlinja i Teori Informaci[제어 및 정보 이론의 문제], 18(4), 237–250.
• Zoltan Füredi (1996). "On r-Cover-free Families". Journal of Combinatorial Theory, Series A. 73 (1): 172–173. doi:10.1006/jcta.1996.0012.