- •Предназначено студентам очной формы обучения.
- •Введение
- •1. Оценки сложности алгоритмов
- •1.1. Определение понятия алгоритм
- •1.2. Оценка сложности алгоритмов
- •2. Линейные структуры данных
- •2.1. Методы организации и хранения линейных списков
- •2.2. Операции со списками при последовательном хранении
- •2.3. Операции со списками при связном хранении
- •2.4. Организация двусвязных списков
- •Задания для самоконтроля
- •2.5. Стеки и очереди
- •2.6. Сжатое и индексное хранение линейных списков
- •3. Сортировка и слияние
- •3.1. Пузырьковая сортировка
- •3.2. Сортировка вставкой
- •3.3. Сортировка посредством выбора
- •3.4. Сортировка квадратичной выборкой
- •3.5. Слияние списков
- •3.6. Сортировка списков путем слияния
- •3.7. Быстрая и распределяющая сортировки
- •4. Поиск
- •4.1. Последовательный поиск
- •4.2. Бинарный поиск
- •4.4. Методы вычисления адреса
- •4.5. Выбор в линейных списках
- •5. Рекурсия
- •6. Алгоритмы на графах и сетях
- •6.1. Исходные понятия
- •6.2. Матричные представления графов
- •6.3. Другие представления графов
- •6.4. Поиск в глубину как система исследования графа
- •6.5. Перебор цепей поиском в глубину
- •6.6. Взвешенные графы. Ориентированные графы
- •6.7. Нахождение фундаментального множества циклов
- •6.8. Выявление мостов и точек сочленений
- •6.9. Поиск в ширину как система исследования графа
- •6.10. Кратчайшие пути, ведущие от заданного узла X ко всем прочим
- •6.11. Алгоритм Дейкстры нахождения кратчайших путей во взвешенном графе
- •6.12. Улучшения алгоритма Дейкстры
- •6.13. Построение кратчайшего каркаса
- •6.14. Нахождение всевозможных кратчайших путей в графе
- •6.15. Потоковые задачи
- •6.16. Пример практической задачи на графах
- •7. Генераторы случайных и псевдослучайных последовательностей
- •7.1. Общая постановка задачи
- •7.3. Генератор случайных чисел, поставляемый с системой
- •7.4. Генератор с малым кодом
- •7.5. Генератор Парка-Миллера
- •7.6. Улучшенная версия генератора Парка-Миллера
- •7.7. Быстрый генератор для 32-битового представления целых и действительных чисел
- •7.8. Алгоритм л'Экюера, комбинирующий две последовательности
- •Оглавление
- •7. Генераторы случайных и псевдослучайных последовательностей 144
- •394026 Воронеж, Московский просп., 14
Оглавление
Предназначено студентам очной формы обучения. 2
Введение 3
1. ОЦЕНКИ СЛОЖНОСТИ АЛГОРИТМОВ 4
1.1. Определение понятия алгоритм 4
1.2. Оценка сложности алгоритмов 5
2. ЛИНЕЙНЫЕ СТРУКТУРЫ ДАННЫХ 12
2.1. Методы организации и хранения линейных списков 12
2.2. Операции со списками при последовательном хранении 14
2.3. Операции со списками при связном хранении 17
2.4. Организация двусвязных списков 19
2.5. Стеки и очереди 24
2.6. Сжатое и индексное хранение линейных списков 29
3. Сортировка и слияние 38
3.1. Пузырьковая сортировка 38
3.2. Сортировка вставкой 40
3.3. Сортировка посредством выбора 41
3.4. Сортировка квадратичной выборкой 43
3.5. Слияние списков 43
3.6. Сортировка списков путем слияния 45
3.7. Быстрая и распределяющая сортировки 48
4. ПОИСК 57
4.1. Последовательный поиск 57
4.2. Бинарный поиск 60
4.3. М-блочный поиск 61
4.4. Методы вычисления адреса 61
4.5. Выбор в линейных списках 64
5. РЕКУРСИЯ 70
6. АЛГОРИТМЫ НА ГРАФАХ И СЕТЯХ 82
6.1. Исходные понятия 82
6.2. Матричные представления графов 84
6.3. Другие представления графов 88
6.4. Поиск в глубину как система исследования графа 89
6.5. Перебор цепей поиском в глубину 94
6.6. Взвешенные графы. Ориентированные графы 97
6.7. Нахождение фундаментального множества циклов 98
6.8. Выявление мостов и точек сочленений 102
6.9. Поиск в ширину как система исследования графа 107
6.10. Кратчайшие пути, ведущие от заданного узла X ко всем прочим 111
6.11. Алгоритм Дейкстры нахождения кратчайших путей во взвешенном графе 113
6.12. Улучшения алгоритма Дейкстры 118
6.13. Построение кратчайшего каркаса 124
6.14. Нахождение всевозможных кратчайших путей в графе 128
6.15. Потоковые задачи 131
6.16. Пример практической задачи на графах 139
7. Генераторы случайных и псевдослучайных последовательностей 144
7.1. Общая постановка задачи 144
7.2. ЛП-последовательности 146
7.3. Генератор случайных чисел, поставляемый с системой 151
7.4. Генератор с малым кодом 152
7.5. Генератор Парка-Миллера 156
7.6. Улучшенная версия генератора Парка-Миллера 158
7.7. Быстрый генератор для 32-битового представления целых и действительных чисел 160
7.8. Алгоритм Л'Экюера, комбинирующий две последовательности 161
ЗАКЛЮЧЕНИЕ 165
В учебном пособии по дисциплинам «Методы программирования» и «Средства и методы программирования» рассмотрены вопросы построения эффективных алгоритмов и программ их реализации, включающие: 165
оценку сложности алгоритмов; 165
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 165
Учебное издание
Кащенко Генадий Алексеевич
Карпеев Дмитрий Олегович
МЕТОДЫ ПРОГРАММИРОВАНИЯ
В авторской редакции
Компьютерный набор Г.А. Кащенко
Подписано к изданию 31.10.2011.
Объем данных 1.95 Мб.
ФГБОУВПО «Воронежский государственный технический университет»