Прочитав название книги Владстона Ф. Фило, многие из вас, наверное, скажут: «Ну вот, ещё одна книга для чайников. Опять нам будут рассказывать о том, что такое двоичная система исчисления и какие бывают циклы». Отчасти вы будете правы: в книге рассказывается о простых и базовых понятиях и принципах, которые должен знать каждый программист. Только вот «теоретический минимум», изложенный в книге, включает в себя множество интересных и полезных вещей, о которых мало пишут в подобной литературе начального уровня. Задайте себе вопрос: действительно ли вы так хорошо знаете основы того, что называется Computer Science?

А вы в этом уверены?

Давайте проведём небольшой эксперимент. Попробуйте ответить на следующие вопросы:

• Сколько вы знаете методов сортировки массива, кроме метода «пузырька»?

• Почему двоичное дерево поиска должно быть хорошо сбалансировано?

• Зачем в процессоре выделяют кэш уровня L1, L2 и L3?

• Чем декларативное программирование отличается от логического и императивного?

• Почему алгоритмы с экспоненциальной временно́й сложностью на большом объёме данных считаются невыполнимыми?

• Какие задачи относятся к классу NP-полных?

• Как хранятся связный и двусвязный списки в памяти компьютера?

• Что такое каррированная функция?

Если вы не смогли уверенно ответить на бо́льшую часть этих вопросов, но сами вопросы показались вам интересными, то вам стоит прочитать эту книгу. Хотя бы для общего развития.

В оригинале книга называется «Computer Science Distilled: Learn the Art of Solving Computational Problems».

Общие впечатления

В каждом разделе книги изложение ведётся от простого к сложному. Есть в книге и совсем базовые знания. Например, в ней действительно описываются двоичная система, булева алгебра и блок-схемы. Но автор делает это кратко, чтобы затем перейти к изложению более интересных вещей. Вообще, в книге почти нет ничего лишнего — вся информация изложена сжато, но вполне доступно. Несущественные и очевидные промежуточные шаги часто пропущены. Благодаря этому описание алгоритмов и правил читается легко. Как говорил Гомер Симпсон, «Мне некогда читать, передай смысл». Это как раз то, чего не хватает многим учебникам начального уровня, которые переполнены лишней и ненужной информацией.

Иллюстрации в этой книге сделаны качественно и профессионально. Автор не поленился составить графические примеры к большинству сложных алгоритмов. Рисунки очень помогают в изучении материала. Например, после изложения принципов выполнения логических операций приведена принципиальная схема суммирования двухразрядных чисел. По схеме можно самостоятельно проследить, как выполняется суммирование с помощью простейших элементов AND и XOR. Ещё в книге есть несколько подходящих к случаю комиксов с таких сайтов, как xkcd.com и geek-and-poke.com.

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

В конце каждой главы приведены ссылки на полезные материалы. Все они оформлены как разделы на сайте code.energy. Вот пример (PDF). В некоторых случаях они ведут на страницу с соответствующей книгой в магазине Amazon. Но есть и такие, которые открывают страницы или PDF-файлы. Последние, конечно, полезнее, чем ссылки на книгу в магазине.

Просто, как бином

В первой главе книги излагаются самые основы: блок-схемы, булева алгебра, базовые формулы комбинаторики и теории вероятности. Это именно то, чему студентов технических специальностей учат на предметах «Информатика» и «Дискретная математика». Если вы знаете, что A XOR B тождественно !(А↔B) и как вычислить вероятность наступления совместных, несовместных и взаимодополняющих событий, то можете смело пропускать эту главу. Кстати, на каждое правило в главе приведены довольно интересные примеры.

Надейтесь на лучшее, но готовьтесь к худшему

Во второй главе книги автор рассказывает о понятии вычислительной сложности алгоритмов. В ней приведена методика расчёта временно́й сложности алгоритма — так называемого «О большого» — по числу требуемых операций и количеству входных данных. Наглядно показано, как различаются алгоритмы с единичной, линейной, логарифмической, квадратичной и экспоненциальной сложностью. Рассказано, почему первые — самые лучшие, а вторые последние — самые худшие алгоритмы. Ну и про пространственную сложность алгоритмов тоже упомянуто — память у современных компьютеров большая, но всё же конечная. В этой главе книги как раз говорится о том, что такое сложность алгоритма и как её вычислить.

Сначала стратегия, потом тактика

Третья глава называется «Стратегия». В ней очень доходчиво объясняется, что такое итерация и рекурсия и в каких случаях их лучше всего использовать. Автор рассказывает о том, как лучше организовать проверку всех подходящих решений задачи — от грубого полного перебора до поиска с возвратом и эвристических алгоритмов, а также объясняет, как использовать разделение множеств для оптимизации сортировки значений и решения других задач. Также здесь немного рассказано о динамическом программировании и методе ветвей и границ. В целом эта глава о том, как выбрать оптимальный метод для решения поставленной задачи.

Балансируем деревья

Четвёртая глава книги посвящена структурам и абстрактным типам хранения данных. Я просто перечислю те структуры и типы, о которых в ней говорится: стек, очередь, очередь с приоритетом, список, сортированный список, множество, массив, связный список, двусвязный список, дерево, двоичное дерево, двоичная куча, граф, хеш-таблица. Никаких сюрпризов в этой главе нет, автор последовательно и обстоятельно рассказывает о каждом типе и каждой структуре.

Опять пресловутая задача о коммивояжёре

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

SQL vs NoSQL

Шестую главу большинство читателей может лишь бегло пролистать. Ну кто из программистов не знает о реляционных и нереляционных базах данных, SQL, индексах, транзакциях и распределённых моделях? Тем же, кто только начинает свой путь в области разработки будет полезно прочитать эту главу, чтобы систематизировать базовые знания и ничего не упустить.

Почему памяти полно, а программа всё равно «тормозит»

Седьмая глава называется просто и незамысловато: «Компьютеры». В ней рассказывается о том, что такое ЦП и ОЗУ и как они обмениваются командами и данными. А ещё про ассемблер, операционные системы и компиляторы. Упоминание команд одного из первых процессоров удивительным образом перекликается с разделом «Программное обеспечение с открытым исходным кодом». Сразу вспоминается рассказ Линуса Торвальдса о том, как всё начиналось, в книге «Just for fun».

Дальше рассказывается о такой полезной вещи, как иерархия памяти. Если вы не смогли ответить на вопрос про кэш уровня L1, L2 и L3, то вам стоит почитать эту часть книги.

Есть не только императивное программирование

Наконец, в восьмой главе содержится то, ради чего всё затевалось — рассказ о программировании. Глава разделена на два подраздела: «Лингвистика» и «Парадигмы программирования». В первом излагаются совсем базовые вещи. Например, что такое переменная. А второй подраздел можно читать, как отдельную статью-обзор современных парадигм разработки. К примеру, если вы адепт императивного программирования и не знаете, что такое карринг и замыкание, вам будет интересно познакомиться с декларативным программированием. Кстати, есть ещё логическая парадигма, о ней тоже кратко рассказывается в этой главе.

Критика формы

К сожалению, в книге есть ошибки. Не могу сказать, появились ли они в процессе перевода и локализации книги или были в оригинальном издании. Например, на странице 39 вместо числа, 1/8388608 указано число 1/8 и рядом — 8388608. На странице 48 неправильно описан порядок определения стоимости алгоритма. Некоторые читатели сообщают об других ошибках в формулах и вычислениях. Конечно, в подобных базовых учебниках такие ошибки недопустимы. Но, с другой стороны, даже интересно отыскивать подобные ляпы в книге. Заодно лучше усваиваешь излагаемый материал.

Ещё один недостаток бумажного издания — это очень плохой мягкий переплёт со склейкой страниц у корешка. Знаете, есть такие книги, которые при первом прочтении начинают странно потрескивать, когда вы переворачиваете страницы. А при втором прочтении они просто распадаются на отдельные страницы. Эта книга как раз из таких — «одноразовых». Так что советую читать эту книгу в электронном варианте.

Это не Кнут, но тоже полезно

Нужно понимать, что «Теоретический минимум по Computer Science» — это не Дональд Кнут и его «Искусство программирования». Те, кто давно и профессионально занимается программированием, пожалуй, не найдут в этой книге для себя ничего нового. Она, скорее, будет интересна начинающим программистам и другим специалистам IT-сферы: тестировщикам, постановщикам задач, техническим писателям. В любом случае всегда полезно проверить и систематизировать свои базовые знания в том, что называется Computer Science. Для этого книга Владстона Ф. Фило очень хорошо подходит.

Бонусная задача

В заключение — небольшая задача из книги на знание теории вероятностей.

Ваш замок защищён пятью башнями. Каждая имеет 20%-ную вероятность поразить захватчика, прежде чем он достигнет ворот. Каковы шансы остановить его? Правильный ответ есть в книге.

Статья была впервые опубликована на другом ресурсе 2 декабря 2020.