Алгоритмы и структуры данных Введение

Алгоритмы и структуры данных | Введение

1. Что такое алгоритм?

1.1. Вычислительные алгоритмы

Говоря об алгоритмах, мы подразумеваем алгоритмы обработки информации, то есть набор вычислительных процедур, приводящий к определенной цели. Цель предполагает заданную связь между входными и выходными данными, и цель считается достигнутой тогда и только тогда, когда вычислительный алгоритм выдает правильный результат на всём диапазоне входных данных за конечное время. При этом каждый шаг алгоритма должен иметь четко определенный смысл.

Итак, корректно определенный вычислительный алгоритм обладает свойствами конечности времени выполнения алгоритма, определенности формулировки каждого шага, наличием определенного множества входных данных и определенной функции, которую алгоритм должен вычислить эффективно [Кнут1, с. 31].

Алгоритм считается правильным, если он реализует указанную функцию $f : D \to Y$, где $D \subset X$ – множество входных данных, $X$ – тип входных данных, $Y$ – тип выходных данных.

Алгоритм считается эффективным, если для его выполнения требуется хранить не слишком много данных и работает он не слишком долго.

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

1.2. Абстракция данных

В рамках программной реализации вычислительного алгоритма мы всегда говорим о конкретном представлении информации об объектах реального мира (либо абстрактных объектах – текстах, например) в памяти электронно-вычислительного устройства. При этом мы хорошо понимаем, что способов такого представления может быть сколько угодно. Но все такие представления соответствуют одной и той же информационной структуре.

Таким образом, информационная структура – это совокупность сведений о каком-нибудь объекте, и для представления этих сведений можно использовать не только двоичный код, но и любой формальный язык.

На формальном языке мы можем описать и тип информационной структуры (метаданные), и конкретную информацию в этой структуре (данные), что мы и делаем, когда пишем программу на некотором языке программирования.

Заметим, что информационная структура не зависит от языка, с помощью которого она представлена. Это дает нам возможность абстрагироваться от способа представления информации об объектах.

Как мы можем работать с объектами без конкретизации языка их описания? Использовать абстрактный алгебраический язык. (“Алгоритм” и “алгебра” – слова однокоренные.) Например, мы можем определить такие абстракции, как: “целые числа”, “действительные (вещественные) числа”, “комплексные числа”, “классы вычетов по модулю $m$”, “многочлены”, “матрицы”, “множества”, “функции”. (Последние две абстракции чересчур абстрактны вне определенного контекста.) Каждую абстракцию будем интерпретировать как тип информационной структуры, а элемент соответствующей алгебраической конструкции – это информационная структура.

Но чисто алгебраических структур недостаточно для охвата всех типов информационных структур. Среди информационных структур популярны таблицы, словари, деревья, сети. И хотя их можно определить через множества и функции, такое определение в контексте хранения данных в памяти ЭВМ не всегда будет уместным.

Например, как определить информационную структуру “последовательность элементов некоторого типа $T$”? Можно как множество пар

\[\{(i,a_i) : i = 1, 2, \dots, n\} \subset \mathbb N \times T,\]

можно как функцию

\[a : \{1, \dots, n\} \to T,\]

а можно как совокупность объектов типа $T$, для которых указан порядок их следования:

\[a_1, \; a_2, \; \dots, \; a_n \in T\]

Для типа информационной структуры, выраженной в виде алгебраической конструкции либо связки объектов, будем применять термин абстрактный тип данных [АхоХопУль, с. 23]. Всякий абстрактный тип данных предполагает набор операций над объектами этого типа.

Операция над объектом является либо запросом, который вычисляет определенную функцию от объекта, либо модификацией, которая изменяет сам объект по определенному правилу.

Примеры АТД:

1) “числовое множество”

Операции над объектами:

запросы: поиск элемента, количество элементов;

модификации: добавить элемент, удалить элемент.

Бинарные операции типа: объединение $\cup$, пересечение $\cap$, разность $\setminus$.

2) “логическое высказывание”

Бинарные операции типа: конъюнкция $\&$, дизъюнкция $\vee$.

Унарные операции типа: отрицание $\lnot$.

3) “число”

Бинарные операции типа: $+, \; -, \; \cdot, \; /$.

4) “последовательность типа $T$”

Операции над объектами:

запросы: значение заданного элемента, длина последовательности;

модификации: добавить элемент, удалить элемент, изменить заданный элемент.

Бинарные операции типа: конкатенация $\times$.

5) “первокурсник”

Студенты стоят в очереди на заселение, и мы можем мысленно произвести над ними какие-то вычислительные операции – например, упорядочить по росту, разбить всё множество студентов на два подмножества по некоторому критерию. Но при сортировке мы не людей будем переставлять, а работать с информацией о студентах.

Информацию о них можно представить в виде информационной структуры, которая будет объектом абстрактного типа данных ${\tt Студент}$. Например:

\[\tt Студент = \{ ФИО, пол, школа, направление\ подготовки, откуда\ приехал \}\] \[ФИО \in {\tt Str} \times {\tt Str} \times {\tt Str}\] \[пол \in \{ \bigtriangleup, \bigtriangledown \}\] \[школа \in \{ШЕН, ИШ, \dots\}\] \[направление\ подготовки \in Направления\] \[откуда\ приехал \in [Регион, НаселенныйПункт]\]

Ограничения:

\[(школа, направление) \in R_1\] \[(регион, населенный\ пункт) \in R_2\]

$R_1, R_2$ – отношения между типами. На $n$-арных отношениях основаны реляционные базы данных [Дунаев, с. 249].

Например,

\[(ШЕН,\, ПМИ) \in R_1, \quad (ИШ,\, ПМИ) \notin R_1\] \[(Приморский\ край,\, Владивосток) \in R_2, \quad (Якутия,\, Москва) \notin R_2\]

Таким образом, абстракция данных позволяет нам формулировать не только вычислительные алгоритмы, состоящие из операций над данными, хранящимися в памяти электронно-вычислительного устройства, но и оперировать формальными представлениями любых информационных структур. На практике это соответствует автоматической системе управления техническим или организационным процессом.

Итак, алгоритм удобно формулировать в абстрактных терминах, то есть не конкретизируя способ представления объектов АТД. Это позволяет отделить построение и анализ вычислительной процедуры от способа хранения данных и формы записи алгоритма. С одной стороны, это удобнее, чем пытаться держать в голове всё и сразу. С другой стороны, если абстрагироваться от лишних деталей, то сформулированный таким образом ход вычислений не будет зависеть от реализации отдельных операций, что повышает эффективность разработки. Наконец, абстракция данных может быть выражена в явном виде на некоторых языках программирования (пример – объектно-ориентированное и обобщенное программирование в C++).

1.3. Структуры данных и реализация алгоритмов

Под структурой данных мы понимаем представление информационной структуры (или абстрактного типа данных) в двоичном виде с указанием способа вычисления набора операций над данными.

Под представлением АТД будем понимать взаимно однозначное соответствие между множеством представимых объектов АТД и множеством строк определенной структуры (множеством представлений) над некоторым алфавитом.

Примеры представлений АТД:

1) АТД “целое число”, СД “32-битное целое число со знаком”

Множество представимых объектов: $-2^{31}..2^{31}-1$ (мощность множества $2^{32}$).

Алфавит: $B = \{0, 1\}$.

Множество представлений: $B^{32} = \{(b_1, b_2, \dots, b_{32}) : b_i \in B\}$.

Соответствие [Андреева, разд. 2.1]:

Для чисел $n \in 0 .. 2^{31}-1$: $b_{32} = 0$, $(b_1, \dots, b_{31})$ – представление числа $n$ в 2-ичной системе счисления.

Для чисел $n \in -2^{31}..-1$: $b_{32} = 1$, $(b_1, \dots, b_{31})$ – представление числа $2^{31}-|n|$ в 2-ичной системе счисления.

2) АТД “последовательность типа $T$”, СД “массив элементов типа $T$”

Представление каждого элемента последовательности определяется представлением типа $T$. Представление последовательности в виде массива означает, что все элементы последовательности будут располагаться в памяти последовательно друг за другом. Тогда, зная адрес первого элемента массива, легко вычислить адреса всех остальных элементов по формуле арифметической прогрессии.

Длина массива может совпадать с длиной последовательности, если длина последовательности фиксирована, либо равняться максимально возможной длине последовательности, либо изменяться динамически.

3) АТД “последовательность типа $T$”, СД “связный список элементов типа $T$”

Элементы последовательности могут храниться в памяти где угодно, а не только друг за другом. Каждый элемент последовательности хранится в памяти вместе со ссылкой на следующий элемент последовательности. В двусвязном списке в такой структуре также присутствует ссылка на предыдущий элемент последовательности.

4) АТД “программа на ЯП Си”

Алфавит: $\{буквы\} \cup \{цифры\} \cup \{пробельные\ символы\} \cup \{скобки,\ знаки\ операций\ и\ т.п.\}$

Множество представлений: последовательности строк, построенные по определенным правилам.

Соответствие: последовательности символов однозначно соответствует древовидная структура программы, включающая описание хранимых данных и действий над этими данными.

Другое представление упомянутой структуры программы – структура данных в памяти компьютера, которая строится в ходе компиляции.

Всякий алгоритм, сформулированный для вычислительной машины на определенном языке, является операцией над данными. Таким образом, если алгоритм сформулирован в абстрактных терминах над соответствующими АТД, то реализация алгоритма предполагает замену операций над АТД операциями над СД (с учетом возможного сужения множества представимых объектов по отношению ко всему АТД) и запись этих операций на определенном ЯП.

Итог

Информационная структура – это некое описание объекта, с которым мы работаем.

Абстрактный тип данных – это формальное описание.

Структура данных – это указание, в каком виде хранить эти данные и как организовать доступ к ним.

Алгоритм удобно формулировать в абстрактных терминах, то есть не конкретизируя способ представления объектов АТД. Поскольку алгоритм сам является объектом АТД “алгоритм”, то способ записи алгоритма также не важен.

Литература

[Кнут1] Кнут – Искусство программирования. Т. 1. Основные алгоритмы

[АхоХопУль] Ахо, Хопкрофт, Ульман – Структуры данных и алгоритмы (2000)

[Дунаев] Дунаев – Занимательная математика. Множества и отношения (2008)

[Андреева] Андреева, Босова, Фалина – Математические основы информатики (2005)