Построение и анализ алгоритмов обработки данных

Министерство образования и науки Российской Федерации
Уральский федеральный университет
имени первого Президента России Б. Н. Ельцина

И. А. Селиванова, В. А. Блинов

ПОСТРОЕНИЕ И АНАЛИЗ  
АЛГОРИТМОВ ОБРАБОТКИ ДАННЫХ

Учебно-методическое пособие

Рекомендовано методическим советом УрФУ для студентов,  
обучающихся по программе бакалавриата  
по направлению подготовки  
230100 — Информатика и вычислительная техника

2-е издание, стереотипное

Москва
Издательство «ФЛИНТА»
Издательство Уральского университета
2017

УДК 004.021(075.8)
ББК 32.973-018.2я73
          С29

Рецензенты:
кафедра прикладной информатики Института урбанистки УралГАХА 
(зав. кафедрой канд. техн. наук, доц. Г. Б. Захарова);
зав. кафедрой математики и естественно-научных дисциплин Уральского института экономики, управления и права, канд. 
физ. -мат. наук, доц. С. П. Трофимов

Научный редактор — канд. техн. наук, доц. В. П. Битюцкий

С29

Селиванова, И. А.
Построение и анализ алгоритмов обработки данных

[Электронный ресурс] : учеб.-метод. пособие / И. А.
Селиванова, В. А. Блинов.   — 2-е изд., стер. — М. : ФЛИНТА :
Изд-во Урал. ун-та, 2017. —  108 с.

ISBN 978-5-9765-3234-2 (ФЛИНТА)
ISBN 978-5-7996-1489-8 (Изд-во Урал. ун-та)

Пособие содержит необходимый теоретический материал и примеры 
реализации данных, которые используются для неформального описания 
и реализации алгоритмов. Приведены и исследованы алгоритмы внутренней 
и внешней сортировки, алгоритмы поиска. Все рассмотренные методы 
сопровождаются наглядными примерами, кроме того, для большинства 
алгоритмов приведены фрагменты программного кода, что облегчает 
понимание деталей реализации алгоритмов. Заключительная глава содержит 
задания для 
лабораторных занятий.
Библиогр.: 4 назв. Табл. 6. Рис. 46.
УДК 004.021(075.8)
ББК 32.973-018.2я73

ISBN 978-5-9765-3234-2 (ФЛИНТА)
ISBN 978-5-7996-1489-8 (Изд-во Урал. ун-та)

                © Уральский федеральный  
                     университет, 2015

1. Алгоритмы и структуры дАнных

О
сновой программирования является алгоритм — конечный 
набор инструкций, приводящий от начальных данных к искомому результату. Алгоритмы необходимы из-за того, что решение 
задач ведется при ограниченном наборе ресурсов, таких как память, 
вычислительное время и прочее.
На данный момент разработано множество алгоритмов различной 
сложности и в различных областях, и знание алгоритмов, их использование и комбинирование позволяет решить большинство современных задач программирования.
Структурой данных называют множество элементов данных 
и множество связей между ними. Как и в случае с алгоритмами,  
их существует множество, и каждая используется в своей области 
задач.
Для реализации многих приложений выбор структуры данных — 
единственное важное решение: когда выбор сделан, разработка алгоритмов не вызывает затруднений. Для одних и тех же данных различные структуры будут занимать неодинаковое дисковое пространство. 
Одни и те же операции с различными структурами данных создают 
алгоритмы неодинаковой эффективности. Поэтому выбор алгоритмов тесно взаимосвязан с выбором структуры данных.

1.1. Классификация структур данных

Классификация структур данных может быть выполнена по различным признакам:
• 
по способу представления;
• 
по виду памяти, используемой для сохранности данных;
• 
по сложности представления;

Построение и анализ алгоритмов обработки данных

• 
по характеру упорядоченности элементов в структуре;
• 
по изменчивости.
Способ представления. Различают физическую и логическую 
(абстрактную) структуры данных. Физическая структура данных — 
это способ представления (хранения) данных в машинной памяти 
компьютера. Логическая структура — это рассмотрение структуры 
данных без учета ее представления в машинной памяти. В общем 
случае между логической и соответствующей ей физической структурами существуют расхождения, которые определяются самой структурой и особенностями той среды, в которой она должна быть реализована. Существуют процедуры, которые осуществляют отображение 
логической структуры в физическую и, наоборот, физической структуры в логическую.
Вид памяти, используемой для сохранности данных. В зависимости от размещения физических структур, а соответственно, 
и доступа к ним, различают внутренние и внешние структуры данных. 
Внутренние структуры — это данные, размещенные в статической 
и динамической памяти компьютера. Внешние структуры размещаются на внешних устройствах и называются файловыми структурами 
или файлами. Примеры файловых структур: файлы, В-деревья и др.
Сложность представления. Структуры данных делятся на элементарные и составные. Элементарными называются такие структуры данных, которые не могут быть расчленены на составные части. 
С точки зрения физической структуры важным является то обстоятельство, что в конкретной машинной архитектуре, в конкретной системе программирования всегда можно заранее сказать, каков будет 
размер элементарной единицы данных и как она будет размещена 
в памяти. С логической точки зрения элементарные единицы данных 
являются неделимыми. Составными называются такие структуры 
данных, которые могут быть разбиты на части — другие (элементарные или составные) структуры данных. Составные структуры данных 
конструируются программистом с использованием средств интеграции данных, предоставляемых языками программирования.
Характер упорядоченности элементов в структуре. Важный 
признак составной структуры данных — характер упорядоченности 
ее частей. По этому признаку структуры можно делить на линейные 
и нелинейные. Линейные структуры разделяют на структуры с последовательным расположением элементов в памяти (векторы, строки, 

1. Алгоритмы и структуры данных

массивы, стеки, очереди) и структуры с произвольным связным распределением элементов в памяти, к которым относятся односвязные 
и двусвязные линейные списки. Нелинейные структуры — многосвязные списки, деревья, графы.
Изменчивость. Изменчивость определяется изменением числа элементов и/или связей между составными частями структуры. 
В определении изменчивости структуры не учитывается факт изменения значений элементов данных, поскольку в этом случае все 
структуры данных имели бы свойство изменчивости. По признаку 
изменчивости различают структуры статические и динамические. 
Статическими, например, являются массивы, множества, записи, таблицы; динамическими — связные списки, графы, деревья.

1.2. Операции над структурами данных

Набор операций, используемых во многих алгоритмах, ограничивается возможностью вставлять элементы в множество, удалять их, 
а также проверять, принадлежит ли множеству тот или иной элемент. 
Динамическое множество, поддерживающее перечисленные операции, называется словарем (dictionary).
В динамических множествах некоторых типов предполагается, 
что одно из полей объекта идентифицируется как ключевое (key 
field). Если все ключи различны, то динамическое множество представимо в виде набора ключевых значений. Иногда объект содержит 
сопутствующие данные (satellite data), которые находятся в других его 
полях, но не используются реализацией множества. Кроме того, объект может содержать поля, доступные для манипуляции во время выполнения операций над множеством; иногда в этих полях хранятся 
данные или указатели на другие объекты множества.
На множестве структур данных существует набор операций, разделяющийся на запросы (queries), которые возвращают информацию 
о множестве, и модифицирующие операции (modifying operations), изменяющие множество. Ниже приведен список типичных операций:
• 
поиск в множестве элемента с заданным значением;
• 
добавление в множество элемента с заданным значением;
• 
удаление из множества элемента с заданным значением;
• 
поиск в множестве элемента с наименьшим значением;
• 
поиск в множестве элемента с наибольшим значением.

Построение и анализ алгоритмов обработки данных

Время, необходимое для выполнения операций множества, обычно 
измеряется в единицах, связанных с размером множества, который 
указывается в качестве одного из аргументов (например, О
n
(log ) ).

1.3. Понятие алгоритма обработки данных

Алгоритмом обработки данных называют метод решения задачи, 
который возможно реализовать в выбранной среде программирования. Тщательная разработка алгоритма является весьма эффективной частью процесса решения задачи в любой области применения. 
В разработку алгоритма для реальной задачи входит осознание степени ее сложности, выяснение ограничений на входные данные, разбиение задачи на менее трудоемкие подзадачи.
Алгоритм не должен быть привязан к конкретной реализации. 
В силу разнообразия используемых сред программирования, их требований к аппаратным ресурсам и платформенной зависимости, 
сходные по структуре, но различные в реализации алгоритмы могут 
выдавать отличающиеся по эффективности результаты. При этом 
некоторые среды программирования содержат встроенные библиотечные функции, реализующие базовые алгоритмы обработки данных. Чтобы решения были переносимыми и оставались актуальными, не рекомендуется их ориентировать на процедурную реализацию 
среды. Поэтому главным в рассматриваемом подходе является выбор 
метода решения с учетом специфики задачи. Адаптация к среде осуществляется позже.
Выбор того или иного метода обработки данных определяется 
не только сложностью задачи. Учитывать необходимо и массовость 
применения разработанного кода: при однократном или редком обращении к реализации предпочтительнее бывают простые алгоритмы, которые несложны в разработке. При этом допускается увеличение времени работы программы.
Алгоритмы должны обладать следующими формальными свойствами:
• 
понятность;
• 
дискретность;
• 
детерминированность;
• 
результативность;
• 
массовость.

1. Алгоритмы и структуры данных

Понятность. Исполнитель алгоритма должен знать, как его выполнять.
Дискретность. Алгоритм должен представлять процесс решения 
задачи как последовательное выполнение простых шагов (этапов), 
каждый из которых выполняется за конечное время.
Детерминированность. Каждое правило алгоритма должно 
быть четким, однозначным и выдавать для одних исходных данных 
всегда один и тот же результат.
Результативность. При корректно заданных исходных данных 
алгоритм должен завершать работу и выдавать результат за конечное 
число шагов.
Массовость. Алгоритм разрабатывается в общем виде и должен 
быть применим для некоторого класса задач и разных исходных данных.

1.4. Представление алгоритмов

На практике наиболее распространены следующие формы представления алгоритмов:
• 
словесная (записи на естественном языке);
• 
графическая (изображения из графических символов);
• 
псевдокоды (полуформализованные описания алгоритмов 
на условном алгоритмическом языке, включающие в себя как 
элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);
• 
программная (тексты на языках программирования).
Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается 
в произвольном изложении на естественном языке. Например: записать алгоритм нахождения наибольшего общего делителя (НОД) двух 
натуральных чисел.
Алгоритм может быть следующим:
1)
задать два числа;
2)
если числа равны, то взять любое из них в качестве ответа 
и остановиться, в противном случае продолжить выполнение 
алгоритма;
3)
определить большее из чисел;

Построение и анализ алгоритмов обработки данных

4)
заменить большее из чисел разностью большего и меньшего 
из чисел;
5)
повторить алгоритм с шага 2.
Словесный способ не имеет широкого распространения из-за отсутствия строгой формализации словесного описания алгоритма.
Графический способ представления алгоритмов является более 
компактным и наглядным по сравнению со словесным. При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый 
из которых соответствует выполнению одного или нескольких действий. Такое графическое представление называется схемой алгоритма (или граф-схемой алгоритма — ГСА).
В схеме алгоритма каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т. п.) соответствует геометрическая фигура, представленная в виде блочного 
символа. Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий.
Правила выполнения схем алгоритма определяются в ГОСТ 
19.701–90. В следующей таблице приведены наиболее часто употребляемые символы.
Таблица 1.1
Элементы схемы алгоритма

Название  
символа
Символ
Отображаемая функция

Процесс

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

1. Алгоритмы и структуры данных

Решение

Логический блок: проверка условий.
Выбор направления выполнения алгоритма 
в зависимости от некоторых условий.
Используется 
для 
обозначения 
переходов 
управления по условию. В каждом блоке «решение» должны быть указаны вопрос, условие или 
сравнение, которые он определяет.
Отображает решение или функцию с одним 
входом и несколькими альтернативными выходами, например знаки >, <, =, операции if, case

Блоки вводавывода

Общее обозначение ввода или вывода данных

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

Терминатор

Начало или конец программы, пуск-останов, 
вход или выход в подпрограммах.
Элемент отображает выход во внешнюю среду 
и вход из внешней среды (начало и конец программы)

Предопределенный процесс

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

Модификация

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

На рис. 1.1 изображена типовая схема алгоритма.

Окончание табл. 1.1

Построение и анализ алгоритмов обработки данных

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

Ввод исходных данных

Обработка 
введенных 
данных

Вызов 
процедуры

Вывод 
результата

Конец

Нет

Да

Данные 
корректны?