Докладчик: Николай Николаевич Непейвода (ИПС им. А.К. Айламазяна РАН)
Дата: 10 октября 2014
Время: 13:00
Место: зал ученого совета ИПС
Презентация:
Скачать
Аннотация:
Ещё в 1938 г. Банах и Мазур доказали, что нет алгоритмов сложения и умножения чисел, представленных в традиционной позиционной системе. В других предположениях этот же факт установил Л. Брауэр в 1922 г., одновременно предложив "двоичное" представление с перекрывающимися "разрядами": отрезок от 0 до 1 делится на интервалы от 0 до 2/3 и от 1/3 до 1, каждый из них по такой же схеме ещё на два и так далее. Такое представление неоднозначно, зато действия вычислимы.
В докладе представлены следующие результаты.
- Дано общее определение брауэровой системы представления действительных чисел и доказана вычислимость всех алгоритмических функций в любой такой системе.
- Показано, что сложение в двоичной брауэровой системе осуществляется за 2-3 такта, а в троичной за 1-2, и последнюю оценку не удаётся уменьшить в других брауэровых системах.
- Показано, что, если при переводе в брауэрову систему с перекрытием отрезков не менее чем на 1/2 длины каждого из них выбрать аккуратное представление (такое, где расстояние для каждого знака числа от конца интервала, в который входит число, не менее половины перекрытия), то сложение вычисляется полностью параллельно за один такт, без переносов.
Ставятся нерешённые задачи.