Математика *

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

В этом посте мы используем математический аппарат под названием «марковский процесс принятия решений» для нахождения доказуемо оптимальных стратегий игры 2048 для полей размером 2x2 и 3x3, а также на доске 4x4 вплоть до тайла 64. Например, вот оптимальный игрок в игру 2x2 до тайла 32:


Случайное начальное число (random seed) определяет случайную последовательность тайлов, добавляемых игрой на поле. «Стратегия» игрока задаётся таблицей, называемой алгоритмом (policy). Она сообщает нам, в каком направлении нужно сдвигать тайлы в любой возможной конфигурации поля. В этом посте мы рассмотрим способ создания алгоритма, оптимального в том смысле, что он максимизирует шансы игрока на получение тайла 32.

Оказывается, что в игре 2x2 до тайла 32 очень сложно выиграть — даже если играть оптимально, игрок выигрывает только примерно в 8% случаев, то есть игра оказывается не особо интересной. Качественно игры 2x2 сильно отличаются от игр 4x4, но они всё равно полезны для знакомства с основными принципами.

В идеале мы хотим найти оптимальный алгоритм для полной игры на поле 4x4 до тайла 2048, но как мы убедились из предыдущего поста, количество возможных конфигураций поля очень велико. Поэтому невозможно создать оптимальный алгоритм для полной игры, по крайней мере, с помощью используемых здесь методов.

Однако мы можем найти оптимальный алгоритм для укороченной игры 4x4 до тайла 64, и, к счастью, мы увидим, что оптимальная игра на полях 3x3 качественно выглядит похожей на некоторые успешные стратегии полной игры.

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

Существует классическая задача для собеседований, часто формулируемая следующим образом:

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

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

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

Введение

В настоящее время в качестве бронебойных боеприпасов широкое применение получили бронебойные оперенные подкалиберные снаряды (БОПС), обладающие высокой проникающей способностью.

Это достигается за счет высокой начальной скорости боеприпаса (1650 – 1840 м/с) и малого поперечного сечения (d = 20-30 мм). Для компенсации силы сопротивления воздуха применяют придание боеприпасу реактивной тяги.

Прямоточный воздушно-реактивный двигатель (ПВРД), прост по конструкции, имеет высокий коэффициент полезного действия при больших числах Маха компактен, поскольку не требует наличие окислителя в составе топлива, так как использует кислород окружающей среды [1].

Привет, Хабр. Помните офигенную статью «Вы и ваша работа» (+219, 2222 в закладки, 350k прочтений)?

Так вот у Хэмминга (да, да, самоконтролирующиеся и самокорректирующиеся коды Хэмминга) есть целая книга, написанная по мотивам его лекций. Мы ее тут переводим, ведь мужик дело говорит.

Это книга не просто про ИТ, это книга про стиль мышления невероятно крутых людей. «Это не просто заряд положительного мышления; в ней описаны условия, которые увеличивают шансы сделать великую работу.»

Мы уже перевели 6 (из 30) глав.

Глава 9. N-мерное пространство

(За перевод спасибо Алексею Фокину, который откликнулся на мой призыв в «предыдущей главе».) Кто хочет помочь с переводом — пишите в личку или на почту magisterludi2016@yandex.ru

Когда я стал профессором после 30 лет активных исследований в Bell Telephone Laboratories главным образом в отделе математических исследований, я вспомнил, что профессора должны осмыслять и резюмировать прошлый опыт. Я положил ноги на стол и стал обдумывать свое прошлое. В ранние годы я занимался в основном вычислениями, то есть я был вовлечен во многие большие проекты, требующие вычислений. Думая о том, как были разработаны несколько больших инженерных систем, в которые я был частично вовлечен, я начал, находясь теперь на некотором расстоянии от них, видеть, что у них было много общих элементов. Со временем я начал понимать, что задачи проектирования находятся в n-мерном пространстве, где n — число независимых параметров. Да, мы создаем 3-мерные объекты, но их проектирование находится в многомерном пространстве, 1 измерение для каждого проектируемого параметра.

Многомерные пространства понадобятся для того, чтобы дальнейшие доказательства стали интуитивно понятны без строгой детализации. Поэтому мы будем сейчас рассматривать n-мерное пространство.

Математика — это «язык, который ни читать, ни понять невозможно без инициации» (Эдвард Ротштейн, «Эмблемы ума»)

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

Для математики существует особый протокол чтения. Как мы учимся читать литературу, так и математику мы должны научиться читать. Школьникам следует изучать протокол чтения для математики так же, как они учатся правилам чтения романа или стихотворения, учатся понимать музыку и живопись. Замечательная книга «Эмблемы ума» Эдварда Ротштейна выявляет взаимосвязь между математикой и музыкой, неявно затрагивая протоколы чтения для математики.

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




Как видно из рисунка выше, клеточный автомат проходит три этапа:

1. Случайное поле.
2. Цветные области.
3. Спирали, также известные как демоны.

Добавим еще одно измерение к решетке. В этом измерении мы отобразим состояние ячейки. Ячейка будет подниматься до тех пор, пока она не достигнет вершины кубоида, а затем она упадет вниз. Такая модель является хорошим представлением об изменении состояния клеточного автомата.


Выберем несколько (например 12) случайных ячеек и рассмотрим изменение их состояний во времени.

В этой статье я расскажу и покажу свой способ сегментации строк на слова. Если вам не интересна жизнь сибиряка в тропиках, можете смело пропускать вступление.

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

Джон Хортон Конвей утверждает, что не работал ни дня в своей жизни. Этот отрывок из биографии «Гений за игрой» показывает, какие серьёзные математические теории, вроде сюрреальных чисел, могут появиться из развлечений и игр.



Грызя указательный палец левой руки своими старыми обломанными британскими зубами, с набухшими старческими венами, с задумчиво нахмуренной под давно нестриженными волосами бровью, математик Джон Хортон Конвей без сожаления тратит своё время на раздумья и теоретические изыскания. Хотя он будет утверждать, что ничем не занимается, ленится, и играет в игрушки.

Он работает в Принстоне, хотя славу он обрёл в Кембридже (будучи сначала студентом, а затем профессором с 1957 по 1987 года). Конвей, 77-и лет, утверждает, что не работал ни дня в своей жизни. Он имеет в виду, что тратит почти всё свое время на игры. И в то же время, он профессор Принстона по прикладной и вычислительной математике (сейчас уже почётный). Член Королевского сообщества. И признанный гений. «Титул „гений“ часто неправильно используют»,- говорит Перси Дьяконис, математик из Стэнфорда. – Джон Конвей – гений. При этом он может работать в любой области. И у него чутьё на всякие необычные вещи. Его нельзя поставить в какие-то математические рамки".

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



Лекцию в марте прошлого года прочитал на факультете компьютерных наук Ростислав Яворский, доцент департамента анализа данных и искусственного интеллекта. На факультете Ростислав Эдуардович ведет курсы «Введение в программирование», «Компьютерная алгебра», «Неклассические логики и представление знаний».

Структура публикации

• Оговорка про крен
• Подготовка GPS-трека
• Как из массива векторов получить углы Крылова-Эйлера
• Имитация показаний гироскопа
• Вектор ускорения свободного падения и направление «на север»
• Имитация показаний акселерометра, компаса и барометра

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

Поводом к написанию этого поста послужила статья «Mathcad Express — бесплатный математический редактор, про который мало кто знает».

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

Это четвертая статья в цикле «Теория категорий для программистов».

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

Без объектов

Самая простая категория — без объектов и, как следствие, без морфизмов.

Краткий синопсис

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

P.S. Весьма «сухой язык», но вполне читабельно после университетской программы. По большей части определения парадоксов брались из Википедии (упрощённая формулировка и готовая TeX-разметка).

Введение

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

Следует начать с определения.

Что есть множество? Вопрос достаточно простой, ответ на него вполне интуитивен. Множество это некий набор элементов, представляемый единым объектом. Кантор в своей работе Beiträge zur Begründung der transfiniten Mengenlehre даёт определение: под «множеством» мы понимаем соединение в некое целое M определённых хорошо различимых предметов m нашего созерцания или нашего мышления (которые будут называться «элементами» множества M)[1]. Как видим, суть не изменилась, разница лишь в той части, которая зависит от мировоззрения определяющего. История же теории множеств как в логике так и в математике весьма противоречива. Фактически начало ей положил Кантор в XIX веке, далее Рассел и остальные продолжили работу.

Парадоксы (логики и теории множеств) — (греч. — неожиданный) — формально-логические противоречия, которые возникают в содержательной множеств теории и формальной логике при сохранении логической правильности рассуждения. Парадоксы возникают тогда, когда два взаимоисключающих (противоречащих) суждения оказываются в равной мере доказуемыми. Парадоксы могут появиться как в пределах научной теории, так и в обычных рассуждениях (например, приводимая Расселом перифраза его парадокса о множестве всех нормальных множеств: «Деревенский парикмахер бреет всех тех и только тех жителей своей деревни, которые не бреются сами. Должен ли он брить самого себя?»). Поскольку формально-логическое противоречие разрушает рассуждение как средство обнаружения и доказательства истины (в теории, в которой появляется парадокс, доказуемо любое, как истинное, так и ложное, предложение), возникает задача выявления источников подобных противоречий и нахождения способов их устранения. Проблема философского осмысления конкретных решений парадоксов — одна из важных методологических проблем формальной логики и логических оснований математики.

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

В части 1 мы говорили о том, какие строительные блоки нужны для формализации Хиндли-Милнера, а в этом посте мы конкретизируем их определения и сформулируем формализацию в целом:

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

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

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

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

Добрый день, уважаемые коллеги. В этой статье я хочу поделиться с Вами своими методическими наработками, которые использую в курсе «Теория автоматического управления» на кафедре СУиИ НИУ ИТМО.
Основной задачей, которую я перед собой ставил, было объединение теоретических знаний для решения практической задачи. Такой задачей стало управление приводами Lego робота. Лишний повод поиграть в игрушки, да и студентам проще воспринимать суровый матан… Вот пример описания этого набора: habrahabr.ru/post/166449.

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

Сегодня исполняется ровно 250 лет с того дня, как немецкий физик и математик Иоганн Генрих Ламберт, отвлёкшись от своих трактатов по оптике и астрономии, доказал, что Пи является иррациональным числом. Это значит, что не существует таких целых чисел p и q, для которых было бы верно равенство Пи = p/q.

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

Но всё-таки, каков же смысл работы Ламберта? Какова её польза для общества?