Сергей Самойленко @samsergey
Руководитель, научный сотрудник, преподаватель
Information
- Rating
- Does not participate
- Location
- Петропавловск-Камчатский, Камчатский край, Россия
- Date of birth
- Registered
- Activity
Руководитель, научный сотрудник, преподаватель
Это, кстати, не так сложно.
Перепишем ОДУ второго порядка
f′′ = –f
в систему:
f′ = –g, g′ = f
и рассмотрим свойство выражения:
f² + g². Мы знаем только как меняется скорость наших функций f и g, так что давайте посмотрим на скорость изменения этой суммы:
(f² + g²)′ = 2ff′ – 2gg′ = –2fg + 2gf = 0.
Нулевая скорость изменения этих выражений говорит о том, что эта сумма является константой. Выбрав такие начальные условия, чтобы f(0) = 1, а g(0)=0 получаем, что эта константа равна единице.
Кроме того, можно показать, что что если какое-либо из решений системы имеет хотя бы один максимум, то обе эти функции должны иметь бесконечное множество минимумов и максимумов, причём экстремальное значение одной функции обязательно соответствует нулю другой.
Неплохая статья, правда! Но, как любитель математики не могу не прокомментировать этот пассаж:
Проблемы с решением этой задачи кроются не столько в математике, сколько в формулировке самой задачи. Что такое "конечная форма" и "аналитическое решение"? В какой именно конечной форме ищется решение, в каком поле? И тут открывается классный путь в теорию полей и трансцедентных чисел, на мой взгляд, не менее увлекательный, чем экскурс по миру метрик!
Что же до "зависимости тригонометрических функций от метрики", соглашусь с комментарием выше: тригонометрические функции, синусы и косинусы, фундаментальнее геометрии, из которой они вышли. Они являются решением важных дифференциальных уравнений (линейных второго порядка), образуют ортонормированный басис в гильбертовом пространстве (поэтому работает преобразование Фурье), кроме того, внутренняя структура этих функций глубоко связана с группой, образуемой операцией умножения в поле комплексных чисел. А то, что через них напрямую выражаются отношения в прямоугольном треугольнике, является свойством Евклидовой геометрии, а это лишь одна из многообразия возможных геометрий.
Я пишу это не чтобы позанудствовать, а чтобы показать, сколько ещё интереснейших направлений исходит от этой задачи в различные области математики!
Обожаю эту могучую "реальность", в которой всё всегда не так, как на самом деле :) Если бы реальность сопротивлялась моделированию с помощью математики, мы бы строили иную математику. Пока всё, имеющее смысл, сходится. Споры с привлечением "реальности", чаще всего, возникают вокруг утверждений смысла не имеющих.
Таких конструктивных вопросов было два. Из 42 комментов про "пользу" и "несовершенство" :)
Комментарии напомнили знаменитый анекдот про японскую лесопилку и суровых сибирских мужиков.
Интереснейшая задача, человек вплотную подошел к её реальному решению, рассказал как он это сделал и полностью открыт для общения со спецами, но! Самым интересным для уважаемых спецов оказалось тыкать в робота палкой, до тех пор, пока он не сломается, а потом гордо сказать: "ага!!" :)
Поздравляю автора с отличной задачей и классной реализацией! Уверен, что вы с сыном получили то, что искали: и пользу и удовольствие. А сын ещё и получил возможность восхититься тем, на что способны математика и папа!
В то время, как тыкатели палками могут гордиться тем, что они могут сломать что угодно, доказывая тем самым превосходство человека "над системой" :)
К сожалению, автор попадает в ловушку "убийства дракона": пытаясь победить формализм исходя из соображений "реальности" и "практической полезности", он теперь вынужден создать новый формализм, причем по всем правилам. Без четкой аксиоматики, без доказательства того, что новая система является полем, использовать её наряду с числами нельзя. Кроме того, похоже, что в этой системе есть нетривиальные делители нуля, а значит, она полем не является, значит неизбежны проблемы с единственностью разложения на множители и сокращениями при делении. Самое же главное, дракон, с которым сражается автор, столь же нереален и далёк от практики, как и указанная в самом начале "проблема формальной математики". Даже сугубо реалистичной инженерной физике никогда не мешали ограничения, накладываемые на операции с числами теорией полей, а, напротив, помогали познавать и моделировать сущности. Анализ размерности — прекрасный инструмент инженера, теория групп — инструмент теорфизика, теория конечных полей, типов и категорий — инструмент программиста. Возможно, предлагаемый здесь формализм может стать одним из таких инструментов, но пока я вижу в нём больше противоречий (указанных уже комментаторами выше), чем может позволить себе теория.
К слову, если статья на математическую тему начинается с упоминания теоремы Гёделя о полноте, это сильный признак её нематематичности. А если она, к тому же, переключается на вопросы "практичности" математики, то материал, скорее всего, не интересен и не полезен.
Лучше оставить в покое Гёделя, и построить стройную непротиворечивую аксиоматику, с выводом основных положений, типа теоремы Безу, основной теоремы арифметики и т.п. А если уж так хочется "полезности", показать пример приложения новой системы за пределами возможностей уже известных.
Конечность, строго говоря, не обязательна:
\ dev\null
тому пример. И вы правильно определили основные структуры, присущие файлу, как математическому объекту.Это называется проблема поиска денотационной семантики. Работа в этом направлении идёт и далека от завершения. Для многих это жуть жуткая и муть мутная, каждый день не нужная. Но для тех кто пишет компиляторы и верификаторы это крутой инструмент.
А файл (POSIX) можно отождествить с анаморфизмом, порождающим свободный моноид, его обработчики — с гиломорфизмами. Файловая система — дерево, или более общий граф, если она реляционная и т.п. Мы используем эти понятия, не зная, что "говорим прозой".
И хотел бы добавить, современная математика огромна. Не торопитесь судить о ней в терминах "никакая математика не определит"… Например, о трех табуретках: теория устойчивости, даже линейная удовлетворительно отличит одно применение от другого.
Ну, скучно же, ребята!!! Один пишет про ошибки, допущенные другим в статье про ошибки третьих… спор о том, кто больше неправ продолжился в комментариях. Ну неправ, и что? Лучше бы написали о каком-нибудь крутом и красивом решении, которое показывает как XXX парадигма расширяет наш инструментарий, да с примерами, да так чтобы захотелось попробовать! А то "тут ООП, тут не ООП..." Как говорил Жванецкий: "Воруйте с прибылей!"
Ну да, но их же нужно откуда-то брать. И при этом не забивать память гигами нулей и единиц, используя решето, и не тратить на это даже секунды. Я далёк от теории чисел, но понимаю, что есть более эффективные способы, хотя бы, вероятностные — генерим случайное большое число и тестируем каким-нибудь Миллером-Рабином.
Я имел в виду не задачу криптографии в целом, а генерацию простых чисел (если таковая, действительно ставится при факторизации больших чисел, опять же, могу напутать по незнанию). Эта генерация, по существу, чиста и может быть встроена в чистый код, но имплементирована может быть как угодно, лишь бы эффективно. Впрочем, тут мне лучше умолкнуть.
Это да. Мне хотелось продемонстрировать не столько чистое ФП, сколько его выразительность и гибкость. Если требуют решето именно Эратосфена и именно двойным циклом и именно с вычёркиваем, то… и это можно.
А так, есть классные функциональные решения тут и тут. Но они уже не совсем то решето, о котором обычно рассуждают.
Для своих нехитрых нужд я бы взял ваш однострочник и не заморачивался. Для криптографии какой-нибудь — быстрый императивный код через FFI, но я в ней мало смыслю, если честно.
Кормящим матерям и путникам не возбраняется :)
Спасибо, это, действительно, многовато для комментария. Пройдёмся по вашим вопросам.
var
), как раз часто требует уточнения, поскольку в Haskell выражение5
может означать либо целое число, либо число с плавающей точкой, либо, вообще, какой-нибудь тип-обертку типаSum
илиMax
. Компилятор очень постарается понять из контекста, что же это такое, но программист может его здорово запутать :)Немного прокомментирую это решение. Я использовал
Data.Vector.Unboxed.Mutable
только для эффективности. От этой структуры здесь лишь конструкторM.replicate
и функции доступаM.read
bM.write
. На месте этой структуры могли быть немутабельные векторы, Array (или даже список со всеми вытекающими проблемами эффективности). Программа и её результат бы от этого не изменились, только сигнатура. И то, её я не писал вручную, мне рассказал о ней компилятор :)Именно этот выбор определил то, что результат будет "жить" в IO. Но ровно эту же программу можно погрузить в чистую ST, в любом случае, она принципиально императивна, что не помешало мне реализовать её в Haskell.
Циклы реализованы через рекурсию, вполне прямолинейно, в виде хвостового вызова. Из магии только монадические штучки
>>
и>>=
, которые можно рассматривать как пайпы.И, наконец, я нарочно написал тело цикла
sieve
так, чтобы он "выглядел" как изменение переменнойm
, чтобы показать, что если уж мы мыслим наш алгоритм императивно, то его можно и выразить императивным кодом, не изменяя принципам ФП. Мы не монахи и императивность не грех, если всё делать аккуратно, с благословения компилятора.В бенчмарке использовался вариант с преобразованием в список, чтобы честно. Оно добавило константу, но оставило асимптотику.
Вот решение, вполне прямолинейное и наивное.
заполняет массив значениями
True
иFalse
согласно оригинальному замыслу, в двух вложенных циклах (sieve
иfill
). Сигнатура страшная, но алгоритм прост как пробка.Если надо список простых чисел (индексы со значениями
True
), то можно написать такое:Результаты прогона на ноуте (сплошная линия — n*log(log(n))):

Да,
main
не функция. Сказывается привычка :) Это точка входа — выражение, которое вычисляется при запуске программы.Ага! спасибо, посмотрю, operational переводится лучше, но они не тождественны, а связаны через
Coyoneda
. Интересно, сам Олег Киселёв как их называет?Придется, но это, правда, не "очень сложно"!
Мне импонирует ваше стремление разобраться! Переменное состояние и сайд-эффекты в ФП исключены вовсе не ради инкапсуляции, вернее не только ради неё. Если мы готовы принять это ограничение, то становятся возможными:
var
илиauto
, поскольку он проникает на все уровни программы от сигнатуры функции до самых мелких её деталей. И это не для экономии нажатий клавиш при определении функции, а для настоящей и осознанной типобезопасности. Компилятор в чистых типизированных ФЯП не тестировщик и не надзиратель, а друг и помощник, подсказывающий и объясняющий программисту даже не в чём состоит ошибка, а что ему писать дальше. Это не автодополнение IDE доступных полей и методов, а подсказка сложных и очень нетривиальных решений, которые потом могут превратиться в научные разработки. Это круто и от этого уже трудно отказаться!Отсутствие сайд-эффектов и переменных не цель ФП, а средство достижения гораздо больших целей. И, более того, если надо, я всегда могу их себе завести, но они гарантированно будут локальными и с тонко настраиваемой семантикой.