Erhalten Sie Zugang zu diesem und mehr als 300000 Büchern ab EUR 5,99 monatlich.
- Herausgeber: Питер
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Russisch
Алгоритмы — это сердце и душа computer science. Без них не обойтись, они есть везде — от сетевой маршрутизации и расчетов по геномике до криптографии и машинного обучения. «Совершенный алгоритм» превратит вас в настоящего профи, который будет ставить задачи и мастерски их решать как в жизни, так и на собеседовании при приеме на работу в любую IT-компанию. Если вы уже достаточно прокачались в асимптотическом анализе, жадных алгоритмах и динамическом программировании, самое время рассмотреть понятие NP-трудности, которое часто вызывает неподдельный страх. Тим Рафгарден покажет, как распознать NP-трудную задачу, расскажет, как избежать решения с нуля, и поможет найти эффективные пути решения. Познакомиться с дополнительными материалами и видеороликами автора (на английском языке) можно на сайте www.algorithmsilluminated.org.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 331
Veröffentlichungsjahr: 2024
Das E-Book (TTS) können Sie hören im Abo „Legimi Premium” in Legimi-Apps auf:
Ähnliche
Переводчик А. Логунов
Тим Рафгарден
Совершенный алгоритм. Алгоритмы для NP-трудных задач. — СПб.: Питер, 2024.
ISBN 978-5-4461-1799-4
© ООО Издательство "Питер", 2024
Оглавление
Предисловие
Перед вами четвертая из серии книг, написанных на базе проводимых мною с 2012 года онлайн-курсов по алгоритмам. Эти курсы, в свою очередь, появились благодаря лекциям для студентов, которые я читал в Стэнфордском университете в течение многих лет. Четвертая часть исходит из того, что читатель уже немного знаком с асимптотическим анализом и О-большим, поиском в графах и алгоритмами кратчайшего пути, жадными алгоритмами и динамическим программированием (все эти темы освещены в предыдущих частях).
О чем эти книги
Четвертая часть серии «Совершенный алгоритм» посвящена NP-трудным1 задачам и работе с ними.
Алгоритмические инструменты для решения NP-трудных задач. Многие реальные задачи являются NP-трудными и кажутся не поддающимися решению теми типами всегда правильных и всегда быстрых алгоритмов, которые были представлены в предыдущих частях. При встрече с NP-трудной задачей придется пойти на компромисс между правильностью и скоростью. Вы увидите старые методы (жадные алгоритмы) и новые (локальный поиск) для разработки быстрых «приближенно правильных» эвристических алгоритмов для работы с приложениями по задачам планирования, максимизации влияния в социальных сетях и задаче коммивояжера. Мы также рассмотрим старые методы (динамическое программирование) и новые (решатели задач смешанного целочисленного программирования и задач выполнимости булевых формул) для улучшения работы алгоритмов исчерпывающего поиска. Приложения будут включать задачу коммивояжера, поиск сигнальных путей в биологических сетях и переупаковку телевизионных станций на аукционе радиочастотного спектра в США.
Распознавание NP-трудных задач. Эта книга научит вас быстро распознавать NP-трудную задачу и не тратить время на разработку идеального алгоритма для ее решения. Вы познакомитесь с многочисленными широко известными и базовыми NP-трудными задачами, начиная от задач выполнимости и раскраски графов и заканчивая задачей о гамильтоновом пути. Вы попробуете доказать NP-трудность с помощью редукций.
Для более подробного ознакомления с содержанием книги загляните в разделы «Выводы», где выделены наиболее важные моменты. «Полевое руководство по разработке алгоритмов» на с. 283 даст представление о том, как темы этой книги вписываются в общую алгоритмическую картину.
Разделы книги, помеченные звездочками, — самые продвинутые. Читатели, испытывающие нехватку времени, могут пропустить их при первом чтении без потери непрерывности.
Темы, затронутые в первых трех частях.Первая часть серии «Совершенный алгоритм» охватывает асимптотические обозначения (О-большое и его близких родственников), алгоритмы «разделяй и властвуй» и основной метод, рандомизированные алгоритмы, быструю сортировку и ее анализ, а также линейно-временные алгоритмы отбора. Во второй части рассмотрены различные структуры данных (кучи, сбалансированные деревья поиска, хеш-таблицы, фильтры Блума), графовые примитивы (поиск сначала в ширину и сначала в глубину, связность, кратчайшие пути) и области их применения (от дедупликации до анализа социальных сетей). Третья часть посвящена жадным алгоритмам (задаче планирования, определению минимального остовного дерева графа, кластеризации, кодам Хаффмана), а также динамическому программированию (задаче о рюкзаке, выравниванию рядов, поиску кратчайших путей, построению деревьев оптимального поиска).
Навыки, которые вы приобретете
Освоение алгоритмов требует времени и усилий. Ради чего все это?
Возможность стать более эффективным программистом. Вы изучите несколько невероятно быстрых подпрограмм для обработки данных и несколько полезных структур для организации данных, которые можете применять непосредственно в ваших собственных программах. Реализация и применение этих алгоритмов расширят и улучшат ваши навыки программирования. Вы также узнаете основные приемы разработки алгоритмов, которые актуальны для решения разнообразных задач в широких областях, получите инструменты для прогнозирования производительности этих алгоритмов. Такие шаблоны могут быть вам полезны для разработки новых алгоритмов решения задач, которые возникают в вашей собственной работе.
Развитие аналитических способностей. Алгоритмические описания, мыслительная работа над алгоритмами дают большой опыт. Посредством математического анализа вы получите углубленное понимание конкретных алгоритмов и структур данных, описанных в этой книге. Вы приобретете навыки работы с несколькими математическими методами, которые широко применяются для анализа алгоритмов.
Алгоритмическое мышление. Научившись разбираться в алгоритмах, трудно не заметить, что они окружают нас повсюду, едете ли вы в лифте, наблюдаете ли за стаей птиц, управляете ли вы своим инвестиционным портфелем или даже наблюдаете за тем, как учится ребенок. Алгоритмическое мышление становится все более полезным и распространенным в дисциплинах, не связанных с информатикой, включая биологию, статистику и экономику.
Знакомство с величайшими достижениями информатики. Изучение алгоритмов напоминает просмотр эффектного клипа с многочисленными суперхитами минувших шестидесяти лет развития информатики. Вы больше не будете чувствовать себя чужим на фуршете для специалистов в области computer science, когда кто-то отпустит шутку по поводу алгоритма Дейкстры. Прочитав эти книги, вы будете точно знать, что он имеет в виду.
Успешность при прохождении собеседования. На протяжении многих лет бесчисленные студенты развлекали меня рассказами о том, как знания, почерпнутые из этих книг, позволяли им успешно справляться с любым техническим вопросом, который им задавали во время собеседования.
В чем особенность этой книги
Эта книга предназначена только для одного: постараться научить основам алгоритмизации максимально доступным способом. Воспринимайте ее как конспект лекций, которые опытный наставник по алгоритмам будет давать вам на протяжении серии индивидуальных уроков.
Существует ряд прекрасных, гораздо более традиционных и энциклопедически выверенных учебников по алгоритмам. Любой из них с пользой украсит эту серию книг дополнительными деталями, задачами и темами. Хотелось бы, чтобы вы поискали и нашли что-то полезное среди этих книг для себя. Кроме того, есть книги, которые ориентируются на программистов, ищущих готовые реализации алгоритмов на конкретном языке программирования. Множество соответствующих примеров также находятся в свободном доступе в интернете.
Для кого эта книга?
Весь смысл этой книги, как и онлайн-курсов, на основе которых она создана, — быть широко- и легкодоступной настолько, насколько это возможно. На моих онлайн-курсах широко представлены люди всех возрастов, профессионального опыта и слоев общества, есть немало учащихся и студентов, разработчиков программного обеспечения (как состоявшихся, так и начинающих), ученых и профессионалов со всех уголков мира.
Эта книга не является введением в программирование, и было бы просто идеально, если бы вы уже обладали основными навыками программирования на каком-либо распространенном языке (например, Java, Python, C, Scala, Haskell). Если вам требуется развить свои навыки программирования, то для этих целей есть несколько прекрасных бесплатных онлайн-курсов, обучающих основам программирования.
По мере необходимости мы также используем математический анализ, чтобы разобраться в том, как и почему алгоритмы действительно работают. Свободно доступные конспекты лекций «Математика для Computer Science» Эрика Лемана и Тома Лейтона являются превосходным и освежающим память пособием по системе математических обозначений (например, и ), основам теории доказательств (метод индукции, доказательство от противного и др.), дискретному распределению вероятностей и многому другому.2
Дополнительные ресурсы
Эта книга основана на онлайн-курсах, которые в настоящее время запущены в рамках проектов Coursera и Stanford Lagunita. Имеется также ряд ресурсов в помощь вам для повторения и закрепления опыта, который можно извлечь из онлайн-курсов.
Видео. Если вы больше настроены смотреть и слушать, чем читать, обратитесь к материалам с «Ютьюба», доступным на сайте www.algorithmsilluminated.org. Эти видео затрагивают все темы этой серии книг. Надеюсь, что они пропитаны тем же заразительным энтузиазмом в отношении алгоритмов, который, увы, невозможно полностью воспроизвести на печатной странице.
Тестовые задания. Как узнать, что вы действительно усваиваете понятия, представленные в этой книге? Тестовые задания с решениями и объяснениями разбросаны по всему тексту; когда вы сталкиваетесь с одним из них, призываю вас остановиться и подумать об ответе, прежде чем читать далее.
Задачи в конце главы. В конце каждой главы вы найдете несколько относительно простых вопросов для проверки усвоения материала (S), а затем более трудные и менее ограниченные по времени сложные задачи (H). Подсказки или решения всех этих задач, отмеченных соответственно знаками (H)и (S), приводятся в конце книги. Читатели могут взаимодействовать со мной и друг с другом по поводу оставшихся задач в конце главы через дискуссионный форум книги (см. ниже).
Задачи по программированию. В конце большинства глав предлагается реализовать программный проект, целью которого является закрепление детального понимания алгоритма путем создания его рабочей реализации. Наборы данных, а также тестовые примеры и их решения можно найти на www.algorithmsilluminated.org.
Форумы. Существенной причиной успеха онлайн-курсов являются реализованные через дискуссионные форумы возможности общения для слушателей. Это позволяет им помогать друг другу лучше понимать материал курса, а также отлаживать свои программы. Читатели этих книг имеют такую же возможность благодаря форумам, доступным на сайте www.algorithmsilluminated.org.
Благодарности
Эти книги не существовали бы без энтузиазма и интеллектуального голода тысяч участников моих курсов по алгоритмам на протяжении многих лет как на кампусе в Стэнфорде, так и на онлайновых платформах. Я особенно благодарен тем, кто предоставлял подробные отзывы на более ранний проект этой книги, среди них: Тоня Бласт, Юань Цао, Лесли Дэймон, Тайлер Дэ Девлин, Роман Гафитню, Бланка Хуэрго, Карлос Гуйя, Джим Хумельсин, Тим Кернс, Владимир Кокшенев, Байрам Кулиев, Клейтон Вонг, Лексин Йе и Даниэль Зингаро. Также благодарю нескольких экспертов, которые предоставили техническую консультацию: Амира Аббуда, Винсента Коницера, Кристиана Коницера, Авиада Рубинштайна и Илайю Сигала.
Я всегда ценю предложения и исправления от читателей. О них лучше всего сообщать через дискуссионные форумы, описанные выше.
Тим Рафгарден Нью-Йорк, штат Нью-Йорк. Апрель 2020
От издательства
Не удивляйтесь, что эта книга начинается с девятнадцатой главы. С одной стороны, она является четвертой частью курса «Совершенный алгоритм» Тима Рафгардена, а с другой — самостоятельным изданием, в котором рассматриваются вопросы NP-трудных задач. Приложения А, Б и В вы можете найти в книге «Совершенный алгоритм. Основы» (часть 1) и «Совершенный алгоритм. Графовые алгоритмы и структуры данных» (часть 2).
Ваши замечания, предложения, вопросы отправляйте по адресу [email protected] (издательство «Питер», компьютерная редакция). Мы будем рады узнать ваше мнение! На веб-сайте издательства www.piter.com вы найдете подробную информацию о наших книгах.
1 Класс NP-трудных задач (NP, nondeterministic polynomial time — недетерминированный полиномиально-временной) — это класс сложности, используемый для классификации задач принятия решений. NP — это множество задач, для которых экземпляры задач с ответом «да» имеют доказательства, проверяемые за полиномиальное время детерминированной машиной Тьюринга. — Примеч. пер.
2 См. Mathematics for Computer Science, Eric Lehman, Tom Leighton: http://www.boazbarak.org/cs121/LehmanLeighton.pdf.
