diff options
| -rw-r--r-- | .gitignore | 3 | ||||
| -rw-r--r-- | Lecture.cls (renamed from sem5/Lecture.cls) | 0 | ||||
| -rw-r--r-- | Makefile (renamed from sem5/Makefile) | 2 | ||||
| -rw-r--r-- | computer-networks/computer-networks.tex (renamed from sem5/computer-networks/computer-networks.tex) | 0 | ||||
| -rw-r--r-- | computer-networks/lectures/lecture1.tex (renamed from sem5/computer-networks/lectures/lecture1.tex) | 0 | ||||
| -rw-r--r-- | computer-networks/lectures/lecture5.tex (renamed from sem5/computer-networks/lectures/lecture5.tex) | 0 | ||||
| -rw-r--r-- | databases/databases.tex (renamed from sem5/databases/databases.tex) | 0 | ||||
| -rw-r--r-- | databases/lectures/lecture1.tex (renamed from sem5/databases/lectures/lecture1.tex) | 0 | ||||
| -rw-r--r-- | databases/lectures/lecture2.tex (renamed from sem5/databases/lectures/lecture2.tex) | 0 | ||||
| -rw-r--r-- | information-theory/information-theory.tex (renamed from sem5/universal-algebra/universal-algebra.tex) | 6 | ||||
| -rw-r--r-- | information-theory/lectures/lecture1.tex (renamed from sem5/information-theory/lectures/lecture1.tex) | 0 | ||||
| -rw-r--r-- | information-theory/lectures/lecture2.tex (renamed from sem5/information-theory/lectures/lecture2.tex) | 0 | ||||
| -rw-r--r-- | information-theory/lectures/lecture3.tex (renamed from sem5/information-theory/lectures/lecture3.tex) | 0 | ||||
| -rw-r--r-- | information-theory/lectures/lecture4.tex (renamed from sem5/information-theory/lectures/lecture4.tex) | 0 | ||||
| -rw-r--r-- | information-theory/lectures/lecture5.tex (renamed from sem5/information-theory/lectures/lecture5.tex) | 0 | ||||
| -rw-r--r-- | information-theory/lectures/lecture6.tex (renamed from sem5/information-theory/lectures/lecture6.tex) | 0 | ||||
| -rw-r--r-- | information-theory/lectures/lecture7.tex (renamed from sem5/information-theory/lectures/lecture7.tex) | 0 | ||||
| -rw-r--r-- | languages/languages.tex (renamed from sem5/languages/languages.tex) | 0 | ||||
| -rw-r--r-- | languages/lectures/lecture1.tex (renamed from sem5/languages/lectures/lecture1.tex) | 0 | ||||
| -rw-r--r-- | languages/lectures/lecture2.tex (renamed from sem5/languages/lectures/lecture2.tex) | 0 | ||||
| -rw-r--r-- | languages/lectures/lecture5.tex (renamed from sem5/languages/lectures/lecture5.tex) | 0 | ||||
| -rw-r--r-- | preamble.sty (renamed from sem5/preamble.sty) | 8 | ||||
| -rwxr-xr-x | run.sh | 3 | ||||
| -rw-r--r-- | sem5/information-theory/information-theory.tex | 18 | ||||
| -rwxr-xr-x | sem5/run.sh | 2 | ||||
| -rw-r--r-- | sem5/universal-algebra/lectures/lecture1.tex | 50 | ||||
| -rw-r--r-- | sem5/universal-algebra/lectures/lecture3.tex | 92 | ||||
| -rw-r--r-- | sem5/universal-algebra/lectures/lecture4.tex | 84 |
28 files changed, 17 insertions, 251 deletions
@@ -9,4 +9,5 @@ *.toc *.bbl *.blg -*.md
\ No newline at end of file +*.md +.DS_Store diff --git a/sem5/Lecture.cls b/Lecture.cls index 32b3de1..32b3de1 100644 --- a/sem5/Lecture.cls +++ b/Lecture.cls @@ -3,5 +3,5 @@ clean: find . | grep -P "(.aux|.fdb_latexmk|.fls|.log|.synctex.gz|.out)" | xargs rm -f -mrproper: clean +fullclean: clean find . | grep -P "(.pdf|.md)" | xargs rm -f diff --git a/sem5/computer-networks/computer-networks.tex b/computer-networks/computer-networks.tex index b1ef05b..b1ef05b 100644 --- a/sem5/computer-networks/computer-networks.tex +++ b/computer-networks/computer-networks.tex diff --git a/sem5/computer-networks/lectures/lecture1.tex b/computer-networks/lectures/lecture1.tex index f992c47..f992c47 100644 --- a/sem5/computer-networks/lectures/lecture1.tex +++ b/computer-networks/lectures/lecture1.tex diff --git a/sem5/computer-networks/lectures/lecture5.tex b/computer-networks/lectures/lecture5.tex index 13cf56b..13cf56b 100644 --- a/sem5/computer-networks/lectures/lecture5.tex +++ b/computer-networks/lectures/lecture5.tex diff --git a/sem5/databases/databases.tex b/databases/databases.tex index b9beb1a..b9beb1a 100644 --- a/sem5/databases/databases.tex +++ b/databases/databases.tex diff --git a/sem5/databases/lectures/lecture1.tex b/databases/lectures/lecture1.tex index d1859d4..d1859d4 100644 --- a/sem5/databases/lectures/lecture1.tex +++ b/databases/lectures/lecture1.tex diff --git a/sem5/databases/lectures/lecture2.tex b/databases/lectures/lecture2.tex index e7052ab..e7052ab 100644 --- a/sem5/databases/lectures/lecture2.tex +++ b/databases/lectures/lecture2.tex diff --git a/sem5/universal-algebra/universal-algebra.tex b/information-theory/information-theory.tex index 12f87bc..707c765 100644 --- a/sem5/universal-algebra/universal-algebra.tex +++ b/information-theory/information-theory.tex @@ -4,11 +4,15 @@ \begin{document} \author{Андрей гущин} -\title{Универсальная прикладная алгебра} +\title{Теория информации} \maketitle \include{lectures/lecture1.tex} +\include{lectures/lecture2.tex} \include{lectures/lecture3.tex} \include{lectures/lecture4.tex} +\include{lectures/lecture5.tex} +\include{lectures/lecture6.tex} +\include{lectures/lecture7.tex} \end{document} diff --git a/sem5/information-theory/lectures/lecture1.tex b/information-theory/lectures/lecture1.tex index 5cf5dc7..5cf5dc7 100644 --- a/sem5/information-theory/lectures/lecture1.tex +++ b/information-theory/lectures/lecture1.tex diff --git a/sem5/information-theory/lectures/lecture2.tex b/information-theory/lectures/lecture2.tex index 5c4e598..5c4e598 100644 --- a/sem5/information-theory/lectures/lecture2.tex +++ b/information-theory/lectures/lecture2.tex diff --git a/sem5/information-theory/lectures/lecture3.tex b/information-theory/lectures/lecture3.tex index 2103c8d..2103c8d 100644 --- a/sem5/information-theory/lectures/lecture3.tex +++ b/information-theory/lectures/lecture3.tex diff --git a/sem5/information-theory/lectures/lecture4.tex b/information-theory/lectures/lecture4.tex index 0c2d14f..0c2d14f 100644 --- a/sem5/information-theory/lectures/lecture4.tex +++ b/information-theory/lectures/lecture4.tex diff --git a/sem5/information-theory/lectures/lecture5.tex b/information-theory/lectures/lecture5.tex index a202dd5..a202dd5 100644 --- a/sem5/information-theory/lectures/lecture5.tex +++ b/information-theory/lectures/lecture5.tex diff --git a/sem5/information-theory/lectures/lecture6.tex b/information-theory/lectures/lecture6.tex index 1907f9d..1907f9d 100644 --- a/sem5/information-theory/lectures/lecture6.tex +++ b/information-theory/lectures/lecture6.tex diff --git a/sem5/information-theory/lectures/lecture7.tex b/information-theory/lectures/lecture7.tex index 21c1f00..21c1f00 100644 --- a/sem5/information-theory/lectures/lecture7.tex +++ b/information-theory/lectures/lecture7.tex diff --git a/sem5/languages/languages.tex b/languages/languages.tex index 6e10590..6e10590 100644 --- a/sem5/languages/languages.tex +++ b/languages/languages.tex diff --git a/sem5/languages/lectures/lecture1.tex b/languages/lectures/lecture1.tex index 0c48aa2..0c48aa2 100644 --- a/sem5/languages/lectures/lecture1.tex +++ b/languages/lectures/lecture1.tex diff --git a/sem5/languages/lectures/lecture2.tex b/languages/lectures/lecture2.tex index b669a62..b669a62 100644 --- a/sem5/languages/lectures/lecture2.tex +++ b/languages/lectures/lecture2.tex diff --git a/sem5/languages/lectures/lecture5.tex b/languages/lectures/lecture5.tex index 34bd3cb..34bd3cb 100644 --- a/sem5/languages/lectures/lecture5.tex +++ b/languages/lectures/lecture5.tex diff --git a/sem5/preamble.sty b/preamble.sty index e3939ec..f35f534 100644 --- a/sem5/preamble.sty +++ b/preamble.sty @@ -67,8 +67,12 @@ \newtheorem*{remark}{Замечание} % ----------------- % - % --- Лемма --- % \theoremstyle{definition} \newtheorem*{lemma}{Лемма} -% ----------------- %
\ No newline at end of file +% ----------------- % + +% --- Лемма --- % +\theoremstyle{definition} +\newtheorem*{axiom}{Аксиома} +% ----------------- % @@ -0,0 +1,3 @@ +#!/bin/sh +[ -z "$@" ] && echo "Usage: $0 <base filename>" && exit 1 +cd $1 && find . -name "*.tex" | entr pandoc -s $1.tex -o $1.md
\ No newline at end of file diff --git a/sem5/information-theory/information-theory.tex b/sem5/information-theory/information-theory.tex deleted file mode 100644 index a38a193..0000000 --- a/sem5/information-theory/information-theory.tex +++ /dev/null @@ -1,18 +0,0 @@ -\documentclass{../Lecture} -\usepackage{../preamble} - -\begin{document} - -\author{Андрей гущин} -\title{Теория информации} -\maketitle - -% \include{lectures/lecture1.tex} -% \include{lectures/lecture2.tex} -% \include{lectures/lecture3.tex} -% \include{lectures/lecture4.tex} -% \include{lectures/lecture5.tex} -% \include{lectures/lecture6.tex} -\include{lectures/lecture7.tex} - -\end{document} diff --git a/sem5/run.sh b/sem5/run.sh deleted file mode 100755 index 23e6b81..0000000 --- a/sem5/run.sh +++ /dev/null @@ -1,2 +0,0 @@ -#!/bin/sh -cd $1 && find -name "*.tex" | entr pandoc -s $1.tex -o $1.md
\ No newline at end of file diff --git a/sem5/universal-algebra/lectures/lecture1.tex b/sem5/universal-algebra/lectures/lecture1.tex deleted file mode 100644 index 98db9dc..0000000 --- a/sem5/universal-algebra/lectures/lecture1.tex +++ /dev/null @@ -1,50 +0,0 @@ -% Лекция 1 (03.09.21) -\section{Алгебра отношений} -Обозначение множеств: -\begin{itemize} - \item $A = \{ a : P(A) \}$ - \item $[0, 1] = \{ x : x \in R \land 0 \leq x \leq 1 \}$ - \item $A = \{ 0, 1, \dots, 10 \}$ -\end{itemize} - -Основные действия над множествами: -\begin{itemize} - \item Сравнение множеств: $A = B$ означает, что $|A|=|B| \land \forall x \in A \iff x \in B$ - \item Объединение: $A \cup B$ --- множество, состоящее из элементов $A$ или $B$. $A \cup B = \{ x : x \in A \lor x \in B \}$ - \item Разность множеств: $A - B = \{ x : x \in A \land x \not\in B \}$ -\end{itemize} - -\begin{definition} - $\{ x, y \}$ называется неупорядоченной парой элементов $x$, $y$. -\end{definition} - -\begin{definition} - Множество $(a, b) = \{ a, \{a, b\} \}$ называют упорядоченной парой. -\end{definition} - -$A_1 \cdot \ldots \cdot A_n = \{ (a_1, a_2, \dots, a_n) : \dots \}$ - -\dots - -\begin{definition} - Всюду определённое и однозначеное бинарное отношение $\phi \subset A \times B$ обозначается $\phi: A \to B$ и - называется отображением $A$ в $B$, или \textit{функцией} на множестве $A$ со значениями в множестве $B$. -\end{definition} - -Для отображения $\phi: A \to B$: -\begin{itemize} - \item Область определения $D_p = A$ - \item Область значений $E_p = B$ -\end{itemize} - -\begin{definition} - Отображение $\phi: A \to B$ называется: - \begin{itemize} - \item \textit{Преобразованием} множества $A$, если $A = B$; - \item \textit{Отображением} множества $A$ на множество $B$, если $E_\phi = B$; - \item \textit{Взаимно однозначным отображением} множества $A$ в множество $B$, если оно является взаимно однозначным бинарным отношением; - \item \textit{Взаимно однозначным отображением} $A$ на $B$ если оно взаимно однозначно и $E_\phi = B$; - \item \textit{Перестановкой} множества $A$, если оно является взаимно однозначным отображением множества $A$ на себя. - \end{itemize} -\end{definition} - diff --git a/sem5/universal-algebra/lectures/lecture3.tex b/sem5/universal-algebra/lectures/lecture3.tex deleted file mode 100644 index 4707dd5..0000000 --- a/sem5/universal-algebra/lectures/lecture3.tex +++ /dev/null @@ -1,92 +0,0 @@ -% Лекция 3 (17.09.21) -\begin{example} - На $Z$ рассматривается бинарное отношение $(x, y) \in \varepsilon \iff |x| = |y|$. - Очевидно, что $\varepsilon$ рефлексивно, симметрично и транзитивно. - $\varepsilon$ является эквивалентным на $Z$ с классами $\varepsilon(x) \{ x, -x \}$ -\end{example} - -\begin{example} - На $Z$ для фиксированного $m \in N$ $(x, y) \in \varepsilon \iff$ $x - y$ делится - на $m$ то есть $x - y = k \cdot m$ для некоторого $k \in Z$. - \begin{itemize} - \item - \textit{Рефлексивность}. $(x, x) \in \varepsilon$ равносильна - $x - x = m \cdot k$, ($\exists k \in R$) --- выполняется - $x - x = m \cdot O$ для $O \in Z$ - \item - \textit{Симметричность}. - $(x, y) \in \varepsilon \implies (y, x) \in \varepsilon$, - то есть $x \cdot y = m \cdot k, \, \exists k \in Z \implies - y \cdot x = m \cdot l, \, (\exists l \in Z)$ --- верно, - то есть $l = -k \in Z$ - \item - \textit{Транзитивность}. - $(x, y) \in \varepsilon \land (y, z) \in \varepsilon \implies - (x, z) \in epsilon$, то есть - $x - y = m \cdot k, \, (\exists k \in Z) \lor - y - z = m \cdot l, \, (\exists l \in Z) \implies - x -z = m \cdot p, \, (\exists p \in Z)$. - \end{itemize} - - $x - z = (x - y) + (y - z) = m \cdot k + m \cdot l = m \cdot (k + l)$ для $k + l \in Z$ - - Получаем, что $\varepsilon$ --- отношение эквивалентности, которое - обозначается $\text{mod}\, m$ и называется отношением сравнения по модулю $m$. - - Классы отношения эквивалентности $\varepsilon$ : - \begin{eqnarray} - \varepsilon(0) &= \{ 0, m, 2m, \dots, -m, -2m \} = m \cdot \Z \\ - \varepsilon(1) &= \{ 1, m + 1, 2m + 1, \dots, -m + 1, -2m + 1 \} = m \cdot \Z + 1 \\ - &\dots \\ - \varepsilon(m - 1) &= \{ m - 1, 2m - 1, \dots \} = m \cdot \Z + (m - 1) \\ - \varepsilon(m) &= m \cdot \Z + m = m \cdot (Z + 1) = m \cdot Z = m(0) - \end{eqnarray} - - Фактор-множество $\Z/\text{mod}\, m = \{ \varepsilon(0), \dots, \varepsilon(m - 1) \}$ -\end{example} - -\begin{example} - На множестве $V$ всех векторов на плоскости рассмотрим бинарное отношение $\varepsilon$: - $(a, b) \in \varepsilon \iff (a \upuparrows b \land |a| = |b|)$. - $\varepsilon$ является отношением эквивалентности с классами эквивалентности - $\varepsilon(a) = \{ x \in V : a \upuparrows x \land |a| = |x| \}$. - Фактор-множество: $V/\varepsilon = \{ \varepsilon(a) : a \in V \}$ -\end{example} - -\begin{definition} - Бинарное отношение $\varepsilon$ на множестве $A$ называется \textit{отношением - эквивалентности} (или просто \textit{эквивалентностью}), если оно рефлексивно, - симметрично и транзитивно. -\end{definition} - -\begin{definition} - \textit{Ядром отображения} $\phi: A \to b$ называется бинарное отношение - $ker \phi$ на множестве $A$, которое определяется по формуле - \begin{equation*} - ker \phi \{ (a, b) \in A^2 : \phi(a) = \phi(b) \} - \end{equation*} -\end{definition} - -\begin{definition} - \textit{Каноническим отображением} эквивалентности $\varepsilon$ называется - отображение $nat \varepsilon$ множества $A$ на фактор-множество $A/\varepsilon$, - которое каждому элементу $a \in A$ ставит в соответствие содержащий его класс - эквивалентности $[a]$. Легко видель, что $ker nat \varepsilon = \varepsilon$ -\end{definition} - -\begin{definition} - Подмножество $T \subset A$ называется полной системой представителей классов - эквивалентности $\varepsilon$ на множестве $A$, если: - \begin{enumerate} - \item $\varepsilon(T) = A$ - \item из условия $t_1 \equiv t_2(\varepsilon)$ следует $t_1 = t_2$ - \end{enumerate} -\end{definition} - -Классы эквивалентности $[t] \in A/\varepsilon$ могут быть отождествленны со -своими представителями $t$ и фактор-множество $A/\varepsilon$ может быть -отождествленно с множеством $T$. - -... - -Извествен алгоритм построения СДНФ для любой формулы $\Phi (\neq 0)$ diff --git a/sem5/universal-algebra/lectures/lecture4.tex b/sem5/universal-algebra/lectures/lecture4.tex deleted file mode 100644 index eb76b95..0000000 --- a/sem5/universal-algebra/lectures/lecture4.tex +++ /dev/null @@ -1,84 +0,0 @@ -% Лекция 4 01.10.21 -\begin{definition}[Принцип двойственности] - Если утверждение $\Phi$ верно для всех упорядоченных множеств, то - двойственное ему утверждение также верно для всех упорядоченных множеств. -\end{definition} - -\begin{example} - \begin{enumerate} - \item - Для утверждения ``если в упорядоченном множестве существует $\sup X$, - то он единственнен'' двойственным будет ``если в упорядоченном - множестве существует $\inf X$, то он единственен''. - \item - Для утверждения ``упорядоченное множество $(A, \leq)$ имеет - наибольший элемент'' двойственным будет ``упорядоченное множество - $(A, \leq)$ имеет наименьший элемент''. - \end{enumerate} -\end{example} - -\subsection{Упорядочивание множества слов} - -\subsection{Подмножества и морфизмы упорядоченных множеств} -\begin{lemma}[Цорна] - Если в упорядоченном множестве любая цепь имеет верхнюю - грань, то каждый элемент этого множества содержится в - некотором максимальном элементе. -\end{lemma} - -\begin{lemma}[Аксиома выбора] - Для любого множества $A$ существует такая функция - $f : P(A) \to A$, что $f(X) \in X$ для любого $X \in P(A)$. -\end{lemma} - -\begin{definition} - Упорядоченное множество удовлетворяет \textit{условию минимальности}, - если каждое его непустое подмножество имеет минимальный элемент. -\end{definition} - -\begin{lemma}[Обобщённый принцип индукции] - Если упорядоченное множество удовлетворяет \textit{условию минимальности} - и подмножество $B \subset A$ содержит все такие элементы $a \in A$, для - которых при всех $x < a$ выполняется $x \in B$, то $B = A$. -\end{lemma} - -\begin{definition} - \textbf{Морфизмы} --- это отображения $\varphi : A \to B$, которые сохряняют - дополнительную алгебраическую структуру на множества $(A, B)$. - - Если $a_1 \leq_A a_2 \implies \varphi(a_1) \leq_B \varphi(a_2) \quad (\forall a_1, a_2 \in A)$ -\end{definition} - -\begin{example} - $\varphi : (\N, \leq_\N) \to (\Z, \leq_\Z)$ -\end{example} - -\subsection{Отношение квазипорядка} - -\begin{definition} - Бинарное отношение $\omega$ на множестве $A$ называется \textit{отношением - квазипорядка} (или просто \textit{квазипорядком}), если оно рефлексивно - и транзитивно. - - Отношение $\delta = \omega \cap \omega^{-1}$ называется \textit{ядром} - квазипорядка $\omega$. -\end{definition} - -\begin{example} - \begin{enumerate} - \item - Любая эквивалентность $\equiv$ и любой порядок $\leq$ на множестве - $A$ являются квазипорядками с ядрами $\delta = \equiv$ и - $\delta = \Delta_A$ соответственно. - \item - Отношение делимости $|$ на множество целых чисел $\Z$ является - квазипорядком с ядром $\delta = \{ (n, \mp n) | n \in \Z\}$. - \item - Отношение логического следлвания на множестве $F_{AB}$ формул - логики высказываний является квазипорядком, ядром которого - является отношение логической равносильности формул. - \item - Отношение достижимости вершин в ориентированном графе является - квазипорядком, ... - \end{enumerate} -\end{example}
\ No newline at end of file |