Общие сведения

Книга предназначена для студентов, прошедших двухсеместровый вводный курс вычислительных технологий (стандартный курс «CS1/CS2»), в ходе которого они писали программы для реализации базовых алгоритмов, и работы с такими структурами данных, как деревья и графы, а также с базовыми структурами данных (массивы, списки, очереди и стеки).
Так как переход между этим курсом и первым курсом по алгоритмам еще не стал стандартным, книга открывается с изложения тем, которые знакомы студентам некоторых образовательных учреждений по курсу CS1/CS2, но в других учреждениях включаются в учебный план первого курса по алгоритмам. Соответственно, эта часть может рассматриваться либо как обзор, либо как новый материал; включая ее, мы надеемся, что книга может быть использована в более широком диапазоне учебных курсов и с большей гибкостью в отношении исходных знаний, обязательных для читателя.

В соответствии с описанным подходом мы разрабатываем базовые методы про- ектирования алгоритмов, изучая задачи из многих областей компьютерной науки и сопутствующих областей. В частности, приводятся довольно подробные описа- ния возможных применений из области систем и сетей (кэширование, коммутация, междоменная маршрутизация в Интернете), искусственного интеллекта (плани- рование, игры, сети Хопфилда), распознавание образов (сегментация изображе- ний), извлечение информации (обнаружение точки перехода, кластеризация), исследование операций (планирование воздушного движения) и вычислительная биология (выравнивание последовательностей, вторичная структура РНК).

Понятие вычислительной неразрешимости и ЖР-полноты в частности играет значительную роль в книге. Это соответствует нашему подходу к общему процессу

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

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

Чтобы упростить работу с такими задачами, в каждую главу включается раз- дел «Упражнения с решениями», в котором мы берем одну или несколько задач и подробно описываем процесс поиска решения. По этой причине обсуждение каждого упражнения с решением получается намного длиннее, чем простая запись полного, правильного решения (другими словами, намного длиннее, чем было не- обходимо для полноценного решения, если бы эта задача была задана студенту для самостоятельного решения). Как и в остальном тексте книги, обсуждения в этих разделах должны дать читателю представление о более масштабных процессах, применяемых для решения задач такого типа и в конечном итоге приводящих к точному решению.

Стоит упомянуть еще два обстоятельства, связанных с использованием этих за- дач для самостоятельной работы в учебных курсах. Во-первых, задачи упорядочены приблизительно по возрастанию сложности, но это всего лишь приблизительный ориентир, и мы не советуем уделять ему слишком много внимания; так как основная часть задач была разработана для самостоятельной работы студентов, большие под- множества задач в каждой главе довольно тесно связаны в отношении сложности. Во-вторых, если не считать начальных глав, над решением этих задач придется потрудиться — как для того, чтобы связать описание задачи с алгоритмическими методами, описанными в главе, так и для непосредственного проектирования ал- горитма. В своем учебном курсе мы назначали около трех таких задач на неделю.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Общие сведения:

  1. I. Общие сведения о профессии.
  2. I. Общие сведения о профессии.
  3. 4.3. ПЛАНЕТЫ Общие сведения
  4. 4.4. Поля Общие сведения
  5. 4.5. АСПЕКТЫ Общие сведения
  6. 1. Краткие общие сведения
  7. 1. Краткие общие сведения
  8. Знаки зодиака Общие сведения
  9. Статья 422. Разглашение сведений военного характера, составляющих государственную тайну, или потеря документов или материалов, содержащих такие сведения
  10. 16.3. Перечни сведений, составляющих государственную тайну, и сведения, которые не могут относиться к государственной тайне
  11. Статья 158. Фальсификация избирательных документов, документов референдума или фальсификация итогов голосования, предоставление ложных сведений в органов Государственного реестра избирателей или фальсификация сведений Государственного реестра избирателей
  12. 16.6. Рассекречивание сведений и их носителей
  13. 16.7. Распоряжение сведениями, составляющими государственную тайну
  14. Статья 895. Конфиденциальность сведений о договоре
  15. 16.4. Отнесение сведений к государственной тайне и их засекречивание
  16. ИНЖЕНЕР ВСПОМИНАЕТ НУЖНЫЕ СВЕДЕНИЯ
  17. Дополнительные сведения