Классические задачи Computer Science на языке Python. Обзор книги
- воскресенье, 20 декабря 2020 г. в 00:26:15
python
https://habr.com/ru/company/piter/blog/533902/
Привет, Хабр!
Одной из самых интересных наших книг по Python в течение уходящего года оставались "Классические задачи Computer Science на языке Python" от Дэвида Копеца.
Для тех, кто еще не успел ознакомиться с этой книгой, предлагаем ее обзор, написанный по оригинальному изданию в октябре 2019 года. Также можно ознакомиться с небольшим обсуждением на Reddit. Также все желающие могут высказаться по поводу допечатки — для этого в конце статьи поставлена голосовалка.
Мне очень понравилась книга «Классические задачи Computer Science на языке Python» от Дэвида Копеца. В ней действительно рассмотрено множество разнообразных проблем, подробной информации по которым мне ранее не попадалось. Лишь некоторые примеры: нейронные сети, задачи удовлетворения ограничений, генетические алгоритмы, алгоритм минимакс. В отличие от многих других книг по алгоритмам и задачам на программирование, в этой книге показаны полноценные (но небольшие) программы, которые вы с легкостью сможете исследовать самостоятельно.
Мне нравится изучать алгоритмы. Я проработал книгу «Карьера программиста», прошел несколько MOOC-курсов, в частности, "Design and Analysis of Algorithms" от профессора Тима Рафгардена. Тем не менее, в книге Копеца нашлись и такие алгоритмы, упоминания о которых я раньше не встречал.
Нейронные сети. Мой любимый раздел в книге посвящен нейронным сетям. Автор описывает создание полноценной нейронной сети. Тем временем он описывает, как работают все ее части – в общем и в частностях. Рассказывает, как устроены нейроны и слои, как действует функция активации, как при обучении используется обратное распространение, как корректируются веса.
Наконец, нейронная сеть используется на примере ирисов Фишера. Это классический набор данных, собранный в 1930-е, в котором представлено 150 экземпляров цветов, относящихся к различным видам ирисов (по 50 экземпляров каждого вида). Каждый экземпляр сопровождается четырьмя числовыми значениями: длина наружной доли околоцветника; ширина наружной доли околоцветника; длина внутренней доли околоцветника; ширина внутренней доли околоцветника. Сначала значения нормализуются. Затем создается сеть с тремя слоями. Во входном слое четыре нейрона (по одному на каждую категорию значений ввода из выборки), в скрытом слое шесть нейронов, а в выходном слое три нейрона (по одному на каждый рассматриваемый вид ириса).
Случайным образом были отобраны 140 из 150 образцов, которые затем использовались для обучения сети. Обучение прогоняется по 140 образцам за 50 итераций. Затем сеть используется для прогнозирования того, к какому из трех видов ирисов относятся 10 оставшихся образцов. В большинстве случаев сеть правильно идентифицирует как минимум 8 из 10 образцов, а достаточно часто – и все 10.
Мне в самом деле понравился такой опыт: запрограммировать с нуля целую нейронную сеть, не прибегая к библиотекам машинного обучения. Я некоторое время поэкспериментировал с этой программой (весь код к книге выложен на GitHub). Например, я вывел распечатку всех весов во всех нейронах после того, как сеть была полностью обучена. Я хотел взглянуть, будет ли прослеживаться сходство между весами между разными прогонами. Оказалось, что от прогона к прогону веса поразительно отличаются, хотя, прогностическая успешность во всех случаях оставалась схожей. Может быть, это азбучная истина, но мне было очень интересно убедиться в этом самостоятельно.
Состязательный поиск. В этой главе мы знакомимся с алгоритмом минимакс. Он находит наилучший ход в игре с нулевой суммой, в которой участвуют два соперника. Идея заключается в анализе потенциальных ходов, выступая от имени то одного, то другого соперника; каждый соперник реагирует на последний из сделанных ходов, пока игра не будет завершена (либо не будет достигнута максимальная глубина рекурсии). В первом примере из книги ИИ играет в крестики-нолики. В данном случае может быть полностью проанализирована вся последовательность ходов, так как размер игрового поля составляет всего 3 на 3 клетки.
Как и в других главах, здесь сначала разрабатывается общая структура, которая затем рассматривается применительно к сложным случаям. После примера с крестиками-ноликами таким же образом разбирается игра «Четыре в ряд». В данном случае оценка ходов гораздо сложнее, чем в «Крестики-нолики», поэтому здесь поиск в глубину ограничен тремя ходами. Я много обращался к этой главе, поскольку ранее не встречал описания алгоритма минимакс.
Задачи на удовлетворение условий. Здесь также разрабатывается общая структура, которая затем используется для решения нескольких задач. В сердце этой структуры – рекурсивный поиск с возвратом. Первая проблема, решаемая в этой главе – это задача раскрашивания карты Австралии. Можно ли обойтись всего тремя цветами и раскрасить карту так, чтобы смежные территории по обе стороны любой границы между регионами отличались по цвету? (Ответ: да). Вторая задача – расставить восемь ферзей на шахматной доске, добившись, чтобы ни один ферзь не был под боем у любого другого. Третья задача – расставить список слов в виде сетки, чтобы получился квадрат для поиска слов. Наконец, структура используется для решения классической криптоарифметической загадки SEND + MORE = MONEY. Цель – выяснить, каким цифра соответствует каждая буква, чтобы получившееся арифметическое равенство было верным.
Эта глава мне понравилась, так как в ней приведено много очень разнообразных примеров, а также поскольку ранее я не пользовался таким подходом для решения подобных задач (как минимум, систематически).
Генетические алгоритмы. Прежде, чем я изучил эту главу, я лишь в самых общих чертах представлял себе, как работают генетические алгоритмы. В коде к этой главе демонстрируется класс-хромосома, который инстанцируется случайно выбранными генами. Хромосома может оценивать собственную приспособленность к среде и реализует скрещивание (комбинацию себя самой с другой хромосомой того же типа), а также мутирует (вносит сама в себя небольшие, совершенно случайные изменения).
Алгоритм начинается со случайной популяции. В каждом поколении этой популяции алгоритм проверяет (при помощи функции приспособленности), имеется ли достаточно хорошее решение (приспособленность выше заданного порогового значения). Если такого решения нет, то создается новое поколение путем многократных операций по скрещиванию пар особей (чем выше приспособленность каждой отдельной особи, тем вероятнее, что эти особи пойдут в дело). Далее несколько особей отбирается для мутаций. Теперь эти новые особи дают начало новой популяции и, опять же, проверяются их функции приспособленности. Цикл повторяется для заданного количества поколений.
В качестве примеров рассматривается решение следующих задач: максимизация математического выражения, загадка «SEND + MORE = MONEY», упоминавшаяся выше, а также упорядочивание элементов в списке с целью минимизировать размер списка при сжатии. Достоинство этой главы, как и многих других, заключается в том, что все концепции показаны в контексте компактного, но полного решения.
Поиск. Алгоритмы из этой главы оказались для меня не новы (кроме A*), но глава все равно интересна благодаря приведенным в ней примерам. Автор демонстрирует принципы поиска в ширину и поиска в глубину на примере выхода из лабиринта. Лабиринты представляют собой обычные сетки 9 на 9 клеток каждая, в которых случайным образом расставлены преграды. На экран выводятся с использованием одних лишь символов ASCII. При помощи алгоритмов находится путь через сетку, идущий по диагонали, при этом минующий препятствия. Путь, находимый таким образом, также прочерчивается через лабиринт.
Можно с легкостью менять эти программы, чтобы проверить, как алгоритмы работают в различных сценариях. После ознакомления с поиском в ширину и в глубину автор рассказывает о A*. Вся разница заключается в том, что пути вычерчиваются с применением эвристики (евклидово расстояние), используемой в качестве ориентировочного механизма и подсказывающей, какие пути вычертить в первую очередь. В последнем примере из этой главы используется поисковая функция, при помощи которой решается задача о переправке троих миссионеров и троих людоедов на каноэ через реку. Ограничение заключается в том, что количество людоедов не может превышать количество миссионеров ни на берегу, ни в лодке, иначе людоеды съедят миссионеров. Думаю, это очень умное и интересное применение поискового алгоритма.
В других главах содержатся алгоритмы, с которыми я уже знаком.
Простые задачи (первая глава). В первой главе содержится множество небольших примеров. Сначала в ней описываются различные способы расчета чисел Фибоначчи (в частности, рекурсивный, с мемоизацией, итеративный и с генератором Python). Далее рассматриваются манипуляции с битами для сжатия и работы с XOR-шифрами. Наконец, нам в этой главе понадобится рекурсия для решения задачи о ханойских башнях.
Задачи на графы. В четвертой главе рассмотрены графовые алгоритмы для нахождения кратчайшего пути и минимального связующего дерева, а в качестве примера используется карта городов США. Также рассмотрен алгоритм Дейкстры.
Кластеризация методом K-средних. В этой главе показано, как сгруппировать точки данных в заранее определенное количество кластеров, основываясь на относительном расстоянии от каждой точки до центра кластера. Примеры в этой главе мне были не столь интересны, как примеры из других глав.
Другие задачи. В последней главе рассмотрены задача о рюкзаке, задача коммивояжера и мнемоника телефонных номеров.
Во всех программах используются принятые в Python подсказки типов. У меня к таким подсказкам двоякое отношение. С одной стороны, типы способствуют лучшему пониманию программы. Но, с другой стороны, я не привык видеть их в Python, и иногда мне приходилось сначала разбираться в этих подсказках, прежде чем я начинал понимать логику программы.
Если и хочется пожаловаться на какой-то раздел – то на тот, в котором рассказано о динамическом программировании. На мой взгляд, ему недостает полноты. Динамическое программирование – хитрая штука и, если вы собираетесь использовать его в реальных решениях, то вам потребуются дополнительные примеры на эту тему.
Основные причины, по которым эта книга мне очень понравилась – широта рассмотренных алгоритмов, полноценные (при этом компактные решения), которые легко исследовать самостоятельно, а также интересные примеры, подобранные в качестве иллюстрации алгоритмов.
- Блог компании Издательский дом «Питер»
- Python
- Программирование
- Профессиональная литература
Привет, Хабр!
Одной из самых интересных наших книг по Python в течение уходящего года оставались "Классические задачи Computer Science на языке Python" от Дэвида Копеца.
Для тех, кто еще не успел ознакомиться с этой книгой, предлагаем ее обзор, написанный по оригинальному изданию в октябре 2019 года. Также можно ознакомиться с небольшим обсуждением на Reddit. Также все желающие могут высказаться по поводу допечатки — для этого в конце статьи поставлена голосовалка.
Мне очень понравилась книга «Классические задачи Computer Science на языке Python» от Дэвида Копеца. В ней действительно рассмотрено множество разнообразных проблем, подробной информации по которым мне ранее не попадалось. Лишь некоторые примеры: нейронные сети, задачи удовлетворения ограничений, генетические алгоритмы, алгоритм минимакс. В отличие от многих других книг по алгоритмам и задачам на программирование, в этой книге показаны полноценные (но небольшие) программы, которые вы с легкостью сможете исследовать самостоятельно.
Мне нравится изучать алгоритмы. Я проработал книгу «Карьера программиста», прошел несколько MOOC-курсов, в частности, "Design and Analysis of Algorithms" от профессора Тима Рафгардена. Тем не менее, в книге Копеца нашлись и такие алгоритмы, упоминания о которых я раньше не встречал.
ГЛАВЫ, ПОНРАВИВШИЕСЯ МНЕ БОЛЬШЕ ВСЕГО
Нейронные сети. Мой любимый раздел в книге посвящен нейронным сетям. Автор описывает создание полноценной нейронной сети. Тем временем он описывает, как работают все ее части – в общем и в частностях. Рассказывает, как устроены нейроны и слои, как действует функция активации, как при обучении используется обратное распространение, как корректируются веса.
Наконец, нейронная сеть используется на примере ирисов Фишера. Это классический набор данных, собранный в 1930-е, в котором представлено 150 экземпляров цветов, относящихся к различным видам ирисов (по 50 экземпляров каждого вида). Каждый экземпляр сопровождается четырьмя числовыми значениями: длина наружной доли околоцветника; ширина наружной доли околоцветника; длина внутренней доли околоцветника; ширина внутренней доли околоцветника. Сначала значения нормализуются. Затем создается сеть с тремя слоями. Во входном слое четыре нейрона (по одному на каждую категорию значений ввода из выборки), в скрытом слое шесть нейронов, а в выходном слое три нейрона (по одному на каждый рассматриваемый вид ириса).
Случайным образом были отобраны 140 из 150 образцов, которые затем использовались для обучения сети. Обучение прогоняется по 140 образцам за 50 итераций. Затем сеть используется для прогнозирования того, к какому из трех видов ирисов относятся 10 оставшихся образцов. В большинстве случаев сеть правильно идентифицирует как минимум 8 из 10 образцов, а достаточно часто – и все 10.
Мне в самом деле понравился такой опыт: запрограммировать с нуля целую нейронную сеть, не прибегая к библиотекам машинного обучения. Я некоторое время поэкспериментировал с этой программой (весь код к книге выложен на GitHub). Например, я вывел распечатку всех весов во всех нейронах после того, как сеть была полностью обучена. Я хотел взглянуть, будет ли прослеживаться сходство между весами между разными прогонами. Оказалось, что от прогона к прогону веса поразительно отличаются, хотя, прогностическая успешность во всех случаях оставалась схожей. Может быть, это азбучная истина, но мне было очень интересно убедиться в этом самостоятельно.
Состязательный поиск. В этой главе мы знакомимся с алгоритмом минимакс. Он находит наилучший ход в игре с нулевой суммой, в которой участвуют два соперника. Идея заключается в анализе потенциальных ходов, выступая от имени то одного, то другого соперника; каждый соперник реагирует на последний из сделанных ходов, пока игра не будет завершена (либо не будет достигнута максимальная глубина рекурсии). В первом примере из книги ИИ играет в крестики-нолики. В данном случае может быть полностью проанализирована вся последовательность ходов, так как размер игрового поля составляет всего 3 на 3 клетки.
Как и в других главах, здесь сначала разрабатывается общая структура, которая затем рассматривается применительно к сложным случаям. После примера с крестиками-ноликами таким же образом разбирается игра «Четыре в ряд». В данном случае оценка ходов гораздо сложнее, чем в «Крестики-нолики», поэтому здесь поиск в глубину ограничен тремя ходами. Я много обращался к этой главе, поскольку ранее не встречал описания алгоритма минимакс.
Задачи на удовлетворение условий. Здесь также разрабатывается общая структура, которая затем используется для решения нескольких задач. В сердце этой структуры – рекурсивный поиск с возвратом. Первая проблема, решаемая в этой главе – это задача раскрашивания карты Австралии. Можно ли обойтись всего тремя цветами и раскрасить карту так, чтобы смежные территории по обе стороны любой границы между регионами отличались по цвету? (Ответ: да). Вторая задача – расставить восемь ферзей на шахматной доске, добившись, чтобы ни один ферзь не был под боем у любого другого. Третья задача – расставить список слов в виде сетки, чтобы получился квадрат для поиска слов. Наконец, структура используется для решения классической криптоарифметической загадки SEND + MORE = MONEY. Цель – выяснить, каким цифра соответствует каждая буква, чтобы получившееся арифметическое равенство было верным.
Эта глава мне понравилась, так как в ней приведено много очень разнообразных примеров, а также поскольку ранее я не пользовался таким подходом для решения подобных задач (как минимум, систематически).
Генетические алгоритмы. Прежде, чем я изучил эту главу, я лишь в самых общих чертах представлял себе, как работают генетические алгоритмы. В коде к этой главе демонстрируется класс-хромосома, который инстанцируется случайно выбранными генами. Хромосома может оценивать собственную приспособленность к среде и реализует скрещивание (комбинацию себя самой с другой хромосомой того же типа), а также мутирует (вносит сама в себя небольшие, совершенно случайные изменения).
Алгоритм начинается со случайной популяции. В каждом поколении этой популяции алгоритм проверяет (при помощи функции приспособленности), имеется ли достаточно хорошее решение (приспособленность выше заданного порогового значения). Если такого решения нет, то создается новое поколение путем многократных операций по скрещиванию пар особей (чем выше приспособленность каждой отдельной особи, тем вероятнее, что эти особи пойдут в дело). Далее несколько особей отбирается для мутаций. Теперь эти новые особи дают начало новой популяции и, опять же, проверяются их функции приспособленности. Цикл повторяется для заданного количества поколений.
В качестве примеров рассматривается решение следующих задач: максимизация математического выражения, загадка «SEND + MORE = MONEY», упоминавшаяся выше, а также упорядочивание элементов в списке с целью минимизировать размер списка при сжатии. Достоинство этой главы, как и многих других, заключается в том, что все концепции показаны в контексте компактного, но полного решения.
Поиск. Алгоритмы из этой главы оказались для меня не новы (кроме A*), но глава все равно интересна благодаря приведенным в ней примерам. Автор демонстрирует принципы поиска в ширину и поиска в глубину на примере выхода из лабиринта. Лабиринты представляют собой обычные сетки 9 на 9 клеток каждая, в которых случайным образом расставлены преграды. На экран выводятся с использованием одних лишь символов ASCII. При помощи алгоритмов находится путь через сетку, идущий по диагонали, при этом минующий препятствия. Путь, находимый таким образом, также прочерчивается через лабиринт.
Можно с легкостью менять эти программы, чтобы проверить, как алгоритмы работают в различных сценариях. После ознакомления с поиском в ширину и в глубину автор рассказывает о A*. Вся разница заключается в том, что пути вычерчиваются с применением эвристики (евклидово расстояние), используемой в качестве ориентировочного механизма и подсказывающей, какие пути вычертить в первую очередь. В последнем примере из этой главы используется поисковая функция, при помощи которой решается задача о переправке троих миссионеров и троих людоедов на каноэ через реку. Ограничение заключается в том, что количество людоедов не может превышать количество миссионеров ни на берегу, ни в лодке, иначе людоеды съедят миссионеров. Думаю, это очень умное и интересное применение поискового алгоритма.
ДРУГИЕ ГЛАВЫ
В других главах содержатся алгоритмы, с которыми я уже знаком.
Простые задачи (первая глава). В первой главе содержится множество небольших примеров. Сначала в ней описываются различные способы расчета чисел Фибоначчи (в частности, рекурсивный, с мемоизацией, итеративный и с генератором Python). Далее рассматриваются манипуляции с битами для сжатия и работы с XOR-шифрами. Наконец, нам в этой главе понадобится рекурсия для решения задачи о ханойских башнях.
Задачи на графы. В четвертой главе рассмотрены графовые алгоритмы для нахождения кратчайшего пути и минимального связующего дерева, а в качестве примера используется карта городов США. Также рассмотрен алгоритм Дейкстры.
Кластеризация методом K-средних. В этой главе показано, как сгруппировать точки данных в заранее определенное количество кластеров, основываясь на относительном расстоянии от каждой точки до центра кластера. Примеры в этой главе мне были не столь интересны, как примеры из других глав.
Другие задачи. В последней главе рассмотрены задача о рюкзаке, задача коммивояжера и мнемоника телефонных номеров.
К ЧЕМУ БЫ ПРИЦЕПИТЬСЯ
Во всех программах используются принятые в Python подсказки типов. У меня к таким подсказкам двоякое отношение. С одной стороны, типы способствуют лучшему пониманию программы. Но, с другой стороны, я не привык видеть их в Python, и иногда мне приходилось сначала разбираться в этих подсказках, прежде чем я начинал понимать логику программы.
Если и хочется пожаловаться на какой-то раздел – то на тот, в котором рассказано о динамическом программировании. На мой взгляд, ему недостает полноты. Динамическое программирование – хитрая штука и, если вы собираетесь использовать его в реальных решениях, то вам потребуются дополнительные примеры на эту тему.
ВЫВОД
Основные причины, по которым эта книга мне очень понравилась – широта рассмотренных алгоритмов, полноценные (при этом компактные решения), которые легко исследовать самостоятельно, а также интересные примеры, подобранные в качестве иллюстрации алгоритмов.