Математика для гиков - Рафаель Роузен 7 стр.

Однако самый подробный пример процедуры, которая могла отличить машину от живого существа, обладающего разумом, был представлен в 1950 году в работе Алана Тьюринга, британского математика и криптографа, который во время Второй мировой войны взломал код немецкой шифровальной машины «Энигма». Его работа «Вычислительные машины и разум» содержала тест, который помог бы ответить на вопрос: «Может ли машина обладать разумом?»

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

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

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

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

Даже сегодня тест Тьюринга не потерял свою привлекательность. Тесты Тьюринга проводят каждый год; в 2014 году в России виртуальный собеседник Женя Густман прошел его, убедив 33 % судей, что он человек. Однако некоторые люди оспаривают эту победу: Женя был создан, чтобы имитировать 13-летнего мальчика из Украины, который выучил английский как второй язык.

Несмотря на достижения и в военное время, и в мирное, с Тьюрингом очень жестоко обошлись в Великобритании. Узнав о гомосексуализме Тьюринга – а это было уголовным преступлением в то время, – британское правительство арестовало его в 1952 году. Так как считалось, что гомосексуалистов могут шантажировать, его допуск к засекреченной информации был отозван, и ему предложили выбрать между тюремным заключением и инъекциями эстрогена, которые подавляли либидо. Он выбрал инъекции. Возможно, из-за того, как относилось к нему правительство, в 1954 году Тьюринг покончил жизнь самоубийством.

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

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

2.7. Что такое секстант?

Математическое понятие: геометрия

Если вы плывете на лодке в открытом океане, как вы определите, где находитесь? Чтобы усложнить задачу, давайте исключим использование GPS или всего, что связано с электричеством. (Google-картами пользоваться нельзя.) Проблема кажется непреодолимой, но мореплаватели веками определяют свое месторасположение, поэтому мы знаем, что это возможно. В чем секрет?

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

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

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

Предположим, что 21 июня 2015 года вы отплыли на лодке от берега острова Рождества, австралийской территории около Индонезии в Индийском океане. Используя секстант, вы сможете определить, что солнце на 66 градусов выше горизонта. С помощью этой информации вы можете определить, что широта равна 10,48 градуса в Южном полушарии.

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

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

Первый настоящий секстант был изобретен Джоном Кэмпбеллом в 1757 году и был впервые использован по максимуму, включая и определение времени, исследователем капитаном Куком в 1768 году, когда он отправился в Новую Зеландию, чтобы нанести ее на карту.

2.8. Дележ аренды

Математические понятия: справедливый дележ, комбинаторика

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

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

В 1999 году Френсис Су, профессор математики из колледжа Харви Мадд, опубликовал исследование, в котором объяснил, как решить проблему справедливого дележа, используя лемму Шпернера, теорему, затрагивающую раздел математики, известный как комбинаторика (см. главу 1.26). Изначально лемма затрагивает треугольники. Возьмите треугольник и разделите его внутри на маленькие треугольники. Вы можете разделить его на любое количество треугольников; просто убедитесь, что они плотно прилегают друг к другу и между ними нет свободного пространства. Дальше обозначьте вершины большого треугольника цифрами 1, 2 и 3 так, чтобы каждая вершина была обозначена разными цифрами. На этом этапе заметьте, что углы некоторых треугольников меньшего размера касаются как минимум одной стороны большого треугольника. На каждом угле напишите цифру. На стороне между вершинами 1 и 2 отметьте каждый угол меньших треугольников 1 или 2. (Какую цифру вы поставите, зависит только от вас.) На стороне между вершинами 2 и 3 отметьте каждый угол 2 или 3, а на стороне между углами 3 и 1 отметьте каждый угол 3 или 1. Что касается углов внутри большого треугольника, вы можете отметить их цифрами 1, 2 и 3 в любом порядке. Лемма Шпернера утверждает, что там должен быть хотя бы один маленький треугольник с вершинами 1, 2 и 3. Их может быть больше чем один, но их всегда будет нечетное число.

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

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

Особый пример справедливого дележа возник после Второй мировой войны, когда члены антифашистской коалиции пытались выяснить, что делать с Берлином. В итоге они поделили город на четыре секции. Секции США, Великобритании и Франции сформировали Западный Берлин, а секция СССР сформировала Восточный Берлин.

2.9. Справедливое разрезание торта на куски

Математическое понятие: справедливый дележ

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

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

2. Будет невозможно сделать кого-то счастливее, чем они уже есть, и при этом не расстроить никого другого. Это условие называется результативностью.

3. Разделение должно быть справедливым, то есть каждый человек должен видеть, что все куски имеют одинаковую ценность. (Например, если торт делили три человека, и каждый из них любил цветы из крема, они бы увидели, что разделили справедливо, если бы на каждом куске был цветок.)

В 2014 году два исследователя, Джулиус Барбанель из Юнион-колледжа и Стивен Брамс из Нью-Йоркского университета, опубликовали алгоритм в журнале The Mathematical Intelligencer, который, по их утверждению, отвечает всем трем критериям, результатом чего является идеальное разрезание торта на доли. (Однако их метод предполагает, что торт делят всего лишь два человека.) Алгоритм берет во внимание тот факт, что торт «гетерогенный», то есть он имеет разные части, которые два человека ценят по-разному. Один человек, например, может любить большое количество крема на внешнем крае торта, а другому больше нравится тесто, нежели крем. Кроме того, этот метод зависит от третьей стороны, которая выступает в качестве судьи. Наконец, в алгоритме упоминается функция плотности вероятности, которая является просто математическим способом представления предпочтений людьми разных частей торта.

В первом шаге алгоритма каждый человек представляет свою функцию плотности вероятности, или ФПВ, судье. (Судья может принимать различные формы: компьютер, старшая сестра, прохожий на улице или родители.) Судья отмечает на торте все места, где ФПВ пересекаются; другими словами, где пересекаются предпочтения каждого человека. Судья назначает порции согласно этим предпочтениям, и если на этом этапе каждый человек получает куски одинакового размера, алгоритм останавливается, и все начинают есть. Например, скажем, что человек А любит шоколадный торт, а человек Б любит ванильный. Если торт поделен пополам двумя разными вкусами, то судья просто может разрезать торт по демаркационной линии и дать каждому человеку кусок, который ему больше нравится. Но если торт разделен не поровну, то человек с большим куском отдает часть своей доли другому человеку, начиная с того места, где степень его предпочтений является наименьшей. Этот процесс продолжается, пока объем порции каждого человека не станет одинаковым.

Помимо метода Брамса – Барбанеля, который помогает двум людям справедливо поделить торт, существует другой, более общий метод, который может помочь неограниченному количеству людей разделить торт на неограниченное количество кусков. Этот метод изобрели Брамс и другой математик, Алан Тейлор, он был опубликован в январе 1995 года в выпуске журнала American Mathematical Monthly. Этот общий метод несколько сложный, но суть в том, что после того, как торт был порезан человеком А, человек Б может обрезать некоторые куски, чтобы сделать их более одинаковыми, если он чувствует, что человек А несправедливо порезал торт. Затем человек В может обрезать куски, потом человек Г и так далее. Кроме того, этот метод обеспечивает наличие лишних кусков торта, поэтому если кто-то почувствует себя обманутым, они всегда смогут выбрать один из оставшихся кусков, который будет такого размера, каким бы его хотели видеть.

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

2.10. Эффективная доставка посылок

Математическое понятие: задача коммивояжера

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

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