Erhalten Sie Zugang zu diesem und mehr als 300000 Büchern ab EUR 5,99 monatlich.
- Herausgeber: Питер
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Russisch
Алгоритмы это не только задачи поиска, сортировки или оптимизации, они помогут вам поймать бейсбольный мяч, проникнуть в «механику» машинного обучения и искусственного интеллекта и выйти за границы возможного. Вы узнаете нюансы реализации многих самых популярных алгоритмов современности, познакомитесь с их реализацией на Python 3, а также научитесь измерять и оптимизировать их производительность.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 324
Veröffentlichungsjahr: 2023
Das E-Book (TTS) können Sie hören im Abo „Legimi Premium” in Legimi-Apps auf:
Ähnliche
Переводчик Е. Матвеев
Брэдфорд Такфилд
Алгоритмы неформально. Инструкция для начинающих питонистов. — СПб.: Питер, 2022.
ISBN 978-5-4461-1919-6
© ООО Издательство "Питер", 2022
Все права защищены. Никакая часть данной книги не может быть воспроизведена в какой бы то ни было форме без письменного разрешения владельцев авторских прав.
Оглавление
Посвящается моим родителям Дэвиду и Бекки Такфилд, которые когда-то поверили в меня и научили играть в «Точки и квадраты»
Об авторе
Брэдфорд Такфилд (Bradford Tuckfield) — специалист по теории данных и писатель. Руководит фирмой Kmbara (https://kmbara.com/), занимающейся консультациями в области теории данных, а также ведет литературный сайт Dreamtigers (http://thedreamtigers.com/).
О научном редакторе
Алок Малик (Alok Malik) — специалист по теории данных из Нью-Дели (Индия). Занимается созданием моделей глубокого обучения в областях обработки естественного языка и распознавания изображений на Python. Малик разрабатывал такие решения, как языковые модели, классификаторы изображений и текста, системы перевода, модели преобразования речи в текст, системы распознавания именованных сущностей и детекторы объектов. Кроме того, он участвовал в написании книги о машинном обучении. В свободное время любит читать о финансах, преподает на курсах дистанционного обучения и играет на приставке.
Благодарности
«Одно и то же слово по-разному звучит у разных писателей. Один выдирает его из своего нутра. Другой вынимает его из кармана пальто». Так Шарль Пеги (Charles Peguy) сказал о написании отдельных слов. То же относится к главам и целым книгам. В одних случаях мне казалось, что я вынимал эту книгу из кармана пальто. В других все выглядело так, словно я выдирал ее из своего нутра. Будет уместно поблагодарить всех, кто внес свой вклад в этот долгий процесс — либо одалживая мне пальто, либо помогая мне залечить нутро.
Многие хорошие люди помогали мне на долгом пути, который я прошел, чтобы получить опыт и квалификацию, необходимые для написания книги. Мои родители Дэвид и Бекки Такфилд преподнесли мне множество бесценных даров, начиная с жизни и образования, и продолжали верить и вдохновлять меня, а также помогать мне в других отношениях — слишком многочисленных, чтобы я мог их здесь перечислить. Скотт Робертсон (Scott Robertson) дал мне первую работу по написанию кода, хотя моей квалификации было явно недостаточно. Рэнди Дженсон (Randy Jenson) принял меня на первую работу, связанную с теорией данных, — и снова несмотря на мою неопытность и ограниченный опыт. Кумар Кашьяп (Kumar Kashyap) предоставил мне первую возможность руководить группой разработки для реализации алгоритмов. Дэвид Зу (David Zou) стал первым человеком, заплатившим мне за написание статьи (десять долларов за вычетом процента PayPal за десять коротких обзоров фильмов), и это было настолько прекрасно, что я решил более плотно заняться писательской работой. Адитья Дейт (Aditya Date) был первым, кто предложил мне написать книгу и предоставил первую возможность для этого.
Меня также вдохновляли многие учителя и наставники. Дэвид Кардон (David Cardon) предоставил первую возможность участвовать в академических исследованиях и многому научил в процессе работы. Брайан Скелтон (Bryan Skelton) и Леонард Ву (Leonard Woo) стали для меня примерами тех, на кого я бы хотел быть похожим, когда вырасту. Уэс Хатчинсон (Wes Hutchinson) научил важнейшим алгоритмам (таким как кластеризация методом k-средних) и помог лучше понять их работу. Чед Эммет (Chad Emmett) научил думать об истории и культуре, я посвятил ему главу 2. Ури Саймонсон (Uri Simonsohn) показал, как следует подходить к анализу данных.
Некоторые люди помогли мне превратить написание книги в приятное занятие. Сешу Эдала (Seshu Edala) помог отрегулировать мой рабочий график, чтобы высвободить время для работы над книгой, и постоянно подбадривал меня. С Алексом Фридом (Alex Freed) было очень приятно работать на протяжении всего процесса редактирования. Дженнифер Игар (Jennifer Eagar) неофициально стала первым человеком, купившим экземпляр книги за несколько месяцев до ее выхода; это помогало мне в трудные времена. Хланг Хланг Тун (Hlaing Hlaing Tun) была всегда готова поддержать и помочь, оставалась милой и доброжелательной на каждом этапе.
Я не могу вернуть весь долг благодарности, но, по крайней мере, могу сказать спасибо всем, кто мне помогал. Спасибо!
Введение
Алгоритмы встречаются повсюду. Вероятно, вы уже выполнили сегодня как минимум несколько алгоритмов. В книге вы прочтете о десятках алгоритмов: простых и сложных, знаменитых и малоизвестных — но все они интересны и заслуживают вашего внимания. Первый алгоритм в книге также оказывается самым вкусным — он описывает процесс приготовления парфе с гранолой и ягодами; данный алгоритм полностью приведен на рис. 1. Возможно, вы привыкли называть алгоритмы такого типа «рецептами», но он соответствует определению алгоритма у Дональда Кнута: конечный набор правил, определяющий последовательность операций для решения конкретного типа задач.
Парфе с гранолой и ягодами
Указания
1. Добавьте 1/6 чашки голубики в креманку.
2. Выложите половину чашки турецкого йогурта на голубику.
3. Выложите 1/3 чашки гранолы на йогурт.
4. Выложите половину чашки турецкого йогурта на гранолу.
5. Положите клубнику на содержимое креманки.
6. Украсьте взбитыми сливками.
Рис. 1. Алгоритм: конечный набор правил, определяющий последовательность операций для решения конкретного типа задач
Приготовление десертов — не единственная область жизни, управляемая алгоритмами. Ежегодно правительство США требует, чтобы каждый взрослый гражданин выполнял определенный алгоритм, и старается посадить в тюрьму тех, кто делает это неправильно. В 2017 году миллионы американцев выполнили свой долг, завершив алгоритм, показанный на рис. 2, который был взят из формы 1040-EZ.
Рис. 2. Инструкции по заполнению налоговой декларации соответствуют определению алгоритма
Что общего у налогов и ягодного десерта? Налоги нужно обязательно платить, они выражаются в числовом виде, рассчитываются по сложным формулам, и люди их обычно терпеть не могут. Десерты встречаются не так часто, являются произведением искусства, и их все обожают. Единственное, что у них есть общего, — при подготовке и того и другого используются алгоритмы.
Великий ученый в области вычислительной теории Дональд Кнут замечал, что термин «алгоритмы» почти синонимичен терминам «рецепт»,«процедура» и «рутина». При декларировании налогов с использованием формы 1040-EZ выполняются 12 шагов (конечный список), определяющих операции (такие как сложение на шаге 4 и вычитание на шаге 6) для решения конкретной задачи: стремления избежать тюремного заключения за уклонение от уплаты налогов. Для приготовления парфе нужны шесть шагов, определяющих операции (такие как добавление ягод на шаге 1 и выкладывание йогурта на шаге 2) для решения конкретной задачи: желания отведать десерт.
Когда вы больше узнаете об алгоритмах, вы начнете видеть их повсеместно и оцените, насколько впечатляющими они могут быть. В главе 1 мы обсудим выдающуюся человеческую способность ловить мяч и ознакомимся с подробностями алгоритма из области подсознания, который позволяет нам это делать. Позднее рассмотрим алгоритмы отладки кода, максимизации доходов, сортировки списков, планирования задач, правки текста, доставки почты и победы в таких играх, как шахматы или судоку. Попутно вы научитесь оценивать алгоритмы по нескольким атрибутам, которые, по мнению профессионалов, важны для алгоритмов. Со временем вы сможете в совершенстве овладеть искусством создания алгоритмов, которое открывает перспективу для творческого подхода и проявления личных качеств в точной и формальной области.
Для кого написана эта книга
В книге доступным языком описываются различные алгоритмы, при этом они сопровождаются кодом на Python. Чтобы извлечь из нее максимум пользы, вам понадобится некоторый опыт в областях, перечисленных ниже.
• Программирование. Все значимые примеры в книге поясняются с помощью кода Python. Я постарался предоставить подробный анализ и объяснения для каждого фрагмента кода, чтобы книга была понятной для читателя, не имеющего опыта программирования на Python и значительного опыта программирования вообще. Тем не менее читатель, обладающий хотя бы базовым пониманием основных концепций программирования — присваивания значений переменным, циклов for, команд if/then и вызовов функций, — будет лучше подготовлен к усвоению материала.
• Школьный курс математики. Алгоритмы часто используются для достижения тех же целей, для которых служат и математические конструкции: решение уравнений, оптимизация и вычисление значений. В алгоритмах также применяются многие принципы, связанные с математическим мышлением, например необходимость использования точных определений. Иногда в своих рассуждениях мы заходим на математическую территорию, включая алгебру, теорему Пифагора, число пи и основы математического анализа. Я постарался избежать хитроумных рассуждений и ограничиться рамками школьного курса математики.
Каждый, кто уверенно чувствует себя в указанных областях, сможет легко усвоить весь материал книги. Она была написана для нескольких групп читателей.
• Учащиеся. Книга подходит для изучения вводного курса алгоритмов, информатики или программирования уровня средней или высшей школы.
• Профессионалы. Практикующие специалисты тоже смогут узнать много полезного из книги. Это и программисты, желающие освоить Python, и разработчики, которые хотят расширить свои знания в области основ информатики и улучшить код за счет алгоритмического мышления.
• Энтузиасты-любители. Они составляют настоящую целевую аудиторию книги. Алгоритмы затрагивают практически каждую часть нашей жизни, поэтому каждый читатель сможет найти в издании что-то интересное, расширяющее границы восприятия окружающего мира.
О книге
В книге не рассматриваются все аспекты всех известных алгоритмов; это лишь вводный курс. Прочитав ее, вы будете четко понимать, что такое алгоритм, как писать код для реализации важных алгоритмов, и оценивать и оптимизировать эффективность алгоритмов. Вы также познакомитесь со многими популярными алгоритмами, которыми пользуются профессионалы. Ниже представлена структура издания.
• В главе 1 «Алгоритмы при решении задач» мы обсудим, как ловим мяч, поищем доказательства существования подсознательного алгоритма, управляющего человеческим поведением, и выясним, как это может нам помочь в практической реализации алгоритмов и их разработке.
• В главе 2 «Алгоритмы в истории» мы совершим путешествие по миру и во времени, чтобы узнать, как древние египтяне и русские крестьяне умножали числа, древние греки находили наибольшие общие делители, а средневековые японские ученые строили магические квадраты.
• В главе 3 «Максимизация и минимизация» представлены методы градиентного подъема и градиентного спуска. Эти простые методы поиска максимумов и минимумов функций используются для оптимизации — важной цели многих алгоритмов.
• В главе 4 «Сортировка и поиск» представлены фундаментальные алгоритмы сортировки списков и поиска в них элементов. Вы также узнаете, как оценивать эффективность и скорость работы алгоритмов.
• В главе 5 «Чистая математика» мы займемся чисто математическими алгоритмами, включая алгоритмы построения непрерывных дробей, вычисления квадратных корней и генерирования псевдослучайных чисел.
• В главе 6 «Расширенная оптимизация» рассматривается нетривиальный метод поиска оптимальных решений: имитация отжига. Кроме того, в ней представлена задача о коммивояжере — одна из стандартных задач современной информатики.
• В главе 7 «Геометрия» рассматривается генерирование диаграмм Вороного, которые находят применение во многих геометрических областях.
• В главе 8 «Язык» речь пойдет об осмысленной расстановке отсутствующих пробелов в тексте и формировании рекомендаций по выбору следующего слова во фразах.
• В главе 9 «Машинное обучение» рассматриваются деревья принятия решений — один из фундаментальных методов машинного обучения.
• В главе 10 «Искусственный интеллект» мы займемся амбициозным проектом: реализацией алгоритма, который может играть против нас и, возможно, выигрывать. Мы начнем с простой игры «Точки и квадраты» и поговорим о том, как можно улучшить быстродействие программы для этой игры.
• В главе 11 «Полный вперед» речь пойдет о том, как перейти к продвинутым задачам, связанным с алгоритмами. Вы узнаете, как построить чат-бот и выиграть миллион долларов, построив алгоритм для головоломки судоку.
Настройка окружения
Алгоритмы, описанные в книге, реализуются на Python. Он распространяется бесплатно, является языком с открытым исходным кодом и работает на всех основных платформах. Ниже описана процедура установки Python для систем Windows, macOS и Linux.
Установка Python в системе Windows
Чтобы установить Python в системе Windows, выполните следующие действия.
1. Откройте страницу с новейшей версией Python для Windows (не забудьте включить завершающую косую черту): https://www.python.org/downloads/windows/.
2. Щелкните на ссылке версии Python, которую хотите скачать. Чтобы скачать новейшую версию, щелкните на ссылке Latest Python 3 Release — 3.X.Y, где 3.X.Y — номер последней версии (например, 3.8.3). Код, приведенный в книге, был протестирован как на Python 3.6, так и на Python 3.8. Если вы захотите скачать более старую версию, то прокрутите страницу до раздела Stable Releases и найдите нужную версию.
3. Ссылка, на которой вы щелкнули на шаге 2, открывает страницу выбранного вами выпуска Python. В разделе Files щелкните на ссылке Windows x86-64 executable installer.
4. Ссылка из шага 3 открывает файл .exe на вашем компьютере. Это установочный файл; щелкните на нем дважды, чтобы открыть. Файл автоматически запускает процесс установки. Установите флажок Add Python 3.X to PATH, где X — номер версии для загруженной установочной программы (например, 8). Затем нажмите кнопку Install Now и выберите настройки по умолчанию.
5. Когда появится сообщение Setup was successful, нажмите кнопку Close, чтобы завершить процесс установки.
На вашем компьютере появилось новое приложение Python 3.X, где X — номер установленной версии Python 3. В поле поиска Windows введите Python. Когда приложение появится на экране, щелкните на нем, чтобы открыть консоль Python. Вводите на консоли команды Python, и они будут выполнены.
Установка Python в macOS
Чтобы установить Python в системе macOS, выполните следующие действия.
1. Откройте страницу с новейшей версией Python для macOS (не забудьте включить завершающую косую черту): https://www.python.org/downloads/mac-osx/.
2. Щелкните на ссылке версии Python, которую хотите скачать. Чтобы скачать новейшую версию, щелкните на ссылке Latest Python 3 Release — 3.X.Y, где 3.X.Y — номер последней версии (например, 3.8.3). Код, приведенный в книге, был протестирован как на Python 3.6, так и на Python 3.8. Если захотите скачать более старую версию, то прокрутите страницу до раздела Stable Releases и найдите нужную версию.
3. Ссылка, на которой вы щелкнули на шаге 2, открывает страницу выбранного вами выпуска Python. В разделе Files щелкните на ссылке macOS 64-bit installer.
4. Ссылка из шага 3 открывает файл .pkg на вашем компьютере. Это установочный файл; дважды щелкните на нем, чтобы открыть. Файл автоматически запускает процесс установки. Выберите настройки по умолчанию.
5. На вашем компьютере создается папка Python 3.X, где X — номер установленной версии Python. В этой папке дважды щелкните на значке IDLE. На экране появляется приложение 3.X.Y Shell, где 3.X.Y — номер новейшей версии. Это консоль Python, из которой можно выполнять любые команды Python.
Установка Python в системе Linux
Чтобы установить Python в системе Linux, выполните следующие действия.
1. Определите, какой менеджер пакетов используется вашей версией Linux. Два типичных варианта — yum и apt-get.
2. Откройте консоль Linux (также называемую терминалом) и выполните следующие две команды:
> sudo apt-get update
> sudo apt-get install python3.8
Если вы используете yum или другой менеджер пакетов, то замените оба упоминания apt-get в этих двух строках именем yum или именем вашего менеджера пакетов. Аналогичным образом, если вы захотите установить более старую версию Python, замените 3.8 (номер последней версии на момент написания книги) другим номером версии (например, 3.6 — одной из версий, которые использовались при тестировании кода книги). Чтобы узнать номер новейшей версии Python, перейдите по адресу https://www.python.org/downloads/source/. Здесь вы найдете ссылку Latest Python 3 Release — 3.X.Y, где 3.X.Y — номер версии; используйте первые две цифры в приведенной выше команде установки.
3. Запустите Python, выполнив следующую команду с консоли Linux:
python3
Консоль Python открывается в консольном окне Linux. Здесь вы можете вводить команды Python.
Установка сторонних модулей
Часть кода, представленного в книге, зависит от модулей Python, которые не входят в базовое программное обеспечение Python, загруженное с официального сайта Python. Чтобы установить сторонние модули на компьютере, выполните инструкции, изложенные на http://automatetheboringstuff.com/2e/appendixa/.
Резюме
В ходе знакомства с алгоритмами мы посетим много разных мест и окунемся в различные исторические эпохи. Вы познакомитесь с открытиями, сделанными в Древнем Египте, Вавилоне, Афинах времен Перикла, Багдаде, средневековой Европе, Японии периода Эдо и Британской Индии, а также с выдающимися достижениями современности и ее ошеломляющими технологиями. Нам придется искать новые решения задач и преодолевать ограничения, которые на первый взгляд кажутся непреодолимыми. При этом мы установим связь не только первопроходцев древней науки, но и всех, кто пользуется компьютером или ловит бейсбольные мячи, с поколениями пользователей алгоритмов, а также их создателей, которые еще не родились, но в отдаленном будущем будут развивать оставленное нами наследие. Эта книга поможет вам сделать первые шаги в мир алгоритмов.
От издательства
Ваши замечания, предложения, вопросы отправляйте по адресу [email protected] (издательство «Питер», компьютерная редакция).
Мы будем рады узнать ваше мнение!
На веб-сайте издательства www.piter.com вы найдете подробную информацию о наших книгах.
2. Алгоритмы в истории
Алгоритмы часто ассоциируются с компьютерами. И в этом есть резон; компьютерные операционные системы могут использовать множество алгоритмов высокой сложности, и программирование хорошо подходит для точной реализации всех видов алгоритмов. Однако алгоритмы имеют более фундаментальную природу, чем компьютерная архитектура, на которой они реализуются. Как упоминалось в главе 1, слово «алгоритм» появилось более тысячи лет назад, однако алгоритмы описывались в древних рукописях еще задолго до этого. Даже вне памятников письменности существуют многочисленные данные, свидетельствующие о применении сложных алгоритмов в Древнем мире — например, технологии строительства.
В этой главе представлены несколько алгоритмов древнего происхождения. В них проявляется выдающаяся изобретательность и оригинальность мышления, особенно если учесть, что они создавались и проверялись без помощи компьютеров. Начнем с обсуждения русского крестьянского умножения — метода арифметических вычислений, который, несмотря на свое название, может происходить из Египта и не иметь никакого отношения к крестьянам. Затем рассмотрим алгоритм Евклида — важный «классический» алгоритм для нахождения наибольшего общего делителя. Напоследок рассмотрим изобретенный в Японии алгоритм для построения волшебных квадратов.
