![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Примечания к упражнениям
Классификация упражнений — это занятие, сопряженное с рядом трудностей, поскольку читатели такой книги, как эта, обладают различными уровнями знаний и опыта. Тем не менее, определенное указание не помешает, поэтому многие упражнения помечены одним из четырех маркеров, дабы проще было выбрать соответствующий подход. Упражнения, которые проверяют, насколько хорошо вы усвоили материал, помечены незаполненным треугольником, например: > 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 вершин и Е ребер? Книга снабжена настолько большим количеством упражнений, что их все невозможно прочесть и усвоить. Тем не менее, я надеюсь, что среди них есть достаточно таких, которые могут послужить для читателей большим стимулом к углубленному исследованию соответствующих тем.
|