Примечания к упражнениям

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

Упражнения, которые проверяют, насколько хорошо вы усвоили материал, помечены незаполненным треугольником, например:

> 18.34. Рассмотрим граф 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.

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

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

Упражнения, которые дополняют текст новой и требующей размышления информа­цией, помечены незаполненной окружностью, в частности:

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

Такие упражнения заставляют сосредоточиться на важных понятиях, связанных с ма­териалом, изложенным в тексте, либо искать ответа на вопрос, который может возник­нуть во время чтения. Возможно, читатели сочтут полезным прочесть эти упражнения даже при отсутствии времени на их выполнение.

Упражнения, которые имеют целью бросить вызов читателю, провоцируя его на реше­ние трудной задачи, помечены черной точкой:

• 20.73. Опишите, как вы будете искать дерево MST графа настолько большого, что в основной памяти одновременно могут находиться всего лишь V ребер.

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

Несколько упражнений, которые особенно трудны (по сравнению с большинством других), помечены двумя черными точками, например:

•• 20.40. Разработайте походящий генератор случайных графов с V вершинами и Е реб­рами, такой, что время выполнения алгоритма Прима, использующего поиск по при­оритетам (программа 20.7), будет нелинейным.

Эти упражнения аналогичны вопросам, которые могут ставиться в научной литерату­ре, однако материал книги может так подготовить читателей, что им доставит удоволь­ствие попытаться ответить на них (а возможно, и преуспеть в этом).

Предисловие

Мы старались, чтобы все пометки были безотносительны к программной и математи­ческой подготовке читателей. Те упражнения, которые требуют наличия опыта по про­граммированию или математическому анализу, очевидны. Мы настоятельно рекоменду­ем всем читателям проверить свое понимание алгоритмов, реализовав их. Тем не менее, упражнения подобные приведенному ниже, не представляют каких-либо трудностей для профессиональных программистов или студентов, изучающих программирование, но мо­гут потребовать существенных усилий от тех, кто в последнее время по ряду причин про­граммированием не занимался:

• 17.74. Напишите программу, которая генерирует V случайных точек на плоскости, после чего строит граф, состоящий из ребер, соединяющих все пары точек, удален­ных друг от друга на расстояние, не превышающее d (см. рис. 17.13 и программу 3.20). Определите, какое значение d следует выбрать, чтобы ожидаемое число ребер было равно Е.

В том же духе мы рекомендуем читателям стремиться учитывать приводимые нами аналитические обоснования свойств всех алгоритмов. С другой стороны, упражнения, подобные приведенному ниже, не составят сложности для профессионального математика или студента, изучающего дискретную математику, однако наверняка потребуют значи­тельных усилий от тех, кто давно не занимался математическим анализом:

о 19.5. Сколько орграфов соответствует каждому неориентированному графу, содержа­щему V вершин и Е ребер?

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