Обзор книги «Теоретический минимум по Computer Science. Все что нужно программисту и разработчику»

Фундаментальные знания по Computer Science являются камнем преткновения для многих начинающих программистов, а то и не начинающих. Большинство программистов касаются этой темы только при подготовке к техническому собеседованию (или уже непосредственно на самом собеседовании). Справедливости ради, не всем программистам в процессе работы нужны знания о регистрах процессора или даже о временной сложности алгоритмов сортировки (например, если в языке есть функция «sort», которая уже использует алгоритм быстрой сортировки). Однако, если Вы решили, что Вам нужны фундаментальные знания Computer Science, и желательно в течении пары дней, то могу порекомендовать книгу «Теоретический минимум по Computer Science. Все что нужно программисту и разработчику» («Computer Science Distilled: Learn the Art of Solving Computational Problems»). Автор — Фило Владстон Феррейра (Wladston Ferreira Filho).

Книгу можно рекомендовать начинающим программистам. Читается она очень легко и не занимает много времени. Главное преимущество этой книги в отсутствии «воды». Материал изложен четко и кратко, с долей ненавязчивого юмора. Решение алгоритмических задач, рассмотренных в книге, сопровождается подробным изложением хода рассуждения. Каждый вывод основан на знаниях, полученных из предыдущего шага, что делает книгу самодостаточной и особенно ценной.

Предлагаю Вам свой обзор этой книги. Книга состоит из восьми глав. Вот их краткое описание.

Глава 1. Основы

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

Глава 2. Вычислительная сложность

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

Глава 3. Стратегия

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

Глава 4. Данные

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

Глава 5. Алгоритмы

В данной главе сравнивается временная сложность разных алгоритмов сортировки. Помимо временной сложности, рассматриваются и затраты памяти для каждого из алгоритмов. Можно узнать интересные нюансы о некоторых алгоритмах. Например, что для массивов, в которых не упорядочено незначительное количество элементов, сортировка «Вставками» имеет линейную временную сложность O(n). Описаны разные способы обхода графа. Рассмотрен пример с алгоритмом PageRank, используемым в поисковых системах для выставления «веса» web-страниц.

Глава 6. Базы данных

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

Глава 7. Компьютеры

В данной главе кратко изложены основные принципы работы компьютера без углубления в арифметические действия над регистрами. Описано взаимодействие между процессором и памятью, роль кэша, адресной шины и шины данных. Приведено сравнение объемов разных уровней памяти и скорости доступа к ним. Рассказывается о разрыве между производительностью процессора и памяти. Объясняется отличие 32-х разрядной архитектуры от 64-х разрядной. Кроме того, рассмотрены такие понятия, как компиляция, интерпретация, дизассемблирование, обратный инженерный анализ.

Глава 8. Программирование

Из этой главы читатель может узнать, чем отличаются императивная и декларативная парадигмы программирования. Дается объяснение терминов «Область видимости», «Функция высшего порядка», «Каринг функции», «Сопоставление с шаблоном». Особенно порадовало доходчивое объяснение понятия «замыкания», сопровождаемое вариантами использования и примерами псевдокода.

Все алгоритмические задачи, рассмотренные в данной книге, можно часто встретить на собеседованиях. Если Вы готовитесь к техническому интервью, эта книга будет очень кстати, но не будет исчерпывающей. В дальнейшем вам понадобятся более развернутые труды. Автор позаботился и об этом. После каждой главы дается список материалов, которые помогут углубиться в изучение заявленной темы. Среди данных материалов весьма известные книги Эндрю Таненбаума, Стива Макконела и Мартина Фаулера.

Разумеется, если есть возможность читать книгу в оригинале — читайте. Неточности перевода никто не отменял, но лично мне русский перевод не испортил впечатление о книге.