Математика. Настоящий учебник посвящен системе Mathematica прикладному пакету компьютерной алгебры, при помощи которого можно решать любые задачи, в которых в той или иной форме встречается математика
 Скачать 4.43 Mb.
|
|
Глава I. ЧТО ТАКОЕ КОМПЬЮТЕРНАЯ АЛГЕБРА? Компьютерная алгебра является одной из самых мифологизированных областей. Не только большинство пользователей, но и многие профессио- нальные математики и программисты не имеют представления о реальной силе, возможностях и специфике имеющихся систем, не говоря уже о бли- жайших перспективах этой области. Мы постараемся развеять некоторые из этих мифов. Для нас не представляет сомнения, что: • При помощи систем компьютерной алгебры уже сегодня воз- можно проводить все обычные в математике и ее приложениях вычисления. Все импликации этого факта не только не осознаны, но даже не начинали еще всерьез рассматриваться. • Основные системы компьютерной алгебры являются в первую очередь языками программирования сверхвысокого уровня, приближающи- мися по своей выразительной силе к живому языку, и их следует изучать именно как языки, а не как обычные компьютерные приложения. • Математикам свойственно недооценивать то, в какой степени разви- тие математики зависит от внешних обстоятельств, в первую очередь от доступных вычислительных средств. Развитие компьютерной алгеб- ры уже сегодня оказывает радикальное воздействие на исследо- вания во многих областях чистой математики (таких, как теория групп, комбинаторика, теория чисел, коммутативная алгебра, алгебраиче- ская геометрия и т.д.). В самое ближайшее время это влияние распро- странится на всю математику и приведет к кардинальному пересмотру ос- новных направлений исследований, переоценке всех ценностей и полному изменению стиля работы математиков. 11 • Бешеное сопротивление, которое вызывает развитие компьютерной ал- гебры среди методистов и многих преподавателей математики, связано с тем, что дальнейшее развитие этих систем уже в ближайшие 10–15 лет приведет к полному обесцениванию всех традиционных вы- числительных навыков и необходимости полного пересмотра препода- вания математики на школьном и университетском уровне. • Бешеное сопротивление, которое вызывает развитие компьютерной ал- гебры среди многих представителей Computer Science, связано с тем, что эти системы полностью обесценивают и подавляющую часть традиционных программистских навыков. При помощи этих систем любой грамот- ный любитель может за несколько минут написать программу, аналог которой на Fortran или C потребовал бы нескольких дней работы профессионального программиста. Мы думаем, что имеется еще одно чрезвычайно существенное обстоя- тельство, объясняющее неистовое эмоциональное неприятие систем ком- пьютерной алгебры и побуждающее многих игнорировать их возможности — и даже само их существование. Дело в том, что эти системы непри- нужденно решают задачи, которые, как традиционно считалось, являются чисто человеческими и требуют интеллекта и мышления, задачи, на которых основано все традиционное преподавание, задачи, представляющие серьез- ные трудности для большинства человеческих существ! Опыт общения с этими системами побуждает отбросить шоры европейской рационалистиче- ской философии и заново обдумать все, что связано с интеллектом и мыш- лением, полностью разделив те уровни, на которых происходит вычисление и те, на которых происходит понимание, те, на которых функционирует интеллект (=мышление?) и те, на которых функционирует сознание. Начиная с 1950-х годов чрезвычайно популярна дискуссия на тему “мо- жет ли компьютер мыслить?” Усилия физиков были направлены на то, чтобы доказать, что компьютер может мыслить, в то время как аргумен- ты лириков каждый раз основывались на таком переопределении понятия мышления, которое позволяло игнорировать каждый новый успех физиков. Исследования в области компьютерной алгебры вплотную подвели нас к та- кой точке, где никакое дальнейшее переопределение понятия мышления не представляется возможным и мы вынуждены констатировать, что ком- пьютер может мыслить. Тем самым, подлинный вопрос искусственного интеллекта должен теперь ставиться так: “может ли компьютер понять, что он может мыслить?” — или, по Декарту, cogito cogitare. 12 § 1. Математика и компьютеры Anyone who cannot cope with mathematics is not fully human. At best he is a tolerable subhuman who has learned to wear shoes, bathe and not make messes in the house. Lazarus Long, “Time Enough for Love” Проблема N 1 кибернетики: Каким местом человек думает? Проблема N 2 кибернетики: Как он это этим местом делает? А.Соловьев, `Ишкушштвенный интеллект' Прежде чем переходить к обсуждению собственно системы Mathematica, мы сделаем несколько общих замечаний о роли компьютера и, в особенно- сти, о роли символьных вычислений в научном исследовании и препода- вании математики как на школьном, так и на университетском уровне. Нам кажется, что этот вопрос является сегодня не просто важной, а цен- тральной проблемой для всех, кто всерьез задумывается над тем, чему и как нужно учить школьников и студентов технических, экономических и естественнонаучных (а может быть и гуманитарных!!!) специальностей в курсах математики и информатики. Сегодняшнее построение курса математики в общеобразовательной шко- ле отягощено двухтысячелетней традицией и, в целом, не находится бо- лее даже на уровне потребностей XVI века!!! Чуть лучше обстоит дело в нескольких специализированных физико-математических школах, но и здесь, с нашей точки зрения, необходим дальнейший радикальный пере- смотр всей программы, в сторону ее углубления и модернизации. Курс же информатики в значительной степени унаследовал свойственное 50-м и началу 60-х годов — и совершенно абсурдное с сегодняшней точки зре- ния!!! — отождествление любого серьезного использования компьютера с традиционным программированием. Высказанные в предыдущем абзаце утверждения могут показаться че- ресчур драматичными, и нуждаются в пояснении. С нашей точки зрения, существующий сегодня школьный курс математики ориентирован, прежде всего, на выработку вычислительных навыков и механического использова- ния небольшого числа стандартных алгоритмов — кстати, в большинстве своем чрезвычайно неэффективных с вычислительной точки зрения! Не следует думать, конечно, что это является чисто Российской проблемой; насколько мы можем судить, во всех странах Западной Европы — не го- воря уже про США!! — преподавание математики в школе в целом либо поставлено еще значительно хуже, чем в России, либо страдает крайним формализмом (как во Франции). Не следует думать также, что это являет- ся исключительно проблемой средней школы — почти в такой же степени архаично и ни в малейшей степени не отвечает сегодняшним потребностям и преподавание математики в университетах и технических ВУЗах. Тра- диционные вузовские курсы — в первую очередь уже абсолютно застой- ные курсы математического анализа, но в значительной степени также и 13 архаичные курсы линейной алгебры, дифференциальных уравнений, тео- рии вероятностей и дискретной математики — также направлены почти исключительно на механическое овладение рудиментарными вычислитель- ными навыками, без всякого понимания подлинной структуры предмета, его современного состояния и более широкого контекста. В прошлом подобные вычислительные навыки имели несомненную цен- ность, но сегодня необходимость массового обучения им более чем сомни- тельна. Многие разделы математики и вычислительные приемы, которые изучаются сегодня в школе, по своей функциональности в современном ми- ре подобны добыванию огня при помощи трения. Мы не говорим, что это полностью лишает их ценности, вызывает сомнение лишь необходимость систематического упражнения в их применении. Мы провели бы границу следующим образом: появление калькуляторов не отменяет необходимость в заучивании таблицы умножения. Однако появление калькуляторов дела- ет абсолютно бессмысленным систематическое упражнение в опера- циях над многозначными числами — никому из сегодняшних школьников в нормальных условиях не придется выполнять подобные операции вручную, просто потому, что любое, самое примитивное вычислительное устройство делает это быстрее, эффективнее и надежнее. Комментарий. И сегодня в Японии придается чрезвычайно большое значение разви- тию у детей младшего возраста навыков устного счета, вплоть до заучивания наизусть таблицы умножения 100 × 100, что в сочетании с правильным алгоритмом умножения многозначных чисел (разбиение на блоки и замена умножений сложениями и сдвигами) позволяет им легко умножать в уме восьмизначные числа. Однако никто из японских эдукационистов не говорит, что это делается с какой-то практической целью. Един- ственная цель этих упражнений — тренировка памяти и лучшее кровоснабжение мозга. Американские эдукационисты придерживаются противоположной теории, в большин- стве американских школ не учат даже таблицу умножения 10 × 10, а для улучшения мозгового кровообращения используются уроки физкультуры. Из личного опыта мы знаем, что рядовой американский студент не в состоянии перемножить без калькулято- ра 7 на 8. Однако нам трудно решить для себя, как следует относиться к этому факту. 14 § 2. Компьютерная алгебра Одной из первых областей применения компьютерной алгебры бы- ла небесная механика. Классическим примером, упоминаемым во всех обзорах, служит пересчет Депритом, Хенрардом и Ромом ре- зультатов Делоне. Введение новой техники позволило им пере- считать гамильтониан в теории Луны. Делоне потратил 20 лет, выполняя вычисления вручную. Деприту, Хенрарду и Рому пона- добилось всего лишь 20 часов работы небольшой ЭВМ. Следует отдать должное аккуратности Делоне, в работах которого, опуб- ликованных в 1867 году и содержащих результаты вплоть до 9-го порядка по малым параметрам, все было вычислено безошибоч- но, за исключением одного сложения в 7-м порядке. Это вычис- ление лунной орбиты требует тщательного рассмотрения многих физических эффектов, таких как несферичность Земли, наклон эклиптики и влияние Солнца. Гамильтониан, описывающий рас- сматриваемую систему, занимает несколько страниц; к каждому члену нужно применять до 600 преобразований. Я.А.ван Хюльзен, Ж.Калме 2 Появление современных систем символьных вычислений или, как ча- сто говорят, компьютерной алгебры, сокращенно CA (Computer Algeb- ra), ставит — с еще большей остротой — тот же самый вопрос в приме- нении к большинству разделов школьного и вузовского курса математики. Название компьютерная алгебра хорошо отражает суть дела, но не слиш- ком удачно с точки зрения маркетинга и рекламы. Оно создает у несве- дущего человека впечатление, что речь идет исключительно о проведении алгебраических вычислений на компьютере. На самом деле оно указывает лишь на то, что большинство используемых в этих системах алгоритмов основано на использовании методов современной алгебры и теории чисел, предметная же область этих систем гораздо шире, при помощи них можно анализировать все в области нашего опыта и умозрения, что под- дается точному определению. Ядром большинства современных си- стем компьютерной алгебры действительно являются следующие три блока вычислений: • численные вычисления неограниченной точности (так называемые безошибочные вычисления) с целыми, рациональными, вещественными и комплексными числами; • собственно алгебраические (алиас символьные) вычисления с много- членами, перестановками, векторами, матрицами etc.; • логические и структурные манипуляции с высказываниями, последо- вательностями, списками, множествами etc. 2 Я.А.ван Хюльзен, Ж.Калме, Применения компьютерной алгебры. — В кн. Компью- терная алгебра, М., Мир, 1986, с.308–325. Речь в этом отрывке идет о работе A.Deprit, J.Henrard, A.Rom, Lunar ephemeris: Delaunay's theory revisited. — Science, 1970, vol.168, p.1569–1570. Сегодня это вычисление выполняется Mathematica за несколько минут. 15 Однако в действительности кроме этого при помощи систем компьютерной алгебры можно проводить все обычные в математике и ее приложениях аналитические вычисления: • численное и символьное дифференцирование, интегрирование, реше- ние дифференциальных уравнений и уравнений в частных производных и тому подобное; • доказательство несложных теорем, включая доказательство всех тео- рем из школьного курса геометрии; • логическую обработку и преобразование текстов любой природы: текстов на естественных языках, шифров, музыкальных текстов, etc.; • анализ и редактирование изображений, все геометрические и графи- ческие построения — вплоть до создания мультфильмов; • статистическую обработку численных, текстовых, логических и гра- фических данных; • создание баз данных, электронных энциклопедий, интерактивных справочников, учебников и задачников по любой области знания; • математическое моделирование любых процессов, компьютерный экс- перимент; • разработку, тестирование и анализ алгоритмов, компьютерных про- грамм и прикладных пакетов; • и многое другое. Показательно в этой связи, что в США и Западной Европе такие систе- мы компьютерной алгебры общего назначения как Maple или Mathematica имеют даже большее распространение среди физиков, химиков, биологов, инженеров, экономистов и других представителей естественных и матема- тических наук, чем среди собственно математиков. Кстати, профессиональ- ные математики часто предпочитают высоко эффективные сугубо специ- ализированные системы типа Cayley, GAP, MAGMA, Singular, Lie, Chevie, CoCoA, Fermat, PARI, DELiA, GRep, Magnus, Macaulay, Schur, FELIX и дру- гие, направленные собственно на алгебраические или теоретико-числовые вычисления, численные или матричные вычисления неограниченной точ- ности, решение дифференциальных уравнений и все такое, без всякой гра- фики, меню, палитр, мультфильмов и прочих глупостей. Появление систем компьютерной алгебры должно оказать и громадное влияние на преподавание курса информатики. Уже давно стало ясно, что для подавляющего большинства пользователей компьютерная грамотность состоит отнюдь не в навыках программирования, а в умении эффективно ориентироваться в существующих системах математического обеспечения и квалифицировано их использовать. Лучшие же системы символьных вы- числений вообще полностью упраздняют необходимость в традиционном программировании в стиле ПошелНа: If ... Then ... и GoTo ... Де- ло в том, что они являются не компилирующими, а интерпретирующими и 16 сами превращают определение объекта, написанное на языке, по сути до- статочно близком к реальному математическому английскому языку, но с более жесткими правилами синтаксиса (расстановка скобок, знаков препи- нания, прописные и строчные буквы и пр.), в программу для его вычисле- ния. § 3. Влияние компьютеров на математическое мышление Science is what we understand well enough to explain to a computer. Art is everything else we do. Donald Knuth The great advances in science usually result from new tools rather than from new doctrines. Freeman Dyson Mathematics is much less formally complete and precise than computer programs. William P. Thurston To be a scholar of mathematics you must be born with talent, insight, concentration, taste, luck, drive and the ability to visualize and guess. — Чтобы стать профессиональным математиком, нужно родить- ся с талантом, проницательностью, сосредоточенностью, стилем, удачей, настойчивостью, внутренним зрением и воображением. Paul R. Halmos С нашей точки зрения абсолютно не поняты теоретические основы ис- пользования систем компьютерной алгебры в преподавании и исследова- ниях за пределами математики и теоретической физики, а также те из- менения, которые эти системы предполагают в собственно математиче- ском мышлении пользователя. Даже многие авторы учебников по ком- пьютерной математике, не говоря уже о широких кругах пользователей- неспециалистов не отличают настоящие системы компьютерной алгебры, такие как Maple или Mathematica, ни от специализированных пакетов чис- ленных вычислений, таких как MatLab или Statistica, ни даже от чисто учебных программ, графических калькуляторов или систем для работы с текстом, содержащим формулы, таких как Mathcad. В большинстве случаев принятое сегодня изложение математики — не только в школе, но и на математических факультетах университетов — воз- никло в докомпьютерную эпоху и совершенно неудовлетворительно с алго- ритмической точки зрения. Между тем, во многих случаях даже небольшое изменений определений делает их значительно более пригодными для прак- тических вычислений. Скажем, не только в школьном, но и в университет- ском курсе, степень определяется рекурсивно как x n = x n −1 x. Между тем, самое незначительное изменение этого определения может драматически увеличить его применимость. Например, можно определить степень ука- занной выше формулой в случае, когда n нечетно и формулой x n = (x n/2 ) 2 17 в случае, когда n четно. Для объектов, умножение которых занимает за- метное время (матрицы или многочлены высокой степени), вычисление, скажем, 1000-й степени с использованием второго определения может быть в сотни раз быстрее, чем с помощью первого. Заметим, что речь не идет о наиболее эффективном профессиональном алгоритме для вычисления сте- пени — в большинстве случаев достаточно просто задумываться над по- добного рода нюансами. Еще более интересные феномены связаны с умножением матриц. Обыч- ный алгоритм умножения матриц размера 2 × 2 требует 8 умножений ко- эффициентов. Ф.Штрассен предложил алгоритм требующий лишь 7 умно- жений. Для больших степеней этот алгоритм дает еще более драматиче- скую редукцию числа умножений. Примерно так же можно упростить и гауссово исключение. Важность этого открытия трудно переоценить — некоторые специалисты считают его одним из 10 наиболее важных мате- матических открытий XX века. При решении серьезных вычислительных задач (например, при приближенном решении дифференциальных уравне- ний движения, в задачах оптимизации), где приходится умножать и обра- щать тысячи матриц порядка 1000 и более, этот алгоритм дает громадную экономию времени, делающую возможными немыслимые ранее вычисле- ния (NASA использует этот алгоритм при управлении в реальном времени космическими аппаратами). Другой столь же впечатляющий пример, связанный с умножением мат- риц, где четко видна граница между возможным и невозможным — вы- числения в конечных группах. Одним из самых замечательных достиже- ний математики XX столетия явилась классификация конечных простых групп. Как выяснилось, кроме нескольких бесконечных серий таких групп имеется еще ровно 26 “маленьких исключений”, так называемых споради- ческих групп. Самая большая из этих спорадических групп, называемая “Большим Монстром” или “Дружественным Гигантом”, имеет порядок 2 46 · 3 20 · 5 9 · 7 6 · 11 2 · 13 3 · 17 · 19 · 23 · 29 · 31 · 41 · 47 · 59 · 71 и наименьшая степень ее точного матричного представления равна 196883. Умножение двух матриц такого порядка на может оказаться непосильным для лучших современных рабочих станций, поскольку время, необходимое для вычислений в этой группе традиционными методами, на много поряд- ков превосходит возраст Вселенной (кстати, уже просто хранение большого числа таких матриц и результатов промежуточных вычислений в памяти машины представляет собой достаточно серьезную проблему). В то же вре- мя умножение столбца высоты 196883 на матрицу размера 196883 × 196883 требует лишь минут машинного времени и вполне осуществимо, так что в последние годы многие специалисты занимаются разработкой алгоритмов “матричных вычислений без матриц”. Для матриц с полиномиальными коэффициентами подобные эффекты наступают уже значительно раньше, скажем на очень важном с точки зрения приложений в физике случае мат- риц размера 248 × 248. 18 В компьютерной алгебре значительно (бесконечно?) больше математи- ки, чем в традиционном программировании и значительно больше про- граммирования, чем в традиционной математике. В действительности да- же для профессионального математика овладение основными принципами компьютерной алгебры на начальном этапе требует значительного интел- лектуального усилия. Дело в том, что кроме всех обычных математиче- ских операций компьютерная алгебра включает в себя громадное количе- ство структурных операций, связанных с манипуляцией с выражениями, и алгоритмических операций, связанных с управлением ходом вычислений (flow of calculation). Большинство этих структурных и алгоритмиче- ских операций не имеют стандартных названий и обозначений в традици- онной математике. Более того, многие из этих новых операций и прово- димых при их осуществлении различий в классической математике вообще отсутствуют, по крайней мере на сознательном уровне. Поэтому даже для профессионального математика изучение компьютерной алгебры является ценнейшим опытом, который позволяет взглянуть на уже известные ему математические явления совершенно другими глазами: the purpose of travel is not visiting new places, but having new eyes. § 4. Возможности систем компьютерной алгебры. Ленин, как известно, любил гимнастику. Но все же иногда неко- торых тяжестей не осиливал. Так, бывало, схватится за бревно, а поднять от земли — слабо. Виктор Тихомиров. Легенды о революции Say, aliens invade the Earth and threaten to obliterate it in one year's time unless we compute R(5, 5). If we marshalled the world's best minds and fastest computers, then within a year we could probably calculate the value. If the aliens demanded R(6, 6), however, we would be better off preparing for interstellar war. Paul Erd¨ os Воспроизведем из книги Вольфрама (глава “The Limits of Mathematica”) список операций, которые универсальная система компьютерной алгебры такая, как Mathematica, в состоянии за секунды выполнить на современ- ном персональном компьютере. • Производить арифметические операции с целыми числами содержа- щими несколько сотен миллионов десятичных цифр; • Породить миллион десятичных знаков таких чисел, как π или e; • Разложить по степеням многочлен, содержащий миллион слагаемых; • Разложить на множители многочлен от четырех переменных, содер- жаший сто тысяч слагаемых; • Решить систему квадратичных неравенств, имеющую несколько тысяч независимых компонент; • Найти целые корни разреженного многочлена степени миллион; 19 • Применить рекуррентное правило миллион раз; • Вычислить все простые до десяти миллионов; • Найти численную обратную плотной матрицы размера 1000 × 1000; • Решить разреженную систему линейных уравнений с миллионом неиз- вестных и ста тысячами ненулевых коэффициентов; • Вычислить определитель целочисленной матрицы размера 250 × 250; • Вычислить определитель символьной матрицы размера 25 × 25; • Найти приближенные значения корней многочлена степени 200; • Решить разреженную задачу линейного программирования с несколь- кими сотнями тысяч переменных; • Найти преобразование Фурье списка из миллионов элементов; • Изобразить миллион графических примитивов; • Отсортировать список из десяти миллионов элементов; • Найти фрагмент в строке из десяти миллионов знаков; • Загрузить несколько десятков мегабайт численных данных; • Отформатировать сотни страниц вывода в традиционной форме. По этому поводу стоит отметить несколько обстоятельств. Прежде все- го стоит указать, что производительность другой high-end системы, Maple может незначительно отличаться в ту или иную сторону, но в любом случае, время выполнения тех же задач в Maple также измеряется несколькими се- кундами. Тем самым, Mathematica и Maple могут решить любую задачу, которая может реально возникнуть у нематематика, за half no time, и вы- бор между ними не может определяться никакими практическими сообра- жениями, а диктуется исключительно индивидуальными предпочтениями. Поскольку MatLab Extended Symbolic Math Toolbox представляет собой клон Maple, от него также можно ожидать сопоставимой производительно- сти (при несколько большем, чем собственно у Maple, расходовании систем- ного ресурса). Разумеется, на рабочих станциях с несколькими гигабайта- ми оперативной памяти под операционной системой типа UNIX, из всех этих систем можно выжать гораздо больше! – количественные характеристики, актуальные для вашего компьютера можно получить в системе помощи Mathematica в разделе Wolfram System Information \ Benchmark. От себя добавим в этот список еще один пункт, который Вольфрам не включил ввиду полной очевидности: • Решение всех вычислительных задач по математике, которые были выполнены за 15 лет обучения математике в школе и университете. Подчеркнем, что в этом пункте речь идет о вычислительных задачах — таково подавляющее большинство задач, предлагаемых школьникам и сту- дентам. Кроме того, разумеется, учитывается только собственно время работы CPU, без ввода условий задач с клавиатуры и вывода на экран. Комментарий. Интересно отметить, что решение задач “на доказательство” требует в сотни раз больше времени. Дело в том, что единственным систематическим методом 20 доказательства геометрических фактов является введение координат, истолкование гео- метрических теорем как задач вещественной алгебраической геометрии и последующее применение полиномиальных алгоритмов, связанных с базисами Гребнера. Известно, что уже при нескольких десятках переменных проверка принадлежности многочлена идеалу может представлять собой достаточно серьезную задачу. С другой стороны, легко придумать и чисто вычислительные задачи, которые поста- вят в тупик любой современный компьютер и любую систему компьютерной алгебры. Такова, например, задача разложения на множители целого числа со 100 цифрами. Во- обще, стоит иметь в виду, что увеличив объем вычислений в задаче, на решение которой требуется несколько секунд, всего в тысячу раз, мы получим задачу, на решение кото- рой требуется час, а в миллион раз — несколько месяцев. При росте объема вычислений всего в миллиарды раз на ее решение потребуются уже столетия! Поэтому полезно по- нимать, хотя бы в самых общих чертах, как при росте объема данных или значений параметров растет объем вычислений. § 5. Об “ошибках” систем компьютерной алгебры At the source of every error which is blamed on the computer you will find at least two human errors, including the error of blaming it on the computer. The Tao of Real Programming It seems that creating man God has grossly overestimated his abilities. Oscar Wilde Не только газета, но и короткая запись где-нибудь на стенке в местах общего пользования иногда дает сильный толчок вообра- жению. Виктор Конецкий, Никто пути пройденного у нас не отберет Многие критики введения компьютерной алгебры в преподавание, часто упоминают об “ошибках”, встречающихся в подобных системах. С нашей точки зрения, все слухи о таких ошибках основаны на устаревшей инфор- мации и носят чисто пропагандистский характер, а люди, выдвигающие по- добные аргументы, либо не владеют реальной ситуацией, либо сознательно лицемерят. Разумеется, компьютеру свойственно ошибаться, этим он мало отлича- ется от бога. Следует отдавать себе отчет, что определяющим является не возможность наличия ошибок, а вероятность их осуществления и, в особен- ности, их этиология. Следует четко отличать несколько причин ошибок: 1. Ошибки системы. Часть ошибок относится на счет самих систем компьютерной алгебры. • Ошибки в математике и алгоритмах, использованных в системах компьютерной алгебры. Такие ошибки возможны, но исключительно ма- ловероятны. Например, было обнаружено, что первые версии систем Maple или Mathematica неправильно считают некоторые интегралы. Выяснилось однако, что ошибки в таблицах интегралов! 21 • Программистские ошибки в системах компьютерной алгебры также возможны, но для коммерческих систем, прошедших многолетнее тестиро- вание и имеющих миллионы пользователей, крайне маловероятны. • Конфликты с операционной системой и другими приложениями. Известно, что в начале и середине 1990-х годов использование систем ком- пьютерной алгебры на бытовых компьютерах очень часто приводило к си- стемным ошибкам и коллапсу системы. Основная причина этого состояла в том, что когда такой системе не хватало памяти для записи результатов промежуточных вычислений, она начинала писать их поверх собственного ядра и даже поверх системных файлов Windows. Однако никто не слы- шал про подобные явления для Unix'овских рабочих станций, так что все подобные конфликты следует рассматривать не как дефект систем компью- терной алгебры, а как изъян операционной системы. Кроме того, начиная с Windows NT эта проблема устранена. Мы уверены, что если даже ошибки в таких системах, как Maple и Ma- thematica и имеются, то вероятность встретиться с ними настолько мала, что ей можно полностью пренебречь. 2. Ошибки пользователя. Гораздо более вероятными представляются нам ошибки, допущенные самим пользователем. Значительная часть этих ошибок ничем не отличается от ошибок, возникающих при любой попытке программирования математических задач. • Опечатки. Известно, что из каждых двадцати символов, введенных человеком с клавиатуры компьютера, по крайней мере один является оши- бочным. Опечатка в одном символе в большинстве случаев либо делает вы- ражение бессмысленным, либо приводит к вычислению совершенно не того, что имелось в виду. В отличие от многих примитивных языков програм- мирования в больших системах компьютерной алгебры прописные буквы отличаются от строчных. Таким образом, TexForm значит совсем не то же самое, что TeXForm. Однако в подобных случаях эти системы предупре- ждает о возможных опечатках: possible spelling error. • Синтаксические ошибки. Сюда относится любая попытка вычис- лить выражение, составленное с нарушением правил языка. Типичными ошибками такого рода являются несбалансированность выражений, вызов в них функций с неправильным числом аргументов или аргументами непра- вильных форматов, и многое другое. Большая часть этих ошибок момен- тально обнаруживается, так как система просто откажется вычислять син- таксически неправильное выражение. • Программистские ошибки. Типичные программистские ошибки, возникающие при использовании систем компьютерной алгебры, это ис- пользование переменных, которым не были присвоены значения, либо ис- пользование старых значений переменных, несогласованность форматов, выясняющаяся при вычислении (т.е. не на лингвистическом, а на семанти- ческом уровне) и многое другое. В большинстве случаев подобного рода ошибки либо порождают сообщение об ошибке, либо приводят к бесконеч- 22 ной рекурсии. Однако в некоторых случаях (в особенности при использова- нии старых значений переменных!!) могут возникать чрезвычайно трудно отслеживаемые невоспроизводимые ошибки. Имеются несколько стандарт- ных приемов: чистка и локализация переменных, явное задание начальных значений всех используемых итераторов и т.д., которые позволяют резко уменьшить вероятность возникновения неотслеживаемых ошибок. Кроме того, как всегда, правильно вначале тестировать любую написанную про- грамму на совсем простых примерах. Если Вы хотите вычислить 10000!, убедитесь вначале, что написанная Вами программа правильно вычисляет 3! – большинство ошибок будет обнаружено уже на этом этапе. • Математические ошибки. На начальном этапе программирования на языках компьютерной алгебры чрезвычайно велика вероятность возник- новения математических ошибок. Впрочем, такого рода ошибки харак- терны для начального этапа любой попытки уточнения понятий и их пере- вода с одного языка на другой. Типичными ошибками такого рода явля- ются неправильное определение порядка выполнения операций, неправиль- ная интерпретация функций и т.д. После нескольких месяцев интенсивного использования системы и выработки устойчивого навыка тестировать все программы на легко проверяемых примерах, количество подобных ошибок резко снижается. Однако, с нашей точки зрения перечисленные в этом пункте ошибки не являются специфичными для компьютерной алгебры, а возникают в любом вычислении достаточно большого объема. / 3. Непонимание основных принципов компьютерной алгебры. Ос- новным и с нашей точки зрения наиболее серьезным источником ре- альных ошибок является незнание и/или непонимание основных принципов организации вычислений в системах компьютерной алгебры. В первую очередь это относится к следующим моментам: • Непонимание разницы между формой и значением выраже- ния. В отличие от всех традиционных вычислительных систем, системы компьютерной алгебры производят вычисление с формой выражения, а не только с его значением. Это значит, что, система тщательно различает не только сами объекты, но и их имена, имена имен, имена имен имен, и т.д. Например, с точки зрения внутреннего представления данных в системе, выражения (x + 1)(x − 1) и x 2 − 1 следует рассматривать как абсолютно различные!!! Скажем, неосторожно использовав условный оператор If[(x+1)*(x-1)==x^2-1,1,0], не следует надеяться получить в ответе 1. А вычисление If[(x+1)*(x-1)===x^2-1,1,0] и вовсе вернет 0. • Применение правил преобразования. Системы компьютерной ал- гебры автоматически производят некоторые типы преобразований, но не производят других типов преобразований. В большинстве случаев у кон- структоров систем были чрезвычайно серьезные принципиальные и/или 23 практические основания для принятия подобного рода решений. В то же время не только начинающий, но даже профессиональный программист, не знакомый, однако, со спецификой символьных вычислений, скорее все- го, не осознает разницу между, скажем, применением ассоциативности и применением дистрибутивности, и исходит их того, что система должна проводить вычисление так же, как это делал бы в аналогичной ситуации человек. При некотором опыте в большинстве случаев этого действительно можно добиться. Однако то, что системы компьютерной алгебры не всегда делают то, что от них ожидают, совсем не означает, что они бесполезны!!! • Использование приближенных вычислений. Приближенные вы- числения представляют собой меч без ручки и проводящий их вынужден держаться за лезвие. Серьезнейшей концептуальной ошибкой, лежа- щей в основе большинства реально описанных случаев, когда проведение вычисления приводило к неправильному ответу, является применение приближенных вычислений к задачам с точными условиями. За- дачи с точными условиями должны обрабатываться только безошибочными алгоритмами. Никаких округлений в процессе вычисления производиться не должно, округляться может только окончательный ответ. Точно так же, приближенные вычисления (без контроля точности) внутри рекуррентной или итеративной процедуры в большинстве случаев абсолютно бессмыслен- ны и с необходимостью приводят к ошибочному результату 3 • Разбухание промежуточных выражений. Начинающий обычно не знает, в какой форме задавать вопрос, и пытается вывести на экран то, что с точки зрений целей вычисления является промежуточным выра- жением. Например, в действительности его интересует длина некоторого списка, но он пытается вывести сам этот список. Так как форматирование ответа для его вывода на экран в большинстве случаев занимает значи- тельно больше времени, чем само вычисление, такое поведение снижает эффективность использования систем компьютерной алгебры, и даже де- лает невозможным решение некоторых типов задач, которые при грамот- ной постановке вопроса и/или организации вычислений решаются за доли секунды. 3 Совершенно поразительные примеры численной неустойчивости, замечательно ил- люстрирующие эту мысль, приведены в статье О.А.Иванов, Современная математика в школьных задачах. — Соросовский Образ. Ж., 2000, т.6, N.6, с.1–7. |