Книга «Теоретический минимум по Computer Science. Все что нужно программисту и разработчику»
Хватит тратить время на скучные академические фолианты! Изучение Computer Science может быть веселым и увлекательным занятием.
Владстон Феррейра Фило знакомит нас с вычислительным мышлением, позволяющим решать любые сложные задачи. Научиться писать код просто — пара недель на курсах, и вы «программист», но чтобы стать профи, который будет востребован всегда и везде, нужны фундаментальные знания. Здесь вы найдете только самую важную информацию, которая необходима каждому разработчику и программисту каждый день.
3.5. Эвристические алгоритмы
В обычных шахматах — 32 фигуры шести типов и 64 клетки, по которым они ходят. После каких-то четырех первых ходов число возможных дальнейших позиций достигает 288 млрд. Даже самые сильные игроки в мире не в состоянии найти идеальный ход. Они полагаются на интуицию, чтобы найти тот, который окажется достаточно хорошим. Мы можем делать то же самое при помощи алгоритмов. Эвристический метод, или просто эвристика, — это метод, который приводит к решению, не гарантируя, что оно — лучшее или оптимальное. Эвристические алгоритмы помогут, когда методы вроде полного перебора или поиска с возвратом оказываются слишком медленными. Существует много отличных эвристических подходов, но мы сосредоточимся на самом простом: на поиске без возврата.
«Жадные» алгоритмы
Очень распространенный эвристический подход к решению задач — использование так называемых «жадных» алгоритмов. Основная их идея состоит в том, чтобы никогда не откатываться к предыдущим вариантам. Это полная противоположность поиску с возвратом. Иными словами, на каждом шаге мы пытаемся сделать самый лучший выбор, а потом уже не подвергаем его сомнению. Давайте испытаем эту стратегию, чтобы по-новому решить задачу о рюкзаке (из раздела «Полный перебор» ).
Жадный грабитель и рюкзак. Грабитель пробирается в ваш дом, чтобы украсть предметы, которые вы хотели продать. Он решает использовать ваш рюкзак, чтобы унести в нем украденное. Что он возьмет? Имейте в виду, что чем быстрее он уйдет, тем меньше вероятность, что его поймают с поличным.
В сущности, оптимальное решение здесь должно быть ровно таким же, что и в задаче о рюкзаке. Однако у грабителя нет времени для перебора всех комбинаций упаковки рюкзака, ему некогда постоянно откатываться назад и вынимать уже уложенные в рюкзак вещи! Жадина будет совать в рюкзак самые дорогие предметы, пока не заполнит его:
Здесь мы не принимаем во внимание то, как наше текущее действие повлияет на будущие варианты выбора. Такой «жадный» подход позволяет отыскать подборку предметов намного быстрее, чем метод полного перебора. Однако он не дает никакой гарантии, что общая стоимость подборки окажется максимальной.
В вычислительном мышлении жадность — это не только смертный грех. Будучи добропорядочным торговцем, вы, возможно, тоже испытываете желание напихать в рюкзак всего побольше или очертя голову отправиться в поездку.
Снова коммивояжер. Коммивояжер должен посетить n заданных городов и закончить маршрут в той точке, откуда он его начинал. Какой план поездки позволит минимизировать общее пройденное расстояние?
Как мы убедились в разделе «Комбинаторика» (см. главу 1), число возможных комбинаций в этой задаче демонстрирует взрывной рост и достигает неприлично больших величин, даже если городов всего несколько. Найти оптимальное решение задачи коммивояжера с тысячами городов — чрезвычайно дорого (а то и вовсе невозможно).
И тем не менее вам нужен маршрут. Вот простой «жадный» алгоритм для этой задачи:
1) посетить ближайший город, где вы еще не были;
2) повторять, пока не объедете все города.
Можете ли вы придумать более хороший эвристический алгоритм, чем тот, что использует «жадный» подход? Специалисты по информатике вовсю ломают голову над этим вопросом.
Когда жадность побеждает силу
Выбирая эвристический алгоритм вместо классического, вы идете на компромисс. Насколько далеко от идеального решения вы можете отойти, чтобы результат все еще удовлетворял вас? Это зависит от конкретной ситуации.
Впрочем, даже если вам непременно требуется найти идеальный вариант, не стоит сбрасывать эвристику со счетов. Эвристический подход иногда приводит к самому лучшему решению. Например, вы можете разработать «жадный» алгоритм, способный найти такое же решение, что и алгоритм полного перебора. Давайте посмотрим, как такое осуществляется.
Электрическая сеть. Поселки в удаленном районе не были электрифицированы, но вот в одном из них начали строить электростанции. Энергия пойдет от поселка к поселку по линиям электропередач. Как включить все поселки в сеть, используя минимум проводов?
Данная задача может быть решена очень просто.
1.Среди поселков, еще не подключенных к сети, выбрать тот, который находится ближе всех к электрифицированному поселку, и соединить их.
2.Повторять, пока все поселки не будут подключены.
На каждом шаге мы выбираем для соединения пару поселков, которая на текущий момент выглядит самой лучшей. Несмотря на то что мы не анализируем, как этот вариант влияет на будущие возможности выбора, присоединение самого близкого поселка без электричества — всегда правильный выбор. Здесь нам повезло: структура задачи идеально подходит для решения «жадным» алгоритмом. В следующем разделе мы увидим структуры задач, для решения которых нужна стратегия великих полководцев.
Для Хаброжителей скидка 20% по купону — Computer Science
Теоретический минимум по computer science все что нужно программисту и разработчику
Каждый в нашей стране должен научиться программировать, потому что это учит думать.
Когда компьютеры начали менять мир, открывая перед людьми беспрецедентные возможности, расцвела новая наука — computer science. Она показала, как использовать компьютеры для решения задач. Это позволило нам использовать весь потенциал вычислительных машин. И мы достигли удивительных, просто сумасшедших результатов.
Computer science повсюду, но эта наука по-прежнему преподается как скучная теория. Многие программисты даже не изучали ее! Однако она крайне важна для эффективного программирования. Некоторые мои друзья не могут найти хорошего программиста, чтобы взять его на работу. Вычислительные мощности сегодня в изобилии, а вот людей, способных ими пользоваться, не хватает.
Рис. 1. Компьютерные задачи[1]
Эта книга — моя скромная попытка помочь миру, а также подтолкнуть вас к эффективному использованию компьютеров. В ней понятия computer science представлены в простой форме. Я свел научные подробности к минимуму. Хочется надеяться, что computer science произведет на вас впечатление, и ваш программный код станет лучше.
Эта книга для меня?
Если вы хотите щелкать задачи как орешки, находя эффективные решения, то эта книга для вас. От вас потребуется только чуть-чуть опыта в написании программного кода. Если вам приходилось этим заниматься и вы различаете элементарные операторы вроде for и while, то все в порядке. В противном случае вы найдете все необходимое (и даже больше) на каких-нибудь онлайновых курсах программирования[2]. Вы можете пройти такой курс всего за неделю, и притом бесплатно. Для тех же, кто уже знаком с информатикой, эта книга станет превосходным повторением пройденного и поможет укрепить знания.
Но разве computer science не только для ученых?
Эта книга — для всех. Она о вычислительном мышлении. Вы научитесь превращать задачи в вычислимые системы. Вы также будете использовать вычислительное мышление в повседневных задачах. Упреждающая выборка и кэширование помогут вам упростить процесс упаковки вещей. Освоив параллелизм, вы станете эффективнее управляться на кухне. Ну и, разумеется, ваш программный код будет просто потрясающим.
Теоретический минимум по Computer Science. Все что нужно программисту и разработчику
Посоветуйте книгу друзьям! Друзьям – скидка 10%, вам – рубли
Эта и ещё 2 книги за 299 ₽
Отзывы 14
Прекрасная книга. Рекомендовал и старшим школьникам и студентам. Действительно является за нательным введением в компьютерные науки. Ознакомиться рекомендовал бы всем.
Прекрасная книга. Рекомендовал и старшим школьникам и студентам. Действительно является за нательным введением в компьютерные науки. Ознакомиться рекомендовал бы всем.
Очень хорошая книга. Подойдёт как новичкам, чтобы познакомится с основами Computer Science, так и профессионалам, чтобы освежить некоторые моменты в памяти. Читается очень легко и интересно, очень понравилась глава про стратегии решения алгоритмов (очень нужный материал, жаль, что не в каждой книге он есть).
Очень хорошая книга. Подойдёт как новичкам, чтобы познакомится с основами Computer Science, так и профессионалам, чтобы освежить некоторые моменты в памяти. Читается очень легко и интересно, очень понравилась глава про стратегии решения алгоритмов (очень нужный материал, жаль, что не в каждой книге он есть).
Отличное введение в computer science. Очень современно и обезвожжено. Предварительное знакомство с темой не обязательно, хотя желательно
Отличное введение в computer science. Очень современно и обезвожжено. Предварительное знакомство с темой не обязательно, хотя желательно
Книга очень начального уровня. Строго рекомендуется для школьников и студентов начальной школы. Просто и понятное изложение, лёгкое повествование. Книга старается покрыть многие области computer science и не всегда это получается успешно, например как с логическими языками программирование. Ещё как всегда ратсраивают ошибки в переводе от издательства «Питер».
Книга очень начального уровня. Строго рекомендуется для школьников и студентов начальной школы. Просто и понятное изложение, лёгкое повествование. Книга старается покрыть многие области computer science и не всегда это получается успешно, например как с логическими языками программирование. Ещё как всегда ратсраивают ошибки в переводе от издательства «Питер».
Всегда интересно посмотреть на что то от общего к частному, поэтому эта книга полезна для полноценного понимания именно тематики компьютеров и всё что с ними связано.А так как ответвлений много, то можно двигаться уже дальше в более конкретные области. Кто то скажет, что это голая теория, но именно с теории надо изучать большинство наук.
Всегда интересно посмотреть на что то от общего к частному, поэтому эта книга полезна для полноценного понимания именно тематики компьютеров и всё что с ними связано.А так как ответвлений много, то можно двигаться уже дальше в более конкретные области. Кто то скажет, что это голая теория, но именно с теории надо изучать большинство наук.
Новичкам в области программирования книга будет очень полезной, однако студенты, отучившиеся уже один-два курса, в этой книге ничего нового почти не найдут.
Новичкам в области программирования книга будет очень полезной, однако студенты, отучившиеся уже один-два курса, в этой книге ничего нового почти не найдут.
Отзыв о книге «Теоретический минимум по 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. Программирование
Из этой главы читатель может узнать, чем отличаются императивная и декларативная парадигмы программирования. Дается объяснение терминов «Область видимости», «Функция высшего порядка», «Каринг функции», «Сопоставление с шаблоном». Особенно порадовало доходчивое объяснение понятия «замыкания», сопровождаемое вариантами использования и примерами псевдокода.
Все алгоритмические задачи, рассмотренные в данной книге, можно часто встретить на собеседованиях. Если Вы готовитесь к техническому интервью, эта книга будет очень кстати, но не будет исчерпывающей. В дальнейшем вам понадобятся более развернутые труды. Автор позаботился и об этом. После каждой главы дается список материалов, которые помогут углубиться в изучение заявленной темы. Среди данных материалов весьма известные книги Эндрю Таненбаума, Стива Макконела и Мартина Фаулера.
Разумеется, если есть возможность читать книгу в оригинале — читайте. Неточности перевода никто не отменял, но лично мне русский перевод не испортил впечатление о книге.
Отзыв о книге «Теоретический минимум по 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. Программирование
Из этой главы читатель может узнать, чем отличаются императивная и декларативная парадигмы программирования. Дается объяснение терминов «Область видимости», «Функция высшего порядка», «Каринг функции», «Сопоставление с шаблоном». Особенно порадовало доходчивое объяснение понятия «замыкания», сопровождаемое вариантами использования и примерами псевдокода.
Все алгоритмические задачи, рассмотренные в данной книге, можно часто встретить на собеседованиях. Если Вы готовитесь к техническому интервью, эта книга будет очень кстати, но не будет исчерпывающей. В дальнейшем вам понадобятся более развернутые труды. Автор позаботился и об этом. После каждой главы дается список материалов, которые помогут углубиться в изучение заявленной темы. Среди данных материалов весьма известные книги Эндрю Таненбаума, Стива Макконела и Мартина Фаулера.
Разумеется, если есть возможность читать книгу в оригинале — читайте. Неточности перевода никто не отменял, но лично мне русский перевод не испортил впечатление о книге.