Официальный подлинный алгоритм примечание математическая теория и реализация программирования навыки
Вес товара: ~0.7 кг. Указан усредненный вес, который может отличаться от фактического. Не включен в цену, оплачивается при получении.
Описание товара
Amatalize   запись
Глава 1. Сортировка 1.
1.1 Сравнительная сортировка.................................................................................................................. 1
1.1.1 Гребенчатая сортировка......................................................................................................... 2
1.1.2 Куча................................................................................................................. 4
1.1.3 Сортировка слиянием............................................................................................... 5
1.1.4 Быстрая сортировка............................................................................................................... 8
1.1.5 Интроспекционная сортировка.................................................................................................. 10
1.1.6 Тимсорт.................................................................................................................................. 11
1.2 Сортировка без сравнения............................................................................................................... 14
1.2.1 Сортировка ковшами.................................................................................................. 14
1.2.2 Поразрядная сортировка............................................................................................... 15
1.3 Резюме.................................................................................................................................. 16
Глава 2 Хэши 17
2.1 Основные концепции и реализация.................................................................................................. 17
2.1.1 Хэш-функция.................................................................................................. 17
2.1.2 Хэш-таблица............................................................................................................... 19
2.2 Применение хеширования.................................................................................................. 20
2.2.1 Поиск по сходству.................................................................................................. 20
2.2.2 Информационная безопасность.................................................................................................. 23
2.2.3 Биткойн............................................................................................................................... 25
2.2.4 Балансировка нагрузки.................................................................................................. 26
Глава 3 Динамическое программирование и алгоритмы аппроксимации 29
3.1 Основные понятия............................................................................................................................. 29
3.1.1 Динамическое программирование.................................................................................................. 29
3.1.2 Вычислительная сложность.................................................................................................. 30
3.2 Редактирование расстояния струны.............................................................................. 30
3.2.1 Описание проблемы.................................................................................................. 31
3.2.2 Алгоритм динамического программирования........................................................................................ 33
3.2.3 Оптимизация подвижного состава.................................................................................. 35
3.2.4 Верхний предел.............................................................................................................. 36
3.2.5 Возврат решения............................................................................................ 37
3.2.6 Алгоритм «разделяй и властвуй»............................................................................................ 38
3.2.7 Редактирование расстояния для нескольких строк............................................................................ 41
3.3 Подмножества и проблемы........................................................................................................ 43
3.3.1 Описание проблемы.................................................................................................. 43
3.3.2 Алгоритм динамического программирования для задачи суммы подмножества................................................. 43
3.3.3 Задача оптимизации........................................................................................................ 44
3.3.4 Советы по использованию подвижных массивов.................................................................................. 45
3.3.5 Жадный алгоритм............................................................................................................ 46
3.3.6 Расслабленное динамическое программирование............................................................................................ 47
3.3.7 Сопутствующие вопросы.................................................................................................. 48
3.4 Задача коммивояжера............................................................................................................ 50
3.4.1 Описание проблемы.................................................................................................. 50
3.4.2 Алгоритм динамического программирования........................................................................................ 52
3.4.3 Задача с одним ударом............................................................................................ 52
3.4.4 Алгоритм Кристофидеса.............................................................................................. 54
3.4.5 Алгоритм Лина-Кернигана............................................................................................ 55
3.5 Резюме................................................................................................................................. 58
Глава 4. Метод исключения Гаусса 59
4.1 Введение в проблему.................................................................................................................. 59
4.2 Основы матричного программирования.................................................................................................. 60
4.3 Тригонометрические уравнения.................................................................................................................. 62
4.3.1 Треугольная матрица............................................................................................................... 62
4.3.2 Хранение треугольной матрицы.................................................................................................. 63
4.3.3 Решение тригонометрических уравнений................................................................................................. 64
4.4 Метод исключения Гаусса............................................................................................................ 66
4.4.1 Обзор алгоритма.................................................................................................. 66
4.4.2 Гауссово преобразование............................................................................................................ 68
4.4.3 Разложение LU............................................................................................................... 69
4.4.4 Разложение Холецкого............................................................................................ 70
4.5 Выбор поворота.................................................................................................................. 71
4.5.1 Выбор сводного списка............................................................................................ 71
4.5.2 Выбор всех поворотов........................................................................................ 73
4.5.3 Поворотный элемент и сумма расчета.................................................................................. 74
4.6 Основы программирования с разреженной матрицей............................................................................75
4.6.1 Разреженные векторы............................................................................................ 76
4.6.2 Разреженная матрица............................................................................................................... 79
4.7 Разреженное LU-разложение........................................................................................................ 82
4.7.1 Алгоритм Марковица................................................................................................. 82
4.7.2 Алгоритм минимальной степени.............................................................................................. 83
Глава 5 Теория графов и линейное программирование 86
5.1 Основы линейного программирования............................................................................................................ 86
5.1.1 Метод исключения Фурье-Моцкина.................................................................... 89
5.1.2 База.................................................................................................................................. 91
5.1.3 Симплексный метод.................................................................................................. 93
5.1.4 Двойственность.................................................................................................................. 95
5.2 Полная одномодовая матрица............................................................................................................ 98
5.2.1 Матрица корреляции.................................................................................................. 98
5.2.2 Полная одномодовая матрица............................................................................................................ 99
5.2.3 Полная одномодовая теория матриц и графов............................................................................ 100
5.2.4 Полное одномодовое матричное и линейное программирование............................................................ 103
5.3 Классические задачи теории графов........................................................................................ 104
5.3.1 Проблема короткого замыкания с одним источником.................................................................... 104
5.3.2 Задачи максимального соответствия и минимального покрытия двудольных графов.................................................... 106
5.3.3 Проблемы с максимальным расходом и минимальным срезом............................................ 108
5.4 Дополнительная литература............................................................................................................... 109
5.4.1 Пошаговое линейное программирование............................................................................................ 109
5.4.2 Позитивное полуопределенное программирование........................................................................................................ 111
Глава 6. Неограниченная оптимизация 113
6.1 Максимальное значение унимодальной функции................................................................................................. 114
6.1.1 Правило третей.............................................................................................................................. 115
6.1.2 Метод бисекции.................................................................................................................. 115
6.1.3 Метод золотого сечения.................................................................................................. 116
6.1.4 Резюме............................................................................................................................... 117
6.2 Метод безпроизводной оптимизации............................................................................................ 118
6.2.1 Метод поиска по образцу................................................................................................. 118
6.2.2 Метод координатного спуска.................................................................................................. 119
6.2.3 Метод агентской модели.................................................................................................. 120
6.3 Метод производной оптимизации.................................................................................................. 121
6.3.1 Поиск линии............................................................................................................... 122
6.3.2 Метод градиентного спуска............................................................................................................ 123
6.3.3 Метод сопряженных градиентов............................................................................................ 124
6.3.4 Метод Ньютона............................................................................................................... 127
6.3.5 Квазиньютоновский метод............................................................................................................ 128
6.4 Наименьшие квадраты.................................................................................................................. 132
6.4.1 Линейный метод наименьших квадратов........................................................................................ 133
6.4.2 Нелинейный метод наименьших квадратов........................................................................................ 133
Глава 7. Итерационные методы 136
7.1 Итерационный метод для решения линейных уравнений........................................................................................ 136
7.1.1 Метод итерации устойчивого формата первого порядка............................................................................ 136
7.1.2 Алгоритм подпространства Крылова............................................................................................ 142
7.1.3 Метод безусловной оптимизации............................................................................ 147
7.2 Итерационный метод для нелинейных уравнений.................................................................... 147
7.2.1 Итерация с фиксированной точкой............................................................................................................ 148
7.2.2 Итерация Ньютона-Рафсона............................................................................................ 149
7.2.3 Метод безусловной оптимизации............................................................................ 152
Глава 8. Интерполяция и аппроксимация 153
8.1 Интерполяция............................................................................................................................... 153
8.1.1 Общие алгоритмы интерполяции............................................................................................ 154
8.1.2 Применение интерполяции............................................................................................ 158
8.2 Монтаж................................................................................................................................................. 163
8.2.1 Общие алгоритмы подгонки........................................................................................ 164
8.2.2 Применение фитинга............................................................................................................... 166
Ссылка 169
Введение
В этой книге представлены несколько распространенных алгоритмов, включая базовые алгоритмы, такие как сортировка и хеширование, а также методы численных вычислений, такие как неограниченная оптимизация, интерполяция и подгонка. Представляя алгоритмы, эта книга сочетает в себе собственное понимание математической основы и сценариев применения, чтобы помочь читателям понять основные идеи алгоритмов. Эта книга максимально избегает экзаменационных объяснений и стремится пробудить интерес читателей и расширить их кругозор. Например, при знакомстве с хешированием объясняется, как применять идеи алгоритмов хеширования для решения множества практических задач, таких как поиск по сходству и балансировка нагрузки. Например, при представлении метода исключения Гаусса он объясняет соответствующую математическую теорию и конкретные методы реализации программирования, а также применяет его для решения крупномасштабных разреженных линейных уравнений и т. д. Эта книга предназначена для читателей, которые имеют определенные знания в области высшей математики и языков программирования и предварительное понимание алгоритмов, включая студентов колледжей и университетов, программистов, аналитиков алгоритмов и дизайнеров и т. д. Целью книги является помочь читателям глубже изучить алгоритмы и понять теоретическую основу и примеры применения, связанные с алгоритмами.
раньше слова
Название этой книги“Примечания к алгоритму”, в основном основанный на опыте автора по изучению алгоритмов во время учебы в Китайской академии наук, и может быть использован в качестве дополнения к существующим учебникам по алгоритмам. В этой книге обсуждаются несколько тем, связанных с компьютерными алгоритмами. Представляя алгоритмы, он сочетает в себе собственное понимание математической основы и сценариев применения, чтобы помочь читателям понять основные идеи алгоритмов. Чтение этой книги требует определенной математической базы и алгоритмической основы.
Многие классические учебники по алгоритмам подробно описывают различные аспекты алгоритмов, но, охватывая широкий круг тем, они неизбежно упускают из виду многие детали.Например, какие алгоритмы действительно стоит применять для решения практических задач, какие варианты алгоритмов достойны нашего понимания, какое математическое теоретическое обеспечение лежит в основе алгоритмов и т. д.
Всего в книге 8 глав.Помимо объяснения базовых знаний, каждая глава также отвечает на множество сопутствующих интересных вопросов.
? Сортировка. Существует множество видов алгоритмов сортировки.Существуют библиотечные функции, обеспечивающие алгоритмы сортировки в более популярных языках программирования. Вызвать эти библиотечные функции напрямую очень просто.Но почему алгоритмы, которые они используют, эффективны и каковы различия между этими алгоритмами и некоторыми классическими алгоритмами сортировки?
? Хеш: При объяснении алгоритмов хеширования мы обычно сосредотачиваемся на роли хэш-функций и различных методах реализации хеш-таблиц.Но при применении хеш-функций для решения различных задач наиболее изобретательной частью является разработка хеш-функции.Чем интересны формы хэш-функций для задач в разных областях?
? Динамическое программирование и алгоритмы аппроксимации: Обычно эти два типа алгоритмов не обсуждаются вместе.Как они будут дополнять друг друга, сталкиваясь с проблемами разной сложности?
? Метод исключения Гаусса. Основной процесс алгоритма очень прост, но на практике он далеко не так прост.Как сохранить стабильность вычислений?Как решить проблему вычислительной эффективности разреженных матриц?
? Теория графов и линейное программирование: Многие задачи теории графов можно решить с помощью линейного программирования.Некоторые классические выводы теории графов на самом деле можно объяснить с помощью связанных с ними теорем линейного программирования.Как можно использовать линейное программирование как более общий инструмент для решения задач теории графов?
? Неограниченная оптимизация: Неограниченная оптимизация в основном используется для решения проблемы максимального или минимального значения функции.Почему эти широко используемые методы работают?Какая между ними разница?
? Итеративный метод: Каковы распространенные итеративные алгоритмы?Почему они работают?
? Интерполяция и подгонка: В чем идея интерполяции и подгонки?Каковы сходства и различия?Как применить это к обработке изображений?
Читатели обнаружат, что в этой книге не только указано, какие алгоритмы могут решить проблему, но также указано, какие алгоритмы могут решить проблему лучше.Это поможет нам глубже понять алгоритм.
Ввиду ограниченного уровня автора в книге неизбежно присутствуют ошибки и неточности.Критика и поправки читателей приветствуются.
Дяо Жуй, Се Ян
июль 2016 г.