Инструкции по автоматическому поиску кораблей

Теперь представьте, что где-то в сетке располагаются два эсминца. На этот раз мы не скажем, где они. Ваш друг снова сообщает вам сумму значений в каждой строке и столбце. На этот раз вы узнаете, что у вас есть 2 в строке А, 0 в строке В и 0 в строке C; 1 в столбце 1, 0 в столбце 2, 1 в столбце 3 и 0 в столбце 4, как на рис. 71a. Где же корабли?

Вот общий подход к поиску кораблей. Во-первых, нам сказали, что в строке А сумма равна 2. Значит, там что-то есть! Мы можем распространить информацию о присутствии чего-то на всю строку А до самого конца. Хотя мы распределили данные по всей строке, мы все еще не знаем, где находится «что-то», а просто уверены, что оно где-то там есть. Давайте продолжать. Теперь распределим данные по строкам В и С. Здесь нет дополнительной информации, потому что в каждой строке стоит по нолю. В результате получается сетка как на рис. 71b.

Мы знаем, что в строке А что-то есть, это здесь и показано. Но пока мы не знаем, что же это такое. Теперь мы смотрим на столбцы и создаем новую сетку. Если так же распределить информацию по столбцам, где в столбце 1 будет 1, в столбце 2 — 0, в столбце 3 — 1 и в столбце 4 — 0, то получится сетка как на рис. 72a.

Мы знаем, что в столбцах 1 и 3 что-то есть, но не знаем, где именно. Чтобы окончательно решить эту задачу и восстановить расположение кораблей, мы просто складываем эти сетки с распределенной информацией вместе и получаем сетку как на рис. 72b.

В объединенной сетке, например, A1 = 2 + 1 = 3, A2 = 2 + 0 = 2, A3 = 2 + 1 = 3 и так далее. Если теперь посмотреть на эту объединенную сетку с двумя наборами распределенных данных, то мы увидим на ней два пиковых значения 3 на позициях A1 и A3. Эти пиковые значения и отмечают, где находятся корабли. Итак, у нас есть автоматический детектор кораблей, но, что еще важнее, есть и способ открыть истинное расположение кораблей на сетке. Мы можем восстановить, как выглядит наш пруд, по одним подсказкам — см. рис. 73. Чтобы этого добиться, нужно использовать результаты, которые получаются при сложении всех данных в строке и в столбце. Теперь пришло время сняться с якоря и вернуться к рентгеновским лучам. Как вы, вероятно, догадались, все это время мы занимались задачей, связанной именно с ними.

Вернемся к рентгеновским лучам

Рентген укажет место

Рентгеновский луч, проходя сквозь тело, поглощается костной тканью. Поэтому в конкретной точке рентгенографической пластины мы получаем нечто похоже на объединение всех «кораблей» (участки, занятые костной тканью) на пути рентгеновского луча (можно сказать, на строке игрового поля). Итак, наш рентгеновский луч похож на последовательность чисел: строка А = 2, строка B = 0 и строка C = 0. Мы знаем, что луч, поступающий в позицию А, прошел через большее число костей (кораблей), чем лучи, прошедшие через B или C. Но мы хотим знать, как эти кости расположены по отношению друг к другу. Находятся ли они близко или же далеко? В обоих случаях рентгеновское излучение будет поглощено в одном и том же объеме. Но можно вращать источник рентгеновского излучения, как и наш детектор кораблей, вокруг пациента, начиная сверху, а не сбоку, и сделать еще один снимок. На этот раз на рентгенографической пластинке появится информация о форме: колонка 1 = 1, колонка 2 = 0, колонка 3 = 1 и колонка 4 = 0.

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

Томограф группы «Битлз»

Этот метод называется компьютерная томография. Первый коммерческий успешный томограф, так называемый «сканер EMI», был разработан для звукозаписывающей компании Thorn EMI еще в 1960-е гг. Рассказывают, что компания финансировала дорогостоящие медицинские исследования на деньги, которые заработала на группе «Битлз» (возможно, самая успешная и влиятельная музыкальная группа за всю историю). Им нужно было потратить огромные деньги! Математические основания обратной проекции существовали уже давно. Однако пока не были разработаны способы их применения в медицине и, что более важно, пока не появились персональные компьютеры, на которых можно было бы производить математические расчеты в разумное время, все эти достижения оставались без внимания и никто не подозревал о связанных с ними революционных возможностях.

Изобретатель «сканера EMI» инженер-электрик сэр Годфри Хаунсфилд совместно с другим ученым был удостоен Нобелевской премии по медицине, а позже за свои достижения возведен в рыцарское достоинство. Сейчас томография постоянно используется в медицине, а еще в археологии — например, чтобы увидеть, как выглядят в разрезе египетские мумии, и в геофизике, чтобы заглянуть внутрь нашей планеты. Это еще один пример того, как математика, техника и программирование, объединившись в нужный момент, могут полностью изменить наш образ действий.

Магниты и модели

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

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

Чтобы сделать снимок тела изнутри, человека, находящегося в сканере, сначала подвергают воздействию постоянного магнитного поля. Это поле ориентирует все протоны тела в одном направлении. Затем к исследуемой области применяется электромагнитное излучение определенной частоты. При этом величина магнитного поля добавляется к исходной. В результате в разных областях тела создается разное магнитное поле. Если воздействовать на протоны нужной радиочастотой, они либо поглотят ее, либо излучат обратно. Частота, на которую отреа­гируют протоны, определяется силой местного магнитного поля. Она, в свою очередь, зависит от плотности протонов и объема мягких тканей.

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

Магнитный срез

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

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

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

Увидеть в действии

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

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

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

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

Еще больше измерений

Тепло и хорошо

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

Полость у нас в голове

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

Дышите глубже

Подобным образом, пульс и уровень кислорода в крови можно измерить с помощью датчика на кончике пальца. Это устройство пропускает сквозь палец световые волны в инфракрасном спектре и регистрирует, сколько поглотила кровь. В крови есть белок гемоглобин, который придает ей красный цвет и, что важнее, доставляет кислород в органы и ткани. Молекулы гемоглобина со связанным кислородом поглощают инфракрасный свет не так, как «ненасыщенный» гемоглобин без кислорода. Трюк, однако, в том, чтобы добавить еще один источник света, который будет светить только красным. Красный свет легче проходит сквозь кровь, полную кислорода, но поглощается, если кислорода нет, то есть происходит обратный процесс. Если использовать их вместе, можно точно измерить количество кислорода. Красный свет с длиной волны 660 нм и инфракрасный с длиной волны 940 нм подаются попеременно. Собранные данные с помощью цифровой справочной таблицы в устройстве (это удобное представление, которое позволяет быстро и легко справиться с задачей) конвертируются в показатель уровня кислорода в крови. Кроме того, это устройство, которое называется пульсоксиметр, позволяет измерять пульс, и этот показатель тоже отображается на экране. Прибор изобрели в 1970-х гг., а в продаже он впервые появился в 1980-х. Сегодня рынок пульсоксиметров оценивается в сотни миллионов долларов.