Алгоритмы неформально. Инструкция для начинающих питонистов - [2]

Парфе с гранолой и ягодами

Указания

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, и разработчики, которые хотят расширить свои знания в области основ информатики и улучшить код за счет алгоритмического мышления.

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

О книге

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