diff options
| -rw-r--r-- | aaitch/aaitch.org | 79 | ||||
| -rw-r--r-- | secure-networks/secure-networks.org | 80 | ||||
| -rw-r--r-- | th-graph/th-graph.org | 327 |
3 files changed, 486 insertions, 0 deletions
diff --git a/aaitch/aaitch.org b/aaitch/aaitch.org new file mode 100644 index 0000000..d8c44e5 --- /dev/null +++ b/aaitch/aaitch.org @@ -0,0 +1,79 @@ +#+TITLE: Алгоритмы алгебры и теории чисел +#+AUTHOR: Андрей Гущин +#+LATEX_CLASS: Lecture +#+LATEX_HEADER: \usepackage{../preamble} + +# Лекция 1 (08.09.22) +* Делимость в кольце целых чисел + +Множество натуральных чисел можно определить с помощью аксиомы Пеано +1. $1 \in N$ +2. $\forall a \in N \; \existsonly a^+$ +3. $\forall a \in N \; a^+ \ne 1$ +4. $a^+ = b^+ \implies a = b$ +5. Если нек подмножество n входящее в мнво нат чисел и оно содержит единицу + и для нек нат $a$ существует последующее число содержащееся в $n$, + то эти множества совпадают + +На этих аксиомах строятся вся арифметика натуральных чисел, +то есть любой паре натуральных чисел можно однозначно сопоставить число, +которое будет являться натуральным. При этом будут вып 4 условия +1. a + 1 = a^+ +2. сумма будет ассоц +3. сумма будет коммут +4. сумма будет дистрибутивна + +Каждой паре нат чисел можно однозн сопост произведение, которое также +будет являться натуральным числом. При этом также будут выполняться 6 +условий +1. a \cdot 1 = a^+ +2. a \cdot b^+ = ab + a +3. сумма будет ассоц +4. сумма будет коммут +5. сумма будет дистрибутивна +6. ... + +Из аксиом 2 и 4 следует что множ нат чисел линейно и упорядочено. + +Из множества нат чисел построим множество целых чисел + +Опр. Множество целых чисел будем определять как объединение множества натуральных чисел + множ отриц нат чисел и нуля. Обозначается буквой Z. На множестве целых чисел определяются + операции сложения и умножения и задаются теми же правилами, что и для натуральных чисел. + +Опр. Пусть над нек множеством \Omega некоторой произвольной природы определены операции сложения + и умножения. Тогда это множество называется кольцом, если выполняются следующие условия: + 1. Сложение коммутативно + 2. Сложение ассоциативно + 3. Существует нулевой элемент, принадлежащий этому множеству такой, что a + 0 = a + 4. \forall a \in \Omega существует противоположный ему элемент, такой, что a + -a = 0 + 5. Умножение должно быть дистрибутивно относительно сложения: a * (b + c) = (a * b) + (a * c) + +- Если в кольце умножение коммутативно, то кольцо называется коммутативным. +- Если в кольце умножение ассоциативно, то кольцо называется ассоциативным. +- Если в кольце существует единичный элемент e, такой что a * e = e * a = a, то кольцо + называется кольцом с единицей +- Если в ассоциативном коммутативном кольце с единицей для любого элемента a \ne 0, такой, + что a * a^-1 = a^-1 * a = e, то такое кольцо будет называться полем +- Следует ответить, что множество натуральных чисел является ассоциативным коммутативным кольцом с единицей + +** Делимость целых чисел + +Пусть a и b произвольные целые числа и пусть существует нек целое число q, что a = b * q. Тогда можно сказать, +что число a делится на число b. (Записывается как три точки) + +Свойства делимости +1. Каждое число a делится на единицу и делится на само себя +2. Отношение делимости транзитивно +3. Если a и b делится на c, то их сумма, разность и произведение на любое + произвольное целое число также будет делиться на c. +4. Пусть дано равенство a_1 + a_2 + \dots + a_m = b_1 + b_2 + \dots + b_n в + котором все члены кроме одного делятся на c. Тогда этот оставшийся член также будет делиться на c. +5. Пусть a и b целые числа. Если + +Опр. Пусть a и b целые числа и b \ne 0 и a = bq + r, где r = 0->b, то число q называется неполным частным + или просто частным, а число r является остатком от деления числа a на b. + +Теорема. Пусть a и b произвольные числа и b > 0. Частное и остаток от деления a + на b существуют и определены однозначно. + diff --git a/secure-networks/secure-networks.org b/secure-networks/secure-networks.org new file mode 100644 index 0000000..4151dfd --- /dev/null +++ b/secure-networks/secure-networks.org @@ -0,0 +1,80 @@ +#+TITLE: Основы построения защищенных компьютерных сетей +#+AUTHOR: Андрей Гущин +#+LATEX_CLASS: Lecture +#+LATEX_HEADER: \usepackage{../preamble} + +# Лекция 1 (10.09.22) +* Сетевые угрозы, уязвимости и атаки + +** Модель OSI +... + +** Формат пакета TCP/IP +... + +** Порядок установки соединения +... + +** Основные сетевые уязвимости +... + +** Обеспечение ИБ +- Разглашение +- Несанкционированный доступ (НСД) +- Утечка по техническим каналам + +** Понятие угрозы ИБ +- Угроза (безопасности информации) +- Источник угрозы безопасности информации +- Контролируемая зона +- Несанкционированный доступ (несанкционированные действия) + +** Классификация угроз +- По характеру воздействия + - Активные + - Пассивные +- По цели воздействия + - Угрозы с нарушением конфиденциальности информации + - Угрозы нарушения целостности информации + - Угрозы нарушения доступности информации + - Угрозы комплексного воздействия на информацию +- По условию начала процесса реализации угрозы + - Угрозы реализуемые по запросу + - Угрозы реализуемые по наступлению ожидаемого события + - Безусловные воздействия +- По наличию обратной связи + - С обратной связью + - Без обратной связи (однонаправленная атака, DDoS) +- По расположению субъекта атаки относительно + - Внутрисегментные + - Межсегментные +- По соотношению количества нарушителей и хостов относительно которых реализуются угрозы + - Один к одному + - DDoS +- По уровню эталонной модели взаимодействия открытых систем + - Угрозы на физическом уровне + - Угрозы на канальном уровне + - Угрозы на сетевом уровне + - Угрозы на /OSI/ уровне + + +# Лекция (17.09.22) +** Наиболее частые угрозы + +- + +# Лекция (15.10.22) + +** Меры, направленные на обеспечение ИБ +1) Правовые +2) Организационные +3) Технические + +** Технические средства защиты сети +1) Межсетевые экраны +2) VLAN +3) Системы обнаружения/предотвращения вторжений +4) Системы HoneyPot +5) VPN и другие виды шифрования +6) Системы анализа защищённости +7) Антивирусные средства diff --git a/th-graph/th-graph.org b/th-graph/th-graph.org new file mode 100644 index 0000000..f33e602 --- /dev/null +++ b/th-graph/th-graph.org @@ -0,0 +1,327 @@ +#+TITLE: Теория графов +#+AUTHOR: Андрей Гущин +#+LATEX_CLASS: Lecture +#+LATEX_HEADER: \usepackage{../preamble} + +# Лекция 1 (08.09.22) +* Лекция + +Опр. Пусть $A, B$ - два непустых множества. Декартовым произведением $A$ и $B$ +называется множество $A \times B = \{ (a, b) : a \in A, \, b \in B \}$ + +Пустое отношение --- это отношение, не содержащее ни одной пары. + +Универсальное отношение содержит все возможные пары + +Опр. Двоичной булевой алгеброй называется множество $B = \{ 0, 1 \} $, на котором +определены следующие операции: +- Булево умножение +- Булево сложение +- Булево отрицание + +Пусть множества $A = \{ a_1, \dots, a_m \}, B = \{ b_1, \dots, b_n \}$. +... + +\( a = b + c \) + + +** Бинарные отношения +1. Отношение $\rho \subseteq A \times A$ называется рефлексивным $(\forall x \in A) ((x, x) \in \rho)$. + В матрице отношения элементы шлавной диагонали = 1; +2. +3. +4. Отношение $\rho \subseteq A \times A$ антисимметрично тогда и только тогда, когда + $(\forall x, y \in A) ((x, y) \in \rho \land (y, x) \in \rho) \implies (x = y)$. В + Матрице отношения элементы, симметричные единицам относительной главной диагонали, равны 0. + (Исключение - сама главная диагональ). +5. Отношение $\rho \subseteq A \times A$ транзитивно тогда и только тогда, когда $(\forall x, y, z \in A) + ((x, y) \in \rho \land (y, z) \in \rho \implies (x, z) \in \rho). + + +Опр. Отношением эквивалентности на на $A$ называется отношение $\varepsilon \subseteq A \times A$, +которое одновременно рефлексивно, симметрично и транзитивно. + +\begin{definition} +Отношение $\omega \subseteq A \times A$ ... порядка ... если ... +\end{definition} + +** Типы графов. Операции над графами. + +\begin{definition} +Опр. Орграфом $\vec{G} = (V, \alpha)$, где $V$ --- конечное непустое множество, +а $\alpha \subseteq V \times V$. Элементы множества $V$ называются вершинами, а +элементы множества $\alpha$ --- дугами (!!!). $V$ --- множество вершин, $\alpha$ --- +отношение смежности. + +- $(u, v) \in \alpha$ --- значит, из $u$ в $v$ есть дуга. +- Если $u = v$, то есть $(u, u) \in \alpha$, то дуга называется петлёй. +- Говорят, что дуга $(u, v)$ инцидентна вершинам $u$ и $v$, то есть + своим концам. +\end{definition} + +$A = M(\alpha)$ --- матрица смежности. Если $\alpha_{ij} = 1$, то есть дуга из +$i$-ой вершины в $j$-ую. + +\begin{definition} +Говорят. что ограф $\vec{G} = (U, \alpha)$ изоморфен $\vec{H} = (V, \beta)$, если +существует биекция $\varphi: U \to V$, которая сохраняет отношение смежности: +$(\forall u_1, u_2 \in U) ((u_1, u_2) \in \alpha \iff (\varphi(u_1), \varphi(u_2)) \in \beta)$. +\end{definition} + +** Неориентированные графы + +Граф $G = (V, \alpha)$ называется неориентированным (или просто графом), если отношение +смежности $\alpha$ антирефлексивно и симметрично. +- Нет петель, дуги встречаются парами +- $(u, v)$, $(v, y)$ --- ребро обозначается $\{ u, v \}$. + +** Симметризация + +Опр. Каждому орграфу $\vec{G} = (V, \alpha)$ естественным образом можно + сопоставить неориентированный граф, который называется его + симметризацией. Это граф $(V, (\alpha \cup \alpha^{-1}) \backslash + \Delta)$, то есть дуги заменяются рёбрами и исключаются петли. + +** Диграфы + +Опр. Ограф $\vec{G} = (V, \alpha)$ называется направленным графом или + /диграфом/, если его отношение смежности антисимметрично (то есть в диграфу + нет встречных дуг, за исключением быть может петель). + +Опр. Орграф $\vec{G} = (V, \alpha)$ называется полным, если его отношение + смежности универсально, то есть $\alpha = V \times V$. Обозначается + $\vec{K_n}$. + +Опр. Неориентированный граф называется полным, если его отношение смежности + $\alpha$ имеет вид $(V \times V) \backslash \Delta$. Обозначается $K_n$ + +** Вполне несвязные графы + +Опр. Орграф называется вполне несвязным (нуль-графом), если его отношение + смежности пусто. Обозначается $O_n$. Очевидно, что для каждого $n$ + существует единственный граф $K_n$, $\vec{K_n}$, $O_n$ + +Опр. Диграф называется полным, если в каждой вершине имеется петля и между двумя + различными вершинами существует, и при том единственная, дуга. Полный + диграф называется турниром. + +** Степени вершин + +Пусть $\vec{G} = (V, \alpha)$ --- орграф, $v$ --- некоторая его вершина. + +Опр. Степенью исхода вершины $v$ называется число $d^+$, равное количеству дуг в + $\vec{G}$, имеющих $v$ своим началом. $d^+(v) := |\alpha(v)|$. + +Опр. Степенью захода вершины $v$ называется число $d^-$, равное количеству дуг в + $\vec{G}$, имеющих $v$ своим концом. $d^+(v) := |\alpha^{-1}(v)|$. + +** Спецификация орграфа + +Опр. Спецификацией орграфа называется вектор вида $(v_1^{(d_1^+, d_1^-)}, \dots, + v_n^{(d_n^+, d_n^-)}$, где $d_i^+ = d^+(v_i), d_i^- = d^-(v_i)$. + +Опр. Для неориентированного графа степени исхода и захода равны: $d^+(v) = + d^-(v) = d(v)$. Называется $d(v)$ просто степенью вершины. + + +** Двудольные графы + +Опр. Граф называется /двудольным/, если его множество вершин может быть разбито + на два подмножества $V_1$ и $V_2$. + - $V = V_1 \cup V_2$ + - $V_1 \cap V_2 = \empty$ + - для любого ребра $\{ u, v \}$, $u$ и $v$ принадлежат различным множествам. + +Опр. Двудольный граф, который содержит все возможные рёбра, отвечающие этому условию, + называется полным двудольным графом. И обозначается $K_{m, n}$, где $n$ и $m$ --- + количество вершин $n = |V_1|, m = |V_2|$. + +Опр. Двудольный граф $K_{1, n}$ называется звёздным графом. + +Опр. $K_{3, 3}$ граф Куратовского. + +# Лекция 3 (22.09.22) +* Изоморфизм + +\begin{definition} +$\ved{G} = (U, \alpha), \vec{H} = (V, \beta)$. Орграф G изоморфен орграфу H, если существует +биекция $\varphi : U \to V$ и при этом сохраняет отношение смежности. +$(\forall u_1, u_2 \in U) ((u_1, u_2) \in \alpha \iff (\varphi(u_1), \varphi(u_2)) \in \beta)$. +\end{definition} + +\begin{definition} + Граф G вкладывается в H если существует инъекция $\varphi : + (\forall u_1, u_2 \in U) ((u_1, u_2) \in \alpha \implies (\varphi(u_1), \varphi(u_2)) \in \beta)$. +\end{definition} + +\begin{definition} + Немым изображением графа называют его изображение, в котором пропущены имена меток. +\end{definition} + +Два графа изоморфны тогда и только тогда, когда они допускают +одинаковое немое изображение. + +Отношение измоморфизма это отношение эквивалентности и классы этого +отношения называются абстрактными графами. + +\begin{definition} + Изоморфизм графа на себя называется автоморфизмом. +\end{definition} + +\begin{definition} + Графы которые имеют только тождественный автоморфизм называются + ассиметричными или тождественными. +\end{definition} + +\begin{definition} + Две вершины $u$ и $v$ называются подобными, если существует + автоморфизм, в котором вершина $u$ переходит в вершину $v$. Граф, в + котором все вершины подобны называется вершинно-симметрическим или + вершинно-транзитивным. +\end{definition} + +Если в графе все вершины подобны, то этот граф регулярен. + +\begin{definition} + Два ребра называются подобными, если существует автоморфизм + $\varphi$, такой, что образом одного ребра является второе ребро. +\end{definition} + +\begin{definition} + Граф у которого все рёбра подобны называется рёберно-симметрическим + или рёберно-транзитивным. +\end{definition} + +\begin{definition} + Граф, который является вершинно-симметрическим и + рёберно-симметрическим называется симметричным. +\end{definition} + +** Части графа. Отказоустойчивость и расширение. + +\begin{definition} + $\vec{G} = (V, \alpha)$. Его частью называется граф $\vec{G^*} = + (V^*, \alpha^*)$, где $V^* \subseteq V, \alpha^* \subseteq \alpha + \cap (V^* \times V^*)$. Часть графа состоит из некоторых вершин и + некоторых соединяющих их дуг или рёбер. +\end{definition} + +\begin{definition} + Подграфом ографа $\vec{G}$ называется орграф $\vec{G^*} = (V^*, + \alpha^*)$, где $V^* \subseteq V, \alpha^* = \alpha \cap (V^* \times + V^*)$ +\end{definition} + +\begin{definition} + Максимальным подграфом орграфа $\vec{G}$ называется орграф, + получающийся удалением одной вершины и всех связанных с ней дуг. +\end{definition} + +\begin{definition} + Список максимальных подграфов называют колодой $P(\vec{G})$. +\end{definition} + +\begin{definition} + Граф $G$ называется реконструкцией графа $H$ если колода $P(G) = P(H)$. +\end{definition} + +\begin{definition} + Граф $G$ является реконструируемым, если он изоморфен всякой своей реконструкции. +\end{definition} + +\begin{definition} + Гипотеза Келли-Улама (Гипотеза о вершинной реконструирумости). Все + неориентированные графы с числом вершин больше двух являются + вершинно-реконструируемыми. Гипотеза справедлива для несвязных + графов, деревьев, двудольных графов. +\end{definition} + +\begin{definition} + Всякий неориентриваонный граф с числом рёбер больше трёх является + рёберно-реконструируемым. +\end{definition} + +\begin{definition} + Инвариант графа --- это один или более параметров, которые являются + одинаковыми для всех изоморфных графов. Инвариант называется полным, если + он различен для любых неизоморфных графов. +\end{definition} + +# Лекция (06.10.22) + +** Расширения циклов +..... + +\begin{theorem}[МВ-1Р, Абросимов, 2000] + Графы, построенные по предлагаемым схемам являются МВ-1Р цикла с + соответствующим числом вершин и при $n > 5$ строят графы, не + изоморфные соответствующим реализациям из теоремы 2. + + /Рисунки схем/ +\end{theorem} + +* Основные типы неориентированных графов + +** Пути в графе. Связные графы. + +\begin{definition} + Путём называется последовательность рёбер, в которой каждые два + соседних ребра имеют общую вершину, и никакое ребро не встерчаеся + более одного раза. При этом считается, что оба конца каждого ребра, + кроме первого и последнего, являются концами соседних рёбер. +\end{definition} + +\begin{definition} + Путь называется циклическим, если его первая и последняя вершины совпадают. +\end{definition} + +\begin{definition} + Путь, любая вершина которого принадлежит не более чем двум рёбрам, называется простым. +\end{definition} + +\begin{definition} + Простой циклический путь называется циклом. Простой путь, не + являющийся циклом, называется цепью. +\end{definition} + +\begin{definition} + Длиной пути называется количество входящих в его состав рёбер. +\end{definition} + +Очевидно, что в $n$-вершинном графе цепь не может иметь длину больше, чем $n - 1$, а +цикл не может иметь длину больше, чем $n$. + +\begin{definition} + Наибольшее из расстояний от вершины до всех оставшихся вершин называется + эксцентриситетом вершины. + + $E(u)$ --- эксцентреситет, $E(u) = \max d(u, v), \, v \in V$ +\end{definition} + +** Связные графы + +\begin{definition} + Классы отношения связности графа называются его связными + компонентами или просто компонентами. +\end{definition} + +\begin{definition} + Граф с универсальным отношением связности называется связным графом. + Граф с тождественным отношением связности называется вполне + несвязным. +\end{definition} + +\begin{theorem} + Если вершины $u$ и $v$ являются единственными нечётными вершинами графа + $G$, то они связаны в этом графе. +\end{theorem} +\begin{proof} + Предположим противное, то есть $u$ и $v$ не связаны в + графе $G = (V, \alpha)$. Обозначим через $G_1$ и $G_2$ + компоненты связности графа $G$, содержащие соответственно + вершины $u$ и $v$. + + В графе $G_1$ вершина $u$ является единственной нечётной вершиной, + что противоречит теореме Эйлера (количество нечётных вершин должно + быт чётно). +\end{proof} |