Алгоритмы - построение и анализ (1021735), страница 215
Текст из файла (страница 215)
Чтобы проверить это утверждение, обозначим й = 6 (д, Т [1]). Тогда из определений функций 6 и <т следует, что Рь 1 РтТ [1]. Следовательно, либо Ь = = О, либо Ь ) 1 и (отбрасывая последний символ из Рь и ОТ [1]) Рь 1 1 Рц (в этом случае Ь вЂ” 1 Е к' [д]). Таким образом, либо )с = О, либо /с — 1 Е к' [д], что и доказывает сформулированное выше утверждение.
Доказанное утверждение используется следующим образом. Обозначим через д' значение, юторое принимает величина д в строке 6, и воспользуемся уравнением к' [д] = (й: Ь < д и Рь ~ Рц) из леммы 32.5 для обоснования итерации д — к [д], перечисляющей элементы множества (lс: Рь ) Р'~. В строках 6-9 путем проверки элементов множества я' [д'] в убывающем порядке определяется величина 6 Я,Т [1]).
Указанное утверждение используется в юде для того, чтобы начать работу с д = ф(Т; 1) = з (Т, 1) и выполнять итерации д — к [д] до тех пор, пока не будет найдено значение д, такое что д = 0 или Р [д+ Ц = = Т [1]. В первом случае 6 (д', Т [1] = О), а во втором — значение переменной д равно максимальному элементу множества Е', так что 6 (д', Т [1]) = д+1 согласно следствию 32.7. Строка 12 в процедуре КМР Млтснек необходима для того, чтобы избежать возможного обращения к элементу Р [т+ 1] в строке 6 после того, как будет обнаружено вхождение образца Р. (Согласно указанию, приведенному в упражнении 32.4-6, аргумент, что д = и (Т; 1), остается справедливым во время следующего выполнения строки б: для любого а Е Е Б (тп, а) = Б (и [тп], а) или, что эквивалентно, п(Ра) = и (Р [ [а).) Остальная часть обоснования корректности алгоритма Кнута-Морриса-Пратга следует из корректности процедуры Г~нгге А(л'омАтон МАтснек, поскольку теперь должно быть понятно, что процедура КМР МАтснек просто имитирует ее поведение.
Упражнения 32.4-1. Вычислите префиксную функцию для образца аЬаЬЬаЪЬаЬЬаЬаЬЬаЬЬ (алфавит имеет вид Е = (а, Ь1). Глава 32. Поиск подстрок 1045 32.4-2. Найдите верхнюю границу размера я*[у] как функцию от величины д. Приведите пример, показывающий, что ваша оценка не может быть улучшена. 32.4-3.
Объясните, как найти вхождения образца Р в текст Т, зная функцию и для РТ (те. строки длиной т+и, полученной в результате конкатенации строк Р и Т). 32.4-4. Покажите, как улучшить процедуру КМР МАтсннк, заменив функцию я в строке 7 (но не в строке 12) функцией я', рекурсивно определяемой для д = 1, 2,..., т следующим образом: О если я [д] = О, я' [о] = з' [к [д]] если я [д] ~ О и Р [я [д] + Ц = Р [д + 1], я [а] если я [а] ~ О и Р [я [а] + 1] ~ Р [а + 1]. Объясните, почему модифицированный алгоритм работает корректно, а также в чем состоит смысл этого улучшения. 32.4-5.
Разработайте алгоритм, который бы позволил в течение линейного времени определить, является ли текстовая строка Т циклической перестановкой другой строки Т'. Например, строки агс и саг являются циклическими перестановками друг друга. * 32.4-6.
Разработайте эффективный алгоритм вычисления функции переходов Б для конечного автомата поиска заданного образца Р. Время работы алгоритма должно быть равно О (т Д). (Указание: докажите, что б (д, а) = = б (я [д], а), если д = т или Р [д+ Ц ф а.) Задачи 32-1. Поиск подстрок на основе коэффициентов повторения Обозначим как у' строку, полученную в результате г-кратной конкатенации строки у с самой собой. Например, (аЬ) = аЬаЬаЬ. Говорят, что коэффициент ловторенил (геребйюп Гасюг) строки х е Е* равен г, если х = у" для некоторой строки у Е Е' и значения т > О. Через р(х) обозначим наибольший из коэффициентов повторения х.
а) Разработайте эффективный алгоритм, принимающий в качестве входных данных образец Р [1..т] и вычисляющий значение р (Р;) для 1 = 1, 2,..., т. Чему равно время работы этого алгоритма? б) Определим для произвольного образца Р [1..т] величину р' (Р) как шах1<;< р(Р;). Докажите„что если образец Р выбирается случайным образом из множества всех бинарных строк длиной т, то математическое ожидание р' (Р) равно О (1). Часть Чй. Избранные темы 1046 в) Покажите, что приведенный ниже алгоритм поиска подстрок юрректно находит все вхождения образца Р в текст Т [1..и] в течение времени 0 (р* (Р) и + ти).
иеРет1т!ОН МАтснек(Р, Т) 1 т — 1еидЯР) 2 и — 1еидй[Т) З Ь 1+р'(Р) 4 д~-О 5 в -О 6 и)п1е в < и — ти 7 беЫТ[в+д+Ц = Р[д+Ц 8 1Ьеп д -д+1 9 1Т д = ти 10 1Ьеп рпп1 "Образец обнаружен при сдвиге" в 11 Ы д = т или Т[в+ д+ Ц ~ Р[д+ Ц 12 Феп в — в+ шах(1, [д/1в)) 13 д ~- О Этот алгоритм был предложен Галилом (ОаИ) и Сейферасом (Яе(Гегав). Развивая зти идеи, они получили алгоритм поиска подстрок с линейным временем работы, использующий всего 0 (1) памяти, кроме необходимой для хранения строк Р и Т.
Заключительные замечания Связь поиска подстрок с теорией юнечных автоматов обсуждается в книге Ахо (А)ю), Хопкрофта (Норсгой) и Ульмана (П!1шап) [5). Алгоритм Кнута-МоррисаПратта [187) разработан Кнутом (Клеей) и Прапом (Ргап) и независимо Моррисом (Мотив); результаты своих исследований они опубликовали совместно. Алгоритм Рабина-Карпа был предложен Рабином (КаЫп) и Карпом (Катр) [175). Галил (Оай1) и Сейферас (Бе(Гегав) [1071 разработали интересный детерминистический алгоритм поиска подстрок с линейным временем работы, в ютором используется лишь 0 (1) памяти сверх необходимой для хранения образца и текста.
ГЛАВА 33 Вычислительная геометрия Вычислительная геометрия — это раздел теории вычислительных систем, изучающий алгоритмы, предназначенные для решения геометрических задач. В современных инженерных и математических расчетах вычислительная геометрия, в числе других областей знаний, применяется в машинной графике, в робототехнике, при разработке СВИС, при автоматизированном проектировании и в статистике. Роль входных данных в задачах вычислительной геометрии обычно играет описание множества таких геометрических объектов, как точки, отрезки нли вершины многоугольника в порядке обхода против часовой стрелки.
На выходе часто дается ответ на такие запросы об этих объектах, как наличие пересекающихся линий. Могут также выводиться параметры новых геометрических объектов, например, выпуклой оболочки множества точек (это минимальный выпуклый многоугольник, содержащий данное множество). В этой главе мы ознакомимся с несколькими алгоритмами вычислительной геометрии в двух измерениях, т.е. на плоскости. Каждый входной объект представлен множеством точек (ры рз,...), где каждая точка р, = (х;, у;) образована парой действительных чисел х;, у; Е Н..
Например, и-угольник Р представлен последовательностью вершин (ро, ры..., р„1) в порядке обхода границы многоугольника. Вычислительная геометрия может работать в трех измерениях, и даже в большем их числе, но визуализация подобных задач и их решений может оказаться очень трудной. Однако даже в двух измерениях можно ознакомиться с хорошими примерами применения методов вычислительной геометрии. В разделе 33.1 показано, как быстро и точно ответить на такие основные вопросы о расположении отрезков: если два отрезка имеют общую конечную точку, то как следует перемещаться при переходе от одного из ннх к другому — по часовой стрелке или против часовой стрелки, в каком направлении следует сво- Часть ЧП.
Избранные темы 1048 рачивать при переходе от одного такого отрезка к другому, а также пересекаются ли два отрезка. В разделе 33.2 представлен метод, известный под названием "выметание", или "метод движущейся прямой". Он используется при разработке алгоритма со временем работы 0 (и 18 и), определяющего, имеются ли пересечения среди и отрезков. В разделе 33.3 приведены два алгоритма "выметания по кругу", предназначенные для вычисления выпуклой оболочки множества п точек (наименьшего содержащего их выпуклого многоугольника): сканирование по Грэхему (бгаЬаш'з зсап), время работы которого равно 0(п18п), и обход по Джарвису (1агч1з'з шагсЬ), время выполнения которого равно 0 (пп), где Ь вЂ” количество вершин в оболочке.
Наконец, в разделе 33.4 приводится алгоритм декомпозиции со временем работы 0(п18п), предназначенный для поиска пары ближайших точек в заданном на плоскости множестве из и точек. 33.1 Свойства отрезков В некоторых представленных в этой главе алгоритмах требуется ответить на вопросы о свойствах отрезков.
Выпуклой комбинацией (сопчех сошЬ(пайоп) двух различных точек рз = (хмуг) и рз = (хз, уз) называется любая точка рз = = (хз, уз), такая что для некоторого значения а, принадлежащего интервалу 0 < < а < 1, выполняются равенства хз = ахз + (1 — а) хз и Уз = ау~ + (1 — с~) Уз. Также пишут, что рз = арз + (1 — а) рз. Интуитивно понятно, что в роли рз может выступать любая точка, которая принадлежит прямой, соединяющей точки рз и рз, и находится между этими точками. Если заданы две различные точки рз н рз, то отрезкам прямой (йле зейтеп1) р~р~ называется множество выпуклых комбинаций рз и рз. Точки р~ и рз называются конечными точками (епоро(п1з) отрезка рзрз. Иногда играет роль порядок следования точек рз и рз, и тогда говорят о направленном отрезке (о1гес1еб зейшеш) рзрз.
Если точка рз совпадает с началом координат (ог181п), т.е. имеет координаты (0,0), то направленный отрезок рзрг можно рассматривать как вектор (чес1ог) рз. В этом разделе исследуются перечисленные ниже вопросы. 1. Если заданы два направленных отрезка рор~ и рорз, то находится ли отрезок рорз в направлении по часовой стрелке от отрезка рорз относительно их общей точки ро? 2. Если заданы два направленных отрезка рорз и р~р~, то в какую сторону следует свернуть в точке рз при переходе от отрезка рорз к отрезку р~рз? 3. Пересекаются ли отрезки рррр и рзр4? На рассматриваемые точки не накладывается никаких ограничений. На каждый из этих вопросов можно ответить в течение времени 0(1), что не должно вызывать удивления, поскольку объем входных данных, которыми выражается каждый из этих вопросов, равен 0 (1).
Кроме того, в наших методах Глава 33. Вычислительная геометрия 1049 используются только операции сложения, вычитания, умножения и сравнения. Не понадобится ни деление, ни вычисление тригонометрических функций, а ведь обе эти операции могут оказаться дорогостоящими и приводить к проблемам, связанным с ошибками округления.
Например, метод "в лоб" при определении того, пересекаются ли два отрезка, — найти для каждого из них уравнение прямой в виде у = тх+ Ь (где гп — угловой коэффициент, а Ь вЂ” координата пересечения с осью у), вычислить точку пересечения этих прямых и проверить, принвдпежит ли эта точка обоим отрезкам. В таком методе при вычислении координат точки пересечения используется деление.
Если отрезки почти параллельны, этот метод очень чувствителен к точности операции деления на реальных компьютерах. Изложенный в данном разделе метод, в котором удается избежать операции деления, намного точнее. Векторное произведение Вычисление векторного произведения составляет основу методов работы с отрезками. Рассмотрим векторы рг и рз, показанные на рис. 33.1а. Векторное произведение (егозя ргодис1) рг х рз можно интерпретировать как значение (со знаком) площади параллелограмма, образованного точками (О, 0), рг, рз и рг + рз = = (хг+ хз, у1 + уз). Эквивалентное, но более полезное определение векторного произведения — определитель матрицы: 1.
1 х1 хз 1 р1 х рг = г1е1 = хгуз — хзуг = -рз х р1. ~, Уг Уг ) Если величина р1 х рз положительна, то вектор рг находится по часовой стрелке от вектора рз относительно начала координат (О, 0); если же векторное произведение отрицательно, то вектор р1 находится в направлении против часовой стрелки от вектора рз. (См. упражнение 33.1-1.) На рис. 33.1б показаны области, расположенные по и против часовой стрелки относительно вектора р.
Граничный случай возникает, когда векторное произведение равно нулю. В этом случае векторы коллинеарны (со11шеаг), т.е. они направлены в одном и том же или в противоположных направлениях. Чтобы определить, находится ли направленный отрезок рор1 по часовой стрелке от направленного отрезка рорз относительно их общей точки ро, достаточно использовать ее как начало координат.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
