basic-ds.tex

\chapter{Базовые структуры данных и алгоритмы}
\label{ch:basic-ds}

\section{$O$-нотация}
\label{sec:o-notation}

\textbf{Размер входных данных} зависит от рассматриваемой задачи.

\textbf{Время работы} алгоритма измеряется в количестве элементарных операций. Оно зависит от размера входных данных.

\textbf{Порядок роста}, или \textbf{скорость роста}. Пусть время работы алгоритма в наихудшем случае выражается формулой $an^2 + bn + c$, где $a$, $b$ и $c$ --- некоторые константы. Поскольку при больших $n$ членами меньшего порядка можно пренебречь, то рассматривается только главный член формулы $n^2$. Таким образом, время работы алгоритма в наихудшем случае равно $\Theta(n^2)$.

При \emph{асимптотическом анализе} нас интересует то, как растет время выволнения алгоритма с увеличением размера входных данных \emph{в пределе}.

\subsection{Обозначения}
\begin{tabular}{lp{11cm}}
  \toprule
  Обозначение & Объяснение \\
  \midrule
  $f(n) \in O(g(n))$ & $f$ ограничена сверху функцией $g$ (с точностью до постоянного множителя) асимптотически \\
  $f(n) \in \Omega(g(n))$ & $f$ ограничена снизу функцией $g$ (с точностью до постоянного множителя) асимптотически \\
  $f(n) \in \Theta(g(n))$ & $f$ ограничена снизу и сверху функцией $g$ асимптотически \\
  $f(n) \in o(g(n))$ & $g$ доминирует над $f$ асимптотически \\
  $f(n) \in \omega(g(n))$ & $f$ доминирует над $g$ асимптотически \\
  \bottomrule
\end{tabular}

\subsection{Определения}
\begin{align}
  f(n) \in O(g(n)) \quad = \quad &\exists c > 0, n_0 \quad \forall n > n_0 \quad f(n) \leq c \cdot g(n),\\
  f(n) \in \Omega(g(n)) \quad = \quad &\exists c > 0, n_0 \quad \forall n > n_0 \quad c \cdot g(n) \leq f(n),\\
  f(n) \in \Theta(g(n)) \quad = \quad &\exists c_1 > 0, c_2 > 0, n_0 \quad \forall n > n_0 \nonumber\\
                                      &c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n),\\
  f(n) \in o(g(n)) \quad = \quad &\forall \varepsilon > 0 \quad \exists n_0 \quad \forall n > n_0 \quad f(n) < \varepsilon \cdot g(n),\\
  f(n) \in \omega(g(n)) \quad = \quad &\forall c > 0 \quad \exists n_0 \quad \forall n > n_0 \quad c \cdot g(n) < f(n).
\end{align}

\section{Двоичный поиск}
\label{sec:binary-search}

Алгоритм поиска элемента в отсортированном массиве. В худшем случае выполняется за $\log{n}$.

Суть алгоритма следующая:

\begin{itemize}
  \item Выбирается опорный элемент, который находится в середине отсортированного массива.
  \item Если искомый элемент равен опорному, то возвращается индекс опорного элемента.
  \item Иначе:
    \begin{itemize}
      \item Если искомый элемент меньше опорного, то выполняются вышеуказанные действия для части, отстоящей слева от опорного элемента и состоящей из элементов, которые до сих пор не рассматривались вообще.
      \item Если искомый элемент больше опорного, то выполняются вышеуказанные действия для части, отстоящей справа от опорного элемента и состоящей из элементов, которые до сих пор не рассматривались вообще.
    \end{itemize}
\end{itemize}

\begin{clst}{Итеративный алгоритм бинарного поиска}{lst:iter-bin-search}
int binary_search(int elem, int array[], size_t length)
{
    int mid, min = 0, max = length - 1;

    do {
        mid = min + (max - min) / 2;
        if (elem > array[mid])
            min = mid + 1;
        else
            max = mid - 1;
    } while (min <= max && array[mid] != elem);

    if (array[mid] == elem)
        return mid;

    /* elem is not found */
    return -1;
}
\end{clst}

\begin{clst}{Рекурсивный алгоритм бинарного поиска}{lst:rec-bin-search}
int binary_search_aux(int elem, int array[], int low, int high)
{
    int mid;

    if (high < low)
        /* elem is not found */
        return -1;

    mid = low + (high - low) / 2;
    if (array[mid] > elem)
        return binary_search_aux(elem, array, low, mid - 1);
    if (array[mid] < elem)
        return binary_search_aux(elem, array, mid + 1, high);

    return mid;
}

int binary_search_rec (int elem, int array[], size_t length)
{
    return binary_search_aux(elem, array, 0, length - 1);
}
\end{clst}

\section{Быстрая сортировка}
\label{sec:qsort}

Она же \emph{quicksort}. Алгоритм состоит из следующих этапов:
\begin{itemize}
  \item выбирается опорный элемент;
  \item оставшиеся элементы делятся на две группы:
    \begin{enumerate}
      \item первая группа состоит из элементов, которые меньше опорного;
      \item вторая из тех, что больше либо равны;
    \end{enumerate}
  \item каждая группа обрабатывается аналогично.
\end{itemize}

\begin{center}
  \begin{tabular}{lc}
    \toprule
    Случай & Стоимость \\
    \midrule
    Худший & $\Theta(n^2)$ \\
    Лучший & $\Theta(n \log n)$ \\
    В среднем & $\Theta(n \log n)$ \\
    \bottomrule
  \end{tabular}
\end{center}

Вырожденный случай будет тогда, когда опорный элемент всегда будет наименьшим либо же наибольшим из всех элементов, обрабатываемой части массива.

\begin{clst}{Реализация}{lst:qsort}
static inline void swap(int a[], int i, int j)
{
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

void quicksort(int a[], int n)
{
    int i, last = 0;

    if (n <= 1)
        return;

    swap (a, 0, rand () % n);
    for (i = 1; i < n; i++)
        if (a[i] < a[0])
            swap(a, ++last, i);
    swap(a, 0, last);

    quicksort(a, last);
    quicksort(a + last + 1, n - last - 1);
}
\end{clst}

\section{Расширяемые массивы}
\label{sec:ext-arrays}

Массив, который расширяется по мере необходимости.
\begin{center}
  \begin{tabular}{lc}
    \toprule
    Операция & Стоимость \\
    \midrule
    Доступ к $n$-ому элементу & $\Theta(1)$ \\
    Затраты памяти & $\Theta(n)$ \\
    Вставка в конец & $\Theta(1)$ \\
    Вставка в произвольное место & $\Theta(n)$ \\
    \bottomrule
  \end{tabular}
\end{center}

В приведённой реализации ёмкость массива удваивается при вставке в уже заполненный до отказа массив. Поэтому вставка в конец заполненного массива выполняется за $\Theta(n)$, где $n$ — текущая ёмкость. Но если следом будет вставлено ещё $n - 1$ элемента, то можно считать, что и первый элемент был вставлен за константное время\footnote{За подробностями обращайтесь к \emph{амортизационному анализу (amortized analysis)}.}.

\begin{clst}{Некоторые операции}{lst:dynarray-impl}
struct ea {
    int count;
    int max;
    int *a;
};

enum {
    EA_INIT = 1,
    EA_GROW = 2
};

int add(struct ea *ea, int value)
{
    if (NULL == ea->a) {
        ea->a = (int *) malloc(EA_INIT * sizeof(int));
        if (NULL == ea->a)
            return -1;

        ea->max = EA_INIT;
        ea->count = 0;
    } else if (ea->count == ea->max) {
        int *a = (int *) malloc(EA_GROW * ea->max * sizeof(int));
        if (NULL == a)
            return -1;

        memcpy(a, ea->a, ea->count * sizeof(int));
        free(ea->a);

        ea->max *= EA_GROW;
        ea->a = a;
    }

    ea->a[ea->count] = value;
    return ea->count++;
}

int del(struct ea *ea, int value)
{
    for (int i = 0; i < ea->count; i++)
        if (value == ea->a[i]) {
            memmove(ea->a + i, ea->a + i + 1,
                    (ea->count - i - 1) * sizeof(int));

            ea->count--;
            return 1;
        }

    return 0;
}
\end{clst}

\begin{clst}{Пример использования}{lst:dynarray-usage}
struct ea array;

(void) add(&array, 5);
(void) add(&array, 3);
(void) add(&array, 2);
(void) add(&array, 7);
(void) add(&array, 6);

for (int i = 0; i < array.count; i++)
    printf("%d ", array.a[i]);
printf("\n");

(void) del(&array, 2);
(void) del(&array, 7);

for (int i = 0; i < array.count; i++)
    printf("%d ", array.a[i]);
printf("\n");
\end{clst}

\section{Списки}
\label{sec:lists}

Последовательность элементов. Различают \emph{односвязный} и \emph{двусвязный} списки. В односвязном списке можем двигаться в лишь одну сторону, находясь на каком-либо элементе; в двусвязном --- в любую.
\begin{center}
  \begin{tabular}{lc}
    \toprule
    Операция & Стоимость \\
    \midrule
    Доступ к $n$-ому элементу & $\Theta(n)$ \\
    Затраты памяти & $\Theta(n)$ \\
    Вставка в начало & $\Theta(1)$ \\
    \bottomrule
  \end{tabular}
\end{center}

Ниже приведено определение списка и реализация некоторых операций над ним.

\begin{clst}{Некоторые операции}{lst:list-impl}
struct list {
    int data;
    struct list *next;
};

struct list *make_item(int data)
{
    struct list *item = (struct list *) malloc(sizeof(struct list));

    item->data = data;
    item->next = NULL;

    return item;
}

struct list *add_front(struct list *head, struct list *item)
{
    item->next = head;
    return item;
}

struct list *add_back(struct list *head, struct list *item) {
    struct list *p;

    if (NULL == head)
        return item;

    for (p = head; p->next != NULL; p = p->next)
        ;
    p->next = item;
    return head;
}

#define for_each(n, head)                       \
    for (n = (head); n != NULL; n = n->next)    \

struct list *remove_item(struct list *head, int data)
{
    struct list *current, *prev = NULL;

    for_each(current, head) {
        if (data == current->data) {
            if (NULL == prev)
                head = current->next;
            else
                prev->next = current->next;

            free(current);
            return head;
        }

        prev = current;
    }

    return head;
}

void print_forwards(struct list *head)
{
    struct list *next;

    for_each(next, head)
        printf("%x ", next->data);
}

void print_backwards(struct list *item)
{
    if (NULL == item)
        return;

    print_backwards(item->next);
    printf("%x ", item->data);
}
\end{clst}

\begin{clst}{Пример использования}{lst:list-usage}
struct list *head = NULL;

head = add_front(head, make_item(1));
head = add_front(head, make_item(2));
head = add_front(head, make_item(3));
head = add_back(head, make_item(4));
head = add_back(head, make_item(5));

print_forwards(head);
printf("\n");
print_backwards(head);
printf("\n");

head = remove_item(head, 3);
head = remove_item(head, 1);
head = remove_item(head, 5);

print_forwards(head);
printf("\n");
print_backwards(head);
printf("\n");
\end{clst}

\section{Бинарные деревья поиска}
\label{sec:trees}

\textbf{Бинарное дерево} --- иерархическая структура данных. Каждый элемент содержит данные и указывает на $0..2$ других элементов. На каждый элемент, кроме \emph{корня}, указывает только один другой элемент. \emph{Листья} не указывают ни на один элемент.

\textbf{Бинарное дерево поиска} --- бинарное дерево, для каждого узла которого выполняются:
\begin{enumerate}
  \item Элементы левого поддерева ``меньше'' самого узла.
  \item Элементы правого поддерева ``больше'' самого узла.
  \item Оба поддерева --- бинарные деревья поиска.
\end{enumerate}

\begin{center}
  \begin{tabular}{lcc}
    \toprule
    Операция & Стоимость & Вырожденный случай \\
    \midrule
    Поиск элемента & $\Theta(\log n)$ & $\Theta(n)$ \\
    Затраты памяти & $\Theta(n)$ & \\
    Вставка & $\Theta(\log n)$ & $\Theta(n)$ \\
    Обход & $\Theta(n)$ & \\
    \bottomrule
  \end{tabular}
\end{center}

Примером вырожденного случая является бинарное дерево поиска, содержащие элементы от $1..10$, вставленных по порядку.

\begin{clst}{Некоторые операции}{lst:bst-impl}
struct tree {
    int data;
    struct tree *left;
    struct tree *right;
};

struct tree *make_node(int data)
{
    struct tree *node = (struct tree *) malloc(sizeof(struct tree));

    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return node;
}

struct tree *insert(struct tree *root, struct tree *node)
{
    if (NULL == root)
        return node;

    if (root->data < node->data)
        root->right = insert(root->right, node);
    else if (root->data > node->data)
        root->left = insert(root->left, node);
    /* skipping items that are already in the struct tree */

    return root;
}

void apply_fn_preorder(struct tree *root, void (*fn)(struct tree *))
{
    if (NULL == root)
        return;

    fn(root);
    apply_fn_preorder(root->left, fn);
    apply_fn_preorder(root->right, fn);
}

void print_node(struct tree *node) {
    printf("%d\n", node->data);
}

void print_tree(struct tree *root)
{
    apply_fn_preorder(root, &print_node);
}
\end{clst}

\begin{clst}{Пример использования}{lst:bst-usage}
struct tree *root = NULL;

root = insert(root, make_node(8));
root = insert(root, make_node(3));
root = insert(root, make_node(1));
root = insert(root, make_node(6));
root = insert(root, make_node(10));

print_tree(root);
\end{clst}

\section{Бинарные пирамиды}
\label{sec:bin-heaps}

Бинарное дерево, для которого выполнены следующие условия:
\begin{itemize}
  \item Значение в узле больше\footnote{Для ясности и удобства мы рассматриваем только отношение большинства, но, конечно же, можно использовать и отношение меньшинства при построение пирамиды, в таком случае в корне будет минимальное значение.} значений его потомков.
  \item Любой лист находится на высоте либо $d - 1$, либо $d$.
  \item Незаполненным может быть только наинизший уровень.
  \item Низший уровень заполняется слева направо.
\end{itemize}

\begin{center}
  \begin{tabular}{lc}
    \toprule
    Операция & Стоимость \\
    \midrule
    Поиск max элемента & $\Theta(1)$ \\
    Удаление max элемента & $\Theta(\log n)$ \\
    Вставка & $\Theta(\log n)$ \\
    \bottomrule
  \end{tabular}
\end{center}

Построение пирамиды из произвольного массива происходит следующим образом.

Обрабатываются уровни, начиная с предпоследнего и заканчивая корневым. На каждом уровне рассматриваются все элементы (не важно в каком порядке, но пусть для определённости направление будет справа налево). Если рассматриваемый элемент больше, чем его потомки, то переходим к следующему элементу. Если же нет, то меняем элемент с соответствующим потомком, — и спускаем подобным образом элемент по уровням до тех пор, пока он меньше своих прямых потомков, если таковые имеются.

\begin{clst}{Некоторые операции}{lst:binheap-impl}
#define HEAP_SIZE 50

struct binheap {
    int data[HEAP_SIZE];
    int size;
};

static inline int topos(int i)
{
    return i + 1;
}

static inline int toindex(int i)
{
    return i - 1;
}

static inline int parent(int i)
{
    return toindex(topos(i) / 2);
}

static inline int left(int i)
{
    return toindex(2 * topos(i));
}

static inline int right(int i)
{
    return toindex(2 * topos(i) + 1);
}

static inline void swap(int a[], int i, int j)
{
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

void max_heapify(struct binheap *heap, int i)
{
    int l = left(i);
    int r = right(i);
    int largest = i;

    if (l < heap->size && heap->data[l] > heap->data[i])
        largest = l;
    if (r < heap->size && heap->data[r] > heap->data[largest])
        largest = r;

    if (largest != i) {
        swap(heap->data, i, largest);
        max_heapify(heap, largest);
    }
}

void build_max_heap(struct binheap *heap)
{
    if (heap->size <= 1)
        return;

    for (int i = toindex(heap->size / 2); i >= 0; i--)
        max_heapify(heap, i);
}
\end{clst}

\begin{clst}{Пример использования}{lst:binheap-usage}
int i;
struct binheap heap = {
    .data = { 9, 1, 11, 13, 7, 3, 15, 17, 5 },
    .size = 9
};

build_max_heap(&heap);
for (i = 0; i < heap.size; i++)
    printf("%d ", heap.data[i]);
\end{clst}

\section{Пирамидальная сортировка}
\label{sec:heapsort}

Она же \emph{heapsort}. Алгоритм состоит из следующих шагов:
\begin{itemize}
  \item Создается невозрастающая бинарная пирамида in-place.
  \item Первый элемент (максимальный) меняется с последним. Подмассив $[1..(n - 1)]$ легко преобразуется в пирамиду. Повторять эти действия пока необходимо.
\end{itemize}

\begin{center}
  \begin{tabular}{lc}
    \toprule
    Случай & Стоимость \\
    \midrule
    Худший & $\Theta(n \log n)$ \\
    Лучший & $\Omega(n), O(n \log n)$ \\
    В среднем & $\Theta(n \log n)$ \\
    \bottomrule
  \end{tabular}
\end{center}

\begin{clst}{Реализация}{lst:heapsort}
void heapsort(struct binheap *heap)
{
    int size = heap->size;

    build_max_heap(heap);
    for (int i = size - 1; i > 0; i--) {
        swap(heap->data, 0, i);
        heap->size -= 1;
        max_heapify(heap, 0);
    }

    heap->size = size;
}
\end{clst}

\section{Очереди с приоритетом}
\label{sec:priority-queues}

Абстрактный тип данных, поддерживающий следующие операции:
\begin{itemize}
  \item $Insert(S, x)$ --- вставляет элемент $x$ в множество $S$;
  \item $Maximum(S)$ --- возвращает элемент с наибольшим ключом;
  \item $ExtractMax(S)$ --- возвращает элемент с наибольшим ключом, удаляя его из $S$;
  \item $IncreaseKey(S, x, k)$ --- заменяет ключ элемента $x$ ключом $k$, который не меньше текущего.
\end{itemize}

Мы будем реализовывать этот тип с помощью бинарной пирамиды. В следующей реализации ключ и данные представлены одним и тем же полем структуры для простоты.

Операция $heap\_maximum$ просто возвращает первый, корневой, элемент пирамиды.
Операция $heap\_extract\_max$ делает то, что и $heap\_maximum$, но при этом удаляет элемент из пирамиды. Происходит это следующим образом:

\begin{itemize}
  \item Первый элемент пирамиды заменяется последним.
  \item Размер пирамиды уменьшается на единицу.
  \item Новый корневой элемент распалагается в надлежащее место операцией $max\_heapify$.
\end{itemize}

Операция $heap\_increase\_key$ увеличивает приоритет заданного элемента, заодно перемещая его в надлежащее место. Делается это так:

\begin{itemize}
  \item Элементу назначается новый приоритет.
  \item Элемент перемещается до тех пор, пока он больше своего родителя либо же он не стал корневым.
\end{itemize}

Операция $heap\_insert$ добавляет новый элемент с заданным приоритетом $k$ в очередь. Свершение сего таково:

\begin{itemize}
  \item Элемент добавляется в конец с приоритетом $-\infty$.
  \item Вызовывается $heap\_increase\_key$ с переданным приоритетом $k$.
\end{itemize}

\begin{clst}{Некоторые операции}{lst:pqueue-impl}
int heap_maximum(struct binheap *heap)
{
    return heap->data[0];
}

int heap_extract_max(struct binheap *heap)
{
    int max = heap->data[0];

    heap->size -= 1;
    heap->data[0] = heap->data[heap->size];
    max_heapify(heap, 0);

    return max;
}


int heap_increase_key(struct binheap *heap, int i, int k)
{
    if (k < heap->data[i])
        return -1;

    heap->data[i] = k;
    while (i > 0 && heap->data[parent(i)] < heap->data[i]) {
        swap(heap->data, i, parent(i));
        i = parent(i);
    }

    return 0;
}

void heap_insert(struct binheap *heap, int k)
{
    heap->data[heap->size] = INT_MIN;
    heap->size += 1;
    heap_increase_key(heap, heap->size - 1, k);
}
\end{clst}

\begin{clst}{Пример использования}{lst:pqueue-usage}
int i;
struct binheap heap = {
    .data = { 9, 1, 11, 13, 7, 3, 15, 17, 5 },
    .size = 9
};

build_max_heap(&heap);
heap_insert(&heap, 8);
heap_insert(&heap, 19);
(void) heap_extract_max(&heap);
(void) heap_increase_key(&heap, 6, 12);
for (i = 0; i < heap.size; i++)
    printf("%d ", heap.data[i]);
\end{clst}

\section{Хеш-таблицы}
\label{sec:hash-tables}

Используются для отображения \emph{ключей} на \emph{значения}, иными словами --- для реализации \emph{словарей}. Ключи получают из значений при помощи \emph{хеш-функций}. В идеальном случае хеш-функция отображает каждый ключ на единственное значение. В неидеальном случае случаются коллизии.

\begin{center}
  \begin{tabular}{lcc}
    \toprule
    Операция & Стоимость & Вырожденный случай \\
    \midrule
    Поиск элемента & $O(1)$ & $\Theta(n)$ \\
    Затраты памяти & $\Theta(n)$ & \\
    Вставка & $O(1)$ & \\
    \bottomrule
  \end{tabular}
\end{center}

\subsection{Построение хеш-функций}
Значения качественной хеш-функции распределены (приблизительно) равномерно.

\textbf{Метод деления}. Отображение ключа $k$ в одну из ячеек путем получения остатка от деления $k$ на $m$, т.е $h(k) = k \mod m$.

Недостатком метода является зависимость качества хеш-функции от выбора $m$. Так, если $m = 2^p$, то значением $h(k)$ будут просто $p$ младших битов числа $k$. То есть распределение хеш-функции напрямую будет определяться распределением хешируемых значений.

\textbf{Метод умножения}. $h(k) = \lfloor m (kA \mod 1) \rfloor$, где $0 < A < 1$.
Достоинством метода является нечувствительность к выбору значения $m$.
Кнут предлагает использовать значение $A = \frac{1}{\varphi} \approx \frac{\sqrt{5} - 1}{2} \approx 0.6180339887...$

\subsection{Разрешение коллизий}
\textbf{Метод цепочек}. Каждая ячейка хеш-таблицы указывает на голову списка \emph{пар ключ-значение}. Значения, которые имеют одинаковые ключи, добавляются в один и то же список.

\textbf{Открытая адресация}. Все элементы хранятся непосредственно в самой хеш-таблице. Множество ячеек для проверки \emph{вычисляется}, а не представляется в виде списка. Таким образом, хеш-таблица может оказаться заполненной; в таком случае придётся выделять таблицу б\'{о}льшего размера и копировать все элементы в новую таблицу, предварительно вычисляя новое значение хеш-функции для каждого из них. Коэффициент заполнения $\alpha$ не может превышать единицу.

В конкретных реализациях хеш-таблиц, когда $\alpha \in [0.7; 0.75]$, происходит расширения хеш-таблицы, так как при $\alpha > 0.75$ эффективность резко падает (вплоть до того, что разрешение коллизий по методу цепочек может быть эффективней).

Распространенные методы вычисления:

\begin{itemize}
  \item \textbf{Линейное исследование}. $h(k, i) = (h^{'}(k) + i) \mod m$, где $h^{'}$ --- вспомогательная хеш-функция, $i \in [0, m -1 ]$.
  \item \textbf{Квадратичное исследование}. $h(k, i) = (h^{'}(k) + c_1i + c_2i^2) \mod m$, где $h^{'}$ --- вспомогательная хеш-функция, $i \in [0, m -1 ]$, $c_1$ и $c_2$ --- вспомогательные константы, отличные от $0$.
  \item \textbf{Двойное хеширование}. $h(k, i) = (h_1(k) + ih_2(k)) \mod m$, где $h_1$ и $h_2$ --- вспомогательные хеш-функции, $i \in [0, m -1 ]$.
\end{itemize}

Требуется, чтобы последовательность исследований $h(k, 0), h(k, 1), ..., h(k, m - 1)$ была перестановкой $0, 1, ..., m - 1$, то есть чтобы хеш-функция пробегала по всем ячейкам хеш-таблицы.

\subsection{Реализация}
Хеш-таблица построена на основе обычного массива длины $m$. Разрешение коллизий по методу цепочек.

\begin{clst}{Некоторые операции}{lst:htable-impl}
#define HTABLE_SIZE   20
#define MULTIPLIER    31

struct item {
    char *name;
    int value;
    struct item *next;
};

struct item *make_item(char *name, int value)
{
    struct item *item = (struct item *) malloc(sizeof(struct item));

    item->name = name;
    item->value = value;
    item->next = NULL;

    return item;
}

unsigned int hash(char *str)
{
    unsigned int h = 0;
    unsigned char *p = (unsigned char *) str;

    for (; *p != '\0'; p++)
        h = MULTIPLIER * h + *p;
    return h % HTABLE_SIZE;
}

struct item *lookup(struct item *htable[], char *name, bool create, int value)
{
    int h = hash(name);
    struct item *i = htable[h];

    for (; i != NULL; i = i->next)
        if (strcmp(name, i->name) == 0)
            return i;

    if (create) {
        i = make_item(name, value);
        i->next = htable[h];
        htable[h] = i;
    }
    return i;
}
\end{clst}

\begin{clst}{Пример использования}{lst:htable-usage}
struct item *htable[HTABLE_SIZE] = { NULL };

char *strings[] = { "string1", "string2", "string3",
                    "string4", "string5" };
int i;
struct item *it;

for (i = 0; i < 3; i++)
    lookup(htable, strings[i], true, i + 1);
for (i = 0; i < 5; i++) {
    it = lookup(htable, strings[i], false, 0);
    if (it)
        printf("%s in hash table, value = %d\n", it->name, it->value);
    else
        printf("%s somewhere else\n", strings[i]);
}
\end{clst}

\section{Динамическое программирование}
\label{sec:dyn-programming}

Если задача может быть решена рекурсивно, то есть ee решение может быть выражено через решение ee подзадач, причем некоторые подзадачи вычисляются много раз, то разумно, единожды вычислив подзадачу, сохранить ее значение и использовать его впоследствии. Такой прием называется \emph{динамическим программированием}.

Процесс разработки алгоритма динамического программирования состоит из следующих этапов:
\begin{enumerate}
  \item Описание структуры оптимального решения.
  \item Рекурсивное определение значения, соответствующего оптимальному решению.
  \item Вычисление значения, соответствующего оптимальному решению с помощью метода восходящего анализа.
  \item Составление оптимального решения на основе информации, полученной на предыдущих этапах.
\end{enumerate}

\subsection{Числа Фибоначчи}

Хоть числа Фибоначчи и не вычисляются методом динамического программирования, но на их примере наглядно изображается суть третьего пункта алгоритма динамического программирования.

Число Фибоначчи $F_n$ определено рекурсивно следующим образом:

\[
F_n = \left\{
  \begin{array}{l l}
    0 & \quad \text{при} \quad n = 0\\
    1 & \quad \text{при} \quad n = 1\\
    F_{n - 1} + F_{n - 2} & \quad \text{иначе}
  \end{array} \right.
\]

Прямая запись их определения на языке программирования имеет \emph{экспоненциальное} время работы. Проиллюстрируем это на примере вычисления $F_5$:

\begin{align*}
  F_5 & = F_4 + F_3\\
  & = F_3 + F_2 + F_2 + F_1\\
  & = F_2 + F_1 + F_1 + F_0 + F_1 + F_0 + 1\\
  & = F_1 + F_0 + 1 + 1 + 0 + 1 + 0 + 1\\
  & = 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1\\
  & = 5,
\end{align*}
то есть для того, чтобы вычислить $F_5$, нужно вычислить $F_4$ — $1$ раз, $F_3$ — $2$ раза, $F_2$ — $3$ раза, $F_1$ — $5$ раз, и $F_0$ — $3$ раза.

\begin{clst}{Медленная реализация}{}
unsigned long fib_slow(unsigned long n)
{
    if (n <= 1)
        return n;
    return fib_slow(n - 2) + fib_slow(n - 1);
}
\end{clst}

Может не хватить терпения дождаться вычисления $F_{100}$, используя вышеприведённую реализацаю на современном компьютере.

Используя приём динамического программирования можно сократить его до $\Theta(n)$, но за это придется заплатить $\Theta(n)$ памяти. Для этого нужно завести массив $t$, в котором элемент $t_i = t_{i - 1} + t_{i - 2}$, где $2 \leq i \leq n$.

\begin{clst}{Быстрая реализации с использованием массива}{}
unsigned long fib_fast(unsigned long n)
{
    unsigned long t[n + 1];

    if (n <= 1)
        return n;

    t[0] = 0;
    t[1] = 1;
    for (unsigned long i = 2; i <= n; i++)
        t[i] = t[i - 2] + t[i - 1];

    return t[n];
}
\end{clst}

Можно избавиться от необходимости использования $\Theta(n)$ памяти, если приметить, что для вычисления $F_i$ нужно только два вычисленных значения $F_{i - 1}$ и $F_{i - 2}$.

\begin{clst}{Быстрая реализация без дополнительного использования памяти}{}
unsigned long fib_fastest(unsigned long n)
{
    unsigned long t[] = { 0UL, 1UL };
    unsigned long tmp;

    if (n <= 1)
        return n;

    for (unsigned long i = 2; i <= n; i++) {
        tmp = t[0];
        t[0] = t[1];
        t[1] = t[1] + tmp;
    }

    return t[1];
}
\end{clst}

\subsection{Размен денег}
Пусть имеются копейки различных достоинств $K = \left\{ k_0, k_1, ..., k_k \right\}$, $k_i \in \mathbb{N}$, и $k_0 = 1$ коп. всегда. Для примера зафиксируем следующие номиналы: $k_0 = 1$ коп., $k_1 = 5$ коп., $k_2 = 10$ коп., $k_3 = 25$ коп.

Условимся, что элементы $K$ упорядочены, то есть $k_k > k_{k - 1} > ... > k_0$. Также количество копеек любого достоинства неограничено.

Поставленная задача — найти наименьший набор копеек, которым можно разменять сумму в $n$ копеек.

\textbf{Структура оптимального решения}. Обозначим через $C_{i, j}$ — наименьший набор копеек достоинств $k_0, k_1, ..., k_i$, которым можно разменять сумму $j$. Тогда сделать размен $C_{i, j}$ можно двумя способами:

\begin{enumerate}
  \item Сделать размен, не используя копейки достоинства $k_i$ (даже если и возможно её использование), то есть \[ C_{i, j} = C_{i - 1, j}. \]
  \item Использовать копейку достоинства $k_i$ и попробовать разменять сумму за вычетом номинала этой копейки, то есть \[ C_{i, j} = 1 + C_{i, j - k_i}. \]
\end{enumerate}

Тогда оптимальное решение примет вид \[ C_{i, j} = min(C_{i - 1, j}, 1 + C_{i, j - k_i}). \]

\textbf{Рекурсивное определение значения оптимального решения}. Из предыдущего рассуждения рекурсивное определение довольно очевидно, если держать в говове, что нулевая сумма не разменивается никоим образом и что сумму $j$ мы можем разменять $j$ копейками достоинства $1$ коп.:

\[
C_{i, j} = \left\{
  \begin{array}{l l}
    \infty & \quad \text{при} \quad j < 0\\
    0 & \quad \text{при} \quad j = 0\\
    j & \quad \text{при} \quad i = 0\\
    min(C_{i - 1, j}, 1 + C_{i, j - k_i}) & \quad \text{при} \quad j \geq 1
  \end{array} \right.
\]

\textbf{Вычисление значения оптимального решения «снизу вверх»}. Очевиднейшим образом можно построить таблицу значений $C_{i, j}$, основываясь на её рекурсивном определении.

\begin{clst}{}{}
#define array_size(a)                           \
    (sizeof(a) / sizeof((a)[0]))                \

#define min(a, b)                               \
    ({  __typeof__(a) _a = (a);                 \
        __typeof__(b) _b = (b);                 \
        _a < _b ? _a : _b; })

void change_coins(unsigned int n, unsigned int k, unsigned int coins[k],
                  unsigned int solution[k][n + 1])
{
    unsigned int i, j;

    for (i = 0; i < k; i++)
        solution[i][0] = 0;
    for (j = 1; j <= n; j++)
        solution[0][j] = j;

    for (i = 1; i < k; i++)
        for (j = 1; j <= n; j++)
            if (j < coins[i])
                solution[i][j] = solution[i - 1][j];
            else
                solution[i][j] = min(solution[i - 1][j],
                                     1 + solution[i][j - coins[i]]);
}
\end{clst}

После выполнения \lstinline{solution[k - 1][n]} будет содержать минимальное количество копеек, необходимых для размена.

\textbf{Составление оптимального решения}. Двигаясь из $C_{k, n}$ по обратному пути, можно восстановить конкретное оптимальное решение.

\begin{clst}{}{}
void recover_coins(unsigned int n, unsigned int k, unsigned int coins[k],
                   unsigned int solution[k][n + 1], unsigned int counts[k])
{
    unsigned int i, j;

    for (i = 0; i < k; i++)
        counts[i] = 0;

    i = k - 1;
    j = n;
    while (true) {
        if (0 == j)
            break;

        if (0 == i) {
            counts[0] += j;
            break;
        }

        if (solution[i - 1][j] < (1 + solution[i][j - coins[i]]))
            i -= 1;
        else {
            counts[i] += 1;
            j -= coins[i];
        }
    }
}
\end{clst}

\begin{clst}{Пример использования}{}
unsigned int i, j;
unsigned int n = 8;
unsigned int coins[] = { 1, 4, 6 };
unsigned int k = array_size(coins);
unsigned int solution[k][n + 1];
unsigned int counts[k];

change_coins(n, k, coins, solution);

for (i = 0; i < k; i++) {
    for (j = 0; j <= n; j++)
        printf("%d ", solution[i][j]);
    printf("\n");
}

if (0 == solution[k - 1][n])
    printf("No solution\n");
else {
    recover_coins(n, k, coins, solution, counts);

    for (i = 0; i < k; i++)
        printf ("%d kop.: %d\n", coins[i], counts[i]);
}
\end{clst}

\subsection{Расстояние Левенштейна}
Расстояние Левенштейна, или редакционное расстояние, — это минимальное количество операций вставки символа, удаления символа и замены одного символа на другой, необходимых для превращения одной строки в другую.

\textbf{Структура оптимального решения}. Пусть $S_1$ и $S_2$ --- две строки длины $m$ и $n$ соответственно. Обозначим редакционное расстояние этих строк через $d(m, n)$. Будем искать его через решение подзадач $d(i, j)$ для всех $i$ от $0$ до $m$ и для всех $j$ от $0$ до $n$.

\emph{Базовыми} случаями будут

\[
d(i, 0) = i
\]
и
\[
d(0, j) = j,
\]
так как для того, чтобы превратить строку $S_1[1..i]$ в пустую, необходимо удалить $i$ символов. Аналогично рассуждение и для превращения $S_2[1..j]$ в пустую строку.

Рассмотрим иные случаи. $d(i, j)$ равно количеству операций необходимых для преобразования. Последней операцией может быть вставка, удаление или замена, или же операции может и не быть вообще (то есть $S_1[i] = S_2[j]$).

Если последняя операция — вставка, то — вставка символа $S_2(j)$ в конец первой строки. Отсюда следует, что количество операций (кроме последней), которые преобразуют $S_i[1..i]$ в $S_2[1..j - 1]$, должно быть минимальным. Получаем, что $d(i, j) = d(i, j - 1) + 1$.

Аналогично: если последняя операция — удаление, то — удаление символа $S_1[i]$. Тогда количество всех предшествующих этому операций должно быть минимальным для преобразования $S_1[1..i - 1]$ в $S_2[1..j]$. То есть $d(i, j) = d(i - 1, j) + 1$.

Если же последняя операция — замена, то — замена $S_1[i]$ на $S_2[j]$. Поэтому предшествующие операции преобразуют $S_1[1..i - 1]$ в $S_2[1..j - 1]$, причём количество их — минимально. Иначе говоря: $d(i, j) = d(i - 1, j - 1) + 1$ в этом случае.

Если $S_1[i] = S_2[j]$, то никакой операции не требуется, поэтому $d(i, j) = d(i - 1, j - 1)$, то есть последовательность операций для преобразования $S_1[1..i]$ в $S_2[1..j]$ равна последовательности операций для преобразования $S_1[1..i - 1]$ в $S_2[1.. j - 1]$.

\textbf{Рекурсивное определение значения оптимального решения}. Исходя из изложенного, расстояние Левенштейна $d(i, j)$ можно посчитать по следующей рекуррентной формуле:

\[
  d(i, j) = \left\{
    \begin{array}{l r}
      0 & \quad \text{при} \quad i = 0, j = 0\\
      i & \quad \text{при} \quad i > 0, j = 0\\
      j & \quad \text{при} \quad i = 0, j > 0\\
      \min(\\
      \quad d(i, j - 1) + 1,\\
      \quad d(i - 1, j) + 1,\\
      \quad d(i - 1, j - 1) + t(S_1[i], S_2[j])\\
      )
        & \text{при} \quad i > 0, j > 0\\
    \end{array} \right.,
\]
где $t(a, b)$ равна нулю при $a = b$, в ином случае --- единице.

\textbf{Вычисление значения оптимального решения «снизу вверх»}. По формуле элементарно строится таблица значений. По окончании вычислений \lstinline{distances[m][n]} будет содержать редакционное расстояние.

\begin{clst}{}{}
#define min(a, b)                               \
    ({  __typeof__(a) _a = (a);                 \
        __typeof__(b) _b = (b);                 \
        _a < _b ? _a : _b; })

void distance(char *word1, char *word2, unsigned int *distances)
{
    unsigned int m = strlen(word1) + 1;
    unsigned int n = strlen(word2) + 1;
    unsigned int i, j;
    unsigned int add, del, change;

    for (i = 0; i < m; i++)
        distances[i * n] = i;
    for (j = 1; j < n; j++)
        distances[j] = j;

    for (i = 1; i < m; i++)
        for (j = 1; j < n; j++) {
            add = distances[i * n + (j - 1)] + 1;
            del = distances[(i - 1) * n + j] + 1;
            change = (word1[i - 1] == word2[j - 1]) ? 0 : 1;
            change += distances[(i - 1) * n + (j - 1)];

            distances[i * n + j] = min(min(add, del), change);
        }
}
\end{clst}

\begin{clst}{Пример использования функции}{}
char *word1 = "cat";
char *word2 = "kate";
unsigned int m = strlen(word1) + 1;
unsigned int n = strlen(word2) + 1;
unsigned int distances[m][n];
unsigned int i, j;

distance(word1, word2, (unsigned int *)distances);

for (i = 0; i < m; i++) {
    for (j = 0; j < n; j++)
        printf("%u ", distances[i][j]);
    printf("\n");
}
\end{clst}

\section{Некоторые заметки о языке C}
\label{sec:c-notes}

\begin{itemize}
  \item Правило right-left.
  \item Корректно ли выражение \lstinline{2["abc"]}. Если корректно, что оно значит?
  \item Безопасное использование макросов. Операторы \lstinline{#} и \lstinline{##}.
\end{itemize}

\begin{thebibliography}{9}

\bibitem{basic-ds:cormen05}
  Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн,
  \emph{Алгоритмы: построение и анализ}.
  Вильямс,
  2-е изд.,
  2005.

\bibitem{basic-ds:gusfield05}
  Д. Гасфилд,
  \emph{Строки, деревья и последовательности в алгоритмах}.
  СПб.: Невский диалект; БХВ-Петербург,
  2003.

\bibitem{basic-ds:kernigan04}
  Б. Керниган, Р. Пайк,
  \emph{Практика программирования}.
  Вильямс,
  2005.

\bibitem{basic-ds:harbison09}
  С. Харбисон, Г. Стил,
  \emph{Язык программирования С}.
  Бином,
  5-е изд.,
  2009.

\bibitem{basic-ds:love08}
  Р. Лав,
  \emph{Разработка ядра Linux}.
  Вильямс,
  2-е изд.,
  2008.

\bibitem{basic-ds:ritchie08}
  Б. Керниган, Д. Ритчи,
  \emph{Язык программирования С}.
  Вильямс,
  2-е изд.,
  2008.

\bibitem{basic-ds:levitin06}
  А. Левитин,
  \emph{Алгоритмы: введение в разработку и анализ}.
  Вильямс,
  2006.

\bibitem{basic-ds:shen07}
  А. Шень,
  \emph{Программирование. Теоремы и задачи}.
  МЦНМО,
  3-е изд.,
  2007.

\end{thebibliography}