Структуры и алгоритмы обработки данных: учеб. пособие/СПбГУАП. СПб.
,
2003. 172с. : ил.
© ГОУ ВПО «Санкт-Петербургский государственный университет аэрокосмического приборостроения», 2004
Авторы учебного пособия: Ключарев Александр Анатольевич, Матьяш Валерий Анатольевич и Щекин Сергей Валерьевич В данной методичке описаны основные принципы работы со структурами и построение алгоритмов. Также здесь представлены примеры на языке Pascal. Основные темы - хеширование, деревья, графы, списки, стек, очередь, дек, оценка сложности алгоритма, алгоритмы поиска в тексте, алгоритмы сортировки. В пособии приводятся описания различных форм организации данных в программах, методов обработки данных в различных классах задач и осуществляется их сравнительный анализ.
Учебное пособие предназначено для изучения теоретического материала дисциплин «Структуры и алгоритмы и обработки данных» и «Структуры и алгоритмы компьютерной обработки данных» студентами различных форм обучения, проходящих подготовку по специальностям 220400 и 351500 и полностью соответствует требованиям Государственных образовательных стандартов по этим специальностям.
В учебном пособии описаны структуры данных и алгоритмы, которые являются основой современного компьютерного программирования. Знание этих структур и алгоритмов позволяет осуществлять выбор наиболее оптимальных способов решения задач, возникающих при создании программного обеспечения различного назначения.
Учебное пособие состоит из трех разделов.
В первом разделе рассматриваются основные понятия алгоритмов и структур данных, а также основные подходы к анализу их сложности. Во втором разделе приводятся описания различных структур данных и основных операций над ними. Рассмотрены элементарные типы данных, линейные и нелинейные структуры, а также файлы. Третий раздел посвящен основным алгоритмам обработки рассмотренных ранее структур данных и анализу сложности этих алгоритмов. Приводятся различные алгоритмы поиска, сортировки, сжатия данных и алгоритмы на графах, а также обсуждаются методы разработки алгоритмов.
Материал учебного пособия базируется на следующих дисциплинах: «Программирование на языках высокого уровня», «Математическая логика и теория алгоритмов», «Дискретная математика», «Математическое обеспечение программных систем». Содержание:
Понятия алгоритма и структуры данных.
Анализ сложности и эффективности алгоритмов и структур данных.
Структуры данных.
Элементарные данные.
Данные числовых типов.
Данные целочисленного типа.
Данные вещественного типа.
Операции над данными числовых типов.
Данные символьного типа.
Данные логического типа.
Данные типа указатель.
Линейные структуры данных.
Массив.
Строка.
Запись.
Множество.
Таблица.
Линейные списки.
Линейный однонаправленный список.
Линейный двунаправленный список.
Циклические списки.
Циклический однонаправленный список.
Циклический двунаправленный список.
Разреженные матрицы.
Матрицы с математическим описанием местоположения элементов.
Матрицы со случайным расположением элементов
Стек.
Очередь.
Дек.
Нелинейные структуры данных.
Мультисписки.
Слоеные списки.
Графы.
Спецификация.
Реализация.
Деревья.
Общие понятия.
Обходы деревьев.
Спецификация двоичных деревьев.
Реализация.
Основные операции.
Файлы.
Организация.
B-деревья.
Представление файлов B-деревьями.
Основные операции.
Общая оценка B-деревьев.
Алгоритмы обработки данных.
NP-сложные и труднорешаемые задачи.
Методы разработки алгоритмов.
Метод декомпозиции.
Динамическое программирование.
Поиск с возвратом.
Метод ветвей и границ.
Метод альфа-бета отсечения.
Локальные и глобальные оптимальные решения.
Алгоритмы поиска.
Поиск в линейных структурах.
Последовательный (линейный) поиск.
Бинарный поиск.
Хеширование данных.
Функция хеширования.
Открытое хеширование.
Закрытое хеширование.
Реструктуризация хеш-таблиц.
Поиск по вторичным ключам.
Инвертированные индексы.
Битовые карты.
Использование деревьев в задачах поиска.
Упорядоченные деревья поиска.
Случайные деревья поиска.
Оптимальные деревья поиска.
Сбалансированные по высоте деревья поиска.
Поиск в тексте.
Прямой поиск.
Алгоритм Кнута, Мориса и Пратта.
Алгоритм Боуера и Мура.
Алгоритмы кодирования (сжатия) данных.
Основные виды сжатия.
Метод Хаффмана. Оптимальные префиксные коды.
Кодовые деревья.
Алгоритмы сортировки.
Основные виды сортировки.
Алгоритмы внутренней сортировки.
Сортировка подсчетом.
Сортировка простым включением.
Сортировка методом Шелла.
Сортировка простым извлечением.
Древесная сортировка.
Сортировка методом пузырька.
Быстрая сортировка (Хоара).
Сортировка слиянием.
Сортировка распределением.
. Сравнение алгоритмов внутренней сортировки.
Алгоритмы внешней сортировки.
Алгоритмы на графах.
Алгоритм определения циклов.
Алгоритмы обхода графа.
Поиск в глубину.
Поиск в ширину (волновой алгоритм).
Нахождение кратчайшего пути.
Алгоритм Дейкстры.
Алгоритм Флойда.
Переборные алгоритмы.
Нахождение минимального остовного дерева.
Алгоритм Прима.
Алгоритм Крускала.
2003. 172с. : ил.
© ГОУ ВПО «Санкт-Петербургский государственный университет аэрокосмического приборостроения», 2004
Авторы учебного пособия: Ключарев Александр Анатольевич, Матьяш Валерий Анатольевич и Щекин Сергей Валерьевич В данной методичке описаны основные принципы работы со структурами и построение алгоритмов. Также здесь представлены примеры на языке Pascal. Основные темы - хеширование, деревья, графы, списки, стек, очередь, дек, оценка сложности алгоритма, алгоритмы поиска в тексте, алгоритмы сортировки. В пособии приводятся описания различных форм организации данных в программах, методов обработки данных в различных классах задач и осуществляется их сравнительный анализ.
Учебное пособие предназначено для изучения теоретического материала дисциплин «Структуры и алгоритмы и обработки данных» и «Структуры и алгоритмы компьютерной обработки данных» студентами различных форм обучения, проходящих подготовку по специальностям 220400 и 351500 и полностью соответствует требованиям Государственных образовательных стандартов по этим специальностям.
В учебном пособии описаны структуры данных и алгоритмы, которые являются основой современного компьютерного программирования. Знание этих структур и алгоритмов позволяет осуществлять выбор наиболее оптимальных способов решения задач, возникающих при создании программного обеспечения различного назначения.
Учебное пособие состоит из трех разделов.
В первом разделе рассматриваются основные понятия алгоритмов и структур данных, а также основные подходы к анализу их сложности. Во втором разделе приводятся описания различных структур данных и основных операций над ними. Рассмотрены элементарные типы данных, линейные и нелинейные структуры, а также файлы. Третий раздел посвящен основным алгоритмам обработки рассмотренных ранее структур данных и анализу сложности этих алгоритмов. Приводятся различные алгоритмы поиска, сортировки, сжатия данных и алгоритмы на графах, а также обсуждаются методы разработки алгоритмов.
Материал учебного пособия базируется на следующих дисциплинах: «Программирование на языках высокого уровня», «Математическая логика и теория алгоритмов», «Дискретная математика», «Математическое обеспечение программных систем». Содержание:
Понятия алгоритма и структуры данных.
Анализ сложности и эффективности алгоритмов и структур данных.
Структуры данных.
Элементарные данные.
Данные числовых типов.
Данные целочисленного типа.
Данные вещественного типа.
Операции над данными числовых типов.
Данные символьного типа.
Данные логического типа.
Данные типа указатель.
Линейные структуры данных.
Массив.
Строка.
Запись.
Множество.
Таблица.
Линейные списки.
Линейный однонаправленный список.
Линейный двунаправленный список.
Циклические списки.
Циклический однонаправленный список.
Циклический двунаправленный список.
Разреженные матрицы.
Матрицы с математическим описанием местоположения элементов.
Матрицы со случайным расположением элементов
Стек.
Очередь.
Дек.
Нелинейные структуры данных.
Мультисписки.
Слоеные списки.
Графы.
Спецификация.
Реализация.
Деревья.
Общие понятия.
Обходы деревьев.
Спецификация двоичных деревьев.
Реализация.
Основные операции.
Файлы.
Организация.
B-деревья.
Представление файлов B-деревьями.
Основные операции.
Общая оценка B-деревьев.
Алгоритмы обработки данных.
NP-сложные и труднорешаемые задачи.
Методы разработки алгоритмов.
Метод декомпозиции.
Динамическое программирование.
Поиск с возвратом.
Метод ветвей и границ.
Метод альфа-бета отсечения.
Локальные и глобальные оптимальные решения.
Алгоритмы поиска.
Поиск в линейных структурах.
Последовательный (линейный) поиск.
Бинарный поиск.
Хеширование данных.
Функция хеширования.
Открытое хеширование.
Закрытое хеширование.
Реструктуризация хеш-таблиц.
Поиск по вторичным ключам.
Инвертированные индексы.
Битовые карты.
Использование деревьев в задачах поиска.
Упорядоченные деревья поиска.
Случайные деревья поиска.
Оптимальные деревья поиска.
Сбалансированные по высоте деревья поиска.
Поиск в тексте.
Прямой поиск.
Алгоритм Кнута, Мориса и Пратта.
Алгоритм Боуера и Мура.
Алгоритмы кодирования (сжатия) данных.
Основные виды сжатия.
Метод Хаффмана. Оптимальные префиксные коды.
Кодовые деревья.
Алгоритмы сортировки.
Основные виды сортировки.
Алгоритмы внутренней сортировки.
Сортировка подсчетом.
Сортировка простым включением.
Сортировка методом Шелла.
Сортировка простым извлечением.
Древесная сортировка.
Сортировка методом пузырька.
Быстрая сортировка (Хоара).
Сортировка слиянием.
Сортировка распределением.
. Сравнение алгоритмов внутренней сортировки.
Алгоритмы внешней сортировки.
Алгоритмы на графах.
Алгоритм определения циклов.
Алгоритмы обхода графа.
Поиск в глубину.
Поиск в ширину (волновой алгоритм).
Нахождение кратчайшего пути.
Алгоритм Дейкстры.
Алгоритм Флойда.
Переборные алгоритмы.
Нахождение минимального остовного дерева.
Алгоритм Прима.
Алгоритм Крускала.