chapter-01.tex

\chapter{Введение}
\label{chap:intro}

\epigraph{
1. Запишите задачу на бумаге.\\
2. Подумайте действительно хорошенько.\\
3. Запишите решение задачи.
}{<<Алгоритм Фейнмана>>, по Мюррею Гелл-Манну.}


Представьте себе такую задачу. Вам нужно посетить все города, городки и поселки, например, Швеции и вернуться в исходную точку. Это может занять немало времени (ведь нужно заглянуть в 27 978 мест), так что вам хочется сделать маршрут покороче. Вы собираетесь заехать в каждое место только один раз следуя кратчайшим путем. Будучи программистом Вы точно не собираетесь рисовать маршрут вручную. Вместо этого вы попробуете написать программу, которая все рассчитает сама. Однако, по какой-то причине вам это никак не удается. Очевидное решение неплохо работает на небольшом количестве городов, но на реальной задаче расчет никак не завершается, а улучшить программу оказывается неожиданно сложно. Как быть?

Между тем, в 2004-ом году команда из 5 исследователей\footnote{David Applegate, Robert Bixby, Vašek Chvátal, William Cook и Keld Helsgaun} нашла такой путь по Швеции, после того как несколько подобных проектов завершились неудачей. Эта команда использовала самое новое ПО с кучей хитрых оптимизаций, запущенное на кластере из 96 машин на Xeon 2.6ГГц. Их программа проработала с марта 2003-го до мая 2004-го, прежде чем было получено оптимальное решение. Ребята посчитали, что с учетом разных перерывов общее процессорное время, потраченное на решение задачи, оказалось равным \textit{85 годам}!

Представьте теперь похожую задачу: из Кашгара, на самого западе Китая, вам нужно попасть в Нинбо, на восточное побережье, следуя кратчайшем путем. В Китае 3 583 715 км автомобильных и 77 384 км железных дорог, которые пересекаются в миллионах мест и образуют неисчислимое количество возможных маршрутов. Может показаться, что эта проблема аналогична предыдущей, но уже сейчас такая задача \textit{поиска кратчайшего пути} решается без каких-либо затруднений и задержек GPS-навигаторами и онлайн-картами. Если вы отметите два названных города на любимом картографическом сервисе, то получите кратчайший маршрут за пару мгновений. В чем тут дело?

Дальше в книге вы узнаете больше о двух этих задачах. Первая называется \textit {проблемой коммивояжера} и описана в главе \ref{chap:hard-problems}, а так называемая проблема поиска кратчайшего пути рассматривается в главе \ref{chap:from-a-to-b}. Я надеюсь, что вы начнете хорошо понимать, почему одни задачи так сложны для решения, в то время как другие имеют несколько известных и эффективных решений. Что еще важнее, вы научитесь работать с любыми вычислительными и алгоритмическими задачами, либо эффективно решая их, используя описанные в книге техники и алгоритмы, либо показывая, что они слишком сложны, и приближенное решение "--- это лучшее, на что можно рассчитывать. Эта глава вкратце описывает всю книгу: что вы можете от нее получить и что требуется от вас. В ней также обозначены темы остальных глав, чтобы вы могли читать их выборочно.

\section{Так о чем же тут речь?}

Эта книга "--- о решении алгоритмических задач для программистов на Python. Так же как например в книгах о паттернах в ООП, здесь описываются обобщенные задачи и обобщенные же решения. Вам как алгоритмисту в большинстве случаев будет нужно не только реализовать или выполнить существующий алгоритм, как было бы к примеру в математической задаче. Нет, от вас ждут разработки новых алгоритмов, новых \textit{обобщенных решений} для доселе не встреченных, обобщенных задач. В этой книге вы познакомитесь с принципами создания таких решений.

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

Есть еще одна разновидность книг об алгоритмах: <<Структуры данных и алгоритмы в (пробел)>>, где вместо пробела подставлено название любимого языка программирования автора. Таких книг немало (особенно если вместо пробела стоит Java), но многие из них сосредотачиваются на относительно простых структурах данных, в ущерб более серьезному материалу. Это можно понять, если книга рассчитана на начальное обучение структурам данных, но для программиста на Python изучение одно- и двухсвязных списков может и не оказаться таким уж увлекательным (хотя вы \textit{обязательно} встретите упоминание о них в следующей главе). Да, и несмотря на то, что очень важно владеть такими техниками как, например, хэширование, у вас уже есть хэш-таблицы в виде словарей в Python "--- нет необходимости реализовывать их самостоятельно. Вместо всего этого я обращу внимание на более высокоуровневые алгоритмы. Множество важных концепций, доступных как <<черные ящики>> в самом Python или в его стандартной библиотеке (к примеру сортировка, поиск и хэширование), объясняются коротко в специальных блоках по ходу текста.

И есть конечно же еще один факт, который отличает эту книгу от всех этих <<Алгоритмов в Java/C/C++/C\#>>: в ее названии есть Python. Это делает ее на шаг ближе к независимым от языка книгам (таким как Кнут, Кормен или Клейнберг и Тардос), которые часто используют \textit{псевдокод}, что-то вроде выдуманного языка программирования, разработанного для чтения программ, а не для их исполнения. А одна из ключевых особенностей Python "--- это читабельность программ на нем, их можно назвать исполняемым псевдокодом. Даже если вы никогда не писали на Python, то скорее всего сможете разобраться в большинстве программ. Код в этой книге был написан именно с такой мыслью "--- вам не нужно быть экспертом по Python, чтобы понять примеры (хотя и может потребоваться взглянуть на описание некоторых встроенных функций). Так что если вы хотели бы примеры в псевдокоде, можете просто считать их таковыми. И в завершение...

\paragraph{О чем эта книга:}
\begin{itemize}
\item Об анализе алгоритмов, особенно их асимптотическом времени исполнения;
\item Об основных принципах проектирования алгоритмов;
\item О том, как представить привычные структуры данных в Python;
\item О том, как реализовать широко известные алгоритмы на Python.
\end{itemize}

\paragraph{Что описано коротко или лишь частично:}
\begin{itemize}
\item Алгоритмы, которые доступны в Python как часть самого языка или его стандартной библиотеки;
\item Строгая формальная база (хотя в книге и есть известная доля доказательств и объяснений).
\end{itemize}

\paragraph{Чего нет в этой книге:}
\begin{itemize}
\item Численных и численно-теоретических алгоритмов (кроме нескольких советов по работе с числами с плавающей запятой в главе \ref{chap:basics});
\item Параллельных алгоритмов и многопроцессорного программирования.
\end{itemize}

Как вы видите, <<реализация разных вещей на Python>> "--- это лишь часть общей картины. Принципы проектирования и теоретические основания описаны в книге в надежде, что они позволят вам разрабатывать \textit{собственные} алгоритмы и структуры данных.


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "mapl"
%%% End: