Различные реализации игры «Жизнь» описывались на Хабре уже неоднократно. В этой статье, в качестве продолжения этой темы, рассматривается ещё один её вариант: в качестве игрового поля используется регулярная решётка на плоскости Лобаческого. Описываются общие методы использования плоскости Лобачевского в программах и необходимые для этого математические приёмы.
Как возникла плоскость Лобачевского, достаточно известно. В позапрошлом веке господа Гаусс, Лобачевский и Бойяи, проживавшие примерно в одно время в разных странах тогдашней Европы, задумались, что будет, если отменить пятый постулат Евклида и заменить его на противоположную аксиому. Оказалось, что не случится ничего плохого, и никаких противоречий не возникнет. Заметная часть последующего изучения неевклидовой геометрии была посвящена выяснению того, кто из них у кого украл идею этой самой геометрии.
Менее известно, что несмотря на «отрицательный» способ определения неевклидовой геометрии (вместо того, чтобы сказать, что через точку проходит ровно одна прямая, не пересекающая данную, мы говорим, что таких прямых может быть сколько угодно), мы, тем не менее, получаем систему теорем и формул, не менее стройную, чем та, что есть в евклидовой геометрии. И одновременно, у нас есть гораздо большее разнообразие геометрических фигур, в том числе, разбиений плоскости на правильные многоугольники.

Мы собрали в одном месте все созданные совместно с ПостНаукой краткие обучающие видеоматериалы от профессоров Университета Иннополис.


Если темы вам интересны, добро пожаловать под кат.

Всем привет! Мы решили поделится переводом главы «Квантовое время» из книги Шона Кэрролла:

Что такое время в современном понимании и почему оно обладает именно такими свойствами? Почему время всегда двигается в одном направлении? Почему существуют необратимые процессы? Двадцать лет назад Стивен Хокинг пытался объяснить время через теорию Большого Взрыва. Теперь Шон Кэрролл, один из ведущих физиков-теоретиков современности, познакомит вас с восхитительной парадигмой теории стрелы времени, которая охватывает предметы из энтропии квантовой механики к путешествию во времени в теории информации и смысла жизни.

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

Хочу представить вашему вниманию комические купле каверзные вопросы по C#.
Не удержался и решил запостить немного классики.
Некоторые вопросы в подборке кому-то могут показаться слишком простыми, но небольшой подвох в них, как правило, есть. Иногда можно и простым вопросом подловить. Будут полезны тем, кто изучает язык.
Всех, кому интересно, прошу под кат!

Категорически приглашаем всех желающих на онлайн-курс «Введение в теоретическую информатику» Александра Ханьевича Шеня, подготовленный совместно с Computer Science центром и платформой Stepic. Курс начнётся 24 февраля.



Александр Ханьевич — автор многих популярных книг по математике и программированию. Многие его книги и брошюры можно бесплатно скачать с сайта издательства МЦНМО: например, «Программирование: теоремы и задачи» (Шень, 2004), «Лекции по математической логике и теории алгоритмов» (Верещагин, Шень, 2012), «Классические и квантовые вычисления» (Китаев, Шень, Вялый, 1999). Под его редакцией вышел перевод первого издания классического учебника «Алгоритмы: построение и анализ» (Кормен, Лейзерсон, Ривеста, 1990), а также недавнего учебника «Алгоритмы» (Дасгупта, Пападимитриу, Вазирани, 2006).

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

Будем рады видеть вас среди слушателей онлайн-курса!
stepic.org/104

Недавно viktorpanasiuk опубликовал задачу о конфетах, которая «зацепила» многих (в частности, koldyr опубликовал на Хабре свое аналитическое решение), в том числе и меня. Задача практическая, от инженера-кондитера, формулировалась так: «Найти максимально допустимое отклонение массы конфеты при ее производстве, чтобы нетто коробки, состоящей из n=12 штук их, не выходило за пределы M=310±7 грамм в 90% случаев. Закон распределения считать нормальным».

Автор решил задачу, исходя из предположения о нормальном распределении конфет по массе, и нашел среднюю массу конфеты (очевидно, равную µ=M/n=25.83 г) и стандартное отклонение σ=1.23 г. Использование метода Монте-Карло, т.е. генерация N*n случайных чисел с гауссовым распределением конфет со средним µ и стандартным отклонением σ, подтверждает правильность решения. Распределение масс коробок является гауссовым, и его параметры близки к найденным аналитически (расчеты в Mathcad Express в форматах MCDX и XPS прилагаются). На левом графике показана гистограмма плотности распределения (по массе) конфет, а на правом — соответственно, распределения коробок.



В финале процитированной статьи автор упоминает о немного измененной (на практике, более актуальной) задаче определения границ массы отдельной конфеты, при выходе за которые эту (чересчур большую или маленькую) конфету нужно отбросить, чтобы коробки удовлетворяли исходным условиям (310±7 г в 90% случаев). На мой взгляд, исходная статья уже содержит решение, надо лишь посмотреть на нее немного с другой точки зрения.

Одной из самых сильных сторон языка программирования Go является встроенная поддержка concurrency, основанная на труде Тони Хоара «Communicating Sequential Processes». Go создан для удобной работы с многопоточным программированием и позволяет очень легко строить довольно сложные concurrent-программы. Но задумывались ли вы когда-нибудь, как выглядят различные паттерны concurrency визуально?

Конечно, задумывались. Все мы, так или иначе, мыслим визуальными образами. Если я попрошу вас о чём-то, что включает числа «от 1 до 100», вы мгновенно их «увидите» в своей голове в той или иной форме, вероятно даже не отдавая себе в этом отчёт. Я, к примеру, ряд от 1 до 100 вижу как линия с числами уходящая от меня, поворачивающая на 90 градусов вправо на числе 20 и продолжающая до 1000+. И, покопавшись в памяти, я вспоминаю, что в самом первом детском саду в раздевалке вдоль стены были написаны номерки, и число 20 было как-раз в углу. У вас же, вероятно, какое-то свое представление. Или вот, другой частый пример — представьте круглый год и 4 сезона года — кто-то их видит как квадрат, каждая грань которого принадлежит сезону, кто-то — как круг, кто-то ещё как-то.

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

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

Вновь приветствую читателей «Хабра»!

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

Данную статью можно считать вольным переводом (хотя скорее попыткой разобраться) данной статьи. И да, написанна она скорее для математиков, нежели для широкой аудитории.

Небольшой спойлер: в начале это казалось мне какой-то магией, но потом я понял подвох…

В наши дни машина Тьюринга (далее МТ) — универсальное определение понятия алгоритма, а значит и универсальное определение «решателя задач». Существует множество других моделей алгоритма — лямбда исчисление, алгорифмы Маркова и т.д., но все они математически эквивалентны МТ, так что хоть они и интересны, но в теоретическом мире ничего существенно не меняют.

Вообще говоря, есть другие модели — Недетерминированная машина Тьюринга, Квантовые машины Тьюринга. Однако они (пока) являются только абстрактными моделями, не реализуемые на практике.

Полгода назад в Science Advances вышла интересная статья с моделью вычислений, которая существенно отличается от МТ и которую вполне возможно реализовать на практике (собственно статья и была о том, как они посчитали задачу SSP на реальном железе).

И да. Самое интересное в этой модели то, что, по заверению авторов, в ней можно решать (некоторые) задачи из класса NP полных задач за полином времени и памяти.

Говоря «хаос», мы, обычно, подразумеваем полное отсутствие порядка, абсолютную неупорядоченность и случайность. С математической точки зрения, хаос и порядок – понятия не взаимоисключающие. Теория хаоса (есть что-то завораживающие в названиях математических теорий) – достаточно молодая математическая область, создание которой приравнивают по значимости открытий ХХ века к созданию квантовой механики. Хаос случается в нелинейных динамических системах. Иначе говоря, любой процесс, который протекает со временем, может быть хаотичным (например, высота дерева, температура тела или популяция мадагаскарских тараканов).

Всем привет!

Эта статья посвящается удивительным особенностям в мире хаоса. Я постараюсь рассказать о том, как обуздать такую странную и сложную вещь, как хаотический процесс и научиться создавать собственные простейшие генераторы хаоса. Вместе с вами мы пройдем путь от сухой теории до прекрасной визуализации хаотических процессов в пространстве. В частности, на примере известных хаотических аттракторов, я покажу как создавать динамические системы и использовать их в задачах, связанных с программируемыми логическими интегральными схемами (ПЛИС).

Пусть мы хотим вычислить десятимиллионное число Фибоначчи программой на Python. Функция, использующая тривиальный алгоритм, на моём компьютере будет производить вычисления более 25 минут. Но если применить к функции специальный оптимизирующий декоратор, функция вычислит ответ всего за 18 секунд (в 85 раз быстрее):


Дело в том, что перед выполнением программы интерпретатор Python компилирует все её части в специальный байт-код. Используя метод, описанный хабрапользователем SkidanovAlex, данный декоратор анализирует получившийся байт-код функции и пытается оптимизировать применяющийся там алгоритм. Далее вы увидите, что эта оптимизация может ускорять программу не в определённое количество раз, а асимптотически. Так, чем больше будет количество итераций в цикле, тем в большее количество раз ускорится оптимизированная функция по сравнению с исходной.

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

Недавно на хабре появилась неплохая статья про вычисление N-ного числа фибоначи за O(log N) арифметических операций. Разумный вопрос, всплывший в комментариях, был: «зачем это может пригодиться на практике». Само по себе вычисление N-ого числа фибоначи может и не очень интересно, однако подход с матрицами, использованный в статье, на практике может применяться для гораздо более широкого круга задач.

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

loop 1000000000
  loop 1000000000
    loop 1000000000
      a += 1
      b += a
    end
  end
end
end

Незамедлительно выведет a = 1000000000000000000000000000, b = 500000000000000000000000000500000000000000000000000000, несмотря на то, что если бы программа выполнялась наивно, интерпретатору необходимо было бы выполнить октиллион операций.

Эти два графа являются изоморфными

Математик Ласло Бабай (László Babai) с факультета компьютерных наук и математики Чикагского университета представил быстрый новый алгоритм для решения задачи изоморфизма графов — одной из фундаментальных проблем теории сложности вычислений. Алгоритм приводит проблему очень близко к классу P. По мнению некоторых специалистов, это один из самых значительных результатов в теоретической информатике за десятилетие, если не за несколько десятилетий.

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

Однако, в зависимости от вида, каждые 7, 11, 13 или 17 лет периодические цикады одновременно массово вылезают на свет и превращаются в шумных летающих тварей, спариваются и вскоре умирают.

Хотя наши странные цикады весело уходят в иной мир, возникает очевидный вопрос: это просто случайность, или числа 7, 11, 13 и 17 какие-то особенные?

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



В первом случае поиск занимает A?ⁿAⁿ времени, во втором — Aⁿ.

Степени обозначают повторяемость строк, то есть A?³A³ — это то же самое, что и A?A?A?AAA. Графики отражают время, требуемое для поиска через регулярные выражения.

Обратите внимание, что в Perl для поиска строки из 29 символов требуется более 60 секунд. А при втором методе — 20 микросекунд. Это не ошибка. При поиске 29-символьной строки Thompson NFA работает примерно в миллион раз быстрее. Если нужно найти 100-символьную строку, то Thompson NFA справится менее чем за 200 микросекунд, а Perl понадобится более 10¹⁵ лет. Причём он взят лишь для примера, во многих других языках наблюдается та же картина — в Python, PHP, Ruby и т. д. Ниже мы рассмотрим этот вопрос более детально.

Наверняка вам трудно поверить приведённым данным. Если вы работали с Perl, то вряд ли подмечали за ним низкую производительность при работе с регулярными выражениями. Дело в том, что в большинстве случаев Perl обращается с ними достаточно быстро. Однако, как следует из графика, можно столкнуться с так называемыми патологическими регулярными выражениями, на которых Perl начинает буксовать. В то же время у Thompson NFA такой проблемы нет.

Возникает логичный вопрос: а почему бы в Perl не использовать метод Thompson NFA? Это возможно и следует делать, и об этом пойдёт далее речь.

Апериодическая мозаика Соколара-Тейлора

В последнее время я работаю над своей книгой «Математика 1001», делаю дополнения для следующей редакции, которая будет издана за рубежом. Поэтому я отслеживаю математические достижения, случившиеся примерно с 2009 года. И я решил представить вам десятку самых важных событий по этой теме с того времени, в порядке субъективного увеличения важности.

10. Синъити Мотидзуки заявил о доказательстве им abc-гипотезы. Событие попало в конец списка, поскольку до сих пор его доказательство не поддержано большим кругом математиков. Иначе оно занимало бы первое место. А пока, к разочарованию заинтересованных сторон, оно находится в лимбе.

9. Тернарная проблема Гольдбаха. «Начиная с 7, любое нечётное число является суммой трёх простых». Ещё с 1937 года это утверждение верно для достаточно больших нечётных чисел, но в 2013 году перуанский математик Харальд Гельфготт проверил это утверждение на компьютере для чисел вплоть до 10³⁰. Независимо от него это сделал и Дэвид Плат.

Недавно Владимир Подольский vpodolskiy, аналитик в департаменте по работе с образованием IBS, закончил обучение по специализации Data Science на Coursera. Это набор из 9 курсеровских курсов от Университета Джонса Хопкинса + дипломная работа, успешное завершение которых дает право на сертификат. Для нашего блога на Хабре он написал подробный пост о своей учебе. Для удобства мы разбили его на 2 части. Добавим, что Владимир  стал еще и редактором проекта по переводу специализации Data Science на русский язык, который весной запустили IBS и ABBYY LS.

Часть 1. О специальности Data Science в общих чертах. Курсы: Инструменты анализа данных (программирование на R); Предварительная обработка данных; Документирование процесса обработки данных.

Привет, Хабр!

Не так давно закончился мой 7-месячный марафон по освоению специализации «Наука о данных» (Data Science) на Coursera. Организационные стороны освоения специальности очень точно описаны тут. В своём посте я поделюсь впечатлениями от контента курсов. Надеюсь, после прочтения этой заметки каждый сможет сделать для себя выводы о том, стоит ли тратить время на получение знаний по аналитике данных или нет.

Если вы регулярно используете Git, то вам могут быть полезны практические советы из этой статьи. Если вы в этом пока новичок, то для начала вам лучше ознакомиться с Git Cheat Sheet. Скажем так, данная статья предназначена для тех, у кого есть опыт использования Git от трёх месяцев. Осторожно: траффик, большие картинки!

Содержание:

1. Параметры для удобного просмотра лога
2. Вывод актуальных изменений в файл
3. Просмотр изменений в определённых строках файла
4. Просмотр ещё не влитых в родительскую ветку изменений
5. Извлечение файла из другой ветки
6. Пара слов о ребейзе
7. Сохранение структуры ветки после локального мержа
8. Исправление последнего коммита вместо создания нового
9. Три состояния в Git и переключение между ними
10. Мягкая отмена коммитов
11. Просмотр диффов для всего проекта (а не по одному файлу за раз) с помощью сторонних инструментов
12. Игнорирование пробелов
13. Добавление определённых изменений из файла
14. Поиск и удаление старых веток
15. Откладывание изменений определённых файлов
16. Хорошие примечания к коммиту
17. Автодополнения команд Git
18. Создание алиасов для часто используемых команд
19. Быстрый поиск плохого коммита