Учебное пособие. М.: НАУКА, ФИЗМАТЛИТ, 2007. – 376 с.
Разработка и анализ компьютерных алгоритмов — новая дисциплина,
возникшая на стыке дискретной математики, программирования и
классической теории алгоритмов, играющая важную роль в современных
компьютерных технологиях. Для большинства практически значимых
задач, решаемых сегодня с использованием компьютеров, существуют
разнообразные алгоритмы их решения. Этот факт приводит к тому, что
разработчики программных средств сталкиваются с проблемой выбора
наиболее рационального алгоритма решения поставленной задачи. В
данном учебном пособии изложены некоторые подходы к решению задачи
выбора на основе теории ресурсной эффективности.
Основной материал книги базируется на лекционных курсах «Математическая логика и теория алгоритмов» и «Разработка эффективных алгоритмов», читаемых автором, на протяжении ряда лет, в Московском государственном университете приборостроения и информатики (МГУПИ), а также на научных публикациях, посвященных исследованию и анализу вычислительных алгоритмов. Оглавление:
Элементы теории алгоритмов
Понятие и определения алгоритма
Требования к алгоритмам и их свойства
Временная и емкостная сложность алгоритма
Основные сложностные классы задач Модели вычислений и алгоритмические базисы
Введение в модели вычислений
Машина с произвольным доступом к памяти
Объектный и алгоритмический базисы
Модель вычислений для языка процедурного программирования с поддержкой механизма рекурсивного вызова Введение в теорию ресурсной эффективности компьютерных алгоритмов
Терминология и обозначения в теории ресурсной эффективности и асимптотическом анализе функций
Функции ресурсной эффективности компьютерных алгоритмов и их программных реализаций
Способы построения комплексных критериев оценки качества алгоритмов
Временные оценки и прогнозирование времён выполнения программных реализаций на основе функции трудоемкости Классификационные признаки и специальные классификации компьютерных алгоритмов и задач
Классы открытых и закрытых задач и теоретическая нижняя граница временной сложности
Классификация компьютерных алгоритмов на основе угловой меры асимптотического роста функций
Классификация компьютерных алгоритмов и задач по влиянию на трудоемкость особенностей входов
Классификация компьютерных алгоритмов по информационной и размерностной чувствительности
Классификация компьютерных алгоритмов по требованиям к дополнительной памяти
Классы статических и потоковых алгоритмов и их особенности Методика сравнительного анализа и рационального выбора компьютерных алгоритмов
Угловая мера близости ресурсных оценок
Методика сравнительного анализа алгоритмов по ресурсным функциям
Области эквивалентной ресурсной эффективности компьютерных алгоритмов Универсальные методы разработки алгоритмов
Метод декомпозиции задачи
Метод рекуррентных соотношений
Метод динамического программирования Методы разработки алгоритмов решения оптимизационных задач
Постановка и примеры задач целочисленного программирования
Методы разработки точных алгоритмов решения целочисленных задач
Эволюционные вычисления и генетические алгоритмы Анализ итерационных алгоритмов
Методика анализа основных алгоритмических конструкций
Анализ трудоемкости количественно-зависимых алгоритмов
Метод вероятностного анализа количественно-параметрических алгоритмов
Метод амортизационного анализа Анализ рекурсивных алгоритмов
Анализ вычислительной сложности рекурсивных алгоритмов, основанных на методе декомпозиции
Метод подсчета вершин дерева рекурсии
Метод рекуррентных соотношений Примеры эффективных алгоритмов для задач с фиксиро- ванной длиной входа
Обмен содержимого ячеек
Умножение комплексных чисел
Поиск максимума из трех чисел
Сортировка трех чисел по месту
Возведение числа в целую степень
Извлечение квадратного корня Ресурсно-эффективные алгоритмические решения для некоторых задач с переменной длиной входа
Поиск минимума и максимума в массиве
Организация счетчика в массиве
Определение областей применения для алгоритмов сортировки вставками и сортировки методом индексов
Выбор алгоритма умножения длинных целых чисел на основе анализа временной эффективности
Выбор рациональных алгоритмов поиска по ключу на основе анализа их информационной чувствительности Ресурсно-эффективные комбинированные алгоритмические решения
Комбинированный рекурсивно-итерационный алгоритм сортировки
Эффективный по трудоемкости комбинированный алгоритм решения классической задачи одномерной упаковки
Модификация алгоритма метода ветвей и границ для задачи коммивоя- жера на основе рационального использования доступного объема памяти
Рациональные ресурсно-адаптивные алгоритмические решения по ком- поненту формирования глобальной матрицы в системе конечно- элементного анализа
Рациональная организация аналитической базы данных с использованием алгоритмов решения задачи упаковки с динамической внутренней границей объема
Основной материал книги базируется на лекционных курсах «Математическая логика и теория алгоритмов» и «Разработка эффективных алгоритмов», читаемых автором, на протяжении ряда лет, в Московском государственном университете приборостроения и информатики (МГУПИ), а также на научных публикациях, посвященных исследованию и анализу вычислительных алгоритмов. Оглавление:
Элементы теории алгоритмов
Понятие и определения алгоритма
Требования к алгоритмам и их свойства
Временная и емкостная сложность алгоритма
Основные сложностные классы задач Модели вычислений и алгоритмические базисы
Введение в модели вычислений
Машина с произвольным доступом к памяти
Объектный и алгоритмический базисы
Модель вычислений для языка процедурного программирования с поддержкой механизма рекурсивного вызова Введение в теорию ресурсной эффективности компьютерных алгоритмов
Терминология и обозначения в теории ресурсной эффективности и асимптотическом анализе функций
Функции ресурсной эффективности компьютерных алгоритмов и их программных реализаций
Способы построения комплексных критериев оценки качества алгоритмов
Временные оценки и прогнозирование времён выполнения программных реализаций на основе функции трудоемкости Классификационные признаки и специальные классификации компьютерных алгоритмов и задач
Классы открытых и закрытых задач и теоретическая нижняя граница временной сложности
Классификация компьютерных алгоритмов на основе угловой меры асимптотического роста функций
Классификация компьютерных алгоритмов и задач по влиянию на трудоемкость особенностей входов
Классификация компьютерных алгоритмов по информационной и размерностной чувствительности
Классификация компьютерных алгоритмов по требованиям к дополнительной памяти
Классы статических и потоковых алгоритмов и их особенности Методика сравнительного анализа и рационального выбора компьютерных алгоритмов
Угловая мера близости ресурсных оценок
Методика сравнительного анализа алгоритмов по ресурсным функциям
Области эквивалентной ресурсной эффективности компьютерных алгоритмов Универсальные методы разработки алгоритмов
Метод декомпозиции задачи
Метод рекуррентных соотношений
Метод динамического программирования Методы разработки алгоритмов решения оптимизационных задач
Постановка и примеры задач целочисленного программирования
Методы разработки точных алгоритмов решения целочисленных задач
Эволюционные вычисления и генетические алгоритмы Анализ итерационных алгоритмов
Методика анализа основных алгоритмических конструкций
Анализ трудоемкости количественно-зависимых алгоритмов
Метод вероятностного анализа количественно-параметрических алгоритмов
Метод амортизационного анализа Анализ рекурсивных алгоритмов
Анализ вычислительной сложности рекурсивных алгоритмов, основанных на методе декомпозиции
Метод подсчета вершин дерева рекурсии
Метод рекуррентных соотношений Примеры эффективных алгоритмов для задач с фиксиро- ванной длиной входа
Обмен содержимого ячеек
Умножение комплексных чисел
Поиск максимума из трех чисел
Сортировка трех чисел по месту
Возведение числа в целую степень
Извлечение квадратного корня Ресурсно-эффективные алгоритмические решения для некоторых задач с переменной длиной входа
Поиск минимума и максимума в массиве
Организация счетчика в массиве
Определение областей применения для алгоритмов сортировки вставками и сортировки методом индексов
Выбор алгоритма умножения длинных целых чисел на основе анализа временной эффективности
Выбор рациональных алгоритмов поиска по ключу на основе анализа их информационной чувствительности Ресурсно-эффективные комбинированные алгоритмические решения
Комбинированный рекурсивно-итерационный алгоритм сортировки
Эффективный по трудоемкости комбинированный алгоритм решения классической задачи одномерной упаковки
Модификация алгоритма метода ветвей и границ для задачи коммивоя- жера на основе рационального использования доступного объема памяти
Рациональные ресурсно-адаптивные алгоритмические решения по ком- поненту формирования глобальной матрицы в системе конечно- элементного анализа
Рациональная организация аналитической базы данных с использованием алгоритмов решения задачи упаковки с динамической внутренней границей объема