Перед вами хендбук по алгоритмам от авторов, увлеченных красотой и элегантностью математики.
В этой книге мы сделаем акцент на фундаменте построения алгоритмов и преобразовании их в программы. Это важно — практически на любую задачу можно посмотреть с различных сторон, и это может привести к необычайным результатам: где-то подход станет намного проще и понятнее, а где-то значительно вырастет эффективность, и итоговая программа будет находить результат в тысячи и даже в миллионы раз быстрее.
Зачем изучать алгоритмы? Этот вопрос интересует большинство начинающих разработчиков. На него нет однозначно верного ответа, но мы считаем изучение алгоритмов важным и полезным.
Алгоритмизация превращает мысли и рассуждения в последовательность действий. Но к одному и тому же результату могут приводить разные действия — поэтому составление алгоритма это ещё и поиск наиболее эффективного (в данный момент) набора действий.
Зная фундаментальные алгоритмы, вы сможете виртуозно использовать стандартные библиотеки языков программирования, уверенно оценивать ожидаемое время работы программы, читать и понимать код, написанный другими программистами.
Алгоритмизация важна и «для общего развития»: она помогает планировать свои действия в реальной жизни. Почти всё, что нас окружает, можно описать алгоритмически. Взять, например, очередь.
Здесь алгоритмы помогают по-разному организовать работу с клиентами — в зависимости от разных факторов: количества посетителей, количества сотрудников и так далее. Организация очереди в аэропорту и в супермаркете отличается:
- в супермаркете клиенты оплачивают покупки по одному;
- в аэропорту подходят к стойке в общей очереди, но «обработчики» забирают клиентов по одному, как только заканчивают работу с предыдущим.
И там, и тут — очередь, организованная по принципу «первый пришёл — первый вышел» (First In First Out, FIFO), но за счёт различий в реализации в каждом случае удаётся получить оптимальное время на обслуживание клиентов.
Очередь — важный примитив из простых абстрактных структур данных, более детально о ней поговорим в одном из параграфов.
В основе нашего хендбука — перевод интерактивного учебника Ace Your Next Coding Interview by Learning Algorithms through Programming and Puzzle Solving (Alexander S. Kulikov, Pavel Pevzner), дополненный новыми практическими задачами и несколькими тематическими разделами.
Мы уверены, что по-настоящему разобраться в новом материале помогает глубокая практическая проработка — для закрепления новых знаний необходимо попробовать решить задачу и посмотреть на неё под разными углами, задать себе вопросы о возможном применении того или иного подхода, или способах его обобщить.
Обязательно решайте практические задачи, закрепляйте свои знания.
Проверка решений практических заданий проводится автоматически в системе Яндекс Контест. Мы подготовили наборы тестовых примеров, которые покрывают различные возможные ошибки в программной реализации алгоритмов. Если для какой-то из задач вы обнаружите, что решение проходит системные тесты, но при этом не является корректным, присылайте ваши дополнительные тесты, обязательно добавим их в задачу, чтобы улучшить ее качество.
И последнее, на чём хочется заострить внимание: в этой книге мы будем больше фокусироваться на проектировании подходов и создании эффективных алгоритмов — где-то не будем совсем строго доказывать корректность алгоритмов, а где-то только выпишем итоговую трудоемкость, но опять же не будем её строго обосновывать. Корректность и анализ трудоемкости (в худшем случае и в среднем) — очень важные части составления алгоритмов, но всему свое время, давайте погружаться постепенно.
Желаем вам удовольствия от познания нового, а ещё — успешного применения алгоритмических подходов в жизни, при трудоустройстве и в решении практических задач. Надеемся, что вы будете так же радоваться придуманным подходам, как радуемся мы.
И ещё кое-что: для этого хендбука у нас есть коммьюнити студентов. В нём можно найти единомышленников, обсудить материалы и задания. Вступить в него можно по ссылке. А чтобы быть в курсе обновлений хендбука — советуем подписаться на рассылку.