на школьную страницу...
Что общего между крылом самолета и
движением руки робота?
И крыло самолета, и движение руки робота и даже человека
можно описать алгебраическими уравнениями, то есть уравнениями типа: многочлен(от нескольких переменных)=0.
Множество точек, заданное системой алгебраических уравнений,
образует поверхность или кривую или их комбинацию.
Все это называется многообразием.
Портновские лекала, например, составлены из отрезков кривых третьего порядка.
А крыло автомобиля - из частей поверхностей третьего порядка.
Однако, в современной компьютерной графике поверхности составляют из
кусочков простейших многообразий - плоских треугольников, и потому, для получения приемлемого результата их требуются сотни тысяч.
А вот если бы поверхность аппроксимировали участками многообразий третьего порядка,
хватило бы и сотни кусочков, но работать с поверхностями 3-го, даже 2-го порядков,
графические программы еще не научились.
Изучением многообразий занимается алгебраическая геометрия.
Системы алгебраических уравнений решают последовательным исключением переменных,
приводя ее к специальному удобному виду.
Полученный набор многочленов называется базисом Гребнера.
Первый алгоритм нахождения базиса Гребнера придумал австриец
Бруно Бухбергер еще в 60-х годах прошлого века, но реализация алгоритма Бухбергера стала возможной
лишь с появлением достаточно мощных компьютеров.
Усовершенствованный вариант этого алгоритма используется в современных
системах КОМПЬЮТЕРНОЙ АЛГЕБРЫ.
К сожалению, в огромном количестве практически важных случаев этот алгоритм работает
недопустимо долго.
В 1999 году француз Жан-Шарль Фожер придумал удивительно быстрый алгоритм F4
(а затем и улучшенную версию F5).
Однако, Фожер не раскрыл тайн своего алгоритма, а за большие деньги разрешил
включить его в систему компьютерной алгебры MAPLE.
