Леонард Адлеман

Леонард Адлеман

Леонард Макс Адлеман (родился 31 декабря 1945 года) — американский ученый-компьютерщик. Он является одним из создателей алгоритма шифрования RSA, за что в 2002 году получил премию Тьюринга. Он также известен созданием области ДНК-вычислений и введением термина «компьютерный вирус».

Биография

Леонард М. Адлеман родился в еврейской семье в Калифорнии. Его семья иммигрировала в Соединенные Штаты из современной Беларуси, из района Минска. Он вырос в Сан-Франциско и учился в Калифорнийском университете в Беркли, где в 1968 году получил степень бакалавра математики, а в 1976 году — степень доктора философии в области электротехники и компьютерных наук (EECS). Он также был математическим консультантом фильма «Тихоходы». В 1996 году он стал членом Национальной инженерной академии за вклад в теорию вычислений и криптографию. Он также является членом Национальной академии наук.

Адлеман также увлекается любительским боксом и спарринговал с Джеймсом Тони.

Открытие

В 1994 году в его статье Molecular Computation of Solutions To Combinatorial Problems было описано экспериментальное использование ДНК в качестве вычислительной системы. В ней он решил задачу о гамильтоновом цикле с семью вершинами, представляющую собой NP-полную задачу, похожую на задачу коммивояжера. Хотя решение задачи с семью вершинами тривиально, эта статья является первым известным случаем успешного использования ДНК для вычисления алгоритма. Было доказано, что ДНК-вычисления обладают потенциалом в качестве средства решения нескольких других крупномасштабных задач комбинаторного поиска. Адлемана часто называют отцом ДНК-вычислений.

В 2002 году он и его исследовательская группа смогли решить «нетривиальную» задачу с использованием ДНК-вычислений. В частности, они решили SAT-задачу с 20 переменными, имеющую более 1 миллиона возможных решений. Они сделали это так же, как Адлеман использовал в своей основополагающей статье 1994 года. Сначала была синтезирована смесь цепей ДНК, логически представляющих пространство решений задачи. Затем с этой смесью провели алгоритмические манипуляции с использованием биохимических методов, чтобы отсеять «неправильные» цепи, оставив только те, которые «удовлетворяли» задаче. Анализ нуклеотидной последовательности этих оставшихся цепей выявил «правильные» решения исходной задачи.

Он является одним из первооткрывателей теста простоты Адлемана — Померанса — Румели.

Фред Коэн в своей статье 1984 года Experiments with Computer Viruses приписал Адлеману авторство термина «компьютерный вирус».

По состоянию на 2017 год Адлеман работает над математической теорией страт. Он является профессором компьютерных наук в Университете Южной Калифорнии.

Награды

За вклад в изобретение криптосистемы RSA Адлеман вместе с Роном Ривестом и Ади Шамиром был удостоен премии Парижа Канеллакиса за теорию и практику в 1996 году и премии Тьюринга в 2002 году, которую часто называют Нобелевской премией по информатике. Адлеман был избран членом Американской академии искусств и наук в 2006 году и фелло ACM в 2021 году.