Метка: хакинг

• Вы узнаете

  • Полезные инструменты для Windows и Linux
  • Сокрытие секретных данных в картинках
  • Необходимые утилиты для работы в терминале
  • Переустановка Windows через удаленный доступ
  • Ускорение работы Windows 11 на старом железе
  • Твики, трюки и «секретные» настройки Windows 11
  • Постройка необычного корпуса для компьютера
  • Сборка ноутбука своими руками с нуля
  • Установка суперконденсатора в беспроводную мышь, чтобы заряжать ее за секунды
  • Компьютеры Apple c процессором M1 для хакера

Книгу можно купить в нашем интернет-магазине.

 

Большинство пользователей не любят что-либо менять в компьютере: обычно все настройки сводятся к смене обоев Рабочего стола. Да и модифицировать «железо» берутся далеко не все — а вдруг что-нибудь сломается? Мы, хакеры, не такие! Для настоящего компьютерного гика нет большего удовольствия, чем нырнуть в самую глубину операционной системы, что-нибудь там поменять, перенастроить и переделать, чтобы все заработало быстрее, эффективнее и лучше. А если нам хочется усовершенствовать компьютер или ноутбук, в ход идут лобзик, дрель и паяльник! Если ты тоже переполнен жаждой познания, любишь изучать «внутренний мир» операционных систем и софта, а также мечтаешь, чтобы твой комп стал уникальным и неповторимым — эта книга для тебя!

Валентин Холмогоров, редактор рубрики «Взлом» журнала «Хакер»

В книге собраны сказки о созвездиях, светилах и других небесных обитателях, которые придумали народы, живущие в Сибири и на Дальнем Востоке: эвенки, кеты, хакасы, буряты и алтайцы. А  пересказала их писатель Марина Бабанская, которая все детство провела во Владивостоке и с тех пор влюблена в эти края.

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

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

Книгу можно купить в нашем интернет-магазине.

• Теоретическая часть: основные положения и терминология
• Более 800 задач с ответами и решениями
• Широкое использование тематики информационно-коммуникационных технологий
• Контрольные вопросы к каждой главе
• Схема информационной зависимости материала книги
• Дополнительная справочная информация

Книгу можно купить в нашем интернет-магазине.

 

Зачем школьнику эта книга

Назначение книги — помочь ребёнку 10–13 лет сделать первые шаги в программировании и получить удовольствие от этого процесса.
Почему не «научить программировать», «освоить Python», «подготовиться к олимпиадам»? Потому что всё это будет вторым, третьим, n-м шагами на пути программиста. А для начала нужно на этот путь встать и проверить, подходит ли он тебе. В 4–6 классах школы нужно как можно больше всего попробовать, чтобы к 7–9 классу найти то, что нравится и хорошо получается и углубиться в него, а в 10–11 прагматично идти к будущей профессии.

Книгу можно купить в нашем интернет-магазине.

В нашем издательстве вышла уникальная книга, которая позволит детям  5-7 классов освоить азы программирования и конструирования электронных устройств: «BBC micro:bit для юных конструкторов и программистов». В книге рассмотрено более 20 творческих проектов с использованием учебной платы BBC micro:bit .

Ребёнок шаг за шагом через игру и творчество освоит основы программирования, научится проектировать и конструировать простейшие электронные устройства.

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

Книгу можно купить в нашем интернет-магазине.

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

Начинающим авторам, а также всем, кто желает узнать, как рождаются книги “из первых рук”, а может быть, мечтает написать собственную, рекомендуем к прочтению: https://habr.com/ru/post/681672/

 Осторожно! В статье содержится высокая концентрация полезных советов и интересных идей!

Сказки писательницы Наоми (настоящее имя Гертруда Ланда) основаны на древних еврейских притчах. Со всем уважением к первоисточнику автор написала добрые и мудрые сказки, в которых главные герои царь Соломон, жители Иерусалима и Востока, древние мудрецы и прекрасные принцессы и даже животные, характером и повадками чем-то похожие на людей. Мораль этих сказок будет понятна любому ребенку и, несомненно, пойдет на пользу, как и знакомство с древнейшей еврейской культурой.

Иллюстрации Екатерины Глейзер, вдохновлявшейся древним Иерусалимом, восточными базарами, экспонатами в музеях Израиля, — прекрасное дополнение к этим сказкам.

…Еврейская мудрость более общечеловеческая и универсальная, чем любая другая; и это не только из-за ее незапамятного возраста…но из-за мощной человечности, которая его насыщает, из-за его высокой оценки человека.
Максим Горький

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

Книгу можно купить в нашем интернет-магазине.

Маленькая Баба Яга никогда не ходила в школу, не выговаривала букву «р» и жила на болоте, где в подружках у неё были одни лягушки. И вот однажды под Новый год она решила стать Снегурочкой, чтобы исполнять самые заветные детские мечты.

Татьяна Кудрявцева постоянно публикуется в легендарной газете «Пионерская правда», её произведения для детей получили награды на литературном конкурсе им. Радия Погодина и международном конкурсе им. Сергея Михалкова.

… Маленькая Баба-Яга и Волк отправились в свои странствия по Стране Сбывшихся желаний. Ведь под Новый год все загадывают желания: и дети, и взрослые. В домах зажигаются ёлки, по городу разносится волшебный запах хвои, и новоесчастье — у ворот. Сказки эти были напечатаны в детской газете. Многие ребята потом просили меня написать продолжение. В продолжении Маленькая Баба-Яга стала Снегурочкой, а Волк пошёл к ней в собаки.

Но недавно, перечитывая эти сказки, я вдруг поняла: получилось всё наоборот! Первая часть, на самом деле, должна стать второй, а вторая — первой. Со сказками чего только не бывает, даже сказочная путаница, ведь они волшебные…

Я решила напечатать их все вместе. В память о своём учите

Книгу можно купить в нашем интернет-магазине.

Путеводитель знакомит читателя с Петербургом Достоевского: историческими районами города, где с 1837-го по 1881 годы жил писатель и где проживали герои почти всех его романов. Путеводитель состоит из 5 маршрутов, каждый их которых рассчитан на 2-3 часовую пешеходную экскурсию. Во втором издании учтена новейшая литература, приводится краткая библиография, добавлены описания новых памятных мест.

Путеводитель знакомит читателя с Петербургом Достоевского. Это не один, а два города: столица Российской империи между 1837 и 1881 годами, когда здесь жил писатель, город, удивительно хорошо сохранившийся (в отличие от диккенсовского Лондона, Парижа Гюго или Москвы Толстого), и пространство, созданное воображением писателя, где жили его герои.

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

Путеводитель состоит из 5 маршрутов, каждый из которых рассчитан на 2-3-часовую пешеходную экскурсию.

Об авторе

Лев Лурье – историк и журналист. В 1989 г. основал первую в новой России Петербургскую классическую гимназию (школа № 610), где и по сей день преподает историю. Четырежды лауреат конкурса «Золотое перо» и обладатель Гран-при «Журналист года» этого конкурса. В 2006-2009 гг. возглавлял Дирекцию документального вещания ТРК «Петербург – Пятый канал», вел авторские передачи «Культурный слой» и «Живая история». Прошлое, о котором в телепередачах, книгах и статьях повествует Лев Лурье, населяют не памятники, а живые люди. Их можно уважать или, напротив, осуждать, но к ним нельзя оставаться равнодушными.

Книгу можно купить в нашем интернет-магазине.

В издательстве “БХВ” вышло третье издание бестселлера Стивена Скиены: “Алгоритмы. Руководство по разработке. 3-е изд.“.

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

В третьем издании расширен набор рандомизированных алгоритмов, алгоритмов хеширования, аппроксимации и квантовых вычислений. Добавлено более 100 новых задач, даны ссылки к реализациям на C, C++ и Java.

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

Книгу можно купить в нашем интернет-магазине.

Предисловие…………………………………………………………………………………………… 17

Читателю…………………………………………………………………………………………………………………………………….. 17

Преподавателю………………………………………………………………………………………………………………………….. 19

Благодарности…………………………………………………………………………………………………………………………… 20

Ограничение ответственности………………………………………………………………………………………………….. 21

Часть I. Практическая разработка алгоритмов…………………. 23

Глава 1. Введение в разработку алгоритмов…………………………………………… 25

1.1. Оптимизация маршрута робота………………………………………………………………………………………… 26

1.2. Задача календарного планирования………………………………………………………………………………… 30

1.3. Обоснование правильности алгоритмов…………………………………………………………………………… 33

1.3.1. Задачи и свойства…………………………………………………………………………………………………….. 34

1.3.2. Представление алгоритмов……………………………………………………………………………………… 35

1.3.3. Демонстрация неправильности алгоритма……………………………………………………………. 35

Остановка для размышлений:  «Жадные» кинозвезды?……………………………………………………. 37

1.3.4. Индукция и рекурсия………………………………………………………………………………………………… 38

Остановка для размышлений:  Правильность инкрементных алгоритмов……………………… 39

1.4. Моделирование задачи………………………………………………………………………………………………………. 40

1.4.1. Комбинаторные объекты…………………………………………………………………………………………. 41

1.4.2. Рекурсивные объекты……………………………………………………………………………………………….. 42

1.5. Доказательство от противного………………………………………………………………………………………….. 44

1.6. Истории из жизни………………………………………………………………………………………………………………… 45

1.7. История из жизни. Моделирование проблемы ясновидения…………………………………………… 45

1.8. Прикидка……………………………………………………………………………………………………………………………… 49

Замечания к главе………………………………………………………………………………………………………………………. 50

1.9. Упражнения…………………………………………………………………………………………………………………………. 50

Поиск контрпримеров………………………………………………………………………………………………………… 50

Доказательство правильности………………………………………………………………………………………….. 51

Математическая индукция………………………………………………………………………………………………… 52

Приблизительные подсчеты………………………………………………………………………………………………. 52

Проекты по реализации……………………………………………………………………………………………………… 53

Задачи, предлагаемые на собеседовании………………………………………………………………………… 53

LeetCode………………………………………………………………………………………………………………………………. 54

HackerRank…………………………………………………………………………………………………………………………. 54

Задачи по программированию………………………………………………………………………………………….. 54

Глава 2. Анализ алгоритмов…………………………………………………………………… 55

2.1. Модель вычислений RAM………………………………………………………………………………………………….. 55

2.1.1. Анализ сложности наилучшего, наихудшего и среднего случая………………………… 56

2.2. Асимптотические («Big Oh») обозначения………………………………………………………………………… 58

Остановка для размышлений:  Возвращение к определениям…………………………………………. 61

Остановка для размышлений:  Квадраты…………………………………………………………………………… 61

2.3. Скорость роста и отношения доминирования………………………………………………………………….. 61

2.3.1. Отношения доминирования……………………………………………………………………………………… 63

2.4. Работа с асимптотическими обозначениями……………………………………………………………………. 64

2.4.1. Сложение функций……………………………………………………………………………………………………. 64

2.4.2. Умножение функций…………………………………………………………………………………………………. 64

Остановка для размышлений:  Транзитивность………………………………………………………………… 65

2.5. Оценка эффективности……………………………………………………………………………………………………….. 65

2.5.1. Сортировка методом выбора…………………………………………………………………………………… 65

Доказываем временную сложность Θ-большое…………………………………………………….. 66

2.5.2. Сортировка вставками……………………………………………………………………………………………… 67

Доказываем временную сложность Θ-большое…………………………………………………….. 68

2.5.3. Сравнение строк……………………………………………………………………………………………………….. 68

Доказываем время исполнения по Θ-большое………………………………………………………. 69

2.5.4. Умножение матриц…………………………………………………………………………………………………… 70

2.6. Суммирование…………………………………………………………………………………………………………………….. 71

Остановка для размышлений:  Формулы факториала………………………………………………………. 72

2.7. Логарифмы и их применение……………………………………………………………………………………………… 73

2.7.1. Логарифмы и двоичный поиск…………………………………………………………………………………. 73

2.7.2. Логарифмы и деревья……………………………………………………………………………………………….. 74

2.7.3. Логарифмы и биты……………………………………………………………………………………………………. 74

2.7.4. Логарифмы и умножение…………………………………………………………………………………………. 75

2.7.5. Быстрое возведение в степень…………………………………………………………………………………. 75

2.7.6. Логарифмы и сложение……………………………………………………………………………………………. 76

2.7.7. Логарифмы и система уголовного судопроизводства…………………………………………… 76

2.8. Свойства логарифмов…………………………………………………………………………………………………………. 77

Остановка для размышлений:  Важно ли деление точно пополам………………………………….. 79

2.9. История из жизни. Загадка пирамид…………………………………………………………………………………. 79

2.10. Анализ высшего уровня (*)………………………………………………………………………………………………. 82

2.10.1. Малораспространенные функции……………………………………………………………………….. 83

2.10.2. Пределы и отношения доминирования……………………………………………………………….. 84

Замечания к главе………………………………………………………………………………………………………………………. 85

2.11. Упражнения……………………………………………………………………………………………………………………….. 86

Анализ программ………………………………………………………………………………………………………………. 86

Упражнения по асимптотическим обозначениям………………………………………………………….. 87

Суммирование…………………………………………………………………………………………………………………… 92

Логарифмы………………………………………………………………………………………………………………………… 93

Задачи, предлагаемые на собеседовании………………………………………………………………………. 93

LeetCode…………………………………………………………………………………………………………………………….. 94

HackerRank……………………………………………………………………………………………………………………….. 94

Задачи по программированию………………………………………………………………………………………… 94

Глава 3. Структуры данных…………………………………………………………………… 95

3.1. Смежные и связные структуры данных…………………………………………………………………………….. 95

3.1.1. Массивы…………………………………………………………………………………………………………………….. 96

3.1.2. Указатели и связные структуры данных………………………………………………………………… 97

Поиск элемента в связном списке……………………………………………………………………………. 98

Вставка элемента в связный список……………………………………………………………………….. 99

Удаление элемента из связного списка………………………………………………………………….. 99

3.1.3. Сравнение……………………………………………………………………………………………………………….. 100

3.2. Стеки и очереди………………………………………………………………………………………………………………… 101

3.3. Словари……………………………………………………………………………………………………………………………… 102

Остановка для размышлений:  Сравнение реализаций словаря (I)……………………………….. 103

Остановка для размышлений:  Сравнение реализаций словаря (II)……………………………… 105

3.4. Двоичные деревья поиска………………………………………………………………………………………………… 108

3.4.1. Реализация двоичных деревьев…………………………………………………………………………….. 108

Поиск в дереве………………………………………………………………………………………………………… 109

Поиск наименьшего и наибольшего элементов дерева………………………………………. 110

Обход дерева………………………………………………………………………………………………………….. 110

Вставка элементов в дерево………………………………………………………………………………….. 111

Удаление элемента из дерева……………………………………………………………………………….. 112

3.4.2. Эффективность двоичных деревьев поиска………………………………………………………….. 112

3.4.3. Сбалансированные деревья поиска……………………………………………………………………… 113

Остановка для размышлений:  Использование сбалансированных деревьев поиска….. 114

3.5. Очереди с приоритетами………………………………………………………………………………………………….. 115

Остановка для размышлений:  Построение базовых очередей с приоритетами………….. 115

3.6. История из жизни. Триангуляция…………………………………………………………………………………….. 117

3.7. Хеширование…………………………………………………………………………………………………………………….. 121

3.7.1. Коллизии…………………………………………………………………………………………………………………. 121

3.7.2. Выявление дубликатов с помощью хеширования……………………………………………….. 123

3.7.3. Прочие приемы хеширования……………………………………………………………………………….. 125

3.7.4. Каноникализация……………………………………………………………………………………………………. 125

3.7.5. Уплотнение……………………………………………………………………………………………………………… 126

3.8. Специализированные структуры данных………………………………………………………………………. 126

3.9. История из жизни. Геном человека………………………………………………………………………………….. 127

Замечания к главе……………………………………………………………………………………………………………………. 131

3.10. Упражнения…………………………………………………………………………………………………………………….. 131

Стеки, очереди и списки…………………………………………………………………………………………………. 131

Элементарные структуры данных………………………………………………………………………………… 132

Деревья и другие словарные структуры………………………………………………………………………. 132

Применение древовидных структур……………………………………………………………………………… 134

Задачи по реализации……………………………………………………………………………………………………. 135

Задачи, предлагаемые на собеседовании……………………………………………………………………. 136

LeetCode………………………………………………………………………………………………………………………….. 137

HackerRank……………………………………………………………………………………………………………………… 137

Задачи по программированию……………………………………………………………………………………… 137

Глава 4. Сортировка и поиск……………………………………………………………….. 138

4.1. Применение сортировки…………………………………………………………………………………………………… 138

Остановка для размышлений:  Поиск пересечения множеств………………………………………… 141

Остановка для размышлений:  Использование хеша для решения задач……………………… 142

4.2. Практические аспекты сортировки…………………………………………………………………………………. 143

4.3. Пирамидальная сортировка…………………………………………………………………………………………….. 145

4.3.1. Пирамиды………………………………………………………………………………………………………………… 146

Остановка для размышлений:  Поиск в пирамиде…………………………………………………………… 148

4.3.2. Создание пирамиды……………………………………………………………………………………………….. 148

4.3.3. Наименьший элемент пирамиды…………………………………………………………………………… 149

4.3.4. Быстрый способ создания пирамиды (*)……………………………………………………………… 151

Остановка для размышлений:  Расположение элемента в пирамиде…………………………….. 153

4.3.5. Сортировка вставками…………………………………………………………………………………………… 154

4.4. История из жизни. Билет на самолет………………………………………………………………………………. 155

4.5. Сортировка слиянием. Метод «разделяй и властвуй»…………………………………………………… 158

4.6. Быстрая сортировка. Рандомизированная версия…………………………………………………………. 160

4.6.1. Интуиция: ожидаемое время исполнения алгоритма быстрой сортировки………. 163

4.6.2. Рандомизированные алгоритмы……………………………………………………………………………. 164

Остановка для размышлений:  Болты и гайки…………………………………………………………………. 166

4.6.3. Действительно ли алгоритм быстрой сортировки работает быстро?……………….. 167

4.7. Сортировка распределением. Метод блочной сортировки………………………………………….. 167

4.7.1. Нижние пределы для сортировки………………………………………………………………………….. 168

4.8. История из жизни. Скиена в суде…………………………………………………………………………………….. 170

Замечания к главе……………………………………………………………………………………………………………………. 172

4.9. Упражнения……………………………………………………………………………………………………………………….. 172

Применение сортировки: сортировка чисел………………………………………………………………….. 172

Применение сортировки: интервалы и множества………………………………………………………… 174

Пирамиды………………………………………………………………………………………………………………………….. 175

Быстрая сортировка…………………………………………………………………………………………………………. 175

Сортировка слиянием………………………………………………………………………………………………………. 176

Другие алгоритмы сортировки……………………………………………………………………………………….. 177

Нижние пределы………………………………………………………………………………………………………………. 178

Поиск…………………………………………………………………………………………………………………………………. 178

Задачи по реализации……………………………………………………………………………………………………… 178

Задачи, предлагаемые на собеседовании……………………………………………………………………… 179

LeetCode……………………………………………………………………………………………………………………………. 179

HackerRank……………………………………………………………………………………………………………………….. 180

Задачи по программированию……………………………………………………………………………………….. 180

Глава 5. Метод «разделяй и властвуй»…………………………………………………. 181

5.1. Двоичный поиск и связанные с ним алгоритмы……………………………………………………………… 181

5.1.1. Частота вхождения элемента………………………………………………………………………………… 182

5.1.2. Односторонний двоичный поиск…………………………………………………………………………… 183

5.1.3. Корни числа……………………………………………………………………………………………………………. 184

5.2. История из жизни. Поиск «бага в баге»…………………………………………………………………………… 184

5.3. Рекуррентные соотношения…………………………………………………………………………………………….. 186

5.3.1. Рекуррентные соотношения метода «разделяй и властвуй»………………………………. 187

5.4. Решение рекуррентных соотношений типа «разделяй и властвуй» (*)……………………….. 188

5.5. Быстрое умножение………………………………………………………………………………………………………….. 190

5.6. Поиск наибольшего поддиапазона и ближайшей пары………………………………………………… 192

5.7. Параллельные алгоритмы……………………………………………………………………………………………….. 194

5.7.1. Параллелизм на уровне данных……………………………………………………………………………. 194

5.7.2. Подводные камни параллелизма………………………………………………………………………….. 195

5.8. История из жизни. «Торопиться в никуда»……………………………………………………………………… 196

5.9. Свертка (*)…………………………………………………………………………………………………………………………. 197

5.9.1. Применение свертки……………………………………………………………………………………………….. 198

5.9.2. Быстрое полиномиальное умножение (**)…………………………………………………………… 199

Замечания к главе……………………………………………………………………………………………………………………. 202

5.10. Упражнения…………………………………………………………………………………………………………………….. 202

Двоичный поиск……………………………………………………………………………………………………………… 202

Алгоритмы типа «разделяй и властвуй»………………………………………………………………………. 203

Рекуррентные соотношения…………………………………………………………………………………………… 203

LeetCode………………………………………………………………………………………………………………………….. 204

HackerRank……………………………………………………………………………………………………………………… 204

Задачи по программированию……………………………………………………………………………………… 205

Глава 6. Хеширование и рандомизированные алгоритмы……………………. 206

Остановка для размышлений:  Город быстрой сортировки…………………………………………… 207

6.1. Обзор теории вероятностей……………………………………………………………………………………………… 207

6.1.1. Теория вероятностей………………………………………………………………………………………………. 207

6.1.2. Составные события и независимость……………………………………………………………………. 209

6.1.3. Условная вероятность……………………………………………………………………………………………. 210

6.1.4. Распределения вероятностей…………………………………………………………………………………. 211

6.1.5. Среднее и дисперсия………………………………………………………………………………………………. 212

6.1.6. Броски монет…………………………………………………………………………………………………………… 212

Остановка для размышлений:  Случайный обход графа……………………………………………….. 213

6.2. Задача мячиков и контейнеров………………………………………………………………………………………… 214

6.2.1. Задача о собирании купонов………………………………………………………………………………… 216

Остановка для размышлений:  Время покрытия для K_n………………………………………………….. 216

6.3. Почему хеширование является рандомизированным алгоритмом?…………………………….. 217

6.4. Фильтры Блума…………………………………………………………………………………………………………………. 218

6.5. Парадокс дня рождения и идеальное хеширование………………………………………………………. 220

6.6. Метод минимальных хеш-кодов……………………………………………………………………………………… 222

Остановка для размышлений:  Приблизительная оценка численности популяции……… 224

6.7. Эффективный поиск подстроки в строке…………………………………………………………………………. 225

6.8. Тестирование чисел на простоту…………………………………………………………………………………….. 226

6.9. История из жизни. Как я дал Кнуту свой средний инициал………………………………………….. 228

6.10. Откуда берутся случайные числа?……………………………………………………………………………….. 229

Замечания к главе……………………………………………………………………………………………………………………. 230

6.11. Упражнения…………………………………………………………………………………………………………………….. 230

Вероятность…………………………………………………………………………………………………………………….. 230

Хеширование…………………………………………………………………………………………………………………… 231

Рандомизированные алгоритмы……………………………………………………………………………………. 231

LeetCode………………………………………………………………………………………………………………………….. 232

HackerRank……………………………………………………………………………………………………………………… 232

Задачи по программированию……………………………………………………………………………………… 232

Глава 7. Обход графов………………………………………………………………………….. 233

7.1. Разновидности графов………………………………………………………………………………………………………. 234

7.1.1. Граф дружеских отношений………………………………………………………………………………….. 237

7.2. Структуры данных для графов………………………………………………………………………………………… 240

7.3. История из жизни. Жертва закона Мура………………………………………………………………………… 244

7.4. История из жизни. Создание графа…………………………………………………………………………………. 248

7.5. Обход графа………………………………………………………………………………………………………………………. 250

7.6. Обход в ширину………………………………………………………………………………………………………………… 251

7.6.1. Применение обхода………………………………………………………………………………………………… 254

7.6.2. Поиск путей…………………………………………………………………………………………………………….. 255

7.7. Применение обхода в ширину…………………………………………………………………………………………. 256

7.7.1. Компоненты связности…………………………………………………………………………………………… 256

7.7.2. Раскраска графов двумя цветами………………………………………………………………………….. 257

7.8. Обход в глубину………………………………………………………………………………………………………………… 259

7.9. Применение обхода в глубину…………………………………………………………………………………………. 263

7.9.1. Поиск циклов…………………………………………………………………………………………………………… 263

7.9.2. Шарниры графа………………………………………………………………………………………………………. 264

7.10. Обход в глубину ориентированных графов…………………………………………………………………. 268

7.10.1. Топологическая сортировка………………………………………………………………………………… 270

7.10.2. Сильно связные компоненты……………………………………………………………………………….. 272

Замечания к главе……………………………………………………………………………………………………………………. 274

7.11. Упражнения…………………………………………………………………………………………………………………….. 275

Алгоритмы для эмуляции графов………………………………………………………………………………….. 275

Обход графов………………………………………………………………………………………………………………….. 276

Приложения…………………………………………………………………………………………………………………….. 277

Разработка алгоритмов…………………………………………………………………………………………………. 278

Ориентированные графы……………………………………………………………………………………………….. 280

Шарниры графа……………………………………………………………………………………………………………… 281

Задачи, предлагаемые на собеседовании……………………………………………………………………. 282

LeetCode………………………………………………………………………………………………………………………….. 282

HackerRank…………………………………………………………………………………………………………………….. 282

Задачи по программированию……………………………………………………………………………………… 282

Глава 8. Алгоритмы для работы со взвешенными графами………………….. 283

8.1. Минимальные остовные деревья…………………………………………………………………………………….. 284

8.1.1. Алгоритм Прима……………………………………………………………………………………………………… 285

8.1.2. Алгоритм Крускала………………………………………………………………………………………………… 288

8.1.3. Структура данных непересекающихся множеств……………………………………………….. 290

8.1.4. Разновидности остовных деревьев……………………………………………………………………….. 293

8.2. История из жизни. И всё на свете — только сети……………………………………………………………. 295

8.3. Поиск кратчайшего пути………………………………………………………………………………………………….. 298

8.3.1. Алгоритм Дейкстры………………………………………………………………………………………………… 299

Остановка для размышлений:  Кратчайший путь с учетом веса вершин……………………… 302

8.3.2. Кратчайшие пути между всеми парами вершин………………………………………………….. 302

8.3.3. Транзитивное замыкание……………………………………………………………………………………….. 304

8.4. История из жизни. Печатаем с помощью номеронабирателя……………………………………….. 305

8.5. Потоки в сетях и паросочетание в двудольных графах………………………………………………… 309

8.5.1. Паросочетание в двудольном графе…………………………………………………………………….. 310

8.5.2. Вычисление потоков в сети……………………………………………………………………………………. 311

8.6. Произвольный минимальный разрез……………………………………………………………………………….. 315

8.7. Разрабатывайте не алгоритмы, а графы…………………………………………………………………………. 316

Остановка для размышлений:  Нить Ариадны………………………………………………………………… 317

Остановка для размышлений:  Упорядочивание последовательности…………………………. 317

Остановка для размышлений:  Размещение прямоугольников по корзинам…………………. 318

Остановка для размышлений:  Конфликт имен файлов………………………………………………….. 318

Остановка для размышлений:  Разделение текста…………………………………………………………… 318

Замечания к главе……………………………………………………………………………………………………………………. 319

8.8. Упражнения……………………………………………………………………………………………………………………….. 319

Алгоритмы для эмуляции графов……………………………………………………………………………………. 319

Минимальные остовные деревья…………………………………………………………………………………….. 319

Поиск-объединение………………………………………………………………………………………………………….. 321

Поиск кратчайшего пути…………………………………………………………………………………………………. 321

Потоки в сети и паросочетание………………………………………………………………………………………. 323

LeetCode……………………………………………………………………………………………………………………………. 323

HackerRank……………………………………………………………………………………………………………………….. 323

Задачи по программированию……………………………………………………………………………………….. 323

Глава 9. Комбинаторный поиск…………………………………………………………… 324

9.1. Перебор с возвратом…………………………………………………………………………………………………………. 324

9.2. Примеры перебора с возвратом………………………………………………………………………………………. 327

9.2.1. Генерирование всех подмножеств………………………………………………………………………… 327

9.2.2. Генерирование всех перестановок……………………………………………………………………….. 329

9.2.3. Генерирование всех путей в графе……………………………………………………………………….. 330

9.3. Отсечение вариантов поиска…………………………………………………………………………………………… 332

9.4. Судоку……………………………………………………………………………………………………………………………….. 333

9.5. История из жизни. Покрытие шахматной доски…………………………………………………………….. 339

9.6. Поиск методом «лучший-первый»…………………………………………………………………………………… 342

9.7. Эвристический алгоритм А*……………………………………………………………………………………………. 345

Замечания к главе……………………………………………………………………………………………………………………. 347

9.8. Упражнения……………………………………………………………………………………………………………………….. 347

Перестановки……………………………………………………………………………………………………………………. 347

Перебор с возвратом………………………………………………………………………………………………………… 348

Игры и головоломки…………………………………………………………………………………………………………. 349

Комбинаторная оптимизация………………………………………………………………………………………….. 350

Задачи, предлагаемые на собеседовании……………………………………………………………………… 350

LeetCode……………………………………………………………………………………………………………………………. 351

HackerRank……………………………………………………………………………………………………………………….. 351

Задачи по программированию……………………………………………………………………………………….. 351

Глава 10. Динамическое программирование………………………………………… 352

10.1. Кэширование и вычисления…………………………………………………………………………………………… 353

10.1.1. Генерирование чисел Фибоначчи методом рекурсии…………………………………….. 353

10.1.2. Генерирование чисел Фибоначчи посредством кэширования……………………….. 354

10.1.3. Генерирование чисел Фибоначчи посредством динамического программирования       356

10.1.4. Биномиальные коэффициенты…………………………………………………………………………… 358

10.2. Поиск приблизительно совпадающих строк………………………………………………………………… 360

10.2.1. Применение рекурсии для вычисления расстояния редактирования…………….. 361

10.2.2. Применение динамического программирования для вычисления
расстояния редактирования………………………………………………………………………………………….. 362

10.2.3. Восстановление пути…………………………………………………………………………………………. 364

10.2.4. Разновидности расстояния редактирования……………………………………………………. 366

10.3. Самая длинная возрастающая подпоследовательность…………………………………………….. 370

10.4. История из жизни. Сжатие текста для штрихкодов……………………………………………………… 372

10.5. Неупорядоченное разбиение или сумма подмножества…………………………………………….. 376

10.6. История из жизни: Баланс мощностей………………………………………………………………………….. 378

10.7. Задача упорядоченного разбиения………………………………………………………………………………. 381

10.8. Синтаксический разбор………………………………………………………………………………………………….. 384

Остановка для размышлений:  Экономичный синтаксический разбор……………………… 386

10.9. Ограничения динамического программирования: задача коммивояжера………………… 387

10.9.1. Вопрос правильности алгоритмов динамического программирования………… 388

10.9.2. Эффективность алгоритмов динамического программирования……………………. 389

10.10. История из жизни. Динамическое программирование и язык Prolog………………………… 390

Замечания к главе……………………………………………………………………………………………………………………. 393

10.11. Упражнения…………………………………………………………………………………………………………………… 394

Простые рекуррентные соотношения…………………………………………………………………………. 394

Расстояние редактирования………………………………………………………………………………………… 394

«Жадные» алгоритмы…………………………………………………………………………………………………… 396

Числовые задачи…………………………………………………………………………………………………………… 397

Задачи на графы…………………………………………………………………………………………………………… 399

Задачи по разработке………………………………………………………………………………………………….. 399

Задачи, предлагаемые на собеседовании………………………………………………………………….. 402

LeetCode………………………………………………………………………………………………………………………… 402

HackerRank…………………………………………………………………………………………………………………… 402

Задачи по программированию……………………………………………………………………………………. 402

Глава 11. NP-полнота…………………………………………………………………………… 403

11.1. Сведение задач……………………………………………………………………………………………………………….. 403

11.1.1. Ключевая идея…………………………………………………………………………………………………….. 404

11.1.2. Задачи разрешимости………………………………………………………………………………………… 405

11.2. Сведение для создания новых алгоритмов…………………………………………………………………… 406

11.2.1. Поиск ближайшей пары……………………………………………………………………………………… 406

11.2.2. Максимальная возрастающая подпоследовательность…………………………………. 407

11.2.3. Наименьшее общее кратное………………………………………………………………………………. 408

11.2.4. Выпуклая оболочка (*)………………………………………………………………………………………. 409

11.3. Простые примеры сведения сложных задач………………………………………………………………… 410

11.3.1. Гамильтонов цикл……………………………………………………………………………………………….. 410

11.3.2. Независимое множество и вершинное покрытие……………………………………………… 412

Остановка для размышлений:  Сложность общей задачи календарного планирования 413

11.3.3. Задача о клике…………………………………………………………………………………………………….. 415

11.4. Задача выполнимости булевых формул………………………………………………………………………. 416

11.4.1. Задача выполнимости в 3-конъюнктивной нормальной форме
(задача 3-SAT)…………………………………………………………………………………………………………………. 417

11.5. Нестандартные сведения задачи SAT…………………………………………………………………………… 419

11.5.1. Вершинное покрытие………………………………………………………………………………………….. 419

11.5.2. Целочисленное программирование…………………………………………………………………… 421

11.6. Искусство доказательства сложности………………………………………………………………………….. 423

11.7. История из жизни. Наперегонки со временем………………………………………………………………. 425

11.8. История из жизни. Полный провал………………………………………………………………………………… 427

11.9. Сравнение классов сложности P и NP…………………………………………………………………………… 430

11.9.1. Верификация решения и поиск решения…………………………………………………………… 430

11.9.2. Классы сложности P и NP………………………………………………………………………………….. 431

11.9.3. Почему задача выполнимости является сложной?…………………………………………. 432

11.9.4. NP-сложность по сравнению с NP-полнотой……………………………………………………. 432

Замечания к главе……………………………………………………………………………………………………………………. 433

11.10. Упражнения…………………………………………………………………………………………………………………… 434

Преобразования и выполнимость……………………………………………………………………………….. 434

Базовые сведения………………………………………………………………………………………………………….. 435

Нестандартные сведения…………………………………………………………………………………………….. 437

Алгоритмы для решения частных случаев задач……………………………………………………… 438

P или NP?……………………………………………………………………………………………………………………….. 439

LeetCode………………………………………………………………………………………………………………………… 439

HackerRank…………………………………………………………………………………………………………………… 439

Задачи по программированию……………………………………………………………………………………. 439

Глава 12. Решение сложных задач……………………………………………………….. 440

12.1. Аппроксимирующие алгоритмы……………………………………………………………………………………. 440

12.2. Аппроксимация вершинного покрытия…………………………………………………………………………. 441

Остановка для размышлений:  Вершинное покрытие в остатке…………………………………. 443

12.2.1. Рандомизированный эвристический алгоритм вершинного покрытия…………. 444

12.3. Задача коммивояжера в евклидовом пространстве…………………………………………………….. 445

12.3.1. Эвристический алгоритм Кристофидеса………………………………………………………….. 446

12.4. Когда среднее достаточно хорошее……………………………………………………………………………… 448

12.4.1. Задача максимальной k-SAT……………………………………………………………………………… 448

12.4.2. Максимальный бесконтурный подграф……………………………………………………………. 449

12.5. Задача о покрытии множества………………………………………………………………………………………. 449

12.6. Эвристические методы поиска………………………………………………………………………………………. 451

12.6.1. Произвольная выборка……………………………………………………………………………………….. 452

Остановка для размышлений:  Выбор пары…………………………………………………………………. 454

12.6.2. Локальный поиск………………………………………………………………………………………………… 455

12.6.3. Имитация отжига………………………………………………………………………………………………… 459

Реализация…………………………………………………………………………………………………………… 462

12.6.4. Применение метода имитации отжига………………………………………………………………. 463

Задача максимального разреза…………………………………………………………………………. 463

Независимое множество…………………………………………………………………………………….. 463

Размещение компонентов на печатной плате………………………………………………….. 464

12.7. История из жизни. Только это не радио………………………………………………………………………… 465

12.8. История из жизни. Отжиг массивов……………………………………………………………………………….. 468

12.9. Генетические алгоритмы и другие эвристические методы поиска…………………………….. 471

12.9.1. Генетические алгоритмы……………………………………………………………………………………. 471

12.10. Квантовые вычисления………………………………………………………………………………………………… 472

12.10.1. Свойства «квантовых» компьютеров………………………………………………………………. 473

12.10.2. Алгоритм Гровера для поиска в базе данных………………………………………………… 475

Решение задачи о выполнимости…………………………………………………………………….. 475

12.10.3. Более быстрое «преобразование Фурье»……………………………………………………….. 476

12.10.4. Алгоритм Шора для разложения целых чисел на множители……………………… 477

12.10.5. Перспективы квантовых вычислений……………………………………………………………… 479

Замечания к главе……………………………………………………………………………………………………………………. 481

12.11. Упражнения…………………………………………………………………………………………………………………… 482

Частные случаи сложных задач…………………………………………………………………………………. 482

Аппроксимирующие алгоритмы…………………………………………………………………………………. 482

Комбинаторная оптимизация……………………………………………………………………………………… 483

«Квантовые» вычисления…………………………………………………………………………………………….. 484

LeetCode………………………………………………………………………………………………………………………… 484

HackerRank…………………………………………………………………………………………………………………… 484

Задачи по программированию……………………………………………………………………………………. 484

Глава 13. Как разрабатывать алгоритмы?……………………………………………. 485

13.1. Список вопросов для разработчика алгоритмов…………………………………………………………. 486

13.2. Подготовка к собеседованию в технологических компаниях…………………………………….. 489

Часть II. Каталог алгоритмических задач…………………………. 493

Глава 14. Описание каталога……………………………………………………………….. 495

14.1. Предостережения……………………………………………………………………………………………………………. 496

Глава 15. Структуры данных……………………………………………………………….. 497

15.1. Словари……………………………………………………………………………………………………………………………. 497

15.2. Очереди с приоритетами………………………………………………………………………………………………… 503

15.3. Суффиксные деревья и массивы…………………………………………………………………………………….. 507

15.4. Графы………………………………………………………………………………………………………………………………. 511

15.5. Множества………………………………………………………………………………………………………………………. 515

15.6. Kd-деревья……………………………………………………………………………………………………………………….. 519

Глава 16. Численные задачи………………………………………………………………… 525

16.1. Решение системы линейных уравнений………………………………………………………………………… 526

16.2. Уменьшение ширины ленты матрицы…………………………………………………………………………… 530

16.3. Умножение матриц…………………………………………………………………………………………………………. 532

16.4. Определители и перманенты…………………………………………………………………………………………. 535

16.5. Условная и безусловная оптимизация………………………………………………………………………….. 538

16.6. Линейное программирование………………………………………………………………………………………… 542

16.7. Генерирование случайных чисел………………………………………………………………………………….. 547

16.8. Разложение на множители и проверка чисел на простоту…………………………………………. 552

16.9. Арифметика произвольной точности……………………………………………………………………………. 555

16.10. Задача о рюкзаке………………………………………………………………………………………………………….. 560

16.11. Дискретное преобразование Фурье…………………………………………………………………………….. 565

Глава 17. Комбинаторные задачи…………………………………………………………. 569

17.1. Сортировка……………………………………………………………………………………………………………………… 570

17.2. Поиск………………………………………………………………………………………………………………………………… 575

17.3. Поиск медианы и выбор элементов……………………………………………………………………………….. 579

17.4. Генерирование перестановок………………………………………………………………………………………… 582

17.5. Генерирование подмножеств…………………………………………………………………………………………. 587

17.6. Генерирование разбиений……………………………………………………………………………………………… 590

17.7. Генерирование графов……………………………………………………………………………………………………. 595

17.8. Календарные вычисления……………………………………………………………………………………………… 599

17.9. Календарное планирование………………………………………………………………………………………….. 601

17.10. Выполнимость………………………………………………………………………………………………………………. 605

Глава 18. Задачи на графах c полиномиальным временем исполнения… 609

18.1. Компоненты связности…………………………………………………………………………………………………… 610

18.2. Топологическая сортировка………………………………………………………………………………………….. 613

18.3. Минимальные остовные деревья…………………………………………………………………………………… 617

18.4. Поиск кратчайшего пути………………………………………………………………………………………………… 622

18.5. Транзитивное замыкание и транзитивная редукция……………………………………………………. 627

18.6. Паросочетание………………………………………………………………………………………………………………… 630

18.7. Задача поиска эйлерова цикла и задача китайского почтальона…………………………….. 634

18.8. Реберная и вершинная связность…………………………………………………………………………………… 637

18.9. Потоки в сети…………………………………………………………………………………………………………………… 641

18.10. Рисование графов………………………………………………………………………………………………………….. 644

18.11. Рисование деревьев………………………………………………………………………………………………………. 649

18.12. Планарность………………………………………………………………………………………………………………….. 652

Глава 19. NP-сложные задачи на графах………………………………………………. 655

19.1. Задача о клике………………………………………………………………………………………………………………… 655

19.2. Независимое множество…………………………………………………………………………………………………. 658

19.3. Вершинное покрытие……………………………………………………………………………………………………… 661

19.4. Задача коммивояжера……………………………………………………………………………………………………. 664

19.5. Гамильтонов цикл…………………………………………………………………………………………………………… 668

19.6. Разбиение графов……………………………………………………………………………………………………………. 672

19.7. Вершинная раскраска…………………………………………………………………………………………………….. 675

19.8. Реберная раскраска………………………………………………………………………………………………………… 679

19.9. Изоморфизм графов………………………………………………………………………………………………………… 680

19.10. Дерево Штейнера………………………………………………………………………………………………………….. 685

19.11. Разрывающее множество ребер или вершин……………………………………………………………… 689

Глава 20. Вычислительная геометрия…………………………………………………… 693

20.1. Элементарные задачи вычислительной геометрии…………………………………………………….. 693

20.2. Выпуклая оболочка………………………………………………………………………………………………………… 698

20.3. Триангуляция………………………………………………………………………………………………………………….. 702

20.4. Диаграммы Вороного…………………………………………………………………………………………………….. 706

20.5. Поиск ближайшей точки………………………………………………………………………………………………… 709

20.6. Поиск в области………………………………………………………………………………………………………………. 713

20.7. Местоположение точки………………………………………………………………………………………………….. 716

20.8. Выявление пересечений…………………………………………………………………………………………………. 720

20.9. Разложение по контейнерам………………………………………………………………………………………….. 724

20.10. Преобразование к срединной оси……………………………………………………………………………….. 728

20.11. Разбиение многоугольника на части…………………………………………………………………………… 731

20.12. Упрощение многоугольников………………………………………………………………………………………. 734

20.13. Выявление сходства фигур………………………………………………………………………………………….. 737

20.14. Планирование перемещений……………………………………………………………………………………….. 740

20.15. Конфигурации прямых…………………………………………………………………………………………………. 744

20.16. Сумма Минковского……………………………………………………………………………………………………… 747

Глава 21. Множества и строки……………………………………………………………… 750

21.1. Поиск покрытия множества……………………………………………………………………………………………. 750

21.2. Задача укладки множества……………………………………………………………………………………………. 755

21.3. Сравнение строк……………………………………………………………………………………………………………… 758

21.4. Нечеткое сравнение строк……………………………………………………………………………………………… 761

21.5. Сжатие текста…………………………………………………………………………………………………………………. 766

21.6. Криптография………………………………………………………………………………………………………………….. 770

21.7. Минимизация конечного автомата……………………………………………………………………………….. 776

21.8. Максимальная общая подстрока………………………………………………………………………………….. 779

21.9. Поиск минимальной общей надстроки…………………………………………………………………………. 782

Глава 22. Ресурсы………………………………………………………………………………… 786

22.1. Программные системы……………………………………………………………………………………………………. 786

22.1.1. Библиотека LEDA………………………………………………………………………………………………. 786

22.1.2. Библиотека CGAL………………………………………………………………………………………………. 787

22.1.3. Библиотека Boost……………………………………………………………………………………………….. 787

22.1.4. Библиотека Netlib……………………………………………………………………………………………….. 788

22.1.5. Коллекция алгоритмов ассоциации ACM………………………………………………………… 788

22.1.6. Сайты GitHub и SourceForge………………………………………………………………………………. 788

22.1.7. Система Stanford GraphBase……………………………………………………………………………… 789

22.1.8. Пакет Combinatorica…………………………………………………………………………………………… 789

22.1.9. Программы из книг……………………………………………………………………………………………… 789

Книга «Programming Challenges»……………………………………………………………………….. 790

Книга «Combinatorial Algorithms for Computers and Calculators»…………………… 790

Книга «Computational Geometry in C»………………………………………………………………. 790

Книга «Algorithms in C++»………………………………………………………………………………….. 790

Книга «Discrete Optimization Algorithms in Pascal»…………………………………………… 791

22.2. Источники данных………………………………………………………………………………………………………….. 791

22.3. Библиографические ресурсы…………………………………………………………………………………………. 791

22.4. Профессиональные консалтинговые услуги………………………………………………………………… 792

Глава 23. Список литературы………………………………………………………………. 793

Приложение. Описание электронного архива………………………………………. 838

Предметный указатель…………………………………………………………………………. 839