Владстон Феррейра Фило - Теоретический минимум по Computer Science [Все что нужно программисту и разработчику]

Переводчик А. Логунов

Технический редактор Н. Суслова

Литературный редактор А. Петров

Художники Л. Егорова, С. Маликова, Р. Яцко

Корректоры Н. Сидорова, Г. Шкатова

Верстка Л. Егорова

© Перевод на русский язык ООО Издательство «Питер», 2018

© Издание на русском языке, оформление ООО Издательство «Питер», 2018

© Серия «Библиотека программиста», 2018

Когда компьютеры начали менять мир, открывая перед людьми беспрецедентные возможности, расцвела новая наука — computer science. Она показала, как использовать компьютеры для решения задач. Это позволило нам использовать весь потенциал вычислительных машин. И мы достигли удивительных, просто сумасшедших результатов.

Computer science повсюду, но эта наука по-прежнему преподается как скучная теория. Многие программисты даже не изучали ее! Однако она крайне важна для эффективного программирования. Некоторые мои друзья не могут найти хорошего программиста, чтобы взять его на работу. Вычислительные мощности сегодня в изобилии, а вот людей, способных ими пользоваться, не хватает.

Рис. 1.Компьютерные задачи [1] Рисунок использован с согласия http://xkcd.com .

Эта книга — моя скромная попытка помочь миру, а также подтолкнуть вас к эффективному использованию компьютеров. В ней понятия computer science представлены в простой форме. Я свел научные подробности к минимуму. Хочется надеяться, что computer science произведет на вас впечатление, и ваш программный код станет лучше.

Если вы хотите щелкать задачи как орешки, находя эффективные решения, то эта книга для вас. От вас потребуется только чуть-чуть опыта в написании программного кода. Если вам приходилось этим заниматься и вы различаете элементарные операторы вроде for и while, то все в порядке. В противном случае вы найдете все необходимое (и даже больше) на каких-нибудь онлайновых курсах программирования [2] См., например, http://code.energy/coding-courses . . Вы можете пройти такой курс всего за неделю, и притом бесплатно. Для тех же, кто уже знаком с информатикой, эта книга станет превосходным повторением пройденного и поможет укрепить знания.

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

Да пребудет с вами сила!

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

моделировать идеи в блок-схемах и псевдокоде;

отличать правильное от неправильного при помощи логики ;

выполнять расчеты ;

уверенно вычислять вероятности .

Этого достаточно, чтобы переводить мысли в вычислимые решения.

Оказавшись перед сложной задачей, поднимитесь над ее хитросплетениями и изложите все самое важное на бумаге. Оперативная память человеческого мозга легко переполняется фактами и идеями. Многие подходы к организации работы предполагают изложение мыслей в письменной форме. Есть несколько способов это сделать. Сначала мы посмотрим, как пользоваться блок-схемами для представления процессов. Затем узнаем, как конструировать программируемые процессы на псевдокоде. Мы также попробуем смоделировать простую задачу при помощи математических формул.

Когда разработчики «Википедии» обсуждали организацию коллективной работы, они создали блок-схему дискуссии. Договариваться проще, если все инициативы перед глазами и объединены в общую картину (рис. 1.1).

Компьютерный код, как и изображенный выше процесс редактирования вики-страницы, по существу является процессом. Программисты часто пользуются блок-схемами для изображения вычислительных процессов на бумаге. Чтобы другие могли понимать ваши блок-схемы, вы должны соблюдать следующие рекомендации [3] Адаптация схемы с сайта http://wikipedia.org . :

• записывайте состояния и инструкции внутри прямоугольников;

• записывайте принятие решений, когда процесс может пойти различными путями, внутри ромбов;

• никогда не объединяйте инструкции с принятием решений;

• соединяйте стрелкой каждый последующий шаг с предыдущим;

• отмечайте начало и конец процесса.

Рис. 1.1.Редакционный процесс в «Википедии» [4] См., например, http://code.energy/coding-courses .

Рассмотрим составление блок-схемы на примере задачи поиска наибольшего из трех чисел (рис. 1.2).

Рис. 1.2.Поиск наибольшего из трех чисел