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

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

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




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

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

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

Купить .





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