С.В.Дужин.
Программа курса "Алгоритмы непрерывной математики".
Осенний семестр 1998-99 года. УГП

• Алгоритмы в алгебре. ([0],[1])
  • Идеалы и точки.
  • Алгоритм Бухбергера.
  • Алгоритм решения систем полиномиальных уравнений.
  • Алгоритм Штурма.
• Алгоритмы в геометрии. ([0],[2],[3],[4])
  • Алгоритмы построения выпуклой оболочки.
  • Алгоритмы изображения пространственных фигур на плоскости.
  • Кривые Безье.
  • Диаграмма Вороного.
  • Триангуляция Делоне.
  • Симплекс-метод.
• Алгоритмы в топологии. ([0],[5],[6])
  • Определение типа двумерной поверности.
  • Алгоритм расплетания кос.

Образцы задач

• 1. Провести редукцию данного многочлена относительно данной системы многочленов при заданном порядке на мономах.
• 2. Применяя алгоритм Бухбергера, построить базис Гребнера данной системы многочленов.
• 3. Дана система полиномиальных уравнений с несколькими неизвестными. Вывести из нее уравнения на каждую переменную отдельно.
• 4. Дан многочлен от одной переменной. Найти число корней на данном отрезке.
• 5. Дано множество точек на плоскости. Построить границу выпуклой оболочки.
• 6. Дана фигура в пространстве. Описать ее проекцию на плоскость (а. центральную с данным центром, б. параллельную с данной осью)
• 7. Построить кривую Безье по данной системе опорных точек.
• 8. Построить диаграмму Вороного и триангуляцию Делоне для данного набора точек плоскости.
• 9. Найти минимум данной линейной функции на данном выпуклом многограннике, используя симплекс-метод.
• 10. По данной нумерованной триангуляции определить топологический тип двумерной поверхности.
• 11. Коса задана словом в алфавите a_i, a_i^{-1}, где a_i -- образующие группы кос. Определить, эквивалентна ли она тривиальной косе.
• 12. Даны две косы. Определить, эквивалентны ли они между собой.

Компьютерные навыки

• 1. Пользоваться системой Maple как суперкалькулятором.
• 2. Писать простые программы на C/C++.

Литература