Как называются правила придуманные экспертами для решения прикладных задач

Обучение с подкреплением для реальных задач

У37 Обучение с подкреплением для реальных задач: Пер. с англ. — СПб.:
БХВ-Петербург, 2023. — 400 с.: ил.

Книга посвящена промышленно-ориентированному применению обучения
с подкреплением (Reinforcement Learning, RL). Объяснено, как обучать промыш-
ленные и научные системы решению любых пошаговых задач методом проб и
ошибок — без подготовки узкоспециализированных учебных множеств данных
и без риска переобучить или переусложнить алгоритм. Рассмотрены марковские
процессы принятия решений, глубокие Q-сети, градиенты политик и их вычисле-
ние, методы устранения энтропии и многое другое. Данная книга — первая на рус-
ском языке, где теоретический базис RL и алгоритмы даны в прикладном, отрасле-
вом ключе.

Для аналитиков данных
и специалистов по искусственному интеллекту

УДК 004.43
ББК 32.973.26-018.1

Группа подготовки издания:

Руководитель проекта Олег Сивченко
Зав. редакцией Людмила Гауль
Перевод с английского Екатерины Черских
Редактор Анна Кузьмина
Компьютерная верстка Ольги Сергиенко
Оформление обложки Зои Канторович

© 2022 BHV
Authorized Russian translation of the English edition of Reinforcement Learning ISBN 9781098114831
© 2021 Winder Research and Development Ltd.
This translation is published and sold by permission of O’Reilly Media, Inc., which owns or controls all rights to publish
and sell the same.

Авторизованный перевод с английского языка на русский издания Reinforcement Learning ISBN 9781098114831
© 2021 Winder Research and Development Ltd.
Перевод опубликован и продается с разрешения компании-правообладателя O’Reilly Media, Inc.

«БХВ-Петербург», 191036, Санкт-Петербург, Гончарная ул., 20

ISBN 978-1-098-11483-1 (англ.) © Winder Research and Development Ltd., 2021
ISBN 978-5-9775-6885-2 (рус.)
© Перевод на русский язык, оформление.
ООО «БХВ-Петербург», ООО «БХВ», 2023

Цель . 21
Кому следует прочитать эту книгу. 22
Руководящие принципы и стиль . 22
Предварительная подготовка. 24
Объем и план. 24
Дополнительные материалы. 25
Условные обозначения, используемые в этой книге. 26

Аббревиатуры. 26
Математические обозначения. 27

Глава 1. Для чего нужно обучение с подкреплением. 29

Почему сейчас. 30
Машинное обучение. 31
Обучение с подкреплением . 32

Когда следует использовать обучение с подкреплением? . 33
Варианты применения обучения с подкреплением . 35
Таксономия подходов обучения с подкреплением. 37
Без модели или на основе модели . 37
Как агенты используют и обновляют свою стратегию. 38
Дискретные или непрерывные действия . 39
Методы оптимизации . 39
Оценка и улучшение политики. 40
Фундаментальные концепции обучения с подкреплением. 41
Первый RL-алгоритм . 41

Оценка ценности. 42
Ошибка предсказания. 43
Правило обновления веса . 43
RL — это то же самое, что ML? . 44
Награда и отклик. 45
Отложенные награды . 46
Ретроспектива . 46
Обучение с подкреплением как дисциплина . 47
Резюме . 49
Дополнительные материалы для чтения . 49
Использованные источники. 50

Глава 2. Марковские процессы принятия решений,
динамическое программирование и методы Монте-Карло . 53

Алгоритм многорукого бандита. 53
Разработка наград . 53
Оценка стратегии: функция ценности. 54
Совершенствование политики: выбор лучшего действия. 57
Моделирование среды . 58
Запуск эксперимента . 59
Улучшение ε-жадного алгоритма . 61

Марковские процессы принятия решений . 62
Контроль запасов . 64
Таблица переходов . 65
Граф переходов . 66
Матрица переходов. 66
Симуляция управления запасами . 68

Политики и функции ценности . 70
Дисконтированные вознаграждения . 70
Прогнозирование вознаграждений с помощью функции ценности состояния. 71
Моделирование с использованием функции ценности состояния . 73
Прогнозирование вознаграждений с помощью функции ценности действия. 75
Оптимальные политики. 76

Генерирование политики Монте-Карло . 78
Итерация по ценности с динамическим программированием. 80

Реализация итерации по ценности. 82
Результаты итерации по ценнности . 84
Резюме . 85
Дополнительные материалы для чтения . 86
Использованные источники. 86

Глава 3. Обучение с учетом временных различий, Q-обучение
и n-шаговые алгоритмы. 87

Обучение с учетом временных различий: формулировка подхода. 88
Q-обучение . 90
SARSA . 92
Q-обучение против SARSA. 93
Пример использования: автоматическое масштабирование контейнеров приложений
для снижения затрат . 96

Отраслевой пример: торги рекламы в режиме реального времени. 98
Определение марковского процесса принятия решения . 98
Результаты торгов в режиме реального времени . 99
Дальнейшие улучшения . 101

Расширения для Q-обучения . 102
Двойное Q-обучение. 102
Отложенное Q-обучение . 103
Сравнение стандартного, двойного и отложенного Q-обучения. 103
Обучение с подкреплением на основе противодействия . 104

n-Шаговые алгоритмы. 105
n-Шаговые алгоритмы в распределенных средах . 108

Трассировки соответствия . 109

Расширения для трассировки соответствия . 112
Алгоритм обучения Q(λ) Уоткинса . 112
Нечеткие стирания в алгоритме обучения Q(λ) Уоткинса . 113
Быстрое Q-обучение . 113
Накопление или замена трассировок соответствия . 113

Резюме . 114
Дополнительные материалы для чтения . 114
Использованные источники. 114

Глава 4. Глубокие Q-сети. 117

Архитектуры глубокого обучения . 118
Основные положения . 118
Архитектуры нейронных сетей. 119
Фреймворки глубокого обучения . 120
Глубокое обучение с подкреплением. 121

Глубокое Q-обучение . 122
Воспроизведение опыта . 122
Клоны Q-сети . 123
Архитектура нейронной сети. 123
Внедрение глубокой Q-сети. 124
Пример: глубокая Q-сеть в среде CartPole. 125
Зачем обучаться онлайн? . 127
Что лучше? Глубока Q-сеть против Q-обучения . 128
Практический пример: сокращение энергопотребления в зданиях . 128

Радужная DQN . 130
Распределительное RL. 130
Воспроизведение приоритетного опыта . 132
Зашумленные сети . 133
Дуэльные сети . 133

Пример: радужная глубокая Q-сеть в Atari Games . 134
Результаты . 134
Обсуждение . 136

Другие улучшения глубокой Q-сети. 138
Улучшение исследования. 138
Повышение вознаграждения. 139
Обучение на основе автономных данных . 140

Резюме . 142
Дополнительные материалы для чтения . 143
Использованные источники. 143

Глава 5. Методы градиента политики . 145

Преимущества прямого изучения политики . 145
Как рассчитать градиент политики . 146
Теорема о градиенте политики. 147
Функции политики . 149

Линейные политики. 150
Логистическая политика . 150
Политика softmax. 151

Произвольные политики . 152

Основные реализации . 152
Метод Монте-Карло (алгоритм REINFORCE) . 153
Пример: алгоритм REINFORCE в среде CartPole. 153
Алгоритм REINFORCE с базовыми показателями . 154
Пример: алгоритм REINFORCE с базовыми показателями в среде CartPole . 156
Уменьшение градиентной дисперсии . 158
n-Шаговый и улучшенный алгоритмы «актор — критик» . 159
Пример: n-шаговый алгоритм «актор — критик» в среде CartPole . 161
Темпы затухания ценностного обучения по сравнению с темпами
ослабления политики. 163
Трассировки соответствия алгоритма «актор — критик». 164
Пример: трассировка соответствия требованиям алгоритма «актор — критик»
в среде CartPole . 165
Сравнение основных алгоритмов градиента политики . 166

Отраслевой пример: автоматическая продажа товаров клиентам . 166
Рабочее окружение: корзина заказов, написанная при помощи библиотеки Gym . 167
Ожидания. 168
Результаты из среды «Корзина покупок». 169

Резюме . 172
Дополнительные материалы для чтения . 173
Использованные источники. 173

Глава 6. Другие методы. 175

Алгоритмы, действующие вне политик. 175
Выборка по значимости. 176
Поведенческие и целевые политики . 178
Q-обучение, действующее вне политики. 178
Градиентное обучение с учетом временных различий. 179
Жадный GQ-алгоритм . 180
Алгоритм «актор — критик» вне политики . 181

Детерминированные градиенты политики . 182
Обычные детерминированные градиенты политики. 182
Глубокие детерминированные градиенты политики . 184
Вывод DDPG . 184
Внедрение DSP . 185
Дважды отложенный DPG . 188
Отложенные обновления политики . 188
Ограниченное двойное Q-обучение . 189
Сглаживание целевой политики. 189
Реализация TD3 . 190
Практический пример: рекомендации на основе отзывов . 192
Улучшения DPG. 193

Методы доверительной области. 194
Дивергенция Кульбака — Лейблера . 196
Эксперименты по дивергенции Кульбака — Лейблера . 196
Естественные градиенты политики и оптимизация политики
доверительной области. 197
Проксимальная оптимизация политики. 200
Усеченная цель PPO . 201
Ценностная функция PPO и цели разведки . 203

Пример: использование сервоприводов для Real-Life Reacher . 205
Описание эксперимента . 205
Реализация алгоритма RL. 206
Повышение сложности алгоритма . 208
Настройка гиперпараметров в моделировании . 209
Результирующие политики . 210

Другие алгоритмы градиента политики . 212
Алгоритм Retrace (λ). 212
Алгоритм ACER . 212
Алгоритм ACKTR . 213
Эмпатические методы . 214

Расширения для алгоритмов градиента политики. 214
Квантильная регрессия в алгоритмах градиента политики. 215

Резюме . 215
Какой алгоритм следует использовать. 215
Замечание об асинхронных методах . 216

Дополнительные материалы для чтения . 216
Использованные источники. 217

Глава 7. Изучение всех возможных политик
с помощью энтропийных методов. 221

Что такое энтропия? . 221
Максимальная энтропия обучения с подкреплением. 222
Мягкий «актор — критик» . 223

Детали реализации SAC и дискретные пространства действий . 224
Автоматическая регулировка температуры. 224
Практический пример: автоматическое управление трафиком
для сокращения очередей. 225
Расширения методов максимальной энтропии . 226
Другие меры энтропии (и ансамбли) . 226
Оптимистичное исследование с использованием верхней границы
двойного Q-обучения. 227
Играем с воспроизведением опыта . 227
Мягкий градиент политики . 227
Мягкое Q-обучение (и производные). 228
Обучение согласованности пути . 228
Сравнение производительности: SAC против PPO . 228
Как энтропия способствует исследованиям? . 230
Как температурный параметр влияет на исследование? . 233
Отраслевой пример: обучение вождению автомобиля с дистанционным управлением . 235
Описание задачи . 235
Минимизация времени обучения . 236
Выразительные действия . 238
Поиск гиперпараметров. 239
Финальная политика . 240
Дальнейшие улучшения . 240
Резюме . 241
Эквивалентность градиентов политики и мягкого Q-обучения . 242
Что это означает для будущего. 242
Что это значит сейчас? . 242
Использованные источники. 243

Глава 8. Улучшение процесса обучения агента . 245

Переосмысление марковских процессов принятия решений . 246
Частично наблюдаемый марковский процесс принятия решений . 246
Предсказание доверительного состояния. 247
Практический пример: POMDP в автономных транспортных средствах. 248
Контекстные MDP . 249
MDP с изменяющимися действиями. 249
Регуляризованные MDP . 250

Иерархическое обучение с подкреплением. 250
Наивный HRL. 251
Высокоуровневые и низкоуровневые иерархии с внутренними наградами. 252
Навыки обучения и неконтролируемое RL . 254
Использование навыков в HRL. 255
Выводы HRL . 255

Мультиагентное обучение с подкреплением . 256
Фреймворки MARL . 257
Централизованное или децентрализованное . 259
Алгоритмы с одним агентом. 260
Практический пример: использование децентрализованного обучения
с одним агентом в беспилотном летательном аппарате . 261
Централизованное обучение, децентрализованное выполнение . 262
Децентрализованное обучение . 263
Другие комбинации . 264
Проблемы MARL . 265
Выводы о MARL . 266

Экспертное руководство . 267
Клонирование поведения . 267
Имитационное RL . 267
Обратное RL . 268
Обучение по учебной программе . 270

Другие парадигмы . 271
Метаобучение . 271
Трансферное обучение . 272

Резюме . 273
Дополнительные материалы для чтения . 274
Использованные источники. 275

Глава 9. Практическое обучение с подкреплением . 279

Жизненный цикл проекта RL . 279
Определение жизненного цикла . 281
Жизненный цикл науки о данных . 281
Жизненный цикл обучения с подкреплением . 282

Определение проблемы: что такое проект RL? . 284
Проблемы с RL являются последовательными . 284
Проблемы RL имеют стратегический характер . 285
Низкоуровневые индикаторы RL . 286
Сущность . 286
Среда . 286
Состояние . 287

Действие . 287
Количественная оценка успеха или неудачи. 287
Типы обучения . 288
Онлайн-обучение . 288
Автономное или пакетное обучение . 288
Параллельное обучение . 290
Обучение без сброса. 291
Проектирование и доработка RL. 292
Процесс . 293
Инженерия среды. 293
Реализация . 294
Моделирование . 294
Взаимодействие с реальной жизнью. 295
Инжиниринг состояния или обучение представлениям . 296
Перспективные модели обучения . 297
Ограничения. 297
Преобразование (уменьшение размерности, автоэнкодеры и модели мира) . 298
Разработка политики . 299
Дискретные состояния . 300
Непрерывные состояния . 301
Преобразование в дискретные состояния. 303
Пространства смешанных состояний. 304
Сопоставление политик с пространствами действий . 305
Бинарные действия . 305
Непрерывные действия . 306
Гибридные пространства действий. 306
Когда выполнять действия. 307
Обширные пространства действий . 307
Исследование. 308
Является ли внутренняя мотивация исследованием. 309
Количество посещений (выборка) . 310
Прирост информации (сюрприз) . 310
Прогноз состояния (любопытство или саморефлексия) . 311
Любопытные задачки . 311
Случайные вложения (сети случайной дистилляции). 312
Расстояние до новизны (эпизодическое любопытство) . 313
Выводы по разведке . 313
Разработка вознаграждений . 314
Рекомендации по разработке вознаграждений . 315
Формирование вознаграждения . 316
Общие награды . 317
Выводы о вознаграждении. 318
Резюме . 318
Дополнительные материалы для чтения . 319
Использованные источники. 320

Глава 10. Этапы в обучении с подкреплением . 325

Реализация. 325
Фреймворки . 326
Фреймворки RL. 326
Другие фреймворки . 328

Масштабирование RL. 329
Распределенное обучение (Gorila) . 330
Обучение на одной машине (A3C, PAAC) . 331
Распределенное воспроизведение (Ape-X). 333
Синхронное распределение (DD-PPO) . 333
Повышение эффективности использования (IMPALA, SEED) . 334
Масштабирование сделанных выводов . 336

Оценка. 337
Показатели эффективности политики . 338
Статистические сравнения политик. 340
Показатели производительности алгоритма . 343
Измерения производительности для конкретных задач. 343
Объяснимость . 344
Выводы оценки . 345

Развертывание. 346
Цели. 346
Цели на разных этапах развития . 346
Лучшие практики. 347
Иерархия потребностей. 348
Архитектура . 349
Вспомогательные инструменты. 351
Разработка против покупки . 352
Мониторинг. 352
Регистрация и отслеживание . 353
Непрерывная интеграция и непрерывная доставка . 353
Отслеживание экспериментов . 354
Настройка гиперпараметров . 355
Развертывание нескольких агентов. 355
Развертывание политик. 356
Безопасность, защита и этика . 357
Безопасное RL. 357
Защитное RL . 359
Этическое RL . 361

Резюме . 363
Дополнительные материалы для чтения . 364
Использованные источники. 365

Глава 11. Выводы и будущее. 369

Советы и рекомендации . 369
Формулирование задачи. 369
Ваши данные . 370
Тренировка . 371
Оценка. 372
Развертывание . 373

Отладка . 373
Алгоритм не может решить проблемы среды! . 375
Мониторинг для отладки. 376

Будущее обучения с подкреплением . 377
Рыночные возможности RL . 377
Будущее RL и направления исследований . 379

Исследования в промышленности . 379
Исследования в науке. 381
Этические стандарты. 383
Заключительные замечания . 384
Дальнейшие шаги. 384
Теперь ваша очередь. 385
Дополнительные материалы для чтения . 385
Использованные источники. 386

Приложение 1. Градиент логистической политики для двух действий. 389

Приложение 2. Градиент политики softmax. 393

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

«Обучение с подкреплением — одна из самых захватывающих областей машинного
обучения и, к сожалению, также одна из самых сложных. Обучение с подкреплени-
ем отлично справляется с задачей выявления бэкграунда, ландшафта и возможно-
стей использования этой новаторской техники способами, которые значительно
улучшат возможности специалистов по обработке данных для своего бизнеса».

Дэвид Арончик,
соучредитель Kubeflow

«Книга доктора Фила Уиндера об обучении с подкреплением — это глоток свежего
воздуха. Он превратил невероятно динамичную тему в простую для понимания
книгу, которая фокусируется на идеях и понимании читателем. Эта книга интерес-
на тем, насколько уместно обучение с подкреплением для обучения в неопределен-
ной среде».

Основатель Your Chief Scientist, инструктор и автор книги
«Вдумчивое машинное обучение»

«Книга, необходимая для всех, кто хочет применить методы обучения с подкрепле-
нием к реальным задачам. Она ведет читателя от первых принципов к современно-
му состоянию с множеством практических примеров и подробных объяснений».

Дэвид Фостер,
партнер Applied Data Science Partners
и автор книги «Генеративное глубокое обучение»

«Отличная книга Фила Уиндера. Проверенный природой метод обучения через
действия наконец нашел свое место в стандартном наборе инструментов разработ-
чика программного обеспечения. Обучение с подкреплением — это маховик искус-
ственного интеллекта, и эта книга направлена на то, чтобы привнести эту перспек-
тиву в приложения в промышленности и бизнесе».

Дэнни Ланге,
старший вице-президент по искусственному интеллекту, Unity

Для Эммы, Евы и Коры

Доктор Фил Уиндер (Dr. Phil Winder) — многопрофильный инженер-програм-
мист, специалист по обработке данных и генеральный директор Winder Research1,
консалтинговой компании в области облачных технологий. Он помогает стартапам
и предприятиям улучшать свои процессы, основанные на данных, платформы и
продукты. Фил специализируется на внедрении машинного обучения для облачных
вычислений в производственной среде и был одним из первых сторонников движе-
ния MLOps.
Он восхитил тысячи инженеров своими учебными курсами по data science в госу-
дарственных и частных организациях, а также на платформе онлайн-обучения
O’Reilly. Курсы Фила посвящены использованию науки о данных в промышленно-
сти и охватывают широкий спектр актуальных, но практических тем, от очистки
данных до глубокого обучения с подкреплением. Он регулярно выступает с докла-
дами и активно участвует в сообществе специалистов по анализу данных.
Фил имеет докторскую степень и степень магистра. Он получил степень в элек-
тронной инженерии в Университете Халла; живет в Йоркшире (Великобритания) со
своим пивоваренным оборудованием и семьей.

1 См. https://winderresearch.com/?.utm_source=oreilly&utm_medium.=book&utm_campaign=rl.

Обучение с подкреплением (reinforcement learning, RL) — это парадигма машинно-
го обучения (machine learning, ML), которая способна оптимизировать последова-
тельные решения. RL интересно тем, что имитирует то, как мы, люди, учимся. Мы
инстинктивно способны изучать стратегии, которые помогают нам справляться со
сложными задачами, такими как езда на велосипеде или сдача экзамена по матема-
тике. RL пытается скопировать этот процесс, взаимодействуя с окружающей сре-
дой для изучения стратегий.
В последнее время компании применяют алгоритмы машинного обучения для при-
нятия единоразовых решений. Они обучаются на данных, чтобы принять лучшее на
текущий момент решение. Однако часто правильное в настоящий момент решение
может оказаться не лучшим решением в долгосрочной перспективе. Да, полная
ванна мороженого осчастливит вас в краткосрочной перспективе, но на следующей
неделе вам придется пропадать в тренажерном зале. Точно так же кликбейтные
рекомендации могут давать самую высокую кликабельность, но в долгосрочной
перспективе такие статьи воспринимаются как мошенничество и наносят ущерб
долгосрочному вовлечению или удержанию читателя.
RL интересно тем, что позволяет изучить долгосрочные стратегии и применить их
к сложным промышленным задачам. Как компании, так и специалисты-практики
могут преследовать цели, которые напрямую связаны с бизнесом, такие как извле-
чение прибыли, наращивание количества пользователей и их удержание, а не тех-
нические показатели оценки, такие как точность или F-мера. Проще говоря, ре-
шение многих проблем зависит от последовательного принятия решений. ML не
предназначено для решения этих проблем, RL — предназначено.

Я написал эту книгу, потому что прочитал о стольких удивительных примерах ис-
пользования RL для решения, казалось бы, невыполнимых задач. Правда, все эти
примеры взяты из академических исследовательских работ, а книги, которые я впо-
следствии прочитал, были либо ориентированы на академические круги, либо
представляли собой расхваленные автором листинги. Мало кто из авторов писал
с промышленной точки зрения или объяснял, как использовать RL в производст-
венных условиях. Я знал, насколько мощной может быть эта технология, поэтому
решил написать книгу об использовании RL в промышленности.

Когда я только приступил к написанию, я хотел сосредоточиться на эксплуатаци-
онных аспектах, но быстро понял, что вряд ли кто-нибудь в отрасли слышал о RL,
не говоря уже о том, чтобы использовать обечение с подкреплением в производст-
ве. Кроме того, в ходе исследования моей аудитории я обнаружил, что многие
инженеры и специалисты по обработке данных никогда даже не видели многих
основополагающих алгоритмов. Таким образом, эта книга превратилась частично
в фундаментальное объяснение, а частично — в практические советы по реализа-
ции. Я надеюсь, что эта книга вдохновит и подтолкнет к использованию RL в про-
мышленной сфере.

Считаю, что это первая книга, в которой обсуждаются проблемы практического
применения RL, и, безусловно, единственная книга, которая объединила алгорит-
мические и операционные разработки в целостную картину процесса разработ-
ки RL.

Кому следует прочитать эту книгу?

Цель этой книги — продвигать использование RL в производственных системах.
Если вы (сейчас или в будущем) создаете продукты в области RL, будь то исследо-
вания, разработки или прикладные вещи, то эта книга для вас. Это также означает,
что я написал книгу, скорее, для практиков, чем для людей из академических кру-
гов.

Руководящие принципы и стиль

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

Во-первых, я полностью избегаю листингов. Я считаю, что в большинстве случаев
книги не подходят для полотен кода (книги по разработке программного обеспече-
ния являются очевидным исключением). Это противоречит общепринятому мне-
нию, но лично мне надоело пролистывать страницы и страницы кода. Я покупаю
книги, чтобы узнать мнение автора, то, как авторы объясняют концепции, идеи.
Другая причина не печатать код заключается в том, что многие реализации, осо-
бенно в последующих главах, действительно довольно сложны, с большим количе-
ством деталей оптимизации в реализации, которые отвлекают от основных идей,
которыми я хочу поделиться. В любом случае вы обычно используете библиотеч-
ную реализацию. Кроме того, есть алгоритмы, которые еще не реализованы, пото-
му что они слишком новы или слишком сложны для включения в стандартные биб-
лиотеки. Исходя из этих и других причин, предупреждаю, что это не типичная кни-
га в жанре «покажи мне код».

Но не волнуйтесь, это не значит, что кода вообще нет. Есть, но он находится в со-
путствующем репозитории вместе с множеством других практических примеров,
практических руководств, обзоров, сборников статей и многих других материалов
(см. разд. «Дополнительные материалы» далее в предисловии).

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

Второй принцип, которого я придерживался, касался математики. RL — это в выс-
шей степени математическая тема, потому что обычно намного проще объяснить
алгоритм с помощью нескольких строк метаматематических выражений, чем двад-
цатью строками кода. Но я полностью осознаю, что математика иногда может
казаться чужеродным языком. Как и любой другой язык программирования, мате-
матика имеет собственный синтаксис, предполагаемые знания и встроенные функ-
ции, которые вы должны знать, прежде чем сможете полностью оценить их.

Поэтому на протяжении всей этой книги я не уклоняюсь от математики, особенно
при объяснении алгоритмов, фундаментальных для RL, потому что они являются
важны сами по себе. Однако я стараюсь ограничить математику там, где могу, и
давать длинные объяснения там, где не могу. Обычно я стараюсь следовать обозна-
чениям, предоставленным Томасом и Окалом1, — марковской нотацией процесса
принятия решений, версией 1. Но я часто злоупотребляю обозначениями, чтобы
сделать все еще проще.

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

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

Четвертый принцип заключается в том, что я всегда пытаюсь указать на подводные
камни или сущности, которые могут пойти не так. Некоторые люди, с которыми я
разговаривал, считают, что это означает, будто RL не готово или я не верю в него;
оно готово, и я в это верю. Но жизненно важно понимать неизвестности и трудно-
сти, чтобы вы не переусердствовали и выделяли достаточно времени на выполне-
ние работы. Это определенно не «нормальная» разработка программного обеспече-

1 Thomas P. S., Okal D. A Notation for markov decision processes // ArXiv:1512.09075. — 2016. — September. —
URL: https://oreil.ly/VT7np.

ния. Так что везде, где вы видите «проблемы» или объяснения «как улучшить», это
существенная и важная информация. Неудача — лучший учитель.

Все это означает, что RL — довольно сложная тема, еще до того, как вы к ней при-
ступите. Чтобы читать эту книгу было максимально интересно, вам нужно немного
познакомиться с наукой о данных (data science) и машинным обучением, и вам по-
требуются небольшие математические знания.

Но не волнуйтесь, если этого у вас нет. Вы всегда сможете наверстать позже.
Я привожу много источников и ссылок для дальнейшего чтения и объясняю вспо-
могательные концепции там, где это имеет смысл. Обещаю, что вы все равно полу-
чите огромное количество знаний.

Книга охватывает весь ваш путь по внедрению продуктов RL в производство. Во-
первых, вам нужно изучить базовую структуру, на которой построено RL. Затем вы
перейдете к простым алгоритмам, использующим эту парадигму. Тогда вы сможете
узнать о все более совершенных алгоритмах, способных на большие подвиги. Затем
вам нужно подумать о том, как применить эти знания к вашей отраслевой задаче.
И наконец, вам необходимо разработать надежную систему, чтобы сделать ее жиз-
неспособной в эксплуатации.

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

Вот общее содержание, чтобы подогреть интерес.

Глава 1 «Для чего нужно обучение с подкреплением?». Книга начинается с акку-
ратного введения в историю и основы RL, вдохновленные другими научными
дисциплинами. Оно закладывает азы и дает обзор различных типов алгоритмов
в RL.

Глава 2 «Марковские процессы принятия решений, динамическое программиро-
вание и методы Монте-Карло». Более сложный материал начинается с главы,
в которой определяются фундаментальные концепции RL, включая марковские
процессы принятия решений, динамическое программирование и методы Мон-
те-Карло.

Глава 3 «Обучение с учетом временных различий, Q-обучение и n-шаговые алго-
ритмы». В этой главе вы перейдете к так называемым методам оценки, которые
призваны количественно охарактеризовать ценность пребывания в определен-
ном состоянии, базовый алгоритм, который доминирует во всех современных
системах RL.

Глава 4 «Глубокие Q-сети». Бо́льшая часть недавнего ажиотажа была вызвана
сочетанием методов оценки и глубокого обучения. Вы подробно изучите это со-
четание, и я обещаю, что вы будете удивлены производительностью этих алго-
ритмов.

Глава 5 «Методы градиента политики». Теперь вы узнаете о второй по попу-
лярности форме алгоритмов RL — методах градиента политики — которые при-
званы натолкнуть вас на параметризованную стратегию к повышению произво-
дительности. Основное преимущество состоит в том, что они могут справляться
с непрерывными действиями.

Глава 6 «Другие методы». У базовых алгоритмов градиента политики имеется
ряд проблем, но в этой главе рассматриваются и исправляются многие недостат-
ки, от которых они страдают. И для повышения эффективности вводится пер-
спективное обучение вне политики.

Глава 7 «Изучение всех возможных политик с помощью энтропийных методов».
Методы энтропии показали высокую надежность и позволяют вырабатывать
стратегии для сложных действий, таких как вождение автомобиля или управле-
ние транспортным потоком.

Глава 8 «Улучшение процесса обучения агента». Отступив от основных алго-
ритмов RL, в этой главе я расскажу, как вспомогательные компоненты могут
помочь в решении сложных проблем. Здесь я сосредоточусь на различных пара-
дигмах RL и альтернативных способах формулирования марковского процесса
принятия решений.

Глава 9 «Практическое обучение с подкреплением». Это первая из двух глав, по-
священных созданию производственных RL-систем. В данной главе вы позна-
комитесь с процессом разработки и реализации промышленных алгоритмов RL.
В ней описывается процесс, проектные решения и практические аспекты реали-
зации.

Глава 10 «Этапы в обучении с подкреплением». Если вам нужен совет о том, как
использовать продукты RL в производственной среде, эта глава для вас. Здесь
я углубляюсь в архитектурный проект, который вам следует рассмотреть, чтобы
сделать ваше решение масштабируемым и более надежным, а затем подробно
описываю ключевые аспекты, на которые вам нужно обратить внимание.

Глава 11 «Выводы и будущее». Последняя глава — это не просто резюме выше-
изложенного. Она содержит множество практических советов и приемов, кото-
рые вы найдете полезными во время вашего путешествия по RL, в ней также
представлены предложения для будущих исследований.

Я создал веб-сайт https://rl-book.com, чтобы систематизировать на нем все допол-
нительные материалы, сопровождающие эту книгу. Здесь вы найдете сопроводи-
тельный код, подробные статьи и рабочие таблицы, сравнения и обзоры технологии
RL, базы данных текущих тематических исследований RL и многое другое.

См. разд. «Руководящие принципы и стиль» ранее в предисловии, чтобы узнать, по-
чему в этой книге не напечатан код.
Причина создания целого веб-сайта, а не просто репозитория кода, заключалась
в том, что я считаю, что RL — это больше чем просто код. Это меняющий парадигму
способ мышления о том, как решения могут иметь долгосрочные последствия. Это
новый набор технологий, и для него нужна совершенно другая архитектура. По
всем этим и другим причинам дополнительная информация не помещается в репо-
зиторий. Она не подходит для печати, потому что может быстро меняться или ста-
новится просто неэффективной. Итак, я создал эту экосистему и уверен, что вы
найдете ее ценной. Обязательно просмотрите ее, и если чего-то не хватает, дайте
мне знать.

Условные обозначения,
используемые в этой книге

В этой книге используются следующие типографские условные обозначения:
курсив указывает на новые термины и иногда используется для выделения;
полужирный шрифт — URL-адреса, адреса электронной почты;
рубленый шрифт используется для обозначения определенных классов или сред
RL, обозначения элеменов программ, таких как переменные или имена функций,
базы данных, типы данных, переменные среды, инструкции и ключевые слова.

Данный элемент обозначает подсказку или совет.

Данный элемент обозначает общее замечание.

Данный элемент обозначает предупреждение или предостережение.

В обучении с подкреплением много аббревиатур, особенно когда речь идет о реа-
лизации алгоритмов.

В целом я предпочитаю использовать марковскую нотацию процесса принятия ре-
шений Томаса и Окала, версию 1. Однако я попытался еще больше упростить ее,
убрав такие формальности, как разграничение по времени, и расширив использова-
ние апострофа для обозначения текущего и следующего моментов. Во всей матема-
тической строгости эти концепции изложены в академических учебниках и статьях.

Как правило, фигурные буквы обозначают множество, а строчны́ е буквы — эле-
мент множества. Апостроф обозначает следующий временно́ й шаг. Прописные
буквы представляют функцию или константу.

Я отказываюсь от формальности выборки определенного состояния из случай-
ной переменной и вместо этого использую конкретную реализацию перемен-

ной, например s , чтобы облегчить читаемость уравнений. В литературе вы

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

Некоторые алгоритмы насыщены индексами, и это означает, что вам нужно буфе-
ризовать данные и обращаться к определенным точкам в получившемся буфере.
Когда я получаю эти алгоритмы, мне приходится прибегать к использованию
нижних индексов; например at будет означать действие в какой-то момент времени
или позиции t .

Если вы не привыкли читать уравнения, делайте это медленно. Сначала посмотри-
те, чтобы понять, что представлено каждым символом, а затем определите, что
в этом уравнении делается. Как и в случае с любым навыком, чем больше раз вы
будете выполнять его, тем проще станет для вас процесс выполнения. Знак «точка
равно» можно читать как «определяется как».

Изучая алгоритмы, прочтите их процедурно. Где возможно, я использую текст, но
во многих случаях уравнение оказывается более кратким. Символ ← в алгоритмах
читается как «обновить»; это предпочтительнее, потому что технически знак равен-
ства означает математическое равенство, например == в вашем программном
обеспечении. Большинство языков программирования злоупотребляют этой но-
тацией и используют символ равенства для обозначения как определения, так и
обновления.

Я решил представить алгоритмы в академическом псевдокоде, а не в стиле, приня-
том в программной инженерии. Я долго думал об этом, но в итоге есть три основ-
ные причины для этого решения. Во-первых, так алгоритмы представлены во всей
академической литературе. Я хотел, чтобы эта книга стала мостиком между про-
мышленным и академическим сообществом, и я думаю, что наличие еще одного
представления усилит этот разрыв. Во-вторых, эти алгоритмы более лаконичны
в академической форме, такова математика. Если бы вам пришлось преобразовать
математику в программный псевдокод, это привело бы к огромному количеству
циклов for и временны́ х переменных. Последняя причина в том, что ошибиться бы-
ло бы слишком легко. Несмотря на то что я упростил математику, псевдокод пред-
ставляет собой реальную реализацию. Преобразование реализаций, представлен-
ных в академических статьях, в программный псевдокод привело бы к слишком
большому количеству ошибок.

Для чего нужно
обучение с подкреплением?

Как люди учатся? Этот обманчиво простой вопрос сбивал с толку мыслителей на
протяжении тысячелетий. Греческий философ Платон и его ученик Аристотель за-
дались вопросом: находятся ли истина и знание внутри нас (рационализм) или они
пережиты (эмпиризм)? Даже сегодня, 2500 лет спустя, люди все еще пытаются от-
ветить на этот вечный вопрос.

Если бы люди уже всё знали, им не нужно было бы больше приобретать жизнен-
ный опыт. Люди могли бы проводить остаток своего земного времени, улучшая
жизнь, принимая правильные решения и размышляя над такими важными вопроса-
ми, как «где мои ключи?» и «я запер входную дверь?». Но как люди вообще полу-
чают эти знания? Вы можете научить знанию. А более высокий уровень среднего
образования ведет к лучшему обществу. Но всему нельзя научить. И на уроках,
и в жизни ученик должен переживать.

Маленькие дети вдохновляют в этом отношении. Им нужно испробовать ряд си-
туаций и результатов. В долгосрочной перспективе они начинают искать полезный
опыт и избегать пагубного (хочется надеяться). Они активно принимают решения и
оценивают результаты. Но жизнь ребенка загадочна, и награды часто вводят в за-
блуждение. Немедленная награда за то, что ребенок залезет в шкаф и съест печенье,
велика, но наказание будет суровее.

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

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

В этой главе представлено введение в обучение с подкреплением (я откладываю
формальное определение обучения с подкреплением до главы 2). Во-первых,

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

В этой книге я употребляю слово «инженер», чтобы абстрактно говорить обо
всех, кто использует свои навыки для разработки решения проблемы. Я имею
в виду инженеров-программистов, инженеров по обработке данных, специали-
стов по данным, исследователей и т. д.

Две причины обусловили необходимость и способность выполнять обучение с под-
креплением: доступ к большим объемам данных и возросшая скорость обработки
данных.

Вплоть до 2000 г. человеческие знания хранились на аналоговых устройствах, та-
ких как книги, газеты и магнитные ленты. Если бы вы сжали эти знания, то
в 1993 г. вам потребовалось бы 15,8 эксабайт пространства (один эксабайт равен
одному миллиарду гигабайт) [1]. В 2018 г. этот показатель увеличился до
33 зеттабайт (1 Збайт = 1 000 000 000 000 Гбайт). Поставщикам облачных услуг да-
же приходится прибегать к использованию жестких дисков размером с контейнер
для загрузки больших объемов данных [2].

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

В 1947 г. Дитрих Принц (Dietrich Prinz) работал на компанию Ferranti в Манчестере
(Великобритания). Там он помог спроектировать и сконструировать первую произ-
водственную версию манчестерского компьютера под названием Ferranti Mark 1 [3].
Он научился программировать Mark 1 под руководством Алана Тьюринга (Alan
Turing) и Сисели Попплуэлл (Cicely Popplewell). Под влиянием статьи Тьюринга на
эту тему в 1952 г. Принц выпустил шахматную программу, которая могла решать
единственный набор задач под названием «matein-2». Это шахматные композиции,
в которых игрок выбирает два хода, приводящих к мату в шахматах. Алгоритм
Принца тщательно перебирал все возможные позиции и вырабатывал решение
в среднем за 15–20 минут. Это реализация алгоритма Монте-Карло, описанного
в главе 2. Принц стал рассматривать шахматное программирование как «ключ к ме-
тодам, которые можно использовать для решения структурных или логистических
задач в других областях с помощью электронных компьютеров». Он был прав [4].

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

Для чего нужно обучение с подкреплением? | 31

Полное описание машинного обучения выходит за рамки этой книги. Но на ма-
шинном обучении основано обучение с подкреплением. Прочтите как можно
больше о машинном обучении, особенно о книгах, которые я рекомендую
в разд. «Дополнительные материалы для чтения » в конце этой главы.

Повсеместное распространение данных и доступность дешевых высокопроизводи-
тельных вычислений позволили исследователям пересмотреть алгоритмы 1950-х го-
дов. Они выбрали название «машинное обучение» (machine learning, ML), но такое
название не вполне удачно, потому что ML одновременно считается и дисципли-
ной, и набором методов. Я считаю машинное обучение детищем науки о данных
(data science), которая представляет собой всеобъемлющую научную область, изу-
чающую данные, генерируемые явлениями. Мне не нравится термин «искусствен-
ный интеллект» (ИИ — artificial intelligence, AI) по той же причине; достаточно
сложно определить, что такое интеллект, не говоря уже о том, как он воплощается.

ML начинается с большого количества информации в виде данных, полученных
в ходе наблюдений. Наблюдение представляет собой набор атрибутов в единой точ-
ке, которые описывают сущность. Например, в избирательном опросе одно наблю-
дение представляет собой предполагаемый голос одного человека. Для задачи фор-
мулирования рекомендаций наблюдением может быть щелчок по определенному
продукту. Инженеры используют ML-алгоритмы для интерпретации этой инфор-
мации и принятия решений.

При обучении с учителем метки представляют ответ на проблему для конкретного
наблюдения. Здесь алгоритм пытается использовать информацию, чтобы угадать
правильный результат. Обучение без учителя работает без меток, и вы принимаете
решения на основе характеристик данных. Я всегда рекомендую своим клиентам из
Winder Research стремиться к контролируемому обучению — например, путем оп-
латы или проведения экспериментов для поиска меток, — потому что, если у вас
нет основополагающей истины, вам будет сложно количественно оценить эффек-
тивность.

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

Учитывая эти описания, попробуйте научить ребенка кататься на велосипеде. Как
лучше всего это сделать? Согласно парадигме ML вы должны разметить множество
наблюдений. Вы можете посоветовать своему ребенку посмотреть видео с профес-
сиональными велосипедистами. Как только он просмотрит достаточное количество
видеороликов, вы, игнорируя любые его протесты о том, что ему было скучно,
можете проверить его способности в соответствии с некоторыми произвольными
техническими критериями успеха. Думаете, это сработает? Нет.

Несмотря на то что ML принципиально подходит для многих прикладных задач,
некоторые проблемы не поддаются машинному обучению. Лучшее решение, про-
должая предыдущий пример, — позволить своему ребенку попробовать самостоя-
тельно прокатиться. Некоторые его попытки ничем не увенчаются. В других случа-
ях у него что-то получится. Каждое решение будет сказываться на его представле-
нии о задаче. После достаточного количества попыток и определенных наставлений
он изучит стратегии, позволяющие максимизировать собственное определение
успеха. Вот в чем обучение с подкреплением превосходит обучение с учителем.

Обучение с подкреплением

Обучение с подкреплением (reinforcement learning, RL) поясняет, как принимать
наилучшие решения последовательно, в определенном контексте, чтобы максими-
зировать реальный показатель успеха. Лицо, принимающее решения, узнает об
этом методом проб и ошибок. Ему не говорят, какие именно решения принимать,
вместо этого он должен учиться самостоятельно, методом проб и ошибок. На
рис. 1.1 представлены четыре компонента RL, в главе 2 мы углубимся в подроб-
ности.

Рис. 1.1. Набросок четырех компонентов, необходимых для RL: агента, который совершает
действия в окружающей среде для наибольшего вознаграждения. Пример (а)

демонстрирует робота, который намеревается пройти через лабиринт, чтобы получить
монету. Пример (б) показывает приложение для электронной коммерции,
которое автоматически добавляет товары в корзины пользователей,
чтобы максимизировать прибыль

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

Для чего нужно обучение с подкреплением? | 33

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

Агент — это субъект, который принимает решения. Это может быть ваш ребенок,
какая-нибудь программа или, например, робот.

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

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

Вот еще пример: вы можете вознаградить робота за достижение цели или агента за
добавление нужного продукта в корзину. Все просто, правда? Но что делать, если
роботу требуется три дня, чтобы выйти из простого лабиринта, потому что он про-
водит бóльшую часть времени, нарезая круги? А если агент начнет добавлять все
подряд товары в корзину?

Такие процессы происходят и в мире животных. Они должны максимально увели-
чить свои шансы на выживание, чтобы передать свои гены потомству. Например,
как и большинству травоядных, лосям нужно много есть, чтобы выжить. Но
в 2011 г. в окрестностях Гётеборга (Швеция) нашли лося, застрявшего в ветвях де-
рева после того, как он наелся ферментированных яблок [5]. Система «вознаграж-
дения» лося, которая вызывает голод, дала сбой, потому что цель ее слишком ли-
шена конкретики. Нельзя есть все подряд, чтобы максимизировать свои шансы на
выживание. Все гораздо сложнее.

Эти примеры подводят нас к главной проблеме в RL, которая известна с тех пор,
как Ада Лавлейс (Ada Lovelace) впервые написала алгоритм для получения чисел
Бернулли. Как сказать машине, что она должна делать? Агенты RL часто остаются
крайними, потому что они оптимизируются не для того, что на самом деле нужно.
И пока я рекомендую вам максимально не усложнять награду. Многие задачи
предполагают естественную награду. В главе 9 эта проблема обсуждается более
подробно.

Итак, четыре компонента образуют марковский процесс принятия решений (Markov
decision process, MDP). MDP используют для того, чтобы сформулировать задачи,
даже не связанные с инженерией. В главе 2 эти идеи представлены более подробно.

Когда следует использовать
обучение с подкреплением?

Некоторые примеры RL, которые вы найдете в Интернете, выглядят вымученными.
Их авторы берут пример ML и пытаются применить к нему RL, несмотря на отсут-
ствие четкого агента или действия. Посмотрите, например, несколько примеров
с попытками включить RL в прогнозирование фондового рынка. Существует воз-

можность использования автоматизированного агента для совершения сделок, но
во многих примерах это не главное; основное внимание по-прежнему уделяется
прогнозной модели. Это неуместно, и такие примеры лучше оставить для ML.

RL работает лучше всего, когда решения принимаются последовательно, а действия
связаны с исследованием окружающей среды. Возьмите робототехнику, это клас-
сическая область применения RL. Цель робота — научиться выполнять неизвест-
ные задачи. Вы не должны указывать роботу, как добиться успеха, потому что это
либо слишком сложно (допустим, вы просите робота построить дом), либо вы мо-
жете быть предвзяты в силу собственного опыта (вы не робот), поэтому вы не знае-
те, как поставить себя на место робота. Если вместо этого вы позволите роботу
провести исследование, он сможет найти оптимальное решение. Этот случай хоро-
шо подходит для RL.

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

Основное преимущество RL заключается в том, что такое обучение оптимизирует-
ся для получения долгосрочных многоэтапных вознаграждений. Второстепенное
преимущество состоит в том, что очень легко включить в процесс метрики, исполь-
зуемые бизнесом. Например, рекламные решения обычно оптимизированы в целях
обеспечения наилучшей кликабельности для отдельной рекламы. Это неоптималь-
но, потому что зрители часто видят несколько рекламных объявлений, а цель не
щелчок (клик), а нечто большее, например удержание потребителя, регистрация
или покупка. Комбинация показываемых рекламных объявлений (в определенном
порядке и с конкретным содержанием) может быть автоматически оптимизирова-
на RL с помощью простой в использовании цели, соответствующей потребностям
бизнеса.

Вы можете отказаться от некоторых из четырех компонентов, представленных
в предыдущем разделе, чтобы упростить разработку. Если в вашей модели нет ес-
тественного сигнала, свидетельствующего о вознаграждении, например, «робот
достиг цели», то можно создать искусственное вознаграждение. Также часто соз-
дают симуляцию окружающей среды. Вы можете квантовать или обрывать дейст-
вия. Но это все компромиссы. Симуляция никогда не заменит реальный жизненный
опыт.

В RL активно ищется оптимальная модель. Вам не нужно создавать случайную вы-
борку и подстраивать ее в автономном режиме. Быстрое онлайн-обучение может
творить чудеса, когда важно в самые сжатые сроки добиться максимальной произ-
водительности. Например, в A/B-тестах, ориентированных на прибыль, когда нуж-
но решить, какой маркетинговый текст использовать, не хочется тратить время на
подготовку случайной выборки, если какой-то вариант недостаточно эффективен.
RL делает это бесплатно. О том, как A/B-тестирование соотносится с RL, вы може-
те узнать в главе 2.

Для чего нужно обучение с подкреплением? | 35

Таким образом, RL лучше всего подходит для прикладных задач, которые тре-
буют последовательных, сложных решений и имеют долгосрочную цель (в кон-
тексте единственного решения). ML может помочь вам в качестве вспомога-
тельного инструмента, но RL лучше всего подходит для сред с прямой обратной
связью. Утверждаю это, поскольку я разговаривал с некоторыми практиками,
которые использовали RL для замены групп специалистов по обработке дан-
ных, настраивающих производительность решений машинного обучения.

Варианты применения обучения с подкреплением

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

В СМИ, как правило, наибольшее внимание уделяется примерам, демонстрирую-
щим, как агенты побеждают людей в играх. Журналистам нравятся броские исто-
рии о том, как люди сдают свои позиции. А ученые продолжают обращаться к иг-
рам из-за сложной моделируемой среды. Но я решил не говорить ни о DeepMind
AlphaGo Zero, ни о версии агента, победившего чемпиона мира по го, ни об OpenAI
Five, победившей чемпионов мира по Dota 2, а вместо этого сосредоточиться на
приложениях и примерах из самых разных промышленных отраслей. Я не говорю,
что игровые примеры — пустая трата времени. Игровые компании могут использо-
вать RL для многих практических целей, например для помощи в тестировании или
оптимизации внутриигровых вариантов «AI» для максимизации дохода. Мне хочет-
ся помочь вам абстрагироваться от хайпа и показать разнообразные области, где
применимо RL. Для того чтобы продемонстрировать, что именно возможно уже
сейчас, я представляю широкий выбор экспериментов, которые лично мне кажутся
интересными.

Область робототехники имеет множество приложений RL, включая улучшение
движения и производственного процесса, игру в бильбоке и переворачивание
блинов [6]. Автономные транспортные средства также являются темой активных
исследований [7].

Вы можете использовать RL для улучшения облачных вычислений. В одной ста-
тье рассказано, как оптимизируются приложения с учетом задержки [8], в дру-
гой обсуждается соотношение «энергоэффективность/использование» [9]. Охла-
ждение центра обработки данных, охлаждение процессора и сетевая маршрути-
зация — все это варианты применения RL, используемые сегодня [10–12].

Финансовая отрасль применяет RL для совершения сделок и распределения
портфеля [13, 14]. Также существует значительный интерес к оптимизации
ценообразования в режиме реального времени [15].

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

RL [16]. А электрические сети могут использовать RL для решения ситуаций,
когда спрос неоднороден; дома являются одновременно производителями и по-
требителями [17].
RL улучшает управление светофорами и активное управление полосами движе-
ния [18, 19]. Умные города также остаются в выигрыше [20].
Недавние статьи предлагают множество вариантов применения RL в здраво-
охранении, особенно в областях дозирования и составления схем лечения [21,
22]. RL можно использовать для разработки более совершенных протезов и про-
тезных контроллеров [23].
Система образования и электронное обучение могут выиграть благодаря при-
цельно подобранным учебным программам на основе RL [24].
Ни один бизнес-сектор не остался незатронутым: игры, технологии, транспорт, фи-
нансы, наука и окружающая среда, промышленность, производство и государст-
венные службы — все они ссылались на приложения RL.

Я не хочу терять вас в бесконечном списке, поэтому вместо этого я отсылаю
вас на соответствующий веб-сайт1, где у меня есть полный каталог приложе-
ний RL.

Любая технология опасна в шаловливых руках. И, помня о популистских аргумен-
тах против AI, можно интерпретировать RL как опасное явление. Прошу вас, как
инженер, как человек, подумать о том, что вы строите. Прикиньте, как это повлияет
на других людей? Какие есть риски? Это противоречит вашей морали? Будьте от-
ветственны за свою работу перед собой. Если вы не можете этого сделать, вам,
вероятно, не следует этим заниматься. Далее приведены еще три задокументиро-
ванных гнусных приложения. У каждого свои этические границы. Где ваша грани-
ца? Какие приложения вам подходят?

Pwnagotchi — это устройство на базе RL, которое активно сканирует, анали-
зирует и взламывает Wi-Fi-сети с WPA/WPA2-защитой путем дешифрования
рукопожатий [25].
Исследователи показали, что можно обучить агентов обходить статические
модели вредоносных программ в антивирусных сканерах [26].
Военное ведомство США разрабатывает модели боевых действий, чтобы проде-
монстрировать, как автономные роботы могут помочь на поле боя [27].
Я более подробно обсуждаю вопросы безопасности и этики в главе 10.

1 См. https://rl-book.com/applications/?utm_source=oreilly&utm_medium=book&utm_campaign=rl.

Для чего нужно обучение с подкреплением? | 37

Таксономия подходов обучения
с подкреплением

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

Без модели или на основе модели

Первое важное решение, которое вы должны принять, — определить, есть ли у вас
точная модель окружающей среды. Алгоритмы на основе моделей используют точ-
ные сведения об окружающей среде, в которой они работают, для улучшения обу-
чения. Например, настольные игры часто ограничивают количество ходов, которые
вы можете сделать, и вы можете использовать эти знания, чтобы, во-первых, огра-
ничить алгоритм так, чтобы он не выполнял недопустимые действия, и во-вторых,
улучшить производительность за счет прогнозирования во времени (например,
если я двинусь сюда, а противник двинется туда, я могу выиграть). В таких играх,
как го и покер, можно использовать алгоритмы, позволяющие опередить людей
благодаря фиксированным правилам игры. Вы и ваш противник можете сделать
ограниченный набор ходов. Это лимитирует количество стратегий, которые алго-
ритмы должны искать. Как и в экспертных системах, решения на основе моделей
обучаются эффективно, потому что они не тратят время на поиск неправильных
путей [28, 29].

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

Однако это еще не все. Некоторые алгоритмы могут изучать модели окружающей
среды одновременно с изучением оптимальных стратегий. Несколько новых алго-
ритмов также могут использовать потенциальные, но неизвестные действия других
агентов (или других игроков). Другими словами, эти агенты способны научиться
противодействовать стратегиям другого агента.

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

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

Как агенты используют и обновляют свою стратегию

Цель любого агента — изучить стратегию, максимизирующую вознаграждение.
Я использую слово «стратегия», потому что это слово легче понять, но правиль-
ный термин «политика». В главе 2 политики рассматриваются более подробно.

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

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

Автономные агенты могут учиться на офлайн-множествах данных или старых жур-
нальных файлах (log-файлах). Это может быть весьма кстати, потому что иногда
сложно или дорого взаимодействовать с реальным миром. Однако, как правило,
RL наиболее полезно, когда агенты обучаются онлайн, поэтому большинство алго-
ритмов нацелены на сочетание онлайнового и офлайнового обучения.

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

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

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

Для чего нужно обучение с подкреплением? | 39

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

Дискретные или непрерывные действия

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

Некоторые действия, по сути, бинарны: дорожный знак «стоп/движение разрешено»
имеет ровно два класса. В других случаях у вас могут быть категории, которые вы
можете закодировать в виде бинарных действий. Например, вы можете разделить
управление дроссельной заслонкой транспортного средства на три бинарных дей-
ствия: полное закрытие, средняя мощность и полная мощность.

Но часто действия требуют большей ловкости. Когда вы ведете машину, вы пово-
рачиваете рулевое колесо на бесконечное количество углов. Если бы вы делали это
дискретно, то это обернулось бы головной болью. Хотели бы вы, чтобы водитель
автобуса поворачивал руль с шагом 90 градусов?

Промежуток или продолжительность действия также могут быть важны. В игре
Super Mario Bros. чем дольше вы удерживаете кнопку прыжка, тем выше прыгает
Марио. Можно включить время в число условий задачи и получить непрерывное
действие, которое, например, представляет интервал времени, в течение которого
вы удерживаете кнопку. Либо можете сделать эту величину дискретной и убедить-
ся, что вы неоднократно опрашиваете агента, чтобы узнать, должен ли он продол-
жать выполнять действие. Если вы уверены, что продолжительность действия не
связана с его выполнением, то ее можно обозначить через отдельную переменную.

Алгоритмы RL должны обрабатывать как бинарные, так и непрерывно изменяемые
действия. Но многие алгоритмы ограничиваются одним вариантом.

Примерно в возрасте 14–16 лет вы, вероятно, научились решать линейные уравне-
ния вручную, имея исходные данные и много бумаги. Но примеры, которые вы
решали, скорее всего, были очень простыми и с одной неизвестной переменной.
В реальном мире вы часто будете работать с сотнями, тысячами или даже миллио-
нами независимых переменных. На этом этапе невозможно использовать те же ме-
тоды, которым вы научились в школе, из-за вычислительной сложности реальных
примеров.

Как правило, вы будете строить модели (которые могут содержать или не содер-
жать линейные уравнения) и обучать их с помощью метода оптимизации. У RL та-
кая же проблема: нужно создать агента, который сможет предложить решение для
поставленной цели. Как именно это происходит — еще одна фундаментальная тема
в RL.

Один из способов — попробовать как можно больше действий и записать результа-
ты. В дальнейшем вы можете направлять агента, следуя стратегии, которая привела
к наилучшему результату. Это так называемые ценностные алгоритмы, и я вскоре
познакомлю вас с ними.
Другой способ — поддерживать модель и настраивать параметры модели, чтобы
стремиться к действиям, которые привели к наилучшему результату. Это так на-
зываемые алгоритмы на основе политик. Вы можете прочитать о них подробнее
в главе 5.
Для того чтобы это было проще понять, представьте себе двумерную сетку с обры-
вом на юге. Ваша задача — сконструировать робота, который будет многократно
проверять каждый квадрат и узнавать, что падение со скалы связано с определен-
ными затратами. Если бы вы использовали алгоритм, основанный на ценностях,
и преобразовали стратегию в слова, он бы сказал: «Не ступайте с обрыва». Алго-
ритм, основанный на политике, сказал бы: «Отойдите от обрыва». Тонкое, но важ-
ное отличие.
Алгоритмы, основанные на ценностных значениях и применении политик, в на-
стоящее время наиболее изучены и, следовательно, наиболее популярны. Но алго-
ритмы на основе имитации, в которых вы оптимизируете агента для имитации дей-
ствий эксперта, могут хорошо работать, когда вы пытаетесь привлечь человека
к руководству процессом. Любые другие алгоритмы, которые не подходят ни
к одному из этих классов, могут породить новые методологии в будущем.

Оценка и улучшение политики

Другой способ интерпретации того, как алгоритм улучшает свою стратегию, —
рассматривать его с точки зрения оценки политики и улучшения политики (рис. 1.2).

Рис. 1.2. Интерпретация того, как алгоритмы обновляют свою стратегию

Во-первых, агент следует стратегии (политике) для принятия решений, и эта поли-
тика генерирует новые данные, описывающие состояние среды.
На основе этих новых данных агент пытается предсказать вознаграждение исходя
из текущего состояния среды; он оценивает текущую политику.

Для чего нужно обучение с подкреплением? | 41

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

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

Фундаментальные концепции обучения
с подкреплением

Идея обучения методом проб и ошибок как фундаментальная основа всех алгорит-
мов RL возникла в ранних работах по психологии обучения животных. Знаменитый
русский физиолог Иван Петрович Павлов впервые сообщил в 1927 г., что можно
запустить пищеварительную систему животного, используя стимулы, не имеющие
отношения к процессу приема пищи. В одном известном эксперименте он измерил
количество слюны, выделяемой собаками, когда им давали пищу. В то же время он
ввел в эксперимент звуковой сигнал. После нескольких повторений у собаки воз-
никало слюноотделение в качестве реакции только на звук [30].

Звук не является естественным предвестником пищи и не помогает при приеме пи-
щи. Связь между врожденными рефлексами, такими как моргание глаз или образо-
вание слюны, и новыми стимулами теперь называется классическим, или павлов-
ским, обусловливанием.

В 1972 г. Роберт Рескорла (Robert Rescorla) и Аллан Вагнер (Allan Wagner) обнару-
жили еще один интересный феномен, который невозможно объяснить с помощью
павловского обусловливания. Сначала они подули струей воздуха в глаз кролика,
и он моргнул. Затем они научили кролика ассоциировать внешний раздражитель,
звук, с дуновением воздуха. Кролик моргнул, когда услышал звук, даже при отсут-
ствии дуновения. Затем они переучили кролика моргать при воздействии как звука,
так и света. Опять же, когда кролик услышал звук и увидел свет без дуновения воз-
духа, он моргнул. Но затем, когда исследователи только мигнули светом, кролик не
моргнул [31].

У кролика сложилась иерархия ожиданий; звук и свет равны мерцанию. Когда кро-
лик не соблюдал базовое ожидание (звук), это блокировало все последующие усло-
вия. Возможно, вы сами испытали это ощущение. Время от времени вы узнаете
что-то настолько невероятное, настолько фундаментальное, что вам может казать-
ся, что любые убеждения, следующие из узнанного, не выдерживают критики.
Ваша базовая обусловленность была нарушена, а ожидания высшего порядка за-

блокированы. Результатом этой работы стала модель Рескорла — Вагнера. Их ис-
следование никогда ранее не было представлено в таком ракурсе, но здесь оно опи-
сывается с применением метода, называемого оценкой ценности.

Представьте, что вы пытаетесь смоделировать опыт с кроликами в постановке Рес-
корла — Вагнера. Цель состоит в том, чтобы предсказать, когда кролик моргнет.
Вы можете создать модель этого эксперимента, описав входные данные и ожидае-
мый результат. Входные данные представляют действия под вашим контролем,
а выход — предсказание того, моргает ли кролик.

Вы можете представить входные данные в виде вектора s = ( s0 , s1, . sn−1 ) , где

si = 1 , если i-й стимул присутствует в испытании, и si = 0 — в противном случае.
Это бинарные действия.

Допустим, например, что функция s0 представляет звук, а s1 ― свет. Тогда вектор
s = [0, 1] представляет ситуацию, когда звук отсутствует, а свет есть.

Вы можете записать предполагаемый результат в виде V , выразив таким образом
прогноз того, моргнет кролик или нет. Затем состояния отображаются в правильное
предсказание с помощью функции V (s) .

Я твердо решил максимально упростить математику, чтобы улучшить читае-
мость и понимание книги. Это означает, что книга теряет математическую фор-
мальность, такую как обозначение оценки с помощью оператора hat, для улуч-
шения читаемости. См. академические статьи, где соблюдается полная мате-
матическая строгость.

Теперь самое сложное: определение функции отображения. Одним из распростра-
ненных решений является умножение входных данных на параметры, находящие-
ся под вашим контролем. Вы можете изменить эти параметры, чтобы получить
результат, зависящий от входов. Эти параметры называются весами, а модель, ко-
торую вы только что построили, является линейной.
Веса определяются другим вектором w, который имеет ту же форму, что и призна-
ки. Например, данные могут показать, что свет не заставлял кролика моргать;
он моргнул только тогда, когда услышал звук. В результате получается модель
с весом, равным 1, для параметра звука, и весом, равным 0, для параметра света.

Формально функция представляет собой сумму входных данных, умноженных на
веса. Эта операция называется скалярным произведением. Результат, который пока-
зан в уравнении 1.1, является предсказанием того, моргает ли кролик.

Уравнение 1.1. Оценка ценности

V (s, w) w0s0 + w1s1 + … + wnsn = w ⋅ s = wT s .

Но в целом, как вы определяете значения весов?

Для чего нужно обучение с подкреплением? | 43

Вы можете использовать метод оптимизации, чтобы найти оптимальные парамет-
ры. Самый распространенный метод — количественно оценить, насколько неверна
ваша оценка по сравнению с реальной (правильным ответом). Затем вы можете по-
пробовать множество разных весов, чтобы минимизировать ошибку.

Ошибка δ в вашем прогнозе — это разница между фактическим результатом экс-
перимента E и прогнозом (оценкой ценности). Прогноз основан на текущем со-
стоянии окружающей среды (наблюдение за кроликом) s и текущих весах. Все
переменные меняются со временем и часто обозначаются индексом t , но я игнори-
рую это, чтобы уменьшить количество обозначений. Вы можете увидеть это
в уравнении 1.2.

Уравнение 1.2. Ошибка предсказания

Одной из трактовок уравнения 1.2 является утверждение, что δ характеризует сте-
пень непредсказуемости. Если вы сделаете прогноз, что кролик обязательно морг-
нет, а этого не произойдет, то разница между тем, что вы предсказали, и тем, что
произошло, будет велика; вы будете удивлены результатом.

Учитывая количественное определение удивления, как следует изменить веса?
Один из способов — изменить веса пропорционально ошибке прогноза. Например,
рассмотрим ситуацию, когда ожидалось, что звук (индекс 0) и свет (индекс 1) име-
ют одинаковую важность. Набор весов w = [1, 1] .

На этот раз эксперимент состоит в том, чтобы использовать только свет, а звук не
использовать. Таким образом, наблюдаемое состояние эксперимента x (s) = [0, 1] .
Для того чтобы сделать прогноз V (s, w) , вычислите скалярное произведение на
только что приведенных векторах. Результат равен 1 (моргает).

Когда вы запустили симуляцию, кролик не моргнул. Фактическое значение было 0.
Значение δ в уравнении 1.2 равно 1.

Знание предыдущего состояния и ошибки прогноза помогает изменить веса. Умно-
жая их, получаем δx (s) = [0, 1] . Добавление этого к текущим весам дает w = [1, 0] .

Обратите внимание, как новые веса правильно предсказали бы фактический ре-
зультат 0 (не моргает): wT x (s) = [1, 0]T [0, 1] = 0 .

Правило обновления веса

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

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

Это формализовано как правило обновления весов. В уравнении 1.3 вы можете
управлять скоростью обновления весов с помощью гиперпараметра α , который
должен находиться в диапазоне от 0 до 1. Уравнение 1.3 обновляет веса последова-
тельно, т. е. веса на следующем временнóм шаге выводятся из весов текущего
временнóго шага. Опять же, я игнорирую нижние индексы, чтобы упростить обо-
значения.

Уравнение 1.3. Правило обновления весов

RL — это то же самое, что ML?

Математические выражения, представленные в уравнениях 1.1 и 1.3, описывают
психологическую модель обучения животных. Вы можете легко применить тот же
подход к программным агентам. Но настоящая причина для такого углубления
заключалась в том, чтобы дать математическое упражнение для разминки перед
остальной частью книги. Здесь я ввел математические символы, которые исполь-
зуются в последующих главах (в исходной статье использовались символы и тер-
минология, неприменяемые в психологии).

Если вы ненадолго абстрагируетесь от математики, идея обновления весов для по-
лучения лучшего соответствия может показаться знакомой. Вы правы, если узнали
в этом регрессию из ML. Цель состоит в том, чтобы предсказать числовой резуль-
тат (общее вознаграждение) на основе заданного набора входных данных (наблю-
дений). Практики называют это проблемой предсказания. Для того чтобы прини-
мать правильные решения, вам необходимо уметь предугадывать, какие действия
будут оптимальными.

Главное отличие ML от RL в том, что вы даете агентам свободу выбора. Это кон-
трольная часть задачи, и на первый взгляд кажется, что это простое дополнение
к задаче предсказания машинного обучения. Однако не стоит недооценивать эту
проблему. Вы можете подумать, что лучшая политика — выбрать действие, для
которого прогнозируется наивысший известный результат. Нет, так не делается,
потому что могут быть другие состояния, которые приносят еще большее возна-
граждение.

Контроль обеспечивает автономию; супермашины могут учиться на своих ошиб-
ках. Этот навык открывает ряд новых возможностей. Многие задачи настолько
сложны — например, как научить робота фотографировать определенный объ-
ект, — что инженерам приходится прибегать к ограничениям, правилам и разби-
вать задачу на подзадачи. Точно так же я работаю с клиентами, которым приходит-

Для чего нужно обучение с подкреплением? | 45

ся ежедневно или ежечасно переобучать свои модели для вовлечения новых дан-
ных. Хватит! Откажитесь от контроля и используйте RL.

Алгоритмы RL пытаются сбалансировать эти две проблемы — исследование и экс-
плуатацию — разными способами. Одно общее различие заключается в том, как
алгоритмы изменяют скорость, с которой ведется исследование. Некоторые алго-
ритмы исследуют задачу с фиксированной скоростью, другие устанавливают ско-
рость, пропорциональную предсказанному значению. Некоторые даже пытаются
определить вероятность получения максимальной награды для заданного состоя-
ния. Это проблема обсуждается на протяжении всей книги.

Награда и отклик

Исследователи ML черпали вдохновение в нейробиологии. Наиболее часто приво-
димым примером, иллюстрирующим это, является создание искусственного нейро-
на, на основе которого строятся нейронные сети сетей и глубокое обучение. Искус-
ственный нейрон — это модель единичного нейрона, входящего в состав мозга, во
многом подобно тому, как атомная модель предполагает наличие элементарной
единицы материи. На парадигму RL, в частности, повлияла коммуникативная мо-
дель, действующая в мозге.

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

Традиционные теории о присутствии дофамина основывались на усиливающемся
и приятном эффекте химического вещества. Но исследования начала 1990-х годов
выявили ряд поразительных фактов. Исследователи смогли количественно изме-
рить активность дофамина у обезьян. Их результаты показали, что существует фо-
новый уровень постоянного выброса дофамина. Исследователи обучили каждую
обезьяну выполнению традиционной условной задачи (подобной той, которую мы
рассмотрели в разд. «Оценка ценности» ранее в данной главе): обезьяны ожидали
еду через несколько минут после включения света. Когда тренировка началась, на-
блюдался значительный всплеск уровня дофамина над фоновым уровнем при полу-
чении награды. Со временем исследователи заметили, что высвобождение дофами-
на у обезьян сдвигается в сторону появления света. В конце концов, каждая обезья-
на переживала выброс дофамина всякий раз, когда видела свет [32]. Если вы
простите мне небольшое отступление к реальному человеческому опыту, я могу
засвидетельствовать, что мои дети больше взволнованы перспективой получить
мороженое, чем на самом деле есть мороженое.

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

чала награды, наблюдался отрицательный эффект дофамина (по сравнению с ис-
ходным уровнем) [33].

Как и в разд. «Ошибка предсказания» ранее в данной главе, эти события можно хо-
рошо смоделировать с помощью корректирующего процесса. Дофаминовые нейро-
ны сами по себе не сигнализируют о награде. Дофамин — это сигнал, представ-
ляющий ошибки предсказания вознаграждения. Другими словами, дофамин — это
δ мозга.

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

Проблему отложенного вознаграждения также сложно решить в RL. Часто агенту
нужно долго ждать, чтобы обнаружить награду. Здесь могут помочь алгоритмиче-
ские приемы, но, по сути, изменение сигнала вознаграждения так, чтобы он обеспе-
чивал более частые обновления, помогает агенту найти решение. Такое изменение
вознаграждения называется формированием вознаграждения, но мне нравится
думать об этом как об инжиниринге наград, сродни разработке функций в ML.

С этой проблемой связано присвоение награды. Например, какие решения привели
вас к ситуации, в которой вы находитесь сейчас? Как вы можете это знать? Раннее
решение могло повлиять на успех или неудачу. Но, учитывая все возможные со-
стояния и действия в сложной системе, решить эту проблему сложно. В целом
можно сказать только, что решения являются оптимальными в среднем с учетом
набора допущений и ограничений.

Идиома «доверяй своей интуиции» означает, что вы должны доверять своей ин-
стинктивной реакции, осваиваясь в новой ситуации. Эти эвристические штампы
подтверждены опытным путем и, как правило, приводят к хорошим результатам.
Критическое мышление — процесс, при котором вы логически и методично прора-
батываете проблему, — требует гораздо больше энергии и концентрации.

Эти два процесса в мозге, часто называемые «1-й и 2-й моделями системы», рабо-
тают как механизм энергосбережения. Зачем тратить драгоценные умственные
ресурсы на повседневные задачи? Затруднительно осознанно думать о том, как
именно ходить. Но страдающим болезнью Альцгеймера приходится сталкиваться
с этой ужасно изнурительной ситуацией ежедневно [34].

Исследователи предполагают, что неврологические различия в головном мозге
объясняют эти системы [35]. Задача «инстинктивной» части мозга — быстро при-
нимать решения. Задача другой — проверить эти действия и при необходимости
принять корректирующие меры.

Для чего нужно обучение с подкреплением? | 47

Эта структура привела к развитию семейства алгоритмов «актор — критик»
(actor — critic). Актор (исполнитель, actor) несет ответственность за принятие важ-
ных решений, чтобы получить максимальное вознаграждение. Критик (critic) готов
спланировать будущее и поправить актора, когда тот получает неправильный ответ.
Это открытие было жизненно важным для многих продвинутых алгоритмов RL.

Обучение с подкреплением как дисциплина

Парадигма RL развивалась как две независимые дисциплины примерно до 1980-х го-
дов. Психология изучала поведение животных. Инженеры-механики и электронщи-
ки разработали теорию для описания оптимального управления системами.

Термин «оптимальное управление» возник в 1950-х годах с целью описания того,
как настроить систему для достижения поставленной цели. Усилия достигли куль-
минации в 1957 г., когда Ричард Беллман (Richard Bellman) разработал марковский
процесс принятия решений (Markov decision process, MDP) — набор требований
к математически управляемой среде и динамическому программированию (метод
решения MDP) [36].

Согласно одному источнику, исследования поведения животных восходят к XIX ве-
ку, когда проводились эксперименты, включающие «экспериментальное нащупы-
вание» [37]. Эдвард Торндайк (Edward Thorndike) запирал кошек в «коробках с го-
ловоломками» и фиксировал, сколько времени требовалось животным, чтобы сбе-
жать. Он обнаружил, что время побега уменьшилось посредством повторения
опытов и закрепления результатов с 5 минут до 6 секунд. Результатом этой работы
стал «закон эффекта», более известный как обучение методом проб и ошибок.

Термин «подкрепление» впервые появился в переводах из рукописей Павлова об
условных рефлексах в 1927 г. Но RL было популяризировано дедушкой вычисли-
тельной техники Аланом Тьюрингом, когда в 1948 г. он изложил свои самые ран-
ние мысли об искусственном интеллекте, как «организовать» физический набор
электронных схем, которые он назвал «машинами», чтобы сделать что-то практиче-
ское:

«Это можно сделать, просто позволив машине произвольно перемещаться в по-
следовательности ситуаций и применяя болевые стимулы, когда сделан непра-
вильный выбор, и стимулы удовольствия, когда сделан правильный. Лучше все-
го применять болевые стимулы, когда сделан неуместный выбор. Это сделано
для того, чтобы не попасть в кольцо неуместных ситуаций. Теперь машина „го-
това к работе“» [39].

Алан Тьюринг (1948)

Я нахожу удивительным, насколько работы Тьюринга актуальны и сегодня. В его
время исследователи создавали роботов для решения повседневных задач. Один
особенно гениальный исследователь по имени Уильям Грей Уолтер (William Grey
Walter) построил «механическую черепаху» в 1951 г. В 1953 г. он представил «чере-
паху» под названием CORA (conditioned reflex analogue — аналог условного реф-
лекса), которая была способна «учиться» в окружающей среде. Робот содержал

схемы, которые могли имитировать эксперименты с павловским обусловливанием.
Уже тогда публика была очарована такими машинами, которые могли «учиться»:

«В Англии полицейский свисток состоит из двух звуков, которые звучат вместе
и издают особенно неприятный звук. Поэтому я пытался научить [CORA], что
одна нота означает препятствие, а другая — пищу. Я попытался создать этот
дифференциальный рефлекс с помощью двух настроенных контуров, один из
которых был связан с реакцией аппетита, а другой — с реакцией избегания. Все
было устроено так, что одна сторона свистка использовалась до того, как маши-
на коснулась объекта, чтобы она научилась избегать его; в то время как другая
сторона свистка использовалась до того, как она должна была увидеть свет. Эф-
фект от подачи обеих нот почти всегда был катастрофическим; машина сразу
шла в темноту в правой части комнаты и пять минут зависала там в каком-то
угрюмом настроении. Она стала невосприимчивой к стимуляции и бегала по
кругу» [40].

Уильям Грей Уолтер (1956)

К концу 1950-х годов интересы исследователей сместились от обучения методом
проб и ошибок к обучению с учителем. Фактически сначала люди использовали эти
два термина как синонимы. Пионеры нейронных сетей, включая Фрэнка Розенблат-
та (Frank Rosenblatt), Бернарда Уидроу (Bernard Widrow) и Теда Хоффа (Ted Hoff),
использовали в своих статьях термины «вознаграждение» и «наказание». Это вы-
звало путаницу, потому что понятия «обучение с учителем», «обучение без учителя»
и «обучение с подкреплением» использовались для обозначения одной и той же
идеи.

В то же время завышенные ожидания возможностей искусственного интеллекта
в 1950–1960-х годах вызвали всеобщее недовольство медленным прогрессом.
В 1973 г. в отчете «Lighthill report» о состоянии исследований искусственного ин-
теллекта в Великобритании критиковалась полная неспособность достичь «гранди-
озных целей» [41]. На основании этого отчета бóльшая часть государственного фи-
нансирования исследований искусственного интеллекта была урезана сначала в Ве-
ликобритании, а затем и в остальном мире. 1970-е годы вошли в историю как «зима
искусственного интеллекта», и прогресс застопорился.

Возрождение RL в 1980-х годах, как было признано, произошло благодаря Гарри
Клопфу (Harry Klopf), который в 1970-х годах заявлял, что знания и навыки ис-
пользования ключевых методов обучения теряются. Он подчеркивал, что контроль
окружающей среды для достижения желаемого результата является ключом к соз-
данию интеллектуальных систем. Ричард Саттон (Richard Sutton) и Эндрю Барто
(Andrew Barto) работали в 1980–1990-х годах над продвижением идей Клопфа по
объединению областей психологии и теории контроля (см. разд. «Фунда-
ментальные концепции обучения с подкреплением» ранее в данной главе) посредст-
вом обучения на основе временны́ х различий (temporal-difference, TD). В 1989 г.
Крис Уоткинс (Chris Watkins) интегрировал все предыдущие направления исследо-
ваний RL и создал Q-обучение.

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

Для чего нужно обучение с подкреплением? | 49

подробнее узнать об истории RL из ссылок в разд. «Дополнительные материалы
для чтения» далее в этой главе.

Компания по исследованию рынка Gartner предполагает, что в США развитие ис-
кусственного интеллекта приносит предприятиям триллионы долларов в год [42].
RL играет большую роль на этом рынке, поскольку многие из сегодняшних бизнес-
задач имеют стратегический характер. От торгового зала до руководства компании
существует множество неоптимизированных многоэтапных решений, таких как
добавление товаров в корзины или определение стратегий выхода на рынок. В оди-
ночку ML не оптимально, т. к. оно недостаточно дальновидно для таких задач. Но
бурный рост объемов данных, вычислительных мощностей и улучшенное модели-
рование дают возможность существовать программно-управляемым агентам ML и
RL, которые могут изучать оптимальные стратегии, превосходящие придуманные
людьми.
Биологические процессы продолжают стимулировать внедрение RL. Ранние психо-
логические эксперименты подчеркивали важность исследования и вознаграждения.
Исследователи предложили различные способы эмуляции обучения с подкреплени-
ем, что породило несколько общих тем. Как инженер, вы должны решить, какая из
этих тем подходит для вашей задачи: например, как вы оптимизируете свой алго-
ритм RL, какую форму принимают действия, требуется ли агенту формальный ме-
ханизм планирования и следует ли обновлять политику в режиме онлайн? Вы при-
обретете больше опыта с помощью этой книги, и в последних главах я покажу вам,
как применять полученный опыт. Тщательно определив действия и вознагражде-
ния, вы можете разработать агентов, которые будут работать в среде для решения
ряда промышленных задач. Но сначала вам нужно узнать об алгоритмах, которые
позволяют агентам изучать оптимальные политики. Таким образом, основная цель
этой книги — научить вас тому, как агенты работают и как их применять.

Дополнительные материалы для чтения

• Ресурсов много, но у Сергея Левина2 один из лучших.

• Саттон Р. С., Барто Э. Дж. Обучение с подкреплением: введение. — MIT Press, 2018

(Sutton R. S., Barto A. G. Reinforcement learning: an introduction. — MIT Press, 2018).

• Исторический обзор RL с 1996 г., но актуален и сегодня [43].

2 См. https://oreil.ly/wgxnk.

[1] Reinsel D., Gantz J., Rydning J. The digitization of the world from edge to core. — IDC,
2018. — URL: https://oreil.ly/96vhZ.

[2] AWS Snowmobile is a service that allows you to use a shipping container to snailmail your
data to its datacenters. — URL: https://oreil.ly/O5-K9.

[3] Papers of Dr Dietrich G. Prinz-Archives Hub. — URL: https://oreil.ly/XCG9g.

[4] Copeland B. Jack. The essential turing. — Clarendon Press, 2004.

[5] Drunk Swedish Elk found in Apple Tree Near Gothenburg // BBC News. — 2011. —
8 September. — URL: https://oreil.ly/zr3Da.

[6] Kormushev P. et al. Reinforcement learning in robotics: applications and real-world
challenges // Robotics. — 2013. — Vol. 2, № 3. — P. 122–48. — URL: https://oreil.ly/juf15.

[7] Huang W., Braghin F., Wang Z. Learning to drive via apprenticeship learning and deep
reinforcement learning // ArXiv:2001.03864. — 2020. — January. — URL:
https://oreil.ly/pqtHi.

[8] Dutreilh X. et al. 2011. Using reinforcement learning for autonomic resource allocation
in clouds: towards a fully automated workflow // ICAS 2011, The Seventh International
Conference on Autonomic and Autonomous Systems. — 2011. — P. 67–74.

[9] Liu N. et al. 2017. A Hierarchical framework of cloud resource allocation and power
management using deep reinforcement learning // ArXiv:1703.04221. — 2017. — August. —
URL: https://oreil.ly/N2wL7.

[10] DeepMind AI reduces Google Data Centre cooling bill by 40% // Deep-Mind. — Accessed
3 July 2019. — URL: https://oreil.ly/rjAae.

[11] Das A. et al. Reinforcement learning-based inter- and intra-application thermal optimization
for lifetime improvement of multicore systems // Proceedings of the 51st Annual Design
Automation Conference. — 2014. — P. 170:1–170:6. — DACʼ14. New York, NY, USA:
ACM.

[12] Littman M., Boyan J. A Distributed reinforcement learning scheme for network routing //
Proceedings of the International Workshop on Applications of Neural Networks to
Telecommunications. — 2013. — 17 June. — URL: https://oreil.ly/543Qz.

[13] Wang H. Large scale continuous-time mean-variance portfolio allocation via reinforcement
learning // ArXiv:1907.11718. — 2019. — August. — URL: https://oreil.ly/5J5qV.

[14] Wang J. et al. AlphaStock: a buying-winners-and-selling-losers investment strategy using
interpretable deep reinforcement attention networks // Proceedings of the 25th ACM SIGKDD
International Conference on Knowledge Discovery & Data Mining — KDDʼ19. — 2019. —
P. 1900–1908. — URL: https://oreil.ly/c0HA2.

[15] Maestre R. et al. Reinforcement learning for fair dynamic pricing // In Intelligent Systems and
Applications, edited by Kohei Arai, Supriya Kapoor, and Rahul Bhatia. Advances in Intelligent
Systems and Computing. — Springer International Publishing, 2019. — P. 120–135.

Сборник по итогам фестиваля «30 ЛЕТ ШКОЛЬНОЙ ИНФОРМАТИКЕ: ПРОШЛОЕ, НАСТОЯЩЕЕ, БУДУЩЕЕ»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ ДОНЕЦКОЙ НАРОДНОЙ РЕСПУБЛИКИ ДОНЕЦКИЙ РЕСПУБЛИКАНСКИЙ ИНСТИТУТ ДОПОЛНИТЕЛЬНОГО ПЕДАГОГИЧЕСКОГО ОБРАЗОВАНИЯ ОТДЕЛ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ 30 ЛЕТ ШКОЛЬНОЙ ИНФОРМАТИКЕ: ПРОШЛОЕ, НАСТОЯЩЕЕ, БУДУЩЕЕ! МАТЕРИАЛЫ ФЕСТИВАЛЯ «30 ЛЕТ. Показать больше

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ ДОНЕЦКОЙ НАРОДНОЙ РЕСПУБЛИКИ ДОНЕЦКИЙ РЕСПУБЛИКАНСКИЙ ИНСТИТУТ ДОПОЛНИТЕЛЬНОГО ПЕДАГОГИЧЕСКОГО ОБРАЗОВАНИЯ ОТДЕЛ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ 30 ЛЕТ ШКОЛЬНОЙ ИНФОРМАТИКЕ: ПРОШЛОЕ, НАСТОЯЩЕЕ, БУДУЩЕЕ! МАТЕРИАЛЫ ФЕСТИВАЛЯ «30 ЛЕТ ШКОЛЬНОЙ ИНФОРМАТИКЕ: ПРОШЛОЕ, НАСТОЯЩЕЕ, БУДУЩЕЕ» 17.05.2016 ГОДА ДОНЕЦК 2016 Спрятать

• Похожие публикации
• Поделиться
• Код вставки
• Добавить в избранное
• Комментарии

Аннотация работы

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

Методы, используемые в работе: в работе используются методы оперирования с простейшими геометрическими фигурами, методы комбинаторики для анализа исследуемых объектов, начальные знания по теории графов.

Задачи работы. В ходе исследования были поставлены следующие задачи:

1. изучение литературы по теме исследования: изучение истории математической проблемы «четырех красок»; изучение художественной литературы, отражающей исследуемую проблему; знакомство с жадным алгоритмом раскраски вершин графа.
2. Проведение серии практических экспериментов по исследованию жадного алгоритма – раскрашивание вершин графа при различном обходе вершин графа.
3. Формализация двух практических задач в виде раскраски вершин графа.
4. Подготовка математического буклета «Раскраска вершин графа» на основе материалов проделанной работы.
5. Создание научно-популярного фильма «Остров пяти красок»

Основной текст тезисов

Исследовательская работа является продолжением практического исследования, начатого нами в прошлом году. Первый год работы был посвящен проблеме четырех красок, которая известна уже более 100 лет. Мы, как и математики, начали с проверки утверждения четырех красок для различных карт. Сначала брали маленькие простые карты, например, карта Мурманской области, потом Липецкой области с 18 районами, карта Московской области. Все эти карты мы раскрасили в 4 цвета, хотя это и получалось не с первого раза. Среди всех опробованных нами карт не нашлось ни одной, где бы нужно было использовать пятую краску. Мы узнали, что теорема четырех красок была доказана математиками в 1976 году при помощи компьютерной программы и была первой теоремой, доказанной при помощи компьютерного моделирования.

Задача раскраски карты может быть формализована как задача раскраски вершин графа. И решается она, разумеется, гораздо более сложным способом, чем просто раскрашивание карт цветными карандашами. В этом году руководитель поставил перед нами задачу изучения математического алгоритма решения этой задачи, что мы и сделали в этом году. Нами был изучен жадный алгоритм раскраски вершин графов, при помощи которого теперь мы можем раскрашивать карты, представленные в виде графов. Применение жадного алгоритма не всегда дает наименьшее количество цветов раскраски. Однако, существенно облегчает раскраску графов. Мы узнали, что карты могут быть представлены в виде планарных графов. И для любого планарного графа возможно раскраска в 4 или менее цветов. А вот выяснить какое минимальное количество цветов необходимо, чтобы раскрасить какой-то произвольный граф – сложная вычислительная задача. И решать ее за разумное время математики пока не умеют. Жадный алгоритм позволяет решать эту задачу быстро, но не дает точный ответ. Например, наши эксперименты с использованием различного порядка обхода вершин графа, показали, что в этом случае мы можем получить различное количество цветов вершин.

Задача раскраски графов имеет и очень интересные практические приложения, что и определяет ее актуальность. Некоторые из них мы рассматриваем в своей работе. Например, задача распределения кроликов по клеткам. Как распределить кроликов по клеткам если они имеют предпочтения (какой кролик с каким не хочет быть в одной клетке). Эту задачу мы рассмотрели на примере распределение животных в зоопарке по клеткам. Вторая задача – задача назначения частот базовым станциям сотовой связи. Нельзя допустить ситуацию, когда две базовые станции находятся в близкорасположенных точках и работают на одной частоте, так как в этом случае не избежать помех. Мы рассмотрели пример на основе карты базовых станций Билайна города Москвы. Соединили ребрами те станции, которые распложены близко друг к другу и провели раскраску вершин графа (базовых станций ) и назначили им разные частоты.

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

Исследование опирается на следующие библиографические источники:

1. Four, five, and six color theorems [Электронный ресурс]. Режим доступа: https://natureofmathematics.wordpress.com/lecture-notes/four-and-five-color-theorems/
2. Теория случайных графов. Интервью с А. Райгородским, д. ф.-м. н., проф. МГУ и МФТИ [Электронный ресурс]. Режим доступа: http://habrahabr.ru/company/postnauka/blog/201416/
3. Л.Ю.Березина. Графы и их применение: Популярная книга для школьников и преподавателей. Изд.стереотип.– М.:Либроком, 2014.
4. Мартин Гарднер. Остров пяти красок. Martin Gardner. The Island Of Five Colours (Fantasia Mathematica, N.Y., 1958) [Электронный ресурс]. Режим доступа: http://lib.ru/INOFANT/GARDNER_M/island.txt

• 3 декабря 2015 г.
• Яков Поляков

Автор: Поляков Яков Александрович, Российская Федерация, г. Липецк, МБОУ СОШ 68 г. Липецк, 5 Б класс

Научный руководитель: Сысоев А.С., к.т.н., доцент кафедры прикладной математики Липецкого государственного технического университета

Аннотация работы
Важно или нет, согласованны ли мнения людей при выставлении оценок, голосовании, ранжировании чего-либо? Конечно, это очень важно. В том объеме информации, которая сегодня нас окружает, учесть это не всегда бывает просто, но возможно.

Посмотрев в этом году конкурс песни «Евровидение», я подумал, а отчего зависит, победит ли песня или нет? От ее качества, известности исполнителя или чего-то еще? Может быть все дело в том, кто с кем граничит? В любом случае, голосуя, делают ли это страны согласованно?

А потом я подумал — выборы старосты в классе — это ведь точно такой же процесс выставления оценок претендентам. А что, если учесть согласованность выставления оценок, чтобы доказать одноклассникам, есть ли четкий лидер в классе или все претенденты достойны быть старостой?

Целью работы является оценка согласованности данных, полученных в двух ситуациях. Во-первых, оценка согласованности мнений стран-участниц конкурса песни «Евровидение — 2015», а во-вторых, оценка согласованности мнений школьников при выборе старосты класса.

Задачи

1. Выяснить, что такое согласованность данных, как она измеряется.
2. Провести анализ согласованности баллов, выставленных участникам конкурса песни «Евровидение — 2015».
3. Используя полученный опыт, произвести оценку согласованности результатов выборов старосты класса.

Методы, используемые в работе: методы математической статистики, методы экспертных оценок.

Основной текст тезисов

Давайте представим себе ситуацию, когда необходимо подтвердить или опровергнуть правоту какого-либо человека или свершившегося факта. Например, при оценке качества интересующего нас продукта или изделия специалистами — добросовестно и беспристрастно подошли ли они к своей работе? Назовем эту оценку исследуемым признаком. Решают задачи, в которых оцениваются значения признака у ряда явлений, процессов или людей. Множество объектов, значения признака которых оценивается, называется множеством факторов. И мы подошли к последнему главному вопросу — кто будет оценивать? Это группа людей, которых называют экспертами. Итак, эксперты выставляют оценки по факторам. В результате получается таблица значений. Задача оценки согласованности данных состоит в том, чтобы с помощью анализа некоторых расчетных математических показателей сказать, едины ли в своем решении были эксперты или нет. То есть, получаем ответ на вопрос — является ли принятое решение мнением большинства. В случае, когда оценок немного, то сделать это легко и без использования математики. Но чаще бывает, когда оценок много и визуальный анализ ни к чему хорошему нас не приведет. Для оценки согласованности данных используется коэффициент ранговой корреляции или конкордации (от франц. concorde — согласие). Коэффициент конкордации отражает степень согласованности мнений экспертов по всем характеристикам. В нашем исследовании мы установили степень согласованности мнений экспертов при выборе стран-победителей на конкурсе Евровидение и при выборе старосты класса. Нами были получены следующие результаты:

1. При анализе согласованности результатов голосования в финале конкурса песни «Евровидения» получили умеренную согласованность. Это говорит, с одном стороны, о том, что страны, оказавшиеся наверху турнирной таблицы действительно достойны этого, и большинство экспертов это подтверждают, а с другой стороны — выставление более низких оценок обусловлено случайными факторами, такими как локальные предпочтения или сложившаяся политическая ситуация.
2. При анализе оценок претендентам на должность старосты класса получили слабую согласованность. Это говорит о том, что все соперники практически в равной степени достойны быть старостой нашего класса.

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

Исследования опираются на литературные источники:

1. Ковалева Т.Ю. Практикум по теории статистики. М.: «КноРус», 2012. — 376 с.
2. Джонсон Н., Лион Ф. Статистика и планирование эксперимента в технике и науке. Методы обработки данных. Пер. с англ. — М.: Мир, 1980. — 620 с.
3. Макаров И.М., Виноградская Т.М., Рубчинский А.А. Теория выбора и принятия решений. М.: Наука, 1982. — 328 с.
4. Eurovision Song Contest. http://www.eurovision.tv/page/timeline

• 7 декабря 2015 г.
• Софья Зубрилина

Графы с цветными рёбрами и их интерпретация с помощью чисел Рамсея

Зубрилина Софья Феликсовна

Россия, Липецкая область, г. Липецк

МБОУ лицей №66, ЦДО “Стратегия”, 8 класс

Научны руководитель к.т.н., доц.кафедры прикладной математики Липецкого государственного технического университета Шуйкова И.А.

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

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

1. изучение графов и их основных свойств, составление списка литературы;
2. изучение алгоритмов реберной раскраски графов и оценка их сложности;
3. рассмотрение прикладных задач, которые формализуются при помощи графов;
4. изучение чисел Рамсея, позволяющие интерпретировать графы с цветными ребрами;
5. программная реализация жадного алгоритма реберной раскраски двудольного графа;
6. анализ свойств реализованного алгоритма.

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

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

Практической основой данной работы послужила проблема составления расписания для «Дня Здоровья», проводимого во всех поликлиниках города. В этот день приглашают квалифицированных врачей из других городов. И все жители могут проконсультироваться у них. Но необходимо решить проблему приёма пациентов, так как создать “живую” очередь в поликлинике будет очень неудобно. Я предлагаю своё решение этой задачи, которое будет опираться на жадный алгоритмы рёберной раскраски графов.

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

В результате проделанной работы были сформулированы следующие выводы:

1. Изучены алгоритмы реберной раскраски графов, создана программная реализация одного из алгоритмов.
2. Изучены графы и их некоторые основные свойства.
3. Изучены алгоритмы рёберной раскраски и их свойства, произведена оценка сложности и время работы алгоритма.
4. Рассмотрены прикладные задачи, которые формализуются при помощи графов.
5. Решена практическая задача “Дне Здоровья”.
6. Изучены числа Рамсея, позволяющие интерпретировать графы с цветными ребрами.

Исследование опирается на следующие библиографические источники:

1. Асанов М., Баранский В., Расин В. — Дискретная математика: Графы, матроиды, алгоритмы — СПб.: Издательство «Лань», 2010. — 291 стр.
2. Шикин Е. В., Чхартишвили А. Г. Математические методы и модели управлений: Учеб. Пособие. – М.: Дело, 2000.
3. Березина Л. Ю. Графы и их применение.: Популярная книга для школьников и преподавателей. Изд. стереотип. — М.: Книжный дом “ЛИБРОКОМ ”, 2014.
4. Дискретная математика для программистов / Ф. А. Новиков – СПб: Питер,

• 10 декабря 2015 г.
• Михаил Первеев

Исследовательский проект: «Комбинаторные задачи. Анализ решения при помощи рекуррентных соотношений и производящих функций»

МАУ ДО ЦДО «Стратегия» и МБОУ СОШ №2 г.Липецка

Шуйкова Инесса Анатольевна, к.т.н., доц. кафедры прикладной математики ЛГТУ

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

Методы, используемые в работе: методы дискретной математики и теории производящих функций.

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

Описание научно-исследовательской работы: в предлагаемой работе рассматриваются методы решения комбинаторных задач: при помощи их рекуррентное представления и решения рекуррентных соотношений и с использованием производящих функций. Рассматриваются решения задач: “Числа Фибоначчи”, “Размен”, “Счастливые билеты” двумя методами. Реализована компьютерная программа, генерирующая комбинаторные объекты.

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

Библиографический список:

1. Виленкин Н.Я. Популярная комбинаторика. – М.: “Наука”, 1975.
2. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. – М.: “Мир”, 1998.
3. Костюкова Н.И. Основы информационных технологий. Графы и их применение. Комбинаторные алгоритмы для программистов. – М.: “БИНОМ. Лаборатория знаний”, 2007.
4. Ландо С.К. Введение в дискретную математику. – М.: МЦНМО, 2012.
5. Сайт алгоритмов и программ [Электронный ресурс] // MAXimal. URL: http://e-maxx.ru/
6. Сайт о производящих функциях последовательностей [Электронный ресурс] // Производящие функции 2010. URL: http://genfunc.ru/

• 24 декабря 2015 г.
• Тимофей Советников

Исследовательский проект: «Экстремальные свойства Платоновых тел, ограниченных правильными треугольниками.»

Советников Тимофей Олегович

Муниципальное автономное образовательное учреждение лицей №18 г. Калининград

Малаховский Николай Владиславович, к.ф.-м.н., доцент кафедры естественнонаучных и технических дисциплин Московского государственного университета технологии и управления (Калининградский филиал)

Цели и задачи:

Научная работа посвящена изучению экстремальных свойствами правильных пирамид. Выражением этих экстремальных свойств являются определённые оценки, справедливые для правильных пирамид с любым числом боковых граней, но которые достигаются только в случае правильных пирамид, у которых все рёбра равны между собой с числом сторон правильного многоугольника, являющегося её основанием, равным 3,4 и 5.

Актуальность, значимость и новизна:

В естественных науках встречаются многие правильные тела, но особое значение имеют правильные многогранники с треугольными гранями тетраэдр, октаэдр и икосаэдр. Например, в структурной химии координационный полиэдр с треугольными гранями представляет собой наиболее компактное расположение соседних атомов, кроме этого существуют и другие причины широкой распространенности тетраэдрической н октаэндрической координации. Икосаэдрическая координация обнаружена в многочисленных структурах сплавов. По вершинам икосаэдра, например, расположены 12 связанных с металлом кислородных атомов в ионе Се(МОз)о3 и карбонильные группы в Fe3(CO)i2 и Со4(СО). Икосаэдрнческие группы присутствуют в элементном боре и некоторых борндах. Кроме того, из икосаэдров или из их частей построен макет, состоящий из атомов бора, во многих боранах. Возникает вопрос об особенной значимости именно тех Платоновых тел, гранями которых являются правильные треугольники. В научной работе этот феномен объясняется экстремальными свойствами правильных пирамид с равными рёбрами, порождающих эти тела.

Итоги исследования

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

Список использованной литературы:

1. Александров А.Д. Выпуклые многогранники. – М.-Л.; 1950.
2. Долбилин Н.П. Жемчужины теории многогранников. – М.: МЦНМО, 2000, с.27-31.
3. Люстерник Л.А. Выпуклые фигуры и многогранники. – М.; 1956.
4. Перепелкин Д.И. Курс элементарной геометрии. Часть II. Геометрия в пространстве. – М.-Л.: Гостехиздат, 1949, с. 34, с.268.
5. Смирнова И.М. В мире многогранников. – М.: Просвещение, 1995.
6. Яглом И.М., Болтянский В.Г. Выпуклые фигуры. – М.-Л.; 1951 /Библиотека математического кружка, выпуск 4.

• 24 декабря 2015 г.
• Анастасия Карбышева

Исследовательский проект: «Пространства квадратов Дюрера»

Карбышева Анастасия Александровна

Муниципальное автономное образовательное учреждение лицей №18 г. Калининград

Научный руководитель: Малаховский Николай Владиславович, к.ф.-м.н., доцент кафедры естественнонаучных и технических дисциплин Московского государственного университета технологии и управления (Калининградский филиал)

Цели и задачи:

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

Актуальность и новизна исследования:

Теория магических квадратов прошла долгий и сложный путь развития. В XIX и XX веках интерес к магическим квадратам вспыхнул с новой силой. Они нашли своё применение в криптографии и приборостроении. Особое место в теории магических квадратов занимает разработка методов их построения. Магические квадраты могут быть применены в криптографии. Они позволяют создать алгоритм перевода зашифрованного текста в изображение и, наоборот. Магические квадраты применяются в технологиях создания телевизоров, что позволяет обеспечить плавные цветовые переходы, полностью устраняя видимые границы на больших однотонных полях изображения.

Описание научно-исследовательской работы:
В научной работе рассматриваются пространства и подпространства, порождаемые магическими квадратами Дюрера. На множестве всех квадратов Дюрера вводятся операции сложения и умножения квадрата Дюрера на действительное число. Доказывается, что множество всех квадратов Дюрера обладает структурой семимерного векторного пространства D над множеством всех действительных чисел , так как в результате этих операций сохраняются магические свойства этих квадратов. Определяется аффинное подпространство(D) пространства D. Рассматривается пятимерное векторное подпространство P пространства D пандиагональных квадратов. Проводятся метрические исследования в подпространствах (D) and P.

Итоги исследования:

Используя методы линейной алгебры в работе получен ряд новых научных результатов по теории магических квадратов Дюрера В частности, рассмотрены пространства и подпространства, порождаемые магическими квадратами Дюрера. На множестве всех квадратов Дюрера введены операции сложения и умножения квадрата Дюрера на действительное число. Доказано, что множество всех квадратов Дюрера обладает структурой семимерного векторного пространства D над множеством всех действительных чисел . Определено аффинное подпространство(D) пространства D. Рассмотрено пятимерное векторное подпространство P пространства D пандиагональных квадратов. Проведены метрические исследования в подпространствах (D) and P.

Список использованной литературы:

1. Я. В. Успенский. Избранные математические развлечения.- Сеятель, 1924.
2. Б. А. Кордемский. Математическая смекалка.- М.: ГИФМЛ, 1958.- 576с.
3. М. М. Постников. Магические квадраты.- М.: Наука, 1964.
4. Н. М. Рудин. От магического квадрата к шахматам.- М.: Физкультура и спорт, 1969.
5. Е. Я. Гуревич. Тайна древнего талисмана.- М.: Наука, 1969.
6. М. Гарднер. Математические досуги.- М.: Мир, 1972.
7. Ю. В. Чебраков. Магические квадраты. Теория чисел, алгебра, комбинаторный анализ.- СПб.: СПб гос. техн. ун-т, 1995.
8. Ю. В. Чебраков. Теория магических матриц.- СПб., 2008.
9. М. Гарднер. Глава 17. Магические квадраты и куб.

• 24 декабря 2015 г.
• Артем Сизых

Исследовательский проект:»Семейства героновых треугольников»

Сизых Артём Константинович

Муниципальное автономное образовательное учреждение лицей №18 г. Калининград

Малаховский Николай Владиславович, к.ф.-м.н., доцент кафедры естественнонаучных и технических дисциплин Московского государственного университета технологии и управления (Калининградский филиал)

Краткая постановка цели и задач исследования:

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

Актуальность, значимость и новизна, итоги исследования:

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

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

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

1. сформулирована и доказана теорема, определяющая однопараметрические λ — семейства героновых треугольников;
2. проведена классификация героновых треугольников, соответствующих различным значениям параметра ;
3. используя таблицу λ — семейств героновых треугольников расширена известная классификация героновых треугольников.

Список использованной литературы:

1. Бухштаб А.А., теория чисел, М., Наука, 1967
2. Кордемский Б. Формулы, производящие героновы триады. ЗС // МВШ, 1984, № 4.
3. Люберанский А. И. Что можно узнать из формулы Герона?// Математика в школе. – 1998. – №6. – с.55–56.
4. Еременко С.Б., Сохет А.М., Ушаков В.Г. Элементы геометрии в задачах. – М.:МЦНМО.2003.

• 24 декабря 2015 г.
• Александр Терентьев

Исследовательский проект: «Обобщение формулы Декарта на n- мерное евклидовое пространство «.
Терентьев Александр Денисович
Муниципальное образовательное учреждение лицей №18 г. Калининград
Малаховский Николай Владиславович, к.ф.-м.н., доцент кафедры естественнонаучных и технических дисциплин Московского государственного университета технологии и управления (Калининградский филиал)

Цели и задачи:

целями научной работы являются обобщения теоремы Декарта на случай n- мерного Евклидова пространства и её применение к задачам трёх мерного евклидова пространства. Решение поставленной задачи осуществляется методами линейной алгебры и математического анализа.

Актуальность и новизна исследования:

актуальность исследования заключается в том, что до этого не были рассчитаны максимальное количество сфер в цепи для Теоремы Декарта для 3-мерного Евклидова пространства и средняя погрешность в радиусах этих сфер.

Описание научно-исследовательской работы:

работа начинается с исторической справки, дальше методами линейной алгебры и математического анализа выведена и доказана Обобщённая теорема Декарта для 3-мерного и n-мерного Евклидова пространств, а так же расчёт средней погрешности сфер в цепи для 3-мерного пространства.

Итоги исследования:

в ходе работы была выведена Обобщённая теорема Декарта для n-мерного Евклидова пространства, были рассчитаны максимальное количество сфер в цепи для Теоремы Декарта для 3-мерного Евклидова пространства и средняя погрешность в радиусах этих сфер.

Список использованной литературы:

1. Учебник 10-11 класса «Алгебра и начало анализа»
2. Курош А. Г «Курс высшей алгебры»
3. Р.Декарт «Рассуждение о методе»
4. Р.Декарт «Геометрия»
5. Р.Декарт «Правила для руководства ума»
6. Ресурсы интернет

• 24 декабря 2015 г.
• Александра Кормилицина

Исследовательский проект:»Стереометрический аналог теоремы Пифагора »
Кормилицина Александра Сергеевна
Муниципальное образовательное учреждение лицей №18 г. Калининград
Научный руководитель: Малаховский Николай Владиславович, к.ф.-м.н., доцент кафедры естественнонаучных и технических дисциплин Московского государственного университета технологии и управления (Калининградский филиал)

Целью научной работы является доказательства факта, что множество вершин невырожденных пифаго-ровых тетраэдров никогда не определяет сферу, а принадлежит эллипсоиду (в отличие от окружности в случае пифагоровых треугольников). В случае неравностороннего треугольника оси эллипса, обра-зованного сечением эллипсоида плоскостью обладают экстремальными свойствами.

Описание научно-исследовательской работы:

В научной работе рассмотрено одно из обобщений теоремы Фалеса на случай трёхмерного пространства и доказано, что в этом случае теорема не верна.

Актуальность, значимость и новизна исследования:

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

Итоги исследования:

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

Список использованной литературы:

1. Скопец З. А. Геометрические миниатюры, М. Просвещение,1990
2. Еленьский Щ. По следам Пифагора. М. Просвещение, 1961
3. Глейзер Г. И. История математики в школе. М. Просвещение, 1982
4. Литцман В., «Теорема Пифагора» М. Просвещение, 1960.

• 25 декабря 2015 г.
• Екатерина Соколова

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

• 26 декабря 2015 г.
• Никита Мариевский

Исследовательский проект:»Обобщение теоремы Пифагора на правильные n- угольники«

Мариевский Никита Андреевич.

Муниципальное автономное образовательное учреждение лицей №18 г. Калининград.

Малаховский Николай Владиславович, к.ф.-м.н., доцент кафедры естественнонаучных и технических дисциплин Московского государственного университета технологии и управления (Калининградский филиал).

Краткая потановка цели и задач исселедования:

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

Описание научно-исследовательской работы:

В научно-исследовательской работе определяется зависимость площади,измеряемой в квадратных единицах, от площади, измеряемой в n-ных единицах, откуда получается вывод, что коэффициент пропорциональности не зависит от длин сторон многоугольника.

Актуальность, значимость и новизна исследования:

Теорема Пифагора играет в геометрии исключительную роль. На ней основано применение в евклидовой геометрии метода координат, который позволяет привнести в геометрию алгебраические методы. Отказываясь от тех или иных условий, можно получать различные обобщения теоремы Пифагора, которые позволяют взглянуть на неё с неожиданной стороны.

Итоги исследования:

Получена связь между обычной площадью (в квадратных единицах) правильного n-угольника со стороной a+b и той же самой площадью, выражаемая в новых единицах.Доказана теорема: площадь правильного n-угольника со стороной a+b равна сумме n площадей треугольника и площади правильного n-угольника со стороной равной смежной гипотенузе (соответственно гипотенузе). Теорему можно рассматривать как n-ный аналог теоремы Пифагора, поскольку в теореме Пифагора единицей измерения площади является площадь квадрата со стороной равной единице длины, соответственно для n-ного аналога теоремы Пифагора единицей измерения площади естественно считать площадь правильного n-угольника со стороной равной единице длины.

Список использованной литературы:

1. Скопец З. А. Геометрические миниатюры, М. Просвещение,1990
2. Еленьский Щ. По следам Пифагора. М. Просвещение , 1961
3. Глейзер Г. И. История математики в школе. М. Просвещение , 1982
4. Литцман В., «Теорема Пифагора» М. Просвещение , 1960.

Файл читается в документе word.

• 28 декабря 2015 г.
• Иван Молчанов

Информационно – моделирующая программа «Моделирование броска тела под углом к горизонту»

Молчанов Иван Витальевич ученик 11 «А» класса, ГУО «Гимназия №1 г. Бреста».

Краткое описание

Данный проект является универсальной информационно – моделирующей системой для изучения темы «Моделирование броска тела под углом к горизонту» из курса физики.

Проект состоит из трёх частей: основной клиентской «Информационно-тестирующей части», «Редактора заданий теста» и серверной части «Сервера».

Информационно-тестирующая часть – запускаемый файл MyGL.exe

Главное окно программы содержит закладки, соответствующие основным её пяти разделам: «Старт», «Теория», «Модель», «Тест», «Отчёт».

Раздел «Старт» содержит название программы и раздел регистрации пользователя. Регистрацию необходимо пройти, если будет осуществляться тестирование с отправкой результатов на сервер. После заполнения всех полей формы регистрации надо нажать кнопку «Подтвердить». Если связь с сервером не предполагается, то регистрацию можно пропустить, нажав кнопку «Игнорировать».

Раздел «Теория» содержит теоретическую информацию по соответствующей теме. В этом разделе организована возможность просмотра множества страниц и их нумерация.

Раздел «Модель» является основным и позволяет произвести моделирование полёта тела, брошенного под углом к горизонту. Модель является визуальной и динамической.

Раздел «Тест» позволяет пройти тест по соответствующей теме. Запуск теста производится нажатием на кнопку «Начать тестирование».

Раздел «Отчёт» содержит подробные результаты выполнения теста. А именно, количество правильных ответов, оценку, а также таблицу с результатами ответов по каждому вопросу.

Редактора заданий теста – запускаемый файл Redactor.exe. Главное окно программы содержит закладки, соответствующие основным её двум разделам: «Часть А» и «Часть В». Редактора заданий теста позволяет вводить текст вопроса, варианты ответов и правильный ответ. Каждый вопрос и варианты ответа сохраняются в файле, содержание которого шифруется. Впоследствии, при использовании вопроса при тестировании варианты ответов переставляются случайным образом.

Сервер – запускаемый файл Server.exe. Должен быть запущен на компьютере учителя. Имеются две кнопки, включающие и отключающие сервер и таблица, в которой будут отображаться результаты тестирования учащихся, передаваемые с компьютеров-клиентов по локальной сети.

• 29 декабря 2015 г.
• Денисия Довга

Петер Густав Лежен Дирихле и его принцип.

Исполнитель: Довга Денисия Кемаловна, Ревунова Дарья Дмитриевна, 8 класс

Руководитель: Калеганова Марина Валерьевна, Учитель математики первой категории

Автономное общеобразовательное учреждение Муниципального образования г. Долгопрудного средняя общеобразовательная школа №1 (АОУ школа №1)

Наша работа касается одного из интересных эвристических методов решения математических задач — принципа Дирихле. Принцип назван в честь немецкого математика Петера Густава Лежена Дирихле (1805-1859 г.), который успешно применял его к доказательству арифметических утверждений.

Целями работы являются следующие:

1. изучить, один из основных методов математики, принцип Дирихле.
2. Выявить круг задач, решение которых основывается на принципе Дирихле;

Задача: Научиться применять соответствующие формулировок принципа Дирихле – наиболее рациональный подход при решении задач.

Объектом нашего исследования является принцип Дирихле

Предметом нашего исследования является различные формулировки принципа Дирихле и их применение при решении задач.

Итоги исследовательской работы.

Петер Густав Лежен Дирихле –автор многих достижений в области математики, но одна из его важнейших заслуг – это формулировка логического приема доказательства, названного его именем. Принцип Дирихле применяется в разных разделах математики: в арифметике, в комбинаторике, в геометрии. Этот принцип можно применять в повседневной жизни, что развивает логическое мышление.

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

Многие олимпиадные задачи решаются, используя это специальный метод.

Дирихле – автор многих достижений в области математики, одна из его важнейших заслуг — это логический прием доказательства, названный его именем.

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

Список используемой литературы

1. http://mirznanii.com/info/id-85
2. https://ru.coursera.org/learn/teoriya-grafov/lecture/lpD8n/nachalo-dokazatiel-stva-primienieniie-printsipa-dirikhlie
3. http://www.problems.ru/articles/216.php
4. https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B8%D0%BD%D1%86%D0%B8%D0%BF_%D0%94%D0%B8%D1%80%D0%B8%D1%85%D0%BB%D0%B5_(%D0%BA%D0%BE%D0%BC%D0%B1%D0%B8%D0%BD%D0%B0%D1%82%D0%BE%D1%80%D0%B8%D0%BA%D0%B0)
5. https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B8%D0%BD%D1%86%D0%B8%D0%BF_%D0%94%D0%B8%D1%80%D0%B8%D1%85%D0%BB%D0%B5
6. https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B8%D0%BD%D1%86%D0%B8%D0%BF_%D0%94%D0%B8%D1%80%D0%B8%D1%85%D0%BB%D0%B5_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D1%84%D0%B8%D0%B7%D0%B8%D0%BA%D0%B0)
7. http://math4school.ru/princip_Dirihle.html
8. http://www.kvant.info/spivak67/archiv/19992000/spivak67/s_diri.htm
9. http://ermine.narod.ru/MATH/STAT/DIRIHLET/sect1.htm
10. http://math4school.ru/princip_Dirihle.html

• 3 января 2016 г.
• Андрей Заводов

1) Физика. Обучающая и тестирующая система

2) Заводов Андрей Павлович

3) МОУ Лицей №43, г. Саранск

4) Виктор Иванович Ивлев, Профессор кафедры физики твердого тела МГУ им. Огарева

5) Цели и задачи:

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

6) Физика. Обучающая и тестирующая система — приложение, позволяющее в удобной форме изучать все термины из школьного курса физики.

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

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

В новой версии добавлены новые возможности тестирования: вставка пропущенных слов в определения или тестирования с вариантами ответа.

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

Особенности Физика. Обучающая и тестирующая система:

• База данных содержит 460 определений.
• 3 варианта тестирования: развернутый ответ, выбор правильного варианта, вставка пропущенных слов
• Возможность самим создавать и настраивать тесты
• Можно одновременно сравнивать несколько результатов.
• Все результаты шифруются.
• Вы можете сами настроить шрифт и размер текста.

7) Постоянно возрастает потребность в тестировании и быстрой проверки работ. Но до сих пор нет системы, которая анализирует и проверяет работы со свободной формой записи ответов.

8) Моя программа учитывает падежи, наличие и отсутствие слов, наличие и отсутствие лишних слов, а также словосочетания и порядок постановки слов в ответе. Опираясь на все эти данные, она выдает совпадение текстов в процентном соотношении, что дает возможность проводить тестирование с развернутым ответом.

9) После долгого редактирования и подгонки конечной формулы, удалось вывести оптимальный (на данный момент) вариант оценки работ.

• 7 января 2016 г.
• Олег Балезин

8-ая международная конференция научно-технических работ школьников «Старт в Науку»

Название научно-исследовательской работы: «Компьютерное моделирование загрязнений атмосферы».

ФИО автора работы: Балезин Олег Александрович, 22.09.2000.

Образовательное учреждение, в котором обучается автор работы: ученик 9 класса МАОУ «Лицей №102 г. Челябинска»

ФИО, должность и место работы научного руководителя: Пашнин Андрей Александрович, педагог дополнительного образования класса МАОУ «Лицей №102 г. Челябинска»

Краткая постановка цели и задач исследования.

Разработка программного комплекса способного моделировать устойчивую картину распространения загрязнений в атмосфере.

Задачи проекта: Реализовать алгоритм моделирования распространения загрязнения атмосферы c использованием клеточных автоматов. Протестировать программу.

Основной текст тезисов. Краткое техническое описание проекта

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

Актуальность исследования.

Состояние качества воздушной среды в городах в настоящее время является одной из острейших проблем современности. В большинстве городов мира загрязнение воздуха достигает критических размеров. По оценкам Всемирной организации здравоохранения (ВОЗ), показатели качества воздуха в 20 крупнейших городах мира в несколько раз превышают установленные ВОЗ нормативы. Более 1 млрд. горожан подвержены воздействию опасных для здоровья уровней загрязнения воздуха.

Значимость и новизна исследования.

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

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

Итоги исследования.

Решены сформулированные задачи проекта:

Реализован алгоритм клеточных автоматов для моделирования загрязнения атмосферы. Программа протестирована на различных конфигурациях. Алгоритм показал адекватные результаты: распространение загрязнений происходило по площадям эллиптической формы по направлению розы ветров.

Перспективы проекта: Привязка данной программы к реальным компьютерным картам местности посредством функции API. Совершенствование интерфейса. Интеграция программного комплекса с системой датчиков загрязнений для оперативного моделирования.

• 7 января 2016 г.
• Мухиба Рахимова

НАУЧНЫЙ ПРОЕКТ НА ТЕМУ:

«ДОКАЗАТЕЛЬСТВА НЕРАВЕНСТВ С ПОМОЩЬЮ ЛИНЕЙНОЙ И КВАДРАТИЧНОЙ ФУНКЦИЙ».

Исполнитель:

Рахимова Мухиба Алишеровна — ученица 11 « В» класса, Президентского лицей — интерната для одаренных детей города Душанбе, Таджикистан.

Научный Руководитель:

Олимджони Пирахмад – учитель по подготовке школьников к олимпиадам по математике в школе «Хотам и ПВ».

Введение

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

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

Приведенный в настоящей работе метод является простым и конкретным методом для решения этих задач.

Краткая постановка цели и задач исследования

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

Заключение

Этот проект включает в себя методы доказательств алгебраических неравенств с помощью линейной и квадратичных функций. До сих пор многие сложные (олимпиадные) неравенства не имеют конкретного и простого метода решений. Этот метод является конкретным и простым для решения многих сложных неравенств. Для использования такого метода для доказательства неравенств достаточно знать характер графика линейных и квадратичных функций. Как отмечено выше, во многих сложных неравенствах можно использовать упамянутые в проекте полезные леммы. А так же, во многих неравенствах можно использовать некоторые известные неравенства или какие-то преобразования с условиями, а потом этот метод. Многие неравенства имеют сложную траекторию решения. С помощью этого метода можно составить задачи для математических олимпиад или математических экзаменах. Для этого необходимо пройти с конца решения вышеупомянутых задач до какого-то результата.

Список использованной литературы

[1] Pham Van Thuan, Trieu Van Hung, Proving inequalities using linear functions, Mathematical Reflections 4 (2006).

[2] Vo Thanh Van, Bat Dang ThucSchurVa Phuong PhapDoi Bien P, Q, R.

[3] Titu Andrescu, Vasile Cirtoaje, Gabriel Dospinescu, MirceaLascu, Old and New Inequalities, Gil Publishing House, 2004.

[4] Vasile Cîrtoaje, Discrete Inequalities, Volume 1, Symmetric Polynomial Inequalities, Art Of Problem Solving 2015.

[5] Vasile Cîrtoaje, Discrete Inequalities, Volume 2, Symmetric Rational Inequalities, Art Of Problem Solving 2015.

• 10 января 2016 г.
• Марина Ионова

Поиск выигрышных стратегий в математической игре «Гекс»

Ионова Марина Олеговна

ГБОУ гимназия г. Сызрани

науч. рук. Константинова Ирина Альбертовна, у читель математики ГБОУ Гимназия г. Сызрани

Целью работы является поиск выигрышных стратегий для игры «Гекс» на полях разной размерности.

Основные задачи исследования: сбор и изучение информации о правилах и истории математической игры «Гекс», рассмотрение подходов классической и прикладной математики к вопросу о выигрыше в игре, составление алгоритмов для выигрыша в игре на полях разной размерности.

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

Игра «Hex» (Гекс) популярна среди школьников и студентов. Правила игры очень просты. Играют двое на четырехсторонней доске из правильных шестиугольников фишками двух цветов. Размеры доски могут быть 4х4, 5×5, 6×6 и 7×7 шестиугольников. Две противоположные стороны доски объявляются «красными», две другие – «синими». Игроки по очереди выкладывают свои фишки. За каждым игроком закреплена пара сторон доски – одинаковых по цвету с его фишками. Цель каждого игрока – соединить связным путем свои стороны своими фишками.

На своем опыте убеждаешься, что игра довольно-таки занимательная, но тут же назревает вопрос: существуют ли выигрышные алгоритмы для обоих игроков? Я поставила перед собой задачу, составить алгоритмы для выигрыша в игре на полях разной размерности (4х4, 5х5, 6х6, 7х7), для чего изучила литературу по данной теме, проанализировала логические основы поиска выигрышных комбинаций и рассмотрела подходы теоретической и прикладной математики к проблеме поиска выигрышной стратегии в игре.

Научные работы, направленные на поиск выигрышных алгоритмов в математических играх, довольно популярны. Однако поиск выигрышных стратегий для игры в «Hex» ранее был не изучен или, по крайней мере, не опубликован, в этом и заключается новизна и актуальность данного исследования.

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

По результатам исследования составлены алгоритмы для выигрыша в игре на полях разностью 4х4, 5х5, 6х6 и 7х7 и применение их для решения условных задач в игре. Так же исследовательская работа имеет немало перcпективных оснований для развития данной игры, такие как разработка 3D версии игры или практическое применение результатов исследования в различных отраслях науки и техники.

Литература

Садовский Л.Е., Садовский А.Л. Математика и спорт / Библиотечка «Квант» вып. 44 – М.: Наука, 1985. – 193 с.

Гекс. Свободная энциклопедия «Википедия». – URL: https://ru.wikipedia.org/wiki/Гекс

• 11 января 2016 г.
• Кирилл Рябцовский

“Расчет количества путей в ориентированном графе”.

Автор: Рябцовский Кирилл Викторович

Школа № 4 7”В” класс г. Сергиев Посад Московской области

Научный руководитель: Машков Дмитрий Александрович

Заместитель начальника отдела сопровождения информационной безопасности Департамента безопасности “Россельхозбанк”.

Цель: разработать математическую модель и алгоритм реализации расчета количества путей в направленном графе и реализовать это в компьютерной программе.

Важность решения данной задачи определена как одна из интереснейших задач теории графов, так и тем, что имеются типовые задачи на ЕГЭ по информатике.

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

• 12 января 2016 г.
• Даниил Пекишев

Цель данной работы: познакомиться с различными методами, позволяющими предъявить нужное замощение или доказать, что требуемое замощение невозможно.

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

В пункте «Паркеты» мы иллюстрируем паркеты, придуманные нами как на плоскости, так и в пространстве, показываем, как с помощью параллельного переноса можно заполнить всю плоскость (всё пространство) данными фигурками, используя для доказательства возможности замощения теорию «Сравнения по модулю». В приложении рассматриваются задачи, составленные автором работы по выше названной теме и приводятся хорошо известные в литературе любопытные результаты «о невозможном и возможном замощении».

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

1) нужную раскраску или определённое расположение чисел на фигуре и полимино;

2) необходимое условие для существования замощения, используя теорию групп;

3) необходимое и достаточное условие регулярности прямоугольного полимино.

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

• 12 января 2016 г.
• Ростислав Цветков

Автор: Цветков Ростислав
Челябинская область, г. Челябинск, Муниципальное общеобразовательное учреждение лицей №11, класс 11
Научный руководитель: Замоздра Сергей Николаевич
Кандидат физико-математических наук, доцент, в должности профессора кафедры теоретической физики ЧелГУ.

Исследование последствий удара метеорита о лёд на воде

Внезапно и непрерывно на Землю падают различные космические тела, но все они в основном разрушаются в атмосфере. Небесные тела, имеющие размеры от одного до нескольких десятков метров, частично сгорают в атмосфере. Остатки этих тел, упавшие на поверхность Земли и образующиеся от них ударные волны могут вызвать существенные разрушения.
Целью нашей работы является предсказывание последствий удара метеорита. Это предсказание может быть выполнено с помощью компьютерного моделирования (преимущество данного метода – возможность широкого выбора параметров) и с помощью экспериментов (ограниченность параметров). Наша цель в этом году – создание компьютерной модели, которая будет наглядно демонстрировать момент падения метеорита в озеро, покрытое льдом.
Основные этапы:
1) Изучить основы метеоритики.
2) Собрать экспериментальную установку для моделирования удара метеорита о водоем, покрытый льдом
3) Создать компьютерную модель падения метеорита в водоем со льдом
4) Обработать и проанализировать результаты
В прошлом году мы исследовали удар метеорита о лёд на воде с помощью натурной модели. В этом году мы продолжили эти исследования с помощью компьютерной модели. Метеорит, лёд и вода представлены как системы частиц. Каждая частица взаимодействует со всеми остальными частицами. Уравнения движения частиц решаются численно методом Эйлера для двухмерной модели, и методом Верле для трёхмерной модели. Программа написана на языке Pascal. В программе можно задать такие параметры как плотность среды, количество частиц, их массу и начальную скорость, толщину слоёв и т.д. Для метеорита можно задавать те же параметры, но отдельно от остальных частиц. Для графического представления результатов вычислений используется программа Gnuplot. Так как данные о положении частиц записываются блоками (один блок – это один момент времени), мы получаем последовательность кадров.
Актуальность работы: Созданная компьютерная модель универсальна и может использоваться не только в метеоритике, но и в других областях науки, где необходимо детально рассмотреть поведение материалов или среды под действием внешних сил. В нашей модели можно задавать любые параметры среды и материалов, а также любые условия.
Выводы:
Удалось при помощи компьютерного моделирования детально рассмотреть момент падения метеорита в озеро со льдом. Трехмерная модель оказалась реалистичней, чем двухмерная, несмотря на большее время расчета. Это связано с тем, что в двухмерной модели энергия от метеорита распространяется только в плоскости, а также потому, что в трёхмерной модели используется более продвинутый способ расчета новых координат частиц. Собранные данные позволяют доказать, что лед на воде гасит волну, которая образовалась при ударе метеорита. Сразу после удара волна имеет достаточно энергии, чтобы беспрепятственно ломать лед, однако при удалении от центра полыньи, амплитуда волны угасает, и чем дальше от центра, тем сложнее волне ломать лед. В данном случае лед выступает в роли гасителя удара. Компьютерное моделирование наглядно показало процессы, происходящие в момент падения метеорита в водоем со льдом. В будущих версиях программы планируется увеличить скорость расчетов и реалистичность модели путем добавления более точного расчета давления жидкости.
Литература

1. Астероидно-кометная опасность / под ред. А.Г. Сокольского. СПб.: ИТА РАН, 1996. 224с.
2. Бадюков, Д.Д. Фрагменты Челябинского метеоритного дождя: распределение по массам, размерам и возможная масса максимального фрагмента /Д.Д. Бадюков, А.Е. Дудоров //Геохимия. 2013. № 7. С. 642-646.
3. Бронштейн, В.А. Метеоры, метеориты, метеороиды / В.А. Бронштейн. М., 1987. 173с.
4. Дудоров, А.Е. Частота падения метеоритов / А.Е. Дудоров, О.В. Еретнова // Вестник Челябинского государственного университета. 2014. №1. Физика. Вып. 19. С. 58-67.
5. Катастрофические воздействия космических тел / под ред. В.В. Адушкина, И.В. Немчинова. М.: Академкнига, 2005.310 с.
6. Пустынский, В.В. Следы космических воздействий на Землю, сборник научных статей / под ред. А.Н. Дмитриева. Новосибирск, «Наука», Сибирское отделение, 1990. 212с.
7. Федынский, В. В. Метеоры / Лекции по астрономии
   Выпуск 4. Государственное издательство технико-теоретической литературы.
   Москва, 1956. 104с.

• 12 января 2016 г.
• Артур Степаненко

«MobiFast : разработка drag and drop CMS для создания мобильных версий сайтов без знания программирования»

Степаненко Артур Русланович ученик 11 класса, ГУО»Гимназия №56 г.Гомеля»

В 2015 году компания Google официально запустила систему Google Friendly. Теперь сайты, которые имеют мобильную версию для смартфонов, трафик с которых в Рунете составляет 30%,получают специальную отметку. В поисковой системе Google эти сайты индексируются лучше и получают некоторые привилегии. Хотя необходимость адаптировать свои сайты к экранам смартфонов возникла намного раньше, это событие подтолкнуло к оптимизации даже тех, кто до последнего не хотел этого делать. В интернете появились конструкторы гибридных приложений и сайтов с большим количеством копирайтов сервиса и рекламы. Другие же сделали ставку на платные тарифы. Но у данных сервисов есть один очень веский аргумент в защиту — они позволяют самостоятельно заниматься разработкой своего сайта людям без знания языков Web-программирования. Цель работы: максимальное облегчение разработки мобильных версий для владельцев сайтов, минимизирование их временных затрат. Актуальность темы: данная тема чрезвычайно актуальна как для владельцев сайтов, так и для пользователей, учитывая то, что доля мобильного трафика постоянно увеличивается и имеет дальнейшие тенденции к росту.

Задачи работы : 1. Разработать drag and drop CMS для создания мобильных версий сайтов без знания программирования. 2. Предусмотреть систему шаблонности. 3. Дать возможность пользователю редактировать исходный код. 4. Предусмотреть последующую компиляцию исходного кода в гибридные мобильные приложения на базе AngularJS.

• 13 января 2016 г.
• Виктория Головнева

1. Полное исследование функции. Применение знаний о свойствах функции к решению задач.
2. Автор работы: Головнева Виктория Владимировна
3. ГБОУ Лицей «МКШ им. В. Н. Челомея»
4. Тё Ольга Владимировна, учитель математики в ГБОУ Лицей «МКШ им. В.Н. Челомея»
5. В начале работы были поставлены цели:

• Определить уровень знаний учеников общеобразовательных школ темы «Исследование функции» путем тестирования на примере учеников школы №3 города Байконур.
• Проанализировать вариант ЕГЭ 2016 по математике и сделать вывод о количестве заданий, в которых необходимы знания о полном анализе функции, а так же свойств функции.
  Привести пример решения таких заданий.
  6. Первая часть работы посвящена определению уровня знаний темы «Функция. Графики функции. Полное исследование функции» у учеников общеобразовательных школ на примере учеников школы №3 города Байконур. Для этого вышеуказанным ученикам был предложен следующий тест.
  На основе результатов этого теста были сделаны выводы о необходимости создания альтернативного способа преподавания этой темы, а именно создания наглядного пособия с понятным объяснением.
  Затем был проанализирован вариант ЕГЭ 2016, сделан вывод о количестве заданий, для решения которых необходимы знания свойств функций.
  Были приведены примеры решения некоторых заданий с использованием знаний об исследовании функции.
  7. данная тема часто в ЕГЭ встречается, а ее объяснению в школьной программе отводится не так уж много времени и объяснение выполняется по старым образцам, сложным и непонятным языком. отсюда можно понять, что предложение альтернативного варианта преподавания данной темы, а так же приведение примера применения полученных знаний для решения задач.
  8.
  1. Учебник «Алгебра и математический анализ» 10 класс, Н.Я.Виленкин — М.,1931. — 115 с.
  2. Педагогический словарь. — М.: Академия. Г. М. Коджаспирова, А. Ю. Коджаспиров. 2005.
  3. Учебник «Алгебра. 8 класс» Теляковский
  4. Учебник «Алгебра. 9 класс» Теляковский — М.,1931. — 26с.
  5. http://www.oksanochka.com/003/001/024.shtml[Электронный ресурс]
  6. http://www.mathprofi.ru/asimptoty_grafika_funkcii.html[Электронный ресурс]

• 13 января 2016 г.
• Александр Назаренко

Расчёт траектории движения горячего пятна в аккреционном диске чёрной дыры

Исполнители: Дёмин Георгий, Назаренко Александр

Образовательное учреждение: Лицей Информационных Технологий №1533

Научный руководитель: Сергей Викторович Репин, сотрудник ИКИ (Института Космических Исследований)

Цель данной работы заключается в создании модели видимого движение горячего пятна, движущегося по круговой орбите в поле керровской чёрной дыры.
Продемонстрировать различие между привычной нам механикой Ньютона и
ОТО. Выполнить моделирование в рамках ОТО, путем численного решения
дифференциальных уравнений движения квантов, что позволит максимально точно продемонстрировать такие параметры, как время движения и энергию излучаемых квантов.

Описание научно-исследовательской работы: Виртуальное проектирование, реализованное в предлагаемом проекте, позволяет не только проводить точное исследование в области физики, но и детально понять, что такое искривленное пространство вокруг чёрной дыры. Для этого предлагается игра «Попади в пятно»,

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

а все движения моделируются в рамках механики ОТО.

Для построения видимой траектории горячего пятна необходимо

вычислить большое количество траекторий квантов, излученных изотропно этим

горячим пятном. Для численного решения дифференциальных уравнений

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

быстродействия. Язык C# используется для написания основного

тела программы и визуализации. Одной из трудностей было совместное

использование этих языков. Также существовала проблема

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

алгоритмов сортировки данных и их оптимального хранения.

Для дополнительной опции понадобилось сделать вид от наблюдателя,

был придуман новый алгоритм пересчёта координат.

Актуальность проекта обусловлена большим научным интересом к

развитию моделей таких астрофизических объектов как аккреционные

диски и черные дыры. Сами эти объекты находятся от нас на огромном

расстоянии и для понимания происходящих там процессов необходимо

численное моделирование наблюдательных эффектов общей теории

Итоги проделанной работы:

Разработана программа, позволяющая:

• Генерировать видимые движения горячих

пятен в аккреционном диске в рамках механики ОТО,

используя большой набор параметров;

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

хранить смоделированную орбиту в удобном и компактном виде и

быстро восстанавливать ее, не выполняя повторных вычислений.

Список используемой литературы:

1. A.F. Zakharov, S. Repin, Astronomy Reports, 43, 705, 1999.
2. A.F. Zakharov, S. Repin, Astronomy Reports, 46, 360, 2002.
3. L.R. Petzold, SIAM Journal of Sci. Stat. Comput., 4, 136, 1983.
4. Л.Д. Ландау, Е.М. Лифшиц. Теория поля, М., Физматлит, 2003. — 536
5. Д.С. Литвинцева. Дипломная работа в лицее 1533, 2014 г.

• 13 января 2016 г.
• Артем Малышев

Работа выполнена учеником 10 класса МБОУ Лицея №40 Малышевым Артемом Андреевичем.

Научный руководитель: Овсянников Роман Ильич кандидат физико-математических наук н.с. 380 отд. ИПФ РАН

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

Проблема: Классические методы моделирования взаимодействия молекул с внешним излучением приводят к «классическому» (непрерывному) спектру, тогда как из экспериментальных работ виден дискретный характер молекулярных спектров.

Цель работы: Расчёт колебательных спектров двухатомных молекул.

Объект исследования: Молекулярная спектроскопия.

Предмет исследования: Двухатомная молекула во внешнем поле.

Задачи:

1) написать одномерную модель изменения молекулярного состояния;
2) составить компьютерную программу, позволяющую рассчитывать взаимодействие молекулы с внешним полем;
3) провести серию расчётов для выявления зависимости величины взаимодействия от частоты и интенсивности внешнего поля;
4) провести сравнительный анализ (полученных в этой работе) спектров с известными (рассчитанными или измеренными в других работах) молекулярными спектрами.

Методы: 1) Численное дифференцирование (нахождение изменения волновых функций в пространстве);
2) Численное интегрирование (эволюция волновых функций во времени).
3) Метод Монте-Карло (случайный выбор начальных условий).

Значимость работы: Молекулярные спектры применяются в большом количестве приложений, где необходимо удалённое детектирование тех или иных молекул: от лабораторного и промышленного анализа газовых смесей до спектроскопического анализа космических объектов.

Литература

1. Бом Д. Квантовая теория. (2-е издание). М.: Наука, 1965
2. Фок В.А. Начала квантовой механики. М.: Наука, 1976
3. Фаронов В.В. Turbo Pascal 7.0. Начальный курс. Нолидж, 2000
4. Синай Я.Г. Курс теории вероятностей, изд. Московского университета, 1985

• 13 января 2016 г.
• Елизавета Масленникова

Задача Томсона для трех, четырех и шести зарядов

Масленникова Елизавета Алексеевна

Муниципальное бюджетное общеобразовательное учреждение «Физико-математический лицей» г. Сергиев Посад.

Забавин Валерий Николаевич, доктор физико-математических наук

Краткая постановка цели и задач исследования:

Доказать равновесность известных расположений на сфере трех, четырех и шести одинаковых зарядов помощью методов элементарной математики.

Описание научно-исследовательской работы:

В начале XX века, конструируя модель атома, английский физик Джозеф Джон Томсон рассматривал задачу о равновесном расположении зарядов на сфере. После открытия атомного ядра эта задача была отложена, а в последнее время вновь привлекла к себе внимание математиков. В некоторых случаях равновесное расположение известно (для небольшого числа зарядов). В части этих случаев равновесность доказана. В работе [1] сообщается, что для трех и четырех зарядов доказательства выполнены с помощью неравенств между средним арифметическим, средним геометрическим и средним гармоническим, но самого доказательства не приводится. В этой же работе выполнены доказательства для шести и двенадцати зарядов с помощью методов, известных узкому кругу специалистов.

Итоги исследования:

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

Список литературы:

1. Н. Н. Андреев, В, А, Юдин. Экстремальные расположения точек на сфере// Математическое просвещение (третья серия). Вып. 1 — М,:МЦНМО, 1997.

2. В. А. Юдин. Минимум потенциальной энергии точечной системы зарядов//Дискретная математика. 1992. Т. 4. Вып.2.

• 14 января 2016 г.
• Владислав Джиджоев

Решение проблемы навигации в крупных учреждениях с использованием концепции «Интернет вещей“

Автор: Джиджоев Владислав Муратович

Республика Северная Осетия-Алания, г. Владикавказ, МБОУ-лицей, 10 класс

Научный руководитель: Джаноян Елена Владимировна, учитель информатики, МБОУ-лицей г. Владикавказ

Цели и задачи: в данной работе рассматривается проблема навигации в распределённых учреждениях. Предлагается решение данной проблемы с использованием концепции «Интернет вещей», а в частности, технологии QR-кодов. Целью исследования являлась разработка информационной системы, решающей поставленную проблему, и её внедрение на территории Северо-Кавказского горно-металлургического института.

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

Результат работы: разработанный программный комплекс состоит из двух частей – серверной и клиентской. Серверная часть является веб-приложением, состоит из базы данных, в которой хранится информация обо всех объектах данной организации. Клиентская часть – это приложения для мобильных операционных систем Android и iOS. В них встроен сканер QR-кодов, который способен распознавать коды, физически находящиеся на объектах, и отображать информацию об объекте на экране мобильного устройства.

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

Весной 2015 года система интегрирована в СКГМИ. Созданы веб-сервер и мобильные приложения, необходимые для реализации проекта, развешены QR-коды на корпусах, постепенно они появляются и на этажах внутри зданий.

Ссылка на Android-версию: https://play.google.com/store/apps/details?id=com.expasys.skgmi

iOS версия находится на стадии публикации

Пример QR-кода для приложения:

Использованная литература:

1. Samuel Greengard. The Internet of Things, The MIT Press, 2015

2. Ovidiu Vermesan, Dr. Peter Friess. Internet of Things: converging technologies for smart environments and integrated ecosystems, River Publishers, 2013

3. Дино Эспозито. Программирование с использованием Microsoft ASP.NET 4, издательство Питер, 2012

4. Satya Komatineni. Dave MacLean. Pro Android 4, Apress, 2012

5. Matthew Knott. Beginning Xcode, Apress, 2014