Читать онлайн «Алгоритмы. Вводный курс»

вводный курс Thomas H. Cormen The WIT Press The MIT Press Cambridge, Massachusetts London, England вводный курс томас х. кормен виль "Вильяме" Москва • Санкт-Петербург • Киев 2014 ББК 32. 973. 26-018. 2. 75 К66 УДК 681. 3. 07 Издательский дом "Вильяме" Зав. редакцией С. Н. Тригуб Перевод с английского и редакция канд. техн. наук И. В. К66 Алгоритмы: вводный курс. : Пер. с англ. — М. : ООО "И. Д. Вильяме", 2014. — 208 с. : ил. — Парал. тит. англ. ISBN 978-5-8459-1868-0 (рус. ) ББК 32. 973. 26-018. 2. 75 Все названия программных продуктов являются зарегистрированными торговыми марками соответствующих фирм. Никакая часть настоящего издания ни в каких целях не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами, будь то электронные или механические, включая фотокопирование и запись на магнитный носитель, если на это нет письменного разрешения издательства MIT Press. Authorized translation from the English language edition published by MIT Press, Copyright © 2013 by Massachusetts Institute of Technology. All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher. Russian language edition published by Williams Publishing House according to the Agreement with R&I Enterprises International, Copyright © 2014 Научно-популярное издание Томас X. Кормен Алгоритмы: вводный курс Литературный редактор Л. Н. Красножон Верстка М. А. Удалое Художественный редактор Е. П. Дынник Корректор Л. А. Гордиенко Подписано в печать 11. 11. 2013. Формат 70x100/16. Гарнитура Times. Печать офсетная. Усл. печ. л. 16,7. Уч. -изд. л. 18,8. Тираж 1500 экз. Заказ № 3919. Первая Академическая типография "Наука" 199034, Санкт-Петербург, 9-я линия, 12/28 ООО "И. Д. Вильяме", 127055, г. Москва, ул. Лесная, д. 43, стр. 1 ISBN 978-5-8459-1868-0 (рус. ) ISBN 978-0-262-51880-2 (англ. ) © Издательский дом "Вильяме", 2014 О Massachusetts Institute of Technology, 2013 Оглавление Предисловие 10 Глава 1 Что такое алгоритмы и зачем они нужны 75 Глава 2 Описание и оценка компьютерных алгоритмов 23 Глава 3 Алгоритмы сортировки и поиска 37 Глава 4 Нижняя граница времени сортировки и как ее превзойти 69 Глава 5 Ориентированные ациклические графы 79 Глава 6 Кратчайшие пути 97 Глава 7 Алгоритмы на строках 119 Глава 8 Основы криптографии 139 Глава 9 Сжатие данных 157 Глава 10 Трудная? Задача... 175 Библиография 205 Предметный указатель 207 Содержание Предисловие 10 Чему научит вас эта книга 11 Что следует знать для понимания материала книги 11 Если вы нашли ошибку 12 Благодарности 12 Глава 1 Что такое алгоритмы и зачем они нужны 15 Корректность 16 Использование ресурсов 17 Компьютерные алгоритмы для людей, не связанных с компьютерами 19 Компьютерные алгоритмы для компьютерщиков 19 Дальнейшее чтение 21 Глава 2 Описание и оценка компьютерных алгоритмов 23 Описание компьютерных алгоритмов 23 Описание времени работы алгоритма 29 Инварианты циклов 32 Рекурсия 34 Дальнейшее чтение 36 Глава 3 Алгоритмы сортировки и поиска 37 Бинарный поиск 39 Сортировка выбором 43 Сортировка вставкой 46 Сортировка слиянием 50 Быстрая сортировка 58 Резюме 65 Дальнейшее чтение 67 Содержание Глава 4 Нижняя граница времени сортировки и как ее превзойти Правила сортировки 69 Нижняя граница сортировки сравнением 70 Сортировка подсчетом 71 Поразрядная сортировка 77 Дальнейшее чтение 78 Глава 5 Ориентированные ациклические графы 79 Ориентированные ациклические графы 82 Топологическая сортировка 82 Представление ориентированных графов 85 Время работы топологической сортировки 87 Критический путь в диаграмме PERT 87 Кратчайший путь в ориентированном ациклическом графе 92 Дальнейшее чтение 96 Глава 6 Кратчайшие пути 97 Алгоритм Дейкстры 98 Алгоритм Беллмана-Форда 106 Алгоритм Фл ойда-Уоршелл а 110 Дальнейшее чтение 117 Глава 7 Алгоритмы на строках 119 Наидлиннейшая общая подпоследовательность 119 Преобразование одной строки в другую 124 Поиск подстрок 131 Дальнейшее чтение 137 Глава 8 Основы криптографии 139 Простые подстановочные шифры 140 Криптография с симметричным ключом 141 Криптография с открытым ключом 144 8 Содержание Криптосистема RSA 146 Гибридные криптосистемы Вычисление случайных чисел Дальнейшее чтение 155 Глава 9 Сжатие данных 157 Коды Хаффмана 158 Факсимильные аппараты 164 LZW-сжатие 165 Дальнейшее чтение 174 Глава 10 Трудная?