1.4-array.tex

\documentclass[alsotrans,beameroptions={aspectratio=169}]{beamerswitch}
\usepackage{sdp}

\title{Редици}

\date{3 октомври 2024 г.}

\titlegraphicx{\basedOnImageWithAttr{10em}{images/array.jpg}{IMGP0612 - dozen eggs}{RaeAllen}{https://flic.kr/p/9vfsS}{\CCBYNCSA{2.0}}}

\newbooltrue{algos}

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\section{Масиви}

\begin{frame}
  \frametitle{АТД: Масив}

  Последователност от елементи от еднакъв вид, които могат да бъдат избирани по номер (индекс).\\[1em]\
  \pause
  \textbf{Операции}\\[0.5em]
  \begin{itemize}
  \item \lst{create(n)} --- създаване на масив със зададена големина
  \item \lst{get(i)} --- получаване на елемент с индекс \tt i
  \item \lst{set(i,x)} --- задаване на стойност \tt x на елемента с индекс \tt i
  \item \lst{size} --- дължина на масива
  \end{itemize}
  \vspace{1em}
  \pause
  \textbf{Свойства на операциите}\\[0.5em]
  \begin{itemize}
  \item \lst{a.set(i,x).get(i)} = \tt x
  \item \lst{a.set(i,x).get(j)} = \lst{a.get(j)}, ако \tt{i $\neq$ j}
  \item \lst{create(n).size} = \tt n
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Статично представяне}

  % TODO: да се нарисува с TikZ
  \begin{tabular}{|*8{c|}}
    \rowcolor{diagramblue}
    \hline
    $a_0$&$a_1$&$a_2$&\ldots&\ldots&\ldots&\ldots&$a_{n-1}$\\
    \hline
    \multicolumn{8}{c}{$\underbrace{\hspace{40ex}}_{\text{дължина}}$}\\
  \end{tabular}\\[3em]
  \textbf{Реализация:} масив във C++.\\[1em]
  \textbf{Пример:} \lst{int a[10];}
  % TODO: пример за операциите
\end{frame}

\begin{frame}
  \frametitle{Динамично представяне}
  \newcommand{\pha}{\hspace{2ex}}

  % TODO: да се нарисува с TikZ
  \begin{tabular}{|*{16}{c|}}
    \multicolumn{16}c{$\overbrace{\hspace{60ex}}^{\text{капацитет}}$}\\
    \rowcolor{diagramblue}
    \hline
    $a_0$&$a_1$&$a_2$&\ldots&\ldots&\ldots&\ldots&$a_{n-1}$&\pha&\pha&\pha&\pha&\pha&\pha&\pha&\pha\\
    \hline
    \multicolumn 8c{$\underbrace{\hspace{40ex}}_{\text{дължина}}$}&\multicolumn 8c{}
  \end{tabular}\\[3em]
  \textbf{Реализация:} \lst{std::vector}.
\end{frame}

\begin{frame}
  \frametitle{\lst{std::vector<T>}}

  Реализация на динамичен масив
  \begin{itemize}
  \item \lst{vector(n)} --- създава вектор с дължина \tt n
  \item \lst{size} --- дължина на вектора
  \item \lst{capacity} --- капацитет на вектора
  \item \lst{[i]}, \lst{at(i)} --- достъп до елемент на индекс \tt i
    % TODO: разлика между [] и at
  \item \lst{front()}, \lst{back()} --- достъп до първи и последен елемент
  \item \lst!push_back(x)! --- добавяне на елемента \tt x в края
  \item \lst!pop_back()! --- изтриване на последния елемент
  \item \lst{insert(...)} --- вмъкване на елементи на произволна позиция
  \item \lst{erase(...)} --- изтриване на елементи на произволна позиция
  \item \lst{==,!=,<,>,<=,>=} --- лексикорафско сравнение на два вектора
  \end{itemize}
  \pause
  Специализация \lst{vector<bool>}: реализирана чрез битови масиви
\end{frame}

\begin{frame}
  \frametitle{\lst{std::string}}

  Реализация на низ (динамична редица от символи)
  \begin{itemize}
  \item Всички методи на \lst{std::vector<char>}
    \begin{itemize}
    \item \alert{но не го наследява!}
    \end{itemize}
  \item Методите са съвместими с \lst{char*}
  \item \lst{replace(...)} --- подмяна на символи на произволна позиции
  \item \lst{+,+=,append(...)} --- конкатенация на низове
  \item \lst!<<, >>! --- операции за вход и изход
  \item \lst!c_str()! --- конвертиране към стандартен C++ низ
  \item \lst{find(...), rfind(...)} --- търсене на първо/последно срещане
  \item \lst!find_first_of(...)! --- първо срещане на символ от друг низ
  \item \lst{substr(...)} --- извличане на подниз
  \item \lst{compare(...)} --- сравнение с друг низ
  \item \lst{copy(...)} --- копиране на символи от C++ низ
  \end{itemize}
\end{frame}

\section{Кортежи}

\begin{frame}
  \frametitle{АТД: Наредена двойка}

  Двойка от елементи от потенциално различен тип, в която редът има значение.\\[0.5em]
  \textbf{Операции}\\[0.5em]
  \begin{itemize}
  \item \lst{create(a,b)} --- създава двойка от елементите \tt a и \tt b
  \item \lst{first} --- първият елемент на двойката
  \item \lst{second} --- вторият елемент на двойката
  \end{itemize}
  \vspace{0.5em}
  \textbf{Свойства на операциите}\\[0.5em]
  \begin{itemize}
  \item \lst{create(a,b).first} = \tt a
  \item \lst{create(a,b).second} = \tt b
  \item \lst{create(p.first,p.second)} = \tt p
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Физическо представяне}

  % TODO: да се нарисува с TikZ
  \begin{center}
    \begin{tabular}{|m{5ex}|m{8ex}|}
      \hline
      \rowcolor{diagramblue}
      a&b\\
      \hline
    \end{tabular}
  \end{center}
  \vspace{2em}

  Възможни реализации:
  \begin{itemize}[<+->]
  \item \lst!struct Pair { int first; char second; };!
  \item \lst!std::pair<T,U>!
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{\lst{std::pair}}

  Реализация на наредена двойка
  \begin{itemize}
  \item \lst{pair(x,y)} --- създаване на двойка (\tt x,\tt y)
  \item \lst{first} --- първи елемент
  \item \lst{second} --- втори елемент
  \item \lst{==,!=,<,>,<=,>=} --- лексикорафско сравнение на две двойки
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{АТД: Кортеж}

  Редица от фиксиран брой елементи от потенциално различен тип, в която редът има значение.\\[0.5em]

  \textbf{Операции}\\[0.5em]
  \begin{itemize}
  \item \lst{create(...)} --- създаване на кортеж по единични елементи
  \item \lst{get(i)} --- получаване на елемент с индекс/име \tt i
  \item \lst{set(i,x)} --- задаване на стойност \tt x на елемента с индекс/име \tt i
  \end{itemize}

  \textbf{Свойства на операциите}\\[0.5em]
  \begin{itemize}
  \item \tt{create(a$_1$,\ldots,a$_i$,\ldots,a$_n$).get(i)} = \tt{a$_i$}
  \item \lst{t.set(i,x).get(i)} = \tt x
  \item \lst{t.set(i,x).get(j)} = \lst{a.get(j)}, ако \tt{i $\neq$ j}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{\lst{std::tuple} (C++11)}

  Реализация на кортеж
  \begin{itemize}
  \item \lst{tuple(...)} --- създаване на кортеж с подадените елементи
  \item \lst!tuple_cat(...)! --- слепва произволен брой кортежи
  \item \lst{get(i)} --- $i$-ти елемент на кортежа
  \item \lst {==,!=,<,>,<=,>=} --- лексикорафско сравнение на два кортежа
  \end{itemize}
\end{frame}

\ifbool{algos}{
\section{Алгоритми за сортиране}
\begin{frame}
  \frametitle{Двоично търсене}
  Алгоритъм за двоично търсене в сортиран масив:
  \begin{enumerate}
  \item търсим елемент \tt Y в сортиран масив в интервала \tt{[left; right]}
  \item първоначално \tt{left = 0}, \tt{right = n - 1}
  \item\label{it:start} намираме средата на масива \tt{mid = (left + right) / 2}
  \item сравняваме търсения елемент \tt Y с ключа \tt X на позиция mid
  \item ако \tt{Y == X} --- успех
  \item ако \tt{Y < X} --- търсим \tt Y отляво, \tt{right = mid - 1} и към \ballref{\ref{it:start}}
  \item ако \tt{Y > X} --- търсим \tt X отдясно, \tt{left = mid + 1} и към \ballref{\ref{it:start}}
  \end{enumerate}
  \pause
  \vspace{2ex}
  Времева сложност: \pause $O(\log n)$ в средния и най-лошия случай
\end{frame}

\begin{frame}
  \frametitle{Алгоритъм за бързо сортиране}

  \begin{enumerate}[<+->]
  \item Избираме елемент от масива („ос“)
  \item Разделяме масива на две части:
    \begin{itemize}
    \item елементи по-малки от оста
    \item елементи по-големи или равни на оста
    \end{itemize}
  \item поставяме оста между двете части на масива
  \item \alert{рекурсивно} сортираме поотделно двете части на масива
  \end{enumerate}
  \onslide<+->
  Този подход за решение се нарича „разделяй и владей“.
  \pause
  \vspace{2ex}
  \textbf{Времева сложност:}
  \begin{itemize}[<+->]
  \item $O(n\log n)$ в средния случай
  \item $O(n^2)$ в най-лошия случай
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Алгоритми за търсене и сортиране в STL}

  \lst!\#include <algorithm>!

  \begin{itemize}
  \item \lst{find(begin, end, value)} -- линейно търсене на елемент в контейнер
  \item \lst{is_sorted(begin, end)} -- проверка дали контейнер е сортиран
  \item \lst{binary_search(begin, end, value)} -- двоично търсене на елемент в сортиран контейнер
  \item \lst{merge(begin1, end1, begin2, end2, output)} -- сливане на два сортирани контейнера
  \item \lst{sort(begin, end)} -- сортиране на контейнер на място
  \end{itemize}
\end{frame}
}{}

\end{document}