Вычислительное мышление. Метод решения сложных задач - Питер Макоуэн

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

Теперь представьте, что где-то в сетке располагаются два эсминца. На этот раз мы не скажем, где они. Ваш друг снова сообщает вам сумму значений в каждой строке и столбце. На этот раз вы узнаете, что у вас есть 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» инженер-электрик сэр Годфри Хаунсфилд совместно с другим ученым был удостоен Нобелевской премии по медицине, а позже за свои достижения возведен в рыцарское достоинство. Сейчас томография постоянно используется в медицине, а еще в археологии — например, чтобы увидеть, как выглядят в разрезе египетские мумии, и в геофизике, чтобы заглянуть внутрь нашей планеты. Это еще один пример того, как математика, техника и программирование, объединившись в нужный момент, могут полностью изменить наш образ действий.

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

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

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

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