Книга «Теоретический минимум по Computer Science. Все что нужно программисту и разработчику»
Хватит тратить время на скучные академические фолианты! Изучение Computer Science может быть веселым и увлекательным занятием.
Владстон Феррейра Фило знакомит нас с вычислительным мышлением, позволяющим решать любые сложные задачи. Научиться писать код просто — пара недель на курсах, и вы «программист», но чтобы стать профи, который будет востребован всегда и везде, нужны фундаментальные знания. Здесь вы найдете только самую важную информацию, которая необходима каждому разработчику и программисту каждый день.
3.5. Эвристические алгоритмы
В обычных шахматах — 32 фигуры шести типов и 64 клетки, по которым они ходят. После каких-то четырех первых ходов число возможных дальнейших позиций достигает 288 млрд. Даже самые сильные игроки в мире не в состоянии найти идеальный ход. Они полагаются на интуицию, чтобы найти тот, который окажется достаточно хорошим. Мы можем делать то же самое при помощи алгоритмов. Эвристический метод, или просто эвристика, — это метод, который приводит к решению, не гарантируя, что оно — лучшее или оптимальное. Эвристические алгоритмы помогут, когда методы вроде полного перебора или поиска с возвратом оказываются слишком медленными. Существует много отличных эвристических подходов, но мы сосредоточимся на самом простом: на поиске без возврата.
«Жадные» алгоритмы
Очень распространенный эвристический подход к решению задач — использование так называемых «жадных» алгоритмов. Основная их идея состоит в том, чтобы никогда не откатываться к предыдущим вариантам. Это полная противоположность поиску с возвратом. Иными словами, на каждом шаге мы пытаемся сделать самый лучший выбор, а потом уже не подвергаем его сомнению. Давайте испытаем эту стратегию, чтобы по-новому решить задачу о рюкзаке (из раздела «Полный перебор» ).
Жадный грабитель и рюкзак. Грабитель пробирается в ваш дом, чтобы украсть предметы, которые вы хотели продать. Он решает использовать ваш рюкзак, чтобы унести в нем украденное. Что он возьмет? Имейте в виду, что чем быстрее он уйдет, тем меньше вероятность, что его поймают с поличным.
В сущности, оптимальное решение здесь должно быть ровно таким же, что и в задаче о рюкзаке. Однако у грабителя нет времени для перебора всех комбинаций упаковки рюкзака, ему некогда постоянно откатываться назад и вынимать уже уложенные в рюкзак вещи! Жадина будет совать в рюкзак самые дорогие предметы, пока не заполнит его:
Здесь мы не принимаем во внимание то, как наше текущее действие повлияет на будущие варианты выбора. Такой «жадный» подход позволяет отыскать подборку предметов намного быстрее, чем метод полного перебора. Однако он не дает никакой гарантии, что общая стоимость подборки окажется максимальной.
В вычислительном мышлении жадность — это не только смертный грех. Будучи добропорядочным торговцем, вы, возможно, тоже испытываете желание напихать в рюкзак всего побольше или очертя голову отправиться в поездку.
Снова коммивояжер. Коммивояжер должен посетить n заданных городов и закончить маршрут в той точке, откуда он его начинал. Какой план поездки позволит минимизировать общее пройденное расстояние?
Как мы убедились в разделе «Комбинаторика» (см. главу 1), число возможных комбинаций в этой задаче демонстрирует взрывной рост и достигает неприлично больших величин, даже если городов всего несколько. Найти оптимальное решение задачи коммивояжера с тысячами городов — чрезвычайно дорого (а то и вовсе невозможно).
И тем не менее вам нужен маршрут. Вот простой «жадный» алгоритм для этой задачи:
1) посетить ближайший город, где вы еще не были;
2) повторять, пока не объедете все города.
Можете ли вы придумать более хороший эвристический алгоритм, чем тот, что использует «жадный» подход? Специалисты по информатике вовсю ломают голову над этим вопросом.
Когда жадность побеждает силу
Выбирая эвристический алгоритм вместо классического, вы идете на компромисс. Насколько далеко от идеального решения вы можете отойти, чтобы результат все еще удовлетворял вас? Это зависит от конкретной ситуации.
Впрочем, даже если вам непременно требуется найти идеальный вариант, не стоит сбрасывать эвристику со счетов. Эвристический подход иногда приводит к самому лучшему решению. Например, вы можете разработать «жадный» алгоритм, способный найти такое же решение, что и алгоритм полного перебора. Давайте посмотрим, как такое осуществляется.
Электрическая сеть. Поселки в удаленном районе не были электрифицированы, но вот в одном из них начали строить электростанции. Энергия пойдет от поселка к поселку по линиям электропередач. Как включить все поселки в сеть, используя минимум проводов?
Данная задача может быть решена очень просто.
1.Среди поселков, еще не подключенных к сети, выбрать тот, который находится ближе всех к электрифицированному поселку, и соединить их.
2.Повторять, пока все поселки не будут подключены.
На каждом шаге мы выбираем для соединения пару поселков, которая на текущий момент выглядит самой лучшей. Несмотря на то что мы не анализируем, как этот вариант влияет на будущие возможности выбора, присоединение самого близкого поселка без электричества — всегда правильный выбор. Здесь нам повезло: структура задачи идеально подходит для решения «жадным» алгоритмом. В следующем разделе мы увидим структуры задач, для решения которых нужна стратегия великих полководцев.
Для Хаброжителей скидка 20% по купону — Computer Science
Теоретический минимум по Computer Science
Библиотека программиста.
Феррейра Фило Владстон «Теоретический минимум по Computer Science. Все, что нужно программисту и разработчику.» Питер, 2018 год, 224 стр., ISBN 978-5-4461-0587-8; (10,6 мб. pdf)
Хватит тратить время на скучные академические фолианты! Изучение Computer Science может быть веселым и увлекательным занятием. Владстон Феррейра Фило знакомит вас с вычислительным мышлением, позволяющим решать любые сложные задачи. Научиться писать код просто — пара недель на курсах, и вы «программист», но чтобы стать профи, который будет востребован всегда и везде, нужны фундаментальные знания. Здесь вы найдете только самую важную информацию, которая необходима каждому разработчику и программисту каждый день. Книга станет превосходным начальным учебником для всех кто увлекаются информационными технологиями (обязательна к прочтению).
Содержание.
Глава 1. Основы 14
1.1. Идеи 15
Блок-схемы 15
Псевдокод 17
Математические модели 18
1.2. Логика 20
Операторы 21
Булева алгебра 23
Таблицы истинности 25
Логика в вычислениях 29
1.3. Комбинаторика 31
Правило умножения 31
Перестановки 32
Перестановки без повторений 34
Комбинации 35
Правило суммирования 36
1.4. Вероятность 38
Подсчет количества возможных вариантов 38
Независимые (совместные) события 39
Несовместные события 40
Взаимодополняющие события 40
«Заблуждение игрока» 41
Более сложные вероятности 42
Подведем итоги 42
Полезные материалы 43
Глава 2. Вычислительная сложность 44
Надейтесь на лучшее, но готовьтесь к худшему 45
2.1. Оценка затрат времени 47
Понимание роста затрат 48
2.2. Нотация «О большое» 50
2.3. Экспоненциальное время 52
2.4. Оценка затрат памяти 54
Подведем итоги 55
Полезные материалы 56
Глава 3. Стратегия 57
3.1. Итерация 58
Вложенные циклы и степенные множества 59
3.2. Рекурсия 62
Рекурсия против итераций 63
3.3. Полный перебор 64
3.4. Поиск (перебор) с возвратом 67
3.5. Эвристические алгоритмы 71
«Жадные» алгоритмы 71
Когда жадность побеждает силу 73
3.6. Разделяй и властвуй 75
Разделить и отсортировать 75
Разделить и заключить сделку 80
Разделить и упаковать 82
3.7. Динамическое программирование 84
Мемоизация Фибоначчи 84
Мемоизация предметов в рюкзаке 85
Лучшая сделка снизу вверх 86
3.8. Ветви и границы 88
Верхние и нижние границы 88
Ветви и границы в задаче о рюкзаке 89
Подведем итоги 92
Полезные материалы 93
Глава 4. Данные 94
Абстракции 95
Тип данных 96
4.1. Абстрактные типы данных 96
Преимущества использования АТД 97
4.2. Общие абстракции 98
Примитивные типы данных 98
Стек 99
Очередь 100
Очередь с приоритетом 100
Список 101
Сортированный список 102
Множество 103
4.3. Структуры 104
Массив 104
Связный список 105
Двусвязный список 107
Массивы против связных списков 108
Дерево 109
Двоичное дерево поиска 112
Двоичная куча 115
Граф 117
Хеш-таблица 117
Подведем итоги 118
Полезные материалы 119
Глава 5. Алгоритмы 120
5.1. Сортировка 121
5.2. Поиск 124
5.3. Графы 125
Поиск в графах126
Раскраска графов 129
Поиск путей в графе 130
PageRank 133
5.4. Исследование операций 133
Задачи линейной оптимизации 134
Задачи о максимальном потоке в Сети 137
Подведем итоги 138
Полезные материалы 139
Глава 6. Базы данных 140
6.1. Реляционная модель 142
Отношения 142
Миграция схемы 145
SQL 146
Индексация 148
Транзакции 151
6.2. Нереляционная модель 152
Документные хранилища 152
Хранилища «ключ — значение» 154
Графовые базы данных 155
Большие данные 156
SQL против NoSQL 157
6.3. Распределенная модель 158
Репликация с одним ведущим 159
Репликация с многочисленными ведущими 159
Фрагментирование 160
Непротиворечивость данных 162
6.4. Географическая модель 163
6.5. Форматы сериализации 165
Подведем итоги 166
Полезные материалы 166
Глава 7. Компьютеры 167
7.1. Архитектура 168
Память 168
Процессор 171
7.2. Компиляторы 177
Операционные системы 181
Оптимизация при компиляции 182
Языки сценариев 183
Дизассемблирование и обратный инженерный анализ 184
Программное обеспечение с открытым исходным кодом 185
7.3. Иерархия памяти 186
Разрыв между памятью и процессором 187
Временная и пространственная локальность 188
Кэш L1 189
Кэш L2 189
Первичная память против вторичной 191
Внешняя и третичная память 193
Тенденции в технологии памяти 194
Подведем итоги 195
Полезные материалы 196
Глава 8. Программирование 197
8.1. Лингвистика 198
Значения 198
Выражения 198
Инструкции 200
8.2. Переменные 201
Типизация переменных 202
Область видимости переменных 202
8.3. Парадигмы 204
Императивное программирование 204
Декларативное программирование 207
Логическое программирование 213
Подведем итоги 214
Полезные материалы 214
Заключение 215
Приложения 217
I. Системы счисления 217
II. Метод Гаусса 219
III. Множества 220
IV. Алгоритм Кэдейна 222
Обзор книги Владстона Феррейра Фило «Теоретический минимум по Computer Science. Всё, что нужно программисту и разработчику»
Авторизуйтесь
Обзор книги Владстона Феррейра Фило «Теоретический минимум по Computer Science. Всё, что нужно программисту и разработчику»
кандидат технических наук, Tech Lead Bercut
Прочитав название книги, многие из вас, наверное, скажут: «Ну вот, ещё одна книга для чайников. Опять нам будут рассказывать о том, что такое двоичная система исчисления и какие бывают циклы». Отчасти вы будете правы: в книге, действительно, рассказывается о простых и базовых понятиях и принципах, которые должен знать каждый программист. Только вот «теоретический минимум», изложенный в книге, включает в себя множество интересных и полезных вещей, о которых мало пишут в подобной литературе начального уровня. Задайте себе вопрос: действительно ли вы так хорошо знаете основы того, что называется Computer Science?
А вы в этом уверены?
Давайте проведём небольшой эксперимент. Попробуйте ответить на следующие вопросы:
Если вы не смогли уверенно ответить на бо́льшую часть этих вопросов, но сами вопросы показались вам интересными, то вам стоит прочитать эту книгу. Хотя бы для общего развития.
Общие впечатления
В каждом разделе книги изложение ведётся от простого к сложному. Есть в книге и совсем базовые знания. Например, в ней, действительно, описываются двоичная система, булева алгебра и блок-схемы. Но автор делает это кратко, чтобы затем перейти к изложению более интересных вещей. Вообще, в книге почти нет ничего лишнего — вся информация изложена сжато, но вполне доступно. Несущественные и очевидные промежуточные шаги часто пропущены. Благодаря этому описание алгоритмов и правил читается легко. Как говорил Гомер Симпсон, «Мне некогда читать, передай смысл». Это как раз то, чего не хватает многим учебникам начального уровня, которые переполнены лишней и ненужной информацией.
Иллюстрации в этой книге сделаны качественно и профессионально. Автор не поленился составить графические примеры к большинству сложных алгоритмов. Рисунки очень помогают в изучении материала. Например, после изложения принципов выполнения логических операций приведена принципиальная схема суммирования двухразрядных чисел. По схеме можно самостоятельно проследить, как выполняется суммирование с помощью простейших элементов AND и XOR. Ещё в книге есть несколько подходящих к случаю комиксов с таких сайтов, как xkcd.com и geek-and-poke.com.
Примеры алгоритмов в книге оформлены очень удобно — в виде псевдокода, который будет понятен всем, кто хоть раз в жизни самостоятельно написал программку с использованием функций, циклов, условий и оператора присваивания.
13–15 декабря, Онлайн, Беcплатно
В конце каждой главы приведены ссылки на полезные материалы. Все они оформлены как разделы на сайте code.energy. Вот пример. В некоторых случаях они ведут на страницу с соответствующей книгой в магазине Amazon. Но есть и такие, которые открывают страницы или PDF-файлы. Последние, конечно, полезнее, чем ссылки на книгу в магазине.
Просто, как бином
В первой главе книги излагаются самые основы: блок-схемы, булева алгебра, базовые формулы комбинаторики и теории вероятности. Это именно то, чему студентов технических специальностей учат на предметах «Информатика» и «Дискретная математика». Если вы знаете, что A XOR B тождественно !(А↔B) и как вычислить вероятность наступления совместных, несовместных и взаимодополняющих событий, то можете смело пропускать эту главу. Кстати, на каждое правило в главе приведены довольно интересные примеры.
Надейтесь на лучшее, но готовьтесь к худшему
Во второй главе книги автор рассказывает о понятии вычислительной сложности алгоритмов. В ней приведена методика расчёта временно́й сложности алгоритма — так называемого «О большого» — по числу требуемых операций и количеству входных данных. Наглядно показано, как различаются алгоритмы с единичной, линейной, логарифмической, квадратичной и экспоненциальной сложностью. Рассказано о том, почему первые — самые лучшие, а вторые — самые худшие алгоритмы. Ну и про пространственную сложность алгоритмов тоже упомянуто — память у современных компьютеров большая, но всё же конечная. Кстати, недавно в ленте Tproger ВКонтакте выкладывали шпаргалку со сложностью всех популярных алгоритмов. В этой главе книги как раз говорится о том, что такое сложность алгоритма и как её вычислить.
Сначала стратегия, потом тактика
Третья глава называется «Стратегия». В ней очень доходчиво объясняется, что такое итерация и рекурсия и в каких случаях их лучше всего использовать. Автор рассказывает о том, как лучше организовать проверку всех подходящих решений задачи — от грубого полного перебора до поиска с возвратом и эвристических алгоритмов, а также объясняет, как использовать разделение множеств для оптимизации сортировки значений и решения других задач. Также здесь немного рассказано о динамическом программировании и методе ветвей и границ. В целом эта глава о том, как выбрать оптимальный метод для решения поставленной задачи.
Балансируем деревья
Четвёртая глава книги посвящена структурам и абстрактным типам хранения данных. Я просто перечислю те структуры и типы, о которых в ней говорится: стек, очередь, очередь с приоритетом, список, сортированный список, множество, массив, связный список, двусвязный список, дерево, двоичное дерево, двоичная куча, граф, хеш-таблица. Никаких сюрпризов в этой главе нет, автор последовательно и обстоятельно рассказывает о каждом типе и каждой структуре.
Опять пресловутая задача о коммивояжёре
Пятая глава содержит описание и разбор различных наиболее часто используемых алгоритмов: сортировки, поиска узла и оптимального пути в графах. Кратко рассказывается об алгоритмах решения задач линейной оптимизации, поиска максимального потока в графе, раскраски графов. Прочитав эту главу, вы получите представление о том, какие существуют стандартные алгоритмы и как их правильно применять.
SQL vs NoSQL
Шестую главу большинство читателей может лишь бегло пролистать. Ну кто из программистов не знает о реляционных и нереляционных базах данных, SQL, индексах, транзакциях и распределённых моделях? Тем же, кто только начинает свой путь в области разработки будет полезно прочитать эту главу, чтобы систематизировать базовые знания и ничего не упустить.
Почему памяти полно, а программа всё равно «тормозит»
Седьмая глава называется просто и незамысловато: «Компьютеры». В ней (сюрприз!) рассказывается о том, что такое ЦП и ОЗУ и как они обмениваются командами и данными. А ещё про ассемблер, операционные системы и компиляторы. Упоминание команд одного из первых процессоров удивительным образом перекликается с разделом «Программное обеспечение с открытым исходным кодом». Сразу вспоминается рассказ Линуса Торвальдса о том, как всё начиналось, в книге «Just for fun».
Дальше рассказывается о такой полезной вещи, как иерархия памяти. Если вы не смогли ответить на вопрос про кэш уровня L1, L2 и L3, то вам стоит почитать эту часть книги.
Есть не только императивное программирование
Наконец, в восьмой главе содержится то, ради чего всё затевалось — рассказ о программировании. Глава разделена на два подраздела: «Лингвистика» и «Парадигмы программирования». В первом излагаются совсем базовые вещи. Например, что такое переменная. А второй подраздел можно читать, как отдельную статью-обзор современных парадигм разработки. К примеру, если вы адепт императивного программирования и не знаете, что такое карринг и замыкание, вам будет интересно познакомиться с декларативным программированием. Кстати, есть ещё логическая парадигма, о ней тоже кратко рассказывается в этой главе.
Критика формы
К сожалению, в книге есть ошибки. Не могу сказать, появились ли они в процессе перевода и локализации книги или были в оригинальном издании. Например, на странице 39 вместо числа, 1/8388608 указано число 1/8 и рядом — 8388608. На странице 48 неправильно описан порядок определения стоимости алгоритма. Некоторые читатели сообщают об других ошибках в формулах и вычислениях. Конечно, в подобных базовых учебниках такие ошибки недопустимы. Но, с другой стороны, даже интересно отыскивать подобные ляпы в книге. Заодно лучше усваиваешь излагаемый материал.
Ещё один недостаток бумажного издания — это очень плохой мягкий переплёт со склейкой страниц у корешка. Знаете, есть такие книги, которые при первом прочтении начинают странно потрескивать, когда вы переворачиваете страницы. А при втором прочтении они просто распадаются на отдельные страницы. Эта книга как раз из таких — «одноразовых». Так что советую читать эту книгу в электронном варианте.
Это не Кнут, но тоже полезно
Нужно понимать, что «Теоретический минимум по Computer Science» — это не Дональд Кнут и его «Искусство программирования». Те, кто давно и профессионально занимается программированием, пожалуй, не найдут в этой книге для себя ничего нового. Она, скорее, будет интересна начинающим программистам и другим специалистам IT-сферы: тестировщикам, техническим писателям, постановщикам задач. В любом случае всегда полезно проверить и систематизировать свои базовые знания в том, что называется Computer Science. Для этого книга Владстона Феррейра Фило очень хорошо подходит. Мне как непрофессиональному программисту читать некоторые разделы этой книги было интересно — я не знал, как ответить, на часть вопросов, заданных в начале этой статьи.
Бонусная задача
В заключение — небольшая задача из книги на знание теории вероятности.
Ваш замок защищён пятью башнями. Каждая имеет 20%-ную вероятность поразить захватчика, прежде чем он достигнет ворот. Каковы шансы остановить его?
Если вы думаете, что ответ — 100% (20% умножить на 5), то вы ошибаетесь. Не суммируйте вероятности независимых событий. Правильный ответ есть в книге.
Теоретический минимум по Computer Science. Все что нужно программисту и разработчику
Владстон Феррейра Фило
Хватит тратить время на скучные академические фолианты! Изучение Computer Science может быть веселым и увлекательным занятием.
Владстон Феррейра Фило знакомит нас с вычислительным мышлением, позволяющим решать любые сложные задачи. Научиться писать код просто — пара недель на курсах, и вы «программист», но чтобы стать профи, который будет востребован всегда и везде, нужны фундаментальные знания. Здесь вы найдете только самую важную информацию, которая необходима каждому разработчику и программисту каждый день. «Эта книга пригодится и для решения повседневных задач. Упреждающая выборка и кэширование помогут сложить рюкзак, параллелизм облегчит готовку на кухне.
Ну и, разумеется, ваш программный код будет просто потрясающим». Владстон Феррейра Фило
Отвратительная книга. В книгу включена куча разных тем, по всем бегут галопом, рассматривая крайне поверхностно. Местами достаточно сложно объясняются простые вещи, что создаёт впечатление, что автор сам не до конца понимает, о чем пишет. В главе по логике сделана логическая ошибка при выведении из одного утверждения другого. В общем бросил недочитав, ибо книга выглядит не то что бесполезной, а даже вредной.
Кстати, это единственная книга от этого автора, что многое объясняет.
Отвратительная книга. В книгу включена куча разных тем, по всем бегут галопом, рассматривая крайне поверхностно. Местами достаточно сложно объясняются простые вещи, что создаёт впечатление, что автор сам не до конца понимает, о чем пишет. В главе по логике сделана логическая ошибка при выведении из одного утверждения другого. В общем бросил недочитав, ибо книга выглядит не то что бесполезной, а даже вредной.
Кстати, это единственная книга от этого автора, что многое объясняет.
Хороший теоретический минимум по Computer Science
много всего
даёт представление о том, что изучается на компьютер сайенс специальности в университетах (ну наверное) если кратко, то — дискретная математика, комбинаторика, логика, теория вероятностей, алгоритмы, железо и программирование. ничего супирсложного, всё вполне реально выучить самостоятельно в любом возрасте :3