- •Структуры и алгоритмы обработки данных
- •Алгоритмы. Основные определения
- •От задачи к программе
- •Написание программы.
- •Типы данных, структуры данных и абстрактные типы данных
- •Указатели и курсоры
- •Время выполнения программ
- •Измерение времени выполнения программы
- •Степень (порядок) роста
- •Вычисление времени выполнения программ
- •Линейные абстрактные типы данных атд «Список»
- •Реализация списков посредством массивов
- •Реализация списков с помощью указателей
- •Атд «Стек»
- •Атд «Очередь»
- •Реализация очередей с помощью циклических массивов
- •Нелинейные абстрактные типы данных Деревья
- •Порядок узлов
- •Прямой, обратный и симметричный обходы дерева
- •Помеченные деревья и деревья выражений
- •Представление деревьев с помощью массивов
- •Специальные виды множеств атд “Дерево двоичного поиска”
- •Атд "Словарь", основанный
- •Представление ориентированных графов
- •Атд для ориентированных графов
- •Задача нахождения кратчайшего пути
- •Int **c, // массив стоимостей
- •Int *d) // массив кратчайших
- •Остовные деревья минимальной стоимости
- •Обход графов
- •Поиск в ширину
- •Поиск в глубину
- •Сортировка
- •Простые схемы сортировки Метод «пузырька»
- •Сортировка вставками
- •Быстрая сортировка
- •Пирамидальная сортировка
- •«Карманная» сортировка
- •Порядковые статистики
- •Методы разработки алгоритмов. Типы алгоритмов
- •Алгоритмы «разделяй и властвуй» (метод декомпозиции)
- •Баланс подзадач
- •Динамическое программирование
- •Перемножение нескольких матриц
- •Шаг 1: строение оптимальной расстановки скобок
- •Шаг 2: рекуррентное соотношение
- •Шаг 3: вычисление оптимальной стоимости
- •Void MatrixChainOrder(int n, // кол-во матриц
- •Int p[], // размеры матриц
- •Int **s) // оптимальное k
- •Шаг 4: построение оптимального решения
- •Int **s, // таблица, полученная
- •Int I, // индексы
- •Когда применимо динамическое программирование?
- •Оптимальность для подзадач
- •Перекрывающиеся подзадачи
- •«Жадные» алгоритмы
- •"Жадные" алгоритмы как эвристики
- •Когда применим жадный алгоритм?
- •Принцип жадного выбора
- •Оптимальность для подзадач
- •Поиск с возвратом
- •Функции выигрыша
- •Метод ветвей и границ
- •Структуры данных и алгоритмы для внешней памяти
- •Внешняя сортировка
- •Хранение данных в файлах
- •Простая организация данных
- •Хешированные файлы
- •Индексированные файлы
- •Содержание
- •Глава I. Линейные абстрактные типы данных 31
- •Глава II. Сортировка 108
Структуры и алгоритмы обработки данных
Процесс создания компьютерной программы для решения какой-либо практической задачи состоит из нескольких этапов: формализация и создание технического задания на исходную задачу; разработка алгоритма решения задачи; написание, отладка, тестирование и документирование программы; получение решения исходной задачи путем выполнения законченной программы. Поэтому в нашем курсе мы рассмотрим алгоритмы и структуры данных как строительные блоки создаваемых компьютерных программ.
Рекомендуемая литература:
-
Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. –М.: Изд. дом «Вильямс», 2000. – 384с.
-
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. –М.: МЦНМО (московский центр непрерывного математического образования), 2000. –960с.
-
Вирт Н. Алгоритмы + структуры данных = программы. М.: «Мир», 1985. –360с. Второе издание 2001.
Алгоритмы. Основные определения
В этой главе вкратце мы рассмотрим основные этапы создания эффективных программ.
-
От задачи к программе
На самом деле, написать программу, решающую какую-то конкретную задачу не так-то просто. Здесь математик и разработчик программного обеспечения могут столкнуться с рядом трудностей. Рассмотрим основные этапы написания программы и возникающие при этом трудности.
-
Разрешима ли задача? Возможно, поставленная задача не может быть решена с помощью компьютера. Например, разработка рецепта вечной молодости или сохранение мира во всем мире.
Даже если мы предполагаем, что наша задача может быть решена на компьютере, обычно для ее формального описания требуется огромное количество разнообразных параметров. И часто только в ходе дополнительных экспериментов можно найти интервалы изменения этих параметров.