Алгоритмы и структуры данных (CDIO)

Оглавление 
 

1 

Министерство образования и науки Российской Федерации 
Сибирский федеральный университет 
 
 
 
 
 
 
 
 
Р. Ю. Царёв 
А. В. Прокопенко 
 
 
АЛГОРИТМЫ  
И  СТРУКТУРЫ  ДАННЫХ  (CDIO) 
 
 
Рекомендовано УМО РАЕ по классическому университетскому 
и техническому образованию в качестве учебника для студентов высших учебных заведений, обучающихся по направлениям подготовки: 09.03.04 «Программная инженерия», 09.03.03 
«Прикладная информатика», 38.03.02  «Менеджмент», 38.03.05  
«Бизнес-информатика» (рег. № 516 от 03.06.2015 г.) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Красноярск 
СФУ 
2016 

Алгоритмы и структуры данных (CDIO) 

2 

УДК 004.422.63(07) 
ББК 32.973я73 
        Ц181 
 
 
 
 
 
Р е ц е н з е н т ы: 
А. Н. Антамошкин, доктор технических наук, профессор Красноярского государственного аграрного университета; 
А. А. Ступина, доктор технических наук, профессор Красноярского 
государственного аграрного университета 
 
 
 
 
 
 
 
 
 
 
 
Царёв, Р. Ю. 
Ц181  
Алгоритмы и структуры данных (CDIO) : учебник / Р. Ю. Царёв, А. В. Прокопенко. – Красноярск : Сиб. федер. ун-т, 2016. – 204 с.  
ISBN 978-5-7638-3388-1 
 
Рассмотрены структуры данных и алгоритмы, которые являются основой 
современной методологии разработки программ. Приведено детальное описание 
и анализ основных алгоритмов обработки данных: сортировка данных, поиск 
образа в строке, алгоритмы обработки графов.  
Предназначен для бакалавров направлений 09.03.04 «Программная инженерия», 09.03.03 «Прикладная информатика», 38.03.02 «Менеджмент», 38.03.05 
«Бизнес-информатика» и преподавателей дисциплины «Алгоритмы и структуры 
данных». 
 
 
Электронный вариант издания см.: 
http://catalog.sfu-kras.ru 
УДК 004.422.63(07) 
ББК 32.973я73 
 
ISBN 978-5-7638-3388-1                                                            © Сибирский федеральный  
                                                                                                          университет, 2016 

Оглавление 
 

3 

 
ОГЛАВЛЕНИЕ 
 
ВВЕДЕНИЕ .......................................................................................................... 6 
 
1. ОБЩИЕ  СВЕДЕНИЯ  ОБ  АЛГОРИТМАХ ................................................ 9 
1.1. Свойства алгоритмов ............................................................................. 11 
1.2. Примеры алгоритмов ............................................................................. 12 
1.3. Типы и структуры данных .................................................................... 14 
1.4. Абстрактные типы данных ................................................................... 16 
1.5. Время выполнения программ ............................................................... 18 
1.6. Вычисление времени выполнения программ ..................................... 24 
 
2. ПОИСК  ОБРАЗА  В  СТРОКЕ .................................................................... 34 
2.1. Прямой поиск строки ............................................................................ 34 
2.2. Алгоритм Кнута, Морриса и Пратта .................................................... 36 
2.3. Алгоритм Бойера и Мура ...................................................................... 39 
 
3. СОРТИРОВКА  МАССИВОВ ..................................................................... 44 
3.1. Сортировка с помощью прямого включения ...................................... 45 
3.2. Сортировка с помощью прямого выбора ............................................ 47 
3.3. Сортировка с помощью прямого обмена ............................................ 49 
3.3.1. Пузырьковая сортировка ............................................................ 49 
3.3.2. Шейкерная сортировка ............................................................... 50 
3.4. Сортировка Шелла ................................................................................. 52 
3.5. Сравнение различных алгоритмов сортировки .................................. 54 
 
4. СОРТИРОВКА  ПОСЛЕДОВАТЕЛЬНОСТЕЙ ......................................... 57 
4.1. Простое слияние .................................................................................... 57 
4.2. Естественное слияние ........................................................................... 61 
4.3. Многопутевая сортировка .................................................................... 64 
4.4. Многофазная сортировка ...................................................................... 75 
 
5. СТРУКТУРЫ  ДАННЫХ ............................................................................. 95 
5.1. Массивы .................................................................................................. 95 
5.2. Списки .................................................................................................... 96 
5.2.1. Стек .............................................................................................. 97 
5.2.2. Очередь ........................................................................................ 98 
5.2.3. Дек ................................................................................................ 99 

Алгоритмы и структуры данных (CDIO) 

4 

5.3. Деревья ................................................................................................... 99 
5.3.1. Двоичное дерево ....................................................................... 101 
5.3.2. Двоичное дерево поиска .......................................................... 103 
5.3.3. Куча ............................................................................................ 104 
5.3.4. АВЛ-дерево ............................................................................... 105 
 
6. ОРИЕНТИРОВАННЫЕ  ГРАФЫ .............................................................. 110 
6.1. Основные определения ....................................................................... 110 
6.2. Представления ориентированных графов ......................................... 112 
6.3. Задача нахождения кратчайшего пути .............................................. 114 
6.4. Нахождение кратчайших путей между парами вершин .................. 119 
6.5. Обход ориентированных графов ........................................................ 125 
6.6. Ориентированные ациклические графы ............................................ 129 
6.7. Сильная связность ............................................................................... 133 
 
7. НЕОРИЕНТИРОВАННЫЕ  ГРАФЫ ........................................................ 136 
7.1. Основные определения ........................................................................ 136 
7.2. Остовные деревья минимальной стоимости ..................................... 139 
7.3. Обход неориентированных графов .................................................... 146 
7.4. Точки сочленения и двусвязные компоненты .................................. 150 
7.5. Паросочетания графов ......................................................................... 153 
7.6. Максимальный поток в сети ............................................................... 157 
 
8. СОВРЕМЕННЫЕ  АЛГОРИТМЫ  ОБРАБОТКИ  ДАННЫХ ............... 163 
8.1. Алгоритмы и простые числа .............................................................. 163 
8.2. Генетические алгоритмы .................................................................... 168 
8.3. Муравьиные алгоритмы...................................................................... 173 
8.3.1. Биологические принципы поведения  
          муравьиной колонии ................................................................ 174 
8.3.2. Идея муравьиного алгоритма .................................................. 174 
8.3.3. Формализация задачи коммивояжера  
          в терминах муравьиного подхода ........................................... 175 
8.3.4. Области применения и возможные модификации ................ 178 
 
9. ПАРАЛЛЕЛЬНЫЕ  АЛГОРИТМЫ ........................................................... 180 
9.1. Введение в параллелизм ..................................................................... 180 
9.1.1. Категории компьютерных систем ........................................... 181 
9.1.2. Параллельные архитектуры ..................................................... 182 
9.1.3. Принципы анализа параллельных алгоритмов ...................... 184 
9.2. Модель PRAM ...................................................................................... 184 
 

Оглавление 
 

5 

9.3. Простые параллельные операции ...................................................... 186 
9.3.1. Распределение данных в модели CREW PRAM ..................... 186 
9.3.2. Распределение данных в модели EREW PRAM ..................... 187 
9.3.3. Поиск максимального элемента списка ................................. 188 
9.4. Параллельный поиск ........................................................................... 190 
9.5. Параллельная сортировка ................................................................... 191 
9.5.1. Сортировка на линейных сетях ............................................... 191 
9.5.2. Четно-нечетная сортировка перестановками ......................... 195 
9.5.3. Другие параллельные сортировки .......................................... 196 
9.6. Параллельные алгоритмы на графах ................................................. 196 
9.6.1. Параллельный алгоритм поиска кратчайшего пути ............. 196 
9.6.2. Параллельный алгоритм поиска  
          минимального остовного дерева ............................................. 198 
 
ЗАКЛЮЧЕНИЕ ............................................................................................... 201 
 
БИБЛИОГРАФИЧЕСКИЙ СПИСОК ........................................................... 203 

Алгоритмы и структуры данных (CDIO) 

6 

 
ВВЕДЕНИЕ 
 
CDIO (от англ. conceive, design, implement, operate – планировать, 
проектировать, производить, применять) представляет собой новую философию обучения студентов инжинирингу. Основной идеей данной инициативы является предоставление студентам инженерных специальностей        
такого образования, которое подчеркивает инженерные основы, изложенные 
в контексте жизненного цикла реальных систем, процессов и продуктов. 
Данный международный проект направлен на устранение противоречий между теорией и практикой в инженерном образовании. Новый подход 
предполагает усиление практической направленности обучения, а также 
введение системы проблемного и проектного обучения.  
CDIO подразумевает проектно-ориентированное обучение, построенное 
на определенных стандартах. В стандартах CDIO определены специальные 
требования к программам CDIO, которые могут выступать руководством 
для реформирования и оценки образовательных программ в области техники и технологий, создавать условия для их непрерывного улучшения            
и интеграции в мировое образовательное пространство. 
Решение любой вычислительной задачи предполагает выполнение 
определенной последовательности шагов. При этом один и тот же результат может быть получен различными способами. Один из способов может 
быть более эффективным, другой менее эффективным, но более легким           
в реализации. Алгоритм, будучи той самой последовательностью шагов, 
можно оценить так, как это будет показано дальше. Имея набор алгоритмов, предназначенных для решения какой-либо проблемы, программист            
в состоянии выбирать удовлетворяющий его нуждам. 
В настоящем учебнике приведены различные алгоритмы решения 
довольно широкого класса задач. Данные алгоритмы не привязаны к какому-либо языку программирования, хотя предполагается, что программная  
реализация будет выполняться на языке программирования высокого 
уровня. Теоретическая часть наглядно иллюстрируется примерами на языках Pascal, Си и псевдоязыке, сочетающем высказывания на естественном 
языке с одним из указанных выше языков программирования. 
Приведенные в данном учебнике алгоритмы представляют собой 
«классику» в области обработки данных. Существенный вклад в развитие 
современной теории алгоритмов и алгоритмизации решения практических 
задач внесли такие ученые, как Н. Вирт [2], Д. Кнут [4], Дж. Макконнелл [6],  
к трудам которых можно обратиться для более глубокого исследования 

Введение 
 

7 

проблемы построения и анализа алгоритмов. Большое количество информации об алгоритмах можно также найти в сети Интернет, как на англоязычных, так и на русскоязычных сайтах. 
Учебник освещает структуры данных и алгоритмы решения наиболее 
распространенных задач, покрывая практически всю область программирования. Здесь приведены как фундаментальные алгоритмы, так и современные методы обработки данных. Учебник состоит из девяти глав, посвященных алгоритмам решения различных классов задач.  
В первой главе приводятся основные сведения об алгоритмах, их  
свойства. Отражена разница между такими понятиями, как «структура  
данных», «тип данных» и «абстрактный тип данных». Показано, как может 
измеряться временная сложность алгоритма, которая в дальнейших главах 
служит основным критерием оценки скорости выполнения алгоритма. 
Следующая глава касается поиска образа в строке. Наглядным примером этой задачи может служить поиск слова в тексте в редакторе Word.  
Вообще задача поиска является одной из фундаментальных задач теоретического программирования. В этой главе приведен алгоритм прямого поиска, а также два алгоритма, позволяющих произвести более эффективный 
поиск.  
Сортировка или упорядочивание ряда объектов по возрастанию или 
убыванию является одной из основных задач обработки данных. Выбор алгоритма и даже класса алгоритмов, используя который возможно произвести 
сортировку, зависит от структуры данных. В связи с этим выделяют два 
типа сортировки: внутреннюю и внешнюю.  
Третья глава учебника посвящена алгоритмам внутренней сортировки, при которой все данные помещаются в оперативную память, где можно 
получить доступ к данным в любом порядке. Работа алгоритмов данного 
класса показана на примере упорядочивания элементов массива. 
Внешняя сортировка применяется в том случае, когда объем упорядочиваемых данных настолько большой, что невозможно поместить все 
данные в оперативную память. Здесь задействуется механизм обмена 
большими блоками данных между внешними запоминающими устройствами и оперативной памятью. Тот факт, что физически непрерывные данные необходимо для удобства перемещения организовывать в блочную 
структуру вынуждает использовать специальные алгоритмы внешней сортировки. Алгоритмам внешней сортировки посвящена четвертая глава,           
в которой предполагается, что все данные хранятся в файлах. 
Невозможно говорить о практической или даже формальной реализации алгоритмов безотносительно структур и типов данных. Пятая глава 
посвящена различным структурам данных, которые позволяют хранить          
и обрабатывать данные, исходя из особенностей решаемой задачи. В дан

Алгоритмы и структуры данных (CDIO) 

8 

ной главе рассматриваются как простые, так и «интегрированные» структуры данных, которые состоят из простых: массивы, списки, деревья, графы.  
В шестой главе показаны ориентированные графы. Решается такая 
важная задача, как поиск кратчайшего пути между двумя вершинами. 
Умение решать данную задачу помогает в планировании кратчайшего 
маршрута, например, при передвижении на транспортном средстве или передаче сообщений по компьютерной сети. Также в этой главе показано, как 
можно перебрать все вершины графа методом обхода в глубину, что может 
потребоваться при поиске одной вершины во всем множестве вершин графа. 
В седьмой главе приведены основные определения, связанные с неориентированными графами. Помимо обхода в глубину рассматривается 
обход в ширину, который, впрочем, также применим и к ориентированным 
графам. Другой немаловажной задачей, алгоритмы решения которой представлены в данной главе, является построение минимального остовного дерева графа. Одно из применений минимальных остовных деревьев – организация локальной компьютерной сети с минимальными затратами            
на объединение всех компьютеров в единую сеть. Здесь же рассматривается 
связность графа и задача о паросочетании. 
Восьмая глава содержит краткое изложение некоторых идей, на основе которых разрабатываются современные алгоритмы. Примечательно, 
что данные алгоритмы используются не только для решения практических 
задач, но также активно применяются в научных исследованиях. Генетические алгоритмы  можно встретить в диссертационных работах по различным направлениям. Здесь же представлены общие сведения о новом перспективном подходе к решению задач оптимизации на основе муравьиных 
алгоритмов. Особый интерес представляет тот факт, что в их основе лежит 
моделирование поведения колонии муравьев. 
Девятая глава позволяет взглянуть на алгоритмы, описанные в предыдущих главах, с иной точки зрения. В данной главе предполагается параллельная обработка данных, которая довольно редко освещается в литературе на русском языке. Данную главу можно также рассматривать как 
введение в параллельное программирование. Здесь приводится обзор            
общих понятий, связанных со структурой параллельных компьютерных 
систем, и сами параллельные алгоритмы решения некоторых из практических задач. 
В учебнике предложен широкий спектр алгоритмов, предназначенных 
для решения основных задач современной теории алгоритмов. Особенностью рассмотренных алгоритмов является возможность их применения для 
решения реальных задач. Рассмотренные алгоритмы могут быть применены в большом числе предметных областей и практических ситуаций. 

1. Общие сведения об алгоритмах 
 

9 

 
1. ОБЩИЕ  СВЕДЕНИЯ  ОБ  АЛГОРИТМАХ 
 
 
В основе любой компьютерной программы всегда лежит некоторый 
алгоритм, программа является изложением алгоритма на некотором языке, 
понятном вычислительной машине. 
Первым дошедшим до нас алгоритмом в его интуитивном понимании как конечной последовательности элементарных действий, решающих 
поставленную задачу, считается предложенный Евклидом в III веке до нашей эры алгоритм нахождения наибольшего общего делителя двух чисел.  
Отметим, что в течение длительного времени, вплоть до начала XX века, 
само слово «алгоритм» употреблялось в устойчивом сочетании «алгоритм  
Евклида». Для описания последовательности пошагового решения других 
математических задач чаще использовался термин «метод».  
Во всех сферах своей деятельности, в частности в сфере обработки 
информации, человек сталкивается с различными способами или методиками решения разнообразных задач. Они определяют порядок выполнения 
действий для получения желаемого результата. Можно трактовать это как 
первоначальное, или интуитивное, определение алгоритма. Таким образом, 
можно нестрого определить алгоритм как однозначно трактуемую процедуру решения задачи. Дополнительные требования о выполнении алгоритма 
за конечное время для любых входных данных приводят к следующему 
неформальному определению алгоритма. 
Алгоритм – это заданное на некотором языке конечное предписание, 
задающее конечную последовательность выполнимых и точно определенных элементарных операций для решения задачи, общее для класса возможных исходных данных. 
Пусть Dz – область (множество) исходных данных задачи Z, a R –  
множество возможных результатов, тогда можно говорить, что алгоритм 
осуществляет отображение Dz → R. Поскольку такое отображение может 
быть не полным, то вводятся следующие понятия: 
Алгоритм называется частичным алгоритмом, если результат может 
быть получен только для некоторых d ∈ Dz и полным алгоритмом, если 
алгоритм получает правильный результат для всех d ∈ Dz. 
Несмотря на усилия ученых, сегодня отсутствует одно исчерпывающе строгое определение понятия «алгоритм». Из разнообразных вариантов 
словесного определения алгоритма наиболее удачные, по мнению автора, 
принадлежат российским ученым А. Н. Колмогорову и А. А. Маркову. 

Алгоритмы и структуры данных (CDIO) 

10 

Определение по Колмогорову: алгоритм – это всякая система         
вычислений, выполняемых по строго определенным правилам, которая 
после какого-либо числа шагов заведомо приводит к решению поставленной задачи. 
Определение по Маркову: алгоритм – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных 
данных к искомому результату. 
Отметим, что различные определения алгоритма в явной или неявной форме постулируют следующий ряд общих требований: 
● алгоритм должен содержать конечное количество элементарно  
выполнимых предписаний, т. е. удовлетворять требованию конечности           
записи; 
● алгоритм должен выполнять конечное количество шагов при решении задачи, т. е. удовлетворять требованию конечности действий; 
● алгоритм должен быть единым для всех допустимых исходных 
данных, т. е. удовлетворять требованию универсальности; 
● алгоритм должен приводить к правильному по отношению               
к поставленной задаче решению, т. е. удовлетворять требованию правильности. 
Неудобства словесных определений связаны с проблемой однозначной 
трактовки терминов. В таких определениях должен быть, хотя бы неявно, 
указан исполнитель действий или предписаний. Алгоритм вычисления 
производной для полинома фиксированной степени вполне ясен тем, кто 
знаком с основами математического анализа, но для прочих он может оказаться совершенно непонятным. Это рассуждение заставляет указать также 
вычислительные возможности исполнителя, а именно уточнить, какие операции для него являются «элементарными». Другие трудности связаны           
с тем, что алгоритм заведомо существует, но его очень трудно описать              
в некоторой заранее заданной форме. Классический пример такой ситуации – алгоритм завязывания шнурков на ботинках «в бантик». Вы сможете 
дать только словесное описание этого алгоритма без использования иллюстраций? 
В связи с этим формально строгие определения понятия алгоритма 
связаны с введением специальных математических конструкций – формальных алгоритмических систем или моделей вычислений, каковыми         
являются машина Поста, машина Тьюринга, рекурсивно-вычислимые 
функции Черча, и постулированием тезиса об эквивалентности такого 
формализма и понятия «алгоритм». Несмотря на принципиально разные 
модели вычислений, использующиеся для определения термина «алгоритм», интересным результатом является формулировка гипотез об эквивалентности этих формальных определений в смысле их равномощности.