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

Введение

1 Система аналитических вычислений Maple

1.1 Использование систем аналитических вычислений в математических исследованиях.

1.2 Основные возможности системы аналитических вычислений Maple.

2 Решение геометрических задач с помощью системы Maple

2.1 Обобщенная задача Т. Поповичи.

2.2 О внутреннем расстоянии на поверхности параллелепипеда

2.3 Задача Дж.В. Фике.

2.4 Задача В.К. Ионина.

2.5 Системная организация алгоритмов поиска решений.

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

Первая глава диссертации посвящена описанию математической системы Maple различных версий и сравнению с аналогичными программными системами компьютерной математики. Упомянуты также примеры задач из классических разделов математики, решенные при помощи компьютерных вычислений.

В первом разделе описываются различные системы компьютерной математики, причем в качестве наиболее мощных выделяются MatLab, Mathernatica и Maple. Кратко характеризуется один из лидеров систем символьной математики математический пакет Mathernatica 2/3, имеющий тысячи встроенных и библиотечных функций и обладающий огромными возможностями графического представления решений. Описываются области применения систем компьютерной алгебры, начиная с образования и кончая фундаментальными исследованиями. Приводятся конкретные примеры, когда использование современных математических пакетов приводило к решению соответствующей задачи.

Во втором разделе первой главы подробно рассматриваются основные возможности систем класса Maple, второго лидера среди систем компьютерной алгебры. Упоминается история создания систем этого класса, а также детально изучается наиболее популярная версия Maple Y Release 4.

Вторая глава диссертации посвящена решению некоторых геометрических задач с помощью системы компьютерной математики Maple Y R4. Отметим, что приведенные решения являются приоритетными и представляют ценность и вне контекста использования вычислительной техники.

Первый раздел второй главы посвящен решению обобщенной задачи Т. Поповичи. Рассмотрим на евклидовой плоскости выпуклый четырехугольник ABCD. Пусть Ai, Bi,.Ci, Di - такие точки отрезков АВ, ВС, CD и DA соответственно, что

AAi\ \BBi\ \CCi\ \DDi\ k \AiB\ ~ \BiC\ ~ \CiD\ ~ \DiA\ ~ для некоторого к > 0. Прямые АВЪ ВС\, CDi, DA\ образуют четырехугольник KLMN (К, L, М, N — точки пересечения первой и четвертой, первой и второй, второй и третьей, третьей и четвертой прямых соответственно), лежащий внутри ABCD. Обозначим через S и s площади четырехугольников ABCD и KLMN соответственно. Задача Т. Поповичи (Т. Popoviciu) ([22], с.39). состоит в доказательстве неравенства

6 5 при к = 1. Решение оригинальной задачи Т. Поповичи было получено в [7]. В первом разделе получено более общее утверждение, справедливое для всех к > 0.

Теорема 2.1.1. Для произвольного выпуклого четырехугольника на плоскости и к > 0 справедливо неравенство

1 ? < 1 9 (fc + l)(fc2 + fc + l) ~S-2k2 + 2k + l ' причем в случае S > 0 равенство (/с + 1)(&2-|- k + l)s = S выполняется лишь для четырехугольников с двумя совпадающими вершинами, а любой четырехугольник со свойством (2к'2 + 2к 4- = помещается в непрерывное семейство четырехугольников с тем же свойством, содержащее некоторый параллелограмм.

Второй раздел посвящен исследованию свойств внутреннего расстояния на поверхности прямоугольного параллелепипеда. Рассмотрим в трехмерном евклидовом пространстве прямой параллелепипед Р — АВСВМВ'С'В' со сторонами длины \АВ\ = а, \АО\ = Ь, \АА!\ = с, а < Ь < с. Объектом нашего исследования является внутреннее расстояние между точками на поверхности 5 = дР параллелепипеда Р. Напомним, что внутренним расстоянием ¿{М, /V) между точками М £ 5 и // £ 5 называется минимум длин ломаных, лежащих в 5 и соединяющих точки М и N. Достаточно сложной задачей является определение самой далекой точки поверхности от заданной точки в смысле внутреннего расстояния. Даже в том случае, когда в качестве фиксированной точки берется вершина параллелепипеда, не вполне ясно какая точка будет от нее самой удаленной. Например для куба самой далекой точкой от вершины является противоположная вершина, в случае же параллелепипеда с размерами 1x1x2 противоположная вершина не является самой удаленной точкой.

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

Теорема 2.2.1 Для прямого параллелепипеда в трехмерном евклидовом пространстве с длинами сторон а < Ь < с необходимым и достаточным условием существования точки на поверхности параллелепипеда, расположенной далее в смысле внутреннего расстояния от заданной вершины, чем противоположная вершина, является неравенство

2с2 - 2Ъс - ас - аЬ > 0. В третьем разделе второй главы решается задача Дж.В. Фике. Рассмотрим на евклидовой плоскости два конгруэнтных пересекающихся прямоугольника Р\ = АВСР и Р2 = ЕГО!. Пусть Ь\ - длина той части границы дР\ первого прямоугольника, которая попадает во внутренность гтг£(Рг) второго. Аналогично, - длина части границы дР2 второго прямоугольника, попадающей во внутренность тЬ{Р\) первого. Задача Дж.В. Фи-ке Рюке^) [27, 26] заключается в доказательстве неравенства

Ьг <Ь2< 3Ъх.

Доказана следующая теорема.

Теорема 2.3.1. Для пересекающихся конгруэнтных прямоугольников на евклидовой плоскости в обозначениях, приведенных выше, выполняется неравенство Ь2< ЗЬг, причем приведенное неравенство неулучшаемо.

Четвертый раздел второй главы посвящен решению задачи В.К. Ио-нина. Рассмотрим на евклидовой плоскости простую замкнутую ломаную, состоящую из нечетного числа звеньев длины 1. Требуется доказать, что площадь области, ограничиваемой данной ломаной, не меньше площади равностороннего треугольника со стороной 1, то есть не меньше чем \/3/4.

Рассматривается несколько более общая постановка. Пусть на евклидовой плоскости дана простая замкнутая ломаная с т звеньями, одно из которых имеет длину а £ [0,1], а длины остальных звеньев равны 1. Обозначим через 5 площадь области, ограничиваемой данной ломаной. Основным результатом данного параграфа является следующая

Теорема 2.4.1. При т = 2п — 1 справедливо неравенство 5 > |\/4 — а2. При т = 2п справедливо неравенство Б > — (1 — °)2- Оба неравенства неулучшаемы.

В качестве следствия при а = 1 получается решение сформулированной выше задачи В.К. Ионина.

Теорема 2.4.2. Любая замкнутая ломаная на евклидовой плоскости,

- 6 состоящая из нечетного числа звеньев длины 1, ограничивает область с площадью не менее чем л/З/4.

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

В диссертации также присутствуют три приложения. Они представляют из себя рабочие листы системы Maple, созданные для решения конкретных задач в рамках названной системы. В приложении 1 приводится решение обобщенной задачи Поповичи, приложение 2 демонстрирует пример доказательства специального тригонометрического неравенства, а приложение 3- посвящено доказательству выпуклости некоторой вспомогательной функции.

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

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

Заключение

С помощью системы Maple в диссертации получены следующие результаты.

1. Получено решение обобщенной задачи Т. Поповичи (Т. Popoviciu) о критических значениях отношений площадей четырехугольников.

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

3. Получено решение задачи Дж.В. Фике (J.W. Fickett) о критических значениях отношений относительных периметров двух конгруэнтных прямоугольников.

4. Решенн задача В.К. Ионина о минимальной площади области, ограничиваемой замкнутой ломаной с нечетным количеством звеньев единичной длины. Найдено обобщение данной задачи на случай любого количества звеньев единичной длины, кроме одного.

5. Получены тестовые задания для проверки эффективности алгоритмов и программных комплексов, направленных на вычисление основных характеристик геометрических объектов в евклидовом пространстве.

Успешное применение математических пакетов зависит, в первую очередь, от правильного выбора модели соответствующей геометрической задачи. Система Maple при исследовании задачи'играет роль экспериментальной базы, позволяет численно проверять возникающие гипотезы и, что более примечательно, указывает путь к математически строгому доказательству.

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

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

Автор выражает благодарность своему научному руководителю профессору Е.Д. Родионову за постоянное внимание и поддержку.

1. Говорухин В.Н., Цибулин В.Г. Введение в Maple V. Математический математический пакет для всех. - М.: Мир, 1997, 208 с.

2. Дьяконов В.П. Математическая система Maple V R3/R4/R5. М.: Солон, 1998, 399 с.

3. Дьяконов В.П., Пеньков А. Современные математические системы. PC WEEK, 1996, N 43 (67), с.42.

4. Дьяконов В.П. Системы символьной математики Mathematica 2 и Mathematica 3. М.: CK ПРЕСС, 1998, 320 с.

5. Дэвенпорт Дж., Сирэ И., Турнье Э. Компьютерная алгебра. Системы и алгоритмы алгебраических вычислений. М.: Мир, 1991, 352 с.

6. Матросов A.B. Maple 6. Решение задач высшей математики и механики. -СПб.: БХВ-Петербург, 2001, 528 с.

7. Никоноров Ю.Г. Некоторые задачи евклидовой геометрии.// Препринт N1, Рубцовский инд-ный институт, Рубцовск, 1998, 32 с.

8. Никоноров Ю.Г., Никонорова Ю.В. Обобщенная задача Поповичи. Те-зизы докладов международной научно-технической конференции "Вузовская наука в современном мире", Рубцовск, 1999, с. 7-8.

9. Никоноров Ю.Г., Никонорова Ю.В. Решение обобщенной задачи Поповичи. // Труды Рубцовского инд-ного института. Т.7. Рубцовск, 2000, с.222-228.

10. Никоноров Ю.Г., Никонорова Ю.В. О внутренней геометрии поверхности прямоугольного параллелепипеда. // Труды Рубцовского инд-ного института. Т.7. Рубцовск, 2000, с.229-232.

11. Никонорова Ю.В. Об одном классе задач на евклидовой плоскости. Материалы 38-ой международной научной студенческой конференции "Студент и научно-технический прогресс", 4.1, Новосибирск, НГУ,2000, с.50-51.

12. Никонорова Ю.В. Новый подход к решению некоторых экстремальных задач на евклидовой плоскости. Тезисы докладов четвертого сибирского конгресса по прикладной и индустриальной математике, 4.1, Новосибирск, ИМ СО РАН, 2000, с.132.

13. Никонорова Ю.В. Об одном классе задач на евклидовой плоскости. Те-зизы докладов международной научно-технической конференции "Вузовская наука в современном мире", Рубцовск, 2000, с.4.

14. Никонорова Ю.В. Об одной изопериметрической задаче В.К. Ионина. Материалы четвертой краевой конференции по математике, Барнаул: Изд-во-АГУ, 2001, с.12.

15. Никонорова Ю.В. Применение пакетов аналитических вычислений к решению некоторых задач евклидовой геометрии. Тезисы докладов 4-ой международной конференции по геометрии и топологии, Черкассы: Изд-во ЧИТИ, 2001, с.74.

16. Никонорова Ю.В. Об одной экстремальной задаче на евклидовой плоскости. Математические труды, Т.4, N1, 2001, с. 111-121.

17. Никонорова Ю.В. Об одной изопериметрической задаче на евклидовой плоскости. // Труды Рубцовского инд-ного института. Т.9. Рубцовск,2001, с.66-72.- 80

18. J.van de Lune, J.J. te Riele, D.T. Winter On the zeros of the Riemann zeta function in the critical strip, IV Math, of Сотр., 46, 1986, p.667-681.

19. Monagan В., Geddes K.O., Heal K.M., Labahn G., Vorkoetter S.M. Maple V Realise 5. Programming Guide. Springer, 1998, 380 p.

20. Monagan M.B., Geddes K.O., Labahn G., Vorkoetter S.M., McCarron J. Maple 6 Programming Guide. Waterloo Maple Inc., 2000, 586 p.

21. Montgomery H.L. Distribution of the Zeros of the Riemann Zeta Function Proceedings Int. Cong. Math. Vancouver, 1974, Vol.1, p.379-381.

22. Ван дер Варден Б.JI. Алгебра. М.: Наука, 1972, 624 с.