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

Долгожданная книга “Реализация полезных алгоритмов на 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

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

Представляем книгу “С++ — это просто”

С++ это просто

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

Для начинающих программистов

Вы изучите:

• Основы объектно-ориентированного программирования
• Синтаксис языка
• Функции С++
• Классы и объекты
• Наследование
• Полиморфизм
• Систему ввода-вывода в C++
• Использование шаблонов
• Обработку исключений
• Базовые принципы разработки современных приложений на С++

Книгу “С++ — это просто” можно купить со скидкой в интернет-магазине издательства “БХВ“.

Об авторе……………………………………………………………………………………………….. 13

Благодарности……………………………………………………………………………………….. 15

Предисловие к третьему изданию…………………………………………………………… 17

Предисловие к первому изданию……………………………………………………………. 19

Глава 1. Введение в ООП……………………………………………………………………….. 21

Истоки…………………………………………………………………………………………………………………………………………. 23

Структурное программирование……………………………………………………………………………………………… 24

Объектно-ориентированное программирование…………………………………………………………………….. 26

Характеристики объектно-ориентированных языков…………………………………………………………….. 28

Объекты………………………………………………………………………………………………………………………………. 28

Классы………………………………………………………………………………………………………………………………… 29

Инкапсуляция……………………………………………………………………………………………………………………… 29

Скрытие данных…………………………………………………………………………………………………………………. 29

Наследование…………………………………………………………………………………………………………………….. 30

Полиморфизм……………………………………………………………………………………………………………………… 31

Отношения включения……………………………………………………………………………………………………….. 31

Шаблоны…………………………………………………………………………………………………………………………….. 32

Обработка исключений……………………………………………………………………………………………………… 32

Многократное использование…………………………………………………………………………………………… 32

Упражнения………………………………………………………………………………………………………………………………… 33

Важное………………………………………………………………………………………………………………………………………… 35

Глава 2. Переходим на C++……………………………………………………………………. 37

Комментарии……………………………………………………………………………………………………………………………… 39

Ввод и вывод в C++……………………………………………………………………………………………………………………. 40

Динамическое объявление переменных…………………………………………………………………………………… 42

Динамическая инициализация………………………………………………………………………………………………….. 43

Вывод типов……………………………………………………………………………………………………………………………….. 43

Синтаксис структуры (struct), объединения (union) и перечисления (enum)………………………… 43

Неименованные объединения и перечисления……………………………………………………………………….. 44

Приведение типов………………………………………………………………………………………………………………………. 45

Пустой указатель (void)…………………………………………………………………………………………………………….. 46

Оператор ::………………………………………………………………………………………………………………………………….. 46

Ссылки………………………………………………………………………………………………………………………………………… 47

Типы обращений к функциям……………………………………………………………………………………………………. 48

Возвращение значения по ссылке…………………………………………………………………………………………….. 51

Спецификатор const…………………………………………………………………………………………………………………… 52

Const-указатели………………………………………………………………………………………………………………….. 53

Const-ссылки………………………………………………………………………………………………………………………. 54

Возврат значений const-переменных……………………………………………………………………………….. 57

Функции-члены типа const………………………………………………………………………………………………… 57

Логический тип данных (bool)………………………………………………………………………………………………….. 58

Упражнения………………………………………………………………………………………………………………………………… 59

Важное………………………………………………………………………………………………………………………………………… 65

Глава 3. Функции………………………………………………………………………………….. 69

Строгая проверка типов……………………………………………………………………………………………………………. 71

Исходные значения для аргументов функции…………………………………………………………………………. 72

Перегрузка функции…………………………………………………………………………………………………………………… 73

Разница в типе возвращаемого значения…………………………………………………………………………. 74

Можно ли задать разные типы данных при помощи typedef?……………………………………….. 75

Можно ли задать разные типы данных при помощи const?…………………………………………… 75

Разные задачи, одно имя……………………………………………………………………………………………………. 76

Перегрузка операторов……………………………………………………………………………………………………………… 76

FAQ по перегрузке операторов…………………………………………………………………………………………. 79

Встраиваемые функции…………………………………………………………………………………………………………….. 79

Зачем полагаться на компилятор?……………………………………………………………………………………. 80

А где гарантия?…………………………………………………………………………………………………………………… 80

Когда ими пользоваться?…………………………………………………………………………………………………… 81

Новый синтаксис возвращаемого типа……………………………………………………………………………………. 81

Функции instance, static, virtual и friend…………………………………………………………………………………… 81

Упражнения………………………………………………………………………………………………………………………………… 82

Важное………………………………………………………………………………………………………………………………………… 85

Глава 4. Классы и объекты……………………………………………………………………. 87

Структуры и классы………………………………………………………………………………………………………………….. 89

Классы и конструкторы…………………………………………………………………………………………………………….. 92

Деструкторы………………………………………………………………………………………………………………………………. 94

Класс Complex……………………………………………………………………………………………………………………………. 95

Указатель this…………………………………………………………………………………………………………………………….. 97

Перегрузка унарных операторов……………………………………………………………………………………………… 98

Объекты и память…………………………………………………………………………………………………………………….. 100

Еще раз о структурах и классах…………………………………………………………………………………………….. 101

Идеальная организация программы………………………………………………………………………………………. 102

Упражнения……………………………………………………………………………………………………………………………… 106

Важное……………………………………………………………………………………………………………………………………… 112

Глава 5. Премудрости классов……………………………………………………………… 115

Статическое и динамическое выделение памяти………………………………………………………………….. 117

Выделение памяти для массивов и структур…………………………………………………………………. 118

Выделение памяти для объектов…………………………………………………………………………………….. 120

Статические члены класса……………………………………………………………………………………………………… 122

Универсальный спецификатор const……………………………………………………………………………………… 124

Перегруженный оператор присваивания и конструктор копирования………………………………. 126

Преобразование данных…………………………………………………………………………………………………………. 129

Преобразование между встроенными типами………………………………………………………………. 129

Преобразование между встроенными и пользовательскими типами………………………….. 130

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

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

Процедура преобразования в целевом объекте…………………………………………………………….. 134

Упражнения……………………………………………………………………………………………………………………………… 137

Важное……………………………………………………………………………………………………………………………………… 139

Глава 6. Наследование…………………………………………………………………………. 141

Наследование…………………………………………………………………………………………………………………………… 143

Еще один пример наследования…………………………………………………………………………………………….. 147

Варианты применения наследования……………………………………………………………………………………. 149

Наследование и конструкторы………………………………………………………………………………………………. 151

Виды наследования…………………………………………………………………………………………………………………. 154

Одиночное наследование………………………………………………………………………………………………… 154

Многоуровневое наследование………………………………………………………………………………………. 155

Множественное наследование……………………………………………………………………………………….. 156

Предупреждение………………………………………………………………………………………………………………………. 157

Поэтапная разработка…………………………………………………………………………………………………………….. 158

Упражнения……………………………………………………………………………………………………………………………… 158

Важное……………………………………………………………………………………………………………………………………… 160

Глава 7. Полиморфизм…………………………………………………………………………. 163

Виртуальная функция……………………………………………………………………………………………………………… 165

Чистая виртуальная функция………………………………………………………………………………………………….. 167

Абстрактный класс………………………………………………………………………………………………………………….. 168

Связывание функций……………………………………………………………………………………………………………….. 168

Анатомия виртуальных функций……………………………………………………………………………………………. 170

Для чего применять виртуальные функции?…………………………………………………………………………. 177

Срезание объекта…………………………………………………………………………………………………………………….. 177

Виртуальные деструкторы……………………………………………………………………………………………………… 179

Вызов виртуальных функций из конструкторов/деструкторов…………………………………… 181

Виртуальные базовые классы………………………………………………………………………………………………… 181

Упражнения……………………………………………………………………………………………………………………………… 183

Важное……………………………………………………………………………………………………………………………………… 184

Глава 8. Система ввода-вывода в C++………………………………………………….. 187

Требования к системе ввода-вывода……………………………………………………………………………………… 189

Решение с использованием потоков в C++…………………………………………………………………………….. 190

Предопределенные потоковые объекты………………………………………………………………………………… 191

Библиотека iostream………………………………………………………………………………………………………………… 191

Класс istream……………………………………………………………………………………………………………………………. 192

Класс ostream…………………………………………………………………………………………………………………………… 194

Вывод символов в кодировке Unicode……………………………………………………………………………. 195

Класс iostream………………………………………………………………………………………………………………………….. 196

Манипуляторы потока……………………………………………………………………………………………………………. 196

Пользовательские манипуляторы………………………………………………………………………………………….. 199

Пользовательские манипуляторы с аргументами…………………………………………………………. 200

Работа с потоками ввода-вывода в файл………………………………………………………………………………. 202

Символьный ввод-вывод…………………………………………………………………………………………………………. 203

Открытие файла……………………………………………………………………………………………………………….. 203

Чтение данных………………………………………………………………………………………………………………….. 204

Обнаружение конца файла (EOF)…………………………………………………………………………………… 204

Закрытие файла……………………………………………………………………………………………………………….. 204

Программа копирования файлов……………………………………………………………………………………………. 204

Ввод-вывод строк…………………………………………………………………………………………………………………….. 205

Ввод-вывод записей…………………………………………………………………………………………………………………. 206

Прямой доступ…………………………………………………………………………………………………………………………. 208

Режимы открытия файла…………………………………………………………………………………………………………. 210

Строковые потоки……………………………………………………………………………………………………………………. 211

Работа с istrstream……………………………………………………………………………………………………………. 212

Ввод-вывод объектов………………………………………………………………………………………………………………. 213

Сериализация…………………………………………………………………………………………………………………………… 214

Обработка ошибок ввода-вывода………………………………………………………………………………………….. 215

Взаимодействие с файловой системой…………………………………………………………………………………… 217

Упражнения……………………………………………………………………………………………………………………………… 220

Важное……………………………………………………………………………………………………………………………………… 222

Глава 9. Расширенные возможности C++…………………………………………….. 225

Отношения включения…………………………………………………………………………………………………………….. 227

Дружественные (friend) функции и классы……………………………………………………………………………. 229

Еще одно применение дружественной функции……………………………………………………………………. 231

Предупреждение………………………………………………………………………………………………………………………. 234

Ключевое слово explicit………………………………………………………………………………………………………….. 234

Ключевое слово mutable…………………………………………………………………………………………………………. 236

Пространство имен………………………………………………………………………………………………………………….. 237

Способы применения пространства имен……………………………………………………………………………… 240

Использование оператора разрешения контекста………………………………………………………… 240

Ключевое слово using……………………………………………………………………………………………………… 241

Динамическая идентификация типа (RTTI)…………………………………………………………………………… 242

Приведение типов в C++………………………………………………………………………………………………………….. 244

static_cast………………………………………………………………………………………………………………………….. 245

dynamic_cast……………………………………………………………………………………………………………………… 246

const_cast………………………………………………………………………………………………………………………….. 248

reinterpret_cast…………………………………………………………………………………………………………………. 248

Предупреждение………………………………………………………………………………………………………………. 249

Указатели на члены классов…………………………………………………………………………………………………… 249

Упражнения……………………………………………………………………………………………………………………………… 253

Важное……………………………………………………………………………………………………………………………………… 254

Глава 10. Шаблоны……………………………………………………………………………… 257

Шаблоны функций…………………………………………………………………………………………………………………… 259

Что происходит во время компиляции?………………………………………………………………………….. 261

Шаблоны функций для пользовательских типов………………………………………………………………….. 261

Еще одна шаблонная функция……………………………………………………………………………………………….. 262

Явная специализация обобщенной функции…………………………………………………………………. 264

Функция с набором обобщенных типов………………………………………………………………………………… 264

Шаблоны и макросы……………………………………………………………………………………………………………….. 265

Сортировка на основе шаблона…………………………………………………………………………………………….. 266

Шаблоны классов……………………………………………………………………………………………………………………. 267

Шаблон класса связного списка…………………………………………………………………………………………….. 271

Полезные советы по шаблонам………………………………………………………………………………………………. 273

Вариативные шаблоны…………………………………………………………………………………………………………… 275

Области применения шаблонов……………………………………………………………………………………………… 276

Упражнения……………………………………………………………………………………………………………………………… 276

Важное……………………………………………………………………………………………………………………………………… 278

Глава 11. Обработка исключений………………………………………………………… 279

Обработка исключений в C++………………………………………………………………………………………………… 281

Работа с библиотечными классами исключений………………………………………………………………….. 284

Библиотечные исключения при создании очереди………………………………………………………. 286

Еще один пример……………………………………………………………………………………………………………… 288

Работа с пользовательскими классами исключений……………………………………………………………. 290

Полезные советы……………………………………………………………………………………………………………………… 292

Спецификация исключений…………………………………………………………………………………………………….. 293

Необработанные исключения………………………………………………………………………………………………… 294

Интеллектуальные указатели и динамические контейнеры………………………………………………… 295

Упражнения……………………………………………………………………………………………………………………………… 297

Важное……………………………………………………………………………………………………………………………………… 298

Глава 12. Стандартная библиотека шаблонов……………………………………… 301

Стандартная библиотека шаблонов……………………………………………………………………………………… 303

Компоненты STL……………………………………………………………………………………………………………………… 304

Контейнеры………………………………………………………………………………………………………………………. 304

Итераторы………………………………………………………………………………………………………………………… 305

Алгоритмы………………………………………………………………………………………………………………………… 306

Вектор (vector)………………………………………………………………………………………………………………………….. 307

Другие операции………………………………………………………………………………………………………………. 308

Вектор объектов класса Point…………………………………………………………………………………………………. 309

Список (list)………………………………………………………………………………………………………………………………. 311

Множество (set) и мультимножество (multi-set)…………………………………………………………………….. 313

Отображение (map) и мультиотображение (multi-map)………………………………………………………… 317

Стек (stack)……………………………………………………………………………………………………………………………….. 319

Очередь (queue)………………………………………………………………………………………………………………………… 320

Объект-функция………………………………………………………………………………………………………………… 322

Упражнения……………………………………………………………………………………………………………………………… 323

Важное……………………………………………………………………………………………………………………………………… 324

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

Яшавант Канеткар

Яшавант Канеткар — автор книг и курсов по языкам C, C++, Java, Python, структурам данных, .NET, IoT. Его книги переведены на хинди, гуджарати, японский, корейский и китайский языки. Получил степень бакалавра в Технологическом институте имени Веермата Джиджабая (VJTI, Мумбаи) и магистра технических наук в Индийском Институте Технологий (IIT, Канпур). В настоящее время является директором нескольких IT-компаний. Был удостоен множества престижных наград за свои предпринимательские, профессиональные и академические достижения, а также за вклад в IT-образование Индии.

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

Представляем книгу “Практическая робототехника. C++ и Raspberry Pi”

Практическая робототехника. C++ и Raspberry Pi

Рассказано о технологии создания автономных роботов на базе одноплатного компьютера Raspberry Pi и о разработке программ для них на языке С++. Показаны принципы написания и даны примеры кода для контроллера привода двигателя, продемонстрированы способы использования датчиков для обнаружения препятствий и построения карт на основе данных лидара. Описаны методы разработки собственных алгоритмов автономного планирования траектории движения, приведен код для автоматической отправки путевых точек контроллеру привода. Рассмотрены библиотеки С++ для написания программ картографии и навигации автономных роботов, даны сведения об использовании контактов аппаратного интерфейса Raspberry Pi GPIO.
Электронный архив на сайте издательства содержит код описанных в книге программ.

Для интересующихся робототехникой

 

В книге представлены исчерпывающие знания по электронике, аппаратному и программному обеспечению для создания настоящих роботов на базе одноплатного компьютера Raspberry Pi.

Вы узнаете как:

  •  использовать датчики для обнаружения препятствий;
  • обучить робота строить карту и планировать траекторию движения;
  • структурировать код на С++, чтобы он получился модульным и взаимозаменяемым с другими проектами по созданию роботов.
  • использовать контакты аппаратного интерфейса Raspberry Pi GPIO и существующие библиотеки С++, чтобы создать полностью автономного программируемого робота на самой доступной компьютерной платформе.

Вы научитесь:

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

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

Об авторе……………………………………………………………………………………………….. 16

Благодарности……………………………………………………………………………………….. 17

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

Вступительное слово………………………………………………………………………………. 21

Введение………………………………………………………………………………………………… 23

Часть I. Введение в компьютеры для робототехники…….. 25

Глава 1. Выбор и настройка компьютера для робота……………………………… 27

Что такое Raspberry Pi?……………………………………………………………………………………………………………… 27

В чем же разница?……………………………………………………………………………………………………………… 28

Значит, Raspberry Pi — единственный вариант контроллера для управления роботом?    28

Разве Raspberry Pi не предназначен для школ, энтузиастов-электронщиков и игрушек? Я хотел узнать о настоящей робототехнике…………………………………………………………………………………………………………… 29

Какие модели Raspberry Pi существуют и почему не все из них подходят
для наших целей?………………………………………………………………………………………………………………………. 29

Raspberry Pi Zero и Raspberry Pi ZeroW…………………………………………………………………………….. 31

Raspberry Pi 2B……………………………………………………………………………………………………………………. 31

Raspberry Pi 3B — лучший выбор!……………………………………………………………………………………. 32

Raspberry Pi 3B+…………………………………………………………………………………………………………………. 32

Новая модель Raspberry Pi 4……………………………………………………………………………………………… 33

Выбор операционной системы…………………………………………………………………………………………………. 33

Raspbian………………………………………………………………………………………………………………………………. 34

Ubuntu…………………………………………………………………………………………………………………………………. 34

Установка и настройка операционной системы…………………………………………………………………….. 35

Установка полной Ubuntu Desktop на ноутбук или настольный ПК…………………………….. 36

Установка Lubuntu на Raspberry Pi………………………………………………………………………………….. 36

Установка и настройка интегрированной среды разработки (IDE)……………………………………… 40

Visual studio Code для ноутбука или настольного ПК……………………………………………………. 40

Code Blocks для Raspberry Pi…………………………………………………………………………………………….. 41

Заключение………………………………………………………………………………………………………………………………… 42

Вопросы……………………………………………………………………………………………………………………………………… 42

Глава 2. Назначение и использование контактов интерфейса GPIO………. 43

Общие сведения о GPIO…………………………………………………………………………………………………………….. 43

Что такое интерфейс GPIO………………………………………………………………………………………………………… 43

Какие же именно функции выполняет GPIO?…………………………………………………………………… 45

Электроника для программистов…………………………………………………………………………….. 45

Типы выходных данных…………………………………………………………………………………………… 50

Типы входных данных……………………………………………………………………………………………… 52

Некоторые распространенные радиодетали…………………………………………………………. 53

Контакты GPIO в качестве выходов………………………………………………………………………… 57

Две системы нумерации контактов GPIO……………………………………………………………….. 58

Контакты GPIO в качестве входов…………………………………………………………………………… 59

Как получить доступ к контактам GPIO Raspberry Pi с помощью программ на C++…………… 61

Библиотека PIGPIO……………………………………………………………………………………………………………………. 62

Установка и настройка библиотеки PIGPIO……………………………………………………………………. 62

Удостоверимся, что Code::Blocks может обращаться к PIGPIO…………………………… 63

Запуск программ PIGPIO………………………………………………………………………………………….. 64

Наш первый проект — hello_blink…………………………………………………………………………… 64

Цифровой вход, управляющий цифровым выходом — hello_button……………………. 67

Функции обратного вызова для обработки событий GPIO…………………………………… 68

Заключение………………………………………………………………………………………………………………………………… 71

Часть II. Начинаем проектировать робота………………………….. 73

Глава 3. Платформа для робота……………………………………………………………… 75

Общие сведения………………………………………………………………………………………………………………………….. 75

Габаритные размеры и режим эксплуатации…………………………………………………………………………. 76

Что лучше — дифференциальный рулевой привод или привод Аккермана?………………………. 78

Дифференциальный рулевой привод……………………………………………………………………………….. 78

Рулевой привод Аккермана……………………………………………………………………………………………….. 79

Готовые платформы для роботов…………………………………………………………………………………………….. 79

Большие готовые платформы……………………………………………………………………………………………. 79

Маленькие готовые роботы………………………………………………………………………………………………. 80

Советы по созданию собственного робота……………………………………………………………………………… 82

Материалы для конструирования……………………………………………………………………………………. 82

Аккумуляторы…………………………………………………………………………………………………………… 83

Ходовая часть……………………………………………………………………………………………………………. 83

Где найти детали для роботов…………………………………………………………………………………. 84

Перепрофилирование роботов-пылесосов или автомобилей с дистанционным управлением 85

Роботы-пылесосы с интерфейсом…………………………………………………………………………………….. 86

Взаимодействие с Roomba………………………………………………………………………………………. 87

“Разморозка” Roomba………………………………………………………………………………………………. 90

Роботы-пылесосы без интерфейса……………………………………………………………………………………. 91

Перепрофилирование автомобилей и грузовиков с дистанционным управлением…………….. 92

Заключение………………………………………………………………………………………………………………………………… 94

Вопросы……………………………………………………………………………………………………………………………………… 94

Глава 4. Типы двигателей для роботов и управление двигателями………… 95

Общие сведения………………………………………………………………………………………………………………………….. 95

Типы двигателей………………………………………………………………………………………………………………………… 95

Сравнение двигателей переменного (AC) и постоянного (DC) токов……………………………. 96

Щеточные двигатели постоянного тока…………………………………………………………………………… 97

Сервоприводы…………………………………………………………………………………………………………………….. 98

Шаговые двигатели……………………………………………………………………………………………………………. 99

Бесщеточные двигатели постоянного тока (BLDC)……………………………………………………… 100

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

Простейший способ управления: включено/выключено……………………………………………… 101

Транзисторы…………………………………………………………………………………………………………………….. 102

Широтно-импульсная модуляция (ШИМ)……………………………………………………………………… 105

ШИМ для создания аналоговых напряжений………………………………………………………. 105

ШИМ в качестве управляющего сигнала……………………………………………………………… 106

Драйверы и контроллеры двигателей……………………………………………………………………………. 107

Драйверы двигателей……………………………………………………………………………………………… 108

Управление двигателями с помощью драйвера двигателя на основе
двойного Н-моста L298N……………………………………………………………………………………….. 109

Контроллеры двигателей……………………………………………………………………………………….. 112

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

Вопросы……………………………………………………………………………………………………………………………………. 114

Бонусное задание…………………………………………………………………………………………………………………….. 114

Глава 5. Связь с датчиками и другими устройствами…………………………… 115

Общие сведения……………………………………………………………………………………………………………………….. 115

Двоичные (логические) сигналы…………………………………………………………………………………………….. 115

Выключатели с защитой от дребезга контактов…………………………………………………………………… 116

Колесные энкодеры…………………………………………………………………………………………………………………. 117

Двоичные сигналы от аналоговых датчиков………………………………………………………………………… 118

Сводная информация о передаче данных с помощью двоичных сигналов……………………….. 119

Передача данных через последовательный интерфейс……………………………………………………….. 119

Последовательная передача данных с помощью UART……………………………………………………… 119

Настройка Raspberry Pi и тестирование последовательной передачи данных
через UART………………………………………………………………………………………………………………………………. 121

Устранение ошибки при открытии последовательного порта…………………………………….. 124

Передача данных через последовательную шину I2C………………………………………………………… 124

Настройка и использование устройства I2C с Raspberry Pi………………………………………… 126

Пример и тестовая программа: hello_i2c_lsm303…………………………………………………………………. 127

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

Вопросы……………………………………………………………………………………………………………………………………. 131

Глава 6. Дополнительное оборудование……………………………………………….. 132

Общие сведения……………………………………………………………………………………………………………………….. 132

Источники питания………………………………………………………………………………………………………………….. 132

Источники питания напряжением 5 В……………………………………………………………………………. 133

Регулируемые источники питания………………………………………………………………………………….. 133

Релейные блоки………………………………………………………………………………………………………………………… 134

Преобразователи логических уровней………………………………………………………………………………….. 135

Преобразователи интерфейса (FTDI)…………………………………………………………………………………….. 136

Микроконтроллеры Arduino…………………………………………………………………………………………………… 137

Микроконтроллеры Digispark…………………………………………………………………………………………………. 137

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

Вопросы……………………………………………………………………………………………………………………………………. 138

Глава 7. Установка компьютера, управляющего роботом……………………. 139

Общие сведения……………………………………………………………………………………………………………………….. 139

Последовательность шагов…………………………………………………………………………………………………….. 140

Установка компьютера и подача питания на него……………………………………………………………….. 140

Соединение компьютера с остальными частями робота…………………………………………………….. 141

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

Вопросы……………………………………………………………………………………………………………………………………. 144

Часть III. Логика функционирования робота…………………… 145

Глава 8. Стратегия управления роботом………………………………………………. 147

Общие сведения……………………………………………………………………………………………………………………….. 147

Управление роботом: верхний и нижний уровни…………………………………………………………………. 147

Основной контур управления…………………………………………………………………………………………………. 149

Наблюдение и сравнение………………………………………………………………………………………………………… 149

Реагирование……………………………………………………………………………………………………………………. 150

Воздействие………………………………………………………………………………………………………………………. 150

Контроллеры с разомкнутым и замкнутым контуром управления…………………………………….. 153

Разработка контроллеров верхнего уровня (главных контроллеров)………………………………… 154

Разработка контроллеров нижнего уровня (технологических контроллеров)………………….. 156

Двухпозиционные контроллеры (регуляторы типа включено-выключено)……………….. 157

Пропорциональные контроллеры………………………………………………………………………………….. 157

Проектирование контроллеров, допускающих некоторую погрешность…………………… 161

Установка минимального значения выходного сигнала……………………………………………… 161

За рамками пропорциональных контроллеров…………………………………………………………….. 162

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

Вопросы……………………………………………………………………………………………………………………………………. 163

Глава 9. Организация совместной работы компонентов………………………. 164

Общие сведения……………………………………………………………………………………………………………………….. 164

Что такое операционная система для роботов?……………………………………………………………………. 165

ROS или создание собственного ПО для управления роботами?……………………………………….. 165

ROS и область коммерческой робототехники………………………………………………………………………. 166

Установка ROS…………………………………………………………………………………………………………………………. 167

Установка ROS Melodic на ноутбуке или настольном компьютере……………………………. 167

Установка ROS Kinetic на Raspberry Pi 3B…………………………………………………………………….. 168

Быстрое тестирование ROS…………………………………………………………………………………………….. 170

Краткий экскурс в ROS……………………………………………………………………………………………………………. 171

Пакеты, узлы, издатели, подписчики, топики и сообщения…………………………………………. 171

Полезные приемы…………………………………………………………………………………………………………………….. 177

Создание и написание пакетов и узлов ROS…………………………………………………………………………. 178

Файловая система ROS……………………………………………………………………………………………………. 178

Создание пакетов ROS…………………………………………………………………………………………………….. 178

Написание программ ROS (узлов)………………………………………………………………………………….. 180

Загрузка, просмотр и запуск программ, скачанных для этой главы…………………………… 186

Как облегчить жизнь с помощью файлов roslaunch и .launch……………………………………………… 187

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

Вопросы……………………………………………………………………………………………………………………………………. 189

Глава 10. Карты для определения местоположения робота…………………… 190

Общие сведения……………………………………………………………………………………………………………………….. 190

Угол, курс, расстояние: общепринятые соглашения……………………………………………………………. 191

Получение данных с датчиков……………………………………………………………………………………………….. 193

Сетчатая карта занятости………………………………………………………………………………………………………. 194

Построение сетчатых карт занятости (OGM) с помощью данных, получаемых с датчиков 196

Маркировка занятых ячеек…………………………………………………………………………………………………….. 199

Маркировка свободных ячеек………………………………………………………………………………………………… 202

Заключительные шаги при составлении карты……………………………………………………………………. 202

Публикация карты в виде сообщения ROS……………………………………………………………………………. 203

Преобразования в ROS……………………………………………………………………………………………………………. 204

Для чего нужны преобразования……………………………………………………………………………………. 205

Использование преобразований в ROS………………………………………………………………………….. 206

Публикация преобразований с помощью static transform publisher……………………………. 207

Публикация сообщений от узлов с помощью транслятора преобразований (transform broadcaster)        208

Получение данных о преобразованиях в узлах……………………………………………………………. 209

Просмотр данных о преобразовании из командной строки………………………………………… 211

Упрощение картографирования с помощью Gmapping……………………………………………………….. 211

Общие сведения о Gmapping…………………………………………………………………………………………… 212

Установка Gmapping……………………………………………………………………………………………………….. 212

Запуск Gmapping и задание параметров в файлах запуска…………………………………………. 212

Этапы создания карты…………………………………………………………………………………………………………….. 214

Визуализация создания карты в реальном времени…………………………………………………………….. 214

Сохранение карты и ее последующее использование…………………………………………………………. 216

Сохранение карт………………………………………………………………………………………………………………. 216

Загрузка ранее сохраненной карты……………………………………………………………………………….. 217

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

Вопросы……………………………………………………………………………………………………………………………………. 217

Глава 11. Отслеживание перемещений и локализация робота……………… 219

Общие сведения……………………………………………………………………………………………………………………….. 219

Поза робота……………………………………………………………………………………………………………………………… 220

Преобразование углов Эйлера в кватернионы……………………………………………………………… 221

Преобразование кватернионов в углы Эйлера……………………………………………………………… 223

Одометрия и точный расчет траектории……………………………………………………………………………….. 223

Колесная одометрия………………………………………………………………………………………………………… 224

Расчет расстояния, пройденного каждым колесом………………………………………………………. 227

Расчет общего расстояния, пройденного роботом……………………………………………………….. 228

Расчет изменения угла поворота тета……………………………………………………………………………. 228

Сложение величины изменения угла поворота с предыдущим значением угла поворота тета   229

Расчет расстояния, пройденного по осям x и y (преобразование координат)……………. 229

Прибавление полученных расстояний к соответствующим значениям предыдущей оценки позы            230

Публикация сообщения одометрии о новой позе для других узлов…………………… 230

Сохранение данных новой позы для использования в следующем цикле………… 230

Точный расчет траектории……………………………………………………………………………………………… 230

Публикация данных одометрии в ROS………………………………………………………………………………….. 232

Издатель сообщений о преобразованиях одометрии…………………………………………………… 234

Дальнейшее отслеживание перемещений робота и его локализация в пространстве………. 236

Инструмент для коррекции позы вручную…………………………………………………………………….. 236

Фидуциальные маркеры………………………………………………………………………………………………………….. 237

Локализация с помощью лазерного сканера………………………………………………………………………… 238

GPS и GNSS……………………………………………………………………………………………………………………………….. 239

Системы локализации на основе радиомаяков…………………………………………………………………….. 239

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

Вопросы……………………………………………………………………………………………………………………………………. 240

Глава 12. Автономное движение…………………………………………………………… 241

Общие сведения……………………………………………………………………………………………………………………….. 241

Обзор движения роботов в ROS……………………………………………………………………………………………… 241

Контроллер двигателя — simple_diff_drive.cpp……………………………………………………………………. 242

Шаги по созданию контроллера двигателя simple_diff_drive……………………………………… 243

Код контроллера двигателя дифференциального рулевого привода,
представленный в общем виде………………………………………………………………………………………… 244

Код контроллера двигателя дифференциального рулевого привода…………………………. 245

Контроллер привода — simple_drive_controller.cpp……………………………………………………………… 251

Шаги по созданию контроллера привода……………………………………………………………………… 251

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

Вопросы……………………………………………………………………………………………………………………………………. 256

Глава 13. Автономное планирование маршрута…………………………………… 257

Общие сведения……………………………………………………………………………………………………………………….. 257

Методы планирования маршрута и сопутствующие проблемы…………………………………………. 257

Проблемы………………………………………………………………………………………………………………………….. 258

Методы планирования маршрута………………………………………………………………………………….. 258

Увеличение границ вокруг препятствий………………………………………………………………………… 259

Карты затрат (costmap)…………………………………………………………………………………………………… 260

Пакет costmap_2d…………………………………………………………………………………………………………….. 260

Планирование маршрута с помощью алгоритма A*……………………………………………………. 263

Как работает алгоритм А*……………………………………………………………………………………………… 264

Пошаговый разбор алгоритма A*………………………………………………………………………………….. 266

Разбор процедуры А*………………………………………………………………………………………………………. 268

Написание программы A* как узла ROS……………………………………………………………………………….. 273

Стандартные вещи, вспомогательные функции и main()……………………………………………… 274

Сердце узла A*: функция find_path()……………………………………………………………………………… 284

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

Вопросы……………………………………………………………………………………………………………………………………. 289

Часть IV. Интерпретация данных,
поступающих с датчиков……………………………………………………….. 291

Глава 14. Колесные энкодеры для одометрии………………………………………. 293

Общие сведения……………………………………………………………………………………………………………………….. 293

Колесные энкодеры…………………………………………………………………………………………………………………. 293

Оптические энкодеры………………………………………………………………………………………………………………. 294

Энкодеры на датчиках Холла………………………………………………………………………………………………… 294

Подключение энкодеров…………………………………………………………………………………………………………. 295

Издатель сообщений об импульсах: tick_publisher.cpp………………………………………………………… 297

Код издателя сообщений об импульсах энкодера……………………………………………………………….. 298

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

Вопросы……………………………………………………………………………………………………………………………………. 302

Глава 15. Ультразвуковые датчики расстояния……………………………………. 303

Общие сведения……………………………………………………………………………………………………………………….. 303

Основная информация об ультразвуковом дальномере HC-SR04………………………………………. 304

Считывание показаний HC-SR04…………………………………………………………………………………… 304

Подключение HC-SR04…………………………………………………………………………………………………………… 304

Издатель данных ультразвукового измерения расстояния: ultrasonic_publisher.cpp………… 305

Издатель сообщений об ультразвуковом измерении расстояния:
пошаговый разбор……………………………………………………………………………………………………………. 305

Обзор кода издателя сообщений об ультразвуковом измерении расстояния…………….. 306

Использование данных ультразвукового измерения расстояния при обнаружении объектов 309

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

Вопросы……………………………………………………………………………………………………………………………………. 311

Глава 16. Инерциальные измерительные блоки (IMU) — акселерометры, гироскопы и магнитометры…………………………………………………………………………………………………………….. 312

Общие сведения……………………………………………………………………………………………………………………….. 312

Акселерометры………………………………………………………………………………………………………………………… 313

Недостатки акселерометра…………………………………………………………………………………………….. 314

Публикация данных IMU в ROS……………………………………………………………………………………… 314

Тип данных sensor_msgs::Imu в ROS………………………………………………………………………………. 315

Код издателя сообщений IMU………………………………………………………………………………………… 316

Гироскопы………………………………………………………………………………………………………………………………… 320

Недостатки гироскопа…………………………………………………………………………………………………….. 321

Добавление данных гироскопа в узел IMU…………………………………………………………………… 321

Магнитометры…………………………………………………………………………………………………………………………. 322

Недостатки магнитометра………………………………………………………………………………………………. 322

Добавление данных магнитометра………………………………………………………………………………… 323

Установка IMU………………………………………………………………………………………………………………………… 325

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

Вопросы……………………………………………………………………………………………………………………………………. 326

Глава 17. GPS и системы на основе внешних радиомаяков………………….. 327

Общие сведения……………………………………………………………………………………………………………………….. 327

Как работают системы на основе радиомаяков…………………………………………………………………… 327

Основные сведения о GPS и GNSS………………………………………………………………………………………….. 329

Точность GPS/GNSS…………………………………………………………………………………………………………. 329

Определение местоположения с помощью GPS/GNSS-RTK с точностью до 2 см……… 330

Ограничения GPS/GNSS…………………………………………………………………………………………………… 331

Данные GPS/GNSS……………………………………………………………………………………………………………. 332

Строки с данными NMEA………………………………………………………………………………………………… 332

Некоторые основные представления данных о широте и долготе……………………………… 334

Публикация данных GPS/GNSS в ROS…………………………………………………………………………………… 335

Пакет ROS: nmea_navsat_driver……………………………………………………………………………………… 335

Установка пакета nmea_navsat_driver…………………………………………………………………………… 336

Изучение документации к пакетам ROS………………………………………………………………………… 337

Запуск узла nmea_serial_driver с параметрами……………………………………………………………. 338

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

Вопросы……………………………………………………………………………………………………………………………………. 339

Глава 18. Устройства LIDAR и данные, которые они предоставляют…… 340

Общие сведения……………………………………………………………………………………………………………………….. 340

Основные сведения об устройствах LIDAR………………………………………………………………………….. 340

Ограничения LIDAR………………………………………………………………………………………………………………… 341

Типы LIDAR……………………………………………………………………………………………………………………………… 342

Однонаправленный (одноточечный) LIDAR…………………………………………………………………. 342

2D-LIDAR………………………………………………………………………………………………………………………….. 343

3D-LIDAR………………………………………………………………………………………………………………………….. 344

LIDAR, установленный на роботе-пылесосе………………………………………………………………… 344

Критерии выбора LIDAR………………………………………………………………………………………………………… 346

Данные LIDAR: сообщение sensor_msgs::LaserScan……………………………………………………………. 347

Факторы, которые необходимо учитывать при монтаже устройств LIDAR……………………… 349

Установка, запуск и испытание распространенной модели LIDAR…………………………………… 350

Действия по настройке RPLIDAR…………………………………………………………………………………… 351

Визуализация сообщения LaserScan……………………………………………………………………………………… 353

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

Вопросы……………………………………………………………………………………………………………………………………. 356

Глава 19. Реальное зрение с помощью видеокамер………………………………. 357

Общие сведения……………………………………………………………………………………………………………………….. 357

Что такое изображение?………………………………………………………………………………………………………….. 358

Атрибуты изображения…………………………………………………………………………………………………… 359

Координаты пиксела……………………………………………………………………………………………………….. 359

Проверка наличия или установка необходимого программного обеспечения………………….. 360

ROS Kinetic………………………………………………………………………………………………………………………… 360

ROS Melodic………………………………………………………………………………………………………………………. 361

Тестирование OpenCV в ROS………………………………………………………………………………………………….. 362

Программное обеспечение для обработки изображений (OpenCV) и ROS………………………… 363

Шаг 1. Публикация изображений в ROS………………………………………………………………………………… 364

Установка usb_cam_node………………………………………………………………………………………………… 364

Запуск usb_cam_node………………………………………………………………………………………………………. 364

Тестирование выходного сигнала камеры…………………………………………………………………….. 366

Шаг 2. Подпишитесь на сообщение об изображении в другом узле…………………………………… 367

Создайте свой пакет ROS для видеонаблюдения………………………………………………………….. 367

Написание кода для подписчика на сообщения с изображением……………………………….. 368

Шаг 3. С помощью cv-bridge преобразуйте изображение RGB, которое использует ROS, в изображение BGR, с которым может работать OpenCV…………………………………………………………………………………………………………………….. 369

Шаг 4. Выполните необходимые операции с изображением………………………………………………. 369

Шаг 5. Публикуйте любые данные, не относящиеся к изображению,
в виде отдельного сообщения ROS…………………………………………………………………………………………. 370

Шаг 6. Преобразуйте измененное изображение обратно в формат RGB…………………………… 370

Шаг 7. Опубликуйте итоговое изображение в отдельном топике……………………………………….. 371

Еще немного про обработку изображений……………………………………………………………………………. 371

Ядра, диафрагмы и блоки……………………………………………………………………………………………….. 371

Важность работы с копиями вместо оригинальных изображений……………………………… 372

Несколько слов об освещении………………………………………………………………………………………… 373

Ревизия шага 4 с включением большего количества операций OpenCV……………………………. 373

Преобразование цветового формата: cvtColor()…………………………………………………………… 374

Размытие изображений: blur(), medianBlur(), GaussianBlur()……………………………………….. 374

Выделение краев: Canny()……………………………………………………………………………………………….. 375

От определения краев на изображении к числовым значениям: HoughLinesP()………… 376

Маскирование изображения: bitwise_and()…………………………………………………………………… 380

Фильтрация по цвету: cvtColor() и inRange()………………………………………………………………………… 383

Полезные инструменты ROS…………………………………………………………………………………………………… 387

Расширенные функции OpenCV и не только…………………………………………………………………………. 387

Распознавание изображений с помощью облачных технологий………………………………………… 388

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

Вопросы……………………………………………………………………………………………………………………………………. 389

Глава 20. Совместное использование различных датчиков………………….. 390

Общие сведения……………………………………………………………………………………………………………………….. 390

Доступно о совместном использовании датчиков………………………………………………………………… 391

Датчик абсолютной ориентации Bosch BN0055………………………………………………………………….. 391

Предоставляемые данные……………………………………………………………………………………………….. 392

Улучшенная одометрия…………………………………………………………………………………………………… 392

Интеграция BN0055: оборудование и издатель ROS……………………………………………………. 393

Интеграция BN0055: узел одометрии…………………………………………………………………………….. 394

Шаг 1. Подписаться на сообщение IMU………………………………………………………………………… 395

Шаг 2. Проверить, что поле ориентации не помечено как “do not use” (не использовать) 395

Шаг 3. Преобразовать кватернионы в углы Эйлера…………………………………………………….. 396

Шаг 4. Сохранить информацию о смещении, если это первое сообщение IMU………… 396

Шаг 5.1. Если это НЕ первое сообщение IMU, сохранить курс IMU………………………….. 397

Шаг 5.2. Передать новое значение курса IMU в функцию расчета параметров одометрии         397

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

Фильтр Калмана………………………………………………………………………………………………………………. 398

Ковариационная матрица……………………………………………………………………………………………….. 401

Ковариационные матрицы в сообщениях ROS……………………………………………………………… 402

Узел robot_pose_ekf node………………………………………………………………………………………………………… 403

Установка robot_pose_ekf……………………………………………………………………………………………….. 404

Запуск robot_pose_ekf……………………………………………………………………………………………………… 404

Последнее замечание о преобразованиях и roslaunch………………………………………………….. 405

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

Вопросы……………………………………………………………………………………………………………………………………. 406

Часть V. Разработка автономного робота…………………………. 407

Глава 21. Сборка и программирование автономного робота………………… 409

Общие сведения……………………………………………………………………………………………………………………….. 409

Раздел 1. Создание физической платформы для робота……………………………………………………… 410

Платформа для робота: общий обзор и список деталей……………………………………………………… 411

Модули, объединяющие в себе колесо и двигатель……………………………………………………… 413

Драйвер(ы) двигателя………………………………………………………………………………………………………. 414

Ролик (третье колесо робота)………………………………………………………………………………………….. 414

Аккумуляторы и зарядное устройство…………………………………………………………………………… 414

Шасси/основание…………………………………………………………………………………………………………….. 415

Компьютеры……………………………………………………………………………………………………………………… 416

LIDAR или другой датчик расстояния…………………………………………………………………………… 416

Колесные энкодеры…………………………………………………………………………………………………………. 417

IMU (инерциальный измерительный блок)……………………………………………………………………. 417

Преобразователь напряжения для компьютера……………………………………………………………. 417

Коммутационная плата для колодки GPIO……………………………………………………………………. 418

Видеокамера…………………………………………………………………………………………………………………….. 418

Вольтметр для контроля напряжения аккумулятора……………………………………………………. 419

Различные материалы……………………………………………………………………………………………………… 420

Сборка платформы для робота………………………………………………………………………………………………. 420

Подготовьте компьютер…………………………………………………………………………………………………… 421

Подготовьте колесные модули……………………………………………………………………………………….. 421

Продумайте схему расположения компонентов…………………………………………………………… 422

Подготовьте шасси…………………………………………………………………………………………………………… 422

Установите колесные модули и ролик…………………………………………………………………………… 422

Установите драйвер двигателя, клеммные колодки и источник питания для компьютера……….. 424

Подготовьте коммутационную плату для колодки GPIO…………………………………………….. 424

Установите компьютер, коммутационную плату для колодки GPIO и IMU………………. 424

Соедините все блоки проводами и установите аккумулятор………………………………………. 425

Установите LIDAR и видеокамеру…………………………………………………………………………………. 425

Еще несколько советов……………………………………………………………………………………………………………. 427

Раздел 2. Программирование робота…………………………………………………………………………………….. 428

Программирование: общие замечания…………………………………………………………………………… 428

Программирование робота: подробная инструкция…………………………………………………….. 429

  1. Создать папку проекта……………………………………………………………………………………….. 430
  2. Получить данные датчиков для публикации……………………………………………………. 430
  3. Настроить управление платформой с помощью пульта ДУ…………………………… 432
  4. Отслеживать перемещение робота и публиковать данные о местоположении 435
  5. Обеспечить перемещение робота по путевым точкам
    (без обхода препятствий)……………………………………………………………………………………….. 436
  6. Составьте карту окружения робота………………………………………………………………….. 438
  7. Загрузить сохраненную карту с помощью файлов запуска……………………………. 439
  8. Добиться автономной навигации робота в пределах карты…………………………… 440

Запуск автономного робота!………………………………………………………………………………………………….. 441

Некоторые советы по устранению неполадок………………………………………………………………. 441

Что дальше?……………………………………………………………………………………………………………………………… 442

Обход динамических препятствий…………………………………………………………………………………. 442

ПИД-регуляторы………………………………………………………………………………………………………………. 443

Главный контроллер, который управляет различными процедурами или задачами.. 443

Реализация преобразования map в odom (полная локализация)………………………………… 443

Следите за новостями в Интернете…………………………………………………………………………………. 443

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

Приложение. Описание электронного архива………………………………………. 445

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

Lloyd Brombach

Ллойд Бромбах — инженер, программист и энтузиаст электроники и робототехники. Участвовал в соревнованиях по робототехнике, таких как финансируемый НАСА конкурс Lunar Regolith Excavation Challenge 2007 и 27-й конкурс Intelligent Ground Vehicle Challenge.