Русский
Русский
English
Статистика
Реклама

Математика

Мы вас посчитали теперь я не знаю, зачем вы ходите на конференции. Зато знаю, почему не ходите

17.11.2020 12:21:43 | Автор: admin
Идти вперед туда, где не ждут; атаковать там, где не подготовились.
Искусство войны, Сунь-Цзы

На прошлой неделе я набросал простую математическую модель принятия решения и оценки того, пойдете вы на конференцию или нет. Для того, чтобы модель была наглядной, нам понадобятся Саша (в очках) и Женя (улыбается), вот они:



Математическая модель для конференции и участников


Давайте познакомимся с нашими героями поближе:


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

Впрочем, только ситхи всё возводят в абсолют, а в реальности такие Саша и Женя в природе встречаются очень редко. Выраженность этих признаков, как и всё в нашем мире, градиентно распределена среди всех участников (и даже неучастников!) конференций. Представьте себя на месте наших героев: у вас есть свой набор ожиданий от конференции, давайте возьмем их сумму за единицу, которую можно распределить между Сашей и Женей. Эту единицу мы назовем Business or Banquet Ratio (далее просто BOBR).



Вы так или иначе окажетесь на нашей прямой, которая, по сути, является математической моделью множества всех участников конференции:


  1. Вот, например, с бокалом и без улыбки у нас будет СЕНЯ (Четверть от Саши, три четверти от Жени: 75% ради нетворкинга, 25% ради докладов). Кого-то притягивает атмосфера большого события и общество единомышленников, такие люди проводят время в кулуарах и на выставке, иногда заходя на пару интересующих докладов и проводя почти все время на выставке и в кулуарах со старыми и новыми знакомыми.
  2. Кто-то наоборот на три четверти ходит ради докладов, знаний и кругозора, однако эти знания можно получить, общаясь с интересными людьми, задавая вопросы докладчикам и коллегам, так что условная четверть ваших ожиданий будет зависеть не от самих докладов, а от того, кто их рассказывает и в каком круге вы их потом обсуждаете. Тут имя не получилось, к сожалению.
  3. Другие ходят на конференцию слушать доклады совместно с друзьями и коллегами, постоянно общаясь и обсуждая то, что удалось услышать на докладе или в кулуарах конференции, разделяя время на знания и общение пополам. Получается САНЯ! Как видите, модель выходит довольно складной

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



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


Давайте прикинем, где бы оказались наши конференции при таком подходе.


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


А теперь немного отвлечемся от математики и постараемся понять, что именно добавляет ценности по шкале Жени (общение и отдых) и обеспечивает разницу между онлайном и офлайном:



Ретроспективное исследование наших проведенных конференций говорит о том, что люди приходили на них ради образовательных и тусовочных (простите за мой французский) целей примерно в равной степени. То есть примерно вот так выглядел Joker 2019:



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


image А значит, BOBR по шкале Жени включает в себя следующие слагаемые:


  1. Встретиться с друзьями, которые приехали издалека или обычно слишком заняты, обсудить с коллегами насущные проблемы.
  2. Сделать селфи для инстаграма с крутыми инженерами, разработчиками любимых инструментов или автором настольной книги.
  3. Отдохнуть, сменить обстановку, перезагрузиться, просто прогуляться в толпе интеллигентных людей.
  4. Пособирать мерч на стендах компаний-спонсоров конференции.
  5. Найти новых знакомых из огромной толпы единомышленников и оппонентов в кулуарных спорах о технологиях и жизни.

image Что можно делать в онлайне:


  1. Потрепаться в чате конференции и чатах докладов.
  2. Пообщаться со спикером в Zoom-комнате доклада.
  3. Поучаствовать в вечеринке в общей Zoom-комнате конференции с теми, кто тоже хочет обсудить всякое.

А это значит, что онлайновый JPoint 2020 выглядел уже так:



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


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


Впрочем, есть еще один нюанс, посмотрите на графики с количеством участников в 2019 офлайне и 2020 онлайне:



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



А мы вот так:

Команда JUG Ru Group по окончании сезона онлайн-конференций выглядела как-то так:


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


Всё. Из-за этого наши онлайн-конференции оказываются в левой части системы координат с минимальной длиной отрезка BOBR:


Мы, как всегда, сделали хорошую программу и собрали спикеров (шкала Саши) на онлайновых JPoint и HolyJS, но это привело к тому, что они еле-еле переползли в зеленый сегмент из-за низкого индекса по шкале Жени.


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


Глядя на это, мы пошли внимательно изучать отзывы участников, думать и прогнозировать будущее.


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


Итак, задача ставилась так, чтобы Joker 2020 и HolyJS 2020 Moscow попали примерно сюда:


Ниже я расскажу, что как мы эту задачу решаем.


Что же делать?


С самого начала локдауна и пандемии многие организаторы по всему миру ушли в виртуальные пространства: митинги в Red Dead Redemption, конференции в Animal Crossing, митапы в Minecraft Мы тоже думали об этом: организация виртуального кинотеатра кажется достаточно тривиальной задачей до тех пор, пока не пытаешься ее скалировать до нужных масштабов:


  1. Несколько сотен или тысяч человек в онлайне;
  2. Хорошие звук и видео, в идеале 4К;
  3. Стабильность подключения, видео- и голосовой связи не только для спикеров, но и для участников;
  4. Интеграция контента и нетворкинга на единой платформе;
  5. Размещение на карте всех POI и партнеров.

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


За весну и лето мы упоролись и посмотрели несколько десятков онлайн-мероприятий и кучу готовых платформ, на которых они проходили и везде обнаруживались проблемы и ограничения в качестве звука/видеопотока, стабильности работы или разрозненности компонент (программа на сайте, доклады и панельные дискуссии в YouTube / Zoom, тусовка в Spatial Chat). Поэтому к лету мы делали просто понятный портал с хорошим плеером, встроенной программой и навигацией, прямыми ссылками в чаты и дискуссионные зоны.


В итоге мы решили первые три задачи из списка выше и оставили две на второй сезон, который идет уже сейчас. Что нам осталось? Правильно, сделать платформу интерактивной и интересной по шкале Жени. Для этого мы снова посмотрели на имеющиеся решения типа Gather Town и Spatial Chat и поняли, что с ними мы можем сделать полноценную онлайн-движуху, но остается последняя проблема: интеграция контентной и нетворкинговой частей.


В конце концов, никто не хочет никуда ходить, и каждое открывание чатиков, зумов и прочего кажется pain in the ass. Чтобы всем было комфортно, важно сделать так, чтобы виртуальное пространство находилось там же, где и доклады, чтобы можно было быстро и без лишних телодвижений переключаться между докладами и общением: помните, нам нельзя ронять шкалу Саши и делать просмотр докладов неудобным, шумным или привязанным к геймификации, чтобы не испортить впечатления у тех, кто пришел смотреть доклады в первую очередь.


Как мы решили задачу с нетворкингом


Поэтому мы что? Правильно! Запилили свой сервис со своей реализацией webRTC и игровыми механиками!


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


Вот классический плеер:



И выставка партнеров:



Или она же в игровом виде:



Давайте посмотрим, что мы сделали, чтобы нашим с вами Саше и Жене было интересно проводить время не только на докладах, но и гуляя по виртуальному пространству.


Логинимся


Логинимся? (гифку безбожно пожало, к сожалению)



Общаемся


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



Как видите, если подойти ближе, то внизу появляется видео собеседника (привет, vbrekelov!) и звук.


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


Отдыхаем


Карта как место проведения: единое пространство, где Женя, отдыхая от докладов, может проходить мини-квесты, общаться со спонсорами конференции и собирать лут (реальный, который потом вышлют к вам!).


Вот так примерно будет выглядеть выставка и стенды партнеров:



На карте также будут места, с которыми можно взаимодействовать в них будут квесты, веб-страницы и различные пасхалки:



Ищем друзей


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



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


Пробуем


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


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


Реклама как вывод


Как видите, в этом сезоне мы постараемся сделать наши конференции не только полезными, но и более веселыми, и это наш большой эксперимент, который состоится 25-28 ноября, на Java-конференции Joker 2020 и HolyJS 2020 Moscow (да-да, мы все еще называем конференции по городам, вот такие мы ретрограды).


Кроме того, будут еще DotNext, SmartData и DevOops (со 2-го по 12-е декабря), а если планируете отправиться на несколько конференций, то смотрите на Full Pass-билет, который даст вам доступ еще и к уже прошедшим конференциям этого сезона.


Присоединяйтесь, смотрите, хвалите, играйте и ругайте! А заодно вспомните и прикиньте, где бы вы расположили себя на графике с Сашей и Женей. ;)


Disclaimer: Давайте только не приходить в комментарии со словами, что офлайн был лучше. JUG Ru Group будут первыми в очереди на проведение старых добрых конференции, когда спикеры из Штатов и Европы смогут до нас доехать, люди не будут бояться жать друг другу руки, а риски отмены не будут кратно превышать вероятности проведения.

Подробнее..

Математика и пандемия COVID-19

23.11.2020 14:22:47 | Автор: admin

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


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


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


Первой переменной в нашем "уравнении" будет витамин D.

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


В организм витамин D отчасти поступает с пищей, но главный источник холекальциферол (витамин D3), вырабатываемый в коже под воздействием прямого солнечного света, что и делает регулярное пребывание на солнце жизненно необходимым для человека. В отсутствие достаточной инсоляции и/или витаминизированной пищи организм расходует запасы витамина D, накопленные при более благоприятных условиях в жировой ткани.


Вот мы и перешли ко второй переменной солнечный свет.

Здесь немного подробнее.


Начнем с географии. Как известно, условная линия сечения, которая называется экватором делит Землю на две половины Северное полушарие и Южное полушарие (Рис 1).


image

Рис 1. Территория Северного полушария (выделена желтым) и Южного полушария

Тепловые пояса (или пояса освещенности). В зависимости от количества солнечного света, падающего на поверхность Земли, на земном шаре выделяют 5 тепловых поясов: тропический, два умеренных, два полярных пояса.


image

Рис 2. Тепловые пояса Земли

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


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


image

Рис 3. Смена времен года в Северном полушарии и Южном полушарии

У нас есть две переменные солнечный свет, витамин D, а также зависимость: больше солнечного света (нахождения на свету) больше витамина D в организме.
Теперь возьмем по три страны Южного и Северного полушарий и рассмотрим график распространения коронавирусной инфекции по месяцам:


image
image
image

Рис 4. Распространение коронавируса в Австралии, Южной Африке, Аргентине

Как видно из Рис 4. рост количества заражений в Южной Африке и Австралии пришелся на холодный зимний период для Южного полушария (июнь, июль, август), а уже с началом весны пошел спад (сентябрь). В Аргентине рост также пришелся на аргентинскую зиму, а спад пошел с середины весны (октябрь).


image
image
image

Рис 5. Распространение коронавируса в Великобритании, Канаде, России


Как видно из Рис 5. после летнего спада рост количества заражений в Великобритании, Канаде и России, как и в Северном полушарии в целом пришелся уже на начало осени (сентябрь).


Выводы:

В осенне-зимний период меньше солнечных дней, соответственно меньше витамина D в организме человека.


Здесь мы получаем "производную" нашего "уравнения" (функции) степень заразности коронавируса в зависимости от числа носителей с дефицитом витамина D. Людей с дефицитом этого витамина в это время года становится больше, а значит коронавирус легче распространяется среди населения.


Отсюда сезонный характер пандемии, скачок второй волны в Северном полушарии (осень-зима для этого региона) и затухающая первая волна в Южном полушарии (весна-лето в Южном полушарии). Сезонный характер пандемии подчеркивает вспышка распространения коронавируса в Северном полушарии одновременно во многих странах.


Решение:


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

Для этого необходимо:


1 сделать доступным (по финансам и времени) анализ на содержание витамина D в организме для всех групп населения.
2 следить, чтоб в аптеках и в магазинах лекарства (БАД тоже) и продукты его содержащие также были доступны.
3 поддержка со стороны государства и СМИ этой акции.

Подробнее..

Математика и пандемия COVID-19. Часть 2

25.11.2020 20:07:40 | Автор: admin
Это мой второй материал на этом ресурсе посвященный пандемии COVID-19. Очень понравилось, что первый материал был не только прочитан большим количеством пользователей, но и еще у некоторых возникали вопросы, которые они оставили в после прочтения. Постараюсь ответить на эти вопросы в русле отмеченных там наблюдений.

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

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

Поехали!

Сезонность и витамин D

Вернемся снова к Северному и Южному полушарию Земли (Рис. 1). Это строгое разделение на полушария условно и переход от одного к другому (по климату, по животному и растительному миру) плавный, как на Рис. 2 с тепловыми поясами.

image
Рис 1. Территория Северного полушария (выделена желтым) и Южного полушария

image
Рис 2. Тепловые пояса Земли

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

Упрощение состоит в том, чтобы рассматривать эту модель Мира, как разделенную на два полушария и при таком разделении мы увидим, как распространение коронавируса одномоментно обострилось именно с началом осенне-зимнего сезона в каждом полушарии, а спало уже весной-летом. А если смотреть частности, то это хорошо видно по крайним странам, которые дальше от экватора (поэтому в прошлый раз выбрали Австралию, ЮАР, Аргентину, Великобританию, Канаду и Россию).

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

Сезонная волна имеет сезонное начало (осень-зима), четкий период, рост заражений, плато и спад. Отдельные локальные во времени и в пространстве волны это просто вспышки. Поэтому рассматривать распространение пандемии коронавируса следует в разрезе полного периода (сезонного цикла), а это первая волна в Южном полушарии (март-август) и вторая в Северном полушарии (сентябрь-?). Первая волна Северном полушарии (после вспышки в Китае), была не полного периода и пришла в конце зимнего сезона поэтому местами даже не успела выйти на плато и была подавлена различными мерами внутри государств.

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

Нет никаких повальных анализов на витамин D, возможно эти исследователи поэтому и не могут найти связи

Испания, Италия И Узбекистан.

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

Чем больше изучаешь эту тему, тем больше открытий для себя. Удивительным оказалось, что большой процент населения стран средиземного моря и вообще южных стран испытывает недостаток витамина D в организме, имея при этом более 300 солнечных дней в году за окном. В каждой стране есть свои особенности этого явления, где-то это сиеста (продленный обеденный перерыв), где-то это повсеместное использование крема от загара (более 90% защиты от ультрафиолета), где-то традиционная одежда (в странах востока, где носят закрытую одежду), а кое-где даже гастрономические особенности (оказалось, что помидоры защищают от ультрафиолета).

Но есть и общее это фототипы кожи.

Шкала Фитцпатрика или шкала фототипов кожи Фитцпатрика, также тест Фитцпатрика числовая шкала, основанная на классификации цвета кожи человека.

image
Рис 3 Фототипы кожи по Фитцпатрику

image
Рис 3.1 Фототипы кожи по Фитцпатрику

Классификация фототипов кожи по Фитцпатрику:

Кельтский. Люди этого фототипа имеют самый светлый оттенок кожи. Они практически никогда не загорают (их кожа не принимает загар), риск возникновения солнечных ожогов (обгорания) очень велик.

Светлый европейский. Кожа этого типа также характеризуется светлым оттенком и высокой чувствительностью к УФ-излучению. Риск обгорания велик, как и в предыдущем случае. Однако светлый европейский фототип кожи незначительно, но принимает загар.

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

Средиземноморский. Светло-коричневый оттенок кожи. Шанс солнечного ожога минимальный. Загар на кожу ложится всегда хорошо.

Средне-восточный. Коричневый оттенок кожи. Люди с этим фототипом кожи практически никогда не обгорают на солнце. Загар характеризуется тёмным оттенком.

Африканский. Люди этого фототипа имеют наиболее тёмный оттенок кожи. Шанс обгорания на солнце практически нулевой. Загар лишь делает кожу ещё темнее.

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

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

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

image
Рис 4. Карта Мира по уровню солнечной инсоляции

Здесь вспоминаем про шкалу Фитцпатрика, смотрим на Рис 4. карту Мира по уровню солнечной инсоляции на регион в котором сформировалась негроидная раса (Африка) и регион в котором некоторые ее представители проживают сейчас (США, Канада, Европа) и понимаем, что людям этого фототипа кожи в этих широтах хронически не хватает солнца, а с ним, как следствие и витамина D в организме.

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

Продолжение следует
Подробнее..

NaN все еще может немного удивить

26.11.2020 18:13:16 | Автор: admin
image

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



Ответ должен быть NaN. Но почему я не уверен в этом? Всю дорогу была уверенность в том, что любые выражения, содержащие NaN, вернут NaN. Ну разве что только если поделить NaN на ноль в этом случае будет вызвано исключение ZeroDivisionError. Сто процентов NaN! Ввожу выражение в ячейку блокнота:
>>> 1**nan + 1**nan2.0

В самом деле? Постойте:
>>> arange(5)**nanarray([nan,  1., nan, nan, nan])

То есть, по какой-то причине, единица в степени NaN это единица, а вот ноль и все остальные числа в степени NaN это NaN. Где логика? В чем дело?

Так, давайте еще раз:
>>> 0**nan, 1**nan(nan, 1.0)


Может быть я просто из-за отсутствия какой-то практической надобности в глубоких познаниях о NaN, просто о чем-то не подозревал? А может я знал, но забыл? А может еще хуже я не знал и забыл?

Заходим на Википедию. Там данный вопрос тоже обозначен как проблема, но почему все именно так устроено, никак не объясняется. Зато узнал что:
>>> hypot(inf, nan)inf

Хотя, в то же время:
>>> sqrt(inf**2 + nan**2)nan

Что, согласитесь, тоже немного странно.

Ладно, с Википедии отправляемся в C99 на 182 страницу и наконец-то получаем логическое объяснение, почему pow(x, 0) возвращает 1 для любых x, даже для x равного NaN:
>>> power(nan, 0)1.0

Если функция $f(x)$ возводится в степень $g(x)$ и при этом $g(x)$ стремится к 0, то в результате получится 1, вне зависимости от того, какое значение имеет $f(x)$.
image
А если результат не зависит от числового значения функции $f(x)$, то 1 является подходящим результатом, даже для NaN. Однако это по-прежнему не объясняет, почему 1 в степени NaN равна 1.

Отыскиваем еще один C99 и на 461 странице не видим никаких объяснений, просто требование того, что pow(+1, y) должно возвращать 1 для всех y, даже равных NaN. Все.

С другой стороны, объяснение, почему pow(NaN, 0)=1 является более предпочтительным, чем pow(NaN, 0)=NaN все-таки наталкивает на мысль о том, что NaN не стоит воспринимать буквально, как Not-a-Number. Допустим, в результате каких- то вычислений мы получили число, превышающее размер памяти, выделенный под данный тип чисел, например:
>>> a = pi*10e307>>> ainf

В результате мы получили inf, что именно это за число мы не знаем, но все же это какое-то число. Затем мы снова что-то вычислили и снова получили слишком большое число:
>>> b = e*10e307>>> binf

Разность a и b вернет NaN:
>>> c = a - b>>> cnan

Единственная причина, по которой мы можем считать c не числом, заключается в том, что мы использовали недостаточно точные вычисления. Однако, в c под NaN все же скрывается какое-то значение. О том, что это за значение, мы не знаем. Но все же это число, а раз это число, то нет ничего удивительного в том, что pow(1, NaN)=1.

Почему же тогда pow(0, NaN)=NaN? Дело в том, что если возвести 0 в любую степень, то мы действительно получим ноль. Кроме одного единственного случая когда степень равна 0:
>>> 0**01

Из-за чего в выражении pow(0, NaN) появляется неопределенность с конкретным значением NaN. Конечно, вероятность того, что под NaN может скрываться 0 исчезающе мала и можно было бы принять, что pow(0, NaN)=0. Но все же лучше перестраховаться, мало ли к чему это может привести. Возможно, так и рассуждали, когда создавались стандарты.

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

P.S. Поскольку NaN относится к числам с плавающей точкой, оно может быть ключом словаря:
>>> d = {0.1: 'a', nan: 'b'}>>> d[nan]'b'

Имеет ли смысл исользовать такое на практике? Думаю, что лучше не стоит.
Подробнее..

Перевод Нормали и обратное транспонирование, часть 1 внешние алгебры

25.11.2020 12:06:49 | Автор: admin

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


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


Единицы и масштабирование


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


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


В качестве примера давайте перечислим всевозможные поведения при масштабировании в трёхмерном пространстве. Обозначим масштабный множитель как $a>0$. Тогда:


  • Безразмерные числа не меняются, иными словами они умножаются на $a^0$.
  • Длины умножаются на $a$.
  • Площади умножаются на $a^2$.
  • Объёмы умножаются на $a^3$.
    Но это ещё не всё: есть так же плотности, которые изменяются как обратные к масштабному коэффициенту величины:
  • Линейные плотности умножаются на $1\over{a}$.
  • Плотности по площади умножаются на $1\over{a^2}$.
  • Объёмные плотности умножаются на $1\over{a^3}$.
    Плотности могут выражать вещи вроде количества текселей на длину, или геометрической вероятности, или количества частиц в объёме. Если 3D-модель масштабируется в сторону увеличения, а размер текстуры не изменяется, тогда плотность текселей на ней уменьшается, и так далее.

Получается, даже ограничившись однородным масштабом и рассмотрев скалярные (не векторные) значения, мы уже наблюдаем феномен: различные значения, которые выглядят структурно одинаковыми (все они являются скалярами), оказывается ведут себя по разному будучи преобразованными, из-за различных единиц которые они несут в себе. А именно, они соответствуют различным степеням длины от -3 до 3. Величина, соответствующая $k$ степеням длины, масштабируется как $a^k$.


(Можно было бы придумать величины со степенями масштабирования $\pm 4$ и более, или даже с дробными стпенями. Но оставим их за рамками рассмотрения, потому что у них нет хорошей геометрической интерпретации в 3D.)


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


Внешние алгебры


Отныне и до конца нам понадобятся внешние алгебры, или алгебры Грассмана. Так как с ними скорее всего знакомы не все читатели, я изложу краткое введение в тему. Для более глубокого понимания обратитесь к этой лекции Эрика Лэнгиела, или к нескольким первым главам книги Дорста Geometric Algebra for Computer Science. В сети есть великое множество других материалов.


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


Мы часто представляем себе вектор как абстрактную стрелку у неё есть направление в пространстве (в котором указывает стрелка) и абсолютная величина, представляемая длиной стрелки. Бивектор во многом такой же, но он плоский, а не линейный. Он представляется не стрелкой, а абстрактным участком плоской поверхности.


Как и у векторов, у бивекторов тоже есть направление в том смысле, что плоскость может быть обращена к различным направлениям в пространстве. Ещё у них есть абсолютная величина, геометрически представимая как площадь участка плоскости. Чего у них нет, так это концепции формы на плоскости. Визуализируя бивектор как часть плоскости, вы можете представлять его как квадрат, круг, параллелограмм или любую другую сколь угодно замысловатую фигуру соответствующей площади.
image
Аналогично, тривекторы это трёхмерные векторные величины, представляющие участок пространства, а не плоскости или стрелку. Опять же, у них определённой формы, а есть только абсолютное значение, которое теперь является объёмом, а не площадью или длиной.


В трёхмерном пространстве у тривекторов нет направления в полезном смысле слова. Иными словами, у них есть единственное возможное направление, которое параллельно пространству. Тем не менее, у тривекторов есть два противоположных направления, которые мы можем назвать "положительным" и "отрицательным", или "правосторонним" и "левосторонним". Это похоже на то, как вектор может указывать влево или вправо на одномерной прямой, и при желании мы можем назвать эти направления положительным и отрицательным.


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


Базисные $k$-векторы


Бивекторы и тривекторы можно разложить на компоненты в базисе, так же как это делается с обычными векторами. Координатная запись вектора $v$, $v=(x, y, z)$, означает, что $v$ может быть представлен как линейная комбинация базисных векторов:


$v=x{\bf e_x}+y{\bf e_y}+z{\bf e_z}$


Базисные векторы ${\bf e_x}$, ${\bf e_y}$, ${\bf e_z}$ определяют направление и масштаб осей $х$, $y$, $z$. Точно так же бивектор $B$ можно представить линейной комбинацией базисных бивекторов:


$B=p{\bf e_{yz}}+q{\bf e_{zx}}+r{\bf e_{xy}}$


Здесь ${\bf e_{xy}}$ это бивектор единичной площади, ориентированный вдоль плоскости $xy$. ${\bf e_{yz}}$ и ${\bf e_{zx}}$ можно представить по аналогии. Базисные бивекторы соответствуют не осям координат, а плоскостям, натянутым на пары осей. Так определяются "координаты бивектора" $(p, q, r)$, с помощью которых мы можем обозначить или соорудить любой бивектор в пространстве.
image
Случай тривектора менее интересен:


$T=t{\bf e_{xyz}}$


Как мы заметили выше, у тривектора в 3D есть только одно возможное направление, потому у них только один базисный элемент: единичный тривектор "вдоль пространства $(xyz)$. Все остальные тривекторы это произведения ${\bf e_{xyz}}$ на скаляр.


Внешнее произведение


Итак, внешняя алгебра содержит различные векторообразные объекты разных степеней: обычные векторы (степень 1), бивекторы (степень 2) и тривекторы (степень 3). Скалярам можно приписать степень 0. Наконец, чтобы объекты разных степеней могли взаимодействовать, внешняя алгебра определяет операцию под названием внешнее произведение, обозначаемое через $\wedge$. Оно даёт возможность сконструировать бивектор умножая два вектора, например:


${\bf e_x}\wedge{\bf e_y} = {\bf e_{xy}}$


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


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


Так же можно перемножить три вектора, или бивектор с вектором, чтобы получить тривектор.


${\bf e_x}\wedge{\bf e_y}\wedge{\bf e_z} = {\bf e_{xy}}\wedge{\bf e_z}={\bf e_{xyz}}$


Такое произведение равнозначно "скалярному смешанному произведению", которое даёт тривектор, представляющий ориентированный объём параллелепипеда, натянутого на три вектора.


Внешнее произведение подчиняется большинству известных правил умножения, например ассоциативности и дистрибутивному закону. Скалярное умножение с ним тоже сочетается. Для скаляра $a$ получаем:


$(au)\wedge v=u\wedge (av) = a(u\wedge v)$


Но внешнее произведение двух векторов антикоммутативно, снова как и векторное произведение. Для векторов $u, v$ имеем:


$u\wedge v=-(v\wedge u)$


Из этого следует несколько выводов. Во-первых, внешнее произведение любого вектора на себя равно нулю: $v\wedge v=0$. Более того, внешнее произведение набора линейно-зависимых векторов тоже равно нулю. Например, $u\wedge v=0$ когда $u$ и $v$ коллинеарны. В случае трёх векторов, $u\wedge v\wedge w=0$ когда $u, v, w$ копланарны.


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


Преобразования $k$-векторов


Ранее я заявлял, что абсолютное значение вектора можно представлять как длину, значение бивектора как площадь, а тривектора как объём. Но что управляет именно таким сопоставлением единиц величинам?


Выше мы видели, что длины, площади и объёмы ведут себя по-разному при масштабировании. Равномерное масштабирование трёхмерного пространства с коэффициентом $a>0$ отмасштабирует длины, площади и объёмы как $a, a^2, a^3$ соответственно. Теперь у нас есть аппарат, показывающий что векторы, бивекторы и тривекторы ведут себя точно так же.


К вектору можно применить масштаб, умножив его на подходящую матрицу:


$v\mapsto Mv$


$\begin{bmatrix} x \\ y \\ z \end{bmatrix} \mapsto \begin{bmatrix} a & 0 & 0 \\ 0 & a & 0 \\ 0 & 0 & a \end{bmatrix} \begin{bmatrix} x \\ y \\ z \end{bmatrix} = \begin{bmatrix} ax \\ ay \\. az \end{bmatrix} = av$


Вектор $v$ как единое целое, его компоненты $x, y, z$, и его скалярное абсолютное значение, умножаются на коэффициент $a$ при масштабировании, поэтому мы может назвать его длиной, и в этом не будет противоречия.


Что насчёт бивекторов? Чтобы увидеть как они ведут себя при масштабировании (или любом другом линейном преобразовании), обратимся к внешнему произведению. В трёхмерном пространстве любой бивектор можно разложить на внешнее произведение двух векторов. Мы умеем преобразовывать векторы, а значит можем преобразовать бивектор, преобразовав составляющие его векторы и взяв внешнее произведение результатов:


$\begin{aligned} B &= u \wedge v \\ (u \wedge v) &\mapsto (Mu) \wedge (Mv) \\ &= (au) \wedge (av) \\ &= a^2 (u \wedge v) \\ &= a^2 B \end{aligned}$


Во как! Так как бивектор состоит из двух сомножителей, каждый из которых масштабируется на $a$, бивектор обретает коэффициент $a^2$, который делает его площадью.


Тривекторы тоже можно преобразовать, раскладывая на векторы. Теперь неудивительно, что три вектор-сомножителя придают тривектору коэффициент $a^3$. Приведём выкладки для полноты:


$\begin{aligned} T &= (u \wedge v \wedge w) \\ (u \wedge v \wedge w) &\mapsto (Mu) \wedge (Mv) \wedge (Mw) \\ &= (au) \wedge (av) \wedge (aw) \\ &= a^3 (u \wedge v \wedge w) \\ &= a^3 T \end{aligned}$


Бивекторы и неравномерный масштаб


Теперь наконец мы можем вернуться к исходному вопросу. Что усложнится, если мы применим неравномерное масштабирование?


Чтобы понять это, давайте рассмотрим пример. Будем масштабировать в 3 раза по оси $x$, оставляя остальные оси неизменными. Получится матрица вида:


$M = \begin{bmatrix} 3 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} $


На обычных векторах её действие очевидно: компонента $x$ умножается на 3, а компоненты $y, z$ не изменяются. В общем случае матрица изменяет как длину, так и направление вектора в зависимости от изначального направления: векторы, близкие к оси $x$ растягиваются сильнее, а близкие к плоскости $yz$ слабее.
image
Как токое преобразование повлияет на бивектор? Для начала давайте зайдём со стороны геометрии. Бивектор обозначает участок плоскости с заданными площадью и направлением, в которое направлена "лицевая" сторона. При растяжении такого участка вдоль оси $x$ мы ожидаем, что и направление и площадь изменятся. Но различные бивекторы изменятся по разному: на бивектор, близкий к плоскости $yz$, растяжение повлияет меньше, а бивектор, чья плоскость близка к $x$, будет растянут сильнее.
image
Окей, вернёмся к алгебре. Как было показано выше, любой бивектор можно разложить на базисные бивекторы, выровненные по осям:


$B = p \, {\bf e_{yz}} + q \, {\bf e_{zx}} + r \, {\bf e_{xy}}$


Чтобы применить масштабирование $M$ к бивектору, нужно лишь применить его к базисным бивекторам. Для этого разложим их на базисные векторы и применим $M$ к ним:


$\begin{aligned} {\bf e_{yz}} = {\bf e_y} \wedge {\bf e_z} \quad &\mapsto \quad (M{\bf e_y}) \wedge (M{\bf e_z}) = {\bf e_y} \wedge {\bf e_z} = {\bf e_{yz}} \\ {\bf e_{zx}} = {\bf e_z} \wedge {\bf e_x} \quad &\mapsto \quad (M{\bf e_z}) \wedge (M{\bf e_x}) = {\bf e_z} \wedge 3{\bf e_x} = 3{\bf e_{zx}} \\ {\bf e_{xy}} = {\bf e_x} \wedge {\bf e_y} \quad &\mapsto \quad (M{\bf e_x}) \wedge (M{\bf e_y}) = 3{\bf e_x} \wedge {\bf e_y} = 3{\bf e_{xy}} \end{aligned}$


Это соответствует геометрической интуиции: $\bf e_{yz}$ не изменился, а $\bf e_{zx}$ и $\bf e_{xy}$ обрели множетель 3, потому что их плоскости включают ось $x$.


Таким образом, вот общий эффект применения $M$ к бивектору $B$:


$B \mapsto p \, {\bf e_{yz}} + 3q \, {\bf e_{zx}} + 3r \, {\bf e_{xy}}$


Теперь, как и в случае с вектором, можно выписать преобразование бивектора $B$ в виде компонент, к котором применяется матрица:


$ \begin{bmatrix} p \\ q \\ r \end{bmatrix} \mapsto \begin{bmatrix} 1 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 3 \end{bmatrix} \begin{bmatrix} p \\ q \\ r \end{bmatrix} = \begin{bmatrix} p \\ 3q \\ 3r \end{bmatrix} $


Это то же самое преобразование, которое мы только что вывели, записанное в другой нотации. Обратите внимание на одно различие: матрица в этом выражении не совпадает с матрицей $M$ исходного преобразования.


Заметим однако забавное совпадение: обратная транспонированная $M$ пропорциональная матрице из предыдущей формулы:


$ M^{-T} = \begin{bmatrix} \tfrac{1}{3} & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} $


К чему бы это?


Присоединённая матрица


Фактически, матрица преобразования для бивектора это присоединённая матрица к $M$.


Она пропорциональна обратной транспонированной матрице с коэффициентом $\det M$. (Обратную к $M$ матрицу можно получить транспонированием присоёдинённой матрицы, разделив её на $\det M$). Присоединённая матрица определена даже когда $M$ необратима. Это хорошее свойство, потому что мы можем преобразовывать вектор необратимой матрицей, и должна быть возможность проделать то же самое с бивектором!


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


У каждого элемента квадратной матрицы $n\times n$ есть алгебраическое дополнение. Вычисляется алгебраическое дополнение элемента на $i$-ой строке и $j$-ом столбце следующим образом:


  1. Возьмём исходную матрицу $n\times n$ и вычеркнем строку $i$ и столбец $j$. Останется подматрица размером $(n-1)\times (n-1)$.
  2. Вычислим определитель этой подматрицы.
  3. Умножим определитель на $(-1)^{i+j}$, то есть изменим его знак если $i+j$ нечётно. Это и есть алгебраическое дополнение!

Теперь склеим алгебраические дополнения обратно в матрицу $n\times n$, в результате чего получится присоединённая матрица.


Но как так получилось, что эта кнострукция работает в преобразовании бивектора? Посмотрим на первый компонент бивектора $p \, {\bf e_{yz}}$. Этот член представляет компонент плоскости $yz$, а потому на него влияют только преобразования, которые $M$ применяет к осям $y$ и $z$. В рецепте приготовления алгебраического дополнения $1,1$ матрицы $M$ тоже использзуется подматрица $2\times2$, которая определяет что $M$ делает с осями $y$ и $z$. Далее мы берём её определитель, который есть ни что иное, как коэффициент масштабирования плоскости $yz$!


Из-за того, что мы выбрали бивекторный базис ${\bf e_{yz}}, {\bf e_{zx}}, {\bf e_{xy}}$именно в таком порядке, каждый элемент присоединённой матрицы автоматически вычисляет детерминант, который определяет как $M$ масштабирует площади в соответствующей плоскости. Или, для внедиагональных элементов, как $M$ отображает площади из одной координатной плоскости в другую. Другими словами, алгебраические дополнения оказались в точности теми коэффициентами, которыми преобразуются компоненты бивектора.


(Между почим, знаковый множитель с третьего шага нужен чтобы разрешить некоторые проблемы упорадоченности. Без него у нас был бы базисный элемент ${\bf e_{xz}}$ вместо ${\bf e_{zx}}$. Последний базисный элемент предпочитается по общепринятому соглашению.)


Несмотря на сфокусированность нашего повествования на трёхмерном случае, замечу, что в размерности $n$ присоединённая матрица преобразует $(n-1)$-векторы в подходящем базисе. Фактически, для преобразования $k$-векторов понадобится матрица $(n-k)$-ых миноров, то есть определителей подматрицы с вычеркнутыми $n-k$ строками и столбцами.


Бивекторы и нормали


В этом месте я должен сделать небольшое признание. На протяжении последних нескольких абзацев я прятал кое что в рукаве. Трюк вот в чём: бивекторы изоморфны обычным векторам в 3D. Фактически, компоненты $(p, q, r)$ бивектора в стандартном базисе это компоненты нормали $(x, y, z)$ к плоскости бивектора с точностью до нормализации!


Давайте посмотрим как так получается. Ранее мы видели, что внешнее произведение набора линейно зависимых векторов равно нулю. Это значит, что плоскость бивектора $B$ может быть задана уравнением:


$B\wedge v=0$


Любой вектор $v$, лежащий в плоскости бивектора $B$ удовлетворяет этому уравнению потому что он образует линейно зависимый набор с двумя векторами, на которые натянута плоскость. Или, с другой стороны, тривектор, образованный $B$ и $v$ будет иметь нулевой объём.


Разложим это уравнение в стандартных векторном и бивекторном базисах и упростим:


$\begin{gathered} (p \, {\bf e_{yz}} + q \, {\bf e_{zx}} + r \, {\bf e_{xy}}) \wedge (x \, {\bf e_x} + y \, {\bf e_y} + z \, {\bf e_z}) = 0 \\ (px \, {\bf e_{yzx}} + qy \, {\bf e_{zxy}} + rz \, {\bf e_{xyz}}) = 0 \\ (px + qy + rz) {\bf e_{xyz}} = 0 \\ px + qy + rz = 0 \\ \end{gathered}$


Поясню на случай если шаги не очень понятны. Во второй строке я распределил внешнее произведение по всем членам базиса, большинство из которых уничтожились, потому что в них во внешнем произведении участвовало по две копии одной оси (например, ${\bf e_{yz}} \wedge {\bf e_y} = 0$). В третьей строке я перегруппировал оси всех тривекторов к единому виду $\bf e_{xyz}$, что вполне законно, если мы отслеживаем изменения знака. Здесь во всех случаях было чётное количество изменений знака. Наконец, я вынес $\bf e_{xyz}$ и сократил на него.


Теперь последняя строка выглядит как скалярное произведение векторов $(p, q, r)$ и $(x, y, z)$! Другими словами, она выглядит как обычное уравнение плоскости $n\cdot v = 0$ с вектором нормали $n=(p, q, r)$.


Отсюда видно, что бивекторные координаты $(p, q, r)$ в базисе ${\bf e_{yz}}, {\bf e_{zx}}, {\bf e_{xy}}$так же являются координатами нормали к плоскости в стандартном векторном базисе ${\bf e_x}, {\bf e_y}, {\bf e_z}$. Более того, внешнее произведение вектора на бивектор идентично скалярному произведению на соответствующий вектор нормали. Формально это применение звезды Ходжа, которая в трёхмерном случае взаимозаменяет бивекторы и их нормали. Подробнее об этом поговорим в будущих статьях.


Дальнейшие вопросы


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


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


Ещё вопрос: в затравке вначале статьи нам встретились единицы как с положительными, так и с отрицательными степенями масштаба, от -3 до 3. Теперь мы увидели, что внешние $k$-векторы масштабируются как стпень $k$ от 0 до 3. Но что насчёт векторных единиц с отрицательными степенями масштаба? Существуют ли они? Если да, то что они такое?


В следующей серии мы зароемся ещё глубже и усложним нашу геометрическую историю ещё сильнее.

Подробнее..

Перевод Наша Вселенная огромная нейронная сеть, и вот почему

20.11.2020 18:16:58 | Автор: admin
10 сентября 2020 года мир облетела новость о том, что мир, по мнению физика Виталия Ванчурина, может быть огромной нейронной сетью. Специально к старту новых потоков курса Machine Learning и версии для подготовленных спецов Machine Learning Pro + Deep Learning представляем вам перевод материала рассуждения о таком подходе к модели мира в свете других современных и порой весьма смелых теорий.





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

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

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

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

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

Если теория Хоффмана вам интересна, посмотрите его выступление на TED
или эти интервью с ним.





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

На этом основывалась специальная теория относительности. Другой пример квантовая механика, где нелокальность кванта предполагает нечто отличное от нашего повседневного опыта.

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

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

Впервые я прочитал о выгрузке сознаний в знаменитой книге Рэя Курцвейла The Singularity is near. Выгрузка разума это полная цифровизация человеческого мозга. Технология, где мозг копируется нейроном за нейроном и моделируется на цифровом компьютере. Если человеческий разум это результат работы мозга, то эта имитированная копия будет полностью идентична человеческому разуму. Итак, если выгрузка разума возможна, как можно создать оптимальную симулированную реальность для оцифрованных разумов?

Первое решение


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

Тогда что можно сделать?


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

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

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

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

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

Если вам интересно, как наш мозг проецирует реальность, посмотрите выступление Анила Сета на TED по этой теме.

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

Но что, если машина согласованности не сможет объединить прогнозы потому, что между ними существует основное противоречие? В этом случае машина согласованности должна изменить ожидания, чтобы синхронизировать их. Ожидания индивидуального разума исходили из прошлого опыта, поэтому манипулирование разумом и изменение ожиданий это что-то вроде путешествия во времени. Машина согласованности возвращается в прошлое и меняет события, чтобы синхронизировать ожидания. Это также идеальное решение для защиты модели. Если бы кто-то смог доказать, что мы живем в симуляции, машина согласованности могла бы вернуться в прошлое и залатать дыру в безопасности. Таким образом, в этой системе вы никогда не сможете доказать, что система симуляция.

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

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

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

Обе теории утверждают, что человеческое сознание результат иерархии. Иерархическая сеть модулей, которая приводит к последовательному сознательному опыту, очень похожа на машину согласованности. Что, если индивидуальный разум (я) находится не на верхнем уровне в иерархии модулей, а в структуре только среднего уровня? Здесь вершина иерархии не индивидуальный разум, а глобальное сознание верхнего уровня, содержащее индивидуальные сознания и поддерживающее согласованность переживаемой ими реальности. Это что-то вроде гигантского мозга со множеством личностей.

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

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

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

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

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

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

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

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

Что можно сделать, исходя из этой теории? Если Хоффман прав и пространство-время не является фундаментальным, то, по его словам, возможно, мы сможем как-то взломать Вселенную.

Если он не прав и сознание результат функции мозга и может быть объяснено физическими законами, тогда мы сможем смоделировать их и в будущем построить наши собственные реальности. Так что правильный вопрос: Когда мы будем жить в симуляции или мы уже живем в ней?

image



Рекомендуемые статьи


Подробнее..

Перевод Беспорядок встречается в более крупных графах, чем считалось ранее

24.11.2020 16:19:42 | Автор: admin

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




Одни из самых упрямых чисел математики, после более 70 лет сопротивления, наконец, начинают поддаваться.

В опубликованном в сентябре четырёхстраничном доказательстве Давид Конлон и Асаф Фербер дали наиболее точную оценку многоцветным числам Рамсея. Эти числа описывают размер графов, до которого они могут вырасти перед тем, как в них начнут неизбежно проявляться определённые закономерности.

В нашей Вселенной абсолютных случайностей нет, сказала Мария Аксенович из Технологического института Карлсруэ в Германии. Всегда где-то есть скопления порядка, и числа Рамсея оценивают его количественно.

Графы это наборы точек (вершин), соединённых линиями (рёбрами). Особенно математиков интересует вопрос, сколько вершин и рёбер можно добавить в граф перед тем, как в нём начнут появляться различные подструктуры.

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

Числа Рамсея относятся к определённой последовательности, монохромной клике. Это набор вершин, которые будут соединены друг с другом рёбрами одного и того же цвета после определенной процедуры раскрашивания.


Асаф Фербер из Калифорнийского университета в Ирвине

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

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

Новое доказательство позволяет определить диапазон значений чисел Рамсея гораздо точнее любого результата с тех пор, как эти числа впервые начал изучать Пал Эрдёш в 1930-х и 40-х годах. Конлон из Калифорнийского технологического института и Фербер из Калифорнийского университета в Ирвине обнаружили новую нижнюю границу для многоцветных чисел Рамсея. Она получилась экспоненциально более точная, чем лучшая из предыдущих оценок. Их результат даёт математикам новый способ понять имеющую чрезвычайную важность для них схему взаимодействия порядка и случайности в графах.

Это потрясающий результат, сказала Аксенович. Мне он очень понравился.

Цветные связи


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

Но если мы начнём с полного графа из шести вершин, раскрасить его рёбра двумя цветами, не порождая монохромную клику из трёх или более вершин, не получится. Иначе говоря, для двух цветов и размера клики 3 число Рамсея будет равным 6 (в графе должно быть не менее 6 вершин).

Числа Рамсея меняются в зависимости от количества цветов и размера искомой монохромной клики. Но в целом их сложно вычислять точные значения известны математикам только в небольшом числе случаев. Даже для небольших клик размером 5 и двух цветов лучше, что могут сказать математики по поводу числа Рамсея что оно находится в промежутке от 43 до 48.

Неловкая ситуация, сказал Ювал Уигдерсон, аспирант из Стэнфорда. Мы работаем над этой задачей уже почти 100 лет, и так ничего и не узнали.


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


Числа Рамсея сложно подсчитать потому, что сложность графа быстро растёт с ростом количества вершин. Для графа из шести вершин и двух цветов все варианты можно перебрать вручную. Для графа из 40 вершин существует 2780 способов раскрасить рёбра в два цвета.

Приходится проверять слишком много, сказала Аксенович.

У математиков, изучающих числа Рамсея, есть байка, создание которой обычно приписывают Эрдёшу. Она описывает, насколько быстро эти вычисления становятся слишком сложными. Представьте, что на Землю вторглись инопланетяне. Они предлагают пощадить нашу планету, если мы сможем выдать правильные значения чисел Рамсея. Если они попросят нас назвать число Рамсея для случая с двумя цветами и кликами размера 5, нам нужно будет бросить все ресурсы человечества на решение этой задачи. Если же они попросят нас посчитать число Рамсея для клик размера 6, нам проще будет сразу готовиться к сражению.

Если они попросят у нас число Рамсея для [клик размера] 6, то лучше сразу атаковать, сказала Аксенович.

Изучая случайность


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

В 1935 году Пал Эрдёш и Дьёрдь Секереш установили первую такую границу. Они применили короткое доказательство того, что числа Рамсея для двух цветов должны быть меньше, чем 4t, где t размер интересующей вас монохромной клики. Они также обнаружили, что числа Рамсея для трёх цветов должны быть меньше 27t. Через 10 лет, в 1947 году, Эрдёш подсчитал первую нижнюю границу для этих чисел: для двух цветов это (2)t вершин, а для трёх (3)t.

Между (2)t и 4t есть большая разница, особенно при очень больших значениях t. Этот разрыв отражает нечёткое понимание чисел Рамсея математиками. Однако форма границ то, как размер нужного графа выражается через размер нужной клики намекает на то, что больше всего интересно математикам.

Что мне очень хотелось бы понять это то, как растут эти числа Рамсея с ростом размера клики, сказала Лиза Сауэрман, постдок в Институте передовых исследований в Принстоне.

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

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

Можно начать, как сделал Эрдёш, со случайного раскрашивания рёбер. Для каждого ребра бросим что-то вроде трёхгранного кубика и раскрасим тем цветом, который выпадет случайно. Эрдёш знал, что легко подсчитать вероятность того, что любое подмножество из 10 рёбер окажется одного цвета. Нужно просто перемножить вероятность того, что одно из рёбер будет, допустим, красным, с вероятностью того, что другое ребро будет красным, и так далее для всех десяти рёбер (то есть, 1/310). Затем он умножил то число на три, чтобы учесть тот факт, что нужную монохромную клику может породить любой из трёх разных цветов.

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

Пока граница объединения остаётся меньше 1, вы знаете, что метод случайной раскраски не гарантирует появления заданной монохромной клики. В нашем примере граница равна 0,0128. Это очень далеко от гарантированного появления монохромной клики в 5 вершин, а значит, для данного примера число Рамсея больше 10 вершин.

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


Пал Эрдёш изобрёл вероятностный метод подсчёта чисел Рамсея.
1) Начинаем с полного графа из 10 вершин. При раскраске рёбер тремя цветами всегда ли можно найти 5 вершин, соединённых 10 рёбрами одного цвета?
2) Вероятность того, что конкретное ребро красное (а не синее или жёлтое) равна 1/3
3) Вероятность того, что 10 рёбер красные, равна (1/3)10
4) Всего монохромную клику могут породить три цвета.
5) Общее количество разных клик из 5 вершин равно 252.
(1/3)10 * 3 * 252 = 0,0128 вероятность получить монохромную клику при случайной раскраске рёбер.


Мы можем доказать существование чего-то, не демонстрируя его напрямую, сказал Уигдерсон.

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

Именно это и удалось сделать Конлону и Ферберу этой осенью.

Включение порядка


Новое доказательство улучшает нижнюю границу чисел Рамсея для трёх и более цветов.

До этой работы нижняя граница для трёх цветов равнялась (3)t (примерно 1,73 t). Конлон и Фербер улучшили её до 1,834t. Для четырёх цветов они подняли нижнюю границу с 2t до 2,135t. Оба эти результата гигантские шаги вперёд. Увеличивая основание, возводимое в степень t, Конлон и Фербер доказали существование экспоненциально больших графов, раскрашенных в три и четыре цвета, у которых нет монохромных клик. Иначе говоря, показали, что беспорядок встречается в более крупных графах, чем считалось ранее.

Целью Конлона и Фербера было раскрасить полный граф, не создавая крупные монохромные клики. Они придумали для этого способ эффективного распределения одного цвета (допустим, красного) по фиксированному правилу перед тем, как применять все остальные цвета случайным образом. Этот гибридный метод дал им контроль над структурой графа, которым не обладал Эрдёш.


Давид Конлон из Калифорнийского технологического института

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

Сначала они брали координаты каждой вершины, возводили их в квадрат и складывали, получая сумму квадратов. Из-за особенности этого геометрического пространства сумма квадратов давала одну из двух величин, 0 или 1. Затем они оставляли только те вершины, чья сумма давала 0, и подсчитывали скалярное произведение пар вершин (стандартная операция для линейной алгебры). Потом они окрашивали ребро в красный, если оно соединяло пару вершин, скалярное произведение которых равнялось определённой величине.

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

Этот подход оказался прекрасным способом избегать появления монохромных клик с ростом графа. Так и было задумано: парочка специально разработала детерминистский этап так, чтобы красные рёбра равномерно распределялись по всему графу. На первый взгляд они выглядели так, будто распределялись случайным образом. В самом деле, Конлон и Фербер называют эту раскраску рёбер псевдослучайной.

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

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

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

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

Перевод Подробнее о тайном математическом обществе, известном под именем Никола Бурбаки

30.11.2020 14:07:23 | Автор: admin

Почти сто лет подряд анонимные члены группы писали книги, выражающие чистые математические мысли



Некоторые из основателей группы: Анри Картан (стоит слева), Андре Вейль (стоит второй справа) и Шолем Мандельбройт (сидит справа).

Приглашение пообщаться с членами одного из старейших тайных математических обществ Антуан Шамберт-Луар получил по телефону. Мне сказали, что Бурбаки хотели бы встретиться со мной, чтобы обсудить возможную совместную работу, сказал он.

Шамберт-Луар принял приглашение, и одну из недель сентября 2001 года он провёл, читая вслух математические тексты по семь часов в день, и обсуждая их с членами группы, личности которых неизвестны остальному миру.

Официально вступить в группу его не приглашали, но в последний день его пребывания ему выдали долгосрочное задание закончить рукопись, над которой группа работала с 1975 года. Когда позднее Шамберт-Луар получил отчёт о встрече, он обратил внимание, что его отметили, как membrifi, то есть, члена группы. С тех пор он помогает развивать почти сизифову математическую традицию, начавшуюся ещё до Второй мировой войны.

Группа известна под именем Никола Бурбаки, и обычно её называют просто Бурбаки. Это коллективный псевдоним, фамилия которого была позаимствована у реального французского генерала XIX века, не имевшего, правда, никакого отношения к математике. Почему было выбрано такое имя, неясно, хотя, возможно, всё дело в розыгрыше, организованном основателями группы, когда они были ещё студентами парижской Высшей нормальной школы (cole normale suprieure, ENS).

У них была традиция, разыгрывать первокурсников. Один из таких розыгрышей состоял в том, чтобы убедить их, что в школу должен прибыть генерал Бурбаки, чтобы прочесть какую-то непонятную лекцию по математике, сказал Шамберт-Луар, математик из Парижского университета, исполняющий обязанности представителя группы, и единственный из известных её членов.

Группа Никола Бурбаки появилась в 1934 году по инициативе небольшой кучки недавних выпускников ENS. Многие из них были лучшими математиками своего поколения. Тщательно изучив эту область, они обнаружили проблему. Что именно это была за проблема известно только по слухам.

По одной версии, Никола Бурбаки был ответом на потерянное в Первой мировой войне поколение математиков. Основатели группы хотели придумать, как сохранить те математические знания, что ещё остались в Европе.

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

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


Один из учебников математики за авторством Никола Бурбаки под названием Элементы математики: группы и алгебры Ли

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

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

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

Одной из отличительных особенностей Бурбаки был стиль текстов: строгий, формальный, сведённый к чистой логике. В книгах математические теоремы формулировались с самого начала, без всяких пропусков. Такая тщательность необычна для математиков.

По сути, у Бурбаки нет никаких пропусков, сказал Гуэзель. Они сверхточные.

Но такая точность не проходит даром книги Никола Бурбаки очень сложно читать. Они не предлагают объяснений происхождения концепций, давая идеям говорить самим за себя.

Никаких комментариев по поводу того, что там происходит и почему, сказал Шамберт-Луар. Вещи постулируются и доказываются, ничего более.

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


Никола Бурбаки остаётся тайным обществом, подчёркивая коллективную природу работы, хотя жёстких мер для сохранения анонимности членов не предпринимается

Упорство в сохранении анонимности проистекает именно из концентрации на совместной работе. Группа хранит тайну своего состава, подчёркивая идею о том, что книги являются чистым выражением математики по её сути, а не мнением отдельных субъектов. Такая этика кажется несовместимой с современной культурой математики.

Сложно представить себе, чтобы группа современных молодых учёных, людей, не имеющих постоянной работы на всю жизнь, посвящала огромное количество времени чему-то, за что они не получат признания, сказала Лилиан Пирс из университета Дьюка. Данная группа построена на альтруизме.

Группа Никола Бурбаки быстро стала влиять на математику. Некоторые из первых книг, опубликованные в 1940-х и 1950-х годах, ввели новый лексикон, сегодня являющийся стандартом например, такие термины, как инъекция, сюръекция и биекция, использующиеся для описания отношений между множествами.

Это был первый из двух главных периодов особого влияния Бурбаки на математику. Второй начался в 1970-х, когда группа опубликовала несколько книжек по группам Ли и алгебрам Ли, который повсеместно считается шедевром, сказал Шамберт-Луар.


Члены Никола Бурбаки ценят совместную работу, обсуждают работы вместе, проговаривая их вслух, и публикуют тексты только после всеобщего согласия.

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

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

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

Хотя их семинары сегодня стали более влиятельными, чем их книги, группа Бурбаки в которую входят порядка 10 человек всё ещё публикует тесты, соответствующие их основополагающим принципам. Время присутствия Шамберт-Луара в группе подходит к концу, поскольку ему уже 49 лет, а по традиции люди покидают группу по достижении 50.

Хотя он готовится выйти из группы, проект, который ему доверили после его первой недели работы, ещё не закончен. 15 лет я терпеливо записывал его на LaTeX, вносил правки, и год за годом мы всё это читали вслух, сказал он.

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

Быстрый поиск касательных и пересечений у выпуклых многоугольников

15.11.2020 18:09:06 | Автор: admin

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


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


Касательные


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


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


Доказательство

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


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


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


Все случаи выше показаны на картинке. Красным показан какой-то путь, пунктиром сокращенный путь.



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


Наивный алгоритм


Самый простой метод построить касательные из точки это перебрать все вершины полигона и найти те, где обе стороны лежат по одну сторону от прямой точка-вершина. Понять. что стороны лежат по одну сторону можно проверив знаки векторных произведений векторов сторон (v1, v2) и вектора из точки (v):
касательная Не касательная


Получается что-то вроде такого:


// |p| хранит вершины полигона в порядке обхода против часовой стрелки.// Класс Point используется для хранения точек или векторов. // Оператор ^ переопределен для векторного произведения. // Оператор - переопределен для векторной разностиstd::pair<int, int> Polygon::GetTangentIds(const Point &a) {    int n = p.size();    std::pair<int, int> res = { -1, -1 };    for (int i = 0; i < n; ++i) {        if (p[i] == a) {            res = { i, i };            break;        }        Point v1 = p[i] - p[(i + n - 1) % n];        Point v = p[i] - a;        Point v2 = p[(i + 1) % n] - p[i];        double dir1 = v1 ^ v;        double dir2 = v ^ v2;        if (dir1 < eps && dir2 < -eps) {            res.first = i;        }        if (dir1 > eps && dir2 > -eps) {            res.second = i;        }    }    return res;}

Обратите внимание на сравнения с eps так правильно сравнивать вещественные числа, чтобы ошибки округления не ломали алгоритм. Плюс или минус выбираются в зависимости от строгости сравнения. < -eps это значит строго меньше 0, < eps значит меньше равно. Знаки расставлены в коде выше так, чтобы выбрать самую удаленную вершину, если точка a лежит на продолжении стороны.


Этот метод работает за O(n). Можно отдельно рассмотреть случай вершины номер 0 и номер n-1, чтобы избавиться от модуля.


Быстрый логарифмический алгоритм


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


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


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


Если вектор-сторона идет слева направо относительно вектора на начало стороны, то это лицевая сторона. В противном случае это обратная сторона. Концы касательных это вершины между "лицевыми" и "обратными" сторонами.


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



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


Давайте для конкретики введем "знаки" у вершин. Все вершины, сторона из которых идет справа налево относительно вектора из точки начала касательных, обозначим как "+" вершины в них значение векторного произведения будет положительно. Все точки, сторона из которых лежит на лицевой стороне или идет слева направо относительно начала касательных, обозначим "-" в них значение векторного произведения отрицательно.
Есть еще один неприятный случай: некоторые вершины могут иметь нулевое векторное произведение, если касательная совпадает со стороной (обозначим такие вершины "0"-вершинами). Еще более странные случаи, если точка-начало касательных лежит на стороне полигона, или вообще совпадает с вершиной. Ниже приведены все возможные случаи расположения начала касательных и "знаки" вершин:


  1. Касательные не совпадают ни с одной стороной.
  2. Левая касательная совпадает со стороной.
  3. Точка лежит на пересечении двух сторон.
  4. Правая касательная совпадает со стороной.
  5. Точка лежит на стороне.
  6. Точка совпадает с вершиной.
  7. Точка внутри полигона.

Нули могут быть с обоих концов от отрезка из плюсов, минусов может и не быть. Одно точно видно плюсы есть всегда. Поэтому давайте в качестве левой касательной брать "0/-" вершину, перед которой идет "+" вершина, а в качестве правой касательной "+" вершину, перед которой идет "0/-" вершина. Этот подход из нескольких возможных концов (при совпадении стороны и касательной) найдет самую далекую. Если же нужен самый близкий конец, то можно после выполнения логарифмического алгоритма попытаться подвинуть левый конец вперед вдоль полигона, а правый назад. Еще, последний случай (точка внутри полигона) немного все портит. В полигоне ничего кроме "+" нет. И мы никогда не найдем границу между двумя областями. Надо аккуратно проверить, что наш поиск не повисает в этом случае и не выдает какие-то неправильные ответы.


Итак, алгоритм для левой касательной:


1. Проверить, вдруг самая первая вершина удовлетворяет условию касательной. Если это не так, то мы знаем, что переключение между "+" и "0/-" происходит (если оно вообще есть) где-то между вершинами с 0 по n-1.2. l=0, r=n-1.4. Пока r-l > 1:  4.1.  Подсчитать "знак" вершины l.  4.2. Взять m: ceil((l+r)/2). Обратите внимание, условие 4. означает, что l < m < r.  4.3. Подсчитать знак вершины m.  4.4. Присвоить r = m, если выполняется один из трех случаев:      l - "+" и m - "-/0"      l - "+" и m - "+" и l лежит левее m      l - "-/0" и m - "/0" и l лежит правее m (или на одной прямой с ней)  4.5. Иначе присвоить l = m.

Есть один нетривиальный момент, что делать, если l и m имеют одни и те же знаки лежат на одной прямой с точкой начала касательных? Т.е. вершина l не лежит ни строго левее ни строго правее m?


Это возможно только в случаях 2, 3, 6 когда левая касательная совпадает со стороной. Если правая касательная совпадает со стороной, то знаки у вершин будут разные (дальняя всегда +). При этом l и m указывают на 2 соседние вершины! Но, поскольку у нас поддерживается l < m, мы же разорвали цикл и ищем внутри не зацикленного массива, то это значит, что l тот самый искомый конец касательной. Т.е. в случае, если обе вершины имеют знаки "-/0" и лежат на одной прямой, мы должны сдвинуть правый конец. Поэтому в пункте 4.4 сравнения надо делать именно так, если знаки совпадают во втором случае.


Для поиска правой касательной строгость сравнения должна быть в обратную сторону. Если обе вершины "-/0" и они лежат на одной прямой, то надо сдвинуть левую границу.


Итак, весь код алгоритма:


Код
std::pair<int, int> Polygon::GetTangentIdsLogarithmic(const Point& a) const{    std::pair<int, int> res = { -1, -1 };    const int n = points_.size();    Point vl = points_[1] - points_[0];    Point to_l = points_[0] - a;    Point v_prev = points_[0] - points_[n - 1];    Point to_prev = points_[n - 1] - a;    double pointing_l = to_l ^ vl;    double pointing_prev = to_prev ^ v_prev;    int l = 0;    int r = n - 1;    // Проверка, что вершина 0 - левая касательная.    if (pointing_prev > eps && pointing_l < eps) {        res.first = 0;        // Случай совпадения касательной и стороны        if (pointing_l > -eps) {            Point v_next = points_[2] - points_[1];            Point to_next = points_[1] - a;            double pointing_next = to_next ^ v_next;            // точка начала еще может лежать на стороне            if (pointing_next < -eps) {                res.first = 1;            }            else if (pointing_next < eps) {                // Или совпадать с вершиной 1.                return { 1, 1 };            }        }    }    else {        // Бинарный поиск.        while (l < r - 1) {            int m = (r + l + 1) / 2;            Point vm = points_[m + 1] - points_[m];            Point to_m = points_[m] - a;            double pointing_m = to_m ^ vm;            double lm_dir = to_l ^ to_m;            if (((pointing_m < eps) || (lm_dir < -eps)) &&                ((pointing_l > eps) || (lm_dir > -eps))) {                r = m;            }            else {                l = m;                to_l = to_m;                pointing_l = pointing_m;            }        }        // На случай, если |a| лежит внутри полигона, надо проверить, что бинпоиск        // остановился на ответе, а не просто на случайной вершине.        int next = (r + 1) % n;        Point to_r = points_[r] - a;        Point vr = points_[next] - points_[r];        double pointing_r = to_r ^ vr;        if (pointing_r < eps && pointing_l > eps) {            res.first = r;            // Проверка, что |a| лежит на продолжении стороны.            Point v_next = points_[(next + 1) % n] - points_[next];            Point to_next = points_[next] - a;            double pointing_next = to_next ^ v_next;            if (pointing_r > -eps) {                // Проверка, что |a| не лежит на стороне.                if (pointing_next < -eps) {                    res.first = next;                }                else if (pointing_next < eps) {                    // Или совпадает с вершиной.                    return { next, next };                }            }        }        else return { -1, -1 };    }    // Теперь работаем с правой касательной.    vl = points_[1] - points_[0];    to_l = points_[0] - a;    v_prev = points_[0] - points_[n - 1];    to_prev = points_[n - 1] - a;    pointing_l = to_l ^ vl;    pointing_prev = to_prev ^ v_prev;    l = 0;    r = n - 1;    // Проверка первой вершины    if (pointing_prev < eps && pointing_l > eps) {        res.second = 0;        // Может ее надо подвинуть назад.        if (res.first != n - 1 && pointing_prev > -eps) {            res.second = n - 1;        }    }    else {        while (l < r - 1) {            int m = (r + l + 1) / 2;            Point vm = points_[m + 1] - points_[m];            Point to_m = points_[m] - a;            double pointing_m = to_m ^ vm;            double lm_dir = to_l ^ to_m;            if (((pointing_l < eps) || (lm_dir < eps)) &&                ((pointing_m > eps) || (lm_dir > eps))) {                r = m;            }            else {                l = m;                to_l = to_m;                pointing_l = pointing_m;            }        }        // Проверка, что бинпоиск остановился на ответе.        Point to_r = points_[r] - a;        Point vr = points_[(r + 1) % n] - points_[r];        double pointing_r = to_r ^ vr;        if (pointing_r > eps && pointing_l < eps) {            res.second = r;            // Проверка, что ответ нужно подвинуть назад.            if ((res.first != l) && pointing_l > -eps) {                res.second = l;            }        }    }    return res;}

Несмотря на длинный и, возможно, пугающий код, этот алгоритм работает быстрее наивного уже при n=4.


Проверка пересечения отрезка и полигона за O(1)


*terms and conditions apply.


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


Оба этих допущения выполняются в моей библиотеке поиска кратчайшего пути вокруг препятствий. Возможных отрезков, которые нужно проверять на пересечение O(k*n^2), если у нас n полигонов с k вершинами. Когда как точек, из которых они торчат всего O(k*n). Поэтому гораздо быстрее сначала проверить все точки-концы отрезков по одному разу и вычеркнуть все отрезки из плохих точек. Второе допущение выполняется, потому что все касательные на все полигоны мы и так строим это же и есть кандидаты на ребра в графе кратчайших путей. Для проверки на пересечения они достаются бесплатно.


Итак, нам даны полигон, отрезок с концами вне полигона и касательные из одного конца отрезка. Если отрезок пересекает полигон, то он точно должен пересекать и хорду между двумя концами касательных (иначе один из его концов должен был бы лежать внутри полигона). Т.е. получается, что нужно проверить пересечение лишь с одним отрезком, а это можно сделать за O(1).

Подробнее..

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

30.11.2020 12:14:44 | Автор: admin


В комбинаторике сочетанием из $inline$n$inline$ по $inline$k$inline$ называют набор $inline$k$inline$ элементов, выбранных из $inline$n$inline$ элементов. В отличие от размещений, число сочетаний не учитывает последовательность размещения элементов, например: Сколько групп из 4 человек, можно получить, если всего в классе 20 человек?. Хотя удобные способы подсчёта давно известны, на ещё два стоит взглянуть.

Обозначается сочетание из $inline$n$inline$ по $inline$k$inline$ так: $inline$C_n^k$inline$. В литературе они чаще обозначаются $inline$ \binom nk$inline$ (но мне больше нравится первый вариант, чтобы не путать с матрицами).

В комбинаторике известны несколько способов подсчёта:

$$display$$C_n^k = \frac{n!}{k!(nk)!}$$display$$

$$display$$C_n^k=\frac{n(n1)(n2)(nk+1)}{k!}=\frac{\prod\limits_{i = nk+1}^n i}{k!}$$display$$

Где $inline$n!$inline$ эн факториал, произведение всех целых чисел от 1 до n (например: $inline$4!=1\cdot2\cdot3\cdot4=24$inline$), а $inline$0!$inline$ считается равным единице. Для вышесказанной задачи получается:

$$display$$C_{20}^4 = \frac{20!}{4!(204)!} = \frac{17\cdot18\cdot19\cdot20}{1\cdot2\cdot3\cdot4} = 4845$$display$$

Или так:

$$display$$C_{20}^4=\frac{20\cdot19\cdot18\cdot17}{4!}=\frac{116280}{24}=4845$$display$$


Вторая формула сочетаний выводится очень просто. Есть понятие числа размещений из $inline$n$inline$ по $inline$k$inline$, когда последовательность элементов имеет значение (то есть набор первый со вторым с пятым это не тоже самое, что первый с пятым со вторым), обозначается $inline$A_n^k$inline$.

Например все размещения из 3 по 2 выглядят так:

12 21
13 31
23 32


Первый элемент можно выбрать $inline$n$inline$ способами, второй $inline$(n1)$inline$ способами, последний $inline$(n(k1))$inline$ способами. Поэтому число размещений из $inline$n$inline$ по $inline$k$inline$ равно $inline$n(n1)(n2)(nk+1)$inline$, всего $inline$k$inline$ множителей.

Для подсчёта сочетаний получившиеся число нужно разделить на $inline$k!$inline$, поскольку есть $inline$k!$inline$ способов разместить $inline$k$inline$ элементов. В данном случае $inline$2!=2$inline$ способа (первый со вторым и второй с первым это одно и тоже сочетание).

Вспомним, как идет счёт в шашках по круговой системе (когда все играют со всеми). Для этого пишут обычную таблицу:

По горизонтали и вертикали идут номера игроков. Диагональ можно закрасить игрок не может играть сам с собой. Результат каждой партии записывают в таблицу два раза. Как сыграл второй с пятым и как сыграл пятый со вторым. Таким образом, количество партий в турнире и есть число сочетаний по 2.

Число вычеркнутых клеток равно $inline$n$inline$, а число всех клеток это $inline$n^2$inline$. Стало быть, число сочетаний по 2 можно посчитать так:

$$display$$C_n^2=\frac{n^2n}{2}$$display$$

Когда я это заметил, не сразу увидел что это равно $inline$\frac{n(n1)}{2!}$inline$. Решил сделать также для $inline$k=3$inline$, с трёхмерной таблицей:

На каждом её слое, кроме диагонали исключаются еще клетки. Например, клетка 161 исключается, потому что единица повторилась два раза.

Всего на каждом слое исключается $inline$n+2(n1)$inline$ клеток.

$$display$$n+2(n1)=3n2$$display$$






Итак, на каждом слое исключается $inline$3n2$inline$ клетки. Всего $inline$n$inline$ слоёв, поэтому общее число исключившихся ячеек:

$$display$$n(3n2)=3n^22n$$display$$

А вся таблица $inline$n^3$inline$. Значит, число сочетаний по 3 можно посчитать так:

$$display$$C_n^3=\frac{n^3(3n^22n)}{3!}=\frac{n^33n^2+2n}{3!}$$display$$

Как уже сказано выше, это и есть общая формула, в которой просто раскрыли скобки:

$$display$$C_n^3=\frac{n^33n^2+2n}{3!}=\frac{n(n1)(n2)}{3!}$$display$$

И тут возник вопрос, можно ли посчитать сочетания, так же представив их через таблицы, не используя факториалы вообще? К слову, в комбинаторике уже известна рекуррентная формула для числа сочетаний: $inline$C_n^k=C_{n1}^{k1}+C_{n1}^k$inline$ (число сочетаний по 0 равно 1, из любого количества элементов можно получить только одну группу в которой 0 элементов). Итак, я попробовал посмотреть, какие еще клетки исключаются в трёхмерной таблице, когда мы делим число оставшихся клеток на $inline$k!$inline$.

Клетки ниже диагонали дублируют клетки, которые выше диагонали вычеркнем их (ячейка 431 то же самое, что и 341). Для того, чтобы получить такое же количество клеток, просто поделим число размещений на 2. Цифрами в самой таблице я отметил, в какой строке встретилось данное сочетание. Например, сочетание 251 впервые встретилось здесь во второй строке, поэтому отмечено цифрой 2. Посмотрим на следующий слой:

Закрашенные клетки с цифрой означают, что данное сочетание уже встречалось. Например, комбинация 152 уже встречалась во второй строке (в виде 251), поэтому отмечена цифрой 2 в закрашенной клетке.

Итак, на втором слое исключается ещё $inline$(n2)$inline$ клетки (кроме тех, которые вычеркнуты из-за повторяющихся чисел в них, и тех, которые вычеркнуты ниже диагонали, из-за того что дублируют верхние). Перебрав так всю таблицу, я получил следующее. На третьем слое исключается ещё $inline$(n2)+(n3)$inline$ клеток:

На четвертом слое вычеркивается ещё $inline$(n2)+(n3)+(n4)$inline$ клеток:

На пятом $inline$(n2)+(n3)+(n4)+(n5)$inline$:

На шестом, по видимому, $inline$(n2)+(n3)+(n4)+(n5)+(nn)$inline$:

Получается, что для подсчёта сочетаний по 3, из числа $inline$\frac{n(n1)(n2)}{2}$inline$ нужно вычесть такую сумму:

$$display$$(n2)+((n2)+(n3))+((n2)+(n3)+(n4))+\\((n2)+(n3)+(n4)+(n5))+((n2)+(n3)+(n4)+(n5)+(nn))$$display$$

Это можно переписать в таком виде:

$$display$$\sum_{i=2}^n{\sum_{j=2}^i(nj)}$$display$$

Ещё можно переписать эту сумму так:

$$display$$5(n2)+4(n3)+3(n4)+2(n5)+(nn)=\\(n1)(n2)+(n2)(n3)+(n3)(n4)+(n4)(n5)+(n5)(nn)$$display$$

То есть:

$$display$$\sum_{i=2}^{n1}{(ni)(ni+1)}$$display$$

Значит, число сочетаний по 3 можно вычислить так:

$$display$$C_n^3=\frac{n(n1)(n2)}{2}\sum_{i=2}^n\sum_{j=2}^i(nj)=\frac{n(n1)(n2)}{2}\sum_{i=2}^{n1}{(ni)(ni+1)}$$display$$

Например число сочетаний из 8 по 3:

$$display$$C_8^3=\frac{8\cdot7\cdot6}{2}\sum_{i=2}^7{(n-i)(n-i+1)}=\\ 168(6\cdot7+5\cdot6+4\cdot5+3\cdot4+2\cdot3+1\cdot2)=\\ 168112=56$$display$$

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

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

$$display$$\begin{pmatrix}-\\0+\\(n3)+\\(n3)+(n4)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+(nn)\end{pmatrix}$$display$$

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

Значит, на втором слое исключается такая сумма:

$$display$$\begin{pmatrix}(n3)+(n4)+(n5)+\\-\\(n3)+\\(n3)+(n4)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)\end{pmatrix}=\begin{pmatrix}-\\(n3)+\\(n3)+(n4)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)\end{pmatrix}$$display$$

Посмотрим на третий:

На третьем исключается сумма:

$$display$$\begin{pmatrix}(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\-\\(n3)+(n4)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)\end{pmatrix}=\begin{pmatrix}-\\(n3)+(n4)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)\end{pmatrix}$$display$$

Уже здесь видно, что общая сумма, которая будет вычитаться будет такой:

$$display$$\begin{pmatrix}-\\0+\\(n3)+\\(n3)+(n4)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)\end{pmatrix}+\begin{pmatrix}-\\(n3)+\\(n3)+(n4)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)\end{pmatrix}+\\\begin{pmatrix}-\\(n3)+(n4)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)\end{pmatrix}+\begin{pmatrix}-\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)\end{pmatrix}+\\\begin{pmatrix}-\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)\end{pmatrix}+\begin{pmatrix}-\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)\end{pmatrix}$$display$$

её можно переписать в таком виде:

4(n3)+3(n4)+2(n5)+1(nn)+
5(n3)+4(n4)+3(n5)+2(nn)+
5(n3)+5(n4)+4(n5)+3(nn)+
5(n3)+5(n4)+5(n5)+4(nn)+
5(n3)+5(n4)+5(n5)+5(nn)+
5(n3)+5(n4)+5(n5)+5(nn)


Получаем:

$$display$$29(n3)+27(n4)+24(n5)+20(nn)$$display$$

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

$$display$$C_n^4=\frac{n(n1)(n2)(n3)}{2}\sum_{i=3}^{n1}{(ni)\left(30\sum_{j=1}^{i2}j\right)}$$display$$

Однако, получившаяся формула будет работать только для $inline$n=6$inline$, ведь для других $inline$n$inline$ коэффициенты будут другие. И, поскольку я не увидел зависимости от $inline$k$inline$ и здесь, решил посмотреть тоже самое для $inline$k=5$inline$, через пятимерную таблицу, весь её первый трёхмерный слой исключается, поскольку единица здесь повторяется во всех ячейках:

Для наглядности запишем это так:

$$display$$\begin{pmatrix}-\\-\\-\\-\\-\\-\end{pmatrix}$$display$$


Смотрим дальше:

Тут, как видно, вычитается такая сумма:

$$display$$\begin{pmatrix}-\\-\\0\\(n4)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}$$display$$

Третий:

Тут вычитается:

$$display$$\begin{pmatrix}-\\(n4)+(n5)+\\-\\(n4)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}=\begin{pmatrix}-\\-\\(n4)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}$$display$$



$$display$$\begin{pmatrix}-\\(n4)+(n5)+\\(n4)+(n5)+\\-\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}=\begin{pmatrix}-\\-\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}$$display$$



$$display$$\begin{pmatrix}-\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)+\\-\\(n4)+(n5)\end{pmatrix}=\begin{pmatrix}-\\-\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}$$display$$


Затем, шестой фрагмент:

$$display$$\begin{pmatrix}-\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\\-\end{pmatrix}=\begin{pmatrix}-\\-\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}$$display$$


На этом первый четырёхмерный слой заканчивается. Не сложно понять, что трёхмерный слой 21 будет дублировать слой 12, а слой 22 исключится весь, также как 11.

Перейдем к слою 23:

Здесь встретилось последнее сочетание из 6 по 5 56423 (клетки, которые встретились впервые отмечены белым, если кто забыл)). Напишем, какую в итоге надо вычесть сумму из $inline$\frac{n(n1)(n2)(n3)(n4)}{2}$inline$, чтобы получить число сочетаний из $inline$n$inline$ по 5. На первом четырёхмерном слое исключилось:

$$display$$\begin{pmatrix}-\\-\\-\\-\\-\\-\end{pmatrix}+\begin{pmatrix}-\\-\\0+\\(n4)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}+\begin{pmatrix}-\\-\\(n4)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}+\begin{pmatrix}-\\-\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}+\\\begin{pmatrix}-\\-\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}+\begin{pmatrix}-\\-\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}$$display$$

На втором:

$$display$$\begin{pmatrix}-\\-\\-\\-\\-\\-\end{pmatrix}+\begin{pmatrix}-\\-\\(n4)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}+\begin{pmatrix}-\\-\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}+\begin{pmatrix}-\\-\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}+\\\begin{pmatrix}-\\-\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}+\begin{pmatrix}-\\-\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}$$display$$

Получается что каждая сумма в скобке обозначает исключившиеся ячейки на трёхмерных слоях. Всего $inline$n$inline$ четырёхмерных слоёв. Запишем это в виде суммы:

$$display$$\begin{aligned} &C_n^5=\frac{n(n1)(n2)(n3)(n4)}{2}\sum_{i_3=1}^n\sum_{i_2=1}^{nk+4}\sum_{i_1=a}^n\sum_{i_0=k1}^b(ni_0)\\ &a=\left\{ \begin{aligned} &k1, \ если \ i_2=i_3=1 \\ &k2, \ иначе \\ \end{aligned}\right.\\ &b=\left\{ \begin{aligned} &i_12+i_2+i_3, \ если \ i_12+i_2+i_3\leqslant n1 \\ &n1, \ иначе \\ \end{aligned}\right. \end{aligned}$$display$$

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

Индекс второй суммы берем до $inline$(nk+4)$inline$, поскольку она образует исключения на четырёхмерных слоях, суммируя вычеркнутые ячейки на трёхмерных, как мы могли видеть выше, у пятимерной таблицы на каждом четырёхмерном слое исключается один трёхмерный, то есть для $inline$n=6$inline$, на каждом четырёхмерном остается пять трёхмерных слоёв, $inline$65+4=5$inline$.

Для $inline$k=6$inline$, шестимерную таблицу можно не смотреть, достаточно выписать индексы её последних трёх измерений:

111 121 131 141 151 161
112 122 132 142 152 162
113 123 133 143 153 163
114 124 134 144 154 164
115 125 135 145 155 165
116 126 136 146 156 166

211
212


Опять же, вычеркнули мы те слои, где хоть одна цифра повторилась. Уже по первому пятимерному слою видно, что на пятимерных слоях для шестимерной таблицы останется на один четырёхмерный слой меньше. Количество оставшихся четырёхмерных слоёв равно $inline$(nk+5)$inline$. А трёхмерных слоёв на каждом четырёхмерном остается все также $inline$(nk+4)$inline$ (по 4 в данном случае: $inline$66+4$inline$). Запись в виде сумм получилась такой:

$$display$$\begin{aligned} &C_n^6=\frac{n(n1)(n2)(n3)(n4)(n5)}{2}\sum_{i_4=1}^n\sum_{i_3=1}^{nk+5}\sum_{i_2=1}^{nk+4}\sum_{i_1=a}^n\sum_{i_0=k1}^b(ni_0)\\ &a=\left\{ \begin{aligned} &k1, \ если \ i_2=i_3=i_4=1 \\ &k2, \ иначе \\ \end{aligned}\right.\\ &b=\left\{ \begin{aligned} &i_13+i_2+i_3+i_4, \ если \ i_13+i_2+i_3+i_4\leqslant n1 \\ &n1, \ иначе \\ \end{aligned}\right. \end{aligned}$$display$$


Запись для $inline$k=3$inline$ можно переписать так:

$$display$$\begin{aligned} &C_n^3=\frac{n(n1)(n2)}{2}\sum_{i_1=a}^n\sum_{i_0=k1}^b(ni_0)\\ &a=k1\\ &b=\left\{ \begin{aligned} &i_1, \ если \ i_1\leqslant n1 \\ &n1, \ иначе \\ \end{aligned}\right. \end{aligned}$$display$$


Для $inline$k=4$inline$ получается:

$$display$$\begin{aligned} &C_n^4=\frac{n(n1)(n2)(n3)}{2}\sum_{i_2=1}^n\sum_{i_1=a}^n\sum_{i_0=k1}^b(ni_0)\\ &a=\left\{ \begin{aligned} &k1, \ если \ i_2=1 \\ &k2, \ иначе \\ \end{aligned}\right.\\ &b=\left\{ \begin{aligned} &i_11+i_2, \ если \ i_11+i_2\leqslant n1 \\ &n1, \ иначе \\ \end{aligned}\right. \end{aligned}$$display$$


Для $inline$k=5$inline$:

$$display$$\begin{aligned} &C_n^5=\frac{n(n1)(n2)(n3)(n4)}{2}\sum_{i_3=1}^n\sum_{i_2=1}^{nk+4}\sum_{i_1=a}^n\sum_{i_0=k1}^b(ni_0)\\ &a=\left\{ \begin{aligned} &k1, \ если \ i_2=i_3=1 \\ &k2, \ иначе \\ \end{aligned}\right.\\ &b=\left\{ \begin{aligned} &i_12+i_2+i_3, \ если \ i_12+i_2+i_3\leqslant n1 \\ &n1, \ иначе \\ \end{aligned}\right. \end{aligned}$$display$$


В общем виде запись для $inline$k\geqslant2$inline$ получается такой (сумма, которую мы вычитаем вычисляется рекуррентно):

$$display$$\begin{aligned} &C_n^k=\frac{\prod\limits_{i=nk+1}^ni}{2}c_k\\ &k_0=k\\ &c_k=\left\{\begin{aligned} &0, \ k=2 \\ &\sum_{i_3=a}^{n}\sum_{i_2=k1}^{b}(ni_2), \ k=3 \\ &\sum_{i_k=1}^{nk_0+k}c_{k1}, \ k\geqslant4 \end{aligned}\right. \\ &a=\left\{ \begin{aligned} &k_01, \ если \ i_4=i_5==i_k=1 \ или \ k_0=3 \\ &k_02, \ иначе \end{aligned}\right.\\ &b=\left\{ \begin{aligned} &i_3(k_03)+i_4+i_5++i_k, \ если\ i_3(k3)+i_4+i_5++i_k\leqslant n1 \ и \ k_0>3 \\ &i_3, \ если\ i_3\leqslant n1 \ и\ k_0=3 \\ &n1, \ иначе \end{aligned}\right. \end{aligned}$$display$$


Второй способ


Как я уже писал выше, число сочетаний по 3 можно записать через одну сумму:

$$display$$C_n^3=\frac{n(n1)(n2)}{2}\sum_{i=2}^n\sum_{j=2}^i(nj)=\frac{n(n1)(n2)}{2}\sum_{i=2}^{n1}{(ni)(ni+1)}$$display$$

А число сочетаний из 6 по 4 можно записать так:

$$display$$C_n^4=\frac{n(n1)(n2)(n3)}{2}\sum_{i=3}^{n1}{(ni)\left(30\sum_{j=1}^{i2}j\right)}$$display$$

Оказывается, что 30 во вторых скобках, это $inline$n(n1)$inline$ (логического обоснования этому я так и не смог найти).

$$display$$C_n^4=\frac{n(n1)(n2)(n3)}{2}\sum_{i=3}^{n1}{(ni)\left(n(n1)\sum_{j=1}^{i2}j\right)}$$display$$

Вторые скобки здесь представляют собой коэффициент, который умножается на $inline$(ni)$inline$. Для $inline$k=3$inline$ этот коэффициент просто уменьшается на 1 с каждым слагаемым первой суммы. Для $inline$4$inline$ число, на которое уменьшается этот коэффициент возрастает на 1. Затем я просто посчитал количество слагаемых $inline$(n4)$inline$, $inline$(n5)$inline$ и $inline$(nn)$inline$ в сумме которая вычитается для $inline$5$inline$:

$$display$$119(n4)+116(n5)+110(nn)$$display$$

Число, на которое увеличивается число, на которое уменьшается коэффициент, возрастает на 1. Этот коэффициент можно записать через две суммы:

$$display$$C_n^5=\frac{n(n1)(n2)(n3)(n4)}{2}\sum_{i=4}^{n1}{(ni)\left(n(n1)(n2)\sum_{j_1=1}^{i3}\sum_{j_0=1}^{j_1}j_0\right)}$$display$$

Зависимость ясна для $inline$k=6$inline$ эта формула будет выглядеть так:

$$display$$C_n^6=\frac{n(n1)(n2)(n3)(n4)(n5)}{2}\\\sum_{i=5}^{n1}{(ni)\left(n(n1)(n2)(n3)\sum_{j_2=1}^{i4}\sum_{j_1=1}^{j_2}\sum_{j_0=1}^{j_1}j_0\right)}$$display$$

А в общем виде (опять же, для $inline$k\geqslant2$inline$) получилось так:

$$display$$\begin{aligned} &C_n^k=\frac{\prod\limits_{i=nk+1}^ni}{2}c_k\\ &k_0=k\\ &c_k=\left\{ \begin{aligned} &0, \ k=2 \\ &\sum_{i=k1}^{n1}{(ni)\left(\prod_{j_k=nk+3}^nj_kd_k\right)}, \ если \ k\geqslant3 \\ \end{aligned}\right.\\ &d_k=\left\{ \begin{aligned} &i1, \ k=3 \\ &\sum_{j_4=1}^lj_4, \ k=4 \\ &\sum_{j_k=1}^ld_{k1}, \ если \ k>4 \\ &l=j_{k+1}, \ если \ k\neq k_0 \\ &l=ik_0+2, \ если \ k = k_0 \\ \end{aligned}\right.\\ \end{aligned}$$display$$

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

Оптимизация цифрового автомата (FSM)

29.11.2020 14:18:58 | Автор: admin
О чём пост?

Данный материал представляет краткое описание проблемы в теории цифровых автоматов и объясняет один из способов решения данной проблемы, который был найден при попытке автоматизации процесса построения цифрововых автоматов.

Введение

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

Термин <<автомат>> в основном используется в двух аспектах:

  • техническом;

  • математическом.

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

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

С точки зрения сигналов цифровой автомат (ЦА) система, которая может принимать входные сигналы, под их воздействием переходить из одного состояния в другое, сохранять его до прихода следующего входного сигнала, выдавать выходные сигналы.

В данной работе рассматриваются цифровые сигналы и двоичная логика на базе логических элементов.

Структурно-функциональная схема цифрового конечного автоматаСтруктурно-функциональная схема цифрового конечного автомата

Применение

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

Другое важнейшее применение теории автоматов математически строгое нахождение разрешимости и сложности задач.

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

Описание проблемы

Построение цифрового автомата -- довольно трудоёмкий процесс. Можно выделить следующие этапы разработки ЦА:

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

2) Оптимизация графа -- с этой задачей человек может справиться довольно быстро.

3) Определение разрядности памяти. Минимальное число триггеров можно вычислить по формуле:

n=ceil(log_2(S))

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

4) Присвоение состояниям кодов. Алгоритма для правильного задания кодов для состояний нет. Именно от этого зависит сложность уравнений, которые мы получим для входов триггеров и количество элементов необходимых для сборки схемы.

5) Составление таблицы состояний-переходов.

6) Составление булевых арифметических уравнений для входов триггеров. Карты Карно составляются по таблице состояний-переходов, уравнения минимизируются.

7) Преобразование уравнений для согласования с элементной базой.

8) Разработка электрической схемы.

Основная проблема -- отсутствие алгоритма для задания кодов состояниям автомата таким образом, чтобы уравнения для входов триггеров были как можно проще.

Решение

Была разработана программа для построения цифровых автоматов. На вход программа принимает граф. В программе граф представляется в наборе вершин и рёбер(вершина, входной сигнал, вершина для перехода). Итерируясь по рёбрам составляются таблицы истинности для каждого разряда в СКНФ и СДНФ. Методом Куайна-Мак-Класки минимизируются обе формы уравнений. Для каждого разряда выбирается выражение с минимальным количеством логических операций <<И>>, <<ИЛИ>>. Общее количество этих операций является критерием качества данной кодировки.

Количество возможных вариантов задания состояний можно рассчитать зная разрядность памяти(M) и количество состояний(S).

Количество кодов:

C=2^M;

Количество вариантов выборки(V) нужного количества состояний(S) из всего количества кодов(C), формула из комбинаторики:

V=\frac{C!}{(C-S)! \cdot S!};

Количество возможных вариантов задания состояний(A) равно:

A=S! \cdot V= \frac{C!}{(C-S)!};

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

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

Схема генетического алгоритмаСхема генетического алгоритма

Результаты

Для исследования был спроектирован автомат с числом возможных вариантов задания состояний равным 6720. Для каждого варианта было рассчитано количество необходимых элементов для реализации.

Данный ЦА описывает поведение пчелы (для простоты восприятия), входной сигнал представляет 0(всё спокойно) или 1(пчела видит шершня).

Граф цифрового автомата, описывающий поведение пчелыГраф цифрового автомата, описывающий поведение пчелы

Описание ЦА:

  • Количество состояний: 5

  • Разрядность памяти: ceil(log2(5)) = 3

  • Разрядность входного сигнала: 1

Пример расчёта числа всех возможных вариантов построения автомата:

C=2^M=2^3=8;V=\frac{C!}{(C-S)! \cdot S!}=\frac{8!}{(8-5)! \cdot 5!}=56;A=S! \cdot V= 5! \cdot 56=6720;

Для любой выборки(V) нашлось не менее X(X<S!) перестановок с наилучшим исходом. Наилучший исход -- исход с минимальным числом элементов необходимых для реализации данного автомата. Для поиска способа кодирования c наилучшим исходом достаточно перебрать S! вариантов.

Анализ показал, что наибольшая вероятность встретить автомат с наилучшим исходом -- если количество 0 и 1 в кодах состояний будет равнозначным.

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

Подробнее..

Jupyter для .NET. Как в питоне

18.11.2020 18:12:16 | Автор: admin
Несколько месяцев назад Microsoft рассказали о Jupyter в .NET. Но активности по этому топику очень мало, а ведь тема очень интересная. Но что такое прикольное придумать? Я решил сделать удобный вывод класса Entity из библиотеки символьной алгебры:



Выглядит круче, чем в питоне. Делается просто, доставляет массу удовольствия. Приглашаю под кат!



О Jupyter


Это что-то вроде IDE для создания интерактивных блокнотиков. Вместо того, что бы в привычных средах запускать весь код сразу, здесь вы запускаете его по кускам, сохраняя состояния переменных. Очень удобно для исследований и простых скриптов чего-нибудь подсчитать.

О dotnet/interactive


Этот проект как раз позволяет встроить дотнет в юпитер. То есть вы буквально можете написать

И получать результаты работы кода прямо вот сразу.

Причем некоторые фишки работают из коробки


Об AngouriMath


Это относительно небольшая библиотека символьной алгебры для .NET для работы с математическими выражениями. Разумеется, с математическими выражениями можно работать в одну строку, но это не всегда удобно/красиво.

Все математические выражения так или иначе наследуются от класса Entity, который имеет метод Latexise, возвращающий строку. Поэтому остается всего лишь его отрендерить.

Встраиваем латех


У нас есть возможность зарегистрировать собственный вывод для наших типов, что я и делаю:

let magic() =    let register (value : ILatexiseable) = $@"            <script src='https://polyfill.io/v3/polyfill.min.js?features=es6'></script>            <script id='MathJax-script' async src='https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js'></script>            \[{value.Latexise()}\]            "    Formatter.Register<ILatexiseable>(register, "text/html")

(хабр почему-то не поддерживает F#)

То есть мы просто регистрируем, что тип ILatexiseable должен выводиться в html-формате, а сам код будет генерироваться нашей функцией. Для рендеринга я взял MathJax, хотя наверное имеет смысл кешировать js-скрипт, но это для будущих обновлений.

Ну и собственно все, теперь все выражения, унаследованные от этого интерфейса, будут красиво рендериться. Вот как это выглядит в C#:



Что именно тут происходит?
1. В первом блоке мы вызываем extension-метод ToEntity(), который парсит выражение
2. Во втором блоке мы создаем систему уравнений и сразу ее выводим
3. В третьем создается матрица и сразу выводится


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



Дальнейшие планы


Я очень большой любитель .NET-а, но я также очень люблю Jupyter. Поэтому Interactive меня очень порадовал, и я поспешил сделать поддержку Interactive для AngouriMath для вывода выражений в LaTeX. Но дальше интереснее. Я думаю сделать что-то типа Entity.Plot(), который выводил бы сразу график функции. Для простых use-кейсов очень нужна штука, мне кажется.

Если хочется попробовать не устанавливая ничего из необходимого, вы можете потыкаться тут: (аларм: почему-то долго грузится, придется подождать)

Спасибо за внимание! Такая вот короткая заметка.

Ссылки


1. Jupyter удобная браузерная среда для интерактивного программирования
2. .NET Interactive та самая гениальная вещь, благодаря которой можно использовать дотнет в юпитере
3. AngouriMath математическая библиотека, для которой я написал оболочку для латеха
4. MyBinder демка для ленивых
Подробнее..
Категории: C , Математика , Net , F , Jupyter notebook , Jupyter , Latex , Angourimath

Не сломать, не потерять теория шара

14.11.2020 14:23:20 | Автор: admin
Изя, вычисли объём шара
Шара необъятна

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

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

В этой статье я поставил цель последовательно описать своё понимание такого загадочного феномена как округлость. Что значит шар.

Задачка.
Возьмём квадрат, угловые точки которого двигаются с некоторыми ограничениями:
1. Площадь четырёхугольника не меняется.
2. Все стороны четырёхугольника не различаются между собой по длине.
3. Первый угол не движется.
4. Второй угол не смещается перпендикулярно направлению к третьему углу. (Как не смещается заднее колесо у велосипеда вбок)
Вопрос: куда движется четвёртый угол, если для второго угла из оставшихся ему движений, от третьего или к третьему, оставить только от третьего.
Это тест на базовый математический интеллект.
Простые ответы к третьему, от третьего, или от третьего или к третьему недостаточно точны.

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

Вращение


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

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

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

Производная простой функций, $x^n (n > 0)$, может быть рассчитана исходя из определения производной:

$(x^n)'_x=\lim_{d \to 0}((x+d)^n-x^n)/d=\\ =\lim_{d \to 0}((x^n + n d x^{n-1}+_{n \geq 2}d^2(...))-x^n)/d =\\= \lim_{d \to 0} n x^{n-1} + _{n \geq 2}d(...)= nx^{n-1}$

Экспоненту можно определить как функцию, производная по аргументу которой совпадает с самой функцией. Для определённости и нетривиальности функция в точке ноль равна единице. Вывести функцию можно, заметив, что производная от степенной функции понижает степень, последовательно приводя к константе, а затем к нулю. Если мы пойдём обратно, начиная с 1, затем добавляя такие слагаемые, которые в качестве производной дают предыдущее слагаемое, то мы получим функцию, которая равна своей производной. Просто потому, что производная такой суммы приводит к тем же самым членам суммирования.

$\begin{matrix} &&&&&\left(1\right)'_x&=0\\ &&&\left(x\right)'_x&=&1\\ &\left(\frac{x^2}{2}\right)'_x&=&x\\ \left(\frac{x^3}{6}\right)'_x=&\frac{x^2}{2}\\ \end{matrix}$



$e[x]=1+x+\frac{x^2}{2}+\frac{x^3}{6}+\frac{x^4}{24}+...=\sum_{n=0}^{\infty}\frac{x^n}{n!}$


$e[x]=1+x\left(1+\frac{x}{2}\left(1+\frac{x}{3}\left(1+\frac{x}{4}\left(...\right)\right)\right)\right)=\sum_{n=0}^{\infty}\frac{x^n}{n!}$


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

$(e[kx])'_x=k e[kx]$

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

Даже если скорость будет не пропорциональна положению относительно центра, но точно перпендикулярна ему, это будет, возможно, не равномерное, но всё же, вращение, на том же удалении, которое было изначально. Ускорению для этого нужно будет работать на соблюдение перпендикулярности скорости относительно положения.

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

$e[ix] = 1 + ix + \frac{(ix)^2}{2} + \frac{(ix)^3}{6} + ... =\\= 1 + ix - \frac{x^2}{2} - i\frac{x^3}{6} + ... =\\= 1 - \frac{x^2}{2} + ... + ix - i\frac{x^3}{6} + ... =\\=1+ \sum_{n=1}^{\infty}(-1)^n\frac{x^{2n}}{(2n)!} +i \sum_{n=0}^{\infty}(-1)^n\frac{x^{2n+1}}{(2n+1)!} =\\= \cos(x) + i \sin(x)$

Получились отдельные функции для координат.

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

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

При достижении восьмой части окружности чётные и нечётные члены разложения экспоненты дают одинаковые суммы.

$ \\e\left[\frac{ix}{4}\right]=ie\left[\frac{x}{4i}\right] \qquad\cos\left(\frac{x}{4}\right)=\sin\left(\frac{x}{4}\right) $

После этого равенство сохраняется, только если двигаться в противоположные стороны.

$ \\e\left[i\frac{x+y}{4}\right]=ie\left[\frac{x-y^*}{4i}\right] \qquad\cos\left(\frac{x+y}{4}\right)=\sin\left(\frac{x-y^*}{4}\right) \\0 < x < 4 $

Корень этого уравнения $x$ равен площади единичного круга, решается множеством различных способов, обозначается символом $\pi$.

$\pi = 2 + \frac{1}{3}\left(2 + \frac{2}{5}\left(2 + \frac{3}{7}\left(2 + \frac{4}{9}\left(...\right)\right)\right)\right)=3.14159...$

Более развёрнуто будет

$\pi = 1 + \frac{2}{2}\left(1 + \frac{1}{3}\left(1 + \frac{4}{4}\left(1 + \frac{2}{5}\left(1 + \frac{6}{6}\left(1 + \frac{3}{7}\left(...\right)\right)\right)\right)\right)\right)$

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

$e[x]=1+\frac{x}{1}\left(1+\frac{x}{2}\left(1+\frac{x}{3}\left(1+\frac{x}{4}\left(1+\frac{x}{5}\left(1+\frac{x}{6}\left(...\right)\right)\right)\right)\right)\right)$

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

$e=1+\frac{1}{1}\left(1+\frac{1}{2}\left(1+\frac{1}{3}\left(1+\frac{1}{4}\left(...\right)\right)\right)\right)=2.71828...$

Если мы разобьём функцию экспоненты реального аргумента на участки, то подобно одинаковому повороту у участков экспоненты мнимого аргумента, каждый участок будет преумножать вдоль аргумента величину функции в одинаковой степени, равной увеличению первого фрагмента, который, из-за равенства единице экспоненты, и значит, производной в нуле, возрастает на участке почти линейно. И в целом, выражение один плюс обратное количеству фрагментов при возведении в степень количества фрагментов приближается к числу e.

$ \\\lim_{n\to\infty}\left(1+\frac{1}{n}\right)^n=e$

Это второй замечательный предел. А первый замечательный предел показывает, что функция

$\frac{\sin(x)}{x}=\sum_{n=0}^{\infty}(-1)^n\frac{x^{2n}}{(2n+1)!}$

в области ноля близка к $x^0$, что в пределе равно единице.

Функция $\operatorname{sinc}(x)=\frac{\sin(x)}{x}, x\ne 0$ интересна ещё тем, что кроме суммы раскладывается в произведение.

$\frac{\sin(x)}{x}=\prod_{n=1}^{\infty}\left(1-\frac{x^2}{\pi^2n^2}\right)$

А подставив $x=\frac{\pi}{2}$ можно выразить

$ \frac{\pi}{2} = 1 + \frac{1}{3}\left(1 + \frac{2}{5}\left(1 + \frac{3}{7}\left(1 + \frac{4}{9}\left(1 + \frac{5}{11}(...)\right)\right)\right)\right)$

как

$ \frac{\pi}{2} = \prod_{n=1}^\infty \left(\frac{4n^2}{4n^2 - 1}\right) = \\ = \prod_{n=1}^\infty \frac{(2n)(2n)}{(2n-1)(2n+1)} = \frac{2}{1} \cdot \frac{2}{3} \cdot \frac{4}{3} \cdot \frac{4}{5} \cdot \frac{6}{5} \cdot \frac{6}{7} \cdot \frac{8}{7} \cdot \frac{8}{9} \cdot \ldots $


Для

$\frac{\pi}{4} = \frac{1}{2} + \frac{1}{3}\left(\frac{2}{4} + \frac{2}{5}\left(\frac{3}{6} + \frac{3}{7}\left(\frac{4}{8} + \frac{4}{9}\left(\frac{5}{10} + \frac{5}{11}(...)\right)\right)\right)\right)$

тоже есть своё выражение:

$ \frac{\pi}{4} = \operatorname{arctg} 1 = \frac{1}{1}-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\frac{1}{9}-\frac{1}{11}+\ldots$

И сходство между этим вариантом и более бодрым определённо есть:

$\frac{\pi}{4} = \frac{1}{2} + \frac{1}{2}\left(1-\frac{1}{3}\right)\left(\frac{1}{2} + \frac{1}{2}\left(1-\frac{1}{5}\right)\left(\frac{1}{2} + \frac{1}{2}\left(1-\frac{1}{7}\right)\\\left(\frac{1}{2} + \frac{1}{2}\left(1-\frac{1}{9}\right)\left(\frac{1}{2} + \frac{1}{2}\left(1-\frac{1}{11}\right)(...)\right)\right)\right)\right)$



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

$e^{z+2ik\pi}=e^z\qquad k\in \mathbb{Z}$

Поэтому функция обратная к экспоненте многозначна, и добавление или вычитание $2\pi$ к мнимой составляющей решения также является решением.

$\ln(e^a\cdot e^{i\varphi})=\ln(e^{a+i\varphi})=a+i\varphi+2ik\pi\qquad k\in \mathbb{Z}$

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

$(y)'_x=(\ln x)'_x=\frac{1}{(x)'_y}=\frac{1}{e^y}=\frac{1}{e^{\ln x}}=\frac{1}{x}$

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

$\int x^{n-1} (a \ln(x) - b)\,dx = x^n\left(\frac{a}{n}\left(\ln(x) - \frac{1}{n}\right) - \frac{b}{n}\right)\\x\ne 0\quad n_0 = 1\quad a_0 = 1\quad b_0 = 0$

Для общности формулы, если $n=0$, то тогда $a = 0, \frac{a}{n}=-b$. После выделения части относящейся к логарифму получим:

$(x^n (\ln(k x) - 1/n))'_x = n x^{n - 1} \ln(k x)$

Для логарифма коэффициент $k$ действует так, что сужает реальную часть функции, но этим же самым он её поднимает, на величину $\ln(k)$. На производную функции такое поднятие не влияет. Как не влияет действительный коэффициент аргумента логарифма на мнимую часть его значения.

У действительного числа всего два вида обращения: изменение знака и обращение степени. У комплексного числа добавляется обращение знака только реальной части, обращение знака только у мнимой части и обращение степени только у модуля числа, без изменения фазы. Это всё одно преобразование, различие в комбинации с первыми двумя преобразованиями. Также, добавляется поворот на i, как вид обращения, для возврата из которого нужно выполнить его не два, а четыре раза. Но остальные две степени это комбинации с другими обращениями, так что добавилось только разложение двойного обращения одного вида на одинарное другого. В итоге, четыре вида бинарного обращения, и каждое число входит в группу из 16 отражений. Если число находится на координатной оси, или на диагонали, или модуль числа единица, тогда различающихся отражений будет меньше. В итоге, пять осей симметрии.

У комплексного числа есть реальная и мнимая составляющая, а квадрат модуля числа вычисляется как сумма их квадратов.

Если обозначить

$a=c+is\\ m^2=c^2+s^2$

тогда у $a$ можно выделить модуль и фазу:

$a=e^{\ln(m)+i\varphi}=e^{\ln(m)}\cdot e^{i\varphi}=e^{\ln(e^{i\theta}\cdot|m|)}\cdot e^{i\varphi}=e^{i\theta}|m| e^{i\varphi}=|a| e^{i\omega}$

Кроме того, что $m$ может быть отрицательным при этом фаза $\varphi$ будет сдвинута на $\pi$ при выполнении этих равенств сами $c$ и $s$ могут быть комплексными числами.

И, например, при чисто мнимом $s$ величина $m^2$ может уйти в отрицательные значения, а значит, $m$ станет мнимым. Логарифм мнимого числа это логарифм соответствующего действительного числа, с добавкой $\frac{\pi}{2}$ к мнимой составляющей. Можно обозначить модулем $|m|$ такое число, у которого логарифм не даёт мнимой части, вся фаза $m$ идёт в $\theta$.

Как вывод, в этих условия у $m$ может быть своя собственная фаза $\theta$. И здесь присутствует cвязь трёх фаз: $\omega=\theta + \varphi$. А дальше, как ни удивительно, может случиться так, что $|m|\ne |a|$, тогда фаза $\varphi$ имеет мнимую составляющую, и фазы уже не связаны суммой.

Чуть подробнее о связях. Сложение и вычитание двух чисел дают две характеристики: удвоенную среднюю величину и удвоенную полуразность. По этим характеристикам можно получить обратно числа, путём их сложения или вычитания, с делением на два, либо на первом этапе, либо на втором. Либо делением на корень из двух на обоих этапах.

Операция совмещения, $a=c+is$, показывает одновременно признаки и сложения и вычитания, так как у одних составляющих вычисляется сумма, а у других разность. Но обращённая операция с обращением знака у одного из слагаемых, $b=c-is$, оставляет именно те величины, которые теряются при исходной операции. Где вычислялось среднее, там считается полуразность, а где вычислялась полуразность, там считается среднее. Для получения из результата его составляющих $(a,b)\to(c,s)$ этого достаточно.

Но есть альтернатива. Фиксация суммы квадратов $m^2=c^2+s^2$ даёт достаточно данных о самих величинах, чтобы вместе с данными об их сумме $d=c+s$ можно было получить их значения, с точностью до порядка в паре. Кроме понятий обратимого среднего и обратимой разности для двух величин можно ввести характеристику их сходства по действительной части, различия по мнимой части, выражается в разнице квадрата суммы и суммы квадратов, а значит, в удвоенном произведении этих двух величин.

$d=c+s \\m^2=c^2+s^2 $

$ \\c=\frac{x+y}{\sqrt2}\quad s=\frac{x-y}{\sqrt2} $

$\\d^2-m^2=(c+s)^2-(c^2+s^2)=2cs=2\frac{x+y}{\sqrt2}\cdot\frac{x-y}{\sqrt2}=x^2-y^2 \\d^2-m^2=x^2-y^2\qquad d^2=2x^2\qquad 2x^2-m^2=x^2-y^2 \\m^2=x^2+y^2 \\x=\frac{d}{\sqrt2}\quad y=\pm\sqrt{m^2-\frac{d^2}{2}} \\c,s=\frac{1}{2}(d\pm\sqrt{2m^2-d^2}) $

Но характеристики $a=c+is,\quad m^2=c^2+s^2$ не являются парой сумма и сумма квадратов. Если заменить $s$ на $\mp ir$, тогда можно переписать

$ \begin{matrix} a=c+is&\to&a=c\pm r \\m^2=c^2+s^2&\to&m^2=c^2-r^2 \end{matrix} $

То есть, если совмещение интерпретировать как сумму или разность, в обоих случаях сумму квадратов нужно интерпретировать как разность квадратов, а это характеристика, показывающая сходство суммы и разности величин. И значит, закономерности будут проще:$\\\frac{m^2}{a}=c-is $

$\\c=\frac{1}{2}\left(a+\frac{m^2}{a}\right) \\s=\frac{-i}{2}\left(a-\frac{m^2}{a}\right) $

Квадрат модуля числа и квадратичная разностная характеристика совпадают только если компоненты $a$ уже разделены на реальную и мнимую. Иначе $m$ и $\varphi$ одновременно содержат отклонения от пары модуль-фаза, и компенсируют отклонения при выполнении их роли.

***
Вторая промежуточная задачка.
Решим задачу о том, как получить вектор максимальной длины сложением из двух других векторов, применяя такие коэффициенты, которые содержат в себе поворот, то есть, сумма квадратов которых постоянна.
$m^2=c^2+s^2$

$r^2=(cx_1+sx_2)^2+(cy_1+sy_2)^2$
$r^2=c^2(x_1^2+y_1^2)+s^2(x_2^2+y_2^2)+2cs(x_1x_2+y_1y_2)$
$r^2=m^2r_1^2+s^2d+csp$
$d = r_2^2-r_1^2$ разница квадратов амплитуд
$p = 2(x_1x_2+y_1y_2)$ квадратичное сходство фаз
Для того чтобы найти максимум далее приравниваем нулю производную.
$0=2sd+\frac{m^2-2s^2}{c}p$
Решение
Вывод используемого далее соотношения.
$c^2=m^2-s^2$
$(s^2-c^2)^2=s^4-2c^2s^2+c^4=(c^2+s^2)^2-4c^2s^2$
$(2s^2-m^2)^2=m^4-4c^2s^2$

$\frac{d}{p}=\frac{2s^2-m^2}{2cs}$
$\frac{d^2}{p^2}=\frac{(2s^2-m^2)^2}{4c^2s^2}=\frac{m^4-4c^2s^2}{4c^2s^2}=\frac{m^4}{4c^2s^2}-1$
$\frac{p^2}{d^2+p^2}=\frac{4c^2s^2}{m^4} = \frac{m^4-(2s^2-m^2)^2}{m^4}=1-\frac{(2s^2-m^2)^2}{m^4}$
$1-\frac{p^2}{d^2+p^2}=\frac{(2s^2-m^2)^2}{m^4}$
$\frac{d^2}{d^2+p^2}=\frac{(2s^2-m^2)^2}{m^4}$
$(2s^2-m^2)^2=\frac{m^4d^2}{d^2+p^2}$
$(2s^2-m^2)=\pm\frac{m^2d}{\sqrt{d^2+p^2}}$
Знак будет в зависимости от того, нужно получить s или c
$s^2=\frac{m^2}{2}\left(1+\frac{d}{\sqrt{d^2+p^2}}\right)\qquad c^2=\frac{m^2}{2}\left(1-\frac{d}{\sqrt{d^2+p^2}}\right)$
$c^2s^2=\frac{m^4}{4}\left(1-\frac{d^2}{d^2+p^2}\right)$
$cs=\frac{m^2}{2}\sqrt{1-\frac{d^2}{d^2+p^2}}=\frac{m^2}{2}\sqrt{\frac{p^2}{d^2+p^2}}=\frac{m^2}{2}\frac{p}{\sqrt{d^2+p^2}}$
$r^2=m^2r_1^2+\frac{dm^2}{2}\left(1+\frac{d}{\sqrt{d^2+p^2}}\right)+\frac{pm^2}{2}\frac{p}{\sqrt{d^2+p^2}}$
$r^2=\frac{m^2}{2}(r_1^2+r_2^2)+\frac{m^2}{2}\frac{d^2}{\sqrt{d^2+p^2}}+\frac{m^2}{2}\frac{p^2}{\sqrt{d^2+p^2}}$
$r^2=\frac{m^2}{2}\left(r_1^2+r_2^2+\sqrt{d^2+p^2}\right)$
Выяснилось, что величина вариации результата в выражении для квадрата амплитуды получается сложением по пифагору разницы квадратов амплитуд и квадратичной схожести фаз.

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

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

Размытие


Представим, что некоторый объект может передвигаться шагами. Если объект может сделать только шаг влево или шаг вправо, мы вполне сможем предсказать, сколько вариантов позиции объекта будет после $n$ шагов их $(n+1)$. Если подсчитать количество всех комбинаций шагов, то будет $2^n$. Для конечной позиции не важно, в каком порядке делались шаги влево и шаги вправо, важна только разница количества этих шагов, так что, для одной конечной позиции будет несколько вариантов прохождения, кроме, разумеется, двух крайних.

Если отследить связь, мы увидим простую закономерность: если разница в количестве шагов разного направления небольшая, то количество вариантов порядка прохождения близко к максимуму. А если разница большая, вплоть до однозначного выбора, то и количество вариантов мало, вплоть до единственного. Осталось разобраться с промежуточными ситуациями.

Это не сложнее бинома Ньютона, прежде всего потому, что это он и есть. И если каждый шаг поделить на $c=a+b$ вариантов, где $a$ шаги влево, а $b$ шаги вправо, то распределение вариантов отслеживается достаточно легко: к числам $a$ и $b$, в степенях, равных количеству шагов данного типа, добавляется биномиальный коэффициент, обозначающий количество путей прохождения к такой комбинации.

Сумма коэффициентов с каждым шагом увеличивается в два раза. Всё количество вариантов больше суммы для предыдущего шага в $c$ раз. Количество вариантов для заданного номера шага можно нормализовать, поделив на $c^n$.

$ n=u+v\qquad k=\binom{n}{u}=\binom{n}{v}=\frac{n!}{u!v!}=\frac{(v+1)\cdot\ldots\cdot n}{u!}\qquad r=\frac{ka^{u}b^{v}}{c^n}\\ $

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

Рассматривать будем только ситуацию, когда вероятность правого шага и левого одинакова. Если рядом называть распределение вероятности с одинаковым номером шага, то следующий ряд рассчитывается относительно предыдущего ряда, без учёта общей нормировки, делением на отсчёт позиции: $\frac{1}{u}$ или $\frac{1}{v}$, направление гиперболы у распределения здесь зависит от направления шага, при этом результат получается одинаковый. Сдавливание влево при движении вправо и сдавливание вправо при движении влево даёт одинаковый результат расширения формы, но это расширение идёт с меньшей скоростью, чем общее расширение. С сохранением пика в середине, процесс относительно всей ширины похож уже не на размытие, а на концентрацию.

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

Это можно проверить: в биномиальном коэффициенте номер ряда можно указывать как квадрат динамической величины, а отсчёт задавать линейно. Так как для получения коэффициента отсчёт считается не от центра, а от края, то линейная величина будет скорректирована, она станет средним между величиной и её квадратом. Что по совпадению равно сумме всех целых величин вплоть до данной. Дробь отношения значения в позиции половины корня от количества шагов (считая позицию от центра) к значению в центре будет стремиться к константе.

$ \lim_{x\to \infty}\binom{x^2}{x(x+ 1)/2}/\binom{x^2}{x^2/2}=\lim_{x\to \infty}\frac{(x^2/2)!\cdot (x^2/2)!}{(x(x+1)/2)!(x(x-1)/2)!}=\frac{1}{\sqrt{e}} $

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

Двумерное распределение является произведением распределений для отдельных координат, при этом величина сохраняется при вращении, значит, одномерное распределение является степенной функцией, и зависит своей степенью от $x^2$, произведение таких степенных функций складывает квадраты координат в единый квадрат. Только, распределение по своей степени обратно величине расстояния, а значит, используется $-x^2$.

Этим условиям подходит функция $C_1e^{-\left(\frac{x}{C_2}\right)^2}$, осталось выяснить значения констант.

Подсчитать квадрат интеграла ненормированного распределения можно через двумерное ненормированное распределение. Производная $(e^{-x^2})'_x$ равна $-2xe^{-x^2}$, значит можно подсчитать интеграл от $x e^{-x^2}$. Если у двумерного интеграла одну координату взять как радиус-множитель, то это получится применить.

$I^2=\int_{0}^{\infty}\int_{0}^{\infty}e^{-(x^2+y^2)}dx dy=\int_{0}^{\infty}\int_{0}^{2\pi r}e^{-r^2}dldr=\\=2\pi \int_{0}^{\infty}r\cdot e^{-r^2}dr=2\pi(1/2\cdot e^{-0^2}-1/2\cdot e^{-\infty^2})=\pi$

$ I=\sqrt{\pi} $

Выясним коэффициент изменения масштаба.

$ f(x)=\frac{e^{-x^2}}{\sqrt{\pi}}\quad\frac{f(x)}{f(0)}=e^{-x^2}=\frac{1}{\sqrt{e}}\Rightarrow x=\frac{1}{\sqrt{2}} $

Нормировка масштаба производится с помощью коэффициента, сохраняющего интеграл функции, $\alpha=\sqrt{2}\sigma$. В итоге, нормальное распределение выглядит так:

$ f(x)=\frac{e^{-\left(\frac{x}{\alpha}\right)^2}}{\alpha\sqrt{\pi}}\\ e^{-\ln(\pi)/2-(x/\alpha)^2-\ln(\alpha)}=e^{-\ln(\pi)/2-(x/\sqrt{2}\sigma)^2-\ln(\sqrt{2}\sigma)}=\\=e^{-\ln(\pi)/2-(x/\sigma)^2/2-\ln(2)/2-\ln(\sigma)}=e^{-(\ln(\pi)+(x/\sigma)^2+\ln(2))/2-\ln(\sigma)}\\ f(x)=\frac{1}{\sigma \sqrt{2\pi e^{\left(\frac{x}{\sigma}\right)^2}}} =\frac{e^{-\frac{x^2}{2\sigma ^2}}}{\sigma \sqrt{2\pi}} $

Многомерное размытие увеличивает степень нормировочного коэффициента $\frac{1}{\sqrt{\pi}}$, для сохранения значения интеграла.

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

***

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

Перевод Чествуем игривое волшебство Джона Хортона Конвея

18.11.2020 18:12:16 | Автор: admin

Всем привет. В преддверии старта продвинутого курса "Математика для Data Science", подготовили для вас перевод статьи, которая была написана в память о легендарном математике Джоне Хортоне Конвее.


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

Легендарный математик Джон Хортон Конвей, умерший в апреле от COVID-19, по-детски искренне увлекался изобретением головоломок и игр. Он провел подробный анализ многих головоломок, таких как кубик Сома, пасьянс с колышками и солдаты Конвея. Он изобрел алгоритм судного дня (быстрый метод вычисления дня недели в вашей голове - Конвей мог сделать это менее чем за две секунды) и бесчисленное количество игр, в том числе игра Рассада (Sprouts) и знаменитую игру Жизнь, которая положила начало изучению клеточных автоматов.

Большая часть серьезных математических работ Конвея также проистекает из его слабости к математическим играм. Он внес оригинальный вклад в теорию групп (Решётка Лича, гипотеза чудовищного вздора), многомерную геометрию, тесселяцию (мозаику), теорию узлов, теорию чисел (сюрреалистические числа), алгебру, математическую логику и анализ.

В этом месяце мы чествуем игривый гений известного британского математика двумя головоломками и исследовательской игрой. Сначала мы поиграем с числовой головоломкой, изобретенной Конвеем, которая без лишней скромности является воплощением самого совершенства. Затем насладимся геометрическим пазлом, относящимся к некоторым из его наиболее визуально доставляющих работ. И наконец, мы погрузимся в игру с открытым финалом, созданную читателем Quanta, которая напоминает культовую игру Жизнь Конвея.

Головоломка 1: Цифровое совершенство

Существует загадочное десятичное 10-значное число abcdefghij. Все его цифры разные, и они обладают следующими свойствами:

  • a делится на 1

  • ab делится на 2

  • abc делится на 3

  • abcd делится на 4

  • abcde делится на 5

  • abcdef делится на 6

  • abcdefg делится на 7

  • abcdefgh делится на 8

  • abcdefghi делится на 9

  • abcdefghij делится на 10

Какое это число?

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

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

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

Головоломка 2: Двойственные треугольники

Есть равнобедренный треугольник, который содержит угол равный x градусов. Отношение двух сторон разной длины равно y.

Оказывается, не один, а целых два разных треугольника имеют одинаковые значения x и y!

Каковы значения x и y для этих двух равнобедренных треугольников? Что особенного в этих треугольниках и какое отношение они имеют к творчеству Конвея?

Для нашей последней головоломки вам снова понадобятся бумага и карандаш. Будет даже лучше, если вы возьмете несколько листов в клетку. Это игра, которая погрузит вас в образ мышления Конвея - вы будете рисовать небольшие диаграммы и создавать различные структуры, как это делал он в своих играх Рассада и Жизнь. Наша игра, которая создает структуры, подобные полимино, была предоставлена Quanta читателем по имени Jona Raphael.

Головоломка 3: Случайные волосатые узоры

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

Рассмотрим два примера:

  • Если у вас пока есть только один тайл, то второй тайл имеет равную вероятность оказаться на севере, юге, востоке или западе от исходного тайла.

  • Если у вас есть кольцо из восьми тайлов, то есть 12 позиций вокруг внешних сторон кольца и одна позиция в середине, и все они действительны для размещения следующего тайла. Для той, что посередине, вероятность получит тайл в четыре раза больше, чем для любой внешней подходящей позиции, потому что у нее четыре общих края с ранее размещенными тайлами, а не только одна.

Мы оцениваем волосатость (H, потому что в оригинале используется hairiness) или внешность любой конфигурации как количество открытых ребер тайлов, деленное на количество тайлов. Например:

  • Для одного тайла на плоскости H = 4 ребра 1 тайл = 4.

  • Для кольца из восьми тайлов H = 16 ребер 8 тайлов = 2.

  • Для ряда из восьми тайлов H = 18 ребер 8 тайлов = 2,25.

Величину, обратную H, можно назвать внутренностью или компактностью конфигурации.

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

(В этом видео 2014 года Numberphile(числофил) Джон Конвей рассказывает, как он создавал игру Жизнь.)

Вот несколько вопросов, которые направят ваше исследование этого квадратного мира.

  1. Новый тайл может быть помещена рядом с одним ребром (касаясь только одного другого тайла), в углу (касаясь двух), внутри буквы U (касаясь трех) или внутри отверстия (касаясь всех четырех). Как каждое размещение влияет на количество открытых ребер в новой конфигурации (узоре)?

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

  3. Какое ожидаемое значение H (приблизительное или точное) для данного значения n?

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

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

Вот и все для начала. Теперь вы можете исследовать эту игру самостоятельно. Попробуйте найти ответы на несколько новых интересных вопросов. Может быть, вы найдете новую структуру (пожалуйста, поделитесь изображения интересных узоров!) Или даже докажете теорему. И пока вы это делаете, предложите название этой игре.

Играйте - подарите духу Конвея улыбку!

Узнать подробнее о курсе.

Подробнее..

Индустрия 4.0. Горно-обогатительный комбинат. Что первично задачи или данные?

20.11.2020 14:23:38 | Автор: admin


Раньше при старте автоматизации ставились цели и сроки завершения работ по автоматизации. С некоторых пор у автоматизации нет ни начала ни конца.

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

Принципиальный вопрос: что первично решаемые задачи или данные?
Далее рассматривается подход, позволяющий рационально воспользоваться потенциалом Индустрии 4.0 и избежать чрезмерных затрат.
Кроме того, цель предлагаемого подхода не попасть в ловушку ERP: сделаем единый источник правды, что решит большинство задач бизнеса.

Инстаграм

1. Модель ГОКа за 50 человека/часов.



Ниже приведена имитационная модель Ковдорского ГОКа, сделанная на основе его принципиальной структурной схемы. Модель была сделана за 40-50 человеко/часов (неделя). Она позволяет получить общую производственную картину, а также составить перечень актуальных задач и необходимые для них данные.

Сравните цену альтернативы: обследование, проект, новая система для управления датчиками (политика вендоров) еще одна к тем, что уже имеет компания. Плюс внедрение, связывание и согласование всех существующих бизнес-процессов.

Обогатительную фабрику горно-обогатительного комбината (ГОК) можно представить в виде системы последовательно и параллельно соединенных модулей (узлов), имеющих изменяющиеся характеристики пропускной способности и значений индикаторов в зависимости от режима работы.

Схема обогатительной фабрики ГОК



Входные данные поступают на разных позициях и соответствуют историческим или прогнозируемым временным рядам.

Далее приведены результаты моделирования по разным обстоятельствам.
Результаты последовательно соответствуют этапам (красный номер на графиках):
1) дробильно- перегрузочный узел;
2) магистральный конвейер;
3) среднее дробление;
4) грохоты;
5) разделение руды после просеивания на два потока: в мелкие дробилки и на конвейер на усреднительный склад;
6) мелкие дробилки;
7) конвейер на усреднительный склад;
8) разделение руды на два потока: на усреднительный склад и в конвейер в корпус обогащений;
9) усреднительный склад;
10) конвейер в корпус обогащений;
11) корпус обогащения;

Цвет итогового выхода одного этапа соответствует цвету входа следующего этапа.
Пунктирные линии показывают время простоя.
Синий цвет исходное поступление руды. Красный цвет итоговая выработка.

Рассмотрим некоторые режимы работы ГОК.

1. Поступление руды постоянно, но с периодическим уменьшением объема.



Выше сводка, ниже расшифровка по участкам.



2. Перерывы в работе дробильно-перегрузочного узла при постоянной подаче руды.



Сверху сводка, снизу детализация.



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

Пока что модель больше нацелена на прогнозирование и решение проблем ремонтов.
Ей не хватает экономики и экономических задач.

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

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

Итак, получаем экономическую задачу при существующих производственно-коммерческих ограничениях.

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

При наличии явно поставленной задачи становится ясным, какие датчики и где необходимо установить.
Такой подход даст возможность подразделению АСУТП компании произвести модернизацию в соответствии со стандартами Индустрии 4.0 своими силами.
Подробнее..

Погодозависимый бизнес

21.11.2020 20:20:09 | Автор: admin


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

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

Явно погодозависимым является около 60-70% бизнеса. Если считать больничные для работников и по уходу за детьми, то процент будет еще больше.

Кроме погодозависимости бизнеса, еще имеет место погодозависимость в потреблении продукции бизнеса.

Для угля это отклонения в жару и холод. Для производителей удобрений засуха или дожди. Для аграрного сектора и фермерских хозяйств каждый тип погодных явлений требует соответствующей реакции.

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

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

1. Искусственный интеллект на практике


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

Погодные станции расположены достаточно далеко друг от друга. В США эту проблему частично решили, подключив более 40 000 частных погодных станций в общую сеть.

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

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

2. Раз природа переходим на лунный календарь


Далее приведены данные для метеостанции Малое Сареево. Основная масса станций расположена далеко друг от друга по расходящимся от Москвы кругам. Единственный вариант, когда станции расположены достаточно близко и соответствуют вершинам треугольника с ребрами в 17-20 км это Малое Сареево, Немчиновка и аэродромная станция Внуково. В этом случае можно хоть как-то перепроверять получаемые результаты.
Малое Сареево: температурные данные (фрагмент данных с 2005 по 2017, дневные линии синии, ночные коричневые):



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

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

3. BigData это нелинейность


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

Остается только экспериментировать и развивать интуицию.

Исходные данные были сглажены через скользящее среднее. В рамке из 4-х картинок:

верхний ряд:
левый рисунок: исходный день(синий)-исходная ночь (коричневая),
правый рисунок: сглаженный день(синий)-сглаженная ночь(коричневая);
нижний ряд:
левый рисунок: исходный день(синий)-сглаженный день(коричневый),
правый рисунок: исходная ночь(синий)-сглаженная ночь(коричневый).

Совмещение дня и ночи очень сильно сбивает картину из-за сложности динамики. Разделение дня и ночи (трудности с плавающей границей рассвет-закат) позволяет видеть практически одинаковый профиль с небольшим смещением (верхний ряд правый рисунок).



4. Близкие профили: сезонные и межсезонные


Полученные профили можно сравнивать. В качестве метрики используем значение интеграла абсолютного значения всех пар функций. Для Малого Сареева имеем 83 лунных полупериода с 2012 по 2017 годы. Распределений округленных значений метрики приведены в таблицах.



Этим значениям соответствует следующее распределение.



Ниже на рисунке приведена сезонная интерференционная картина: за 4 года для Малого Сареева для дневных профилей. Матрица 83х83. В рамках введенной метрики прослеживается некая периодичность.



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

Одинаковые профили с разной температурой не будут близкими. Будем использовать другую метрику: интеграл от абсолютного значения разности функций со смещением на расстояния средней разницы между функциями по 10 точкам. Будем называть такие профили межсезонными.

Распределение становится более определенным первое сезонное, второе межсезонное.



Вторая интерференционная картина также более четкая.



5. Что получилось и что это дает?


Понятно, что после осени будет зима, а после зимы весна. Также ясно, что прогноз погоды достоверен на 3 дня.

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

6. Туман на аэродромах


Следующий пример демонстрирует явную пользу типизации профилей.

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

Имеются устройства, которые периодически измеряют температуру через 50 метров до 1000 метров в высоту (всего 20 измерений).

По той же схеме, что и ранее выделяем типовые профили (фрагмент).



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

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



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

7. Выводы


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

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

Math Invasion. Мой долгострой

23.11.2020 16:15:20 | Автор: admin
Привет, народ!

Расскажу я вам свою историю о том, как я разрабатывал игру. Идея о том, чтобы скрестить shoot em up с математикой, мне пришла ещё в студенческие годы (Где-то в 2008 году).

Собственно, уже тогда я ещё делал попытки воплотить идею в жизнь. Для реализации своих целей, тогда я использовал язык программирования Delphi и, только осваиваемую мною, библиотеку GLScene. Как результат, у меня получилась игра видео которой Вы можете наблюдать ниже. Кстати, саму игру Вы можете скачать по данной ссылке. Запускается она через файл Project1.exe который находится в папке TestFireCursorProject19

С чего начинался Math Invasion


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

Лучшие времена не пришли.

Но, спустя 10 лет, объявилось желание воскресить прежнюю задумку уже в новом формате. К тому же, миру были подарены мощные инструменты для разработки игр. Моё внимание пало на Unity3D. По слухам, удобный инструмент для разработки игр в 2D. Как раз, то что было мне нужно. В 2019 году я приступил к разработке. Для написания кода я выбрал C#, так как с магией JavaScript я был знаком и не хотел портить себе нервы. Но ввиду того что я не был знаком с C#, я тратил на разработку больше времени чем могло уйти. И вот, спустя 2 месяца, имея на руках MVP, по причине нехватки времени для работы которая меня кормит, я забросил разработку ;-D

Прошёл ещё один год.

Я вернулся к доработке. А точнее, к переделке. Потому что за год я успел показать недоделанную игру своим друзьям и знакомым (коим огромное спасибо) и собрать фидбек. Оказалось, что игру я создавал лично для себя, а не для пользователя. (Полную историю изменения игры вы сможете найти у меня в Telegram канале или на странице в Facebook).

Первая версия на Unity3D
image

Я адаптировал игру под мобильное приложение. Внёс изменения в интерфейс и механику игры. Что бы игра не выглядела совсем сухо, я добавил ей дух соперничества, т.е. врага который хочет, что бы вы проиграли. Он то и шлёт на вас эти математические задачи и радуется каждой вашей ошибке. Отсюда и название Math Invasion (Математическое наступление). Мои знакомые сказали, что враг в игре это лишнее.

Мне подсказали другую механику, при которой игра будет более интересна для пользователя. Я не стал переделывать игру ещё раз, но решил в дальнейшем внести новую механику как дополнительный способ прохождения. Назову я этот способ CHALLENGE!!!.

Релиз


Сейчас игра выложена в Play Market и любой желающий может опробовать её. В ней есть недостатки. В неё нужно добавлять дополнительные уровни. Добавить узбекский язык. Она сейчас на уровне чуть выше MVP. Я уже получаю фидбек и вношу изменения на его основе. Я добился того, что игра увидела свет.

Какой я вынес урок для себя?

До начала разработки нужно составить дорожную карту и зафиксировать примерные сроки. Иначе, Ваше творение может застрять в параллельном мире под названием Пока ещё не готово.
Подробнее..

Перевод Основы дискретной математики

24.11.2020 12:18:29 | Автор: admin

Привет, хабр. В преддверии старта базового курса "Математика для Data Science" делимся с вами переводом еще одного полезного материала.


Об этой статье

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

ЧТО ТАКОЕ ДИСКРЕТНАЯ МАТЕМАТИКА?

Это область математики, изучающая объекты, которые могут принимать только уникальные отдельные значения.

Мы рассмотрим пять основных разделов в следующем порядке.

  • Логика

  • Теория множеств

  • Отношения

  • Функции

  • Комбинаторика

  • Графы

ЛОГИКА

Что такое логика?

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

Формальная логика анализирует выводы с чисто формальным содержанием. Примерами формальной логики являются символическая логика и силлогистическая логика (о которой писал Аристотель).

Начнем с азов. Рассмотрим следующее высказывание на естественном языке:

Если я голоден, я ем.

Пусть голоден будет посылкой A, а ем следствием B. Попробуем формализовать:

A=>B (то есть из A следует B)

NB. Посылка и следствие являются суждениями.

Логические выражения

Для нас важна форма, а НЕ содержание. Значение будет истинным, если оно соответствует форме.

Например, 10<4 ЛОЖЬ, а 10>4 ИСТИНА.

Логические операции

Суждение P это утверждение, которое может быть как истинным, так и ложным.

Обозначим истинное значение P единицей (1), а ложное значение P нулем (0).

Существует другое суждение; обозначим истинное значение Q единицей (1), а ложное значение Q нулем (0).

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

Отрицание

ИЛИ

И

Эквивалентность

Импликация

Исключающее ИЛИ

Три закона

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

Обозначим истинное значение R единицей (1), а ложное значение R нулем (0).

Закон ассоциативности

Закон дистрибутивности

Законы де Моргана

Логическая формула

Включает суждения, выражения в скобках и следующие символы:

Квантификаторы

Что такое квантификатор? Квантификатор в естественном языке это слово, которое используется для обозначения количественных отношений (сколько). Например: все, несколько, много, мало, большинство и нисколько.

ТЕОРИЯ МНОЖЕСТВ

Что такое множество?

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

Например, если A={1,2,3,4} и B={2,4,1,3} и порядок неважен, то A=B

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

Иногда нам нужно определить бесконечное множество. Проблема очевидна: мы не сможем записать все его элементы. Значит, мы можем определить множество с помощью характерных признаков всех его элементов.

Операции над множествами

Подмножество

Количество элементов

Объединение

Пересечение

Дополнение

ОТНОШЕНИЯ

Логика отношений изучает отношения между математическими объектами. Мы можем установить связь с N элементами (где N положительное натуральное число).

Бинарное отношение это отношение между двумя элементами (объектами). Формально мы можем записать любое отношение между x и y так: x ~ y

Например, 4<8 или Я студент по отношению к моему преподавателю.

Свойства бинарных отношений

Числовые множества

ФУНКЦИИ

Функция это отношение, которое присваивает переменным новые значения. То есть это отношение между множеством А и множеством В.

Свойства

Функциональная композиция

Это точечное использование функции, результатом которого является другая функция.

КОМБИНАТОРИКА

Простыми словами, это наука о счете.

Перестановки

Это упорядочение уникальных объектов, при котором важен порядок следования.

Комбинации

Это упорядочение уникальных объектов, при котором не важен порядок следования.

Блок-схема алгоритма

ГРАФ

Что такое граф?

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

Если вам понравилась эта статья, приглашаю почитать также мой блог:

www.quantq8.com


Успеть на курс по специальной цене


Читать ещё:

Подробнее..

Тестируем комплементарную кросс-энтропию в задачах классификации текста

27.11.2020 20:16:23 | Автор: admin
Ранее в этом году И. Ким совместно с соавторами опубликовали статью [1], в которой предложили новую функцию потерь для задач классификации. По оценке авторов, с её помощью можно улучшить качество моделей как в сбалансированных, так и в несбалансированных задачах классификации в сочетании со стандартной кросс-энтропией.

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

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



Предварительный анализ


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

В статье комплементарная кросс-энтропия определяется следующим образом:



а полная функция потерь, используемая в обучении модели это сумма со стандартной кросс-энтропией:



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

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

Когда задача включает в себя только два класса, выражение выполняется всегда, и вся комплементарная кросс-энтропия всегда равна нулю. Так что это имеет смысл только в том случае, если число классов в задаче равно трем или более.

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

Проектирование эксперимента


Держа все вышеописанное в голове, можно приступить к разработке эксперимента.

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



Рис. 1. Примеры однотипных текстов, отнесенных к разным классам.

Чтобы упростить задачу, мы переназначим классы и сделаем три: отрицательный, нейтральный, положительный.

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

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



Таблица 1. Классовые пропорции, используемые в экспериментах. Коэффициенты даны относительно количества отрицательных примеров.

Мы сравним комплементарную кросс-энтропию со стандартной кросс-энтропией без весов классов. Мы также не будем рассматривать другие подходы к решению классового дисбаланса, такие как upsampling и downsampling, и добавление синтетических и/или дополненных примеров. Это поможет нам сохранить эксперимент емким и простым.

Наконец, мы разделили данные на train, validation и test сеты в пропорции 0.7 / 0.1 / 0.2.

Мы используем сбалансированную кросс-энтропию в качестве основной метрики производительности модели, таким образом следуя авторам оригинальной статьи. Мы также используем macro-averaged F1 в качестве дополнительной метрики.

Детали проекта


Исходный код нашей реализации, включая предварительную обработку данных, функцию потерь, модель и эксперименты, доступны на GitHub [3]. Здесь мы просто рассмотрим его ключевые моменты.

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

Реализация функции комплементарной кросс-энтропии довольно прямолинейна. Мы используем cross_entropy из PyTorch для стандартной кросс-энтропии, поэтому наша функция потерь принимает на вход логиты. Далее она переводит их в вероятности, чтобы вычислить комплементарную часть.

Предварительная обработка данных включает в себя стандартную токенизацию при помощи модели en из SpaCy.

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

Детали процесса обучения: batch size 256, learning rate 3e-4, размер эмбеддингов 300, размер LSTM 128, уровень dropout 0,1, обучение в течение 50 эпох с остановкой после 5 эпох без улучшения качества на валидации. Мы используем одни и те же параметры как для экспериментов с комплементарной, так и для экспериментов со стандартной кросс-энтропией.

Результаты экспериментов





Таблица 2. Результаты экспериментов. CE для эксперимента со стандартной кросс-энтропией и ССЕ для комплементарной.

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

Ещё одну проблему комплементарной кросс-энтропии можно увидеть на графиках функции потерь (рис. 2).



Рис. 2. Графики потерь для степеней дисбаланса 1 / 0.2 / 0.2 (оранжевый) и 1 / 0.5 / 0.5 (зеленый).

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

В заключение


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

Примечания


[1] Y. Kim et al, 2020. Imbalanced Image Classification with Complement Cross Entropy. arxiv.org/abs/2009.02189
[2] www.kaggle.com/c/sentiment-analysis-on-movie-reviews/overview
[3] github.com/simbirsoft/cce-loss-text
Подробнее..

Регламенты закупок кто виноват, что делать KPI. Базис Гребнера

30.11.2020 22:22:08 | Автор: admin


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

Можно поменять правила, но тут начинаются неприятности. Имеется доказательство того, что часто совсем простые правила ведут к непредсказуемой динамике. Это называется принцип вычислительной неприводимости (The New Kind of Science). Результат применения не очень сложного набора правил нельзя интуитивно предугадать. Его можно только вычислить (смоделировать), произведя соответствующие операции.

Обсудим следующие темы:
динамика закупок производственных предприятий;
что не так в регламентах;
почему система все-таки работает;
исследование KPI через базисы Гребнера.

Инстаграм

1. Анализ данных по закупкам.



Ниже приведены данные закупок 5 действующих предприятий и одного строящегося.
Данные взяты из ERP. Они очень простые:
дата создания заявки о потребности;
дата утверждения потребности после проведения процедур согласования;
дата начала поставок.

Действующий завод 1.



Первый график соответствует координатам <дата создания потребности дата утверждения закупки>. Второй график соответствует координатам <дата утверждения закупки дата начала поставки>. Третий общая картина без даты утверждения в координатах <дата создания потребности дата начала поставки>.

Действующий завод 2.



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

Действующий завод 3.



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

Действующий завод 4.



Действующий завод 5.



При всей серьезности регламентов интересны даты в отрицательных областях. Это значит, что поставка происходит до окончания процедур согласования. Еще это заметка к вопросу об относительной пользе ERP: без нее плохо, но при ее наличии очень много проблем (относящихся к сфере ее ответственности) остается нерешенными.

Строящийся завод.



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

2. Что на практике допускают регламенты.



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

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

Первый раздел касался только фактических сроков зафиксированных в ERP для процессов закупок. Но эти закупки производятся из выделенных сумм, определенных регламентами планирования, которые одинаковы для всех предприятий.

Ниже приведены рисунки, определяющие объемы средств на материалы. Они соответствуют действующим заводам, данные о которых были рассмотрены ранее.



Синим обозначен первоначально утвержденный план.



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



Зеленая линия факт.



Фиолетовая линия уточненный план без факта: показывает насколько изначально завышаются потребности.



Интересно, что вся эта динамика соответствует действующим регламентам.

По таким позициям, как Ресурсы и Услуги, план в точности соответствует факту (о чудо методов прогнозирования).





3. Система правил, KPI и теневое планирование.



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

Это не парадокс, а следствие теневого планирования и правильной работы с KPI (сами выбираем сами отчитываемся).

Никто не смотрит на отрицательные даты в сроках поставки (задним числом) и странную динамику потребностей. Основное внимание направлено на способность не превысить бюджет.

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



На рисунке показано соотношение для материалов: малиновые точки куплено дороже, чем заявлялось, бурые куплено дешевле.



Все покупки услуг вне плановые.



Больший объем ресурсов куплен вне плана.



На гистограммах слева указано распределение количества позиций, а справа их объем.



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



Сводка для ресурсов для ремонтной деятельности.

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

Если такое планирование может иметь место в стесненных обстоятельствах, то целенаправленное развитие системы планирования несомненно будет еще более успешным.

4. Что делать? KPI. Базисы Гребнера.



Как бы не были обоснованы претензии к KPI, но они прочно вошли в систему управления бизнесом.

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

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

Предлагается следующая методика объективной оценки действующих KPI.
Все количественные и качественные KPI переводятся (по достаточно простым и прозрачным правилам) в функциональные зависимости:
f1(x1,x2,x3,x4)
f2(x2,y1,y2,y5)
f3(x4,y2,z1,z2,z3), где x, y, z учитываемые факторы.
Таких зависимостей может быть много. Столько же, сколько KPI или больше.
Формально, в результате получается полиномиальная система от многих переменных.

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

Но в случае KPI он подходит идеально.
Что он позволяет делать?

Во-первых, метод дает ответ, совместима ли система и есть ли у нее решение. Если у системы нет решения, значит выбранные KPI противоречивы.

Во-вторых, для непротиворечивых KPI метод позволяет найти функциональные зависимости (формулы) между KPI разных подразделений и проанализировать их взаимозависимость.

В-третьих, можно понять уровень сепаратизма и несвязанности показателей работы подразделений. Система KPI может распасться (по формулам) на несвязанные между собой (независимые) части.

И, наконец, формализованный перечень факторов x, y, z, фиксирует набор учитываемых проекций бизнеса. Все остальные проекции оказываются забытыми.

Прежде, чем двигаться по пути совершенствования системы планирования и управления, попробуйте протестировать набор KPI Вашей компании.
Подробнее..

Категории

Последние комментарии

© 2006-2020, personeltest.ru