Викиконспекты - Вклад участника [ru]

Двойное хэширование

2011-05-16T22:11:43Z

Лебедев Роман: /* Двойное хэширование */

== Двойное хэширование ==
'''Двойное хэширование (double hashing)''' - один из лучших методов открытой адресации. Перебор ячеек хэш-таблицы, возникающий при двойном хешировании, обладает свойствами, присущими равномерному хешированию. При двойном хешировании хэш-функция <tex> h </tex> имеет следующий вид:

<center>
<tex> h(k,i) = (h_1(k) + i*h_2(k)) mod m </tex>
</center>

[[Файл: Вставка при двойном хэшировании.svg.jpeg|thumb|right|Вставка при двойном хэшировании]]

где <tex> h1 </tex> и <tex> h2 </tex> - вспомогательные хеш-функции, <tex> m </tex> - размер хэш-таблицы. Иными словами, последовательность индексов исследуемых ячеек при работе с ключом <tex> k </tex> представляет собой арифметическую прогрессию (по модулю <tex> m </tex>) с первым членом <tex> h_1(k) </tex> и шагом <tex> h_2(k) </tex>. Следовательно, в данном случае последовательность исследования зависит от ключа k по двум параметрам - выбор начальной исследуемой ячейки и расстояние между двумя исследуемыми ячейками, так как оба параметра зависят от значения ключа.

Пример вставки элемента при двойном хешировании приведен на рисунке справа.

Показана хэш-таблица размером 13 ячеек, в которой используются вспомогательные функции:

<center>
<tex> h_1(k) = k mod 13 </tex>
</center>

<center>
<tex> h_2(k) = 1 + k mod 11 </tex>
</center>

Мы хотим вставить ключ 14. Изначально <tex> i = 0 </tex>. Тогда <tex> h(14,0) = (h_1(14) + 0*h_2(14)) mod 13 = 1 </tex>. Но ячейка с индексом 1 занята, поэтому увеличиваем <tex> i </tex> на 1 и пересчитываем значение хэш-функции. Делаем так, пока не дойдем до пустой ячейки. При <tex> i = 2 </tex> получаем <tex> h(14,2) = (h_1(14) + 2*h_2(14)) mod 13 = 9 </tex>. Ячейка с номером 9 свободна, значит записываем туда наш ключ.

Для того, чтобы последовательность исследования могла охватить всю таблицу, значение <tex> h2 </tex> должно быть взаимно простым с размером таблицы. Есть два удобных способа это сделать. Первый состоит в том, что в качестве размера таблицы используется простое число, а <tex> h2 </tex> возвращает натуральные числа, меньшие <tex> m </tex>. Второй - размер таблицы является степенью двойки, а <tex> h2 </tex> возвращает нечетные значения.

Двойное хэширование превосходит другие в смысле количества последовательностей исследований. Это связано с тем, что каждая возможная пара <tex> (h_1(k),h_2(k)) </tex> дает отличающуюся от других последовательность исследований.

Двойное хэширование

2011-05-16T22:06:36Z

Лебедев Роман: /* Двойное хэширование */

== Двойное хэширование ==
'''Двойное хэширование (double hashing)''' - один из лучших методов открытой адресации. Перестановки индексов, возникающие при двойном хешировании, обладают свойствами, присущими равномерному хешированию. При двойном хешировании функция <tex> h </tex> имеет следующий вид:

<center>
<tex> h(k,i) = (h_1(k) + i*h_2(k)) mod m </tex>
</center>

[[Файл: Вставка при двойном хэшировании.svg.jpeg|thumb|right|Вставка при двойном хэшировании]]

где <tex> h1 </tex> и <tex> h2 </tex> - вспомогательные хеш-функции, <tex> m </tex> - размер хэш-таблицы. Иными словами, последовательность индексов исследуемых ячеек при работе с ключом <tex> k </tex> представляет собой арифметическую прогрессию (по модулю <tex> m </tex>) с первым членом <tex> h_1(k) </tex> и шагом <tex> h_2(k) </tex>. Следовательно, в данном случае последовательность исследования зависит от ключа k по двум параметрам - выбор начальной исследуемой ячейки и расстояние между двумя исследуемыми ячейками, так как оба параметра зависят от значения ключа.

Пример вставки элемента при двойном хешировании приведен на рисунке справа.

Показана хэш-таблица размером 13 ячеек, в которой используются вспомогательные функции:

<center>
<tex> h_1(k) = k mod 13 </tex>
</center>

<center>
<tex> h_2(k) = 1 + k mod 11 </tex>
</center>

Мы хотим вставить ключ 14. Изначально <tex> i = 0 </tex>. Тогда <tex> h(14,0) = (h_1(14) + 0*h_2(14)) mod 13 = 1 </tex>. Но ячейка с индексом 1 занята, поэтому увеличиваем <tex> i </tex> на 1 и пересчитываем значение хэш-функции. Делаем так, пока не дойдем до пустой ячейки. При <tex> i = 2 </tex> получаем <tex> h(14,2) = (h_1(14) + 2*h_2(14)) mod 13 = 9 </tex>. Ячейка с номером 9 свободна, значит записываем туда наш ключ.

Для того, чтобы последовательность исследования могла охватить всю таблицу, значение <tex> h2 </tex> должно быть взаимно простым с размером таблицы. Есть два удобных способа это сделать. Первый состоит в том, что в качестве размера таблицы используется простое число, а <tex> h2 </tex> возвращает натуральные числа, меньшие <tex> m </tex>. Второй - размер таблицы является степенью двойки, а <tex> h2 </tex> возвращает нечетные значения.

Двойное хэширование превосходит другие в смысле количества последовательностей исследований. Это связано с тем, что каждая возможная пара <tex> (h_1(k),h_2(k)) </tex> дает отличающуюся от других последовательность исследований.

Двойное хэширование

2011-05-16T22:01:28Z

Лебедев Роман: /* Двойное хэширование */

== Двойное хэширование ==
'''Двойное хэширование (double hashing)''' - один из лучших методов открытой адресации. Перестановки индексов, возникающие при двойном хешировании, обладают свойствами, присущими равномерному хешированию. При двойном хешировании функция h имеет следующий вид:

<center>
<tex> h(k,i) = (h_1(k) + i*h_2(k)) mod m </tex>
</center>

[[Файл: Вставка при двойном хэшировании.svg.jpeg|thumb|right|Вставка при двойном хэшировании]]

где <tex> h1 </tex> и <tex> h2 </tex> - вспомогательные хеш-функции, <tex> m </tex> - размер хэш-таблицы. Иными словами, последовательность индексов исследуемых ячеек при работе с ключом <tex> k </tex> представляет собой арифметическую прогрессию (по модулю <tex> m </tex>) с первым членом <tex> h_1(k) </tex> и шагом <tex> h_2(k) </tex>. Следовательно, в данном случае последовательность исследования зависит от ключа k по двум параметрам - выбор начальной исследуемой ячейки и расстояние между двумя исследуемыми ячейками, так как оба параметра зависят от значения ключа.

Пример вставки элемента при двойном хешировании приведен на рисунке справа.

Показана хэш-таблица размером 13 ячеек, в которой используются вспомогательные функции:

<center>
<tex> h_1(k) = k mod 13 </tex>
</center>

<center>
<tex> h_2(k) = 1 + k mod 11 </tex>
</center>

Мы хотим вставить ключ 14. Изначально <tex> i = 0 </tex>. Тогда <tex> h(14,0) = (h_1(14) + 0*h_2(14)) mod 13 = 1 </tex>. Но ячейка с индексом 1 занята, поэтому увеличиваем <tex> i </tex> на 1 и пересчитываем значение хэш-функции. Делаем так, пока не дойдем до пустой ячейки. При <tex> i = 2 </tex> получаем <tex> h(14,2) = (h_1(14) + 2*h_2(14)) mod 13 = 9 </tex>. Ячейка с номером 9 свободна, значит записываем туда наш ключ.

Для того, чтобы последовательность исследования могла охватить всю таблицу, значение <tex> h2 </tex> должно быть взаимно простым с размером таблицы. Есть два удобных способа это сделать. Первый состоит в том, что в качестве размера таблицы используется простое число, а <tex> h2 </tex> возвращает натуральные числа, меньшие <tex> m </tex>. Второй - размер таблицы является степенью двойки, а <tex> h2 </tex> возвращает нечетные значения.

Двойное хэширование превосходит другие в смысле количества последовательностей исследований. Это связано с тем, что каждая возможная пара <tex> (h_1(k),h_2(k)) </tex> дает отличающуюся от других последовательность исследований.

Файл:Вставка при двойном хэшировании.svg.jpeg

2011-05-16T21:58:49Z

Лебедев Роман:

Двойное хэширование

2011-05-16T21:58:25Z

Формула включения-исключения

2010-11-07T23:14:28Z

Лебедев Роман: /* Теорема */

== Формула включения-исключения ==
'''Формула включения-исключения''' - это комбинаторная формула, которая позволяет определить мощность объединения конечных множеств, если известны их мощности и мощности всех их возможных пересечений.

[[Файл:пересечение двух множеств.svg.png|thumb|right|случай для двух множеств]]

Например, в случае двух множеств <math>~A, B</math> формула включения-исключения имеет вид:
<center>
<math> | A \cup B | = | A | + | B | - | A \cap B |</math>
</center>
В сумме <math>~| A | + | B |</math> элементы пересечения <math>A \cap B</math> учтены дважды, и чтобы компенсировать это мы вычитаем <math> | A \cap B |</math> из правой части формулы. Справедливость этого рассуждения видна из диаграммы Эйлера-Венна для двух множеств, приведенной на рисунке справа.

Таким же образом и в случае <math>~n>2</math> множеств процесс нахождения количества элементов объединения <math>A_1 \cup A_2 \cup \ldots \cup A_n</math> состоит во включении всего, затем исключении лишнего, затем включении ошибочно исключенного и так далее, то есть в попеременном включении и исключении. Отсюда и происходит название формулы.

== Теорема ==
Пусть <math> A = \bigcup_{i=1}^{n}A_i </math> , тогда по формуле включения-исключения:
<center>
<math> | A | = \sum_{I=(i_1,i_2, \ldots ,i_k) \subset \{ 1,2, \ldots ,n \} } (-1)^{k+1} \Big| \bigcap_{ j \in I } A_j \Big| </math>
</center>

== Доказательство ==
Для случая <math>~n=1</math> и <math>~n=2</math> теорема, очевидно, верна.

Теперь рассмотрим <math>~n>2</math>:
<center>
<math> A = \bigcup_{i=1}^{n}A_i = \Bigg( \underbrace {\bigcup_{i=1}^{n-1}A_i}_{B} \Bigg) \cup A_n </math>

<math> | B | = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j \in I } A_j \Big| </math>

<math> | A | = | B | + | A_n | - | B \cap A_n |</math>

<math> \Big| B \bigcap A_n \Big| = \Bigg| \Bigg( \bigcup_{i=1}^{n-1}A_i \Bigg) \bigcap A_n \Bigg|= \Bigg| \bigcup_{i=1}^{n-1} \bigg( A_i \bigcap A_n \bigg) \Bigg| = </math>

<math> = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \bigg| \bigcap_{ j \in I } \Big( A_j \bigcap A_n \Big) \bigg| = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j\in I \cup \{ n \} } A_j \Big| </math>
</center>

<center>
Таким образом:
</center>

<center>
<math> | A | = | A_n| + \Bigg( \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j \in I } A_j \Big| \Bigg) - \Bigg( \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j\in I \cup \{ n \} } A_j \Big| \Bigg) = \sum_{I \subset \{ 1,2, \ldots ,n \} } (-1)^{k+1} \Big| \bigcap_{ j \in I } A_j \Big| </math>
</center>

== Доказательство ==
Для случая <math>~n=1</math> и <math>~n=2</math> теорема, очевидно, верна.

Теперь рассмотрим <math>~n>2</math>:
<center>
<math> A = \bigcup_{i=1}^{n}A_i = \Bigg( \underbrace {\bigcup_{i=1}^{n-1}A_i}_{B} \Bigg) \cup A_n </math>

<math> | B | = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j \in I } A_j \Big| </math>

<math> | A | = | B | + | A_n | - | B \cap A_n |</math>

<math> \Big| B \bigcap A_n \Big| = \Bigg| \Bigg( \bigcup_{i=1}^{n-1}A_i \Bigg) \bigcap A_n \Bigg|= \Bigg| \bigcup_{i=1}^{n-1} \bigg( A_i \bigcap A_n \bigg) \Bigg| = </math>

<math> = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \bigg| \bigcap_{ j \in I } \Big( A_j \bigcap A_n \Big) \bigg| = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j\in I \cup \{ n \} } A_j \Big| </math>
</center>

<center>
Таким образом:
</center>

<center>
<math> | A | = | A_n| + \Bigg( \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j \in I } A_j \Big| \Bigg) - \Bigg( \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j\in I \cup \{ n \} } A_j \Big| \Bigg) = \sum_{I \subset \{ 1,2, \ldots ,n \} } (-1)^{k+1} \Big| \bigcap_{ j \in I } A_j \Big| </math>
</center>

== Теорема ==
Пусть <math> A = \bigcup_{i=1}^{n}A_i </math> , тогда по формуле включения-исключения:
<center>
<math> | A | = \sum_{I=(i_1,i_2, \ldots ,i_k) \subset \{ 1,2, \ldots ,n \} } (-1)^{k+1} \Big| \bigcap_{ j \in I } A_j \Big| </math>
</center>

== Доказательство ==
Для случая <math>~n=1</math> и <math>~n=2</math> теорема, очевидно, верна.

Теперь рассмотрим <math>~n>2</math>:
<center>
<math> A = \bigcup_{i=1}^{n}A_i = \Bigg( \underbrace {\bigcup_{i=1}^{n-1}A_i}_{B} \Bigg) \cup A_n </math>

<math> | B | = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j \in I } A_j \Big| </math>

<math> | A | = | B | + | A_n | - | B \cap A_n |</math>

<math> \Big| B \bigcap A_n \Big| = \Bigg| \Bigg( \bigcup_{i=1}^{n-1}A_i \Bigg) \bigcap A_n \Bigg|= \Bigg| \bigcup_{i=1}^{n-1} \bigg( A_i \bigcap A_n \bigg) \Bigg| = </math>

<math> = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \bigg| \bigcap_{ j \in I } \Big( A_j \bigcap A_n \Big) \bigg| = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j\in I \cup \{ n \} } A_j \Big| </math>
</center>

<center>
Таким образом:
</center>

<center>
<math> | A | = | A_n| + \Bigg( \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j \in I } A_j \Big| \Bigg) + \Bigg( \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j\in I \cup \{ n \} } A_j \Big| \Bigg) = \sum_{I \subset \{ 1,2, \ldots ,n \} } (-1)^{k+1} \Big| \bigcap_{ j \in I } A_j \Big| </math>
</center>

Формула включения-исключения

2010-11-07T23:13:16Z

Лебедев Роман: /* Формула включения-исключения */

== Формула включения-исключения ==
'''Формула включения-исключения''' - это комбинаторная формула, которая позволяет определить мощность объединения конечных множеств, если известны их мощности и мощности всех их возможных пересечений.

[[Файл:пересечение двух множеств.svg.png|thumb|right|случай для двух множеств]]

Например, в случае двух множеств <math>~A, B</math> формула включения-исключения имеет вид:
<center>
<math> | A \cup B | = | A | + | B | - | A \cap B |</math>
</center>
В сумме <math>~| A | + | B |</math> элементы пересечения <math>A \cap B</math> учтены дважды, и чтобы компенсировать это мы вычитаем <math> | A \cap B |</math> из правой части формулы. Справедливость этого рассуждения видна из диаграммы Эйлера-Венна для двух множеств, приведенной на рисунке справа.

Таким же образом и в случае <math>~n>2</math> множеств процесс нахождения количества элементов объединения <math>A_1 \cup A_2 \cup \ldots \cup A_n</math> состоит во включении всего, затем исключении лишнего, затем включении ошибочно исключенного и так далее, то есть в попеременном включении и исключении. Отсюда и происходит название формулы.

== Теорема ==
Пусть <math> A = \bigcup_{i=1}^{n}A_i </math> , тогда по формуле включения-исключения:
<center>
<math> | A | = \sum_{I=(i_1,i_2, \ldots ,i_k) \subset \{ 1,2, \ldots ,n \} } (-1)^{k+1} \Big| \bigcap_{ j \in I } A_j \Big| </math>
</center>

== Доказательство ==
Для случая <math>~n=1</math> и <math>~n=2</math> теорема, очевидно, верна.

Теперь рассмотрим <math>~n>2</math>:
<center>
<math> A = \bigcup_{i=1}^{n}A_i = \Bigg( \underbrace {\bigcup_{i=1}^{n-1}A_i}_{B} \Bigg) \cup A_n </math>

<math> | B | = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j \in I } A_j \Big| </math>

<math> | A | = | B | + | A_n | - | B \cap A_n |</math>

<math> \Big| B \bigcap A_n \Big| = \Bigg| \Bigg( \bigcup_{i=1}^{n-1}A_i \Bigg) \bigcap A_n \Bigg|= \Bigg| \bigcup_{i=1}^{n-1} \bigg( A_i \bigcap A_n \bigg) \Bigg| = </math>

<math> = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \bigg| \bigcap_{ j \in I } \Big( A_j \bigcap A_n \Big) \bigg| = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j\in I \cup \{ n \} } A_j \Big| </math>
</center>

<center>
Таким образом:
</center>

<center>
<math> | A | = | A_n| + \Bigg( \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j \in I } A_j \Big| \Bigg) - \Bigg( \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j\in I \cup \{ n \} } A_j \Big| \Bigg) = \sum_{I \subset \{ 1,2, \ldots ,n \} } (-1)^{k+1} \Big| \bigcap_{ j \in I } A_j \Big| </math>
</center>

== Теорема ==
Пусть <math> A = \bigcup_{i=1}^{n}A_i </math> , тогда по формуле включения-исключения:
<center>
<math> | A | = \sum_{I=(i_1,i_2, \ldots ,i_k) \subset \{ 1,2, \ldots ,n \} } (-1)^{k+1} \Big| \bigcap_{ j \in I } A_j \Big| </math>
</center>

== Доказательство ==
Для случая <math>~n=1</math> и <math>~n=2</math> теорема, очевидно, верна.

Теперь рассмотрим <math>~n>2</math>:
<center>
<math> A = \bigcup_{i=1}^{n}A_i = \Bigg( \underbrace {\bigcup_{i=1}^{n-1}A_i}_{B} \Bigg) \cup A_n </math>

<math> | B | = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j \in I } A_j \Big| </math>

<math> | A | = | B | + | A_n | - | B \cap A_n |</math>

<math> \Big| B \bigcap A_n \Big| = \Bigg| \Bigg( \bigcup_{i=1}^{n-1}A_i \Bigg) \bigcap A_n \Bigg|= \Bigg| \bigcup_{i=1}^{n-1} \bigg( A_i \bigcap A_n \bigg) \Bigg| = </math>

<math> = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \bigg| \bigcap_{ j \in I } \Big( A_j \bigcap A_n \Big) \bigg| = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j\in I \cup \{ n \} } A_j \Big| </math>
</center>

<center>
Таким образом:
</center>

<center>
<math> | A | = | A_n| + \Bigg( \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j \in I } A_j \Big| \Bigg) - \Bigg( \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j\in I \cup \{ n \} } A_j \Big| \Bigg) = \sum_{I \subset \{ 1,2, \ldots ,n \} } (-1)^{k+1} \Big| \bigcap_{ j \in I } A_j \Big| </math>
</center>

== Теорема ==
Пусть <math> A = \bigcup_{i=1}^{n}A_i </math> , тогда по формуле включения-исключения:
<center>
<math> | A | = \sum_{I=(i_1,i_2, \ldots ,i_k) \subset \{ 1,2, \ldots ,n \} } (-1)^{k+1} \Big| \bigcap_{ j \in I } A_j \Big| </math>
</center>

== Доказательство ==
Для случая <math>~n=1</math> и <math>~n=2</math> теорема, очевидно, верна.

Теперь рассмотрим <math>~n>2</math>:
<center>
<math> A = \bigcup_{i=1}^{n}A_i = \Bigg( \underbrace {\bigcup_{i=1}^{n-1}A_i}_{B} \Bigg) \cup A_n </math>

<math> | B | = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j \in I } A_j \Big| </math>

<math> | A | = | B | + | A_n | - | B \cap A_n |</math>

<math> \Big| B \bigcap A_n \Big| = \Bigg| \Bigg( \bigcup_{i=1}^{n-1}A_i \Bigg) \bigcap A_n \Bigg|= \Bigg| \bigcup_{i=1}^{n-1} \bigg( A_i \bigcap A_n \bigg) \Bigg| = </math>

<math> = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \bigg| \bigcap_{ j \in I } \Big( A_j \bigcap A_n \Big) \bigg| = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j\in I \cup \{ n \} } A_j \Big| </math>
</center>

<center>
Таким образом:
</center>

<center>
<math> | A | = | A_n| + \Bigg( \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j \in I } A_j \Big| \Bigg) + \Bigg( \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j\in I \cup \{ n \} } A_j \Big| \Bigg) = \sum_{I \subset \{ 1,2, \ldots ,n \} } (-1)^{k+1} \Big| \bigcap_{ j \in I } A_j \Big| </math>
</center>

Формула включения-исключения

2010-11-07T23:12:01Z

Лебедев Роман: /* Формула включения-исключения */

Формула включения-исключения

2010-11-07T23:09:52Z

Лебедев Роман:

Формула включения-исключения

2010-11-07T23:07:38Z

Лебедев Роман:

Формула включения-исключения

2010-11-07T23:06:08Z

Лебедев Роман: Новая страница: «== Формула включения-исключения == '''Формула включения-исключения''' - это комбинаторная фор…»

Файл:Пересечение двух множеств.svg.png

2010-11-07T23:04:59Z

Лебедев Роман: