diff options
| author | Andrew Guschin <guschin.drew@gmail.com> | 2022-06-26 13:05:56 +0400 |
|---|---|---|
| committer | Andrew Guschin <guschin.drew@gmail.com> | 2022-06-26 13:05:56 +0400 |
| commit | cad4b972574c9c58357fa21d18dddc388258b4ee (patch) | |
| tree | 7afd8fe5073dc906b219dc926e9cf093a95efd5a /sem5 | |
| parent | 14fffdc1df3661252661dbc96ac9810118f00601 (diff) | |
| parent | 323bfc05e2bf72820299976c8b26057ca8ed86aa (diff) | |
Merge branch 'master' of github.com:vasthecat/university-lectures
Diffstat (limited to 'sem5')
26 files changed, 0 insertions, 2078 deletions
diff --git a/sem5/Lecture.cls b/sem5/Lecture.cls deleted file mode 100644 index 32b3de1..0000000 --- a/sem5/Lecture.cls +++ /dev/null @@ -1,96 +0,0 @@ -\LoadClass[a4paper,oneside]{article} - -\RequirePackage[utf8]{inputenc} -\RequirePackage[russian]{babel} -\RequirePackage{hyperref} -\RequirePackage{underscore} -\RequirePackage{setspace} -\RequirePackage{indentfirst} -\RequirePackage{cancel} -\RequirePackage[left=1.4cm,right=1.4cm, - top=2.3cm,bottom=2.3cm,bindingoffset=0cm]{geometry} -\singlespacing -\RequirePackage{float} -\RequirePackage{fancyhdr} -% \pagestyle{fancy} -% \pagestyle{headings} - - -%---------------------------------------------------------------------------------------- -% TITLE PAGE -%---------------------------------------------------------------------------------------- -\renewcommand{\maketitle} -{ - -\begin{titlepage} % Suppresses displaying the page number on the title page and the subsequent page counts as page 1 - \newcommand{\HRule}{\rule{\linewidth}{0.5mm}} % Defines a new command for horizontal lines, change thickness here - - \center % Centre everything on the page - - %------------------------------------------------ - % Headings - %------------------------------------------------ - - % \textsc{\LARGE Саратовский Государственный Университет}\\[1.5cm] % Main heading such as the name of your university/college - \textsc{\LARGE Саратовский Государственный Университет}\\[0.2cm] % Main heading such as the name of your university/college - \textsc{\Large Факультет Компьютерных Наук и Информационных Технологий}\\[0.5cm] % Major heading such as course name - - % \textsc{\large 1214}\\[0.5cm] % Minor heading such as course title - - %------------------------------------------------ - % Title - %------------------------------------------------ - - \HRule\\[0.6cm] - % {\huge\bfseries Универсальная прикладная алгебра}\\[0.4cm] % Title of your document - {\huge\bfseries\textsc \@title}\\[0.4cm] % Title of your document - - \HRule\\[1.5cm] - - %------------------------------------------------ - % Author(s) - %------------------------------------------------ - - % \begin{minipage}{0.4\textwidth} - % \begin{flushleft} - % \large - % \textit{Законспектировали}\\ - % \textsc{Андрей Гущин\\Иван Улитин\\Роман Стаин\\Николай Шустов} % Your name - % \end{flushleft} - % \end{minipage} - % ~ - % \begin{minipage}{0.4\textwidth} - % \begin{flushright} - % \large - % % \textit{Редактор}\\ - % % \textsc{Боба} % Supervisor's name - % \end{flushright} - % \end{minipage} - - % If you don't want a supervisor, uncomment the two lines below and comment the code above - {\large\textit{Законспектировал}}\\ - \textsc{\@author} % Your name - - %------------------------------------------------ - % Date - %------------------------------------------------ - - \vfill\vfill\vfill\vfill\vfill % Position the date 3/4 down the remaining page - - {\large\the\year{} г.} % Date, change the \today to a set date if you want to be precise - - %------------------------------------------------ - % Logo - %------------------------------------------------ - - %\vfill\vfill - %\includegraphics[width=0.2\textwidth]{placeholder.jpg}\\[1cm] % Include a department/university logo - this will require the graphicx package - - %---------------------------------------------------------------------------------------- - - \vfill % Push the date up 1/4 of the remaining page - -\end{titlepage} - -} -%----------------------------------------------------------------------------------------
\ No newline at end of file diff --git a/sem5/Makefile b/sem5/Makefile deleted file mode 100644 index 0fdb95a..0000000 --- a/sem5/Makefile +++ /dev/null @@ -1,7 +0,0 @@ -.PHONY: clean mrproper - -clean: - find . | grep -P "(.aux|.fdb_latexmk|.fls|.log|.synctex.gz|.out)" | xargs rm -f - -mrproper: clean - find . | grep -P "(.pdf|.md)" | xargs rm -f diff --git a/sem5/computer-networks/computer-networks.tex b/sem5/computer-networks/computer-networks.tex deleted file mode 100644 index b1ef05b..0000000 --- a/sem5/computer-networks/computer-networks.tex +++ /dev/null @@ -1,13 +0,0 @@ -\documentclass{../Lecture} -\usepackage{../preamble} - -\begin{document} - -\author{Андрей Гущин} -\title{Сети и системы передачи информации} -\maketitle - -\include{lectures/lecture1.tex} -\include{lectures/lecture5.tex} - -\end{document} diff --git a/sem5/computer-networks/lectures/lecture1.tex b/sem5/computer-networks/lectures/lecture1.tex deleted file mode 100644 index f992c47..0000000 --- a/sem5/computer-networks/lectures/lecture1.tex +++ /dev/null @@ -1,43 +0,0 @@ -\textbf{Лекция 1 (03.09.21)} -\section{Введение. Конвергенция сетей.} -Сети передачи информации являются логическим результатом эволюции двух важнейших -научно-технических отраслей вычислительной техники и телекоммуникационных -технологий. С одной стороны такие сети такие сети представляют собой -представляют собой группу компьютеров решающих набор взаимосвязанных задач. -Такая группа компьютеров является вычислительной сетью. С другой стороны, сеть -передачи информации может рассматриваться как средство передачи информации на -большие расстояния. - -Глобальные компьютерные сети много унаследовали от других более старых и -распространённых глобальных сетей. Главным технологическим отличием и новшеством -глобальных компьютерных сетей стал отказ от принципа коммутации каналов, который -успешно использовался в течение десятков лет в телефонных сетях. Для телефонных -сетей характерна коммутация каналов, а для компьютерных сетей --- коммутация -пакетов. - -Телефонный канал, который выделяется на всё время сеанса связи абонентов и -который резервирует фиксированную пропускную способность линии связи (как -правило 64 Кб/c) передаёт информацию с постоянной скоростью. Такой канал -связи не может эффективно использоваться пульсирующим трафиком компьютерных -данных у которого периоды интенсивного обмена чередуются с продолжительными -паузами. Пульсирующий и в значительной степени нечувствительный к задержкам -компьютерный траффик гораздо эффективнее передаётся сетями, работающими по -принципу коммутации пакетов, когда данные разделяются на небольшие порции, -называемые *пакетами*, которые самостоятельно перемещаются по сети благодаря -наличию адреса конечного узла в заголовке пакета. - -На первых порах для соединения компьютеров друг с другом использовались -нестандартные сетевые технологии. Сетевая технология --- согласованный набор -программных и аппаратных средств (например, драйверов, сетевых адаптеров, -кабелей и сетевых разъёмов), а также механизмов передачи данных по линиям -связи достаточный для построения вычислительных сетей, разнообразные средства -сопряжения, использующие собственные способы представления данных на линии -связи, свои типы кабелей и т.п., могли соединять только те типы компьютеров -для которых были разработаны. В середине 80-х годов утвердились стандартные -сетевые технологии объединения компьютеров в сеть, что способствовало их росту и -развитию. - -Одним из факторов способствования росту компьютерных сетей стали единые -стандарты. А вторым фактором стало появление персональных компьютеров. В -сетях, состоящих из персональных компьютеров можно было совместно использовать -дорогостоящие периферийные устроства и дисковые массивы. diff --git a/sem5/computer-networks/lectures/lecture5.tex b/sem5/computer-networks/lectures/lecture5.tex deleted file mode 100644 index 13cf56b..0000000 --- a/sem5/computer-networks/lectures/lecture5.tex +++ /dev/null @@ -1,81 +0,0 @@ -\section{Ethernet. Пример стандартной технологии с коммутацией пакетов.} - -Ethernet является одной из первых стандартных сетевых технологий, которая -работает с битовой скоростью 10МБ/с. Рассмотрим общие принципы функционирвания -Ethernet. - -\subsection{Топология} - -Существует два варианта технологии Ethernet: -\begin{itemize} - \item Ethernet на разделяемой среде; - \item Коммутируемый вариант Ethernet. -\end{itemize} - -В первом случае все узлы разделяют общую среду передачи данных. То есть -... по топологии общей шины. - -\textbf{Рисунок} - -Каналы связи бывают трёх типов: -\begin{itemize} - \item Симплексные; - \item Полудуплексные; - \item Полнодуплексные. -\end{itemize} - -2. Когда сеть Ethernet не использует разделяемую среду, а строится на коммутаторах, -объединённых дуплексными каналами связи говорят о коммутируемом варианте Ethernet. -Топология в этом случае является топологией дерева. - -\textbf{Рисунок} - -Для такой топологии между любыми двумя узлами сети существует ровно один путь. - -\subsection{Способ коммутации} - -В технологии Ethernet используется датаграммная коммутация пакетов, которая -основана на транспортном протоколе UDP. При такой коммутации между двумя -узлами не происходит предварительной договорённости о способе обмена пакетами -и не происходит контроля потери пакетов. И не происходит ... с целью повторной -отправки. - -Единицы данных, которыми обмениваются компьютеры в сети Ethernet называются -кадрами. Кадр наряду с полем данных содержит заголовок со служебной информацией, -которая используется для его коммутации и доставки. - -\subsection{Адресация} - -Каждый компьютер имеет уникальный аппаратный адрес, который ещё называют -Ethernet-адресом и который является плоским числовым адресом, то есть в отличие -от IP-адреса не имеет двухуровневую иерархическую структуру. MAC-адрес -идентифицирует компьютер в границах текущей локальной сети и не далее, то есть -по заданному MAC-адресу мы не можем доставить кадр в соседней локальной сети. - -Каждый ПК в локальной сети должен знать IP-адрес шлюза. - -\subsection{Разделение среды и мультиплексирование} - -В сети Ethernet на коммутаторах каждый канал является дуплексным каналом связи, -в следствии чего проблемы его разеления между интерфейсами узлов не возникает. -Передатчики Ethernet-коммутаторов используют дуплексные каналы связи для -мультиплексирования потока кадра от разных конечных узлов. - -В случае Ethernet на разделяемой среде (топология общая шина) информационные -потоки, поступающие от конечных узлов передаются в режиме разделения времени. - -\subsection{Кодирование} -Адаптеры в Ethernet работают с тактовой частотой 20 Мегагерц передавая в среду -прямоугольные импульсы, соответствующие 1 и 0. - -asfdkljadskljа коммутаторах каждый канал является дуплексным каналом связи, -в следствии чего проблемы его разеления между интерфейсами узлов не возникает. -Передатчики Ethernet-коммутаторов используют дуплексные каналы связи для -мультиплексирования потока кадра от разных конечных узлов. - -В случае Ethernet на разделяемой среде (топология общая шина) информационные -потоки, поступающие от конечных узлов передаются в режиме разделения времени. - -\subsection{Кодирование} -Адаптеры в Ethernet работают с тактовой частотой 20 Мегагерц передавая в среду -прямоугольные импульсы, соответствующие 1 и 0. diff --git a/sem5/databases/databases.tex b/sem5/databases/databases.tex deleted file mode 100644 index b9beb1a..0000000 --- a/sem5/databases/databases.tex +++ /dev/null @@ -1,13 +0,0 @@ -\documentclass{../Lecture} -\usepackage{../preamble} - -\begin{document} - -\author{Андрей гущин} -\title{Системы управления базами данных} -\maketitle - -\include{lectures/lecture1.tex} -\include{lectures/lecture2.tex} - -\end{document} diff --git a/sem5/databases/lectures/lecture1.tex b/sem5/databases/lectures/lecture1.tex deleted file mode 100644 index d1859d4..0000000 --- a/sem5/databases/lectures/lecture1.tex +++ /dev/null @@ -1,49 +0,0 @@ -% Лекция 1 (06.09) -\section{Архитектура ANSI-SPARC} - -\begin{itemize} - \item Внешний уровень (представления отдельных пользователей) - \item Концептуальный уровень (обобщённое представление пользователей) - \item Внутренний уровень (представление физического хранения) -\end{itemize} - -Модель данных включает, по меньшей мере, три аспекта: -\begin{itemize} - \item - \emph{аспект структуры} --- методы описания типов и логических - структур данных в базе данных; - \item \emph{аспект манипуляции} --- методы манипулирования данными; - \item - \emph{аспект целостности} --- методы описания и поддержки целостности - базы данных (корректных состояний базы данных). -\end{itemize} - -\subsection{Стуктурная часть реляционной модели} - -Включает следующие объекты: - -\begin{itemize} - \item домены - \item атрибуты - \item кортежи - \item отношения - \item потенциальные (возможные) ключи - \item первичные ключи -\end{itemize} - -Наименьшей единицей данных реляционной модели является атомарное -(неразложимое) для данной предметной области значение данных. - -\textbf{Домен} --- множество допустимых атомарных значений одного и того -же типа. Понятие домена несёт семантическую нагрузку: данные можно -сравнивать, только если они относятся к одному домену. Например, домены -цена и вес относятся к вещественному типу данных, но сравнивать значения -из этих доменов не имеет смысла. - -\begin{itemize} - \item - Минимальный набор атрибутов, который позволяет однозначно - идентифицировать сущность --- \emph{первичный ключ}. - \item \emph{Степень отношения} --- коничество атрибутов (столбцов). - \item \emph{Кардинальное число} --- количество кортежей (строк). -\end{itemize} diff --git a/sem5/databases/lectures/lecture2.tex b/sem5/databases/lectures/lecture2.tex deleted file mode 100644 index e7052ab..0000000 --- a/sem5/databases/lectures/lecture2.tex +++ /dev/null @@ -1,29 +0,0 @@ -% Лекция 2 (16.09.21) -\section{Целостность данных} - -NULL нельзя ни с чем сравнивать, любая операция с NULL даёт в результате NULL. - -\textbf{Целостность} в реляционной базе данных означает правильность -данных в любой момент времени. \textbf{Ограничения целостности} --- это -некие правила позволяющие поддерживать целостность данных в каждый -момент времени. Поддержание целостности базы данных может -рассматриваться как защита данных от неверных изменений или разрушений -(не путать с незаконными изменениями и разрушениями, являющимися -проблемой безопасности). Современные СУБД имеют ряд средств для -поддержания целостности. - -Выделяют три группы правил по целостности: - -\begin{itemize} - \item Целостность по сущностям; - \item Целостность по ссылкам (ограничения уровня БД); - \item Целостность, определяемая пользователем (ограничения уровня атрибута) -\end{itemize} - -\subsection{Целостность по сущностям} - -Так как потенциальные ключи фактически служат идентификаторами объектов -предметной области, то значения этих идентификаторов не могут сожержать -неизвестные значения. Это определяет следующее \emph{правило целостности -сущностей}: атрибуты, входящие в состав некоторого потенциального ключа -не могут принимать null-значений. 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/information-theory/lectures/lecture1.tex b/sem5/information-theory/lectures/lecture1.tex deleted file mode 100644 index 5cf5dc7..0000000 --- a/sem5/information-theory/lectures/lecture1.tex +++ /dev/null @@ -1,194 +0,0 @@ -\subsection{Лекция 1 (02.09.21)} - -Данные, полученные человеком будут называться сообщениями. Информацией -становятся те сообщения, которые используются для принятия каких-либо -решений, то есть снимается неопределённость, которая существовала до их -поступления. - -Следует отметить, что теория информации занимается изучением количества -информации безотносительно какого-то содержания сообщения. Все сообщения -в теории информации формализуются и изучается процесс формирования таких -сообщений и способов их передачи. - -Предметом изучения теории информации являются вероятностные -характеристики исследуемых объектов и явлений. - -Теория информации делится на: - -\begin{itemize} - \item - теорию передачи информации (предметом изучения являются оптимальные методы передачи сообщений); -\end{itemize} - -\textbf{рис. 1} - -Сигналом принято считать некоторую физическую хар-ку, изменяющуюся во -времени. Например, изменение напряжения во времени. - -В общем случае сигналом может быть любое изменение начального состояния -объекта, которое способно вызвать реакцию человека или принимающего -прибора. - -Различают сигналы: -\begin{itemize} - \item зрительные - \item звуковые - \item радиоэлектрические - \item радиосигналы -\end{itemize} - -Следует отметить, что одни сигналы могут как преобразовываться в другие, -так и сами являться источниками формирования новых сигналов. С точки -зрения изменения сигнала с течением времени различают \emph{статические} -и \emph{динамические}. - -Статические --- это сигналы, которые отображают устойчивое изменение -состояния объекта. Динамические --- это сигналы, отображающие -непрерывные изменения некоторого объекта, либо процесса при переходе от -одного устойчивого состояния к другому. К динамическим относятся все -виды электромагнитных колебаний, а также распространения звука в воде и -твёрдых предметах. - -По структуре сообщения сигналы делятся на \emph{непрерывные} и -\emph{дискретные}. Сигналы могут быть непрерывными и дискретными как по -времени, так и по множеству значений. Возможен один из четырёх видов -сигналов: -\begin{itemize} - \item полностью непрерывный сигнал (по времени и множеству значений) - \item непрерывный по множеству значений и дискретным по времени - \item дискретный по множеству значений и непрерывным по времени - \item полностью дискретный -\end{itemize} - -Носителем сигнала всегда является объект или процесс. Однако если -абстрагироваться от его физической природы, то существенными с точки -зрения теории информации будут только его вероятностные характеристики и -другие важные черты с точки зрения данного изучаемого процесса/сигнала. - -\textbf{В теории информации математическая модель сигнала может -противоречить реальной физической структуре.} Допустим, в теории инф мы -предполагаем, что структура сигнала известна приёмнику. - -\subsubsection{Обобщённое спектральное представление детерминированных -сигналов} - -Чтобы изучать непрерывные сигналы для начала изучаются детерминированные -сигналы, при этом они рассматриваются как некоторый ансамбль реализации \ldots{}. - -Мы будем использовать некоторую функцию - -\begin{equation} - u(t) = \sum_{k = 1}^{n} C_k \phi_k(t) \quad (1) -\end{equation} - -Искусственно ограничиваем $t$ некоторым \emph{промежутком времени} -$[t_1; t_2]$. Данная модель называется \textbf{линейной моделью сигнала}. Здесь -$\phi_k(t)$ --- базисные функции, а $C_k$ --- безразмерный -коэффициент. Если заданы все базисные функции, то функция $u(t)$ будет -определяться только коэффициентами $C_k$. Эти коэффициенты будут -называться \textbf{дискретным спектром сигнала}. За пределами интервала -$t \in [t_1; t_2]$ времени сигнал считается \emph{всегда} -\textbf{условно продолжающимся}. - -В некоторых задачах такое представление является неприемлемым, поэтому -для сигналов конечной длительности существует другое представление: - -\begin{equation*} - u(t) = \int_{-\infty}^{\infty} S(\alpha) \phi(\alpha, t) ; d\alpha \quad (2) -\end{equation*} - -Здесь $S(\alpha)$ называется \emph{спектральной плотностью}, а -$\phi(\alpha, t)$ \emph{базисной функцией}. Это модель \emph{непрерывного} сигнала. - -Раздел теории информации, который изучает сигналы в данных -представлениях, называется \textbf{спектральной теорией сигналов}. - -Чем сложнее базисная функция, тем реальнее и сложнее модель. - -В связи с этим обычно используют набор ортогональных базисных функций, -которые удовлетворяют следующему условию: - - -\begin{equation*} - \int_{t_1}^{t_2} \phi_k(t) \phi_l(t) d t = - \begin{cases} 0, &k \neq l \\ \mu, &k = l \end{cases} - \quad (3) -\end{equation*} - -То есть если умножить все $\phi_l (t)$ на данном интервале на коэффициент -$\frac{1}{\sqrt{\mu}}$, то мы получим ортонормированную функцию, то -есть -\begin{equation*} - \int_{t_1}^{t_2} \phi_k(t) \phi_l(t) dt = 1, \quad k = l -\end{equation*} - -Пусть имеется модель, удовлетворяющая условию ортонормированности. -Возьмём модель (1), обе части данной модели умножим на $\phi_l(t)$ и -проинтегрируем на интервале от $t_1$ до $t_2$. Получим - -\begin{equation*} - \int_{t_1}^{t_2} u(t) \phi_l(t) dt = - \int_{t_1}^{t_2} \sum_{k = 1}^{n} C_k \phi_k(t) \phi_l(t) dt = - \sum_{k = 1}^{n} C_k \int_{t_1}^{t_2} \phi_k(t) \phi_l(t) dt -\end{equation*} - -Получаем -\begin{equation*} - C_k = \int_{t_1}^{t_2} u(t) \phi_k(t) dt -\end{equation*} - -Исходя из этого получаем: -\begin{enumerate} - \item Каждый коэффициент $C_k$ может вычисляться независимо друг от друга - \item - Сложность их вычисления будет зависеть только от сложности вычисления - базисных функций, поэтому для изучения сигналов применяются системы - ортогональных функций, в частности применяются - \begin{enumerate} - \item Системы тригонометрических функций - \item Системы функций Хаара - \item Полиномы Лежандра - \item Полиномы Чебышева - \item Полиномы Лагерра - \item Полиномы Эрмита - \end{enumerate} -\end{enumerate} - -\subsubsection{Временная форма представления сигналов} - -Возьмём произвольную непрерывную функцию $u(t)$. Будем считать, что -непрерывная функция представляет собой набор функций примыкающих друг к -другу импульсов бесконечно малой длительности с амплитудой равной -значению сигнала в конкретный момент времени, то есть получим новую -модель, которая записывается через некоторую дельта-функцию. - - -\begin{equation*} - u(t) = \int_{-\infty}^{\infty} u(\tau) \delta(\tau - t) d\tau \quad (4) -\end{equation*} - -\begin{equation*} - \delta = \begin{cases} \infty, &t = \tau \\ 0, &t \neq \tau \end{cases} -\end{equation*} - -Ортонормируем дельта-функцию: - -\begin{equation*} - \int_{-\infty}^{\infty} \delta(\tau - t) d \tau = 1 -\end{equation*} - -Как видно, модель (4) является обобщённым спектральным представлением модели (2), -базисной функцией которого является дельта-функция. Таким же образом с -помощью этой модели мы можем построить дискретную модель, которая будет -называться \textbf{решётчатой} функцией: - -\begin{equation*} - u_l(t) = \sum_{k = -\infty}^{\infty} u(t) \delta(\tau - t), \quad \tau = \Delta t k -\end{equation*} - -$\Delta t$ --- период импульса. - -Пределы суммы могут быть как конечными, так и бесконечными исходя из -физической реальности. - -Эти две модели могут называться временными. diff --git a/sem5/information-theory/lectures/lecture2.tex b/sem5/information-theory/lectures/lecture2.tex deleted file mode 100644 index 5c4e598..0000000 --- a/sem5/information-theory/lectures/lecture2.tex +++ /dev/null @@ -1,180 +0,0 @@ -\subsection{Лекция 2 (09.09.21)} - -\subsubsection{Частотное представление периодических сигналов} - -\textbf{ЗАМЕНИТЬ $l$ на $e$ !!!} - -Рассмотрим детерминированный сигнал. В качестве базисной функции примем -$\phi(t) = e^{Pt}, \quad P = \pm j \omega$. Такое представление -функции базисных сигналов будет называться преобразованием Фурье. -Удобно: - применяя формулу Эйлера данное представление даёт возможность -представить в виде суммы гармоник. Формула Эйлера: -\[\cos \omega t = \frac{ e^{j \omega t} + e^{-j \omega t} }{ 2 }\] - -Предположим, что функция $u(t)$, которой описывается детерминируемый -сигнал реализуется на интервале $[t_1; t_2]$ и удовлетворяет условию -Дирихле. \emph{Условие Дирихле} означает, что функция непрерывна или -имеет конечное число точек разрыва первого рода, а также имеет конечное -число экстремумов. Определим период повторения функции как $T = t_2 - t_1$, при -этом предполагая, что функция продолжается на всём интервале времени. -Тогда формула сигнала $u(t)$ будет иметь следующий вид: \[ -\begin{cases} - u(t) = \frac{1}{2} \sum_{k = -\infty}^{\infty} A(j k \omega) e^{j k \omega_1 t} \\ - A(j k \omega_1) = \frac{2}{T} \int_{t_1}^{t_2} u(t) e^{-j k \omega_1 t} dt -\end{cases} -\], а период вычисляется как \[T = t_2 - t_1 = \frac{2 \pi}{\omega_1}\]. -A\_j\_k называют комплексным спектром периодического сигнала $u(t)$, а -значение этой функции для каждого конкретного $k$ будут называться -\emph{комплексной амплитудой}. - -Пусть $k \omega_1 = \omega$ то есть для данного комплексного спектра мы -попробуем построить огибающую. Тогда -\[ A(j \omega) = \frac{2}{T} \int_{t_1}^{t_2} u(t) e^{-j \omega t} dt \] - -Показательная форма: -\[ A(j k \omega_1) = A(k \omega_1) e^{j \phi(k \omega_1)} \] Функция -$A(k \omega_1)$ --- спектр амплитуд, $e^{j \phi(k \omega_1)}$ --- -спектр фаз. \textbf{Оба они дискретны}. Вторая форма: -\[ A(j k \omega_1) = A_k - j B_k \] -\[ A_k = \frac{2}{T} \int_{t_1}^{t_2} u(t) \cos(k \omega_1 t) dt \] -\[ B_k = \frac{2}{T} \int_{t_1}^{t_2} u(t) \sin(k \omega_1 t) dt \] -Отсюда видно, что \[ A(j \omega_1) = \sqrt{A_k^2 + B_k^2} \] -\[ \phi(k \omega_1) = \arctan \left( \frac{B_k}{A_k} \right) \] Если в -данных формулах положить $k = 0$, то получится равенство для -постоянной (огибающей) составляющей сигнала: -\[ \frac{A_0}{2} = \frac{1}{T} \int_{t_1}^{t_2} u(t) dt \] - -Отсюда: -\[ u(t) = \frac{A_0}{2} + \frac{1}{2} \sum_{k = 1}^{\infty} (A(j k \omega_1) e^{j k \omega_1 t} + A(-j k \omega_1) e^{-j k \omega_1 t}) = \frac{A_0}{2} + \sum_{k = 1}^{\infty} A(k \omega_1) \cos (k \omega_1 t - \phi(k \omega_1))\] - -Спектр амплитуд $A (k \omega_1)$ и спектр фаз $\phi (k \omega_1)$ согласно данному представлению могут быть -представлены в виде совокупности линий, каждая из которых соответствует -определённой частоте. Поэтому эти спектры называют \emph{линейчатыми}. -Сигналы, линейчатые спектры которых включают гармоники некоторых частот, -которые не кратны, называют \emph{почти периодическими}. - -Согласно этому представлению построим распределение энергии в спектре -периодического сигнала. - -\subsubsection{Распределение энергии в спектре периодических сигналов} - -Пусть имеется период $T$, сигнал периодический. Тогда распределение энергии в спектре -периодических сигналов будет определятся интегралом: -\[\int_{0}^{T} |u(t)|^2 dt = \int_{0}^{T} \left| \frac{A_0}{2} + \frac{1}{2} \sum_{k = 1}^{\infty} (A(j k \omega_1) e^{j k \omega_1 t} + A(-j k \omega_1) e^{-j k \omega_1 t}) \right|^2 dt = \] -\[ -= \frac{A_0^2}{4} \int_{0}^{T} dt + -\left( -\frac{A_0}{2} \sum_{k=1}^{\infty} A(jk\omega_1) \int_0^T e^{jk\omega_1 t} dt + \frac{A_0}{2} \sum_{k = 1}^\infty A(-j k \omega_1) \int_0^T e^{-j k\omega_1 t} dt + -\right) \] -\[ + \frac{1}{2} \sum_k \sum_l A(j k \omega_1) A(-j l \omega_1) \int_0^T e^{j k \omega_1 t} e^{-j k \omega_1 t} dt\] - -\[ \int_0^T e^{jk\omega_1 t} dt = \int_0^T e^{-j k \omega_1 t} dt = 0 \] -Эти два интеграла будут равны 0, если $k$ - -\[ \int_0^T e^{j \omega_1 t (k - l)} dt = \begin{cases} - T, k = l \\ - 0, k \neq l -\end{cases}\] - -В результате этого у нас останется -\[ \int_0^T |u(t)|^2 dt = \frac{A_0^2}{2} * \frac{T}{2} + \frac{T}{2} \sum_{k = 1}^{\infty} | A(j k \omega_1) |^2 \] - -Вывод: согласно данному представлению получаем, что средняя за период -энергия будет равна сумме средних энергий, выделяемых каждой гармоникой. - -\subsubsection{Частотное представление непериодических сигналов} - -Предположим, что соответствующая реальному непериодическому сигналу -$u(t)$ удовлетворяет условию Дирихле и абсолютно интегрируема. Тогда -спектральное представление непериодического сигнала $u(t)$ можно строить -путём увеличения периода периодического сигнала до бесконечности. - -С учётом того, что использовался период $\frac{2\pi}{\omega_1}$ будет -иметь представление: -\[ u(t) = \frac{1}{2} \sum_{k = -\infty}^{\infty} \left( \frac{\omega_1}{\pi} \int_{t_1}^{t_2} u(t) e^{-j k \omega_1 t} dt \right) e^{jk \omega_1 t} \] - -Осуществим предельный переход, при этом $T \to \infty$. При этом сумма -перейдёт в интеграл, $\omega_1 = \Delta \omega \to d \omega$, -$k\omega_1 \to \omega$. В результате этих преобразований $u(t)$ -Будет иметь вид: -\[ u(t) = \frac{1}{2\pi} \int_{-\infty}^{\infty} ( \int_{-\infty}^\infty u(t) * e^{-j \omega t} dt) e^{j \omega t} d\omega \] - -Обозначим за $S(j\omega)$ выражение $\int_{-\infty}^\infty u(t) * e^{-j \omega t} dt$, получим: -\[ u(t) = \frac{1}{2\pi} \int_{-\infty}^\infty S(j\omega) e^{j\omega t} d\omega \] -\[ S(j\omega) = \int_{-\infty}^\infty u(t) e^{-j\omega t} dt \] - -Эта пара называется парой преобразования Фурье для непериодического -сигнала. - -Функция $S (j\omega)$ называется комплексной спектральной плотностью или -спектральной характеристикой непериодического сигнала. По аналогии с -период сигналом, спектральная характеристика имеет следующие два представления: Показательная -форма: \[ S(j \omega) = S(\omega) e^{-j\phi(\omega)} \] - -$S(\omega)$ -- спектральная плотность амплитуд, Спектр фаз --- $e^{-j\phi(\omega)}$. - -Построим алгебраическую форму: - -\[ e^{-j\omega t} = \cos(\omega t) - j \sin(\omega t)\] -\[ S(j \omega) = A(\omega) - j B(\omega) \], где -\[ A(\omega) = \int_{-\infty}^{\infty} u(t) \cos(\omega t) dt \] -\[ B(\omega) = \int_{-\infty}^{\infty} u(t) \sin(\omega t) dt \] - -При этом $S(j \omega)$ будет представлена через \[ S(\omega) = \sqrt{|A(\omega)|^2 + |B(\omega)|^2} \] -\[ \phi(\omega) = \arctan \frac{B(\omega)}{A(\omega)} \] - -\ldots{} - -\[ S(\omega) = |S(j \omega)| \] - -\ldots{} - -\[ u(t) = \frac{1}{2\pi} \int_{-\infty}^{\infty} S(\omega) e^{j(\omega t - \phi(\omega))} d\omega = -\frac{1}{2 \pi} \int_{-\infty}^\infty S(\omega) \cos(\omega t) - \phi(\omega)) d\omega + j \int_{-\infty}^\infty S(\omega) * \sin(\omega t * \phi(\omega) d \omega) \] - -Второй интеграл будет = 0 в силу четности, а первый в силу \ldots{} можно записать только ???. Таким образом мы получим -тригонометрическую форму ряда фурье. -\[ u(t) = \frac{1}{\pi} \int_0^\infty S(\omega) \cos(\omega t - \phi(\omega)) d\omega \] - -Если ограничить функцию $u(t)$ интервалом времени от $t1$ до $t2$, то можно записать функцию - -\[ S(j \omega) = \int_{t_1}^{t_2} u(t) e^{-j\omega t} dt \] - -Обращаясь к предыдущим вычислениям, получим \[ A(j \omega) = \frac{2}{T} S(j \omega) \] - -Если у непериодического сигнала взять единичный импульс, можно построить -линейчатый спектр его периодической последовательности. - -\subsubsection{Распределение энергии в спектре непериодического сигнала} - -Выражение для величины, характеризующей энергию для \ldots{} запишем след образом: -\[ \int_{-\infty}^{\infty} |u(t)|^2 dt = \int_{-\infty}^{\infty} u(t) (\frac{1}{2\pi} \int_{-\infty}^{\infty} S(j\omega) e^{-j\omega t} d\omega ) dt = \] -\[ = \frac{1}{2\pi} \int_{-\infty}^{\infty} S(j\omega) (\int_{-\infty}^\infty u(t) e^{j \omega t} dt) d\omega = \] -\[ = \frac{1}{2\pi} \int_{-\infty}^{\infty} S(j\omega) S(-j\omega) d\omega = \frac{1}{2\pi} \int_{-\infty}^\infty |S(j\omega)|^2 d\omega \] - -Согласно равенству Персиваля -\[ = \frac{1}{\pi} \int_0^\infty |S(j \omega)|^2 d\omega \] В соответствии с -этим равенством энергия выделяемая непериодическим сигналом за всё время -его существования можно определить, интегрируя квадрат модуля -спектральной характеристики в интервале частот. - -Определим соотношение между длительностью сигнала и шириной его спектра. -Предположим, что сигнал $u(t)$ имеет определённую продолжительность и -имеет спектральную характеристику $S(j\omega)$. Увеличим длительность -сигнала в некоторую $\lambda$ раз и найдём соответствущую -спектральную характеристику -\[ S_\lambda (j\omega) = \int_{-\infty}^\infty u(\lambda t) e^{-j \omega t} dt = \] -Пусть есть некоторое $\tau = \lambda t$. Тогда -\[ = \frac{1}{\lambda} \int_{-\infty}^\infty u(\tau) e^{-j \omega \tau / \lambda} d\tau = \frac{1}{\lambda} S(j \frac{\omega}{\lambda}) \] - -Из данного равенства видно, что спектр удлиннённого или укороченного в -$\lambda$ раз будет в $\lambda$ уже или шире, при этом коэффициент в -$\frac{1}{\lambda}$ изменяет только амплитуды гармоник и не влияет на -ширину спектра. Это связано с тем, что переменные $t$ и $\omega$ -находятся в показателе степени экспоненциальной функции как прямого преобразования -Фурье, так и обратного. Из этого следует, что длительность сигнала и -ширина его спектра не могут быть одновременно ограничены конечными -интервалами. В частности, имеет место соотношение -$\Delta t : \Delta f = const$, где $\Delta t$ --- длительность -импульса, а $\Delta f$ --- ширина. - diff --git a/sem5/information-theory/lectures/lecture3.tex b/sem5/information-theory/lectures/lecture3.tex deleted file mode 100644 index 2103c8d..0000000 --- a/sem5/information-theory/lectures/lecture3.tex +++ /dev/null @@ -1,198 +0,0 @@ -\subsection{Лекция 3 (16.09.21)} - -\subsubsection{Модели случайных сигналов} - -Наиболее точной моделью сигнала при изучении вопросов его передачи -является \emph{случайный процесс} для которого детерминированные функции -рассматриваются ка отдельные реализации. Случайным процессом будем -называть функцию $U(t)$, значение которой в каждый момент времени -является случайной величиной. По аналогии, случайные процессы могут быть -непрерывные и дискретные как по времени, так и по множеству состояний. -ТО есть по аналогии с классификацией детерминированных сигналов, можно -выделить один из четырёх типов случайного процесса: - непрерывный -случайный процесс по множеству состояний (континууму), при этом -изменения состояния возможны в любой момент времени; - непрерывная -случайная последовательность --- изменения состояний допускаются лишь в -конечном числе моментов времени; - дискретный случайный процесс --- -множество состояний конечно, но изменения состояний могут происходить в -произвольные моменты времени; - дискретная случайная последовательность ---- состояния из конечного множества могут изменяться в конечном числе -моментов времени. - -Для описания свойств случайного процесса мы будем использовать -$n$-мерную плотность вероятности. - -\begin{equation*} - P_N(U_1, U_2, \dots, U_N; t_1, t_2, \dots, t_N) -\end{equation*} - -$n$-мерную плотность вероятности --- система $N$ случайных величин -$U_1, U_2, \dots, U_N$, где -$U_1 = U(t_1), U_2 = U(t_2), \dots U_N = U(t_N)$ взятых в моменты -времени $t_1, t_2, \dots, t_N$. Как частный случай будет -использоваться одномерная плотность вероятности $P_1(U; t)$, которая -будет характеризовать распределение случайной величины в произвольный -момент времени $t$. Если мы возьмём двумерную плотность вероятности -$P_2(U_1, U_2; t_1, t_2)$, то мы получим вероятность совместных -реализаций значений случайных величин в произвольные моменты времени -$t_1, t_2$. При этом будут иметь место соотношения - -\begin{equation*} - P_1(U; t) = \int_{-\infty}^{\infty} P_2(U_1, U_2; t_1, t_2) d U_2 -\end{equation*} - -Работа со случайными величинами высоких порядков является крайне -трудоёмкой вещью, поэтому для характеристики случайного процесса будут -использованы моменты функций первого порядка и второго порядка. (мат -ожидание, дисперсия и корелляционная функция). - -Математическим ожиданием случайного процесса $U(t)$ будем называть -неслучайную функцию $m_U(t)$ значение которой в каждый момент времени -равно математическому ожиданию случайной величины в соответствующем -сечении случайного процесса. -\begin{equation*} - m_U(t) = M\{U(t)\} = \int_{-\infty}^{\infty} U P_1(U; t) dU -\end{equation*} - -Дисперсией случайного процесса $U(t)$ будем называть функция -$D_U(t)$, значение которой в каждый момент времени равно дисперсии -случайной величины в соответсвующем сечении случайного процесса. -\begin{equation*} - D_U(t) = M\{U^o(t)\} = \int_{-\infty}^\infty U^o(t)^2 P_1(U; t) dU -\end{equation*} -Где $U^o$ (o над U) --- нызвается центрированной случайной величиной в -сечении $t$ ($U^o(t) = U(t) - m_U$) - -Кореляционной функции случайного процесса $U(t)$ называют неслучайную -функцию $R_U(t_1; t_2)$, которая для каждой пары произвольно выбранных -значений $t_1$ и $t_2$ равна кореляционному моменту соответствующих -сечений случайного процесса. -\begin{equation*} - R_U(t_1; t_2) = M\{U^o(t_1) U^o(t_2)\} = \int_{-\infty}^\infty \int_{-\infty}^\infty U^o(t_1) U^o(t_2) \cdot P_2 (U_1, U_2; t_1, t_2) dU_1 dU_2 -\end{equation*} -Где $U^o(t_1)$ --- нызвается центрированной случайной величиной в -сечении $t_1$ ($U^o(t_1) = U(t_1) - m_U(t_1)$), а $U^o(t_2)$ --- -нызвается центрированной случайной величиной в момент времени $t_2$ -($U^o(t_2) = U(t_2) - m_U(t_2)$). - -Нормированная автокореляционная функция -\begin{eqnarray} - \rho_U(t_1; t_2) = \frac{R_U(t_1; t_2)}{\sigma_U(t_1) \sigma_U(t_2)} \\ - \sigma_U(t_1) = \sqrt{D_U(t_1)} \\ - \sigma_U(t_2) = \sqrt{D_U(t_2)} -\end{eqnarray} - - -Следует отметить, что если произвольные моменты $t_1 = t_2 = t$, то -автокорелляционная функция выражается в дисперсию, а соответствующая ей -нормированная автокореляционная функция будет равна $1$. - -Если имеется два случайных процесса, то можно рассматривать функцию -взаимной кореляции: -\begin{equation*} - R_{UV}(t_1; t_2) = M\{ U^o (t_1) V^o(t_2) \} -\end{equation*} - -С точки зрения изменчивости указанных характеристик различают -стационарные и нестационарные случайные процессы. Случайный процесс -будет называться в узком смысле, если описывающий его плостности -вероятности не зависят он начала отсчёта времени. Случайный процесс -называют стационарным в широком смысле, если выполняются следующие -соотношения: -\begin{equation*} - \begin{cases} - m_U(t) = m_U = const \\ - D_U(t) = D_U = const \\ - R_U(t, t + \tau) = R_U(\tau) - \end{cases} -\end{equation*} - -То есть мат ожидание и дисперсия постоянны, а кореляционная функция не -зависит он начала отсчёта времени и является функцией одного аргумента -(шага по времени). Обычно предполагается, что стационарный процесс -является \emph{эрготическим} (то есть средняя по ансамблю реализация -равно среднему по времени на одной реализации) если мат ожидание -\begin{eqnarray} - m_u = \lim_{T \to \infty} U(t) dt = U_0 \\ - D_U = \lim_{T \to \infty} \int_0^T (U(t) - U_0)^2 dt \\ - R_U(\tau) = \lim_{T \to \infty} \int_0^T (U(t) - U_0) (U(t + \tau) - U_0) dt -\end{eqnarray} - -Эрготичность стационарного сигнала будет перетекать в эрготичность -источника. - -\subsubsection{Спектральной представление случайных сигналов} - -Аналогично детерминированному сигналу построим для случайного процесса -представление через сумму спектральных составляющих. Для этого будем -использовать так называемое каноническое разложение случайного процесса -$U(t)$, то есть будет представляться в виде: -\begin{equation*} - U(t) = m_U(t) + \sum_K C_k \phi_k(t) \quad (1B) -\end{equation*} - -$m_U(t)$ --- мат ожидание, $\phi_k(t)$ --- неслучайные (координатные) базисные функции, -$C_k$ --- некореллированные случайные случайные величины с мат -ожиданиями равными нулю и дисперсиями $D_k$, где -\begin{equation*} - M_k[C_k C_l] = \begin{cases} P_k, k = l \\ 0, k \neq l \end{cases} -\end{equation*} - -Слагаемые $C_k * \phi_k(t)$ будут называть элементарным случайным -процессом. Случайность такого процесса будет проявляться только через -величину $C_k$. $C_k$ будут называться коэффициентами канонического -разложения. - -Найдём кореляционную функцию случайного процесса $U(t)$, который -представлениследующим элементарным процессом. -\begin{equation*} - R_U(t_1, t_2) = M\{ \sum_k C_k \phi_k(t_1) \sum_l C_l \phi_l(t_2) \} = \sum_{k, l} M\{ C_k C_l \} \phi_k(t_1) \phi_l(t_2) = -\end{equation*} - -Так как $C_k$ и $C_l$ некореллируемые величины, то для \ldots{} -получим следующее выражение. -\begin{equation*} - = \sum_k \phi_k(t_1) \phi_k(t_2) D_k \quad (2B) -\end{equation*} - -Такое представление корелляционной функций называют каноническим -разложением кореляционной функции случайного процесса $U(t)$. Всякому -каноническому разложению случайного процесса (1B) соответствует -каноническое разложение (2B). Это утверждение доказывается при этом -будет справедливо и обратное утверждение. - -Рассмотрим каноническое разложение корелляционной функции. Пусть -$t_1 = t_2 = t$. Тогда получим формулу: -\begin{equation*} - = \sum_k D_k(\phi_k(t))^2 -\end{equation*} - -То есть при выбранном наборе -координатной функции центрированный случайный процесс будет -характеризоваться совокупностью дисперсий коэффициентов разложения, -которые можно рассматривать как обобщённый спектр случайного процесса. - -Для построения спектра случайного процесса нам необходимо найти все -функции $\phi_k(t)$ и некореллированные случайные величины $C_k$, -что во многих случаях представляется достаточно затруднительной задачей. -Пусть $\phi_k$ являются ортогональными координатными функциями и будет -справедливо следующее представление: -\begin{equation*} - \int_{-T/2}^{T/2} m_u^2(t) dt < \infty -\end{equation*} - -Тогда неслучайную функцию $m_u(t)$ на интервале $T$ можно разложить следующим образом: -\begin{equation*} - m_u(t) = \sum_k m_{uk} \phi_k(t) -\end{equation*} - -Здесь $m_{uk} = \int_{-T/2}^{T/2} m_u(t) \phi_k(t) dt$. Тогда -каноническое разложение случайного процесса запишется следующим видом: -\begin{equation*} - U(t) = \sum_k m_{uk} + C_k) \phi_k(t) \quad (3B) -\end{equation*} - -Это соотношение -будет называться \emph{обобщённым спектральным представлением для -случайного процесса, которое раскладывается в каноническое -представление}.
\ No newline at end of file diff --git a/sem5/information-theory/lectures/lecture4.tex b/sem5/information-theory/lectures/lecture4.tex deleted file mode 100644 index 0c2d14f..0000000 --- a/sem5/information-theory/lectures/lecture4.tex +++ /dev/null @@ -1,234 +0,0 @@ -\subsection{Лекция 4 (23.09.21)} - -\subsubsection{Частотное представление стационарных сигналов. Дискретные -спектры.} - -Предположим, что случайный процесс задан на интервале $[-T; T]$. Тогда -соответствующая ему корреляционная функция $R_u(\tau)$ должна -рассматриваться на интервале \ldots{} . При этом должно выполняться -равенство $\tau \in [-2T; 2T]$. Будем считать корреляционную функцию -$R_u(\tau)$ условно продолжающейся с периодом $4T$. Тогда для неё -можно записать пару преобразований Фурье: - -\begin{equation*} - R_u(\tau) = \frac{1}{2} \sum_{k = -\infty}^\infty D_k e^{jk\omega_1 \tau} -\end{equation*} -Где -\begin{equation*} - D_k = \frac{1}{2T} \int_{-2T}^{2T} R_u(\tau) e^{-jk\omega_1 \tau} d\tau -\end{equation*} -и -\begin{equation*} - \omega_1 = \frac{2\pi}{4T} = \frac{\pi}{2T} -\end{equation*} - -Учитывая то, что корреляционная функция является функцией чётной, то -$D_k$ можно представить на полупериоде, то -\begin{equation*} - D_k = \frac{1}{2T} \int_{0}^{2T} R_u(\tau) e^{-jk\omega_1 \tau} d\tau -\end{equation*} - -Пусть $\tau = t_1 - t_2$. Тогда корелляционная функция будет -представляться следующим образом: -\begin{equation*} - R_u(t_1 - t_2) = \frac{1}{2} \sum_{k = -\infty}^\infty D_k e^{jk\omega_1 t_1} e^{-jk\omega_1 t_1} -\end{equation*} - -Сравнивая с данным разложением корелляционной функции с каноническим -разложением кореляционной функции можно заметить, что $\phi_k(t_1)$ и -$\phi_k(t_2)$ будут представляться через экспоненциальные функции. -$\phi_k(t_1) = e^{jk\omega_1 t_1}$, $\phi_k(t_2) = e^{-jk\omega_1 t_2}$ - -Возьмём соответствующее этому каноническое разложение центрированного -случайного процесса, то есть -\begin{equation*} - U^o (t) = \frac{1}{2} \sum_{k = -\infty}^\infty C_k e^{jk\omega_1 t} -\end{equation*} - -добавим для обобщения мат ожидание стационарного случайного процесса. В -результате при объединении экспоненциальных составляющих с одинаковыми -по абсолютной величине индексами разных знаков стационарный случайный -процесс на ограниченном интеравале времени будет представляться суммой -гармоник. То есть -\begin{equation*} - U(t) = m_u + \sum_k (a_k \cos (\omega_1 t) + b_k \sin(\omega_1 t))) -\end{equation*} - -где $\omega_1 = \frac{\pi}{2T}$, $m_u$ --- мат ожидание -стационарного процесса, $a_k$ и $b_k$ --- неслучайные величины. - -Эта форма показывает, что получившиеся спектры являются линейчатыми, то -есть каждой гармонике на спектральной диаграмме будет соответствовать -вертикальный отрезок, длина которого пропорциональна дисперсии амплитуд. - -\#\#\# Частотное представление стационарных случайных сигналов. -Непрерывные спектры. - -Для описания случайного стационарного сигнала возьмём интервал -$(-\infty; \infty)$ и построим его интегральное каноническое -разложение. Для этого немного изменим для кореляционной функции. -\begin{equation*} - R_u(\tau) = \frac{1}{2} \sum_{k = -\infty}^\infty \frac{D_k}{\Delta \omega} e^{jk\omega_1 \tau} \Delta \omega -\end{equation*} - -Где $\Delta \omega$ --- шаг по частоте и он равен -$\omega_{k + 1} - \omega_k = \frac{\pi}{2T}$. \ldots{} характеризующий -интервал частот между соседними гармониками. - -Обозначим через -\begin{equation*} - S_u(k \omega_1) = \frac{D_k}{\Delta \omega} = \frac{2T D_k}{\pi} -\end{equation*} - -Функция $S_u(k \omega_1)$ будет называться \textbf{средней плотностью -дисперсии стационарного процесса}. По сути своей данная функция является -дисперсией, которая приходится на единицу длины частотного интервала. - -С учётом сделанных обозначений формула для кореляции будет иметь -следующий вид: -\begin{equation*} - R_u(\tau) = \frac{1}{2} \sum_{k = -\infty}^\infty S_u(k\omega_1) e^{jk\omega_1 \tau} \Delta \omega -\end{equation*} - -С учётом \ldots{} можем записать в следующем виде - -\begin{equation*} - S_u(k \omega_1) = \frac{1}{\pi} \int_{-2T}^{2T} R_u(\tau) e^{-jk\omega_1 \tau} d\tau -\end{equation*} - -Осуществим предельный переходи при $t \to \infty$. Получим: -$S_u(k \omega_1) \to S_u(\omega)$, $k\omega_1 \to \omega$, -$\Delta \omega \to d\omega$ - -Тогда получим для кореляции: - -\begin{equation*} - \begin{cases} - R_u(\tau) = \frac{1}{2} \int_{-\infty}^\infty S_u(\omega) e^{j\omega\tau} d\omega \\ - S_u(\omega) = \frac{1}{\pi} \int_{-infty}^\infty R_u(\tau) e^{-j\omega\tau} d\tau - \end{cases} -\end{equation*} - -Величина $S_u(\omega) d\omega$ по смыслу \ldots{} представляет собой -дисперсию, приходящуюся на спектр частот - -Функция $S_u(\omega)$ характеризует распределение дисперсии случайного -процесса по частотам и называется \emph{спектральной плотностью -стационарного случайного процесса}. Аналогично вышеизл мат. если мы для -кореляционной функции применим каноническое разложение, то получим -следующую формулу: -\begin{equation*} - R_u(\tau) = \frac{1}{2} \int_{-\infty}^\infty S_u(\omega) e^{j\omega\tau_1} e^{-j\omega\tau_2} d\omega -\end{equation*} - -Согласно данному каноническому представлению дисперсии построим -каноническое распределение случайного процесса. Для этого -\begin{equation*} - U^o(t) = \frac{1}{2} \sum_{k = -\infty}^\infty \frac{C_k}{\Delta \omega} e^{jk\omega_1 t} \Delta \omega -\end{equation*} - -Введём обозначение $G_u(\omega_k) = \frac{C_k}{\Delta \omega}$ и -осуществим предельный переход. Тогда центрированный случайный процесс -будет иметь следующий вид: -\begin{equation*} - U^o(t) = \frac{1}{2} \int_{-\infty}^\infty G_u(\omega) e^{j\omega t} d\omega -\end{equation*} - -В силу сделанных обозначений очевидно, что функция -$G_u(\omega) d\omega$ является случайной функцией с дисперсией -$S_u(\omega) d\omega$ приходящейся на спектральную составляющую . - -\subsubsection{Спектральная плотность мощности.} - -Перейдём к одностороннему спектру для положительных частот. Для функции -$S_u(\omega)$ применим формулу Эйлера и представим её \ldots{} -\begin{equation*} - S_u(\omega) = \frac{1}{\pi} \int_{-\infty}^\infty R_u(\tau) \cos(\omega \tau) d\tau - \frac{j}{\pi} \int_{-\infty}^\infty R_u(\tau) \cdot \sin (\omega \tau) d\tau -\end{equation*} - -В силу чётности \ldots{} а первый интеграл мы можем записать для -положительных частот: -\begin{equation*} - S_u(\omega) = \frac{2}{\pi} \int_0^\infty R_u(\tau) \cos(\omega \tau) d \tau -\end{equation*} - -Отсюда следует, что $S_u(\omega)$ также является действительной и -чётной функцией, а след. таким же образом мы можем ограничить и корел. -функиц. -\begin{equation*} - R_u(\tau) = \int_0^\infty S_u(\omega) \cos(\omega\tau) d\omega -\end{equation*} - -Если в данном выражении $\tau$ положить $0$, то мы получим формулу -для дисперсии. \begin{equation*} - R_u(0) = D_k = \int_0^\infty S_u(\omega) d\omega -\end{equation*} - -Соответственно дисперсия будет характеризовать мощность сигнала, поэтому -функцию $S_u(\omega)$ называют \emph{спектральной плотностью -мощности}. - -\subsubsection{Преобразование непрерывных сигналов в дискретные.} - -\paragraph{Формулировка задачи дискретизации} - -Дискретизация сигнала --- это первообразные функции непрерывного -аргумента в функцию дискретного времени. То есть дискретизация -заключается в замене непрерывного сигнала $U(t)$ совокупностью -координат $[c_1, c_2, \dots, c_n] = A[u(t)]$, где $A[.]$ --- -некоторый оператор. - -С точки зрения простоты реализации целесообразно использовать линейные -операторы, в частности для определения координат сигнала удобно -использовать соотношение -\begin{equation*} - C_i = A[u(t)] = \int_T \phi_i(t) u(t) dt \quad (1) -\end{equation*} - -Где $\phi_i(t)$ --- набор базисных функций (как правило ортогональных). - -При последующем использовании дискретного сигнала для цели управления им -обычно осуществляется его восстановление с использованием другого -заданного оператора: -\begin{equation*} - U^*(t) = B[c_1, c_2, \dots, c_n] -\end{equation*} - -Если у нас дискретизация осуществлялась помощью оператора (1), то для -восстановления будет использован следующий оператор: -\begin{equation*} - U^*(t) = \sum_{i = 1}^N c_i \phi_i(t) -\end{equation*} - -Следует отметить \ldots{} в следствии применения операции интегрирования -будет обладать высокой помехоустойчивостью, но при этом будет иметь -место задержка сигнала на интервал интегрирования $T$, поэтому -наиболее часть дискретизация сводится к замене сигнала совокупностью его -мгновенных значений в отведённые моменты времени. При этом эта -совокупность будет называться \textbf{выборкой мгновенных значений}. Это -достигается использованием дельта-функций в качестве набора базисных -функций. В результате получится некоторая решётчатая функция с -координатами $c_i = u(t_i)$. При этом если шаг дискретизации будет -постоянным, то дискретизация будет называться \textbf{равномерной}. - -При восстановлении таких непрерывных сигналов для обеспечения простоты -реализации широго применяются неортогональные базисные функции, в -частности используются степенные алгебраические полиномы. -Восстановленный сигнал будет в этом случае: -\begin{equation*} - U^*(t) = \sum_{i = 0}^N a_i t^i -\end{equation*} - -Представление непрерывного сигнала некоторой совокупностью -равноотстоящих отсчётов является наиболее распространённым способом -дискретизации. Обычно она осуществляется для дальнейшего преобразования -сигнала в цифорвую форму. В результате цифрового кодирования дискретного -сигнала происходит его квантование, то есть замена в соответствующие -моменты времени мгновенных значений ближайшими разрешёнными. При этом -сигнал оказывается дискретным как по множеству значений, так и по -времени. Преимуществом такого представления сигнала состоит в том, что -множество уровней квантования можно представить небольшим количеством -разрядов. Кроме того при цифровом представлении сигнала для его -обработки могут быть использованы сложные алгоритмы, в том чистле -алгоритм поиска и исправления ошибок при передаче. - diff --git a/sem5/information-theory/lectures/lecture5.tex b/sem5/information-theory/lectures/lecture5.tex deleted file mode 100644 index a202dd5..0000000 --- a/sem5/information-theory/lectures/lecture5.tex +++ /dev/null @@ -1,3 +0,0 @@ -\subsection{Лекция 5 ()} - -\subsubsection{Критерий качества восстановления непрерывного сигнала} diff --git a/sem5/information-theory/lectures/lecture6.tex b/sem5/information-theory/lectures/lecture6.tex deleted file mode 100644 index 1907f9d..0000000 --- a/sem5/information-theory/lectures/lecture6.tex +++ /dev/null @@ -1,154 +0,0 @@ -% Лекция (14.10.21) -\begin{enumerate} - \item - Критерий равномерного приближения - $$\max_{t \in T} |u(t) - u^*(t)| \leq \xi_{\text{доп}}$$ - $$sup_{u_i(t) \in U} |u_i(t) - u^*_i(t)| \leq \xi_\text{доп}$$ - \item - Критерий среднеквадратичного отклонения - $$\sigma = \sqrt{\frac{1}{T} \int_T|u(t) - u^*(t)|^2 dt} \leq \sigma_\text{доп}$$ - $$\sigma_\Sigma = \Sigma_{i = 1}^N$$ - \item - Интегральный критерий - $$\varepsilon = \frac{1}{T} \int_T |u(t) - u^*(t)| dt$$ - - Интегральный критерий для ансамбля вычисляют путём усреднения по ансамблю. - \item - Допустимый уровень вероятности того, что ошибка не превысит допустимое значение - -\end{enumerate} - -Использование каждого из критериев будет зависеть от требований, предъявляемых к системе. - -\subsection{Теорема Котельникова} -Как отмечалось ранее, наиболее широкое применение имеет линейная дискретизация, -при этом для выбора величины шага дискретизации используется модель сигнала в -виде эргодического случайного процесса, при этом каждая реализация которого -представляет собой функцию с ограниченным спектром. Теоретической основой для -такого подходя является теорема Котельникова. - -\begin{theorem}[Теорема Котельникова] - Любая функция $u(t)$, допускающая преобразование Фурье и имеющая непрерывный - спектр, ограниченная полосой частот $[0; \frac{\omega}{2\pi}]$ полностью - определяется дискретным рядом своих мгновенных значений, отсчитанный через - интервал времени $\Delta t = \frac{1}{2f_c} = \frac{\pi}{\omega}$ -\end{theorem} -\begin{proof} - Поскольку по предложению теоремы функция $u(t)$ имеет ограниченный спектр, то - есть $S(j \omega) = 0 \quad \omega > \omega_c$, то функцию $u(t)$ мы можем - записать следующим видом: - - \begin{equation*} - u(t) = \frac{1}{2\pi} \int_{-\omega_c}^{\omega_c} S(j\omega) e^{j\omega t} d\omega - \end{equation*} - - Тогда функцию $S(j \omega)$ на интервале $[-\omega_c; \omega_c]$ можно - разложить в ряд Фурье. - - Тогда пару преобразования Фурье запишем, полагая, что $S(j\omega)$ условно - продолжающаяся с периодом $2\omega_c$. - - \begin{equation*} - \begin{cases} - S(j\omega) = \frac{1}{2} \sum_{-\infty}^\infty H_k e^{jk\omega \Delta t} \\ - A_k = \frac{1}{\omega_c} \int_{-\infty}^\infty S(j\omega) e^{-jk \Delta t \omega} d\omega - \end{cases} - \end{equation*} - - Используя данную пару преобразования Фурье, предварительно предположив, что - $t_k = k \Delta t$, будет иметь следующий вид: - \begin{equation*} - u(k \Delta t) = \frac{1}{2\pi} \int_{-\infty}^\infty S(j\omega) e^{jk\Delta t \omega} d \omega - \end{equation*} - - \begin{equation*} - A_k = \frac{2\pi}{\omega_c} u(-k \Delta t) - \end{equation*} - - \begin{equation*} - S(j\omega) = \frac{\pi}{\omega_c} \sum u(-k \Delta t) e^{jk \Delta t \omega} - \end{equation*} - - В последнем равенстве знак - перед $k$ мы можем поменять на обратный, так - как суммирование ведётся как по положительным, так и по отрицательным числам. - Подставив ... получим: - \begin{equation*} - u(t) = \frac{1}{2\omega_c} \int_{-\infty}^\infty |\sum_{-\infty}^\infty u(k\Delta t) e^{-j k \Delta t \omega}| - \end{equation*} - - Проинтегрировав последнюю часть данного равенства получим следующую функцию. - \begin{equation*} - u(t) = \sum_{-\infty}^\infty u(k \Delta t) \frac{\sin \omega_c (t - k\Delta t)}{\omega_c (t - k \Delta t)} - \end{equation*} - - Таким образом мы выразили функцию $u(t)$ через её дискретные значения взятые в моменты - $k \Delta t$. Предположим, что время $t$ будет выражаться как $n \Delta t, \quad n \in \N$. - Тогда $\omega_c(n\Delta t - k \Delta t) = \omega_c \Delta t (n - k)$. - - Так как $\Delta t = \frac{\pi}{\omega_c} \implies \omega_c \Delta t (n - k) = (n - k) \pi$ - - Таким образом, данная часть функции будет равна единице, если $t = k \Delta t$. - И 0, если $t = n \Delta t, \, n \neq k$. Это означает, что функция $u(t)$ - в момент времени $[t_k; k \Delta t]$ представляет собой ни что иное, как - отсчёты. То есть функция ограничена спектром и может быть представлена рядом, - коэффициенты которого представляют собой отсчёты значения функции взятые через - интервал времени $\Delta t$ -\end{proof} - -На основании этой теоремы строится общая схема приёма и передачи сигнала. на -передающей стороне мгновенные значения сигнала передаются через интервал времени -$\Delta t = \frac{\pi}{\omega_c}$, на принимающей стороне последовательность -импульсов пропускается через идеальный фильтр с частотой среза -$\frac{\omega_c}{2\pi}$. Тогда при длительной передаче на выходе фильтров будет -точное воспроизведение переданного непрерывного сигнала. - -В реальности сигнал всегда имеет конечную длину и, следовательно, его спектр не -ограничен. При этом ошибка возникает не только из-за искусственного ограничения -спектра, но и из-за конечного числа отсчётов, которые в соответствии с теоремой -будут вычисляться как $N = 2 f_c T$. При этом представление сигнала с -ограниченным спектром исключает возможность сигнала переносить информацию. - - -\section{Квантование сигнала} - -Физически реализуемые непрерывный сигнал всегда ограничен диапазон $[u_{min}; -u_{max}]$. В добавок устройство может воспроизводить лишь конечное число -значений сигнала из этого диапазона, в частности, вся непрерывная шкала -амплитудных значений может быть разита на $N$ одинаковых сигналов. А -разрешённые значения равноотстоять друг от друга. Тогда мы можем говорить о -равномерном квантовании. Если же постоянная интервала не соблюдается, то -квантование будет неравномерно, а соответственно постоянная будет - -Из множества мгновенных значений принадлежащих $i$-му шагу квантования только -одно значение $u(t)$ является разрешённым, а любые другие округляются до него. - -Пусть имеется равномерное с шагом $\Delta = \frac{|u_{max} - u_{min}|}{n}$ -И предположим, что при данном равномерном квантовании уровни квантования $u_i$ -размешаются ровно в середине каждого шага. Тогда ошибка квантования будет минимальная -и не будет превышать $0.5 \Delta$. При этом среднеквадратичная ошибка квантования -будет определяться следующим образом: -\begin{equation*} - \sigma_i = \sqrt{\int_{u_{i-1}}^{u_i} (u(t) - u_i)^2 p(u) du} -\end{equation*} - -где $p(u)$ --- функция плотности вероятности мгновенных значений сигнала $u$. - -Если шаг квантования сигнала мал по сравнению с диапазоном значения, то в -пределах каждого шага плотность вероятности можно считать постоянной и равной -величине $P(u_i)$. Тогда данную ошибку можно написать следующим образом: -\begin{equation*} - \sigma_i = \sqrt{P(u_i) \frac{\Delta_i^2}{12}} -\end{equation*} - -С учётом того, что плотность вероятности $p(u_i) > 0$ и $\Delta_i > 0$ -для всех $i = 1, n$ можно записать дисперсию ошибки квантования, которая будет равна -\begin{equation*} - \sigma_i^2 = p(u_i) \frac{\Delta_i^2}{12} -\end{equation*} - -Дисперсия полной ошибки квантования будет определяться как мат ожидание -дисперсии на каждом шаге квантования и будет равна $\sigma^2 = \frac{\Delta^2}{12}$ - -Если на квантуемый сигнал воздействует помеха, то он может попасть в интервал -соответствующий другому уровню квантования и соответственно предсказать сигнал -будет невозможно.
\ No newline at end of file diff --git a/sem5/information-theory/lectures/lecture7.tex b/sem5/information-theory/lectures/lecture7.tex deleted file mode 100644 index 21c1f00..0000000 --- a/sem5/information-theory/lectures/lecture7.tex +++ /dev/null @@ -1,255 +0,0 @@ -% Лекция (21.11.21) -\section{Каналы передачи информации} -Классической теорией информации является теория Шеннона. В основе её лежит -понятие, что человек принимает информацию к сведению постоянно устраняя -некоторую неопределённость. То есть чем больше случайных событий, снимающих -неопределённость системы, тем больше информации они несут. - -Дадим определение источника информации. Самым простым источником информации -является дискретный источник информации без памяти. Простейший дискретный -источник без памяти $X$ в каждый момент времени выдаёт некоторый символ $X_i$ из -конечного алфавита $X = \{x_1, x_2, \dots, x_n\}$ с вероятностью $P(x_i) = p_i$. -Как правило дискретные источники без памяти выбор символов производится -независимо друг от друга. Распределение информации при этом как правило -равномерное. В качестве примера можем привести источник без памяти двоичной -системы. $X = \{ x_1 = 0, x_2 = 1 \}$. Соответственно вероятность $0 \leq p_1 -\leq 1$, $p_2 = 1 - p_1$. При этом в данном источнике выбор очередной цифры -будет производиться независимо от прежних последовательностей и схематически -данный источник можно изобразить следующим образом: **рисунок**. - -Для определения количества информации такого источника используются следующие -три аксиомы. - -\begin{axiom} - Информация одиночного события $x_i \in X$ происходящего с вероятностью $p_i$ - имеет положительное значение. -\end{axiom} - -\begin{axiom} - Совместная информация двух независимых событий $x_i, x_j \in X$ с совместной - вероятностью $P_{ij}$ равно сумме их информаций. - \begin{equation*} - P(x_i, x_j) = P_{ij} = P_i \cdot P_j, \, I(P_{ij}) = I(P_i) + I(P_j) - \end{equation*} -\end{axiom} - -\begin{axiom} - Информация является непрерывной функцией от вероятности события. -\end{axiom} - -Следует отметить, что акс 1 и 2 утверждают то, что информация нескольких событий -не может взаимно уничтожаться. Акс 2 вводит понятие совместной информации -событий. Аксиома 3 говорит о том, что небольшое изменение вероятности событий -приводит к небольшому изменению её информации. Аксиома 2 определяет информацию -двух независимых событий. - -Согласно аксиоме 2 можно заключить, что информация события определяется -как логарифмическая функция её вероятности. Информация события происходящая -с вероятностью $P$ будет равна $I(P) = -\log(P)$. Причём основание логарифма -будет определять алфавит события и единицы измерения информации. - -Наряду с двоичным логарифмом наиболее часто используют натуральный логарифм, -при этом единицы измерения называются ``наты''. - -Исходя из аксиомы 3 можно заключить, что информация постоянно происходящего -события будет равна нулю. Соответственно информация для невозможного события -стремится к бесконечности. - -\subsection{Энтропия и избыточность} - -Рассмотрим источник события. Для его описания будем использовать информацию, -которую несут происходящие в нём события. По аналогии с термодинамикой -введём понятие \textbf{энтропии} как меры неопределённости. - -\textbf{Энтропия} --- это функция, которая возрастает, когда неопределённость -системы возрастает. Неупорядоченность системы. Таким образом, используя -информацию отдельных событий в источнике выразим энтропию следующим образом. - -Энтропия простейшего источник без памяти с алфавитом $X = \{ x_1, x_2, \dots, -x_n \}$ и соответствующими вероятностями $P = \{ p_1, \dots, p_n \}$ будет -обозначаться -\begin{equation*} - H = \sum_{i}^n -P_i \log(P_i) -\end{equation*} - -Предположим эргодичность источника (постоянство поведения). Будем рассматривать -эргодичность во времени. Если провести аналогию с теорией вероятности, то -процесс эргодичности предполагается когда мы бросаем кубик или монетку. -При этом с ростом числа испытаний среднее значение информации источника будет -вычисляться следующим образом: -\begin{equation*} - \overline{I} = \lim_{N \to \infty} \frac{1}{N} \sum_{n = 0}^{N - 1} I(n) -\end{equation*} - -Устремив данное выражение к математическому ожиданию мы получим, что данная -формула будет стремиться к формуле энтропии. Проводя аналогичные рассуждения -Шеннон положил в определение энтропии три следующих аксиомы: - -\begin{axiom} - Энтропия является непрерывной функцией вероятности. Для источников, в которых - события равновероятны и вероятность каждого события равна единица делить на - количество событий. -\end{axiom} - -\begin{axiom} - Энтропия будет возрастать с ростом числа событий. -\end{axiom} - -\begin{axiom} - Разложение процедуры выбора событий на несколько этапов не изменяет энтропию. -\end{axiom} - -Определим максимальную энтропию источника. Для этого воспользуемся теоремой -Шеннона. - -\begin{theorem} - Энтропия простейшего дискретного источника без памяти максимальна, если все - события в нём имеют одинаковую вероятность и в этом случае энтропия будет - равна логарифму от числа событий. $H_0 = \log N$ -\end{theorem} -\begin{proof} - Пусть имеется два дискретных источника $P = \{ p_i \}$ и $Q = \{ q_i \}$ - каждый из которых генерирует свои события. Всего есть $N$ событий . Для - доказательства теоремы нам понадобится верхняя оценка логарифмической функции: - $\ln x \leq x - 1$ Используя оценку получаем, что - \begin{equation*} - \ln q_i - \ln p_i = \ln \frac{q_i}{p_i} \leq \frac{q_i}{p_i} - 1 - \end{equation*} - - Умножив обе части данного равенства на вероятность $p_i$ и просуммировав по - всем событиям $N$ мы получим - \begin{equation*} - \sum_{i = 1}^N p_i (\ln q_i - \ln p_i) \leq \sum_{i = 1}^N p_i(\frac{q_i}{p_i} - 1) - \end{equation*} - - Получаем - \begin{equation*} - H(P) + \sum_{i = 1}^N p_i \ln q_i \leq \sum_{i = 1}^N q_i - \sum_{i = 1}^N p_i = 0 - \end{equation*} - - Таким образом, можем заключить, что энтропия равна - \begin{equation*} - H(P) \leq -\sum_{i = 1}^N p_i \ln q_i = - \end{equation*} - - Если предположить, что источник $Q$ содержит только равновероятные события, - то эта сумма будет равна - \begin{equation*} - = -\sum_{i = 1}^N p_i \ln \frac{1}{N} = \ln N \sum_{i = 1}^N p_i = \ln N - \end{equation*} - - Таким образом при доказательстве на источник $P$ не накладывались никакие - ограничения, то данное неравенство имеет место для любого дискретного - источника без памяти, который содержит $N$ событий. - - Получаем \begin{equation*} - H(x) \leq \log N - \end{equation*} -\end{proof} - -Соответственно максимум достигается тогда, когда имеются одинаковые события. - -\begin{corollary} - Любой источник, содержащий $N$ событий не все из которых имеют одинаковую - вероятность обладает энтропией меньшей, чем $\log N$ -\end{corollary} - -\begin{definition} - Рассмотрим источник событий, который имеет ёмкость $H_0 = \log N$. ДАнный - источник будет являться резервуаром, который никогда не переполняется - и зависит только от количества событий. - - Пусть есть источник $X$ в котором не все события равновероятны, который также - состоит из $N$ событий. - - Разность $R = H_0 - H(X)$ называется \textbf{избыточностью источника}. -\end{definition} - -\begin{equation*} - r = \frac{R}{H_0} = 1 - \frac{H(X)}{H_0} -\end{equation*} - -\begin{definition} - Введём понятие функции Шеннона. Пусть задан двоичный алфавит и есть - источник событий. $P_0 = P$, $P_1 = 1 - P_0$. Выбор символа производится - независимо, соответственно энтропия данного источника будет называться - функцией Шеннона и будет зависеть только от вероятности $P$. - - \begin{equation*} - H(P) = -P \log P - (1 - P) \log(1 - P) - \end{equation*} - - Функция Шеннона всегда положительна и симметрична относительно значения $0.5$. - **рисунок** -\end{definition} - -\subsection{Энтропия связанных источников. Понятие взаимной и условной информации.} - -При аксиономическом ... . Рассмотрим это понятие более подробно. Пусть у нас -есть два источника: $X$ и $Y$. Пусть эти источники связаны между собой. -Результатом работы данных источников будет пара $(x_i, y_i)$. -Если два источника связаны между собой, то события одного источника будут -влиять на события другого источника. То есть по событиям источника $X$ мы -можем предсказать события источника $Y$, то есть в терминах теории информации, -можно определить, что из-за влияния источника $X$ снижается неопределённость -источника $Y$. $P(x_i, y_i) \neq P(x_i) + P(y_i)$ - -То есть данные источники обмениваются какой-то дополнительной информации. Для -определения данной информации введём понятие условной вероятности. Введём -совместную вероятность через их априорные условные вероятности. - -\begin{equation*} - P(x_i, y_i) = P(x_i / y_i) P(y_i) = P(y_i / x_i) P(x_i) -\end{equation*} - -\begin{equation*} - \log P(x_i, y_i) = \log P(x_i / y_i) + \log P(y_i) = \log P(x_i / y_i) + -I(y_i) -\end{equation*} - -То есть -\begin{equation*} - I(x_i, y_i) = I(y_i) - \log P(x_i / y_i) = I(x_i) - \log P(y_i / x_i) -\end{equation*} - -Прибавляя и одновременно вычитая в первой части $I(x_i)$, а во второй части -$I(y_i)$ мы получим следующую формулу: -\begin{equation*} - I(x_i, y_i) = I(x_i) + I(y_i) - \log \frac{P(x_i / y_i)}{P(x_i)} = - I(x_i) + I(y_i) - \log \frac{P(y_i/x_y)}{P(y_i)} -\end{equation*} - -Таким образом если источники связаны, то информация пары $(x_i, y_i)$ -определяется суммой информаций этих событий за вычетом некоторой неотрицательной -величины, которая также снимает неопределённость и, следовательно, тоже является -информацией. Такую информацию называют взаимной информацией пары событий. -Обозначается -\begin{equation*} - I(x_i, y_i) = \log \frac{P(x_i/y_i)}{P(y_i)} = \log \frac{P(y_i/x_i)}{P(x_i)} -\end{equation*} - -Следует отметить, что $I(x_i, y_i)$ всегда положительная и является симметричной -относительно источников. Симметричность относительно источников показывает, -что источники обмениваются взаимной информацией друг с другом, а не в -одностороннем порядке. Возможны два граничных случая: -\begin{enumerate} - \item - Источники независимы. Тогда совместная информация равна нулю (источники не - обмениваются информацией). - \item - Источники жёстко связаны между собой. То есть события одного источника - однозначно определяют события другого источника. То есть условная - вероятность будет равна единице. В этом случае взаимная информация будет - равна информации первого источника и также равна информации второго - источника. -\end{enumerate} - -Введём понятие условной информации. Условная информация будет называться -информация $I(x_i / y_i) = -\log P(x_i / y_i)$. Тогда взаимная информация -через условную будет выражаться следующим образом: -\begin{equation*} - I(x_i, y_i) = I(x_i) + I(y_i / x_i) = I(y_i) + I(x_i / y_i) -\end{equation*} - -То есть информацию пары событий можно определить как сумму информаций событий -источника $Y$ и информации источника событий $X$ при условии, что события -$Y$ уже известно, или наоборот.
\ No newline at end of file diff --git a/sem5/languages/languages.tex b/sem5/languages/languages.tex deleted file mode 100644 index 6e10590..0000000 --- a/sem5/languages/languages.tex +++ /dev/null @@ -1,12 +0,0 @@ -\documentclass{../Lecture} -\usepackage{../preamble} - -\begin{document} - -\author{Андрей гущин} -\title{Универсальная прикладная алгебра} -\maketitle - -\include{lectures/lecture5.tex} - -\end{document} diff --git a/sem5/languages/lectures/lecture1.tex b/sem5/languages/lectures/lecture1.tex deleted file mode 100644 index 0c48aa2..0000000 --- a/sem5/languages/lectures/lecture1.tex +++ /dev/null @@ -1,20 +0,0 @@ -% Лекция (13.09.21) -\section{Предмет, методы и задачи переводоведения} - -Перевод как вид деятельности возник в те времена, когда праязык начал -распадаться на отдельные языки. 20 век считается золотым веком устного перевода. -1953 --- в Париже Пьер-Франсуа Кайе основал [международную федерацию -переводчиков](https://ru.wikipedia.org/wiki/Международная_федерация_переводчиков). -Эта организация занимается --- профессиональная, неполитическая не преследующая -коммерческих целей организация, задачи которой объединение переводческих -организаций разных стран. Со второй половины двадцатого века благодаря -изменениям в экономической, политической, социальной и культурной сферах -возникла потребность в переводах и переводчиках. В разных странах независимо -друг от друга стали появляться бюро переводов и издательства переводной -литературы. По данным ЮНЕСКО ежегодно в мире издаётся около 40000 переводных -изданий (то есть более 100 книг в день). Только во второй половине 20 века -процесс перевода стал объектом всестороннего научного изучения. В центре -внимания лингвистов оказалась смысловая сторона языковых единиц и речевых -произведений, связь языка с мышлением, с реальной действительностью, с обществом -и культурой. Появились новые лингвистические дисциплины, такие как -психолингвистика, социолингвистика, лингвистика текстов, теория речевых актов.
\ No newline at end of file diff --git a/sem5/languages/lectures/lecture2.tex b/sem5/languages/lectures/lecture2.tex deleted file mode 100644 index b669a62..0000000 --- a/sem5/languages/lectures/lecture2.tex +++ /dev/null @@ -1,19 +0,0 @@ - -% Лекция (20.09.21) -\section{Роль перевода для человечества. Культурные и языковые барьеры.} - -\textbf{Перевод} --- деятельность, которая заключается в вариативном -перевыражении, перекодировании текста порождённого на одном языке в текст на -другом языке. Переводчик творчески выбирает вариант в зависимости от вариативных -ресурсов языка, в зависимости от вида перевода, задач перевода, типа текста, и -под действием собственной индивидуальности. \textbf{Перевод} --- это также -результат вышеописанной деятельности. - -Перевод обеспечивает сиюминутные и долговременные контакты между людьми. Всюду, -где существует языковой барьер преодолеть его помогает перевод. Перевод -способствует обмену информацией самого разного характера и этот обмен является -базой прогресса человечества. Современный человек пользуется плодами трудов -переводчиков постоянно. Тенденция к глобализации, которая началась на рубеже -20-21 вв. и до сих пор продолжается, подготовлена деятельностью переводчиков, а -сама глобализация возможна только при условии хорошо организованного -переводческого процесса. Труд переводчиков способствует открытости общества.
\ No newline at end of file diff --git a/sem5/languages/lectures/lecture5.tex b/sem5/languages/lectures/lecture5.tex deleted file mode 100644 index 34bd3cb..0000000 --- a/sem5/languages/lectures/lecture5.tex +++ /dev/null @@ -1,144 +0,0 @@ -% Лекция (11.10.21) -\section{Переводческие компетенции} -Основная идея подхода по компетенциям заключается в том, что главный результат -образования это не отдельные знания, умения и навыки, а способность и готовность -человека к эффективной и продуктивной деятельности в различных социально -значимых ситуациях. Этот подход предполагает формирования потребностей человека -в постоянном пополнении и обновлении знаний, совершенствовании умений и навыков, -их закреплении и превращении в компетенции. Компетенции формируются в процессе -деятельности ради будущей профессиональной деятельности. Система формирования -профессиональной компетентности переводчика нацелена на развитие у обучающихся -совокупности профессионально значимых компетенций, определяемых потребностью -профессии и возможностью дальнейшего профессионального саморазвития. - -\textbf{Переводческая компетенция} --- это сложное, многомерное -лингвокогнитивная категория, включающая профессиональные навыки и умения, -которые позволяют переводчику осуществлять акт межязыковой и межкультурной -коммуникации. - -Характеристики переводчика: -\begin{itemize} - \item языковая; - \item текстообразующая; - \item коммуникативная; - \item техническая; - \item личностная. -\end{itemize} - -\subsection{Языковая компетенция} -\textbf{Языковая компетенция} переводчика включает в себя все аспекты владения -языком, характерные для носителя языка, но кроме того подразумевает собой ряд -специфических особенностей. Переводчик должен помнить о системе, норме и -\href{https://ru.wikipedia.org/wiki/Узус}{узусе языка}, о его словарном составе -и грамматическом строе, о правилах использования единиц языка для построения -речевых высказывания. Переводчик должен обладать этой компетенцией как в -рецептивном, так и в продуктивном планах в обоих языках, участвующих в процессе -перевода. - -\subsection{Коммуникативная компетенция} -Способность человека к (1) интерференции, то есть способности формировании -правильных выводов из речевых высказываний, на основе фоновых знаний также -составляет коммуникативную компетенцию. Также коммуникативная компетенция -предполагает умение не только (2) интерпретировать смысл высказываний, но и -(3) умение проецировать на высказывания в тексте оригинала интерференционные -возможности рецепторов перевода. - -\subsection{Текстообразующая компетенция} -\begin{itemize} - \item - умение создавать тексты различного типа в соответствии с коммуникативной - задачей и ситуацией общения; - \item умение обеспечивать надлежащую структуру текста; - \item - умение использовать языковые единицы текста по правилам построения языковых - единиц в языке; - \item умение оценивать место и соотношение отдельных частей текста; - \item умение воспринимать текст как связное речевое целое. -\end{itemize} - -\subsection{Личностные характеристики} -\begin{itemize} - \item особая психическая организация; - \item гибкость; - \item способность быстро переключать внимание; - \item способность переходить от одного языка к другому; - \item способность переходить от одной культуры к другой. -\end{itemize} - -\subsection{Техническая компетенция} -\begin{itemize} - \item - знания о \begin{itemize} - \item стратегиях перевода; - \item переводческих приёмах; - \item переводческих трансформациях. - \end{itemize} - \item умения; - \item навыки. -\end{itemize} - -Некоторые исследователи также выделяют некоторые дополнительные компетенции. - -\subsection{Лингвистическая компетенция} -\begin{itemize} - \item особое владение двумя языками; - \item - совокупность знаний, умений и навыков в области вербальных и невербальных - средств. -\end{itemize} - -В целом, лингвистическая компетенция отражает способность человека использовать -иностранный и родной языки как средство профессиональной коммуникации. - -\subsection{Операциональная компетенция} -Подразумевает владение технологией перевода, важный компонент переводческой -компетенции. -\begin{itemize} - \item наличие теоретических знаний в области переводоведения; - \item владение трансформациями и приёмами перевода; - \item - умение выбирать и и правильно использовать преодоление переводческих - трудностей, связанных с лексическими, грамматическими и стилистическими - расхождениями текстов. -\end{itemize} - -\subsection{Социокультурная компетенция} -\begin{itemize} - \item - умение интерпретировать смысл высказываний с учётом культурных особенностей - коммуникантов; - \item - умение анализировать коммуникативные ситуации заказчика и получателя в - рамках соответствующих культур; - \item страноведческий и культурологический компоненты. -\end{itemize} - -\subsection{Особенности, характеризующие профессионального переводчика} -\begin{itemize} - \item выносливость; - \item целеустремлённость; - \item собранность; - \item любознательность; - \item самообучаемость; - \item самокритичность; - \item бережное отношение к родному языку; - \item - внимательное наблюдение за грамматикой, лексикой, стилистикой и - идиоматикой иностранного языка; - \item знание теоретических основ научно-технического перевода; - \item практическое использование методов перевода; - \item - повседневное составление собственных узко специализированных двуязычных - словарей с толкованием новых терминов и понятий; - \item владение всеми традиционными и современными инструментами переводчика; - \item - слежение за новинками на рынке информационных технологий, обновление - основных компьютерных программ, приобретение и освоение новых программ; - \item - непристанное оттачивание своего мастерства, развитие привычки к - качественному переводу; - \item - организация собственного труда, оптимальное взаимодействие с заказчиком, - посредником, коллегами, эффективная система снятия вопросов; - \item творческое отношение к переводимому тексту. -\end{itemize}
\ No newline at end of file diff --git a/sem5/preamble.sty b/sem5/preamble.sty deleted file mode 100644 index e3939ec..0000000 --- a/sem5/preamble.sty +++ /dev/null @@ -1,74 +0,0 @@ -\ProvidesPackage{../preamble} - -\RequirePackage{mathtools} -\RequirePackage{amsfonts} -\RequirePackage{enumitem} -% \RequirePackage[standard]{ntheorem} -\RequirePackage{amsthm} -\RequirePackage{tikz} -\RequirePackage{graphicx} -\graphicspath{ {./images/} } - -\newcommand{\bydef}{\stackrel{\text{по опр.}}{\implies}} % by definition - по определению -\newcommand{\dn}{\stackrel{\text{об.}}{=}} % denote - обозначим -\newcommand{\imaginary}{\mathrm{Im} \,} -\newcommand{\real}{\mathrm{Re} \,} -\newcommand{\prop}[1]{#1^{\text{o}}} - -\newcommand{\N}{\mathbb{N}} -\newcommand{\R}{\mathbb{R}} -\newcommand{\Z}{\mathbb{Z}} -\renewcommand{\C}{\mathbb{C}} -\newcommand{\bb}[1]{\mathbb{#1}} - -\newcommand{\approach}[1]{\underset{#1}{\longrightarrow}} -\newcommand{\series}[1]{\displaystyle\sum_{k=1}^\infty #1} -\newcommand{\seriesx}{\displaystyle\sum_{k=1}^\infty x_k} -\newcommand{\seriespow}{\displaystyle\sum_{k=0}^\infty a_k (x - x_0)^k} -\newcommand{\abs}[1]{\left|#1\right|} -\renewcommand{\over}[2]{\stackrel{#1}{#2}} - -% \theoremstyle{break} - -% --- Теорема --- % -% \newtheoremstyle{break}% name -% {}% Space above, empty = `usual value' -% {}% Space below -% {\itshape}% Body font -% {}% Indent amount (empty = no indent, \parindent = para indent) -% {\bfseries}% Thm head font -% {.}% Punctuation after thm head -% {\newline}% Space after thm head: \newline = linebreak -% {}% Thm head spec -% \theorembodyfont{\normalfont} -% \theoremstyle{break} -\newtheorem{theorem}{Теорема}[subsection] -% --------------- % - -% --- Определение --- % -% \theorembodyfont{\normalfont} -\theoremstyle{definition} -\newtheorem{definition}{Определение}[subsection] -% ------------------- % - - -% --- Пример --- % -\theoremstyle{definition} -\newtheorem*{example}{Пример} -% -------------- % - -% --- Следствие --- % -\theoremstyle{definition} -\newtheorem*{corollary}{Следствие} -% ----------------- % - -% --- Замечание --- % -\theoremstyle{definition} -\newtheorem*{remark}{Замечание} -% ----------------- % - - -% --- Лемма --- % -\theoremstyle{definition} -\newtheorem*{lemma}{Лемма} -% ----------------- %
\ No newline at end of file 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 diff --git a/sem5/universal-algebra/universal-algebra.tex b/sem5/universal-algebra/universal-algebra.tex deleted file mode 100644 index 12f87bc..0000000 --- a/sem5/universal-algebra/universal-algebra.tex +++ /dev/null @@ -1,14 +0,0 @@ -\documentclass{../Lecture} -\usepackage{../preamble} - -\begin{document} - -\author{Андрей гущин} -\title{Универсальная прикладная алгебра} -\maketitle - -\include{lectures/lecture1.tex} -\include{lectures/lecture3.tex} -\include{lectures/lecture4.tex} - -\end{document} |