Банк задач по математике

Задача 15.1.1

Рассмотрим четыре бинарные матрицы размера $2 \times 2$

A = \begin{pmatrix} 1 & 1 \\ 0 & 0 \end{pmatrix}, \quad B = \begin{pmatrix} 0 & 1 \\ 0 & 1 \end{pmatrix}, \quad C = \begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix}, \quad D = \begin{pmatrix} 0 & 0 \\ 1 & 1 \end{pmatrix}

над полем $\mathbb {F}$ , $\operatorname {char}(\mathbb {F}) = 2$ . Найдите $A+B+C+D$ и $ABCD$ .

?

Задача 15.1.2

(i)(ii)

Для бинарной матрицы размера $2 \times 2$

A = \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix}, \quad a_{jk} \in \left\{ 0,1\right\}

определим определитель как

\operatorname {det}\left(A\right) = (a_{11} \cdot a_{22}) \oplus (a_{12} \cdot a_{21})

где $\cdot$ — операция И, а $\oplus$ — операция исключающего ИЛИ.

?

(i)

Найдите определитель для следующих матриц размера $2 \times 2$

\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \quad \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \quad \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, \quad \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}, \quad \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}, \quad \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}.

(ii)

Найдите определитель для следующих матриц размера $2 \times 2$

\begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}, \quad \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}, \quad \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}, \quad \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}, \quad \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}

\begin{pmatrix} 1 & 1 \\ 0 & 0 \end{pmatrix}, \quad \begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix}, \quad \begin{pmatrix} 0 & 0 \\ 1 & 1 \end{pmatrix}, \quad \begin{pmatrix} 0 & 1 \\ 0 & 1 \end{pmatrix}, \quad \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}.

Задача 15.1.3

(i)(ii)

Определитель матрицы $3 \times 3$ $A = (a_{jk})$ задаётся выражением

a_{11}a_{22}a_{33} + a_{12}a_{23}a_{31} + a_{13}a_{21}a_{32} - a_{13}a_{22}a_{31} - a_{11}a_{23}a_{32} - a_{12}a_{21}a_{33}.

Для бинарной матрицы $B$ мы заменяем это выражение на

\begin{split} \operatorname {det}\left(B\right) = {} & (b_{11} \cdot b_{22} \cdot b_{33}) \oplus (b_{12} \cdot b_{23} \cdot b_{31}) \oplus (b_{13} \cdot b_{21} \cdot b_{32}) \\ & \oplus (b_{13} \cdot b_{22} \cdot b_{31}) \oplus (b_{11} \cdot b_{23} \cdot b_{32}) \oplus (b_{12} \cdot b_{21} \cdot b_{33}). \end{split}

?

(i)

Вычислите определитель для бинарных матриц

\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}, \quad \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix}.

(ii)

Вычислите определитель для бинарных матриц

\begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 0 \end{pmatrix}, \quad \begin{pmatrix} 1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{pmatrix}, \quad \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}.

Задача 15.1.4

Конечное поле $GF(2)$ состоит из элементов $0$ и $1$ (битов), которые удовлетворяют следующим таблицам сложения (XOR) и умножения (AND)

\begin{array}{c|cc} \oplus & 0 & 1 \\ \hline 0 & 0 & 1 \\ 1 & 1 & 0 \end{array} \qquad \begin{array}{c|cc} \cdot & 0 & 1 \\ \hline 0 & 0 & 0 \\ 1 & 0 & 1 \end{array}

Найдите определитель бинарных матриц

A = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}, \qquad B = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix}.

?

Задача 15.1.5

Булева функция $f : \left\{ 0,1\right\}^{n} \rightarrow \left\{ 0,1\right\}$ может быть преобразована из области $\left\{ 0,1\right\}$ в спектральную область с помощью линейного преобразования

Ty = s

где $T$ — ортогональная матрица $2^{n} \times 2^{n}$ , $y = (y_{0}, y_{1}, \ldots , y_{2^{n}-1})^{T}$ — двузначный ( $\left\{ +1,-1\right\}$ с $0 \leftrightarrow 1$ , $1 \leftrightarrow -1$ ) вектор таблицы истинности булевой функции, а $s_{j}$ ( $j = 0, 1, \ldots , 7$ ) — спектральные коэффициенты ( $s = (s_{0}, s_{1}, \ldots , s_{2^{n}-1})^{T}$ ). Поскольку $T$ обратима, имеем

T^{-1}s = y.

В качестве $T$ выберем матрицу Адамара. Матрица Адамара $H(n)$ размера $2^{n} \times 2^{n}$ определяется рекурсивно как

H(n) = \begin{pmatrix} H(n-1) & H(n-1) \\ H(n-1) & -H(n-1) \end{pmatrix}, \qquad n = 1, 2, \ldots

с $H(0) = (1)$ (матрица $1 \times 1$ ). Обратная к $H(n)$ задаётся как

H^{-1}(n) = \frac{1}{2^{n}} H(n).

Теперь любую булеву функцию $f(x_{1}, \ldots , x_{n})$ можно разложить в виде арифметического полинома

\frac{1}{2^{n+1}} \left(2^{n} - s_{0} - s_{1}(-1)^{x_{n}} - s_{2}(-1)^{x_{n-1}} - \cdots - s_{2^{n}-1}(-1)^{x_{1} \oplus x_{2} \oplus \cdots \oplus x_{n}}\right)

где $\oplus$ обозначает сложение по модулю 2.

Рассмотрим булеву функцию $f : \left\{ 0,1\right\}^{3} \rightarrow \left\{ 0,1\right\}$ , заданную как

f(x_{1}, x_{2}, x_{3}) = \bar{x}_{1} \cdot \bar{x}_{2} \cdot \bar{x}_{3} + \bar{x}_{1} \cdot x_{2} \cdot \bar{x}_{3} + x_{1} \cdot x_{2} \cdot \bar{x}_{3}.

Найдите таблицу истинности, вектор $y$ , а затем вычислите с помощью $H(3)$ спектральные коэффициенты $s_{j}$ , ( $j = 0, 1, \ldots , 7$ ).

?

Задача 15.1.6

Рассмотрим бинарные матрицы

A = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \qquad B = \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}.

Вычислите произведение Адамара $A \bullet B$ и звёздное произведение $A \star B$ .

?

Задача 15.1.7

Бинарной матрицей Адамара называется матрица $M$ размера $n \times n$ (где $n$ чётно) с элементами из $\left\{ 0,1\right\}$ , такая что любые две различные строки или столбца матрицы $M$ имеют расстояние Хэмминга $n/2$ . Расстояние Хэмминга между двумя векторами — это число позиций, в которых они отличаются. Найдите бинарную матрицу Адамара размера $4 \times 4$ .

?

Задача 15.1.8

Сколько бинарных матриц $2 \times 2$ можно составить так, чтобы они содержали две единицы? Найдите коммутатор между этими матрицами.

?

Задачи главы