Серия «Математика и физика»

Джон Томсон и его фабрика по производству нобелевских лауреатов

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

Профессором был Джожеф Джон Томсон (1856 — 1940) — нобелевский лауреат 1906 года и первооткрыватель электрона, но таких последствий никто не ожидал: семеро студентов-исследователей под его руководством получили Нобелевскую премию по физике и химии.

Джон Томсон и его фабрика по производству нобелевских лауреатов Математика, Наука, Познавательно, Timeweb, Ученые, Длиннопост

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


В 1884 году лорд Рэлей (Нобелевский лауреат 1904 года) ушел в отставку с поста руководителя кавендишской лаборатории физики Кембриджского университета — одного из самых престижных научных подразделений того времени. В своей записке об уходе на пенсию он рекомендовал, чтобы молодой 28-летний человек Томсон стал его заменой.

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

Отборочной комиссии, состоящей из лорда Кельвина, Джорджа Гэбриэла Стокса и Джорджа Говарда Дарвина — одних из лучших научных умов своего времени — предстояло сделать трудный выбор, но они всё-таки последовали рекомендации Рэлея.

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

Джон Томсон и его фабрика по производству нобелевских лауреатов Математика, Наука, Познавательно, Timeweb, Ученые, Длиннопост

Томсон в своей лаборатории. Очень подробная и интересная история открытия электрона — здесь

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

Томсон считал образцами для подражания знаменитого химика Далтона и физика Генри Джоуля. Однажды, когда он был совсем маленьким, кто-то из родственников спросил его, чем бы он хотел заниматься, когда вырастет, и Джозеф ответил, что хотел бы заниматься “оригинальными исследованиями”. Не многие мальчики в 1870-х годах и не многие мальчики сейчас могли бы сформулировать такие амбиции в раннем возрасте.

Джон Томсон и его фабрика по производству нобелевских лауреатов Математика, Наука, Познавательно, Timeweb, Ученые, Длиннопост

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

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

Но есть одно достижение Джозефа, о котором не так часто вспоминают. Он был выдающимся педагогов, подобных которому мир не видел. Ряд первоклассных ученых получили свое раннее образование у Томсона — 75 его учеников занимали профессорские должности примерно в 55 университетах по всему миру, 27 были избраны членами королевского общества, а 7 его учеников стали Нобелевскими лауреатами. Последнее достижение до сих пор не повторил ни один ученый в мире!

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

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

❯ Эрнст Резерфорд (1871 — 1937)


Самый известный ученик Дж. Дж. Томсона — Эрнст Резерфорд — автор прорывной планетарной модели атома. Лауреат Нобелевской премии 1908 года по химии Резерфорд родился в Новой Зеландии. В кавендишскую лабораторию он попал во много благодаря управленческим решениям Томсона, который в 1885 году смягчил правила и разрешил перспективным студентам без базового кембриджского диплома проводить исследования в лаборатории.

Джон Томсон и его фабрика по производству нобелевских лауреатов Математика, Наука, Познавательно, Timeweb, Ученые, Длиннопост

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

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


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

❯ Фрэнсис Вильям Астон (1877 — 1945)


Томсон всегда был в поиске талантов и лично убеждал перспективных студентов работать в лаборатории. Одним из таких студентов был Фрэнсис Уильям Астон, которого переманили в Кавендиш для исследования анодных лучей.

Джон Томсон и его фабрика по производству нобелевских лауреатов Математика, Наука, Познавательно, Timeweb, Ученые, Длиннопост

Прошлое место работы Астона — Бирмингемский институт, где он трудился под руководством Пойнтинга (с ним знакомы те, кто помнят одноименный вектор из школьной физики)

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

Джон Томсон и его фабрика по производству нобелевских лауреатов Математика, Наука, Познавательно, Timeweb, Ученые, Длиннопост

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

Астон был удостоен Нобелевской премии в 1922 году за «сделанное им с помощью им же изобретенного масс-спектрографа открытие изотопов большого числа нерадиоактивных элементов и за формулирование правила целых чисел». После этого он еще несколько раз модернизировал устройство.

❯ Чарльз Томсон Вильсон (1869 — 1959)


Шотландский физик, который в начале планировал стать врачом, попал под крыло Томсона в 1892 году.

Джон Томсон и его фабрика по производству нобелевских лауреатов Математика, Наука, Познавательно, Timeweb, Ученые, Длиннопост

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

Джон Томсон и его фабрика по производству нобелевских лауреатов Математика, Наука, Познавательно, Timeweb, Ученые, Длиннопост

Корона (слева) и глория (справа) — это оптические явления, обусловленные дифракцией света на капельках воды. Кстати, в Китае глорию называют «светом Будды». Цветное гало всегда окружает тень наблюдателя, что часто толковалось как степень его просветления (приближённости к Будде и другим божествам).

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

Джон Томсон и его фабрика по производству нобелевских лауреатов Математика, Наука, Познавательно, Timeweb, Ученые, Длиннопост

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

❯ Уильямс Лоуренс Брэгг (1890 — 1971)


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

Джон Томсон и его фабрика по производству нобелевских лауреатов Математика, Наука, Познавательно, Timeweb, Ученые, Длиннопост

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

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

Джон Томсон и его фабрика по производству нобелевских лауреатов Математика, Наука, Познавательно, Timeweb, Ученые, Длиннопост

nλ = 2dsin θ — закон Брэгга-Вульфа. Точки на картинке — атомы кристаллической решетки.

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

Джон Томсон и его фабрика по производству нобелевских лауреатов Математика, Наука, Познавательно, Timeweb, Ученые, Длиннопост

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

❯ Чарльз Гловер Баркла (1877 — 1944)


Как и многие нобелевские лауреаты из нашей подборки, Чарльз Баркла получил образование в Тринити-колледже, а затем перешёл под крыло Джозефа Томсона в кавендишскую лабораторию.

Джон Томсон и его фабрика по производству нобелевских лауреатов Математика, Наука, Познавательно, Timeweb, Ученые, Длиннопост

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

Джон Томсон и его фабрика по производству нобелевских лауреатов Математика, Наука, Познавательно, Timeweb, Ученые, Длиннопост

Исследования Баркли привели к т.н. закону Мозли, который вычислил конкретную формулу зависимости длины волны характеристического излучения от порядкового номера элемента. Закон удивителен тем, что это зависимость — линейная! На горизонтальной оси отмечены корень из частоты и длина волны, на вертикальной — зарядовое число.

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

❯ Оуэн Уилланс Ричардсон (1879 — 1959)


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

Джон Томсон и его фабрика по производству нобелевских лауреатов Математика, Наука, Познавательно, Timeweb, Ученые, Длиннопост

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

В 1900 году он начал исследовать явление термоэлектронной эмиссии («эффект Эдисона»), заключающееся в том, что при нагревании металла электроны набирают достаточно энергии, чтобы преодолеть потенциальный барьер.

Джон Томсон и его фабрика по производству нобелевских лауреатов Математика, Наука, Познавательно, Timeweb, Ученые, Длиннопост

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

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

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

Джон Томсон и его фабрика по производству нобелевских лауреатов Математика, Наука, Познавательно, Timeweb, Ученые, Длиннопост

Ток насыщения пропорционален квадрату температуры, k — постоянная Больцмана, А и В' — параметры, зависящие от материала катода и определяющие его способность к термоэлектронной эмиссии

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

Джон Томсон и его фабрика по производству нобелевских лауреатов Математика, Наука, Познавательно, Timeweb, Ученые, Длиннопост

Кенотроны — выпрямительные электровакуумные устройства, работающие по принципу термоэлектронной эмиссии. До сих пор можно встреть у любителей «ламповой музыка». Их несомненное достоинство — отсутствие искажений, присущих полупроводниковых устройствам.

❯ Эдуард Виктор Эплтон


Эплтон получил Нобелевскую премию в 1947 году — уже после смерти своего учителя и руководителя кавендишской лаборатории.

Джон Томсон и его фабрика по производству нобелевских лауреатов Математика, Наука, Познавательно, Timeweb, Ученые, Длиннопост

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

Джон Томсон и его фабрика по производству нобелевских лауреатов Математика, Наука, Познавательно, Timeweb, Ученые, Длиннопост

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

Английский физик Оливер Хевисайд в 1902 году предположил наличие ионизированного слоя в атмосфере. Его теория включала в себя возможность распространения радиосигнала вокруг Земли, несмотря на её кривизну. Независимо от Хевисайда эксперименты по дальнему приёму коротких волн через Атлантику между Европой и Америкой проводил американский инженер-электрик Артур Кеннели. Они предположили, что где-то вокруг Земли существует ионизированный слой атмосферы, способный отражать радиоволны. Его назвали слоем Хевисайда — Кеннели, а затем — ионосферой.

Джон Томсон и его фабрика по производству нобелевских лауреатов Математика, Наука, Познавательно, Timeweb, Ученые, Длиннопост

Слой Д ионосферы практически полностью поглощает радиосигналы, слой E — способен отражать длинные и средние волны, а слой F — имеет максимальную ионизацию и используется для работы на коротких волнах

Именно за открытие слоя F (на западе его часто называют слоем Эплтона) физик получил заслуженную награду. В серии экспериментов было определено, что он расположен на высоте 300-400 км над поверхностью Земли. Методика, которую Эплтон использовал в ходе исследований, оказала огромное влияние на развитие радиолокации.

❯ P.S.


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

Джон Томсон и его фабрика по производству нобелевских лауреатов Математика, Наука, Познавательно, Timeweb, Ученые, Длиннопост

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

Показать полностью 22

Крестики-нолики, шашки и шахматы: немного об играх в математике

Оригинальный материал

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

Вы вечно проигрываете в крестики-нолики? Устали от бесконечных издевок окружающих? Чувствуете себя неполноценным членом общества? Тогда вы обратились по адресу! Сегодня у вас есть уникальная возможность пройти наш обучающий курс по беспроигрышной стратегии, который стартует уже сегодня! Присоединяйтесь сейчас и получите скидку 10% по промокоду НЕУДАЧНОЕ_ВСТУПЛЕНИЕ!

❯ 1. Беспроигрышная стратегия в крестики-нолики (или как впасть в состояние «ничейной смерти»)

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

Итак, как не проигрывать, если вы ходите первыми (напомню, что в нашем консервативном мире крестики доминируют).

1 ход: всегда в центр;
2 ход: в угол, который дальше всего от предыдущего хода ноликов;
3 ход: защита от попыток нолика чет выстроить или, что вероятнее, – снова ход в угол;
4 ход: тут у вас в наличии либо уже имеются две выигрышные линии, и вы гасите его, либо нолик прикрыл тылы, и исход – ничья.

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

1 ход: в любой угол;
2 ход: а дальше только пытаться помешать крестикам замутить тройничок, ведь больше вы ни на что не способны в силу своей submissive сущности.
Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

Автор потерял нужную картинку из инета, не судите строго

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

Смотрите, корень нашего дерева – пустое поле 3х3. Первый игрок имеет возможность сделать ход на одну из девяти позиций – рисуем дереву девять веток с разными позициями крестиков (там внизу есть картинка). На следующем ходе у каждой ветки с крестиком есть восемь свободных мест для ноликов, то есть каждой ветке рисуем по восемь новых, где в различных комбинациях на поле две клетки заняты крестиком и ноликом. Итого имеем 9х8 – 72 ветки. Следуя такой логике, на дальнейшем шаге у дерева появится по 7 ответвлений, так как свободно только 7 клеток для крестика, количество теперь веток стало 9х8х7=504. Конечное число решений – листиков нашего дерева – равно 9! (все же знают, что это не девять с восклицанием, а факториал? – 9х8х7х6х5х4х3х2х1) или 362880. Теперь достаточно вбить компьютеру все эти исходы и запрограммировать выбирать только выигрышные.

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

Первые ветви дерева решений

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

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

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

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

Вот, например, с шашками дела обстоят интереснее: кроме большого поля у них и правила на порядок сложнее, так что при подсчетах оказывается, что листьев у дерева решений около 5х10^20. Это пять и рядом двадцать нулей. Думаете, это мало? Оно и понятно, у нас мозг просто не способен представить число такого порядка, но для сравнения: чтобы выстроить цепочку от Земли до Марса из бусинок размером с атом потребуется как раз 5,5х10^20 бусинок. Очевидно, что число это офигеть какое большое, и пятидесяти компьютерам не просто так потребовалось почти 20 лет (двадцать лет, Карл!), чтобы полностью рассчитать все возможные исходы шашек и выстроить их дерево решений.

Сие знаменательное событие произошло в 2007 году благодаря команде канадских исследователей во главе с Джонатаном Шеффером, и с этого момента шашки официально вошли в список полностью решенных игр. Если оба соперника не совершают ошибок, то партия всегда заканчивается ничьей. Тут нужно учесть, что речь идет об английских шашках – чекерс; в них назад бьет только дамка.

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

Статья Шеффера и его коллег в журнале Science

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

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

❯ 2. Компьютеры, которые играют в игры

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

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

Итак, по сравнению с великими и ужасными шахматами, шашки (а тем более, крестики-нолики) покажутся развлечением для малышей. Напомню, что для английских шашек количество различных вариантов партий равняется 5х10^20, и полностью просчитать их смогли только спустя 18 лет после начала работы программы.

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

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

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

Десять в сто двадцатой степени. Это много. Так много, что у нас даже нет аналогии, чтобы показать весь ужас этого гигантского числа, его попросту не существует в физическом мире. Чтобы вы понимали, количество атомов в известной нам части Вселенной примерно равно 10^80, а количество оригинальных партий в шахматах больше этой цифры в 10^40 раз. Причем в начале игры все выглядит довольно безобидно: у белых есть всего двадцать ходов – 16 пешками и четыре конями — но с каждым сделанным шагом количество возможных комбинаций на доске очень быстро растет. Так, например, после первого хода каждого из соперников, на поле существует 400 различных позиций для следующего шага, после второго – 72084, после третьего – больше 9 миллионов, после четвертого – более 288 миллиардов. Такое число соразмерно с количеством звезд в нашей галактике, а ведь это всего лишь самое начало партии.

Однако не просто так было сказано, что теория игр без шахмат – как самолёт без двигателя. После окончания Второй мировой еще на заре эпохи машинных вычислений шахматы стали своеобразным эталоном для проверки различных идей в этой области. Клод Шеннон *кстати, именно в честь него число 10^120 называется числом Шеннона*, один из основателей раздела об искусственном интеллекте, говорил, что не видит практической ценности в вычислении всех возможных шахматных партий, но сама эта мысль побуждает исследователей двигаться вперед и развивать технологии до тех пор, пока они не найдут решение.

Первую программу для игры в шахматы написал еще в 1952 году Дитрих Принц (коллега Алана Тьюринга) на компьютере Ferranti Mark. Правда, тут не стоит обольщаться, этот компьютер, лишь отдалённо напоминающий наши современные устройства, был таким слабеньким, что объем его оперативной памяти мог содержать программу только по типу «мат в два хода». Она была рассчитана лишь для последних двух ходов, но начало шахматной эпопеи было положено.

В 1956 году компьютер MANIAC-1 *милое название* сыграл три партии в облегченные шахматы (на поле 6х6 и без слонов) – сам с собой, против сильного игрока и против новичка. Несмотря на то, что опытный шахматист в начале игры решил отказаться от ферзя, программа все равно ему проиграла *какой неумелый маньяк*, но вот последнего – слабого соперника компьютер смог победить. Это была первая победа машины над человеком.
Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

Название MANIAC, кстати, — это аббревиатура: Mathematical Analyzer Numerical Integrator and Automatic Computer. "… Компания Metropolis выбрала имя MANIAC в надежде остановить поток глупых аббревиатур для названий машин»

После изобретения в 1971 году первого микропроцессора, у ученых появилась возможность задействовать более мощные компьютеры, а значит, сохранять в памяти машины еще больше победных комбинаций. В 1974 году был организован первый чемпионат по шахматам среди программ, в 1978 году машина обыграла международного мастера по шахматам, а в 1981-м Cray Blitz стал первым компьютером, получившим рейтинг мастера.

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

Кстати, легендарным Deep Blue стал 11 мая 1997 года, когда выиграл матч из шести партий у чемпиона мира Гарри Каспарова. Интересно, что за восемь лет до этого в Нью-Йорке Каспаров победил более слабого предшественника Deep Blue под названием Deep Thought. Тогда он высказал такую мысль: «Если компьютер сможет превзойти в шахматах лучшего из лучших, это будет означать, что ЭВМ в состоянии сочинять самую лучшую музыку, писать самые лучшие книги. Не могу в это поверить. Если будет создан компьютер с рейтингом 2800, то есть равным моему, я сам сочту своим долгом вызвать его на матч, чтобы защитить человеческую расу». Что ж, ему явно пришлось пересмотреть свои взгляды.

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

Матч 1997 года, который стал предметом документального фильма «Человек против машины»

Окончательно и бесповоротно человечество проиграло железякам в 2005-м: в этот год представитель нашей расы в последний раз смог одержать верх над программой. Сегодня рейтинг живых шахматистов настолько отстал от их железных соперников, что человеку больше никогда не выиграть партию с машиной. На начало сентября 2022 года наивысший шахматный рейтинг человека составляет 2861, а программы 3535.

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

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

Рейтинг живых шахматистов с официального сайта FIDE на начало сентября

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

Рейтинг шахматных программ

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

❯ 3. Go play Go (Последний бой людей)

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

Как вы уже поняли, такая игра есть: мы наконец-то добрались до го. Го – китайская стратегия – является самой древней настольной игрой, сохраняющей свои правила практически неизменными вот уже 2500 лет. До ХХ века игра была распространена только в Азии, но на сегодняшний день она входит в пять дисциплин Всемирных интеллектуальных игр и является самой распространенной настолкой по числу участников (c поправочкой на плотность населения Востока).

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

Чтобы сыграть в классическую версию го вам понадобятся: доска в клетку 19х19 (называется гобан) – 1 шт, белые игральные камни – 180 шт., черные игральные камни – 181 шт., кошка-жена – 1 шт. (если есть больше, поделитесь?). Цель игры — отгородить на доске камнями своего цвета бо́льшую территорию, чем противник. Как видно, здесь нет черных и белых клеток на поле, камни можно ставить на любые пересечения линий, нет и разграничения игральных фигур – все они равноценны друг другу. Собственно, именно эта простота и порождает дьявольски сложные тактику и стратегию.
Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

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

Обычный метод перебора, которым пользуются компьютеры для выбора выигрышной стратегии в шахматах, здесь просто не уместен. Во-первых, дерево решений го необычайно огромно – на начальной позиции существует 55 вариантов ходов (в шахматах – 20), и «растет» оно быстрее – после первых двух ходов соперников существует уже около 16 миллиардов позиций для следующего (в шахматах – меньше ста тысяч). А во-вторых, го – игра, в которой очень важен опыт.

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

Но вот настал 2016 год и программа AlphaGo, разработанная корпорацией Google, в прямом эфире победила мирового мастера с девятым даном – Ли Седоля. Это стало возможно благодаря новому подходу обучения, который кардинально отличается от обучения шахматных компьютеров. Помните, что Deep Blue использовал обычный метод перебора дерева решений просто с кучей оптимизаций и на самом деле кроме мощных процессоров и больших объемов памяти он недалеко ушел от железяк 60-х.

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

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

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

Довольно простая статья о работе AlphaGo.

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

Показать полностью 9

Как определить массу Земли с помощью шаров и веревки

Как определить массу Земли с помощью шаров и веревки Наука, Научпоп, Исследования, Физика, Перевод, Длиннопост, Земля, Познавательно, Эксперимент, Гифка

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

Занятно думать о том, каким способом мы узнаём что-то. Например, масса Солнца составляет около 2 х 1030 кг. Это такое огромное число, что его трудно осознать. И если нам так сложно даже вообразить такие большие числа, как мы будем искать эти значения? Что ж, первоначальный метод заключался в использовании небольших масс, палки и веревки. Пожалуй, это один из важных шагов в определении массы как Солнца, так и всех планет в нашей Солнечной системе. Это эксперимент Кавендиша, впервые проведенный Генри Кавендишем в 1798 году. Эксперимент действительно крутой, поэтому я собираюсь объяснить, как он работает.

Между объектами, обладающими массой, существует гравитационное притяжение. У баскетбольного мяча есть гравитационное взаимодействие с Землей (поскольку они оба имеют массу). Именно это гравитационное взаимодействие заставляет баскетбольный мяч ускоряться, когда он падает на землю, если вы его отпустите. Естественно, все всегда знали, что если отпустить предмет, он упадет. Однако только примерно во времена Ньютона люди осознали, что это притяжение также действует между астрономическими объектами, такими как Земля, Луна и Солнце. Это дает нам модель взаимодействия сил, которую часто называют законом всемирного тяготения Ньютона, но, как и у большинства крупных идей, у нее наверняка было много соавторов.

Как определить массу Земли с помощью шаров и веревки Наука, Научпоп, Исследования, Физика, Перевод, Длиннопост, Земля, Познавательно, Эксперимент, Гифка

Давайте рассмотрим эту модель гравитационной силы. Во-первых, величина этой силы зависит от произведения двух взаимодействующих масс (m1 и m2). Во-вторых, величина уменьшается пропорционально квадрату расстояния между двумя объектами ( r ). Наконец, есть G. Это универсальная гравитационная постоянная. Это ключ к определению массы Земли.

Итак, давайте сделаем шаг назад на мгновение. Когда мы измеряем вещи, нам всегда приходится делать какой-то выбор. Если мы хотим получить массу в килограммах, то мы должны решить, как указать значение 1 кг. Можно сказать, что килограмм — это масса 1 литра воды. Конечно, это не лучшее определение (теперь у нас есть методы получше). Хорошо, а как насчет измерения силы? Мы используем единицу под названием Ньютон, где 1 Ньютон — это сила, необходимая для ускорения тела, массой 1 килограмм, на 1 метр на секунду в квадрате. Да, ситуация выходит из-под контроля, но главное то, что вы можете дать эти определения и построить одну единицу измерения на другой.

А теперь представьте себе этот эксперимент. Предположим, я беру литр воды (который, как я знаю, составляет 1 килограмм) и измеряю гравитационную силу, исходящую от Земли. Если я знаю радиус Земли (греки прекрасно справились с его вычислением) и гравитационную постоянную G, то я могу решить уравнение гравитационной силы для массы Земли (см.выше). Но что такое гравитационная постоянная? Это сложная часть, и вот как вы можете найти значение G.

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

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

Как определить массу Земли с помощью шаров и веревки Наука, Научпоп, Исследования, Физика, Перевод, Длиннопост, Земля, Познавательно, Эксперимент, Гифка

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

Как определить массу Земли с помощью шаров и веревки Наука, Научпоп, Исследования, Физика, Перевод, Длиннопост, Земля, Познавательно, Эксперимент, Гифка

На конце вращающегося горизонтального стержня есть две меньшие массы (обозначенные m1). Эти массы взаимодействуют с большими массами (m2), которые находятся на расстоянии ( r ) от них. Горизонтальный стержень в конечном итоге достигнет некоторого положения равновесия, поскольку из-за скручивания троса, который поддерживает стержень, возникает небольшой крутящий момент. Трос действует как вращающаяся пружина. Чем больше он скручивается, тем больше крутящий момент. Если вы знаете соотношение между углом поворота (θ) и крутящим моментом, вы можете вычислить гравитационную силу, притягивающую массу на конце палки к большей неподвижной массе. В конфигурации на диаграмме выше большие массы заставят палку вращаться по часовой стрелке (как видно сверху). Если вы переместите бóльшие массы на другую сторону от палки, гравитационные силы заставят ее вращаться против часовой стрелки. Это показывает, что вращение происходит из-за гравитационного взаимодействия между парными массами. Как только палка займет устойчивое положение, останется лишь измерить массы и расстояние между ними, чтобы получить гравитационную постоянную.


В этом случае мы получаем гравитационную постоянную G = 6,67 x 10-11N*m^2 кг^2. Вы можете видеть, что эта константа действительно очень мала. В качестве примера мы можем продемонстрировать, как производится вычисление. Предположим, что вы человек, стоящий на расстоянии 1 метра от другого человека такой же массы (около 75 кг). Какая величина силы будет действовать на вас из-за гравитационного притяжения? Подставляя эти значения (вместе с константой) в уравнение силы мы получаем:

Как определить массу Земли с помощью шаров и веревки Наука, Научпоп, Исследования, Физика, Перевод, Длиннопост, Земля, Познавательно, Эксперимент, Гифка

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

Как определить массу Земли с помощью шаров и веревки Наука, Научпоп, Исследования, Физика, Перевод, Длиннопост, Земля, Познавательно, Эксперимент, Гифка

Мы можем назвать это локальной гравитационной постоянной Земли (local-Earth gravitational constant). Все, что вам нужно сделать, это взять массу и умножить на «g» (мы используем строчную букву «g», чтобы ее не путать с другой гравитационной постоянной «G»), и вы получите гравитационную силу (вес). В этом случае вам понадобится объект массой около 4 x 10-11 грамм, чтобы получить вес, равный силе притяжения между двумя людьми. Это все еще слишком мало для того, чтобы понять. А если так? Человеческие волосы могут иметь линейную массовую плотность 6,5 граммов на километр (информация из этой публикации). Это означает, волос длиной всего 6 x 10-6 миллиметров имеет вес, равный притяжению между двумя людьми. Это уму непостижимо. Вот вам бонус, мои расчеты, если вы хотите изменить значения.

Как определить массу Земли с помощью шаров и веревки Наука, Научпоп, Исследования, Физика, Перевод, Длиннопост, Земля, Познавательно, Эксперимент, Гифка

О, да, вы можете повторить тот же самый расчет, но использовать известную массу и вычислить массу Земли. Получится около 5,97 x 10^24 килограмма. Но зачем останавливаться на достигнутом? Вы также можете использовать значение G, чтобы найти массу солнца. Я кратко объясню, как работает этот расчет.

Итак, у вас есть планета, подобная Меркурию, которая вращается вокруг Солнца. Если учесть, что орбита круговая, то на Меркурий действует гравитационная сила со стороны Солнца.

Как определить массу Земли с помощью шаров и веревки Наука, Научпоп, Исследования, Физика, Перевод, Длиннопост, Земля, Познавательно, Эксперимент, Гифка

Гравитационная сила заставляет планету ускоряться и двигаться по кругу (центростремительное ускорение). Но это центростремительное ускорение зависит как от угловой скорости (ω), так и от орбитального расстояния ( R ). Поскольку на планете действует только одна сила (гравитационная сила), она будет равна массе, умноженной на ускорение, и в результате получится следующее соотношение.

Как определить массу Земли с помощью шаров и веревки Наука, Научпоп, Исследования, Физика, Перевод, Длиннопост, Земля, Познавательно, Эксперимент, Гифка

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

Как определить массу Земли с помощью шаров и веревки Наука, Научпоп, Исследования, Физика, Перевод, Длиннопост, Земля, Познавательно, Эксперимент, Гифка

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

Оригинал

Подпишись, чтобы не пропустить новые интересные посты!

Показать полностью 9

Деликатные числа. Математики заявили о новом классе простых чисел

Деликатные числа. Математики заявили о новом классе простых чисел Научпоп, Наука, Исследования, Математика, Длиннопост, Познавательно, Ученые, Гифка

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

Возьмем числа 294 001, 505 447 и 584 141. Заметили в них что-нибудь особенное? Можно догадаться, что все они простые (без остатка делятся только сами на себя и на единицу). Но указанные выше простые числа еще более необычны!

Если вы выберете любую цифру в каждом из этих чисел и измените ее, новое число будет составным и, следовательно, больше не будет являться простым. Изменим, например, цифру 1 в числе 294 001 на 7, и полученное число будет делиться на 7; изменим 1 на 9, и полученное число делится на 3.

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

С тех пор математики пошли дальше, развив идеи Эрдёша. Среди них и лауреат Филдсовской премии Теренс Тао: в статье 2011 года ученый доказал, что «положительная пропорция» (positive proportion) простых чисел — digitally delicate , то есть чувствительна к замене цифр (для всех систем счисления). Это означает, что интервал между последовательными чувствительными простыми числами практически не меняется — другими словами, простые числа, чувствительные к замене цифр, не будут встречаться реже с их увеличением.

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

«Это замечательный результат», — отметил Пол Поллак из Университета Джорджии.

Вдохновленный работами Эрдёша и Тао, Филасета задумался, что произойдет, если добавить бесконечную последовательность нулей в качестве первой части простого числа. Значения чисел 53 и …0000000053 совпадают. Может ли замена любого из этих бесконечных нулей, добавленных к простому числу, автоматически сделать его составным?

Филасета решил назвать такие числа, предполагая, что они существуют, «сильно чувствительными к замене цифр» (widely digitally delicate), и исследовал их свойства в статье, вышедшей в ноябре 2020 года со своим бывшим аспирантом Джеремайей Саутвиком.

Неудивительно, что новое условие затрудняет поиск подобных чисел. «294 001 является чувствительным к замене цифр, но не будет сильно чувствительным, — сказал Поллак, — поскольку, если мы заменим …000 294 001 на …010 294 001, мы получим 10 294 001 — еще одно простое число».

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

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

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

Деликатные числа. Математики заявили о новом классе простых чисел Научпоп, Наука, Исследования, Математика, Длиннопост, Познавательно, Ученые, Гифка

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

Зак Уайт / Университет Южной Каролины

В основе доказательства лежат два инструмента. Первый, использующий понятие «покрывающей системы», был изобретён Эрдёшем в 1950 году для решения другой проблемы теории чисел. «Покрывающая система, — говорит Саутвик, — даёт нам большое количество сегментов, а также гарантирует, что каждое положительное целое число находится хотя бы в одном из этих сегментов». Если, например, вы разделите все положительные целые числа на 2, вы получите два сегмента: один содержит четные числа, в которых остаток равен 0, и другой, содержащий нечетные числа, в которых остаток равен 1. Таким образом, все положительные целые числа были «покрыты», а числа, находящиеся в одном и том же сегменте, считаются «конгруэнтными» друг другу.

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

Сильно чувствительное к замене цифр простое число также должно стать составным, если какая-либо из его цифр уменьшится. Здесь на помощь приходит второй инструмент, — «сито». Теория сита (кстати, появилась еще в Древней Греции) предлагает способ подсчета и оценки для целых чисел, удовлетворяющих определенным свойствам. Филасета и Саутвик использовали подход, аналогичный тому, который использовал Тао в 2011 году, чтобы показать: если вы возьмете простые числа в вышеупомянутом сегменте и уменьшите одну из цифр, положительная пропорция этих простых чисел станет составной. Другими словами, положительная пропорция этих простых чисел сильно чувствительна к замене цифр.

«Теорема Филасеты-Саутвика, — отмечает Поллак, — является красивой и неожиданной иллюстрацией силы покрывающей системы».

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

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

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

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

В то же время, как отметил Померанс, представление числа в виде его цифр в десятичной системе счисления может быть удобным, но это не имеет отношения к тому, что это за число на самом деле». Он заключает, что существуют более фундаментальные способы представления чисел, например, простые числа Мерсенна — простые числа в виде 2^p - 1 для простого числа p.

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

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

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


Оригинал

Подпишись, чтобы не пропустить новые интересные посты!

Показать полностью 1

Матричное умножение. Медленное достижение мифической цели

В недавней работе был установлен новый рекорд скорости по умножению двух матриц. Она также знаменует и конец эпохи для метода, который ученые применяли для исследований на протяжении десятилетий.
Матричное умножение. Медленное достижение мифической цели Наука, Математика, Длиннопост, Ученые, Исследования

Математики стремятся к достижению мифической цели — второй степени (exponent two), то есть к умножению пары матриц n х n всего за n2 шагов. Исследователи подбираются все ближе к своей цели, но получится ли у них когда-нибудь достичь ее?

Для специалистов в области Computer Science и математиков сама идея о «второй степени» связана с представлениями о совершенном мире.

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

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

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

Поэтому наименьшее возможное количество шагов для умножения пар матриц это n2, то есть количество шагов, необходимое просто для записи ответа. Отсюда и название «вторая степень».

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

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

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

Матричное умножение. Медленное достижение мифической цели Наука, Математика, Длиннопост, Ученые, Исследования

Самуэль Веласко / Quanta Magazine

Эта операция известна как получение «скалярного произведения» строки со столбцом (иногда называется «внутренним произведением»). Чтобы вычислить другие элементы в произведении матриц, повторите процедуру с соответствующими строками и столбцами.

В целом, классический метод умножения матриц 2 х 2 состоит из восьми умножений и нескольких сложений. Как правило, этот способ умножения двух матриц размера n х n требует n3 умножений.

Матричное умножение. Медленное достижение мифической цели Наука, Математика, Длиннопост, Ученые, Исследования

С увеличением размера матриц количество умножений, необходимых для нахождения их произведения, растет намного быстрее, чем количество сложений. Чтобы найти произведение матриц 2 х 2 требуется всего восемь промежуточных умножений, а чтобы найти произведение матриц 4 х 4 их требуется уже 64. Однако количество сложений, необходимых для получения суммы этих матриц, не так значительно отличается. Обычно количество сложений равно количеству элементов в матрице, то есть четыре для матриц 2 х 2 и 16 для матриц 4 х 4. Эта разница между сложением и умножением позволяет понять, почему исследователи измеряют скорость умножения матриц исключительно с точки зрения количества требуемых умножений.


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

На протяжении веков люди считали, что n3 — это самый быстрый способ умножения матриц. По имеющимся сведениям, в 1969 году Фолькер Штрассен намеревался доказать, что невозможно умножить матрицы 2 х 2, используя менее восьми умножений. Видимо, он все-таки не смог найти доказательства, а через некоторое время и понял почему: на самом деле, существует способ сделать это с помощью семи умножений!

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

«Это крошечное изменение приводит к огромным улучшениям в работе с большими матрицами», — говорит Уильямс.

Матричное умножение. Медленное достижение мифической цели Наука, Математика, Длиннопост, Ученые, Исследования
Матричное умножение. Медленное достижение мифической цели Наука, Математика, Длиннопост, Ученые, Исследования

Вирджиния Василевска Уильямс из Массачусетского технологического института и Джош Алман из Гарвардского университета открыли самый быстрый способ перемножения двух матриц за n2.3728596 шагов. Джаред Чарни; Ричард Т.К. Хоук

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

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

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

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

«Это очень распространенная в теоретической информатике концепция: преобразовывать задачи и проводить аналогию между ними, чтобы показать, что они одинаково простые или сложные», — сказал Алман.

В 1981 году Арнольд Шёнхаге использовал этот подход, чтобы доказать, что умножение матриц возможно выполнить за n 2.522 шагов. Позднее Штрассен назвал этот подход «лазерным методом» (laser method).

За последние несколько десятилетий каждое улучшение в процессе умножения матриц происходило за счет усовершенствования лазерного метода, поскольку исследователи находили все более эффективные способы трансформации задачи. В своем новом доказательстве Алман и Уильямс стирают различие между 2 задачами и показывают, что уменьшить число умножений возможно. «В целом Джош и Вирджиния нашли способ применить машинные вычисления в рамках лазерного метода и получили лучшие на настоящий момент результаты», — сказал Генри Кон из Microsoft Research.

В их статье теоретическое ограничение скорости умножения матриц улучшено до n2.3728596.

Также благодаря этому исследованию Уильямс может вернуть себе корону в области матричного умножения, которую она по праву получила в 2012 году (n 2.372873), а затем уступила в 2014 году Франсуа Ле Галлю (n 2.3728639).

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

«Маловероятно, что получится приблизиться ко второй степени, используя это семейство методов», — отметил Уманс.

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

Уильямс вспоминает один из разговоров со Штрассеном об этом: «Я спросила его, считает ли он, что возможно получить вторую степень для матричного умножения, и он ответил: «Нет, нет, нет, никогда!».

Оригинал

Подпишись, чтобы не пропустить новые интересные посты!

Показать полностью 4

Как воссоздать изображение всего по нескольким пикселям

Эта статья дает возможность познакомиться с такой методикой получения и восстановления сигнала, как Compressive Sensing.
Как воссоздать изображение всего по нескольким пикселям Машинное обучение, Программирование, Data Science, Длиннопост

Множество всех возможных изображений 2 на 2 с цветами, закодированными одним битом

Пространство изображений огромно, невероятно огромно, но при этом очень мало. Задумайтесь об этом на минуту. Из сетки размером всего 8 на 8 пикселей можно создать 18 446 744 073 709 551 616 различных чёрно-белых изображений. Однако из этих 18 квинтиллионов изображений очень немногие покажутся осмысленными человеческому взгляду. Большинство изображений, по сути, выглядит как QR-коды. Те, которые покажутся человеку осмысленными, принадлежат к тому множеству, которое я называю естественными изображениями. Они представляют крошечную долю пространства изображений 8 на 8. Если мы рассмотрим мегапиксельные изображения, то доля естественных изображений становится ещё меньше, почти ничтожной, однако содержит любое изображение, которое можно придумать. Так чем же эти естественные изображения так уникальны? И можем ли мы использовать эту фундаментальную разницу в собственных интересах?


Спектральное пространство


Рассмотрим два представленных ниже изображения. Оба изображения имеют размер 512 на 512 пикселя. Если вычислить гистограмму значений пикселей, то можно понять, что эти распределения идентичны. И это на самом деле так. Левое изображение такое же, как правое, только пиксели перемешаны случайным образом. Тем не менее между ними есть фундаментальное отличие. Одно выглядит как «снег» на экране старого телевизора, а другое — это лицо человека.

Как воссоздать изображение всего по нескольким пикселям Машинное обучение, Программирование, Data Science, Длиннопост

Слева: случайное изображение. Справа: классическое тестовое изображение женщины с тёмными волосами. Оба изображения принадлежат к пространству изображений 512 на 512

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


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

Как воссоздать изображение всего по нескольким пикселям Машинное обучение, Программирование, Data Science, Длиннопост

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

Воссоздание изображений по нескольким пикселям, задача с высокой степенью неопределённости

Как воссоздать изображение всего по нескольким пикселям Машинное обучение, Программирование, Data Science, Длиннопост

Записано всего 10% пикселей

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


Допустим, что мы точно знаем, какие фотодатчики исправны. Обозначив как x ∊ ℝⁿ неизвестное изображение (где n — общее количество пикселей, и мы считаем, что оно представлено в виде вектора), а как y ∊ ℝᵐ ненулевые яркости пикселей, зафиксированные датчиками, мы можем записать

Как воссоздать изображение всего по нескольким пикселям Машинное обучение, Программирование, Data Science, Длиннопост

Здесь C — это разреженная матрица измерений m × n. Все элементы, соответствующие неисправным фотодатчикам, равны нулю, и она содержит только m ненулевых элементов, соответствующих исправным датчикам. Следовательно, наша задача — выяснить, каким был x исходного изображения, учитывая, что мы наблюдаем только несколько его пикселей.


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

Как воссоздать изображение всего по нескольким пикселям Машинное обучение, Программирование, Data Science, Длиннопост

решение которой задаётся так:

Как воссоздать изображение всего по нескольким пикселям Машинное обучение, Программирование, Data Science, Длиннопост

Матрица C соответствует измерениям единичных пикселей, её строки получены из единичной матрицы n × n. В такой ситуации решение задачи оптимизации не особо нам поможет, поскольку оно вернёт только повреждённое изображение (произведение матриц справа сводится к Cᵀ). Очевидно, что это нам не подходит. Но можно ли найти решение получше?


Используем разреженность в спектральном пространстве


При обсуждении уникальных особенностей естественных изображений мы увидели, что они являются разреженными в пространстве Фурье, поэтому давайте этим воспользуемся. Обозначив как Ψ отображение матрицы n × n из пространства Фурье в пространство пикселей, мы получим следующий вид уравнения измерений:

Как воссоздать изображение всего по нескольким пикселям Машинное обучение, Программирование, Data Science, Длиннопост

где s — преобразование Фурье x (т. е. x = Ψs). Это по-прежнему задача с высокой степенью неопределённости, но теперь у нас есть дополнительная информация о решении, которое мы ищем. Мы знаем, что оно должно быть разреженным. Введя псевдонорму ℓ₀ для s (т. е. его число ненулевых элементов), мы сможем сформулировать следующую задачу оптимизации:

Как воссоздать изображение всего по нескольким пикселям Машинное обучение, Программирование, Data Science, Длиннопост

К сожалению, это задача комбинаторики, очень быстро становящаяся нерешаемой. Чтобы найти её решение, потребуется проверить все возможные сочетания. К счастью в своей революционной работе 2006 года Канде et al. [1, 2] показал, что при условии разумных допущений решение изложенной выше задачи можно получить (с высокой вероятностью) при помощи решения более простой задачи:

Как воссоздать изображение всего по нескольким пикселям Машинное обучение, Программирование, Data Science, Длиннопост

Здесь норма ℓ₁ — это сумма абсолютных значений вектора s. Сегодня хорошо известно, что использование нормы ℓ₁ кроме превращения задачи оптимизации в выпуклую, склонно отдавать предпочтение разреженным решениям. Несмотря на свою выпуклость, эту задачу всё равно может быть достаточно сложно решить на стандартном компьютере. В дальнейшем мы используем более ослабленную версию, задаваемую следующим образом:

Как воссоздать изображение всего по нескольким пикселям Машинное обучение, Программирование, Data Science, Длиннопост

где λ — это задаваемый пользователем параметр, управляющий равновесием между соответствием ограничениям и необходимой разреженностью решения. Эту задачу оптимизации называют Basis Pursuit Denoising. При помощи проксимальных операторов она решается чрезвычайно быстро. Ниже представлена реализация на Julia с использованием StructuredOptimization.jl.

using StructuredOptimization
" " "
Simple implementation of basis pursuit denoising using StructuredOptimization.jl
INPUT
- - - - -
C : The measurement matrix.
Ψ : Basis in which x is assumed to be sparse.
y : Pixel measurements.
λ : (Optional) Sparsity knob.
OUTPUT
- - - - - -
x : Estimated image.
" " "
function bpdn(C, Ψ, y ; λ=0.1)
# - - > Initialize variable.
x = Variable(eltype(y), size(Ψ, 2))
# - - > Solve the compressed sensing problem.
@minimize ls(C * Ψ * x - y) + λ*norm(x, 1)
return ~x
end

Кроме того, мы можем воспользоваться тем фактом, что для спектральных преобразований произведение матрицы и вектора Ψs при помощи алгоритма быстрого преобразования Фурье можно вычислить за O(n log n) операций вместо O(n²).

using StructuredOptimization
" " "
Simple implementation of basis pursuit denoising using StructuredOptimization.jl
INPUT
- - - - -
m, n : Size of the image in both direction.
idx : Linear indices of the measured pixels.
y : Pixel measurements.
λ : (Optional) Sparsity knob.
OUTPUT
- - - - - -
x : Estimated image.
" " "
function bpdn(m, n, idx, y ; λ=0.1)
# - - > Initialize variable.
x = Variable(eltype(y), m, n)
# - - > Solve the compressed sensing problem.
@minimize ls(idct(x)[idx] - y) + λ*norm(x, 1)
return ~x
end

Хотя до сих пор мы предполагали, что Ψ является преобразованием Фурье, в этом фрагменте кода мы использовали косинусное преобразование, являющееся более эффективным преобразованием для изображений. Теперь у нас есть всё необходимое, поэтому давайте вернёмся к исходной задаче. На изображении ниже сравнивается истинное изображение с его реконструкцией при помощи ℓ₁.

Как воссоздать изображение всего по нескольким пикселям Машинное обучение, Программирование, Data Science, Длиннопост

Слева: оригинал изображения. Справа: изображение, воссозданное при помощи compressive sensing на основании данных всего 10% пикселей

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


Заключение


Методика Compressed Sensing совершила революцию в сфере обработки сигналов. Если мы заранее знаем, что сигнал, с которым работаем, разрежен по указанному базису, то compressed sensing позволяет восстановить его по гораздо меньшему количеству сэмплов, чем предполагается по теореме выборки Найквиста-Шеннона. Кроме того, она позволяет значительно сжимать данные непосредственно на этапе получения, уменьшая таким образом необходимый объём хранилища данных. Также Compressed Sensing привела к возникновению неожиданных новых технологий, например, однопиксельной камеры, разработанной Университетом Райса, или новых техник обработки для создания визуализаций МРТ в медицине. Я не сомневаюсь, что в ближайшие несколько лет мы станем свидетелями множества новых способов применения этой методики.


Compressed sensing — это гораздо более глубокая область математики, чем можно судить по этому ознакомительному посту. Существует ещё множество не рассмотренных нами вопросов, например:


- Каково наименьшее количество необходимых измерений?


- Могут ли некоторые измерения быть информативнее других?


- Как выбирать эти измерения, имея базис Ψ?


- Существуют ли другие нормы, лучше подходящие для изображений?


Для ответа на эти вопросы потребуется гораздо больше математики, чем можно представить в посте. Если вы хотите знать больше, то крайне рекомендую изучить оригиналы статей, ссылки на которые я указал в конце. Также стоит изучить потрясающий веб-сайт Numerical Tours Габриеля Пейре или последнюю книгу Брантона и Кутца [3], а также соответствующий канал на YouTube (здесь и здесь).


Ссылки на научные работы


[1] Candès E., Romberg J., Tao T. Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied mathematics. 58(8): 1207–1223. 2006.


[2] Candès E. Compressed sensing. IEEE Transactions on Information Theory. 52(4): 1289–1306. 2006.


[3] Brunton S. L. and Kutz J. N. Data-driven science and engineering: machine learning, dynamical systems, and control. Cambridge University Press, 2019.

Автор оригинала: Jean-Christophe B. Loiseau

Перевод: https://habr.com/ru/company/timeweb/blog/549024/

Показать полностью 12

История проблемы равенства классов P и NP

История проблемы равенства классов P и NP Математика, Теория, Задача, Машина тьюринга, Алгоритм, Научпоп, Длиннопост

В 2000 году Математический институт Клэя определил 7 математических задач, решение которых не могли найти в течение многих лет. За решение каждой из них была назначена награда в размере 1 миллиона долларов. Эти 7 задач известны как «задачи тысячелетия», и на сегодняшний день только одна из них была решена — гипотеза Пуанкаре. В этой статье пойдет речь о вопросе равенства классов P и NP, ответ на который может сильно повлиять на всю IT-сферу.


Вспомогательные детали


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


Алфавит


В теории алгоритмов алфавит — это непустое конечное множество символов. Набор символов ASCII - это алфавит. {0 , 1} - тоже алфавит. {} - такое множество нельзя назвать алфавитом, поскольку оно пустое, а множество целых чисел Z нельзя назвать алфавитом, поскольку оно бесконечно.


Слово


Допустим, мы имеем алфавит. Назовем его A. Тогда словом над алфавитом А является упорядоченное соединение конечного числа символов. Например, 110110 — это слово над алфавитом {0 , 1}, а «habr» - слово над алфавитом ASCII символов. Но число пи не будет словом над алфавитом { . , 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9}, так как число пи из символов данного алфавита не будет конечным. Над любым алфавитом существует пустое слово, обозначать его будем символом e. Слова обладают такой характеристикой, как длина, т. е. количество символов в нем. Обозначать длину слова будем в виде модуля. Длина вышеупомянутого слова |110110| = 6.


Язык


Возьмем уже упомянутый алфавит А. Пусть множество А* содержит все слова над алфавитом А, а множество А+ также содержит все слова над А, за исключением e (значки + и * взяты из регулярных выражений). Множество Аn содержит все слова длины n. Для любого алфавита множества А* и А+ будут бесконечными (можно составить бесконечное количество слов разной длины для любого алфавита). Для алфавита А = {0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9} множество А2 будет представлять набор из двузначных чисел.


Пусть А — алфавит и L ⊆ А*, тогда L называется языком над А. Для любого алфавита пустое множество и А* являются тривиальными языками. При этом пустое множество часто называют пустым языком. Однако не стоит путать пустой язык и язык, содержащий пустое слово e, — они различны. Языки могут быть как бесконечными, так и нет, но обязательно счетными. Т. е. множество всех действительных чисел языком нельзя назвать, т. к. такой набор является неисчисляемым.


Абстрактный исполнитель


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

История проблемы равенства классов P и NP Математика, Теория, Задача, Машина тьюринга, Алгоритм, Научпоп, Длиннопост

Устройство машины Тьюринга

На основе машины Тьюринга определим так называемую разрешающую машину над языком. Для начала введем определение характеризующей функции X(w). Функция X определяет, принадлежит ли слово w языку L. Если да, то значение функции равно «1»; если нет, то «0». Формально это можно записать так:

История проблемы равенства классов P и NP Математика, Теория, Задача, Машина тьюринга, Алгоритм, Научпоп, Длиннопост

Разрешающей машиной D для языка L называется такая машина, которая для каждого w∈A вычисляет характеризующую функцию X(w) за конечное время.


В дополнение к разрешающей машине идет верификатор. Машина V, которая принимает слова w и c и выводит 0 или 1 после конечного числа шагов, называется верификатором для L, если она обладает следующими свойствами:


- выводит 1, только если w входит в язык L;


- для любого w в языке L существует такое c, что V(w,c) = 1.


В данной машине буквой с называется свидетель или сертификат. Фактически, верификатор также проверяет, входит ли какое-либо слово в язык, однако делает это с учетом свидетеля, который ускоряет проверку. Например, возьмем число 182652. Входит ли оно в язык простых чисел, т.е. является ли оно простым. Без компьютера это будет довольно сложно проверить, однако имея сертификат — числа 186 и 982, произведение которых дает в результате число 182652, - задача проверки сильно упрощается. Фактически, свидетель - это любая информация, упрощающая проверку вхождения слова в язык.

Классы сложности и формулировка проблемы


Окей, мы рассмотрели несколько понятий. На первый взгляд, все это больше походит на лингвистику: алфавиты, слова, языки… Причем тут задачи? Чтобы ответить на этот вопрос, обратимся к понятию задача разрешимости (англ. Decision problem). Это такой вопрос (сформулированный в формальной системе), требующий ответа «да» или «нет», зависящего, возможно, от значений некоторых входных параметров. Например, «является ли данное натуральное число x простым?» или «даны два числа: x и y; делится ли x на y?« Метод решения в виде алгоритма называется разрешающей процедурой. Теория вычислимости имеет дело в основном с задачами разрешимости и приведенные выше конструкции наглядно соотносятся с таким типом задач: так разрешающая машина над языком является формализацией разрешающей процедуры. Но как же быть с задачами, такими как задача коммивояжера? На них нельзя дать бинарный ответ. В таких случаях применяют приемы приведения к версии decision problem. В случае коммивояжера проблема по-новому формулируется так: «существует ли маршрут не длиннее, чем заданное значение k?»

В класс сложности NP входят все языки L, для которых существует такой верификатор, что для каждого (w,c) время его работы полиномиально. Иными словами, NP включает в себя задачи разрешимости, для которых при подходящем сертификате для данного w мы быстро сможем удостовериться в том, что w действительно принадлежит L (ответ на вопрос можно довольно быстро проверить). Отсюда и название «верификатор». В качестве примера задачи в NP можно привести определение наличия в графе гамильтонова цикла. Сертификат в данном случае — последовательность вершин, образующих гамильтонов цикл.


Помимо этих классов можно выделить ещё 2: NP-hard и NP-Complete. Они основываются на приводимости одного языка к другому за полиномиальное время: пусть языки A и B — языки над одним алфавитом. Язык А будет приводимым за полиномиальное время к языку B, если существует такая функция f(w), что


w ∈ A ⇔ f ( w ) ∈ B,


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


Тогда в класс NP-hard будут входить языки, к которым приводимы все языки в NP (причем NP-hard язык может входить в NP, а может и нет), а в NP-Complete те языки, которые являются одновременно NP-hard и NP. Примером NP-Complete является язык выполнимых булевых формул (SAT). Таким образом, NP-Complete задачи образуют в некотором смысле подмножество «типовых» задач в классе NP: если для какой-то из них найден «полиномиально быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро».
История проблемы равенства классов P и NP Математика, Теория, Задача, Машина тьюринга, Алгоритм, Научпоп, Длиннопост

Отношение между классами при равенстве и неравенстве

Формулировка проблемы


Теперь, немного погрузившись в теорию алгоритмов, более конкретно обозначим проблему равенства данных классов. Итак, множество P входит в множество NP, но неизвестно, существуют ли языки, которые входят в NP и не входят в P. Что это означает на практике? Итак, простыми словами класс NP можно охарактеризовать как «трудно решить, легко проверить». Классическим примером задачи, входящей в NP, является задача коммивояжера, для решения которой на данный момент известен лишь один алгоритм — старый добрый перебор (мы не рассматриваем эвристические методы). Однако, получив ответ, его будет не так сложно проверить. Класс P же вобрал в себя те задачи, для которых существует эффективный алгоритм решения, позволяющий решать их за полиномиальное время. И равенство или, наоборот, неравенство этих классов пока не доказано. Если эти классы равны, то это будет значить, что для всех задач, которые сейчас решаются путем перебора или другим неэффективным методом, существует(-ют) полиномиальные алгоритмы. А если не равны, то придется смириться с неоптимальностью решения этих задач.


История


История проблемы равенства P и NP началась в 1928 году, когда Давид Гильберт сформулировал проблему, названную Entscheidungsproblem (нем. задача разрешения). Ее суть заключается в нахождении алгоритма, определяющего доказуемость данного утверждения из аксиом с использованием правил логики. По названию очевидно, что это задача является задачей разрешения (выводит «да» или «нет»).


В ходе решения этой проблемы потребовалось определить термины «алгоритм» и «вычислимая функция». В 1936 году Алонзо Чёрч и Алан Тьюринг независимо показали, что общее решение Entscheidungsproblem невозможно, предположив, что интуитивное понятие «эффективная вычислимость» соответствует вычислимости функции на машине Тьюринга. Эта гипотеза сегодня известна как тезис Чёрча-Тьюринга.

История проблемы равенства классов P и NP Математика, Теория, Задача, Машина тьюринга, Алгоритм, Научпоп, Длиннопост

Алонзо Чёрч

20 марта 1956 в письме к Джону фон Нейману Курт Гёдель впервые поставил вопрос о вычислительной сложности. Гёдель интересовался, можно ли получить доказательство теоремы (в математико-логическом смысле слова) за квадратичное или линейное время. К сожалению, письмо было обнаружено лишь в 1989 году и получило широкую огласку, когда Юрис Хартманис опубликовал перевод и комментарий.


Статья Алана Кобэма 1965 года под названием «The intrinsic computational difficulty of functions» является одним из первых упоминаний класса сложности P, состоящего из разрешимых за полиномиальное время задач. Тезис Кобэма-Эдмондса (известный также как расширенный тезис Чёрча-Тьюринга), названный в честь Алана Кобэма и Джека Эдмондса, утверждает, что любая разумная модель вычислений может быть выражена через другую модель с замедлением, не более чем полиномиальным по размеру входных данных. Кобэм предположил, что класс P может быть хорошим способом для описания множества реально вычислимых задач. Любая проблема, не содержащаяся в P, невозможна, но если задача реального мира может быть решена с помощью алгоритма, существующего в P, то такой алгоритм в конечном итоге будет открыт.


В 1965 году Юрис Хартманис и Ричард Стернс опубликовали статью «On the Computational Complexity of Algorithms», отмеченную премией Тьюринга. В ней даются более точные определения сложности алгоритма и класса сложности. Хартманис и Стернс определили класс сложности как совокупность всех задач, которые можно решить за установленные временные рамки. В их статье показано, что существует бесконечная иерархия классов сложности (например, задачи, для которых наиболее быстрый алгоритм имеет время, пропорциональное n, n log n, n^2, n^3, 2^n и т. д.), где небольшое увеличение временного интервала позволяет решать больше задач. Во второй статье Хартманис совместно с Филипом М. Льюисом показали, что подобная иерархия существует и для количества памяти (функция от размера входа) при решении задачи на машине Тьюринга.


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

История проблемы равенства классов P и NP Математика, Теория, Задача, Машина тьюринга, Алгоритм, Научпоп, Длиннопост

Мануэль Блюм

Точная формулировка проблемы равенства P и NP была представлена в 1971 году. Тогда американский ученый Стивен Кук и работавший независимо советский ученый Леонид Левин доказали, что существуют практически актуальные проблемы, которые являются NP-полными. В США Стивен Кук опубликовал статью «The complexity of theorem proving procedures», в которой формализовал понятия редукции за полиномиальное время и NP-полноты, а также доказал существование NP-полной задачи (задача выполнимости булевых формул, SAT). Теорема была независимо доказана Леонидом Левиным и, таким образом, получила название «теорема Кука-Левина».


В 1972 году Ричард Карп сделал рывок в знаменитой статье «Reducibility among Combinatorial Problems», в которой показал, что около 20 разнообразных задач из комбинаторики и теории графов, известных своей вычислительной трудностью, являются NP-полными.


В августе 2010 года Виней Деолаликар, работавший в исследовательском отделении Hewlett-Packard в Пало-Альто в Калифорнии, заявил, что разгадал загадку P vs NP. Он утверждал, что P не равняется NP, однако научное сообщество нашло в его доказательстве фатальную ошибку. В начале 2002 года SIGACT News провел опрос среди 100 ученых, задав им вопрос о равенстве классов NP и P. 61 человек ответили, что «неравны», 9 — «равны», 22 затруднились ответить и 8 сказали, что гипотеза не выводима из текущей системы аксиом и, таким образом, не может быть доказана или опровергнута.


К чему приведет решение проблемы


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


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


Может оказаться и так, что последствия решения окажутся не такими тривиальными, как это часто и бывает в математике. В качестве примера рассмотрим континуум-гипотезу о существовании мощности, меньшей континуума и большей мощности счетного множества. Оказывается, существование такого кардинала нельзя ни доказать, ни опровергнуть в аксиоматике ZFC. Так что мы вправе считать, что такие мощности бывают (впрочем, как и считать, что не бывают). Однако ясно, что мы не можем конструктивно построить соответствующее множество. Возможно, точно также окажется и с алгоритмами для NP-задач в случае равенства NP и P (к слову, некоторые математики в опросе SIGACT News так и ответили: гипотеза не выводима из существующей системы аксиом, то есть не может быть доказана или опровергнута).


Пока что существующих методов доказательств недостаточно для строго математического ответа, но не нужно терять надежду. В марте 2001 года Ричард Карп предсказал, что проблема будет решена молодым математиком (до 30 лет) с использованием подхода, о котором еще никто не думал. Стивен Кук заявил, что кто-нибудь предоставит убедительное доказательство в ближайшие 20 лет.

Показать полностью 5

Притча о мотивации: математик Джордж Данциг

Притча о мотивации: математик Джордж Данциг Мотивация, Школа, Притча, Учитель, Математика, IT, Программирование, Подкаст, Видео

Мотивирующая притча основана на реальных событиях, такой случай имел место в реальной жизни:


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


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


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


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


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

Автор: Владимир Демянович

Оригинал: https://elims.org.ua/pritchi/pritcha-o-rabote-matematik-dzho...

Показать полностью 1
Отличная работа, все прочитано!