Гарри Рой Льюис (род. 1947) — американский ученый-компьютерщик, математик и администратор университета, известный своими исследованиями в области вычислительной логики , учебниками по теоретической информатике и работами по информатике, высшему образованию и технологиям. Он является профессором-исследователем компьютерных наук Гордона Маккея в Гарвардском университете и был деканом Гарвардского колледжа с 1995 по 2003 год.
По сути, вся карьера Льюиса прошла в Гарварде, где он был удостоен награды за «особо выдающийся вклад в преподавание студентов»; среди его учеников были будущие предприниматели Билл Гейтс и Марк Цукерберг , а также многочисленные будущие преподаватели Гарварда и других школ. Веб-сайт «Шесть градусов до Гарри Льюиса», созданный Цукербергом во время учебы в Гарварде, был предшественником Facebook .
Льюис родился в Бостоне [7] и вырос в Уэлсли, штат Массачусетс . [8] Его родители были врачами: отец — заведующим отделением анестезиологии , а мать — главой Деверской государственной школы для детей с умственными недостатками . [9] Его отец был ветераном Второй мировой войны и сыном немецкого лютеранина и русской еврейки . [10] После окончания с отличием в конце одиннадцатого класса Бостонской латинской школы Роксбери он поступил в Гарвардский колледж, где какое-то время был третьим вратарем по лакроссу . [8]
Льюис сказал, что он обнаружил, что «я не был настоящим математиком [когда] вышел из любительской лиги математики средней школы», но был «чрезвычайно взволнован» возможностями исследований в области компьютерных наук в Гарварде. [L2] На старших курсах он читал лекции в аспирантуре, используя программу компьютерной графики SHAPESHIFTER, которую он разработал для отображения преобразований сложной плоскости на электронно-лучевой трубке . SHAPESHIFTER автоматически распознавал формулы и команды, вводимые вручную с помощью стилуса на планшете RAND , и мог быть «обучен» распознавать почерк отдельных пользователей. [6] [11] В то время в Гарварде не было программы получения степени по информатике как таковой , [L2] в 1968 году Льюис получил степень бакалавра ( summa , Quincy House ) в области прикладной математики [5] [12] и был избран Фи Бета Каппа . [13]
Прослужив два года в Уполномоченном корпусе Службы общественного здравоохранения США в качестве офицера в должности математика и ученого-компьютерщика в Национальных институтах здравоохранения в Бетесде, штат Мэриленд , он провел год в Европе в качестве путешествующего научного сотрудника Фредерика Шелдона. Затем он вернулся в Гарвард, где получил степень магистра в 1973 году и доктора философии в 1974 году, после чего сразу же был назначен доцентом кафедры компьютерных наук. Он стал доцентом в 1978 году и профессором компьютерных наук Гордона Маккея в 1981 году.
Льюис официально вышел на пенсию в 2020 году, [14] [15] , но продолжает преподавать в качестве профессора-исследователя в области компьютерных наук Гордона Маккея. [16] Его жена Марлин МакГрат вышла на пенсию в 2021 году, проработав 42 года директором приемной комиссии Гарвардского колледжа. [17] Степень профессора инженерных и прикладных наук Гарри Льюиса и Марлина МакГрата была вручена одним из бывших студентов Льюиса в 2012 году. [18] [19]
Льюис отметил, что - во многом потому, что его карьера началась, когда область информатики «едва существовала», а Гарвард почти не предлагал курсов по информатике на уровне бакалавриата - он создал почти все курсы, которые он преподавал. [20] В конце 1970-х годов он предложил, чтобы в Гарварде была создана специальность по информатике [21] (которая до этого была ответвлением Гарвардской программы прикладной математики). [Л2]
С 2003 по 2008 год он был назначен профессором Гарвардского колледжа в знак признания «особенно выдающегося вклада в преподавание студентов». [22] В 2021 году Компьютерное общество IEEE наградило его ежегодной премией Мэри Кеннет Келлер за преподавание компьютерных наук и инженерии на бакалавриате, отметив «его более чем сорокалетнюю преданность высшему образованию в области компьютерных наук в Гарварде, его авторство вводных учебников по информатике и его наставничество многих будущих педагогов». [23]
Шесть его ассистентов [24] сейчас являются преподавателями Гарварда [20] , а многие другие являются профессорами информатики (или смежных дисциплин) в других местах; [25] многие из них сами получили преподавательские награды, в том числе Эрик Робертс ( Премия Карлстрома Ассоциации вычислительной техники ), [26] Николас Хортон ( Премия Роберта В. Хогга ), [27] Джозеф А. Констан ( Заслуженный деятель Университета Миннесоты). Профессор университетского преподавания, премия для выпускников/профессиональных преподавателей) [28] и Марго Зельцер ( профессор компьютерных наук Герчела Смита в Гарварде, преподавательская награда Phi Beta Kappa , преподавательская премия Абрамсона). [29]
Среди его студентов бакалавриата были Марк Цукерберг (чей веб-сайт «Шесть градусов до Гарри Льюиса» был предшественником Facebook – шесть степеней являются отсылкой к гипотезе маленького мира ), [Примечание 5] основатель Microsoft Билл Гейтс (который решил открытую теоретическую задачу Льюис описал в классе), [Примечание 1] и девять будущих профессоров Гарварда. [20]
Льюис является автором или соавтором пяти учебников:
Льюис также читал курс любительской легкой атлетики и социальной истории спорта в Америке. [7]
В 1994 году Льюис стал соавтором «всеобъемлющего» отчета о структуре Гарвардского колледжа , [33] [34] , а в 1995 году [22] он был назначен деканом Гарвардского колледжа, ответственным за неакадемические аспекты студенческой жизни. [35] В этом качестве он курировал ряд иногда спорных политических изменений, включая изменения в рассмотрении обвинений в сексуальном насилии, реорганизацию программ общественных услуг колледжа, подавление употребления алкоголя несовершеннолетними и случайное распределение студентов по дома для высших слоев общества (противодействие социальной сегрегации, существовавшей при прежней системе распределения в соответствии с предпочтениями учащихся). [Примечание 6] [5] [36] Он также настаивал на улучшении консультирования и здравоохранения. [5] [37] [38] Коллега сказал, что Льюис «изменил студенческую жизнь сильнее, чем кто-либо другой за последнее время». [39] Льюис продолжал преподавать на протяжении всего своего пребывания на посту декана. [22]
После инаугурации в 2001 году двадцать седьмого президента Гарвардского университета Лоуренса Саммерса Льюис и Саммерс вступили в конфликт по поводу руководства Гарвардским колледжем и его образовательной философии. [5] [40] [33] [41] Льюис, например, подчеркивал важность внеклассных занятий, советуя поступающим первокурсникам, что «гибкость в вашем расписании, неструктурированное время в течение дня и вечера, проводимые с друзьями, а не с книгами». все они в более широком смысле необходимы для вашего образования», в то время как Саммерс жаловался на недостаточно интеллектуальный «лагерь Гарвард» и предупреждал студентов, что «вы здесь, чтобы работать, а ваше дело здесь — учиться». [42] [L06] : 86–90 [L1] После того, как Льюис опубликовал то, что The Harvard Crimson назвал «резким обвинением в том, что повышение интеллектуальной строгости должно быть приоритетом [Колледжа]», указав, что потенциальные работодатели проявляют меньший интерес в оценках, чем в личных качествах, сформированных за пределами класса [40] - в марте 2003 года он был безоговорочно отстранен от должности декана. [40] [43] [38] [5]
В 2015 году Льюис занимал должность временного декана Гарвардской школы инженерии и прикладных наук . [44]
Льюис — научный сотрудник Гарвардского центра Беркмана по проблемам Интернета и общества . [45] Помимо своих исследовательских публикаций и учебников, он написал ряд работ о высшем образовании и влиянии компьютеров на общество.
В своей книге «Превосходство без души: как великий университет забыл образование» (2006) , опираясь на его опыт работы деканом Гарвардского колледжа, он критикует то, что он считает отказом американских университетов, включая Гарвард, от
Фундаментальная задача бакалавриата ... превратить восемнадцати- и девятнадцатилетних в двадцатиодно- и двадцатидвухлетних, помочь им вырасти, узнать, кто они, искать более великую цель. за свою жизнь и покинуть колледж лучшими людьми. [L06] : xii
В «Обновлении гражданской миссии американского высшего образования» (совместно с Эллен Кондлифф Лагеманн, 2012 г.) Льюис предупреждает, что «процветающее множество достойных, но нескоординированных программ вытеснило приверженность высшего образования общему благу»:
Продолжающееся ослабление гражданских интересов в американском высшем образовании вызывает тревогу и опасность ... [Колледжи] являются естественным местом для граждан, где они могут изучать ценности, выходящие за рамки их собственного личного благосостояния, и видеть себя частью общества взаимных прав и обязанностей. Это должны быть условия, в которых участие в вопросах, касающихся справедливости и добра, имеет важное значение для повседневной жизни ... Эффективное гражданское образование должно одновременно задействовать способности учащихся мыслить интеллектуально, выносить моральные суждения и [предпринимать действия в ответ на эти суждения] ... Свободные общества не будут процветать, если колледжи, аспирантуры и профессиональные школы не поймут, что гражданское здоровье нации является одной из их главных обязанностей. [ЛЛ] : 10-11
Разработанный на основе курса, читаемого его авторами, « Разнесенные на куски: ваша жизнь, свобода и счастье после цифрового взрыва» (2008 г., с Хэлом Абельсоном и Кеном Ледином) исследует истоки и последствия взрыва цифровой информации в XXI веке, в том числе его влияние на культуру и конфиденциальность:
Теперь в принципе можно запомнить все, что кто-либо говорит, пишет, поет, рисует или фотографирует. Всё ... Глобальные компьютерные сети могут сделать это доступным в любой точке мира практически мгновенно. И компьютеры достаточно мощны, чтобы извлекать смысл из всей этой информации, находить закономерности и устанавливать связи в мгновение ока.
В минувшие столетия другие могли мечтать о том, что такие вещи могут произойти, в утопических фантазиях или кошмарах. Но сейчас они происходят. [ВСЕ] : xiii
«Бейсбол как второй язык: объяснение игры, которую американцы используют, чтобы объяснить все остальное» (опубликовано в качестве эксперимента в открытом доступе в 2011 году) [46] обсуждает множество способов проникновения бейсбольных концепций и образов в американский английский. [47] Это было вдохновлено опытом Льюиса, объясняющего бейсбол иностранным студентам. [46]
Бакалаврская диссертация Льюиса, описывающая SHAPESHIFTER, «Два применения двумерного компьютерного ввода, напечатанного вручную», [L68] была написана под руководством пионера компьютерной графики Ивана Сазерленда [7] и представлена на 23-й Национальной конференции Ассоциации вычислительной техники в 1968 году. За ним последовало несколько докладов на смежные темы. [11]
Большая часть последующих исследований Льюиса касалась вычислительной сложности задач математической логики . Его докторская диссертация «Расширение и сокращение проблемы принятия решений по Эрбрану » была написана под руководством Бертона Дребена и посвящена теореме Эрбрана . [7] [48] Его книга 1979 года « Неразрешимые классы количественных формул» [L79] дополнила книгу «Проблема принятия решения: разрешимые классы количественных формул» Дребена и Уоррена Гольдфарба . [49]
В его статье 1978 года «Переименование набора предложений в набор Хорна» рассматривалась проблема булевой выполнимости , заключающаяся в определении того, может ли логическая формула в конъюнктивной нормальной форме стать истинной путем подходящего назначения ее переменных. В общем, эти проблемы сложны, но есть два основных подкласса выполнимости, для которых известны решения за полиномиальное время : 2-выполнимость (где каждое предложение формулы имеет два литерала) и выполнимость по Хорну (где каждое предложение имеет не более одного положительный литерал). Льюис расширил второй из этих подклассов, показав, что проблему все еще можно решить за полиномиальное время, когда входные данные еще не находятся в форме Хорна, но могут быть переведены в форму Хорна, заменив некоторые переменные их отрицаниями. Проблема выбора переменных, которые следует отрицать, чтобы каждое предложение получило два положительных литерала, превращая переподписанный экземпляр в множество Хорна, оказывается выражаемым как пример 2-выполнимости, другого разрешимого случая проблемы выполнимости. Решая пример с 2-выполнимостью для преобразования заданных входных данных в набор Хорна, Льюис показывает, что экземпляры, которые можно превратить в множества Хорна, также можно решить за полиномиальное время. [L78] Время смены знака в исходной версии того, что Линдхорст и Шахрохи назвали «этим элегантным результатом» [50], составляло O ( mn 2 ) для примера с m предложениями и n переменными, но его можно свести к линейному время , разбивая длинные входные предложения на более мелкие и применяя более быстрый алгоритм 2-выполнимости. [51]
Статья Льюиса «Результаты о сложности для классов количественных формул» (1980) посвящена вычислительной сложности задач логики первого порядка . Такие проблемы вообще неразрешимы , но существует несколько специальных классов этих проблем, определяемых ограничением порядка появления их кванторов, которые, как известно, разрешимы. Одним из таких специальных классов, например, является класс Бернейса–Шенфинкеля . Для каждого из этих специальных классов Льюис устанавливает жесткие экспоненциальные границы времени либо для детерминированной , либо для недетерминированной временной сложности . Например, он показывает, что класс Бернейса-Шенфинкеля является NEXPTIME -полным, а точнее, что его недетерминированная временная сложность ограничена как сверху, так и снизу одной экспоненциальной функцией входной длины. [L80] Бёргер , Гредель и Гуревич пишут, что «эта статья положила начало изучению сложности разрешимых классов проблемы решения». [52]
«Логика конкретных временных интервалов» (1990) касалась темпоральной логики . [L90] Эта статья сопровождала более ранний технический отчет вычислительной лаборатории Айкена «Анализ асинхронных схем с ограниченной временной неопределенностью в конечных состояниях», где он впервые предложил представление асинхронной схемы с ограниченной временной неопределенностью в событиях перехода затвора как конечный автомат . Эта статья была самой ранней работой по проверке свойств времени, которая моделировала время как асинхронно, так и непрерывно, без дискретизации времени и не навязывания глобальных часов. [53]
Некоторые из других часто цитируемых исследовательских работ Льюиса выходят за рамки логики. Его статья «Символическая оценка и глобальный график значений» (1977, совместно с его учеником Джоном Рейфом ) касалась анализа потока данных и символьного выполнения в компиляторах . [RL] И его статья «Симметричные вычисления, ограниченные в пространстве» (1982, с Кристосом Пападимитриу ) [LP82] была первой, кто определил симметричные машины Тьюринга и классы сложности симметричного пространства , такие как SL ( ненаправленный или обратимый аналог недетерминированной пространственной сложности, позже было показано, что оно совпадает с детерминированным логарифмическим пространством ). [54] В 1982 году он возглавлял программный комитет Симпозиума по теории вычислений , [STOC], одной из двух ведущих исследовательских конференций в области теоретической информатики , рассматриваемой в широком смысле. [55]
Льюис — посетитель Ралстон -колледжа и пожизненный попечитель латинской школы Роксбери . [56] С 1995 по 2003 год он был попечителем благотворительного фонда Эдварда Хопкинса . [7] Журналист New York Times Дэвид Фарентхольд — его зять; [57] Еще будучи студентом Гарварда, Фарентхольд писал о своем будущем тесте:
Я слышал, что если вы просидите у реки [то есть у реки Чарльз ] достаточно долго, придет декан колледжа Гарри Р. Льюис '68 и раздаст вам наборы задач по информатике, чтобы вы вернулись к работе. [58]
{{cite conference}}: CS1 maint: несколько имен: список редакторов ( ссылка )См., в частности, стр. 205.Мой отец, сын немецкого лютеранского иммигранта с одной стороны и российского еврейского иммигранта с другой, должно быть, задавался вопросом, кто именно были побежденными и спасенными людьми, с которыми он столкнулся, когда служил в армии в Европе.
Он также написал программу, которую назвал «Шесть степеней Гарри Льюиса», как дань уважения любимому профессору информатики.