А. Бешенов (АУ)

Полуалгебраические множества и цилиндрическое алгебраическое разбиение. Часть I

Полуалгебраические множества представляют собой вещественные решения
систем полиномиальных уравнений и неравенств. Очень важный факт
устанавливает теорема Тарского--Зайденберга: всякая проекция
полуалгебраического множества также является полуалгебраическим
множеством. Это означает, что для вещественных чисел и сигнатуры (=,
<, 0, 1, +, *) возможна элиминация кванторов.

Оказывается, всякое полуалгебраическое множество можно представить в
виде несвязного объединения конечного числа частей, полуалгебраически
гомеоморфных открытым гиперкубам (0,1)^d различной размерности. Это
можно получить при помощи цилиндрического алгебраического разбиения
(cylindrical algebraic decomposition, CAD). Я расскажу об алгоритме
CAD и его применении.

Сюжет лежит где-то в пересечении алгебры, геометрии, логики и алгоритмов.

Конспект:
http://cadadr.org/au/alg-alg/sag-cad-intro.pdf