Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

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

Покупка
Основная коллекция
Артикул: 874930.01.99
Доступ онлайн
500 ₽
В корзину
В учебном пособии кратко изложены базовые понятия теории алгоритмов, приведены методы оценки временной и пространственной сложности алгоритмов, рассмотрены основные структуры данных, описаны способы задания графов и принципы параллельной обработки данных. Материал сопровождается примерами программных реализаций. Учебное пособие рекомендовано для использования студентами, обучающимися по направлению 09.03.01 «Информатика и вычислительная техника», профиль «Разработка доверенного системного и прикладного программного обеспечения» при изучении дисциплины «Алгоритмы и структуры данных».
Истратова, Е. Е. Алгоритмы и структуры данных : учебное пособие / Е. Е. Истратова, И. Н. Томилов, А. А. Якименко. - Новосибирск : Изд-во НГТУ, 2025. - 68 с. - ISBN 978-5-7782-5502-9. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2244205 (дата обращения: 19.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
Министерство науки и высшего образования Российской Федерации 
Федеральное государственное бюджетное образовательное учреждение высшего образования 
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ  
 
 
 
Е. Е. ИСТРАТОВА, И. Н. ТОМИЛОВ,  
А. А. ЯКИМЕНКО 
 
 
 
 
 
АЛГОРИТМЫ  
И СТРУКТУРЫ ДАННЫХ 
 
 
Утверждено  
Редакционно-издательским советом университета 
в качестве учебного пособия 
 
 
 
 
 
 
 
 
 
 
 
 
 
НОВОСИБИРСК 
2025 


УДК 004.422.63(075.8) 
  И913 
 
 
 
Рецензенты: 
д-р техн. наук, профессор кафедры АСУ НГТУ М. Г. Гриф 
канд. техн. наук, доцент кафедры «Проектирование и сертификация 
авиационной техники» ФГБОУ ВО «МАИ» Д. Н. Левин 
 
Работа подготовлена на кафедре автоматизированных  
систем управления  и кафедре вычислительной техники 
 
 
Истратова Е. Е. 
И913  
Алгоритмы и структуры данных : учебное пособие / 
Е. Е. Истратова, И. Н. Томилов, А. А. Якименко. – Новосибирск : 
Изд-во НГТУ, 2025. – 68 с. 
ISBN 978-5-7782-5502-9 
В учебном пособии кратко изложены базовые понятия теории алгоритмов, приведены методы оценки временной и пространственной сложности алгоритмов, рассмотрены основные структуры данных, описаны 
способы задания графов и принципы параллельной обработки данных. 
Материал сопровождается примерами программных реализаций. 
Учебное пособие рекомендовано для использования студентами, 
обучающимися по направлению 09.03.01 «Информатика и вычислительная техника», профиль «Разработка доверенного системного и прикладного программного обеспечения» при изучении дисциплины «Алгоритмы и структуры данных». 
 
 
УДК 004.422.63(075.8) 
 
 
ISBN 978-5-7782-5502-9 
© Истратова Е. Е., Томилов И. Н.,  
 
    Якименко А. А., 2025 
 
© Новосибирский государственный 
 
    технический университет, 2025


 
 
 
 
 
 
 
ВВЕДЕНИЕ 
В учебном пособии описаны алгоритмы и структуры данных, которые являются основой современного компьютерного программирования. Знание этих структур и алгоритмов позволяет осуществлять выбор 
оптимальных способов решения задач, возникающих при создании 
программного обеспечения различного назначения. Это связано с тем, 
что первичная задача программиста заключается в выборе не только 
решения о форме представления данных, но и самих алгоритмов, применяемых к этим данным. Лишь затем выбранная структура программы и данных реализуется на конкретном языке программирования.  
В связи с этим знание классических методов и приемов обработки данных позволяет избежать ошибок, которые могут возникать при чисто 
интуитивной разработке программного обеспечения. 
Учебное пособие содержит шесть разделов и охватывает такие темы, как понятие алгоритма и структуры данных, способы организации 
списков, алгоритмы сортировки и поиска, способы задания и нахождения кратчайших путей в графах, принципы параллельной обработки 
данных. Более подробное описание алгоритмов и структур данных,  
а также основные подходы к анализу их сложности и примеры их использования можно найти в рекомендуемой литературе. 
 
 


 
 
 
 
 
 
1. ПОНЯТИЕ АЛГОРИТМА  
И СТРУКТУРЫ ДАННЫХ 
1.1. ПОНЯТИЕ И СВОЙСТВА АЛГОРИТМОВ 
Алгоритм – это набор конечного числа правил, задающих последовательность выполнения операций для решения задачи определенного 
типа. Ключевыми свойствами алгоритмов являются следующие. 
1. Дискретность. Алгоритм должен представлять процесс решения 
задачи как упорядоченное выполнение некоторых простых шагов. При 
этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, т. е. преобразование исходных данных в результат осуществляется во времени дискретно. 
2. Детерминированность (определенность). В каждый момент времени следующий шаг работы однозначно определяется состоянием  
системы. Таким образом, алгоритм выдает один и тот же результат  
(ответ) для одних и тех же исходных данных. 
3. Понятность. Алгоритм должен включать в себя только те команды, которые доступны исполнителю и входят в его систему команд. 
4. Массовость (универсальность). Алгоритм должен быть применим к разным наборам начальных данных. 
5. Результативность. Завершением алгоритма является получение 
определенных результатов или выдача сообщения о невозможности 
получения результата. 
6. Корректность. Для любого набора данных должен быть правильный результат. 
1.2. ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ АЛГОРИТМОВ 
Вычислительной сложностью называют количество элементарных 
операций, затрачиваемых алгоритмом для решения конкретной задачи. 
Сложность зависит не только от размерности входных данных, но и от 


самих данных. Очевидно, что чем сложнее алгоритм в вычислительном 
плане, тем больше времени и вычислительных ресурсов потребует его 
выполнение. 
Различают временну́ю и пространственную сложность. Временная 
сложность определяет время, требуемое на решение задачи заданной 
размерности с помощью определенного алгоритма. Пространственная 
сложность определяет количество требуемых ресурсов (памяти) при 
тех же условиях. 
Каждый вычислительный алгоритм может быть отнесен к одному 
из двух классов сложности. В данном случае это множество задач, для 
решения которых известны алгоритмы, схожие по трудоемкости.  
В классе P вычислительные затраты линейно растут с увеличением 
размерности. Например, время, требуемое на уборку придомовой территории, прямо пропорционально площади. Если ее увеличить вдвое, 
то и временные затраты возрастут в два раза. Класс NP включает в себя 
задачи, решаемые только с помощью алгоритмов, сложность которых 
экспоненциально зависит от размерности данных. Поэтому они, как правило, неэффективны при работе с большими множествами. Примером 
является задача поиска выхода из лабиринта, временные затраты на которую экспоненциально растут с увеличением числа разветвлений. 
Вычислительная временная сложность (time complexity) – это максимальное возможное количество выполненных алгоритмом элементарных операций (зависимость функции от размера входных данных). 
Вычислительная емкостная сложность (space complexity) – это максимальный возможный размер занятой алгоритмом дополнительной 
памяти (зависимость функции от размера входных данных). Причем эта 
функция возвращает максимум операций/памяти на всех входах такого 
размера, т. е. для худшего случая. Для оценки сложности алгоритмов 
обычно пользуются так называемой О-нотацией (например, O(n2) – 
произносится как «о от эн квадрат»).  
1.3. ПОНЯТИЕ СТРУКТУРЫ ДАННЫХ 
Перед написанием программы важно правильно выбрать структуру 
данных, обеспечивающую эффективное решение задачи. Одни и те же 
данные можно сохранить в структурах, требующих различного объема 
памяти, а алгоритмы работы с каждой структурой могут иметь различную эффективность. Если выбрана наиболее подходящая структура, то 


разработка алгоритма уже не вызовет затруднений, а сам алгоритм решения будет оптимален и по объему занимаемой памяти, и по времени 
работы алгоритма. 
Структуры данных определяют объекты, организованные определенным образом, и операции, которые можно выполнять над объектами. Доступ к объектам и все операции с ними осуществляются только 
через интерфейс. Интерфейс отделяет реализацию структуры данных 
от клиента и является непрозрачным для 
клиента. Структура данных может быть 
представлена как некий черный ящик  
с интерфейсами. Примеры распространенных структур данных: измерения 
температуры за определенный период, 
оценки студента за семестр и др. 
Структуры данных – это совокупность 
логически связанных элементов данных и 
отношений между ними. Под отношениями между данными понимают функциональные связи между ними и указатели на 
то, где находятся эти данные. 
Элемент отношений – это совокупность всех связей элемента с другими элементами данных рассматриваемой структуры. Как бы сложна ни была структура 
данных, в конечном итоге она состоит из 
простых данных. Последовательность переходов от логической организации к физической показана на рис. 1.1. 
Классификация структур данных будет рассмотрена ниже. 
1.4. КЛАССИФИКАЦИЯ СТРУКТУР ДАННЫХ 
Структуры данных могут быть классифицированы в зависимости 
от отношений между элементами и делятся на линейные, иерархические, сетевые и табличные. 
Линейная структура данных – это набор упорядоченных по порядковому номеру элементов (рис. 1.2). 
 
Рис. 1.1. Взаимодействие логической и физической структур данных 


Рис. 1.2. Пример линейной структуры данных 
К линейным структурам данных относятся следующие элементы: 
1) массив; 
2) список; 
3) связный список; 
4) стек; 
5) очередь; 
6) хеш-таблица. 
В нелинейных структурах данных порядок элементов задается определенными правилами. К нелинейным структурам относятся иерархические (древовидные) и графовые структуры. 
Иерархические структуры (рис. 1.3) содержат деревья, которые,  
в свою очередь, включают узлы и ребра. Первый элемент на первом 
уровне называется корнем. Далее элементы соединяются ребрами, при 
этом каждый из элементов находится на определенном уровне (их может быть несколько на один уровень). 
 
 
Рис. 1.3. Пример иерархической структуры данных 
К иерархическим структурам данных относятся следующие элементы: 
1) двоичные деревья; 
2) n-арные деревья; 
3) иерархический список. 


Доступ онлайн
500 ₽
В корзину