Добавил реферат по теории перевода, первую презентацию по теории автоматов

1 files changed, 254 insertions, 0 deletions

diff --git a/Теория автоматов/2_6-2_7/templ.tex b/Теория автоматов/2_6-2_7/templ.tex
new file mode 100644
index 0000000..c25e980
--- /dev/null
+++ b/Теория автоматов/2_6-2_7/templ.tex
@@ -0,0 +1,254 @@
+\documentclass{beamer}
+
+\usepackage[T2A]{fontenc}
+\usepackage[utf8]{inputenc}
+\usepackage[english,russian]{babel}
+\usepackage{wrapfig}
+\usepackage{graphicx}
+\usepackage{multirow}
+\graphicspath{ {./images/} }
+
+\usetheme{Madrid}
+
+\title{Алгоритмы сжатия изображений}
+\author[А.~Ю.~Гущин \and Р.~И.~Стаин]{Андрей~Гущин \and Роман~Стаин}
+\institute[СГУ]{Саратовский Государственный Университет}
+\date{11 ноября 2022 г.}
+
+\begin{document}
+
+\maketitle
+
+\begin{frame}{Представление цифровых изображений}
+  \begin{figure}[H]
+    \includegraphics[width=0.9\textwidth]{compare}
+  \end{figure}
+\end{frame}
+
+\begin{frame}{Алгоритмы сжатия без потерь}
+  Основными и самыми популярными алгоритмами сжатия без потерь являются:
+  \begin{itemize}
+    \item
+      \textbf{RLE} --- используется в форматах PCX --- в качестве основного метода
+      и в форматах BMP, TGA, TIFF в качестве одного из доступных.
+    \item \textbf{LZW} --- используется в формате GIF
+    \item \textbf{Deflate} --- используется в формате PNG
+  \end{itemize}
+\end{frame}
+
+\begin{frame}{Run-Length Encoding (RLE)}
+  \begin{itemize}
+    \item \texttt{WWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW}
+    \pause
+    \item \texttt{9W3B24W1B14W}
+  \end{itemize}
+\end{frame}
+\begin{frame}{Run-Length Encoding (RLE)}
+  \begin{itemize}
+    \item \texttt{ABCABCABCDDDFFFFFF}
+    \pause
+    \item \texttt{1A1B1C1A1B1C1A1B1C3D6F}
+    \pause
+    \item \texttt{-9ABCABCABC3D6F}
+  \end{itemize}
+\end{frame}
+\begin{frame}{Run-Length Encoding (RLE)}
+  \begin{itemize}
+    \item
+      \texttt{AAAAA{\dots}AAAAA}
+    \pause
+    \item \texttt{127A127A2A}
+  \end{itemize}
+\end{frame}
+
+\begin{frame}{Lempel-Ziv-Welch (LZW) --- Кодирование}
+  \begin{table}[H]
+    \centering
+    \scriptsize
+    \begin{tabular}{|c|c|c|r|l|}
+      \hline
+      % Первая строка заголовка
+      \multirow{2}{*}{Символ} &
+      \multirow{2}{*}{Следующий} &
+      \multicolumn{2}{|c|}{Вывод} &
+      \multirow{2}{*}{Расширение словаря} \\ \cline{3-4}
+      % Вторая строка заголовка
+      && Код & \multicolumn{1}{|c|}{Биты} & \\ \hline
+      % Символ & Следующий & Код & Биты             & Расширение словаря \\
+      NULL     & T         &     &                  &                    \\ \hline
+      T        & O         & 20  & \texttt{10100}   & 27: TO             \\ \hline
+      O        & B         & 15  & \texttt{101111}  & 28: OB             \\ \hline
+      B        & E         & 2   & \texttt{100010}  & 29: BE             \\ \hline
+      E        & O         & 5   & \texttt{100101}  & 30: EO             \\ \hline
+      O        & R         & 15  & \texttt{101111}  & 31: OR             \\ \hline
+      R        & N         & 18  & \texttt{110010}  & 32: RN             \\ \hline
+      N        & O         & 14  & \texttt{1001110} & 33: NO             \\ \hline
+      O        & T         & 15  & \texttt{1001111} & 34: OT             \\ \hline
+      T        & T         & 20  & \texttt{1010100} & 35: TT             \\ \hline
+      TO       & B         & 27  & \texttt{1011011} & 36: TOB            \\ \hline
+      BE       & O         & 29  & \texttt{1011101} & 37: BEO            \\ \hline
+      OR       & T         & 31  & \texttt{1011111} & 38: ORT            \\ \hline
+      TOB      & E         & 36  & \texttt{1100100} & 39: TOBE           \\ \hline
+      EO       & R         & 30  & \texttt{1011110} & 40: EOR            \\ \hline
+      RN       & O         & 32  & \texttt{1100000} & 41: RNO            \\ \hline
+      OT       & \#        & 34  & \texttt{1100010} &                    \\ \hline
+               &           & 0   & \texttt{000000}  &                    \\ \hline
+    \end{tabular}
+  \end{table}
+\end{frame}
+\begin{frame}{Lempel-Ziv-Welch (LZW) --- Декодирование}
+  \begin{table}[H]
+    \centering
+    \scriptsize
+    \begin{tabular}{|r|c|c|l|l|}
+      \hline
+      % Первая строка заголовка
+      \multicolumn{2}{|c|}{Ввод} &
+      \multirow{2}{*}{Вывод} &
+      \multicolumn{2}{|c|}{Новая запись} \\ \cline{1-2} \cline{4-5}
+      % Вторая строка заголовка
+      \multicolumn{1}{|c|}{Биты} &
+      Код & &
+      \multicolumn{1}{|c|}{Полная} &
+      \multicolumn{1}{|c|}{Частичная} \\ \hline
+      % Биты          & Код & Вывод & Полная   & Частичная \\
+      \texttt{10100}  & 20  & T     &          & 27: T?    \\ \hline
+      \texttt{01111}  & 15  & O     & 27: TO   & 28: O?    \\ \hline
+      \texttt{00010}  & 2   & B     & 28: OB   & 29: B?    \\ \hline
+      \texttt{00101}  & 5   & E     & 29: BE   & 30: E?    \\ \hline
+      \texttt{01111}  & 15  & O     & 30: EO   & 31: O?    \\ \hline
+      \texttt{10010}  & 18  & R     & 31: OR   & 32: R?    \\ \hline
+      \texttt{001110} & 14  & N     & 32: RN   & 33: N?    \\ \hline
+      \texttt{001111} & 15  & O     & 33: NO   & 34: O?    \\ \hline
+      \texttt{010100} & 20  & T     & 34: OT   & 35: T?    \\ \hline
+      \texttt{011011} & 27  & TO    & 35: TT   & 36: TO?   \\ \hline
+      \texttt{011101} & 29  & BE    & 36: TOB  & 37: BE?   \\ \hline
+      \texttt{011111} & 31  & OR    & 37: BEO  & 38: OR?   \\ \hline
+      \texttt{100100} & 36  & TOB   & 38: ORT  & 39: TOB?  \\ \hline
+      \texttt{011110} & 30  & EO    & 39: TOBE & 40: EO?   \\ \hline
+      \texttt{100000} & 32  & RN    & 40: EOR  & 41: RN?   \\ \hline
+      \texttt{100010} & 34  & OT    & 41: RNO  & 42: OT?   \\ \hline
+      \texttt{000000} & 0   & \#    &          &           \\ \hline
+    \end{tabular}
+  \end{table}
+\end{frame}
+
+\begin{frame}{Алгоритмы сжатия с потерями}
+  Наиболее часто применяемые алгоритмы сжатия с потерями:
+  \begin{itemize}
+    \item
+      Дискретное косинусное преобразование "--- кодирование, основанное на
+      преобразованиях Фурье.
+    \item Вейвлет сжатие "--- сжатие за счёт отбрасывания низких амплитуд.
+    \item Квантование цветов "--- процесс уменьшения количества различных цветов.
+    \item
+      Прореживание (субдискретизация) компонентов цветности "--- усреднение или
+      уменьшение части информации о цветности изображения.
+    \item
+      Фрактальное сжатие "--- алгоритм сжатия изображений с потерями, основанный
+      на применении систем итерируемых функций к изображениям
+  \end{itemize}
+\end{frame}
+
+\begin{frame}{Преобразование цветового пространства}
+  \begin{figure}[H]
+    \includegraphics[width=0.9\textwidth]{YCbCr}
+  \end{figure}
+  \begin{align*}
+    Y'  &= K_R \cdot R' + (1 - K_R - K_B) \cdot G' + K_B \cdot B' \\
+    C_B &= \frac{1}{2} \cdot \frac{B' - Y'}{1 - K_B} \\
+    C_R &= \frac{1}{2} \cdot \frac{R' - Y'}{1 - K_R} \\
+  \end{align*}
+\end{frame}
+
+\begin{frame}{Прореживание (субдискретизация) компонентов цветности}
+  Есть несколько схем прореживания, которые применяются в зависимости от
+  требований к качеству изображения после его восстановления. Структура
+  дискретизации сигнала обозначается как соотношение между тремя частями X:a:b
+  (например, 4:2:2).
+
+  \begin{figure}[H]
+    \includegraphics[width=0.9\textwidth]{subd}
+  \end{figure}
+\end{frame}
+
+\begin{frame}{Дискретное косинусное преобразование}
+  \begin{minipage}[t]{0.48\linewidth}
+    \begin{figure}[H]
+      \includegraphics[width=\textwidth]{dct64}
+    \end{figure}
+  \end{minipage}
+  \hfill
+  \begin{minipage}[t]{0.48\linewidth}
+    \begin{align*}
+      RES &= DCT \cdot IMG \cdot DCT^T \\
+      DCT &=
+        \sqrt{\frac{2}{N}} \cdot
+        \cos{\frac{(2j + 1) \cdot i \cdot \pi}{2 \cdot N}} \\
+      N &= 8, 0 \leq i, j \leq 7
+    \end{align*}
+  \end{minipage}
+\end{frame}
+
+\begin{frame}{Дискретное косинусное преобразование}
+  До преобразования ДКП:
+  \begin{equation*}
+    \begin{pmatrix}
+      100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\
+      100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\
+      100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\
+      100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\
+      100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\
+      100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\
+      100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\
+      100 & 100 & 100 & 100 & 100 & 100 & 100 & 100
+    \end{pmatrix}
+  \end{equation*}
+\end{frame}
+
+\begin{frame}{Дискретное косинусное преобразование}
+  После преобразования ДКП:
+  \begin{equation*}
+    \begin{pmatrix}
+      800 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
+        0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
+        0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
+        0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
+        0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
+        0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
+        0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
+        0 & 0 & 0 & 0 & 0 & 0 & 0 & 0
+    \end{pmatrix}
+  \end{equation*}
+\end{frame}
+
+\begin{frame}{Квантование и кодирование}
+  \begin{minipage}[t]{0.48\linewidth}
+    \begin{figure}[H]
+      \includegraphics[width=\textwidth]{q1}
+    \end{figure}
+  \end{minipage}
+  \hfill
+  \begin{minipage}[t]{0.48\linewidth}
+    \begin{figure}[H]
+      \includegraphics[width=\textwidth]{q2}
+    \end{figure}
+  \end{minipage}
+\end{frame}
+
+\begin{frame}{Фрактальное сжатие изображений}
+  \begin{figure}[H]
+    \includegraphics[width=\textwidth]{fractal}
+  \end{figure}
+\end{frame}
+
+\begin{frame}
+  \frametitle{Внимание!}
+
+  \begin{center}
+    {\Huge Спасибо за внимание!} \\
+    {\footnotesize Сжимайте осторожнее.}
+  \end{center}
+\end{frame}
+
+\end{document}