Алгоритмы - построение и анализ (1021735), страница 4
Текст из файла (страница 4)
Приближенные алгоритмы Оценка качества приближенных алгоритмов Краткое содержание главы 35.1 Задача о вершинном покрытии 1078 1079 1080 1083 1085 1087 1088 1091 1091 1092 1093 1096 1100 1100 1101 1102 1103 1105 1106 1106 1108 1110 1117 1118 1119 1122 1126 1127 1128 1131 1133 1138 1140 1144 1145 1149 1151 1151 1153 1154 Содержание 27 1157 1157 1158 1161 1163 1164 1166 1166 1169 1170 1170 1172 1175 1176 1176 1178 1182 1182 1186 1189 1190 Упражнения 35.2 Задача о коммивояжере 35.2.1 Задача о коммивояжере с неравенством треугольника 35.2.2 Общая задача о коммивояжере Упражнения 35.3 Задача о покрытии множества Жадный приближенный алгоритм Анализ Упражнения 35.4 Рандомизация и линейное программирование Рандомизированный приближенный алгоритм для задачи о МАХ-3-СИР выполнимости Аппроксимация взвешенного вершинного покрытия с помощью линейного программирования Упражнения 35.5 Задача о сумме подмножества Точный алгоритм с экспоненциальным временем работы Схема аппроксимации с полностью полиномиальным временем работы Упражнения Задачи Заключительные замечания Часть УП1.
Приложения: математические основы Введение Приложение А. Ряды А.1 Суммы и их свойства Линейность Арифметическая прогрессия Суммы квадратов и кубов Геометрическая прогрессия Гармонический ряд Интегрирование и дифференцирование рядов Суммы разностей Произведения Упражнения А.2 Оценки сумм Математическая индукция Почленное сравнение Разбиение рядов 1191 1192 1192 1193 1193 1193 1194 1194 1194 1195 1195 1195 1196 1196 1198 28 Содержание Приближение интегралами Упражнения Задачи Заключительные замечания Приложение Б.Множества и прочие художества Б.1 Множества Упражнения Б.2 Отношения Упражнения Б.З Функции Упражнения Б.4 Графы Упражнения Б.5 Деревья Б.5.1 Свободные деревья Б.5.2 Деревья с корнем и упорядоченные деревья Б.5.3 Бинарные и позиционные деревья Упражнения Задачи Заключительные замечания Приложение В.
Комбинаторика и теория вероятности В.1 Основы комбинаторики Правила суммы и произведения Строки Перестановки Сочетания Биномиальные коэффициенты Оценки биномиальных коэффициентов Упражнения В.2 Вероятность Аксиомы вероятности Дискретные распределения вероятностей Непрерывное равномерное распределение вероятности Условная вероятность и независимость Теорема Байеса Упражнения В.З Дискретные случайные величины Математическое ожидание случайной величины Дисперсия и стандартное отклонение Упражнения 1199 1201 1201 1201 1202 1202 1207 1207 1209 1210 1212 1213 1217 1218 1218 1220 1221 1223 1224 1225 1226 1226 1227 1227 1227 1228 1229 1229 1230 1232 1232 1233 1234 1234 1236 1237 1238 1239 1242 1243 Содержание 29 В.4 Геометрическое и биномиальное распределения Геометрическое распределение Биномиальное распределение Упражнения * В.5 Хвосты биномиального распределения Упражнения Задачи Заключительные замечания Библиография Предметный указатель 1243 1244 1245 1248 1249 1254 1255 1256 !257 1277 Введение Эта книга служит исчерпывающим вводным курсом по современным компьютерным алгоритмам.
В ней представлено большое количество конкретных алгоритмов, которые описываются достаточно глубоко, однако таким образом, чтобы их разработка и анализ были доступны читателям с любым уровнем подготовки. Авторы старались давать простые объяснения без ущерба для глубины изложения и математической строгости. В каждой главе представлен определенный алгоритм, описывается метод его разработки, область применения или другие связанные с ним вопросы. Алгоритмы описываются как на обычном человеческом языке, так и в виде псевдокода, разработанного так, что он будет понятен для всех, у кого есть хотя бы минимальный опыт программирования.
В книге представлено более 230 рисунков, иллюстрирующих работу алгоритмов. Поскольку один из критериев разработки алгоритмов — их эффективность, описание всех алгоритмов включает в себя тщательный анализ времени их работы. Данный учебник предназначен в первую очередь для студентов и аспирантов, изучающих тот или иной курс по алгоритмам и структурам данных. Он также будет полезен для технических специалистов, желающих повысить свой уровень в этой области, поскольку описание процесса разработки алгоритмов сопровождается изложением технических вопросов.
В настоящем втором издании в книгу внесено множество изменений на всех уровнях, — от добавления целых новых глав до пересмотра отдельных предложений. Преподавателю Эта книга задумана так, что разнообразие описываемых в ней тем сочетается с полнотой изложения. Она может стать полезной при чтении разнообразных курсов, — от курса по структурам данных для студентов до курса по алгоритмам для аспирантов. Поскольку в книге намного больше материала, чем требуется Введение для обычного курса, рассчитанного на один семестр, можно выбрать только тот материал, который лучше всего соответствует курсу, который вы собираетесь преподавать.
Курсы удобно разрабатывать на основе отдельных глав. Книга написана так, что ее главы сравнительно независимы одна от другой. В каждой главе материал излагается по мере увеличения его сложности и разбит на разделы. В студенческом курсе можно использовать только более легкие разделы, а в аспирантском — всю главу в полном объеме. В книгу вошли более 920 упражнений и свыше 140 задач. Упражнения даются в конце каждого раздела, а задачи — в конце каждой главы.
Упражнения представлены в виде кратких вопросов для проверки степени освоения материала. Некоторые из них простые и предназначены для самоконтроля, в то время как другие — посложнее и могут быть рекомендованы в качестве домашних заданий. Решение задач требует больших усилий, и с их помощью часто вводится новый материал. Обычно задачи сформулированы так, что в них содержатся наводящие вопросы, помогающие найти верное решение. Разделы и упражнения, которые больше подходят для аспирантов, чем для студентов, обозначены звездочкой (*).
Они не обязательно более сложные, чем те, возле которых звездочка отсутствует; просто для их понимания может понадобиться владение более сложным математическим аппаратом. Для того чтобы справиться с упражнениями со звездочкой, может понадобиться более основательная подготовка или неординарная сообразительность. Студенту Надеемся, что этот учебник станет хорошим введением в теорию алгоритмов. Авторы попытались изложить каждый алгоритм в доступной и увлекательной форме.
Чтобы облегчить освоение незнакомых или сложных алгоритмов, каждый из них описывается поэтапно. В книге также приводится подробное обьяснение математических вопросов, необходимых для того, чтобы понять проводимый анализ алгоритмов. Для тех читателей, которые уже в некоторой мере знакомы с какой-то темой, материал глав организован таким образом, чтобы эти читатели могли опустить вводные разделы и перейти непосредственно к более сложному материалу. Книга получилась довольно большой, поэтому не исключено, что в курсе лекций будет представлена лишь часть изложенного в ней материала.
Однако авторы попытались сделать ее такой, чтобы она стала полезной как сейчас в качестве учебника, способствующего усвоению курса лекций, так и позже, в профессиональной деятельности, в качестве настольного справочного пособия для математиков или инженеров. Введение Ниже перечислены необходимые предпосылки, позволяющие освоить материал этой книги. ° Читатель должен обладать некоторым опытом в программировании. В частности, он должен иметь представление о рекурсивных процедурах и простых структурах данных, таких как массивы и связанные списки. ° Читатель должен обладать определенными навыками доказательства теорем методом математической индукции.
Для понимания некоторых вопросов, изложенных в этой книге, потребуется умение выполнять некоторые простые математические преобразования. Помимо этого, в частях 1 и 'Ч1П этой книги рассказывается обо всех используемых математических методах. Профессионалу Широкий круг вопросов, которые излагаются в этой книге, позволяет говорить о том, что она станет прекрасным учебником по теории алгоритмов. Поскольку каждая глава является относительно самостоятельной, читатель сможет сосредоточить внимание на вопросах, интересующих его больше других. Основная часть обсуждаемых здесь алгоритмов обладает большой практической ценностью. Поэтому не обойдены вниманием особенности реализации алгоритмов и другие инженерные вопросы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
