Intel_Nils (526801), страница 21
Текст из файла (страница 21)
Предстаелепая, допускающее сведение задач к подзадачам Заметим, что это сведение означает всего лишь, что задача и йо может быть решена, если мы можем решить задачи ) !(о н ) вйи. Соотношение ) и!со=и) с(о — ) веси может быть в дальнейшем использовано для построения действительного решения. Если имеется несколько возможных способов разбиения исходного подинтегрального выражения на части, соответствующие и и с(о, то каждой такой возможности ставится в соответствие отдельный оператор редукции задачи. Согласно правилу интегрирования суммы функций, имеем и и )г ~~~~ )! (х) а!х = ~~)~~ ~ Г! (х) с(х.
! ! ! Это правило служит оправданием следующего сведения задачи к подзадачам: Другое правило, называемое правилом вынесения постоянного множителя за знак интеграла, позволяет заменить задачу 'я)(х)ссх задачей ~)(х)с(х. Таким образом, получаем такое сведение задачи Остальные . операторы просто осуществляют подстановку одного интегрального выражения в другое и, таким образом, порождают «ИЛИ» вершины. Эти операторы основаны на еле. дующих процессах: 4.7. Примеры сведения видичи к совокупности иодвидич 107 Алгебраические подстановки Пример ~ 1 (гв 4г + 4),(з, = (2 + З )чз, (2 -1- зх)мв в Тригонометрические подстановки Пример Ых ) — с1н О созес О сЮ, х = -1н 9. е 5 4 хе р 26хе+ 16 16 ю Деление числителя на знаменатель Пример ( е — » ~ (г — 1 + — ) дг.
Дополнение до полного квадрата Пример дх р Ых (е — 1 -;-ир ~ тР=ее+и' ' На каждой данной стадии процесса мы располагаем многими альтернативными операторами редукции задачи, которые могли бы быть применены. Если для каждой задачи мы будем использовать все эти прнложимяге альтернативы, то результирующая задача перебора очень быстро станет невообразимо громоздкой. В такого типа задачах весьма существег)но привлечь эвристические соображения, которые позволили бы ограничить число порождаемых вершин. В указанной задаче интегрирования некоторые операторы редукции оказываются настолько полезными, что они (и только они) должны быть использованы во всех случаях, когда они применимы.
Так, сведения задачи, соответствующие интегрированию суммы и вынесению множителя, используются всегда, когда это оказывается возможным. Полезность других правил и операторов, таких, как тригонометрические подстановки, сильно зависит от вида подинтегрального выражения. В одной системе символического интегрирования (Слейджл, 1963а), для которой была написана программа„ все подинтегральные выражения были подвергнуты классификации по тем характеристикам, которыми они обладают. Для каждого класса подинтегральных выражений выбирались различные операторы в соответствии с их эвристической применимостью.
Пример решения. На рис. 4.9 показан «И/ИЛИ» граф перебора, образованный в результате процесса, подобного 108 Гл. 4. Представления, допускающие сведение задач к подзадачам рассмотренному выше'). Задача состоит в интегрировании выражения зз «Ф ,з)з/2 Вершины графа — это описания задач, и в каждой из них указан интеграл.
Заключительные вершины (соответствующие Р и с 4.9. <И/ИЛИ» граф перебора для задачи интегрирования. табличным интегралам) помечены двойными рамочками. Жирными дугами выделен решающий граф для этой задачи. На ') Пример основан на одной задаче интегрирования, которая была ре- шена программой Слейджла В963а). 4.7. Примеры сведения аида«и к совокуиносги подводке 100 основании этого решающего графа и табличных интегралов устанавливаем, что к< 1 ,, сгх= агсабпх+ — (да(агс гбпх) — (д(агс э!пх)а. (1 ке)еп 3 До настоящего момента мы, конечно„не говорили ничего о порядке, в котором производится сведение задачи к подзада'чам.
Этот вопрос будет освещен в следующей главе, в которой рассматриваются методы перебора при сведении задач к совокупности подзадач. Доказательство теорем в планиметрнн Доказательства теорем в планиметрии дают другой пример задач, которые могут быть решены путем сведения к подзадачам. Предположим, например, что нам нужно доказать следующую теорему: любая точка биссектрисы угла равноудалена от его сторон. Пусть задача сформулирована в следуюшем виде: А Дано: х'.РВА = х'.ОВС, АР.) ВА, СР.) ВС, где Р — отрезок, е."ь ВСР— треугольник, ЬВАР— треугольник.
и Требуется доказать; АР = = СР. Читатель (но не наша система решения задач) может обра- В С титься и рис. 4АО, где приведен Р и с. 4.10. Чертеж к рассматри чертеж, соответствуюШий этой ааемому примеру геометрической задаче.
(Позже мы обсудим, ка- теоремы. ким образом система решения эа- Дано: ~ АВР- ~СВР, дач также может воспользовать- АР 1 ВА, ся «чертежомж) СР Х ВС. Мы будем представлять тако- Доказать: АР СР. го типа задачи в виде выражения, имеющего форму В~Т, где 5 — то утверждение, которое предстоит доказать, а Т вЂ” множество посылок. Тогда наш пример описывается следующим выражением: АР = СР х' РВА = х.' РВС, АР ) ВА, СР .) ВС, РВ, Л ВСР, с."1 ВАР.
Элементарными задачами являются задачи доказательства утверждений, относительно которых мы хотим предположить, 110 Гл. 4, Представления, долускаюясие сведение задач к подзадачам что они истинны. Например, в список элементарных задач мы могли бы включить среди других следующие задачи'): Р1 и'Х, = н'.Хз) л'.Хг — прямой угол, л.Хз — прямой угол (прямые углы равны между собой); Р2 ХгХз ХзХз (отрезок равен самому себе); РЗ л.Х~ = л'.Хс (угол равен самому себе); Р4 гзХзХзХзам Ьугузуз ~ХзХз = Узуь ~ХзХ,Хз=~узузуз ~ ~ХзХзХз = ~угузуз (сторона, угол, угол = сторона, угол, угол); Рб к'. Х,ХзХз — прямой) Х,Х, .). ЛзХз (два пересекающихся перпендикулярных отрезка определяют прямой угол); Рб ЛзХз Узуз) ЛХ~ХзХз й ЛУгузуз (соответственные стороны равных треугольников равны).
В достаточно сильной программе доказательства геометрических теорем, конечна, следовало бы использовать множество других более элементарных формул. Приведенных же нами формул достаточно для иллюстрации процесса доказательства нашей теоремы. Чтобы свести задачу к подзадачам, мы введем достаточное число новых посылок с целью сделать данную задачу частным случаем некоторого истинного утверждения. Множество истинных утверждений, пригодных для этого, могло бы быть некоторым подмножеством элементарных задач.
Получаемыми при этом подзадачами будут задачи доказательства новых посылок (при условии, конечно, что даны старые посылки). Чтобы сократить число различных множеств подзадач, мы потребуем, чтобы в этих дополнительных посылках упомийались только те элементы, которые уже встречались в первоначальных посылках. Поскольку, как правило, будет существовать большое число новых посылок, удовлетворяющих этим условиям, то у иас все-таки будет очень большое число различных множеств подзадач. Каждое иэ них соответствует применению отдельного опе атора редукции задачи. окажем, каким образом довольно простая система доказательства геометрических теорем могла бы доказать ту теорему, которая была сформулирована в начале раздела. В этом примере мы будем испольэовать в качестве элементарных задач только множество (Р1, ..., Рб), упомянутое выше.
Когда мы будем добавлять посылки с тем, чтобы сделать некоторое утверждение истинным, мы будем также считать, что лишь чле- '1 Кан и в примере с интегрированием, выражения элементарных задач определяются формула ми. 4.7. Прииери сведения вада«и и совоиупности подвода~7' из ны указанного множества соответствуют истинным утверждениям. Сначала мы расчленим на подзадачи основную задачу АР = СР'1Т (где через Т мы для простоты обозначили множество всех посылок).
Единственной элементарной задачей, которая может быть использована для этого путем добавления посылок к Т, является Рб: Х,Хз = 1'гуз! йз Х,ХгХзы с-"з У|Угу». Для того чтобы эта задача нам пригодилась, нужно положить Хе=А Хз=0 Уз=С Уз=В. так что нам нужна посылка вида йХ~АР ем гзу СР. Так как в Т упоминаются только треугольники г'зВСР и сзВАР, то полагаем Хг = В и У = В. Таким образом, мы сводим нашу первоначальную задачу к задаче Л ВАР ем Л ВСР ~ Т.
В результате редукции этой задачи (путем добавления посылок, согласующихся с Р4) возникает такое множество подзадач: РВ=ОВ ~Т, ~ ВАР= ~ ВСР, ~ ВАР ~ ВС01Т. Продолжая аналогичным образом этот процесс, мы приходим к решающему графу типа «И/ИЛИ», изображенному иа рнс. 4А!. Из-за ограниченности запаса элементарных задач (хорошо соответствующих нашему примеру, но недостаточных в общем случае) в этом процессе не возникает никаких лишних множеств вершин типа «И».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
