Рубрика «математика» - 34

Функция Аккермана — одна из самых знаменитых функций в Computer Science. С ней связан как минимум один фундаментальный результат и как минимум один просто важный. Фундаментальный результат, говоря аккуратно и непонятно, таков: существует всюду определённая вычислимая функция, не являющаяся примитивно-рекурсивной. Важный результат заключается в том, что лес непересекающихся множеств (также известный как disjoint set union) работает очень быстро.

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

Из текста ниже вы узнаете, что такое примитивно-рекурсивные функции и как выяснить, что функция Аккермана к таковым не относится. И, конечно, этот текст убедит вас в том, что это невероятно красивая конструкция и невероятно красивое рассуждение!

Читать полностью »

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

Постоянный поток открытий, связанных с уравнениями жидкости - 1
Сложные потоки жидкости в чашке чая вдохновили учёных на несколько важных доказательств

Научный прогресс не всегда движется по прямой. Исследователи начинают заниматься какими-то вопросами, а потом бросают их. Результаты перестают вдохновлять. На формирование теории могут уйти десятилетия.

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

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

«Это была очень динамичная и удивительная история», — сказал Александр Киселёв, математик из Университета Дьюка, соавтор одного из доказательств.
Читать полностью »

Рубрика «Читаем статьи за вас». Октябрь — Декабрь 2019 - 1

Привет! Продолжаем публиковать рецензии на научные статьи от членов сообщества Open Data Science из канала #article_essense. Хотите получать их раньше всех — вступайте в сообщество!

Статьи на сегодня:

  1. Poly-encoders: Transformer Architectures and Pre-training Strategies for Fast and Accurate Multi-sentence Scoring (Facebook, 2019)
  2. Implicit Discriminator in Variational Autoencoder (Indian Institute of Technology Ropar, 2019)
  3. Self-training with Noisy Student improves ImageNet classification (Google Research, Carnegie Mellon University, 2019)
  4. Momentum Contrast for Unsupervised Visual Representation Learning (Facebook, 2019)
  5. Benchmarking Neural Network Robustness to Common Corruptions and Perturbations (University of California, Oregon State University, 2019)
  6. DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter (Hugging Face, 2019)
  7. Plug and Play Language Models: A Simple Approach To Controlled Text Generation (Uber AI, Caltech, HKUST, 2019)
  8. Deep Salience Representation for F0 Estimation in Polyphonic Music ( New York University, USA, 2017)
  9. Analyzing and Improving the Image Quality of StyleGAN (NVIDIA, 2019)

Читать полностью »

Лёшенька, Лёшенька, сделай одолжение!
Выучи, Алёшенька, таблицу умножения !

Агния Барто

Домашка по арифметике - 1

Сначала задачка для первоклассника. Дано некоторое положительное число. Нужно умножить на него другое число, заранее неизвестное. Вопрос, как посоветуют это сделать благородные доны ??? Бывалый разраб наверняка скажет, мол мужик, ставь умножитель и не парь мне мОзги. И возможно будет в корне неправ! Ибо кроме монстров от Alterra и Xilinx существует ещё и такое замечательное семейство как iCE-40 от Lattice. Ультрамикропотребляющее. Очень дешевое. Да вот беда, больно мелкие они, и увы, умножителей там нет. Я столкнулся с этим года 4 назад, когда портировал некий ADPCM-кодек с ассемблера adsp-2185 на такой кристалл.
Читать полностью »

Перевод статьи подготовлен специально для студентов базового и продвинутого курсов «Математика для Data Science».

Как прошел 2019 год в области математики и Computer Science - 1


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

Для математиков и специалистов по computer science 2019 год был годом повторений и пристального изучения. Одни пересматривали основополагающие принципы, в том время как другие находили поразительно простые доказательства, новые методы решения проблем или постигали неожиданные решения давних задач. Некоторые из этих достижений уже нашли широкое применение в физике и других научных дисциплинах. Другие же существуют исключительно в качестве теории (или просто для развлечения), и с практической точки зрения на сегодняшний день не несут никакой пользы.Читать полностью »

image

Как быть, если дерево поиска разрослось на всю оперативку и вот-вот подопрет корнями соседние стойки в серверной? Что делать с инвертированным индексом, жадным до ресурсов? Завязывать ли с разработкой под Android, если пользователю прилетает «Память телефона заполнена», а приложение едва на половине загрузки важного контейнера?

В целом, можно ли сжать структуру данных, чтобы она занимала заметно меньше места, но не теряла присущих ей достоинств? Чтобы доступ к хэш-таблице оставался быстрым, а сбалансированное дерево сохраняло свои свойства. Да, можно! Для этого и появилось направление информатики «Succinct data structures», исследующее компактное представление структур данных. Оно развивается с конца 80-х годов и прямо сейчас переживает расцвет в лучах славы big data и highload.

Читать полностью »

Визуальная теория информации (часть 2) - 1

Вторая часть перевода лонгрида посвященного визуализации концепций из теории информации. Во второй части рассматриваются энтропия, перекрестная энтропия, дивергенция Кульбака-Лейблера, взаимная информация и дробные биты. Все концепции снабжены прекрасными визуальными объяснениями.

Для полноты восприятия, перед чтением второй части, рекомендую ознакомиться с первой.

Читать полностью »

Визуальная теория информации (часть 1) - 1

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

Теория информации дает нам точный язык для описания многих вещей. Сколько во мне неопределенности? Как много знание ответа на вопрос А говорит мне об ответе на вопрос Б? Насколько похож один набор убеждений на другой? У меня были неформальные версии этих идей, когда я был маленьким ребенком, но теория информации кристаллизует их в точные, сильные идеи. Эти идеи имеют огромное разнообразие применений, от сжатия данных до квантовой физики, машинного обучения и обширных областей между ними.

К сожалению, теория информации может казаться пугающей. Я не думаю, что есть какая-то причина для этого. Фактически, многие ключевые идеи могут быть объяснены визуально!

Читать полностью »

(Кто уже читал предыдущие части перевода этой лекции, перематывайте до таймкода 20:10)

[Хэмминг местами говорит очень неразборчиво, поэтому если есть пожелание по улучшению перевода отдельных фрагментов — пишите в личку.]

Этой лекции не было в расписании, но ее пришлось добавить, чтобы не возникало окна между занятиями. Лекция, в сущности, посвящена тому, как мы знаем то, что мы знаем, если, конечно, мы и в самом деле это знаем. Эта тема стара как мир – она обсуждается последние 4000 лет, если не дольше. В философии для ее обозначения создан специальный термин – эпистемология, или наука о знании.

Я бы хотел начать с первобытных племен далекого прошлого. Стоит отметить, что в каждом из них существовали миф о сотворении мира. По одному древнеяпонскому поверью, некто взболтал грязь, из брызг которой появились острова. Подобные мифы были и у других народов: например, израильтяне верили, что Бог шесть дней творил мир, после чего устал и закончил творение. Все эти мифы схожи – хотя сюжеты их довольно разнообразны, все они пытаются объяснить, почему существует этот мир. Я буду называть такой подход теологическим, поскольку он не предполагает объяснений, кроме как «это произошло по воле богов; они сделали то, что посчитали нужным, и так появился мир».

В районе VI века до н. э. философы античной Греции начали задавать более конкретные вопросы – из чего состоит этот мир, каковы его части, а также попытались подойти к ним скорее рационально, нежели теологически. Как известно, они выделяли стихии: землю, огонь, воду и воздух; у них было еще множество других понятий и убеждений, и медленно, но верно все это преобразовалось в наши современные представления о том, что мы знаем. Тем не менее, тема эта озадачивала людей во все времена, и даже древние греки задавались вопросом, как они знали то, что они знали.
Читать полностью »

Про геометрический смысл кодов Грея - 1

Коды Грея имеют близкую родственную связь с кривой Гильберта.
Впрочем, при общении с коллегами выяснилось, что эта несложная зависимость выглядит в их глазах как нечто нетривиальное. Поиск в интернетах навскидку ничего не дал кроме мутной фразы в вики: “кривые Гильберта в пространствах большей размерности являются представителями обобщений кодов Грея”. Поэтому возникло желание раскрыть тему — коротенько, простым языком.
В результате под катом — «скандалы, интриги, расследования».
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js