Джон Хопкрофт: Учебник, который сформировал дисциплину

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

От сына уборщика до Стэнфорда

Джон Эдвард Хопкрофт родился 7 октября 1939 года в Сиэтле, штат Вашингтон, в семье рабочего класса; его отец, британский ветеран Первой мировой войны, работал уборщиком, и ни один из родителей не закончил среднюю школу. Он также был внуком Джейкоба Ниста, основателя компании Seattle-Tacoma Box Company. Несмотря на ограниченное образование, его родители поощряли его интеллектуальное любопытство, и он получил степень бакалавра электротехники в Сиэтлском университете в 1961 году, за которой последовали степень магистра в 1962 году и докторская степень в 1964 году, обе по электротехнике, в Стэнфордском университете. Эта инженерная подготовка, а не образование в области чистой математики или компьютерных наук, сформировала его более поздний инстинкт к алгоритмам, которые были не просто теоретически элегантными, но и действительно эффективными в исполнении.

Создание учебников дисциплины

Хопкрофт начал свою академическую карьеру в Принстонском университете в качестве доцента, прежде чем перейти в Корнеллский университет, где он провел большую часть своей карьеры, в конечном итоге получив звание профессора инженерии и прикладной математики IBM и занимая руководящие должности, включая заведующего кафедрой и декана инженерного факультета. Именно в Корнелле он в соавторстве с Джеффри Ульманом, а позже с Альфредом Ахо, написал серию учебников по формальным языкам, теории автоматов и проектированию алгоритмов, которые стали стандартными учебными текстами для поколений студентов компьютерных наук по всему миру. Эти книги сделали больше, чем просто обобщили существующие знания — они кодифицировали анализ асимптотической сложности и теорию формальных языков в том виде, в котором их до сих пор преподают на вводных теоретических курсах, дав области общий словарь еще до того, как этот словарь полностью существовал в других местах.

Алгоритмы, которые работают до сих пор

Помимо учебников, собственные исследования Хопкрофта привели к созданию инструментов, которые до сих пор активно используются. Алгоритм Хопкрофта-Карпа, разработанный совместно с Ричардом Карпом, находит максимальные паросочетания в двудольных графах быстрее, чем любой предшествовавший ему метод, и остается стандартной техникой в задачах сетевого потока и назначения. Он также разработал эффективный алгоритм минимизации детерминированных конечных автоматов, фундаментальный инструмент в проектировании компиляторов и формальной верификации. Однако его самым известным результатом стала совместная работа с Робертом Тарьяном: первый алгоритм линейного времени для проверки того, является ли граф планарным — можно ли его нарисовать на плоской поверхности без пересечения ребер — опубликованный в 1974 году. Они построили алгоритм вокруг систематического использования поиска в глубину, превратив то, что было медленной, специальной задачей, в задачу, решаемую за время, пропорциональное размеру самого графа.

Премия Тьюринга и ее коллективный характер

В 1986 году Хопкрофт и Тарьян совместно получили премию ACM A.M. Turing Award, высшую награду в области вычислительной техники, «за фундаментальные достижения в проектировании и анализе алгоритмов и структур данных». В формулировке премии оба ученых названы вместе, и заслуга приписывается совокупности совместных и параллельных работ, а не одному индивидуальному прорыву — алгоритм планарности является главным из достижений, которые имелись в виду, наряду с независимым вкладом каждого из них в более широкую область проектирования алгоритмов.

Вторая карьера в Китае

В десятилетия после получения премии Тьюринга Хопкрофт направил большую часть своей энергии на укрепление образования в области компьютерных наук за пределами Соединенных Штатов, особенно в Китае. Он стал содиректором Центра передовых исследований в области вычислений Пекинского университета и возглавляет центры, носящие его имя, в Шанхайском университете Цзяотун и Хуачжунском университете науки и технологий, наставляя студентов и помогая создавать исследовательские программы по алгоритмам и, в последнее время, по глубокому обучению. Китай наградил его премией Дружбы в 2016 году, признанием, зарезервированным для иностранных экспертов, внесших выдающийся вклад в развитие страны — необычный второй акт для лауреата премии Тьюринга, который уже десятилетиями отошел от работы, принесшей ему премию.

Признание

Хопкрофт был избран в Национальную инженерную академию в 1989 году, стал членом ACM в 1994 году и получил медаль IEEE Джона фон Неймана в 2010 году за выдающиеся достижения в области компьютерных наук и инженерии, в дополнение к премии Тьюринга 1986 года и китайской премии Дружбы 2016 года.

Почему Джона называют гением

Аргумент в пользу гениальности Хопкрофта основывается не на одном ослепительном доказательстве, а на более редком сочетании: исследовательский вклад, достаточно существенный, чтобы получить высшую награду в области, в сочетании с непревзойденным даром дистилляции основ этой области в преподаваемую форму. Алгоритм планарности и алгоритм паросочетания Хопкрофта-Карпа — это те результаты, на которые теоретики компьютерных наук указывают как на действительно умные — сводящие задачи, которые, казалось, требовали перебора, к линейному или почти линейному времени благодаря структурному пониманию. Но честная формулировка, которую сама формулировка премии Тьюринга делает явной, заключается в том, что его самый известный результат принадлежит совместно ему и Роберту Тарьяну; формулировка ни одного из них не стоит отдельно, и премия была присуждена за совокупность достижений, а не за одиночный прорыв. Что реже разделяется и реже празднуется как «гениальность», так это его второй талант: три отдельных учебника в соавторстве, настолько хорошо построенных, что они стали стандартным способом, которым целая дисциплина преподает сама себе свои основы, форма интеллектуального вклада, более близкая к мастерскому преподаванию, чем к индивидуальному изобретению.

Наследие

Наследие Хопкрофта идет по двум параллельным путям, которые редко совпадают в одной карьере — исследовательский послужной список в области алгоритмов, отмеченный премией Тьюринга, и десятилетия второго акта по созданию инфраструктуры образования в области компьютерных наук в Китае. Мало кто в истории этой области формировал то, как она преподается, так прямо или так долго, как автор ее самых широко назначаемых учебников. Тот факт, что человек, который помогал формализовать теорию вычислений в 1960-х и 1970-х годах, к 2010-м годам наставлял студентов по глубокому обучению в Пекинском университете, говорит о необычайной продолжительности и широте его трудовой жизни: карьера, которая началась в эпоху электротехники, близкой к вакуумным лампам, и продолжилась в эпоху нейронных сетей, никогда не теряя своей главной линии — обучения следующего поколения базовой структуре области.