Задача хоть и неожиданная, но довольно простая. Прямо вот без дураков, можно давать на кружке детям почти любого возраста.
Докажите, что в любом вещественном отрезке [a,b] найдется ровно одно рациональное число p/q с минимальным |p|+|q|.
Однако забавно, какое неожиданное применение есть у этого факта. В области компьютерной проверки математических результатов бывает полезно иметь точный тип вещественных чисел. Не float'ы какие-то поганые, а вот именно точное представление R. Например, вещественные числа можно определять функциональным образом.
Для этого можно использовать функциональный аналог последовательностей Коши: регулярные функции (термин overused, но увы, не я его придумал). Регулярная функция - это функция f : Q_+ —> Q. Мы говорим, что такая функция представляет вещественное число a, если f(e)∈[a-e,a+e] для любого e. Иными словами, функция хранит рациональные приближения вещественного числа с любой наперед заданной точностью.
С такими объектами вполне можно жить: определить, какие регулярные функции эквивалентны (проверка вещественных чисел на равенство), определить арифметику, порядок, в общем, все то, что происходит на первых лекциях по матану. Все эти процедуры символьные, а потому эфемерные. Однако, если есть необходимость реально что-то посчитать с нужной точностью, то это можно запустить по настоящему: все вычисления сведутся к арифметике рациональных чисел.
Поскольку сложность точной арифметики с дробями растет очень быстро относительно размера числителей и знаменателей, осмысленно у рац.чисел минимизировать |p|+|q|. Поэтому полезно на все регулярные функции навесить "аппроксиматор", который не просто выдает рац.число f(e)∈[a-e,a+e], а именно то рац. число, на котором минимизируется |p|+|q| в указанном интервале. С точки зрения функционально-символьной это не сильно усложняет жизнь, процедура вычислимая. Зато упрощает реальные вычисления.
Например, математически было бы естественно хранить вещественное число 6000000/3000001 в виде постоянной регулярной функции, которая выдает его самое при любом e. Но с точки зрения оптимизации, при e>0.000001, можно положить f(e)=2/1, - при грубых округлениях и так сойдет.
Мне кажется, тут можно клевых задач напридумать про свойства наипростейших рациональных приближений и какой эффект эти свойства оказывают на реальную сложность арифметики вещественных чисел в функциональных вычислениях.
Подробности см. O'Connor, A Monadic, Functional Implementation of Real Numbers.
PS. Мне вк написали, что числа, которые получаются описанным образом - это наилучшие рац.приближения. Видимо, так оно и есть.
Комментариев нет:
Отправить комментарий