Алгоритмы: разработка и применение. Клейнберг Дж., Тардос Е.
Впервые на русском языке выходит одна из самых
авторитетных книг по разработке и использованию алгоритмов. Алгоритмы — это
основа программирования, определяющая, каким образом программное обеспечение
будет использовать структуры данных. Вы познакомитесь с базовыми аспектами
построения алгоритмов, основными понятиями и определениями, структурами данных,
затем перейдете к основным методам построения алгоритмов, неразрешимости и
методам решения неразрешимых задач, и, наконец, изучите рандомизацию при
проектировании алгоритмов. Самые сложные темы объясняются на четких и простых
примерах, поэтому книга может использоваться как для самостоятельного изучения
студентами, так и учеными-исследователями или профессионалами в области
компьютерных технологий, которые хотят получить представление о применении тех
или иных методов проектирования алгоритмов.
Алгоритмический анализ состоит из двух фундаментальных компонентов: выделения
математически чистого ядра задачи и выявления методов проектирования подходящего
алгоритма на основании структуры задачи. И чем лучше аналитик владеет полным
арсеналом возможных методов проектирования, тем быстрее он начинает распознавать
«чистые» формулировки, лежащие в основе запутанных задач реального мира.
Формат учебника: pdf
Размер для скачивания:
11,5 Мб
Скачать бесплатно или смотреть онлайн:
drive.google
Краткое содержание
Глава 1. Введение:
некоторые типичные задачи 27
Глава 2. Основы анализа алгоритмов 56
Глава 3. Графы 98
Глава 4. Жадные алгоритмы 137
Глава 5. Разделяй и властвуй 226
Глава 6. Динамическое программирование 266
Глава 7. Нахождение потока в сети 347
Глава 8. Л/Р-полнота и вычислительная неразрешимость 458
Глава 9. PSPACE: класс задач за пределами NP 534
Глава 10. Расширение пределов разрешимости 555
Глава 11. Аппроксимирующие алгоритмы 599
Глава 12. Локальный поиск 659
Глава 13. Рандомизированные алгоритмы 704
Алгоритмические идеи вездесущи, а широта их применения наглядно проявляется в
примерах как из области информатики, так и за ее пределами. Некоторые серьезные
изменения стандартов маршрутизации в Интернете произошли вследствие обсуждения
недостатков одного алгоритма кратчайшего пути и относительных преимуществ
другого. Базовые понятия, используемые биологами для выражения сходства между
генами и геномами, имеют алгоритмические определения. Озабоченность,
высказываемая экономистами в контексте практической приемлемости комбинаторных
аукционов, отчасти обусловлена тем фактом, что особыми случаями таких аукционов
являются вычислительно трудноразрешимые задачи поиска. При этом алгоритмические
концепции не ограничиваются хорошо известными, устоявшимися задачами; эти идеи
регулярно проявляются в совершенно новых проблемах, возникающих в самых разных
областях. Ученый из Yahoo!, однажды рассказавший нам за обедом о системе
поставки рекламы пользователям, описывал совокупность задач, которые, по сути,
можно было смоделировать как задачу нахождения потока в сети. То же произошло в
общении с нашим бывшим студентом (ныне консультантом по вопросам управления,
занимающимся правилами подбора персонала для крупных больниц), с которым мы
встретились во время поездки в Нью-Йорк.