Pull to refresh
307
77
Сергей Самойленко @samsergey

Руководитель, научный сотрудник, преподаватель

Send message

Знакомство с p-адическими числами. Часть 2, практическая

Reading time13 min
Views5.6K


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


Мы поговорим об эффективном внутреннем представлении p-адических чисел, о базовых алгоритмах и методах работы с ними, а также о двух классных инструментах в системе типов языка Haskell: о типах-литералах (type literals) и семействах типов (type families).

Читать дальше →
Total votes 13: ↑13 and ↓0+13
Comments1

Знакомство с p-адическими числами. Часть 1

Reading time19 min
Views20K

Иллюстрация сложения в p-адической топологии (E. Harriss and R. Nelson)
Изображение с сайта Mathematical Art Galleries


В этой серии из двух статей я приглашаю вас заглянуть в один любопытный и не самый популярный уголок математики, в котором обитают необычные создания — p-адические числа, а попутно хочу рассказать о написанной мной Haskell-библиотеке для работы с ними, а также о двух классных инструментах: о типах-литералах (type literals) и семействах типов (type families), приближающих нас к заветным зависимым типам.


Я люблю язык Haskell и, начиная с какого-то времени, мне стало комфортно думать на нём, особенно, на математические темы. Когда понадобилось освоить новый инструмент, — p-адические числа, оказалось, что в репозитории hackage, основном для Haskell-сообщества, нет инструментов для работы с ними, даже в таких серьёзных теоретико-числовых библиотеках, как arithmetic, arithmoi или factory. В конце концов, я написал и опубликовал свой модуль padic, и во второй части этой серии расскажу о некоторых деталях его реализации. А сейчас речь пойдёт о самих p-адических числах.

Читать дальше →
Total votes 38: ↑38 and ↓0+38
Comments14

Элегантный вопросительный знак

Reading time20 min
Views6K

В этой заметке я хочу поделиться элегантным решением одной задачи с сайта-хрестоматии RosettaCode. Речь пойдёт о программе, вычисляющей функцию Минковского — одного из инструментов теории чисел и динамических систем. Несмотря на то, что реализовать эту функцию относительно несложно (её код даже приводится в Википедии), имеет смысл подняться на достаточно высокий уровень абстракции, для того, чтобы увидеть предельно простое решение этой задачи. Ну, и получить удовольствие от красоты математики и языка Haskell.

Этот рассказ может быть интересным тому читателю, кто подобно мне, радуется обнаруживая "автомагические" решения, в которых точно подобранные структуры и абстракции, при помощи содержащейся в них математической основы, решают задачу как бы сами собой, гарантируя корректность этого решения.

Сначала мы обсудим саму функцию Минковского, потом разглядим в её действии изоморфизм между двумя алгебраическими структурами и уже с этих позиций напишем короткую программу на Haskell, и, конечно, обсудим что нам с этого всего будет.

Читать далее
Total votes 24: ↑24 and ↓0+24
Comments15

Аппликативные регулярные выражения, как свободный альтернативный функтор

Reading time21 min
Views8K

Предлагаю вашему вниманию перевод замечательной свежей статьи Джастина Ле. В своём блоге in Code этот автор достаточно легким языком рассказывает о математической сути красивых и изящных функциональных решений для практических задач. В этой статье подробно разбирается пример того, как перенос математической структуры, которую образуют данные в предметной области на систему типов программы, может сразу, как писали Джеральд и Сассман "автомагически", привести к работающему решению.


Приведённый на картинке код — это полноценная самодостаточная, расширяемая реализация парсера регулярных выражений, написанная "с нуля". Высший класс, настоящая магия типов!

Читать дальше →
Total votes 31: ↑30 and ↓1+29
Comments5

Теория счастья. Статистика, как научный способ чего-либо не знать

Reading time22 min
Views21K
Продолжаю знакомить читателей Хабра с главами из своей книжки «Теория счастья» с подзаголовком «Математические основы законов подлости». Это ещё не изданная научно-популярная книжка, очень неформально рассказывающая о том, как математика позволяет с новой степенью осознанности взглянуть на мир и жизнь людей. Она для тех кому интересна наука и для тех, кому интересна жизнь. А поскольку жизнь наша сложна и, по большому счёту, непредсказуема, упор в книжке делается, в основном, на теорию вероятностей и математическую статистику. Здесь не доказываются теоремы и не даются основы науки, это ни в коем случае не учебник, а то, что называется recreational science. Но именно такой почти игровой подход позволяет развить интуицию, скрасить яркими примерами лекции для студентов и, наконец, объяснить нематематикам и нашим детям, что же такого интересного мы нашли в своей сухой науке.


Речь в этой главе пойдёт о статистике, о погоде и даже о философии. Не пугайтесь, совсем чуть-чуть. Не более того, что можно использовать для tabletalk в приличном обществе.




Читать дальше →
Total votes 28: ↑28 and ↓0+28
Comments16

Теория счастья. Головокружительный полёт бутерброда с маслом

Reading time21 min
Views13K
Продолжаю знакомить читателей Хабра с главами из своей книжки «Теория счастья» с подзаголовком «Математические основы законов подлости». Это ещё не изданная научно-популярная книжка, очень неформально рассказывающая о том, как математика позволяет с новой степенью осознанности взглянуть на мир и жизнь людей. Она для тех кому интересна наука и для тех, кому интересна жизнь. А поскольку жизнь наша сложна и, по большому счёту, непредсказуема, упор в книжке делается, в основном, на теорию вероятностей и математическую статистику. Здесь не доказываются теоремы и не даются основы науки, это ни в коем случае не учебник, а то, что называется recreational science. Но именно такой почти игровой подход позволяет развить интуицию, скрасить яркими примерами лекции для студентов и, наконец, объяснить нематематикам и нашим детям, что же такого интересного мы нашли в своей сухой науке.



В этой главе мы рассмотрим закон бутерброда и организуем целое исследование с применением метода Монте-Карло, и анализа размерностей. И, наконец, развенчаем популярный миф о том, что именно масло является причиной этого закона подлости.
Читать дальше →
Total votes 26: ↑26 and ↓0+26
Comments11

Теория счастья. Случайности неслучайны?

Reading time20 min
Views51K
Продолжаю знакомить читателей Хабра с главами из своей книжки «Теория счастья» с подзаголовком «Математические основы законов подлости». Это ещё не изданная научно-популярная книжка, очень неформально рассказывающая о том, как математика позволяет с новой степенью осознанности взглянуть на мир и жизнь людей. Она для тех кому интересна наука и для тех, кому интересна жизнь. А поскольку жизнь наша сложна и, по большому счёту, непредсказуема, упор в книжке делается, в основном, на теорию вероятностей и математическую статистику. Здесь не доказываются теоремы и не даются основы науки, это ни в коем случае не учебник, а то, что называется recreational science. Но именно такой почти игровой подход позволяет развить интуицию, скрасить яркими примерами лекции для студентов и, наконец, объяснить нематематикам и нашим детям, что же такого интересного мы нашли в своей сухой науке.



В этой главе мы порассуждаем о предопределённости полёта монетки, о топографических картах, о математических катастрофах и о природе случайности. А по пути заглянем в такие разделы математики, как теория мер и теория динамического хаоса.
Читать дальше →
Total votes 60: ↑57 and ↓3+54
Comments130

Учим поросёнка на моноидах верить в себя и летать

Reading time14 min
Views11K

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



Я провёл простое тестирование и убедился в том, что на простых задачах, использующих только стек, виртуальная машина работает шустро, а при использовании "памяти" — массива со случайным доступом — начинаются большие проблемы. О том, как удалось их решить, не меняя базовых принципов архитектуры программы и достичь тысячекратного ускорения работы программы, и пойдёт речь в предлагаемой вашему вниманию статье.

Читать дальше →
Total votes 41: ↑41 and ↓0+41
Comments16

Стековая машина на моноидах

Reading time32 min
Views15K

Не так давно на Хабре появилась отличная и вдохновляющая статья про компиляторы и стековые машины. В ней показывается путь от простой реализации исполнителя байт-кода ко всё более и более эффективным версиям. Мне захотелось показать на примере разработки стековой машины, как это можно сделать Haskell-way.


На примере интерпретации языка для стековой машины мы увидим, как математическая концепция полугрупп и моноидов помогает разрабатывать и расширять архитектуру программы, как можно использовать алгебру моноидов и каким образом можно строить программы в форме набора гомоморфизмов между алгебраическими системами. В качестве рабочих примеров мы сначала построим интерпретатор, неотделимый от кода в виде EDSL, а потом научим его разным штукам: вести запись произвольной отладочной информации, отделять код программы от самой программы, проводить простой статический анализ и вычислять с различными эффектами.


Статья рассчитана на тех, кто владеет языком Haskell на среднем уровне и выше, на тех, кто его уже использует в работе или исследованиях и на всех любопытных, заглянувших поглядеть чего это функциональщики ещё понаворотили. Ну, и для тех, конечно, кого не испугал предыдущий абзац.

Читать дальше →
Total votes 49: ↑49 and ↓0+49
Comments28

Теория счастья. Термодинамика классового неравенства

Reading time23 min
Views33K
Продолжаю знакомить читателей Хабра с главами из своей книжки «Теория счастья» с подзаголовком «Математические основы законов подлости». Это ещё не изданная научно-популярная книжка, очень неформально рассказывающая о том, как математика позволяет с новой степенью осознанности взглянуть на мир и жизнь людей. Она для тех кому интересна наука и для тех, кому интересна жизнь. А поскольку жизнь наша сложна и, по большому счёту, непредсказуема, упор в книжке делается, в основном, на теорию вероятностей и математическую статистику. Здесь не доказываются теоремы и не даются основы науки, это ни в коем случае не учебник, а то, что называется recreational science. Но именно такой почти игровой подход позволяет развить интуицию, скрасить яркими примерами лекции для студентов и, наконец, объяснить нематематикам и нашим детям, что же такого интересного мы нашли в своей сухой науке.



В этой главе мы порассуждаем о деньгах, рынках и энтропии, а также посмотрим на анимированные гифки, которых, увы, в книжке напечатать не получится.


Читать дальше →
Total votes 46: ↑43 and ↓3+40
Comments111

Теория счастья. Проклятие режиссёра и проклятые принтеры

Reading time10 min
Views13K
Продолжаю знакомить читателей Хабра с главами из своей книжки «Теория счастья» с подзаголовком «Математические основы законов подлости». Это ещё не изданная научно-популярная книжка, очень неформально рассказывающая о том, как математика позволяет с новой степенью осознанности взглянуть на мир и жизнь людей. Она для тех кому интересна наука и для тех, кому интересна жизнь. А поскольку жизнь наша сложна и, по большому счёту, непредсказуема, упор в книжке делается, в основном, на теорию вероятностей и математическую статистику. Здесь не доказываются теоремы и не даются основы науки, это ни в коем случае не учебник, а то, что называется recreational science. Но именно такой почти игровой подход позволяет развить интуицию, скрасить яркими примерами лекции для студентов и, наконец, объяснить нематематикам и нашим детям, что же такого интересного мы нашли в своей сухой науке.





Мы порассуждаем о цейтнотах, дедлайнах и о невовремя ломающихся принтерах.

Читать дальше →
Total votes 32: ↑32 and ↓0+32
Comments6

Теория счастья. Закон зебры и чужой очереди

Reading time16 min
Views41K
Продолжаю знакомить читателей Хабра с главами из своей книжки «Теория счастья» с подзаголовком «Математические основы законов подлости». Это ещё не изданная научно-популярная книжка, очень неформально рассказывающая о том, как математика позволяет с новой степенью осознанности взглянуть на мир и жизнь людей. Она для тех кому интересна наука и для тех, кому интересна жизнь. А поскольку жизнь наша сложна и, по большому счёту, непредсказуема, упор в книжке делается, в основном, на теорию вероятностей и математическую статистику. Здесь не доказываются теоремы и не даются основы науки, это ни в коем случае не учебник, а то, что называется recreational science. Но именно такой почти игровой подход позволяет развить интуицию, скрасить яркими примерами лекции для студентов и, наконец, объяснить нематематикам и нашим детям, что же такого интересного мы нашли в своей сухой науке.





Мы поговорим о фатуме, землетрясениях, очередях и замечательных процессах: пуассоновском потоке, случайном блуждании и немного о цепях Маркова.
Читать дальше →
Total votes 45: ↑43 and ↓2+41
Comments30

Теория счастья. Введение в мерфологию

Reading time12 min
Views33K
Продолжаю знакомить читателей Хабра с главами из своей книжки «Теория счастья» с подзаголовком «Математические основы законов подлости». Это ещё не изданная научно-популярная книжка, очень неформально рассказывающая о том, как математика позволяет с новой степенью осознанности взглянуть на мир и жизнь людей. Она для тех кому интересна наука и для тех, кому интересна жизнь. А поскольку жизнь наша сложна и, по большому счёту, непредсказуема, упор в книжке делается, в основном, на теорию вероятностей и математическую статистику. Здесь не доказываются теоремы и не даются основы науки, это ни в коем случае не учебник, а то, что называется recreational science. Но именно такой почти игровой подход позволяет развить интуицию, скрасить яркими примерами лекции для студентов и, наконец, объяснить нематематикам и нашим детям, что же такого интересного мы нашли в своей сухой науке.



Это, одна из первых глав, в которой на примере велосипедиста рассматриваются нужные нам инструменты для измерения несправедливости: кривая Лоренца и индекс Джини, а также упоминаются пресловутый Парето и грозный инспектор.

Читать дальше →
Total votes 37: ↑37 and ↓0+37
Comments44

Теория счастья. Закон арбузной корки и нормальность ненормальности

Reading time10 min
Views75K
Представляю на суд читателей Хабра неупорядоченные главы из своей книжки «Теория счастья» с подзаголовком «Математические основы законов подлости». Это ещё не изданная научно-популярная книжка, очень неформально рассказывающая о том, как математика позволяет с новой степенью осознанности взглянуть на мир и жизнь людей. Она для тех кому интересна наука и для тех, кому интересна жизнь. А поскольку жизнь наша сложна и, по большому счёту, непредсказуема, упор в книжке делается, в основном, на теорию вероятностей и математическую статистику. Здесь не доказываются теоремы и не даются основы науки, это ни в коем случае не учебник, а то, что называется recreational science. Но именно такой почти игровой подход позволяет развить интуицию, скрасить яркими примерами лекции для студентов и, наконец, объяснить нематематикам и нашим детям, что же такого интересного мы нашли в своей сухой науке.



В этой главе мы начнём с анализа арбузов и их корок, выясним их связь со знаменитым законом Мерфи и убедимся со всей строгостью в том, что о вкусах не спорят.

Читать дальше →
Total votes 118: ↑117 and ↓1+116
Comments250

Безразмерный воздушный шар. Утилитарная магия анализа размерностей

Reading time11 min
Views9K

На написание этой небольшой заметки меня натолкнула недавно опубликованная на Хабре статья Динамика вертикального полёта летательного аппарата легче воздуха. Захотелось написать комментарий, но он быстро перерос во что-то большее и, как кажется, более полезное.

В оригинальной статье приводится пример расчёта динамики воздушного шара или аэростата в атмосфере. При этом учитываются и сопротивление воздуха и градиенты плотности и температуры атмосферы, так что задача сводится к нетривиальному дифференциальному уравнению, которое благополучно решается численно средствами языка Python. В статье всё хорошо: шар взлетел, остановился, где надо, мы получили и предельную высоту и время подъёма. Потребовалось запустить другой шар, скажем, побольше, нагрузить его поосновательнее, или поменять водород на гелий – не проблема – поменяем параметры в программе и снова всё посчитаем. Программка понятная, линейная, работает, что же можно здесь улучшить, если не усложнять модель?

Можно сделать так, чтобы модель и расчёты стали универсально полезными не для какого-то конкретного шара, а для широкого круга задач. Можно обеспечить оптимальную точность вычислений при численном интегрировании дифференциального уравнения. Можно избавиться от необходимости вручную задавать пределы интегрирования и шаг при расчёте в широком диапазоне параметров. Наконец, можно многое рассказать о динамике полёта нашего шара и без численного решения. И для всего этого служит один давний приём, верный и надёжный, когда-то обязательный при любых расчётах на ЭВМ и до их появления, а сейчас факультативный и часто относимый к магии и искусству – приведение уравнений к безразмерному виду и собственным масштабам. Воспользуюсь задачей о воздухоплавании, как примером и покажу, насколько более осмысленным и изящным становится анализ задачи, при использовании этой техники. А потом объясню почему это может быть важным для программистов, и отчего эта статья попала в хаб «Функциональное программирование».
Читать дальше →
Total votes 43: ↑43 and ↓0+43
Comments25

От моноидов к алгебрам де Моргана. Строим абстракции на Haskell

Reading time14 min
Views13K

Что общего у нормального распределения, конечных автоматов, хеш-таблиц, произвольных предикатов, строк, выпуклых оболочек, афинных преобразований, файлов конфигураций и стилей CSS? А что объединяет целые числа, типы в Haskell, произвольные графы, альтернативные функторы, матрицы, регулярные выражения и статистические выборки? Наконец, можно ли как-то связать между собой булеву алгебру, электрические цепи, прямоугольные таблицы, теплоизоляцию труб или зданий и изображения на плоскости? На эти вопросы есть два важных ответа: 1) со всеми этими объектами работают программисты, 2) эти объекты имеют сходную алгебраическую структуру: первые являются моноидами, вторые — полукольцами, третьи — алгебрами де Моргана.

Читать дальше →
Total votes 35: ↑34 and ↓1+33
Comments12
2

Information

Rating
67-th
Location
Петропавловск-Камчатский, Камчатский край, Россия
Date of birth
Registered
Activity