Комбинаторные алгоритмы, Федоряева Т.И., 2011

Комбинаторные алгоритмы, Федоряева Т.И., 2011.

  Учебное пособие написано на основе курса "Комбинаторные алгоритмы", читаемого автором студентам факультета информационных технологий НГУ. Наряду с теоретическими знаниями даётся описание важнейших комбинаторных алгоритмов над объектами дискретной математики, приводится строгое обоснование рассматриваемых алгоритмов и детально изучается их асимптотическая сложность.
Пособие прежде всего ориентировано на студентов программистских специальностей, которым по роду их занятий приходится заниматься разработкой алгоритмов и анализом их вычислительной сложности. Изучение комбинаторных алгоритмов также будет полезно любому заинтересованному читателю для развития самостоятельных навыков по построению и анализу алгоритмов, для решения задач в области дискретной математики и применения методов дискретного анализа в своей профессиональной деятельности.




Машинные алгоритмы и их сложность.
Понятие алгоритма, подобно многим фундаментальным понятиям математики, является настолько интуитивно "понятным", насколько и сложным при его строгой формализации и скорее должно рассматриваться как неопределяемое. С неформальной точки зрения под алгоритмом часто понимается формально описанная вычислительная процедура, получающая исходные данные, называемые входными данными алгоритма, и выдающая результат вычислений на выход. Мы также ограничимся таким подходом, оставляя многочисленные известные формализации данного понятия вне рамок настоящего пособия.

Алгоритмы строятся для решения тех или иных вычислительных задач. Формулировка задачи описывает, каким требованиям должны удовлетворять входные и выходные данные, а алгоритм, решающий эту задачу, для каждой входной последовательности находит решение задачи, записываемое в выходные данные. Такой алгоритм, когда для каждого допустимого ввода результатом его работы является требуемый в задаче вывод, называют корректным. Некорректный алгоритм для некоторых входных данных может вообще не завершить свою работу или выдать выходные данные, отличные от требуемых в задаче.

Оглавление.
Предисловие.
Глава 1. Введение.
1. Машинные алгоритмы и их сложность.
2. Асимптотический формализм оценок времени работы алгоритмов.
3. Алгоритм нахождения n-факториального представления числа.
Глава 2. Генерация комбинаторных объектов.
1. Перестановки и алгоритмы их порождения.
1.1. Индекс перестановки.
1.2. Генерация перестановок в лексикографическом порядке.
1.3. Порождение перестановок через векторы инверсий.
1.4. Алгоритм Джонсона - Троттера генерации перестановок.
2. Подмножества конечного множества.
2.1. Генерация двоичных векторов и подмножеств.
2.2. Коды Грея и алгоритм их генерации.
3. Генерация сочетаний в лексикографическом порядке.
Глава 3. Генерация случайных комбинаторных объектов.
1. Алгоритм построения случайной перестановки.
2. Алгоритм генерации случайного подмножества и сочетания.
Глава 4. Разбиения чисел и множеств.
1. Упорядоченные и неупорядоченные разбиения числа n.
2. Генерация разбиений числа n в словарном порядке.
3. Разбиения конечного множества.
4. Генерация разбиений n-элементного множества.
Глава 5. Сортировка комбинаторных объектов.
1. Задача сортировки.
2. Нижние оценки сложности алгоритма сортировки сравнением.
3. Алгоритм сортировки вставками и оценки времени его работы.
4. Алгоритм пузырьковой сортировки и оценки времени его работы.
5. Алгоритм быстрой сортировки и оценки времени его работы.
6. Алгоритм пирамидальной сортировки и оценки его трудоёмкости.
7. Линейный алгоритм сортировки подсчётом Список литературы.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Комбинаторные алгоритмы, Федоряева Т.И., 2011 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




Хештеги: #учебник по программированию :: #программирование :: #Федоряева