Теоретический минимум по компьютер сайнс

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

Хватит тратить время на скучные академические фолианты! Изучение Computer Science может быть веселым и увлекательным занятием.
Владстон Феррейра Фило знакомит нас с вычислительным мышлением, позволяющим решать любые сложные задачи. Научиться писать код просто — пара недель на курсах, и вы «программист», но чтобы стать профи, который будет востребован всегда и везде, нужны ф Хватит тратить время на скучные академические фолианты! Изучение Computer Science может быть веселым и увлекательным занятием.
Владстон Феррейра Фило знакомит нас с вычислительным мышлением, позволяющим решать любые сложные задачи. Научиться писать код просто — пара недель на курсах, и вы «программист», но чтобы стать профи, который будет востребован всегда и везде, нужны фундаментальные знания. Здесь вы найдете только самую важную информацию, которая необходима каждому разработчику и программисту каждый день.

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

5. Эвристические алгоритмы

В обычных шахматах — 32 фигуры шести типов и 64 клетки, по которым они ходят. После каких-то четырех первых ходов число возможных дальнейших позиций достигает 288 млрд. Даже самые сильные игроки в мире не в состоянии найти идеальный ход. Они полагаются на интуицию, чтобы найти тот, который окажется достаточно хорошим. Мы можем делать то же самое при помощи алгоритмов. Эвристический метод, или просто эвристика, — это метод, который приводит к решению, не гарантируя, что оно — лучшее или оптимальное. Эвристические алгоритмы помогут, когда методы вроде полного перебора или поиска с возвратом оказываются слишком медленными. Существует много отличных эвристических подходов, но мы сосредоточимся на самом простом: на поиске без возврата.

Очень распространенный эвристический подход к решению задач — использование так называемых «жадных» алгоритмов. Основная их идея состоит в том, чтобы никогда не откатываться к предыдущим вариантам. Это полная противоположность поиску с возвратом. Иными словами, на каждом шаге мы пытаемся сделать самый лучший выбор, а потом уже не подвергаем его сомнению. Давайте испытаем эту стратегию, чтобы по-новому решить задачу о рюкзаке (из раздела «Полный перебор» ).

Жадный грабитель и рюкзак. Грабитель пробирается в ваш дом, чтобы украсть предметы, которые вы хотели продать. Он решает использовать ваш рюкзак, чтобы унести в нем украденное. Что он возьмет? Имейте в виду, что чем быстрее он уйдет, тем меньше вероятность, что его поймают с поличным.

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

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

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

Снова коммивояжер. Коммивояжер должен посетить n заданных городов и закончить маршрут в той точке, откуда он его начинал. Какой план поездки позволит минимизировать общее пройденное расстояние?

Как мы убедились в разделе «Комбинаторика» (см. главу 1), число возможных комбинаций в этой задаче демонстрирует взрывной рост и достигает неприлично больших величин, даже если городов всего несколько. Найти оптимальное решение задачи коммивояжера с тысячами городов — чрезвычайно дорого (а то и вовсе невозможно).

И тем не менее вам нужен маршрут. Вот простой «жадный» алгоритм для этой задачи:

1) посетить ближайший город, где вы еще не были;
2) повторять, пока не объедете все города.

Можете ли вы придумать более хороший эвристический алгоритм, чем тот, что использует «жадный» подход? Специалисты по информатике вовсю ломают голову над этим вопросом.

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

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

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

Теоретический минимум по Computer Science [Все что нужно программисту и разработчику] — читать онлайн ознакомительный отрывок

Ниже представлен текст книги, разбитый по страницам. Система сохранения места последней прочитанной страницы, позволяет с удобством читать онлайн бесплатно книгу «Теоретический минимум по Computer Science [Все что нужно программисту и разработчику]», без необходимости каждый раз заново искать на чём Вы остановились. Поставьте закладку, и сможете в любой момент перейти на страницу, на которой закончили чтение.

Владстон Феррейра Фило

Теоретический минимум по Computer Science

Все что нужно программисту и разработчику

Фото

2018

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

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

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

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

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

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

Друзья — это семья, которую мы сами себе выбираем. Я посвящаю книгу моим друзьям Ромуло, Лео, Мото и Крису, которые постоянно меня торопили, чтобы я ее, наконец, закончил.

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

Лорд Байрон, из письма будущей жене Аннабелле (1813 год). Их дочь Ада Лавлейс стала первым программистом

Каждый в нашей стране должен научиться программировать, потому что это учит думать.

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

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

Фото

Рис. 1. Компьютерные задачи[1]

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

Эта книга для меня?

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

Но разве computer science не только для ученых?

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

Фото

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

Информатика не более наука о компьютерах, чем астрономия — наука о телескопах. Информатика неразрывно связана с математикой.

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

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

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

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

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

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

Лучшая рецензия на книгу

Теоретический минимум по Computer Science. Все что нужно программисту и разработчику Владстон Феррейра Фило 978-5-4461-0587-8

sunnyydaisy sunnyydaisy написала рецензию

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

3 августа 2021 г. 23:30

5 Как долго я тебя искала!

Давно хотела изучить основы computer science, но всё не находила подходящий источник. А потом увидела на LiveLib отзыв на эту книгу и сразу решила купить.

Привлекло содержание и небольшой объём (222 страницы). Я свято верю, что краткость — сестра таланта. Очень много всего можно освятить в рамках computer science, но я хотела найти самую мякушку.

И нашла её в книге Владстона Феррейра Фило. Он раскладывает по полочкам основные понятия, кратко освещает наиболее важные аспекты. Для тех, кто хочет копнуть глубже, оставляет ссылки на источники в конце каждой главы.

Мне кажется, это идеальная книга для новичков: она просто объясняет сложные вопросы, даёт направления для дальнейшего изучения и полна смешных картинок. А все мы знаем, какое важное место занимают мемы в иерархии ценностей…

Год издания: 2018

Мягкая обложка, 224стр.
Формат: 70×100/16

Возрастные ограничения: 16+

Теоретический минимум по Computer Science, Владстон Феррейра Фило, 2018, PDF, EPUB

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

Все книги представленные на сайте WEB-Программист только в ознакомительных целях. Любое их использование Вами допускается только в ознакомительных целях. Если Вы планируете их использовать в дальнейшем, то Вы обязаны приобрести их у правообладателей. Администрация сайта не несет ответственность за их использование Вами

Теоретический минимум по Computer Science, Владстон Феррейра Фило, 2018

Когда жадность побеждает силу

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

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

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

1.Среди поселков, еще не подключенных к сети, выбрать тот, который находится ближе всех к электрифицированному поселку, и соединить их.
2.Повторять, пока все поселки не будут подключены.

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