Совершенный алгоритм, Основы, Рафгарден Т., 2019

Совершенный алгоритм, Основы, Рафгарден Т., 2019.

  Алгоритмы — это сердце и душа computer science. Без них не обойтись, они есть везде — от сетевой маршрутизации и расчетов по геномике до криптографии и машинного обучения. «Совершенный алгоритм» превратит вас в настоящего профи, который будет ставить задачи и мастерски их решать как в жизни, так и на собеседовании при приеме на работу в любую IT-компанию. В этой книге Тим Рафгарден — гуру алгоритмов — расскажет об асимптотическом анализе, нотации большое-О, алгоритмах «разделяй и властвуй», рандомизации, сортировки и отбора. Книга «Совершенный алгоритм» адресована тем. у кого уже есть опыт программирования. Вы перейдете на новый уровень, чтобы увидеть общую картину, разобраться в низкоуровневых концепциях и математических нюансах.




Алгоритм начальной школы.
Точно определив вычислительную задачу, мы опишем алгоритм, который ее решает. — тот самый алгоритм, который вы изучали в начальной школе. Мы оценим производительность этого алгоритма числом «примитивных операций», которые он выполняет, в виде функции от количества знаков п в каждом входном числе. Пока же давайте представим примитивную операцию как любую из следующих: (i) сложение двух одноразрядных (n = 1) чисел: (ii) умножение двух одноразрядных чисел или (iii) добавление нуля к началу или концу числа.

Чтобы освежить вашу память, рассмотрим конкретный пример умножения х = 5678 на y = 1234 (здесь п = 4) в столбик, см. рис. 1.1. Сначала алгоритм вычисляет «частичное произведение» первого числа и последней цифры второго числа: 5678x4 = 22712. Вычисление этого частичного произведения сводится к умножению каждой цифры первого числа на 4. записи младшего разряда результата, запоминанию («переносу» на следующий этап) старшего разряда и добавлению этих «переносов» (если они есть) на следующем умножении. При вычислении следующего частичного произведения (5678 х 3 = 17 034) мы делаем то же самое, сдвигая результат на один знак влево (фактически добавляя «0» в конце). И так далее для оставшихся двух частичных произведений. Заключительный шаг состоит в том. чтобы сложить все частичные произведения.

Тогда в третьем классе вы. вероятно, согласились, что этот алгоритм является правильным, имея в виду, что неважно, с каких чисел х и у начинать. При условии, что все промежуточные вычисления выполняются правильно, алгоритм в конечном итоге заканчивается получением результата произведения х х y двух исходных чисел.

Содержание.
Предисловие.
Глава 1. Введение.
Глава 2. Асимптотические обозначения.
Глава 3. Алгоритмы «разделяй и властвуй».
Глава 4. Основной метод.
Глава 5. Алгоритм Quicksort.
Глава 6. Линейный выбор.
Приложения.

Купить .





Теги: учебник по программированию :: программирование :: Рафгарден :: алгоритм