Алгоритмы

Алгоритмы

Введение в разработку

и анализ

Алгоритмы

Введение в разработку и анализ

Introduction to The Design & Analysis of Algorithms

Anany Levitin

Villanova University

▼ ▼

ADDISO N -WESLEY

Boston San Francisco New York London Toronto Sydney Tokyo Singapore Madrid

Mexico City Munich Paris Cape Town Hong Kong Montreal

Алгоритмы

Введение в разработку и анализ

Ананий Левитин

Университет Вилланова

ББК 32.973.26-018.2.75 Л36 УДК 681.3.07

Издательский дом “Вильямс”

Зав. редакцией С.Я. Тригуб

Перевод с английского и редакция канд. физ.-мат.наук С.Г. Тригуб, канд.техн.наук И.В. Красикова

По общим вопросам обращайтесь в Издательский дом “Вильямс” по адресу: info@williamspublishing.com, http://www.williamspublishing.com 115419, Москва, а/я 783; 03150, Киев, а/я 152

Левитин, Ананий В.

Л36 Алгоритмы: введение в разработку и анализ. : Пер. с англ. — М. : Издательский дом “Вильямс”, 2006. — 576 с. : ил. — Парал. тит. англ.

ISBN 5-8459-0987-2 (рус.)

Эта книга, автором которой является преподаватель информатики, пред­ставляет собой один из лучших учебников, посвященных алгоритмам. Делая основной упор на понимание идей, а не на механическое рассмотрение работы того или иного алгоритма, автор излагает принципы разработки алгоритмов так, что они могут быть применены как универсальный инструментарий для широкого диапазона задач, а не только для разработки алгоритмов.

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

ББК 32.973.26-018.2.75

Все названия программных продуктов являются зарегистрированными торговыми марками соответствую­щих фирм.

Никакая часть настоящего издания ни в каких целях не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами, будь то электронные или механические, включая фотокопирова­ние и запись на магнитный носитель, если на это нет письменного разрешения издательства Addison-Wesley Publishing Company, Inc.

Authorized translation from the English language edition published by Addison-Wesley. Copyright © 2003.

All rights reserved. No part of this book may be reproduced or transmined in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage retrieval system, without permission from the publisher.

Russian language edition is published by Williams Publishing House according to the Agreement with R&I Enterprises International. Copyright © 2006.

ISBN 5-8459-0987-2 (pyc.) ISBN 0-201-74395-7 (англ.)

© Издательский дом “Вильямс”, 2006 © Addison-Wesley. 2003

Оглавление

Anany Levitin 2

Алгоритмы 3

Ананий Левитин 3

Оглавление 5

Содержание 5

Содержание

Предисловие

Глава 1. Введение

1. Понятие алгоритма Упражнения 1.1

2. Основы решения алгоритмической задачи Понимание задачи

Определение возможностей вычислительного устройства Выбор между точным или приближенным методом решения задачи

Выбор подходящих структур данных Методы проектирования алгоритмов Методы представления алгоритмов Оценка корректности алгоритма Анализ алгоритма Кодирование алгоритма Упражнения 1.2

3. Важные типы задач Сортировка Поиск

Обработка строк Задачи из теории графов Комбинаторные задачи Геометрические задачи Численные задачи Упражнения 1.3

4. Базовые структуры данных Линейные структуры данных Графы

Деревья

Множества и словари

	Упражнения 1.4	70
	Резюме	71
Глава 2. Основы анализа эффективности алгоритмов			73
2.1	Основы анализа	75
	Оценка размера входных данных	75
	Единицы измерения времени выполнения алгоритма	76
	Порядок роста	78
	Эффективность алгоритма в разных случаях	80
	Повторение пройденного	84
	Упражнения 2.1	85
2.2	Асимптотические обозначения и основные классы
	эффективности	87
	Нестрогое введение	88
	О-обозначение	88
	П-обозначение	89
	©-обозначение	90
	Полезные свойства сделанных асимптотических обозначений Использование пределов для сравнения порядка роста двух	91
	функций	92
	Основные классы эффективности	94
	Упражнения 2.2	96
2.3	Математический анализ нерекурсивных алгоритмов	98
	Упражнения 2.3	105
2.4	Математический анализ рекурсивных алгоритмов	107
	Упражнения 2.4	116
2.5	Пример: числа Фибоначчи Явная формула для определения n-го элемента	119
	последовательности чисел Фибоначчи	120
	Алгоритмы вычисления чисел Фибоначчи	122
	Упражнения 2.5	125
2.6	Эмпирический анализ алгоритмов	127
	Упражнения 2.6	133
	Визуализация алгоритмов	135
	Резюме	139
Глава 3. Метод грубой силы			141
3.1	Сортировка выбором и пузырьковая сортировка	142
	Сортировка выбором	143
	Пузырьковая сортировка	144
	Упражнения 3.1	146

2. Последовательный поиск и поиск подстрок методом грубой

Anany Levitin 2

Алгоритмы 3

Ананий Левитин 3

Оглавление 5

Содержание 5