City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Устойчивая реализация алгоритмов вычислительной геометрии (Антон Ковалев, Транзас, СПбГУ ИТМО)
Seminar on Computer Science

What: Lecture
When: Sunday, 23 October 2011, 15:35–17:10
Where: ПОМИ РАН
Slides: csseminar_lecture_231011.pdf

Description

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

Существует несколько известных приемов эффективной организации точных вычислений. Об одном из этих приемов, фильтрованном вычислении предикатов, и пойдет речь в данном докладе.

Список ключевых тем для обсуждения:

  • особенности арифметики с плавающей точкой;
  • подсчет погрешности арифметических выражений;
  • особенности организации интервальной арифметики (interval arithmetic);
  • арифметика произвольной точности на числах с плавающей точкой (adaptive precision floating-point arithmetic).

Video