Опубликовано

Встречайте: “Методы и алгоритмы анализа данных для веб-разработки и маркетинга”

Методы и алгоритмы анализа данных для веб-разработки и маркетинга

Рассмотрены основные методы и алгоритмы анализа данных для веб-разработки и маркетинга, в том числе методы декомпозиции, визуализации, функционально-стоимостного анализа, эконометрический метод и другие. Приведены алгоритмы  семантического анализа текстов, ранжирования смысловых приоритетов и отбора ключевых фраз, алгоритмы оценки потребительской лояльности, в том числе алгоритм оценки тональности текстов, алгоритм анализа качества веб-интерфейсов Mobile First и другие. Рассмотрены задачи прогнозирования коммерческого спроса, анализа потребительского доверия к бренду, сокращения рекламных расходов, а также комплексного анализа данных деятельности компании. Описан общедоступный инструментарий, такой как Яндекс.Подбор слов, Яндекс.Метрика, ExportBase, Яндекс.Поиск, ГлавРед, EditPlus, Антиплагиат, Гугл.Таблицы, MS Excel и Google Mobile Test.

Электронный архив на сайте издательства содержит цветные рисунки, примеры HTML-документов, скриптов и дополнительные pdf-файлы.

Для начинающих аналитиков данных

Последовательное изложение методов и алгоритмов анализа данных от простого к сложному на доступных для новичков примерах

Многие задаются вопросом: как использовать статистику о поведении пользователей для принятия решений при разработке и сопровождении коммерческих продуктов? Не важно, что в рассмотрении — сайт или моб

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

Новичкам в веб-аналитике предлагается простой и понятный путь от теории к практике для освоения методов и алгоритмов анализа данных, начиная с самых доступных и заканчивая комплексными научными и маркетинговыми исследованиями.

В книге приводятся практические решения комплексных аналитических задач с помощью общедоступного инструментария:

  • Яндекс.Подбор слов (статистика потребительских поисковых запросов);
  • Яндекс.Метрика (статистика и аналитика по сайту компании);
  • ExportBase (доступные базы данных о российских компаниях);
  • Яндекс.Поиск (результаты ранжирования по тематике сайта);
  • EditPlus или аналог (редактор кода для исполнения решений с графиками);
  • ГлавРед (исправление текста);
  • Антиплагиат (уникальность);
  • Гугл.Таблицы или MS Excel (редактор таблиц для обработки данных);
  • Google Mobile Test (анализ веб-сайта на мобилопригодность и индекс Mobilefirst);
    и другие.

    Прикладные методы и алгоритмы анализа данных:

    • анализ и прогноз спроса на товары и услуги на основе статистики;
    • A/B-тестирование гипотез — сравнение и аналитический выбор по заданным мотивационным факторам покупки: цена и выгода;
    • семантический анализ персональных данных пользователей для отбора коммерческих интересов. Алгоритм анализа тональности текстов;
    • решение задачи минимизации рекламных расходов с помощью визуального сопоставления рекламных каналов и аналитического отбора по условиям;
    • оценка лояльности потребителей к бренду с применением опросов по метрике NPS.

     

    Методы принятия решения и повышения эффективности компании:

    • методика TD ABC для расчета затрат по операциям в условиях ограниченных ресурсов компании;
    • имитационное моделирование процессов обработки заявок в расчетно-кассовом и дистанционном банковском обслуживании клиентов для оценки себестоимости транзакций и влияния риска отказов на прибыль компании;
    • качественная оценка состояния компании (стартапа) для принятия решений по стратегическому управлению и инвестированию;
    • факторный анализ для оптимального выбора на основе заданных признаков сравнения;
    • комплексный анализ данных компании методом декомпозиции, фильтрации и анализа статистики поисковых запросов из Яндекс.Метрики и поведения пользователей на сайте компании.

Книгу “Методы и алгоритмы анализа данных для веб-разработки и маркетинга” можно купить со скидкой в интернет-магазине издательства “БХВ“.

Предисловие…………………………………………………………………………………………… 11

Глава 1. Введение в анализ данных……………………………………………………….. 14

Термины и определения…………………………………………………………………………………………………………….. 14

Взаимосвязь сущностей исследования…………………………………………………………………………………….. 17

Постановка и условия задачи…………………………………………………………………………………………… 19

Сбор данных без потерь……………………………………………………………………………………………………. 20

Гипотеза: построение, подтверждение или опровержение……………………………………………. 20

О выборе методов и алгоритмов для решения задачи……………………………………………………. 21

Определение алгоритма…………………………………………………………………………………………………….. 22

Проведение эксперимента…………………………………………………………………………………………………. 24

Анализ экспериментальных данных………………………………………………………………………………… 25

Рекомендации по результатам анализа…………………………………………………………………………… 25

Об апробации результатов исследования……………………………………………………………………….. 26

О логике продуктового мышления……………………………………………………………………………………. 26

Подход к факторному анализу в исследовании……………………………………………………………………… 28

Апробация как часть технологической фазы исследования………………………………………………….. 29

Сбор, хранение и воспроизведение данных……………………………………………………………………………. 29

Рекомендация вести календарь исследования………………………………………………………………… 30

Транспорт данных экспортом из редактора таблиц в веб-приложение……………………….. 31

Таблица статистики из облака с выводом на график……………………………………………………… 31

Формирование личного профиля из компетенций специалиста……………………………………………. 40

Организация процесса работы аналитика………………………………………………………………………………. 42

Сроки и значимость аналитического исследования………………………………………………………………. 45

Комплексный подход к аналитическому исследованию……………………………………………………….. 46

Глава 2. Декомпозиция для исследования сложной системы………………….. 47

Факторинг в программировании………………………………………………………………………………………………. 49

Фильтры поиска недвижимости для упрощения факторного отбора……………………………. 49

Задача о разборчивой невесте………………………………………………………………………………………….. 51

Постановка задачи……………………………………………………………………………………………………. 51

Условия задачи…………………………………………………………………………………………………………. 51

Стратегия «бери или уходи»……………………………………………………………………………………………… 52

Объектно-ориентированный подход к методу декомпозиции……………………………………………….. 52

Стандартизация кода по методологии БЭМ…………………………………………………………………………… 54

Философия БЭМ…………………………………………………………………………………………………………………. 55

Что в целом улучшает метод декомпозиции и БЭМ в работе веб-разработчиков?…….. 59

Рефакторинг программного кода……………………………………………………………………………………………… 61

Чем отличается стандартизация кода от рефакторинга?………………………………………………. 63

Может ли начинающий веб-разработчик сделать рефакторинг исходного кода коммерческого продукта?         63

Декомпозиция рефакторинга…………………………………………………………………………………………….. 63

Первичная обработка данных для анализа…………………………………………………………………………….. 65

Выводы о методе декомпозиции………………………………………………………………………………………………. 67

Глава 3. Визуализация больших данных……………………………………………….. 69

Зачем нужно изучать визуализацию данных и овладевать навыками работы с ней?………… 69

Базовые требования к визуализации данных………………………………………………………………………….. 69

Визуализация эмпирических данных по результатам экспериментов…………………………………. 71

Визуализация динамики процессов…………………………………………………………………………………………. 76

Ошибки и несоответствия между графиком математического моделирования и эмпирической моделью на основе эксперимента………………………………………………………………………………………………………………………. 77

Задачи аналитика………………………………………………………………………………………………………………. 78

Пример плавного вывода графика на веб-странице с использованием сплайнов Катмулла–Рома            78

Постановка задачи……………………………………………………………………………………………………. 79

Решение……………………………………………………………………………………………………………………… 79

Визуализация по принципу «от простого к сложному»…………………………………………………………. 84

Визуальные акценты на ключевых аспектах защиты исследовательской работы……… 84

Система знаков для обмена информацией………………………………………………………………………. 86

Стандартизация визуальных и текстовых данных…………………………………………………………………. 87

Стандартизация по корпоративным стандартам……………………………………………………………. 88

Дизайн-система Material Design (Google Inc.)…………………………………………………………………… 90

Графический метод визуализации данных……………………………………………………………………………… 91

Графический метод — один из наиболее точных для прогнозирования………………………. 93

Переход от плоской визуализации к объемной……………………………………………………………….. 93

Принятие обоснованных решений на основе визуализации данных……………………………………. 95

Логические методы принятия решений……………………………………………………………………………………. 97

Выводы о визуализации аналитических данных……………………………………………………………………. 99

Выводы о принятии решений на основе визуализации данных………………………………………….. 100

Глава 4. Прогнозирование коммерческого спроса на товары и услуги…. 101

Гипотетическая оценка спроса на основе публичной статистики……………………………………… 101

Актуальность коммерческих потребительских запросов…………………………………………………….. 103

Формула актуальности поискового запроса…………………………………………………………………. 104

Как выйти на экспоненту доходности в компании?……………………………………………………………… 107

Эффект сарафанного радио…………………………………………………………………………………………….. 110

Характеристика Mobile-Friendly по веб-сайту «HTML Academy»………………………………. 110

Конверсия целевой аудитории в покупатели продукции…………………………………………………….. 112

Что такое воронка продаж?……………………………………………………………………………………………………. 115

Возможно ли автоматизировать воронку продаж?………………………………………………………. 116

Голосовой помощник………………………………………………………………………………………………………………. 117

Запись, обработка и воспроизведение голосовых команд посетителя……………………….. 118

Выводы из примера реализации голосового помощника Voice Assistant…………………… 118

Как увеличить конверсию в электронной торговле?……………………………………………………………. 119

A/B-тестирование предложений товаров и услуг…………………………………………………………. 122

Цена или выгода?…………………………………………………………………………………………………………….. 124

Как эффективнее сделать представление товаров в витрине целевой страницы для конверсии во входящие заявки(лиды)?………………………………………………………………………………………………………….. 126

Шаг № 1: определение необходимой выборки целевой аудитории для A/B-теста       127

Шаг № 2: отправка данных в Яндекс.Метрику……………………………………………. 128

Шаг № 3: настройка целей и интеграция с кол-трекингом…………………………. 129

Результаты: распределение конверсий по визитам с параметрами теста…………. 130

Выводы о прогнозировании спроса……………………………………………………………………………………….. 131

Глава 5. Семантический метод анализа больших текстов…………………….. 133

Графические форматы для семантического анализа текстов……………………………………………… 133

Алгоритм ранжирования смысловых приоритетов в тексте………………………………………………… 135

Пример № 1: смысловые приоритеты в тексте………………………………………………………………. 135

Выводы из примера………………………………………………………………………………………………… 139

Анализ тональности текста…………………………………………………………………………………………….. 139

Пример № 2: эмоциональная тональность текста……………………………………………….. 140

Вывод из примеров…………………………………………………………………………………………………………… 141

Алгоритм анализа семантического ядра для поисковой оптимизации………………………………. 142

Организация хранения и заполнения семантического ядра………………………………………… 142

Шаг № 1: сбор необходимой технической информации……………………………………… 144

Шаг № 2: построение структуры сайта………………………………………………………………… 144

Шаг № 3: подготовка ключевых фраз для целевых страниц………………………………. 145

Шаг № 4: заполнение важных тегов всех целевых страниц……………………………….. 146

Способ 1………………………………………………………………………………………………………….. 146

Способ 2………………………………………………………………………………………………………….. 147

Шаг № 5: постановка на переобход обновленных страниц веб-сайта……………… 150

Алгоритм отбора ключевых фраз для эффективной работы веб-ресурса………………………….. 151

Последовательность исполнения алгоритма отбора ключевых фраз………………………… 152

Базовые требования к подготовке оптимизированных текстов для сайта…………………. 155

Выводы об эффективности алгоритма отбора ключевых фраз по актуальности……… 159

Эффективность алгоритма для поисковой оптимизации…………………………………….. 159

Актуальность ключевых фраз для повышения эффективности сайта……………….. 159

Рекомендации по подготовке уникального контента перед публикацией веб-ресурса……. 160

Выводы о семантическом анализе текстов……………………………………………………………………………. 161

Глава 6. Анализ потребительского доверия к бренду……………………………. 163

Лояльность потребителей к бренду……………………………………………………………………………………….. 163

Классификация по характеристикам…………………………………………………………………………………….. 164

Алгоритмы и метрики потребительской лояльности……………………………………………………………. 165

Алгоритм анализа тональности текстов пользователей………………………………………………. 165

Потребительские и специализированные отраслевые рейтинги…………………………………. 166

Метрики повторных продаж и количества возвратов………………………………………………….. 168

Метрика «индекс потребительской лояльности» (NPS)………………………………………………… 168

Индекс потребительской лояльности…………………………………………………………………………………….. 168

Промежуточные выводы…………………………………………………………………………………………………. 170

Об алгоритме опроса для оценки NPS……………………………………………………………………………………. 170

Что дает исследуемой компании измерение метрики NPS?………………………………………….. 171

Опрос клиентов для анализа лояльности к бренду………………………………………………………. 172

Шаг № 1: составление списка вопросов……………………………………………………………….. 173

Удовлетворенность клиентов компании………………………………………………………. 173

Доверие к бренду производителя продукции………………………………………………. 173

Репутация бренда…………………………………………………………………………………………… 173

Качество продукции и ее ценность……………………………………………………………….. 173

Атрибуты бренда……………………………………………………………………………………………. 174

Шаг № 2: заполнение веб-формы опроса для публикации…………………………………. 174

Шаг № 3: выборка целевой аудитории для рассылки опроса……………………………. 175

Шаг № 4: выбор канала доставки опроса для рассылки…………………………………….. 176

Шаг № 5: доставка опроса выборке ЦА по расписанию…………………………………….. 176

Алгоритм вычисления индекса лояльности NPS…………………………………………………………… 176

Отчет о вычислении индекса NPS…………………………………………………………………………………… 177

Выводы: что дает аналитику и компании анализ метрики NPS?………………………………………… 179

Глава 7. Методика TD ABC. Функционально-стоимостный анализ себестоимости транзакций в системах массового обслуживания……………………………………………………….. 181

Оценка базовой модели ABC………………………………………………………………………………………………….. 183

Пример № 1: расчет ставки стоимости мощности по TD ABC…………………………………….. 183

Пример № 2: оценка затрат за единицу времени…………………………………………………………… 184

Практическая ценность методики учета затрат TD ABC…………………………………………………….. 188

Общее представление о потоковых системах массового обслуживания для обработки заявок           189

Обслуживание потока заявок в СМО……………………………………………………………………………… 190

Рекомендуемая литература по системам массового обслуживания…………………………… 192

Бизнес-модели СМО для секторов B2C и B2B………………………………………………………………. 192

Социально-экономическое значение СМО……………………………………………………………………. 193

Социально-экономическая характеристика дистанционных услуг…………………………………… 196

Количественные характеристики дистанционных услуг…………………………………………….. 197

Эффект масштаба…………………………………………………………………………………………………………….. 201

Пример № 3: развитие дистанционных каналов обслуживания клиентов
в Альфа-Банке…………………………………………………………………………………………………………………… 202

Тезисные выводы……………………………………………………………………………………………………………… 203

Основания инвестиционной привлекательности внедрения СМО на предприятии…… 203

Интерпретация благоприятных условий для роста прибыли ДБО……………………………… 204

О развитии экономики российских компаний в сфере service on demand…………………………… 205

Обзор сферы дистанционных услуг……………………………………………………………………………….. 205

Управление рисками негативного влияния на сервисы дистанционных услуг в РФ…. 207

Рекомендации для повышения эффективности СМО……………………………………………………. 208

Выводы о пользе изучения методик TD ABС и СМО……………………………………………………………. 210

Глава 8. Факторный анализ для оптимального выбора……………………….. 213

Условия применения факторного анализа…………………………………………………………………………….. 213

Применение факторного анализа в исследованиях……………………………………………………………… 214

Решение сложных задач с помощью факторного анализа………………………………………………….. 215

Объектно-ориентированный подход к многофакторному анализу…………………………………….. 215

Пример № 1: матрица принятия решения………………………………………………………………………. 216

Задача……………………………………………………………………………………………………………………… 216

Требования………………………………………………………………………………………………………………. 216

К рассмотрению……………………………………………………………………………………………………… 216

Решение……………………………………………………………………………………………………………………. 216

Вывод о матрице принятия решений…………………………………………………………………….. 217

Пример № 2: сравнительный многофакторный анализ………………………………………………… 218

Задача……………………………………………………………………………………………………………………… 218

Условия……………………………………………………………………………………………………………………. 218

Решение……………………………………………………………………………………………………………………. 218

Выводы о многофакторном сравнительном анализе…………………………………………… 220

Рекомендуемая литература по изучению факторного анализа…………………………. 220

Статистический анализ рынка промышленных комплектующих в РФ………………………………. 221

Каталог комплектующих для производства и сбыта……………………………………………………. 221

Исходная статистика и эмпирические данные для анализа рынка сбыта…………………. 222

Сбор данных о предприятиях России…………………………………………………………………………….. 222

Расчет рыночной стоимости выпускаемых комплектующих………………………………………. 225

Оценка привлекательности комплектующих по регионам РФ…………………………………….. 227

Муфты соединительные…………………………………………………………………………………………. 231

Шкивы клиновые…………………………………………………………………………………………………….. 232

Алгоритм развития продаж комплектующих в регионах России………………………………… 232

Шаг № 1: обработка исходных данных……………………………………………………………….. 233

Шаг № 2: онлайн-заказ с расчетом цены по формуле…………………………………………. 234

Шаг № 3: аналитика……………………………………………………………………………………………….. 235

Шаг № 4: стратегия «Морской бой»……………………………………………………………………… 236

Оценка точности выводов по факторному анализу рынка сбыта комплектующих в РФ…. 237

Первое приближение: метод проб и ошибок. Наивные выводы аналитика-новичка… 237

Метод мультифакторного анализа для достижения требуемой точности результатов       238

Второе приближение: изменение бизнес-модели для монетизации
доступными средствами………………………………………………………………………………………………….. 239

Глава 9. Задача сокращения рекламных расходов……………………………….. 242

Постановка задачи в общем виде…………………………………………………………………………………………… 242

Рекламные каналы для анализа конверсии и цены………………………………………………………. 243

Результаты………………………………………………………………………………………………………………………… 244

A/B-тестирование гипотез об эффективности рекламных каналов…………………………………….. 245

Задача сокращения рекламных расходов в частном виде…………………………………………… 245

При прочих равных условиях………………………………………………………………………………… 246

Визуальный отбор каналов рекламы для таргетинга…………………………………………………… 250

Предварительные выводы……………………………………………………………………………………… 251

Эконометрический отбор по распределению результатов анализа…………………………… 251

Рекомендации по внедрению…………………………………………………………………………………. 251

Юнит-экономика как необходимый инструментарий веб-аналитика………………………………… 253

Как использовать результаты, полученные по задаче минимизации
рекламных расходов?……………………………………………………………………………………………………………… 254

Выводы о минимизации рекламных расходов……………………………………………………………………… 254

Глава 10. Эконометрический метод оценки эффективности ИТ-проектов 256

О стартапах на начальном этапе развития…………………………………………………………………………… 256

Инвестиционная привлекательность дистанционных услуг в РФ………………………………………. 257

Условия достижения эффективности услуг по запросу……………………………………………………….. 258

Пример применения инструментария юнит-экономики……………………………………………….. 260

Задача……………………………………………………………………………………………………………………… 260

Исходные данные……………………………………………………………………………………………………. 260

Условия задачи……………………………………………………………………………………………………….. 260

Решение……………………………………………………………………………………………………………………. 261

Техническая характеристика ИТ-проекта…………………………………………………………………….. 262

Экономическая характеристика ИТ-проекта………………………………………………………………… 264

Характеристика лояльности посетителей ИТ-проекта………………………………………………… 265

Визуально-аналитическая оценка эффективности ИТ-проекта………………………………………….. 265

Качественная оценка метрик ИТ-проекта……………………………………………………………………… 266

Графики функций……………………………………………………………………………………………………………… 268

Выводы об эконометрическом методе оценки эффективности……………………………………………. 269

Глава 11. Семантический анализ данных пользователей веб-сервиса….. 271

О точке приложения семантического анализа……………………………………………………………………… 271

Постановка цели и задач семантического анализа……………………………………………………………… 273

Шаг № 1: формирование набора потенциальных микросервисов для внедрения в качестве гипотез        274

Шаг № 2: внедрение инструментов для анализа…………………………………………………………… 275

Словарь интересов………………………………………………………………………………………………….. 275

Средний чек каждого пользователя………………………………………………………………………. 279

Пример № 1: вычисление среднего чека………………………………………………………. 281

Оценка рентабельности услуги……………………………………………………………………………… 281

Пример № 2: вычисление рентабельности услуги………………………………………. 281

Шаг № 3: отбор и ранжирование потенциальных услуг из гипотез……………………………. 283

Использование показателя среднего чека для исследования…………………………….. 283

Аналитическая функция R’ для ранжирования услуг………………………………………….. 284

Пример № 3: вычисление популярности услуги по тексту пользователя…. 285

Логическая схема семантического анализа для монетизации……………………………. 287

Шаг № 4: формирование результатов исследования……………………………………………………. 288

Отчет по результатам аналитического исследования………………………………… 288

Визуализация результатов исследования……………………………………………………. 288

Сегментация данных по группам коммерческих интересов……………………………….. 290

Раздел «Монетизация сервисов» веб-интерфейса пользователя………………………… 291

Раздел «Аналитика продаж» веб-интерфейса………………………………………………………. 294

Шаг № 5: прогнозирование рентабельности микросервисов………………………………………. 295

Компетентная оценка рентабельности микросервисов……………………………………………………….. 296

Выводы о семантическом анализе данных…………………………………………………………………………… 297

Глава 12. Алгоритм анализа веб-интерфейсов Mobile First……………………. 299

Ключевые факторы алгоритма Mobile First…………………………………………………………………………… 300

Допустимые размеры шрифтов………………………………………………………………………………………. 301

Отзывчивость в миллисекундах……………………………………………………………………………………… 302

Анализ целевой страницы алгоритмом Mobile First……………………………………………………… 303

Рекомендации по оптимизации целевой страницы для повышения позиций в ранжировании поиска Google 305

Выводы об алгоритме Mobile First………………………………………………………………………………………….. 307

Глава 13. Комплексный анализ исходных данных компании………………. 308

Исходные данные для анализа………………………………………………………………………………………………. 308

Анализ входящих заявок на услуги агентства недвижимости…………………………………………….. 310

Исключение из правила анализа данных………………………………………………………………………. 312

Промежуточные выводы…………………………………………………………………………………………………. 313

Сравнение целевой аудитории……………………………………………………………………………………….. 314

Выводы, сделанные на основе анализа данных компании………………………………………….. 315

Почему следует исключить контекстную рекламу из состава инструментов продвижения нового направления услуг?……………………………………………………………………………………………………………………….. 316

Как этого достичь в сложившихся обстоятельствах?…………………………………………. 317

Почему шагов именно 4, а не условно 5 или 7?……………………………………………………. 318

Рекомендации для руководства агентства недвижимости…………………………………………… 318

Фильтрация исходных данных………………………………………………………………………………………………. 323

Очистка входной статистики путем декомпозиции и фильтрации………………………………. 323

Решение по фильтрации данных…………………………………………………………………………………….. 324

Метрика «Роботность»…………………………………………………………………………………………………….. 325

Метрика «Отказы»……………………………………………………………………………………………………………. 326

Что по существу мы получили?………………………………………………………………………………………. 328

Высокая конкуренция требует интересных решений…………………………………………………… 331

Алгоритм подготовки и публикации уникальных описаний для поисковой оптимизации контента   332

Задача SEO-специалиста………………………………………………………………………………………………… 332

Решение……………………………………………………………………………………………………………………. 332

Соотношение уникальности в карточках объектов……………………………………………………… 335

Как определить будущие хиты продаж по названиям товаров или объектов недвижимости?     336

Процентное соотношение уникального текста в карточке товара……………………………… 337

Проблема контроля и фильтрации входящих заявок из-за множества
точек входа……………………………………………………………………………………………………………… 337

Как исправить ситуацию с проблемой минимального коммерческого спроса на недвижимость и трудностью расчета конверсии?………………………………………………………………………………………………… 338

Результаты анализа данных…………………………………………………………………………………………………… 339

Аналитические выводы и рекомендации для повышения эффективности компании… 340

Вывод № 1: необходима автоматизация воронки продаж………………………………….. 340

Рекомендация № 1: внедрить в веб-сайт и в виртуальную АТС компании голосового помощника для диалога с клиентом………………………………………………………………………………………………………….. 341

Вывод № 2: необходимо увеличение адресной базы в каталоге недвижимости. 344

Рекомендация № 2: ранжировать карточки объектов в каталоге недвижимости от максимума к минимуму по эмоциональному критерию оценок пользователей и по актуальности запросов         344

Вывод № 3: необходима интеграция БД объектов с каталогом
в сообществе ВКонтакте………………………………………………………………………………………… 344

Рекомендация № 3: настроить выгрузку обновленной БД объектов в сообществе агентства недвижимости в соцсети ВКонтакте…………………………………………………………………………………………. 345

Выводы о комплексном подходе к анализу данных…………………………………………………………….. 346

Заключение………………………………………………………………………………………….. 347

Приложение. Описание файлового архива…………………………………………… 349

Предметный указатель…………………………………………………………………………. 350

Поляков Егор Юрьевич – опытный веб-разработчик со стажем работы 15 лет, закончил Санкт-Петербургский государственный университет информационных технологий, механики и оптики. Автор учебных книг и курсов по векторной графике, техническому дизайну и анализу данных.

Опубликовано

Долгожданная книга “Реализация полезных алгоритмов на C++”

Реализация полезных алгоритмов на C++

Книга с подробным описанием всевозможных алгоритмов, которые принято реализовывать на C++ в силу высоких требований к скорости и наращиванию мощности алгоритмов. Алгоритмы относятся к следующим предметным областям: машинное обучение и нейронные сети, статистика, криптография, оптимизация, перемножение матриц, хэширование, строковые алгоритмы, случайные леса, методы работы с числами, сортировка, кластеризация, графовые алгоритмы и другие темы, касающиеся программной инженерии. Затронуты вопросы  командной разработки алгоритмов.

Книгу можно использовать как справочник по алгоритмам для программистов и исследователей и как учебное пособие для студентов соответствующих специальностей. Также будет полезна при подготовке к собеседованиям.

Желаю, чтобы мое желание не исполнилось.
 Дуглас Хофштадтер

Профессия программиста неотделима от работы с алгоритмами и структурами данных. В идеале алгоритм должен быть корректным, легко понятным, применимым для решения разнообразных задач и при этом эффективным. В  книге даны и объяснены реализации всевозможных алгоритмов, готовых к внедрению и не защищенных авторскими правами. Алгоритмы относятся к следующим предметным областям:

  • статистические методы,
  • числовые методы,
  • программная инженерия,
  • сортировка,
  • хэширование,
  • графовые алгоритмы,
  • оптимизация,
  • криптография,
  • строковые алгоритмы,
  • спектральная кластеризация,
  • глубокое обучение,
  • перемножение матриц
  • случайные леса

и другим.

Важнейшая часть книги посвящена машинному обучению и отличается значительным теоретическим и академическим уклоном.

Каждая глава будет для вас небольшим открытием. Например, разобраны малоизученные практические аспекты выпуклой оптимизации, метода Монте-Карло и кластеризации при проектировании и усилении нейронных сетей. Затронуты вопросы  командной разработки алгоритмов.

В зависимости от уровня вашей подготовки книга может послужить учебником или справочником, но на долгие годы останется для вас настольной.

Книгу “Реализация полезных алгоритмов на C++” можно купить со скидкой в интернет-магазине издательства “БХВ“.

Предисловие…………………………………………………………………………………………… 19

  1. С чего всё начинается………………………………………………………………………… 21

1.1. Введение………………………………………………………………………………………………………………………………. 21

1.2. Каким должен быть алгоритм?………………………………………………………………………………………….. 21

1.3. Логика принятия решений………………………………………………………………………………………………….. 23

1.4. Доказательство базовой правильности…………………………………………………………………………….. 25

1.5. Асимптотическая запись…………………………………………………………………………………………………….. 27

1.6. Машинные модели……………………………………………………………………………………………………………… 27

1.7. Рандомизированные алгоритмы………………………………………………………………………………………… 29

1.8. Измерение эффективности………………………………………………………………………………………………….. 29

1.9. Типы данных……………………………………………………………………………………………………………………….. 30

1.10. Эксперименты с алгоритмами…………………………………………………………………………………………. 32

1.11. Управление памятью………………………………………………………………………………………………………… 33

1.12. Оптимизация кода…………………………………………………………………………………………………………….. 34

1.13. Рекурсия…………………………………………………………………………………………………………………………….. 36

1.14. Стратегии вычислений……………………………………………………………………………………………………… 37

1.15. Выбор среди нескольких алгоритмов……………………………………………………………………………… 37

1.16. Создание параллельных алгоритмов……………………………………………………………………………… 38

1.17. Реализация алгоритмов……………………………………………………………………………………………………. 39

1.18. Рекомендуемые курсы для студентов, изучающих информатику………………………………… 40

1.19. Некоторые стратегии обучения………………………………………………………………………………………. 42

1.20. О проектах всей книги………………………………………………………………………………………………………. 43

1.21. Список рекомендуемой литературы……………………………………………………………………………….. 44

  1. Основы разработки программного обеспечения…………………………………. 45

2.1. Введение………………………………………………………………………………………………………………………………. 45

2.2. Обзор цикла разработки…………………………………………………………………………………………………….. 45

2.3. Требования………………………………………………………………………………………………………………………….. 46

2.4. Проектирование структуры компонентов………………………………………………………………………… 47

2.5. Проектирование отдельных компонентов и написание кода…………………………………………. 47

2.6. Шаблоны……………………………………………………………………………………………………………………………… 48

2.7. Управление ошибками……………………………………………………………………………………………………….. 52

2.8. Тестирование………………………………………………………………………………………………………………………. 54

2.9. Просмотр кода…………………………………………………………………………………………………………………….. 56

2.10. Релиз…………………………………………………………………………………………………………………………………… 56

2.11. Обслуживание…………………………………………………………………………………………………………………… 57

2.12. Оценка………………………………………………………………………………………………………………………………… 58

2.13. Следование формальному процессу……………………………………………………………………………….. 58

2.14. Управление данными пользователя………………………………………………………………………………… 59

2.15. Список рекомендуемой литературы……………………………………………………………………………….. 59

  1. Советы по вопросам карьерного роста ипрохождения собеседований.. 60

3.1. Введение………………………………………………………………………………………………………………………………. 60

3.2. Отклик на вакансию……………………………………………………………………………………………………………. 60

3.3. Составление резюме…………………………………………………………………………………………………………… 60

3.4. Поведенческие вопросы и собеседования………………………………………………………………………… 61

3.5. Технические собеседования………………………………………………………………………………………………. 63

3.6. Более сложные вопросы…………………………………………………………………………………………………….. 67

3.7. Собеседование по проектированию систем……………………………………………………………………… 68

3.8. Обсуждение предложения………………………………………………………………………………………………….. 68

3.9. Как красиво уйти с текущей работы?……………………………………………………………………………….. 69

3.10. Боритесь с самуспокоенностью………………………………………………………………………………………. 69

3.11. Советы по дополнительной подготовке………………………………………………………………………….. 70

3.12. Список рекомендуемой литературы……………………………………………………………………………….. 70

  1. Основы компьютерного права……………………………………………………………. 71

4.1. Введение………………………………………………………………………………………………………………………………. 71

4.2. Интеллектуальная собственность……………………………………………………………………………………… 71

4.3. Патенты……………………………………………………………………………………………………………………………….. 72

4.4. Коммерческие тайны………………………………………………………………………………………………………….. 73

4.5. Авторские права………………………………………………………………………………………………………………….. 74

4.6. Товарные знаки…………………………………………………………………………………………………………………… 75

4.7. Управление интеллектуальной собственностью……………………………………………………………… 76

4.8. Контракты……………………………………………………………………………………………………………………………. 76

4.9. Лицензии………………………………………………………………………………………………………………………………. 77

4.10. Трудовые соглашения………………………………………………………………………………………………………. 78

4.11. Конфиденциальность……………………………………………………………………………………………………….. 79

4.12. Киберпреступления………………………………………………………………………………………………………….. 80

4.13. Выступления в качестве свидетеля-эксперта…………………………………………………………………. 80

4.14. Советы по дополнительной подготовке………………………………………………………………………….. 81

4.15. Список рекомендуемой литературы……………………………………………………………………………….. 81

  1. Фундаментальные структуры данных………………………………………………… 82

5.1. Введение………………………………………………………………………………………………………………………………. 82

5.2. Вспомогательные функции………………………………………………………………………………………………… 82

5.3. Вектор………………………………………………………………………………………………………………………………….. 88

5.4. Блочный массив………………………………………………………………………………………………………………….. 92

5.5. Связанный список……………………………………………………………………………………………………………….. 93

5.6. Свободный список со сборкой мусора……………………………………………………………………………… 97

5.7. Стек…………………………………………………………………………………………………………………………………….. 101

5.8. Очередь………………………………………………………………………………………………………………………………. 102

5.9. Деревья………………………………………………………………………………………………………………………………. 105

5.10. Битовые алгоритмы………………………………………………………………………………………………………… 106

5.11. Набор битов…………………………………………………………………………………………………………………….. 109

5.12. Поиск объединения…………………………………………………………………………………………………………. 115

5.13. Примечания по реализации……………………………………………………………………………………………. 116

5.14. Комментарии…………………………………………………………………………………………………………………… 116

5.15. Советы по дополнительной подготовке……………………………………………………………………….. 117

5.16. Список рекомендуемой литературы……………………………………………………………………………… 117

  1. Генерация случайных чисел……………………………………………………………… 118

6.1. Введение…………………………………………………………………………………………………………………………….. 118

6.2. Краткий обзор теории вероятностей………………………………………………………………………………. 118

6.3. Генерация псевдослучайных чисел………………………………………………………………………………… 120

6.4. Класс генераторов псевдослучайных чисел Xorshift……………………………………………………. 122

6.5. Вихрь Мерсенна……………………………………………………………………………………………………………….. 123

6.6. Генератор MRG32k3a………………………………………………………………………………………………………. 123

6.7. Алгоритм RC4……………………………………………………………………………………………………………………. 125

6.8. Выбор генератора…………………………………………………………………………………………………………….. 126

6.9. Использование генератора………………………………………………………………………………………………. 127

6.10. Создание выборок из распределений……………………………………………………………………………. 127

6.11. Генерация выборок из дискретных распределений с ограниченным диапазоном…… 129

6.12. Генерация выборок из особых распределений……………………………………………………………. 133

6.13. Генерация случайных объектов……………………………………………………………………………………. 137

6.14. Генерация выборок из многомерных распределений………………………………………………….. 139

6.15. Метод Монте-Карло………………………………………………………………………………………………………. 140

6.16. Примечания по реализации……………………………………………………………………………………………. 146

6.17. Комментарии…………………………………………………………………………………………………………………… 147

6.18. Советы по дополнительной подготовке……………………………………………………………………….. 147

6.19. Список рекомендуемой литературы……………………………………………………………………………… 148

  1. Сортировка………………………………………………………………………………………. 149

7.1. Введение…………………………………………………………………………………………………………………………….. 149

7.2. Сортировка вставками……………………………………………………………………………………………………… 149

7.3. Быстрая сортировка…………………………………………………………………………………………………………. 150

7.4. Сортировка слиянием……………………………………………………………………………………………………….. 153

7.5. Целочисленная сортировка……………………………………………………………………………………………… 154

7.6. Векторная сортировка……………………………………………………………………………………………………… 155

7.7. Сортировка перестановкой……………………………………………………………………………………………… 158

7.8. Выбор…………………………………………………………………………………………………………………………………. 159

7.9. Множественный выбор…………………………………………………………………………………………………….. 160

7.10. Поиск………………………………………………………………………………………………………………………………… 161

7.11. Примечания по реализации……………………………………………………………………………………………. 161

7.12. Комментарии…………………………………………………………………………………………………………………… 162

7.13. Советы по дополнительной подготовке……………………………………………………………………….. 163

7.14. Список рекомендуемой литературы……………………………………………………………………………… 163

  1. Динамически сортируемые последовательности……………………………….. 164

8.1. Введение…………………………………………………………………………………………………………………………….. 164

8.2. Требования………………………………………………………………………………………………………………………… 164

8.3. Список с пропусками………………………………………………………………………………………………………… 165

8.4. Декартово дерево……………………………………………………………………………………………………………… 170

8.5. Итераторы деревьев………………………………………………………………………………………………………….. 176

8.6. Дополнения и варианты API……………………………………………………………………………………………. 178

8.7. Векторные ключи……………………………………………………………………………………………………………… 179

8.8. Расширение LCP для деревьев…………………………………………………………………………………………. 179

8.9. Префиксное дерево……………………………………………………………………………………………………………. 185

8.10. Тернарное декартово дерево…………………………………………………………………………………………. 186

8.11. Сравнение производительности……………………………………………………………………………………. 191

8.12. Примечания по реализации……………………………………………………………………………………………. 192

8.13. Комментарии…………………………………………………………………………………………………………………… 192

8.14. Советы по дополнительной подготовке……………………………………………………………………….. 194

8.15. Список рекомендуемой литературы……………………………………………………………………………… 194

  1. Хеширование……………………………………………………………………………………. 196

9.1. Введение…………………………………………………………………………………………………………………………….. 196

9.2. Хеш-функции……………………………………………………………………………………………………………………… 196

9.3. Универсальные хеш-функции………………………………………………………………………………………….. 200

9.4. Неуниверсальные хеш-функции………………………………………………………………………………………. 203

9.5. Скользящие хеш-функции………………………………………………………………………………………………… 205

9.6. Коллекция хеш-функций…………………………………………………………………………………………………… 206

9.7. Хеш-таблицы…………………………………………………………………………………………………………………….. 206

9.8. Цепочка хеш-таблиц…………………………………………………………………………………………………………. 206

9.9. Хеш-таблица с линейным зондированием……………………………………………………………………… 211

9.10. Оценка времени……………………………………………………………………………………………………………….. 215

9.11. Фильтр Блума………………………………………………………………………………………………………………….. 216

9.12. Примечания по реализации……………………………………………………………………………………………. 217

9.13. Комментарии…………………………………………………………………………………………………………………… 218

9.14. Советы по дополнительной подготовке……………………………………………………………………….. 219

9.15. Список рекомендуемой литературы……………………………………………………………………………… 219

  1. Приоритетные очереди……………………………………………………………………. 221

10.1. Введение………………………………………………………………………………………………………………………….. 221

10.2. API……………………………………………………………………………………………………………………………………. 221

10.3. Бинарная куча…………………………………………………………………………………………………………………. 221

10.4. Индексированные кучи…………………………………………………………………………………………………… 224

10.5. Примечания по реализации……………………………………………………………………………………………. 229

10.6. Комментарии…………………………………………………………………………………………………………………… 229

10.7. Список рекомендуемой литературы……………………………………………………………………………… 230

  1. Алгоритмы графов………………………………………………………………………….. 231

11.1. Введение………………………………………………………………………………………………………………………….. 231

11.2. Основы……………………………………………………………………………………………………………………………… 231

11.3. Представление графов……………………………………………………………………………………………………. 232

11.4. Поиск………………………………………………………………………………………………………………………………… 235

11.5. Примеры задач поиска…………………………………………………………………………………………………… 237

11.6. Минимальное остовное дерево……………………………………………………………………………………… 239

11.7. Кратчайшие пути……………………………………………………………………………………………………………. 240

11.8. Алгоритмы потока………………………………………………………………………………………………………….. 243

11.9. Двудольное сопоставление……………………………………………………………………………………………. 247

11.10. Устойчивое сопоставление………………………………………………………………………………………….. 248

11.11. Задача назначения……………………………………………………………………………………………………….. 249

11.12. Генерация случайных графов……………………………………………………………………………………… 250

11.13. Примечания по реализации…………………………………………………………………………………………. 251

11.14. Комментарии…………………………………………………………………………………………………………………. 251

11.15. Советы по дополнительной подготовке……………………………………………………………………… 252

11.16. Список рекомендуемой литературы…………………………………………………………………………… 252

  1. Разные алгоритмы и методы…………………………………………………………… 253

12.1. Введение………………………………………………………………………………………………………………………….. 253

12.2. Превращение статических структур данных в динамические……………………………………. 253

12.3. Обеспечение устойчивости структур данных……………………………………………………………… 254

12.4. Хранение кеша………………………………………………………………………………………………………………… 255

12.5. Вектор с k-битным размером слова………………………………………………………………………………. 258

12.6. Объединение множества на интервалах………………………………………………………………………. 259

12.7. Создание первых N простых чисел……………………………………………………………………………….. 259

12.8. Генерация всех возможных перестановок……………………………………………………………………. 260

12.9. Генерация всех возможных сочетаний…………………………………………………………………………. 261

12.10. Генерация всех подмножеств………………………………………………………………………………………. 262

12.11. Создание всех разделов……………………………………………………………………………………………….. 262

12.12. Генерация всех зависимых объектов………………………………………………………………………….. 263

12.13. Примечания по реализации…………………………………………………………………………………………. 263

12.14. Комментарии…………………………………………………………………………………………………………………. 263

12.15. Советы по дополнительной подготовке……………………………………………………………………… 264

12.16. Список рекомендуемой литературы…………………………………………………………………………… 264

  1. Алгоритмы для работы с внешней памятью……………………………………. 265

13.1. Введение………………………………………………………………………………………………………………………….. 265

13.2. Диски и файлы…………………………………………………………………………………………………………………. 265

13.3. Структура файла…………………………………………………………………………………………………………….. 268

13.4. Работа с файлами CSV…………………………………………………………………………………………………… 269

13.5. Модель ввода/вывода…………………………………………………………………………………………………….. 273

13.6. Вектор внешней памяти………………………………………………………………………………………………….. 277

13.7. Сортировка……………………………………………………………………………………………………………………… 280

13.8. Векторные структуры данных………………………………………………………………………………………. 282

13.9. Дерево B+………………………………………………………………………………………………………………………… 283

13.10. Комментарии…………………………………………………………………………………………………………………. 291

13.11. Советы по дополнительной подготовке……………………………………………………………………… 291

13.12. Список рекомендуемой литературы…………………………………………………………………………… 292

  1. Строковые алгоритмы…………………………………………………………………….. 293

14.1. Введение………………………………………………………………………………………………………………………….. 293

14.2. Поиск по одному шаблону…………………………………………………………………………………………….. 293

14.3. Поиск по нескольким шаблонам……………………………………………………………………………………. 296

14.4. Регулярные выражения…………………………………………………………………………………………………… 297

14.5. Расширенные шаблоны………………………………………………………………………………………………….. 299

14.6. Алгоритмы поиска расстояния между строками…………………………………………………………. 301

14.7. Обратный индекс…………………………………………………………………………………………………………….. 305

14.8. Суффиксный индекс………………………………………………………………………………………………………… 306

14.9. Синтаксическое дерево………………………………………………………………………………………………….. 310

14.10. Введение в краткие структуры данных………………………………………………………………………. 310

14.11. Примечания по реализации…………………………………………………………………………………………. 314

14.12. Комментарии…………………………………………………………………………………………………………………. 315

14.13. Советы по дополнительной подготовке……………………………………………………………………… 315

14.14. Список рекомендуемой литературы…………………………………………………………………………… 316

  1. Сжатие……………………………………………………………………………………………. 317

15.1. Введение………………………………………………………………………………………………………………………….. 317

15.2. Основные ограничения…………………………………………………………………………………………………… 317

15.3. Энтропия………………………………………………………………………………………………………………………….. 317

15.4. Битовый поток…………………………………………………………………………………………………………………. 318

15.5. Коды…………………………………………………………………………………………………………………………………. 320

15.6. Статические коды…………………………………………………………………………………………………………… 320

15.7. Коды Хаффмана……………………………………………………………………………………………………………… 324

15.8. Сжатие словаря………………………………………………………………………………………………………………. 328

15.9. Кодирование серий байтов……………………………………………………………………………………………. 331

15.10. Перемещение на передний план………………………………………………………………………………….. 332

15.11. Преобразование Берроуза — Уилера…………………………………………………………………………. 333

15.12. Примечания по реализации…………………………………………………………………………………………. 336

15.13. Комментарии…………………………………………………………………………………………………………………. 336

15.14. Советы по дополнительной подготовке……………………………………………………………………… 337

15.15. Список рекомендуемой литературы…………………………………………………………………………… 337

  1. Комбинаторная оптимизация………………………………………………………….. 338

16.1. Введение………………………………………………………………………………………………………………………….. 338

16.2. Теория сложности…………………………………………………………………………………………………………… 338

16.3. Типичные сложные задачи…………………………………………………………………………………………….. 340

16.4. Алгоритмы приближения……………………………………………………………………………………………….. 344

16.5. Эвристика жадного построения…………………………………………………………………………………….. 345

16.6. Ветвление и границы………………………………………………………………………………………………………. 346

16.7. Поиск крачайшего пути в пространстве с нижними границами…………………………………. 352

16.8. Локальный поиск…………………………………………………………………………………………………………….. 360

16.9. Применение локального поиска к некоторым задачам……………………………………………….. 366

16.10. Алгоритм имитации отжига…………………………………………………………………………………………. 370

16.11. Повторный локальный поиск………………………………………………………………………………………. 375

16.12. Генетические алгоритмы……………………………………………………………………………………………… 377

16.13. Анализ производительности………………………………………………………………………………………… 383

16.14. Подготовка данных для конкретной задачи………………………………………………………………. 384

16.15. Многоцелевая оптимизация…………………………………………………………………………………………. 384

16.16. Обработка ограничений………………………………………………………………………………………………. 385

16.17. Стохастические задачи………………………………………………………………………………………………… 390

16.18. Общие рекомендации……………………………………………………………………………………………………. 390

16.19. Примечания по реализации…………………………………………………………………………………………. 391

16.20. Комментарии…………………………………………………………………………………………………………………. 391

16.21. Советы по дополнительной подготовке……………………………………………………………………… 394

16.22. Список рекомендуемой литературы…………………………………………………………………………… 395

  1. Большие числа………………………………………………………………………………… 397

17.1. Введение………………………………………………………………………………………………………………………….. 397

17.2. Представление………………………………………………………………………………………………………………… 397

17.3. Сложение и вычитание…………………………………………………………………………………………………… 399

17.4. Операции сдвига……………………………………………………………………………………………………………… 400

17.5. Умножение………………………………………………………………………………………………………………………. 401

17.6. Деление……………………………………………………………………………………………………………………………. 402

17.7. Преобразование в десятичное число…………………………………………………………………………….. 404

17.8. Возведение в степень………………………………………………………………………………………………………. 404

17.9. Вычисление логарифма………………………………………………………………………………………………….. 405

17.10. Целочисленный квадратный корень…………………………………………………………………………… 405

17.11. Наибольший общий делитель……………………………………………………………………………………… 406

17.12. Модульная инверсия…………………………………………………………………………………………………….. 406

17.13. Проверка числа на простоту……………………………………………………………………………………….. 407

17.14. Рациональные числа…………………………………………………………………………………………………….. 408

17.15. Примечания по реализации…………………………………………………………………………………………. 410

17.16. Комментарии…………………………………………………………………………………………………………………. 410

17.17. Советы по дополнительной подготовке……………………………………………………………………… 411

17.18. Список рекомендуемой литературы…………………………………………………………………………… 411

  1. Вычислительная геометрия…………………………………………………………….. 412

18.1. Введение………………………………………………………………………………………………………………………….. 412

18.2. Расстояния……………………………………………………………………………………………………………………….. 412

18.3. VP-дерево…………………………………………………………………………………………………………………………. 413

18.4. k-d-дерево………………………………………………………………………………………………………………………… 417

18.5. Решение задач при большом числе измерений…………………………………………………………….. 422

18.6. Структуры данных для геометрических объектов………………………………………………………. 423

18.7. Точки………………………………………………………………………………………………………………………………… 423

18.8. Геометрические примитивы…………………………………………………………………………………………… 424

18.9. Выпуклая оболочка………………………………………………………………………………………………………… 425

18.10. Развертка плоскости…………………………………………………………………………………………………….. 426

18.11. Комментарии…………………………………………………………………………………………………………………. 427

18.12. Советы по дополнительной подготовке……………………………………………………………………… 428

18.13. Список рекомендуемой литературы…………………………………………………………………………… 428

  1. Обнаружение и исправление ошибок……………………………………………… 429

19.1. Введение………………………………………………………………………………………………………………………….. 429

19.2. Бинарные полиномы………………………………………………………………………………………………………. 429

19.3. Многочлены над конечными полями……………………………………………………………………………. 429

19.4. Обнаружение ошибок…………………………………………………………………………………………………….. 430

19.5. Каналы и коды………………………………………………………………………………………………………………… 432

19.6. Вычисление конечного поля………………………………………………………………………………………….. 434

19.7. Полиномы над элементами поля Галуа……………………………………………………………………….. 435

19.8. Коды Рида — Соломона………………………………………………………………………………………………… 438

19.9. Границы кодов минимального расстояния с фиксированным алфавитом………………… 442

19.10. Булевы матрицы……………………………………………………………………………………………………………. 443

19.11. Коды проверки на четность с низкой плотностью…………………………………………………….. 444

19.12. Примечания по реализации…………………………………………………………………………………………. 449

19.13. Комментарии…………………………………………………………………………………………………………………. 450

19.14. Советы по дополнительной подготовке……………………………………………………………………… 451

19.15. Список рекомендуемой литературы…………………………………………………………………………… 451

  1. Криптография…………………………………………………………………………………. 452

20.1. Введение………………………………………………………………………………………………………………………….. 452

20.2. Шифрование файлов………………………………………………………………………………………………………. 452

20.3. Длина ключа……………………………………………………………………………………………………………………. 454

20.4. Хранилище ключей…………………………………………………………………………………………………………. 455

20.5. Криптографическое хеширование………………………………………………………………………………… 456

20.6. Обмен ключами……………………………………………………………………………………………………………….. 456

20.7. Другие протоколы…………………………………………………………………………………………………………… 456

20.8. Примечания по реализации……………………………………………………………………………………………. 457

20.9. Комментарии…………………………………………………………………………………………………………………… 457

20.10. Совет по дополнительной подготовке………………………………………………………………………… 458

20.11. Список рекомендуемой литературы…………………………………………………………………………… 458

  1. Вычислительная статистика…………………………………………………………… 459

21.1. Введение………………………………………………………………………………………………………………………….. 459

21.2. Оценки……………………………………………………………………………………………………………………………… 459

21.3. Оценщики…………………………………………………………………………………………………………………………. 462

21.4. Поиск наиболее эффективных оценщиков……………………………………………………………………. 469

21.5. Некоторые особенности асимптотики………………………………………………………………………….. 473

21.6. Оценка нормальной CDF………………………………………………………………………………………………… 473

21.7. Оценка CDF T-распределения……………………………………………………………………………………….. 474

21.8. Подробнее о доверительных интервалах…………………………………………………………………….. 475

21.9. Границы среднего значения в конечной выборке………………………………………………………… 479

21.10. Доверительные интервалы для общих метрик местоположения……………………………… 481

21.11. Выпадающие значения и надежные выводы……………………………………………………………… 484

21.12. Функции оценок…………………………………………………………………………………………………………….. 486

21.13. Измерение времени выполнения алгоритма……………………………………………………………….. 487

21.14. Корреляционный анализ……………………………………………………………………………………………… 488

21.15. Начальная загрузка……………………………………………………………………………………………………… 490

21.16. Когда использовать начальную загрузку?…………………………………………………………………. 504

21.17. Проверка гипотез………………………………………………………………………………………………………….. 505

21.18. Сравнение тестов………………………………………………………………………………………………………….. 507

21.19. Эффективное использование тестов……………………………………………………………………………. 509

21.20. Валидация исследований…………………………………………………………………………………………….. 514

21.21. Сравнение совпадающих пар……………………………………………………………………………………… 515

21.22. Множественные сравнения………………………………………………………………………………………….. 517

21.23. Сравнение совпадающих кортежей……………………………………………………………………………. 519

21.24. Сравнение независимых выборок……………………………………………………………………………….. 520

21.25. Перестановочные тесты……………………………………………………………………………………………….. 522

21.26. Сравнение нескольких альтернатив в нескольких предметных областях………………. 526

21.27. Работа с данными расчета…………………………………………………………………………………………… 529

21.28. Тестирование различий в распределении………………………………………………………………….. 531

21.29. Сравнение данных с распределением………………………………………………………………………… 532

21.30. Сравнение распределений двух выборок…………………………………………………………………… 534

21.31. Анализ чувствительности…………………………………………………………………………………………….. 535

21.32. Последовательность Соболя……………………………………………………………………………………….. 537

21.33. Планирование экспериментов: основные идеи………………………………………………………….. 541

21.34. Марковская цепь Монте-Карло…………………………………………………………………………………… 544

21.35. Байесовские методы……………………………………………………………………………………………………… 547

21.36. Поиск лучшей альтернативы с помощью моделирования………………………………………… 549

21.37. Расчет размера выборки………………………………………………………………………………………………. 552

21.38. Анализ временных рядов……………………………………………………………………………………………… 553

21.39. Использование статистики на практике……………………………………………………………………… 565

21.40. Анализ решений……………………………………………………………………………………………………………. 567

21.41. Примечания по реализации…………………………………………………………………………………………. 569

21.42. Комментарии…………………………………………………………………………………………………………………. 570

21.43. Советы по дополнительной подготовке……………………………………………………………………… 576

21.44. Список рекомендуемой литературы…………………………………………………………………………… 578

  1. Численные алгоритмы: введение и матричная алгебра…………………… 582

22.1. Введение………………………………………………………………………………………………………………………….. 582

22.2. Арифметика с плавающей точкой…………………………………………………………………………………. 583

22.3. Ошибки при использовании арифметики с плавающей точкой………………………………….. 584

22.4. Ошибка приближения…………………………………………………………………………………………………….. 588

22.5. Показатели устойчивости и состояния…………………………………………………………………………. 589

22.6. Ошибка оптимизации……………………………………………………………………………………………………… 591

22.7. Другие общие темы…………………………………………………………………………………………………………. 593

22.8. Разработка надежного численного программного обеспечения……………………………….. 595

22.9. Матричная алгебра………………………………………………………………………………………………………… 599

22.10. Матричные нормы………………………………………………………………………………………………………… 602

22.11. LUP-разложение……………………………………………………………………………………………………………. 603

22.12. Разложение Холецкого…………………………………………………………………………………………………. 608

22.13. Ленточные матрицы……………………………………………………………………………………………………… 609

22.14. Решение тридиагональных матричных уравнений…………………………………………………… 611

22.15. Ортогональные преобразования…………………………………………………………………………………. 611

22.16. QR-разложение……………………………………………………………………………………………………………… 613

22.17. Собственные значения и собственные векторы симметричной матрицы……………….. 615

22.18. Разложение по сингулярным значениям (SVD)………………………………………………………….. 618

22.19. Собственные значения и собственные векторы асимметричной матрицы……………… 622

22.20. Разреженные матрицы………………………………………………………………………………………………….. 627

22.21. Итерационные методы для разреженных матриц……………………………………………………… 633

22.22. Итерационные методы для собственных значений…………………………………………………… 634

22.23. Введение в интервальную арифметику………………………………………………………………………. 636

22.24. Примечания по реализации…………………………………………………………………………………………. 639

22.25. Комментарии…………………………………………………………………………………………………………………. 639

22.26. Советы по дополнительной подготовке……………………………………………………………………… 642

22.27. Список рекомендуемой литературы…………………………………………………………………………… 642

  1. Численные алгоритмы: работа с функциями………………………………….. 645

23.1. Введение………………………………………………………………………………………………………………………….. 645

23.2. Быстрое преобразование Фурье……………………………………………………………………………………. 645

23.3. Интерполяция: общие идеи……………………………………………………………………………………………. 649

23.4. Полиномиальная интерполяция из существующих данных……………………………………….. 652

23.5. Полиномы Чебышева……………………………………………………………………………………………………… 655

23.6. Кусочная интерполяция…………………………………………………………………………………………………. 662

23.7. Сплайны — для работы с существующими данными…………………………………………………. 668

23.8. Сравнение методов интерполяции………………………………………………………………………………… 672

23.9. Интегрирование………………………………………………………………………………………………………………. 674

23.10. Многомерное интегрирование…………………………………………………………………………………….. 681

23.11. Оценка функции…………………………………………………………………………………………………………….. 685

23.12. Оценка производных…………………………………………………………………………………………………….. 685

23.13. Решение нелинейных уравнений и систем………………………………………………………………….. 691

23.14. Поиск всех корней в одномерном случае……………………………………………………………………. 707

23.15. Обыкновенные дифференциальные уравнения………………………………………………………….. 708

23.16. Решение жестких ОДУ………………………………………………………………………………………………….. 713

23.17. Краевые задачи для ОДУ…………………………………………………………………………………………….. 717

23.18. Уравнения с частными производными: некоторые размышления…………………………… 719

23.19. Некоторые выводы……………………………………………………………………………………………………….. 720

23.20. Примечания по реализации…………………………………………………………………………………………. 721

23.21. Комментарии…………………………………………………………………………………………………………………. 721

23.22. Советы по дополнительной подготовке……………………………………………………………………… 727

23.23. Список рекомендуемой литературы…………………………………………………………………………… 728

  1. Численная оптимизация…………………………………………………………………. 731

24.1. Введение………………………………………………………………………………………………………………………….. 731

24.2. Некоторые общие идеи…………………………………………………………………………………………………… 731

24.3. Минимизация унимодальной функции с одной переменной………………………………………. 732

24.4. Минимизация многомерных функций: введение и координатный спуск…………………… 735

24.5. Линейный поиск………………………………………………………………………………………………………………. 738

24.6. Алгоритмы линейного поиска……………………………………………………………………………………….. 742

24.7. Методы, не требующие вычисления производных……………………………………………………… 748

24.8. Негладкая минимизация…………………………………………………………………………………………………. 753

24.9. Глобальная минимизация………………………………………………………………………………………………. 756

24.10. Оптимизация в дискретном множестве……………………………………………………………………….. 770

24.11. Стохастическая оптимизация……………………………………………………………………………………… 772

24.12. Алгоритмы стохастической аппроксимации……………………………………………………………… 773

24.13. Линейное программирование………………………………………………………………………………………. 776

24.14. Некоторые соображения о нелинейном программировании……………………………………. 779

24.15. Примечания по реализации…………………………………………………………………………………………. 780

24.16. Комментарии…………………………………………………………………………………………………………………. 781

24.17. Советы по дополнительной подготовке……………………………………………………………………… 786

24.18. Список рекомендуемой литературы…………………………………………………………………………… 787

  1. Введение в машинное обучение………………………………………………………. 790

25.1. Введение………………………………………………………………………………………………………………………….. 790

25.2. Что такое машинное обучение?…………………………………………………………………………………….. 790

25.3. Математическое обучение…………………………………………………………………………………………….. 791

25.4. Прогнозирование и структурный вывод……………………………………………………………………….. 796

25.5. Оценка риска предиктора………………………………………………………………………………………………. 796

25.6. Источники риска……………………………………………………………………………………………………………… 799

25.7. Контроль сложности………………………………………………………………………………………………………. 800

25.8. Ошибка аппроксимации…………………………………………………………………………………………………. 802

25.9. Устойчивость…………………………………………………………………………………………………………………… 805

25.10. Оценка риска стратегии обучения………………………………………………………………………………. 806

25.11. Принятие решений и выбор модели…………………………………………………………………………….. 810

25.12. Общие стратегии выбора модели………………………………………………………………………………… 812

25.13. Смещение, дисперсия и бэггинг…………………………………………………………………………………… 813

25.14. Паттерны проектирования…………………………………………………………………………………………… 816

25.15. Подготовка данных………………………………………………………………………………………………………. 817

25.16. Масштабирование………………………………………………………………………………………………………… 819

25.17. Обработка пропущенных значений……………………………………………………………………………. 821

25.18. Выбор признаков………………………………………………………………………………………………………….. 821

25.19. Ядра……………………………………………………………………………………………………………………………….. 827

25.20. Обучение в реальном времени…………………………………………………………………………………….. 829

25.21. Работа с невекторными данными………………………………………………………………………………… 830

25.22. Масштабное обучение…………………………………………………………………………………………………. 830

25.23. Выводы………………………………………………………………………………………………………………………….. 832

25.24. Примечания по реализации…………………………………………………………………………………………. 833

25.25. Комментарии…………………………………………………………………………………………………………………. 833

25.26. Советы по дополнительной подготовке……………………………………………………………………… 839

25.27. Список рекомендуемой литературы…………………………………………………………………………… 840

  1. Машинное обучение: классификация…………………………………………….. 842

26.1. Введение………………………………………………………………………………………………………………………….. 842

26.2. Стратификация по метке класса……………………………………………………………………………………. 842

26.3. Оценка риска…………………………………………………………………………………………………………………… 844

26.4. Сведение мультикласса к двум классам……………………………………………………………………….. 848

26.5. Контроль сложности………………………………………………………………………………………………………. 851

26.6. Наивный классификатор Байеса…………………………………………………………………………………… 853

26.7. Ближайший сосед……………………………………………………………………………………………………………. 856

26.8. Дерево решений………………………………………………………………………………………………………………. 859

26.9. Механизм опорных векторов…………………………………………………………………………………………. 866

26.10. Линейный SVM……………………………………………………………………………………………………………… 868

26.11. Ядро SVM………………………………………………………………………………………………………………………. 873

26.12. Мультиклассовый нелинейный SVM………………………………………………………………………….. 878

26.13. Нейронная сеть……………………………………………………………………………………………………………… 880

26.14. Ансамбли рандомизации……………………………………………………………………………………………… 889

26.15. Обучение в реальном времени…………………………………………………………………………………….. 891

26.16. Бустинг…………………………………………………………………………………………………………………………… 894

26.17. Масштабное обучение…………………………………………………………………………………………………. 898

26.18. Экономичное обучение………………………………………………………………………………………………… 898

26.19. Несбалансированное обучение…………………………………………………………………………………… 903

26.20. Выбор признаков………………………………………………………………………………………………………….. 906

26.21. Сравнение классификаторов……………………………………………………………………………………….. 906

26.22. Примечания по реализации…………………………………………………………………………………………. 909

26.23. Комментарии…………………………………………………………………………………………………………………. 910

26.24. Советы по дополнительной подготовке……………………………………………………………………… 919

26.25. Список рекомендуемой литературы…………………………………………………………………………… 919

  1. Машинное обучение: регрессия………………………………………………………. 922

27.1. Введение………………………………………………………………………………………………………………………….. 922

27.2. Оценка риска…………………………………………………………………………………………………………………… 922

27.3. Управление сложностью………………………………………………………………………………………………… 924

27.4. Линейная регрессия………………………………………………………………………………………………………… 925

27.5. Регрессия лассо……………………………………………………………………………………………………………….. 926

27.6. Регрессия ближайших соседей………………………………………………………………………………………. 930

27.7. Дерево регрессии…………………………………………………………………………………………………………….. 931

27.8. Регрессия случайного леса…………………………………………………………………………………………….. 934

27.9. Нейронная сеть……………………………………………………………………………………………………………….. 935

27.10. Выбор признаков………………………………………………………………………………………………………….. 936

27.11. Сравнение производительности………………………………………………………………………………….. 936

27.12. Примечания по реализации…………………………………………………………………………………………. 937

27.13. Комментарии…………………………………………………………………………………………………………………. 938

27.14. Советы по дополнительной подготовке……………………………………………………………………… 941

27.15. Список рекомендуемой литературы…………………………………………………………………………… 942

  1. Машинное обучение: кластеризация………………………………………………. 943

28.1. Введение………………………………………………………………………………………………………………………….. 943

28.2. Постановка………………………………………………………………………………………………………………………. 943

28.3. Внешняя оценка………………………………………………………………………………………………………………. 945

28.4. Внутренняя оценка и выбор количества кластеров…………………………………………………….. 948

28.5. Расчет устойчивости………………………………………………………………………………………………………. 951

28.6. Кластеризация в евклидовом пространстве…………………………………………………………………. 953

28.7. Кластеризация в метрическом пространстве……………………………………………………………….. 957

28.8. Спектральная кластеризация………………………………………………………………………………………… 960

28.9. Эксперименты…………………………………………………………………………………………………………………. 964

28.10. Примечания по реализации…………………………………………………………………………………………. 964

28.11. Комментарии…………………………………………………………………………………………………………………. 965

28.12. Советы по дополнительной подготовке……………………………………………………………………… 969

28.13. Список рекомендуемой литературы…………………………………………………………………………… 969

  1. Машинное обучение: прочие задачи……………………………………………….. 971

29.1. Введение………………………………………………………………………………………………………………………….. 971

29.2. Обучение с подкреплением……………………………………………………………………………………………. 971

29.3. Функция, присваивающая значения……………………………………………………………………………… 972

29.4. Поиск часто встречающихся комбинаций предметов…………………………………………………. 974

29.5. Полуконтролируемое обучение…………………………………………………………………………………….. 975

29.6. Оценка плотности…………………………………………………………………………………………………………… 976

29.7. Обнаружение выпадающих значений…………………………………………………………………………… 976

29.8. Примечания по реализации……………………………………………………………………………………………. 977

29.9. Комментарии…………………………………………………………………………………………………………………… 977

29.10. Список рекомендуемой литературы…………………………………………………………………………… 978

  1. Отстойник: не слишком полезные алгоритмы и структуры данных.. 979

30.1. Введение………………………………………………………………………………………………………………………….. 979

30.2. Сортировка связанного списка……………………………………………………………………………………… 979

30.3. Частичная сортировка……………………………………………………………………………………………………. 981

30.4. Сжатое префиксное дерево……………………………………………………………………………………………. 981

30.5. Хеширование кукушкой…………………………………………………………………………………………………. 987

30.6. Немного приоритетных очередей…………………………………………………………………………………. 990

30.7. Младший общий предок (LCA) и запрос с минимальным диапазоном (RQM)…………. 996

30.8. Знаковый ранговый критерий Уилкоксона для двух выборок……………………………………. 997

30.9. Критерий Фридмана для согласованных выборок……………………………………………………… 998

30.10. MADS-подобный алгоритм оптимизации…………………………………………………………………… 999

30.11. Алгоритм классификации бустинга SAMME…………………………………………………………… 1000

30.12. Бустинг в задаче регрессии……………………………………………………………………………………….. 1001

30.13. Вероятностная кластеризация…………………………………………………………………………………… 1003

30.14. Иерархическая кластеризация………………………………………………………………………………….. 1007

30.15. Кластеризация на основе плотности………………………………………………………………………… 1010

30.16. Не представленные реализации………………………………………………………………………………… 1012

30.17. Советы по дополнительной подготовке……………………………………………………………………. 1013

30.18. Список рекомендуемой литературы…………………………………………………………………………. 1014

  1. Приложение: примечания о языке С++…………………………………………. 1015

31.1. Введение………………………………………………………………………………………………………………………… 1015

31.2. Путеводитель по литературе, посвященной C++……………………………………………………….. 1015

31.3. Советы по дополнительной подготовке……………………………………………………………………… 1015

31.4. Список рекомендуемой литературы…………………………………………………………………………… 1016

Предметный указатель……………………………………………………………………….. 1017