Гарри Рой Льюис (родился в 1947 году) — американский компьютерный ученый, математик и администратор университета, известный своими исследованиями в области вычислительной логики , учебниками по теоретической информатике и работами по вычислительной технике, высшему образованию и технологиям. Он является профессором-исследователем компьютерных наук имени Гордона Маккея в Гарвардском университете и был деканом Гарвардского колледжа с 1995 по 2003 год.
По сути, вся карьера Льюиса прошла в Гарварде, где его чествовали за «особо выдающийся вклад в преподавание в бакалавриате»; среди его студентов были будущие предприниматели Билл Гейтс и Марк Цукерберг , а также многочисленные будущие преподаватели Гарварда и других школ. Сайт «Six Degrees to Harry Lewis», созданный Цукербергом во время учебы в Гарварде, был предшественником Facebook .
Льюис родился в Бостоне [7] и вырос в Уэллсли, штат Массачусетс. [ 8 ] Его родители были врачами — его отец был заведующим отделением анестезиологии , а его мать была главой школы Dever State School для детей с ограниченными интеллектуальными 9 ] Его отец был ветераном Второй мировой войны и сыном немецкого лютеранина и русской еврейской матери . [10] После окончания с отличием одиннадцатого класса в Бостонской латинской школе Roxbury он поступил в Гарвардский колледж, где некоторое время был вратарем по лакроссу . [8 ]
Льюис сказал, что он обнаружил, что «я не был настоящим математиком [как только] я вышел из любительской лиги математики в старшей школе», но был «чрезвычайно взволнован» возможностями исследований в области компьютерных наук в Гарварде. [L2] Будучи выпускником, он читал лекции выпускникам, используя программу компьютерной графики SHAPESHIFTER, которую он разработал для отображения преобразований комплексной плоскости на электронно-лучевой трубке . SHAPESHIFTER автоматически распознавал формулы и команды, введенные вручную с помощью стилуса на планшете RAND , и мог быть «обучен» распознавать почерк отдельных пользователей. [6] [11] Поскольку в то время в Гарварде не было программы получения степени по компьютерным наукам как таковой , [L2] в 1968 году Льюис получил степень бакалавра ( summa , Quincy House ) по прикладной математике [5] [12] и был избран в Phi Beta Kappa . [13]
После двух лет службы в Корпусе уполномоченных по здравоохранению США в качестве уполномоченного в роли математика и специалиста по информатике для Национальных институтов здравоохранения в Бетесде, штат Мэриленд , он провел год в Европе в качестве стипендиата Фредерика Шелдона. Затем он вернулся в Гарвард, где получил степень магистра в 1973 году и степень доктора философии в 1974 году, после чего был немедленно назначен доцентом кафедры компьютерных наук. Он стал доцентом в 1978 году и профессором кафедры компьютерных наук имени Гордона Маккея в 1981 году. [7]
Льюис официально вышел на пенсию в 2020 году, [14] [15] но продолжает преподавать в качестве профессора-исследователя Гордона Маккея в области компьютерных наук. [16] Его жена Марлин Макграт вышла на пенсию в 2021 году после 42 лет работы директором по приему в Гарвардском колледже. [17] Профессорская должность Гарри Льюиса и Марлин Макграт по инженерным и прикладным наукам была учреждена одним из бывших студентов Льюиса в 2012 году. [18] [19]
Льюис отметил, что — в основном потому, что его карьера началась, когда область компьютерных наук «едва существовала», и Гарвард почти не предлагал курсов по компьютерным наукам на уровне бакалавриата — он создал почти все курсы, которые он преподавал. [20] Именно он предложил в конце 1970-х годов, чтобы Гарвард создал специальность по компьютерным наукам [21] (которая до того была ответвлением программы Гарварда по прикладной математике). [L2]
С 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 г.) Льюис предупреждает, что «процветающее множество достойных, но нескоординированных программ вытеснило приверженность высшего образования общему благу»:
Продолжающееся размывание гражданских интересов в американском высшем образовании вызывает тревогу и является опасным ... [Колледжи] являются естественным местом для граждан, чтобы узнать ценности, выходящие за рамки их личного благополучия, чтобы увидеть себя частью общества взаимных прав и обязанностей. Они должны быть средой, в которой участие в вопросах, касающихся справедливости и добра, является неотъемлемой частью повседневной жизни ... Эффективное гражданское образование должно одновременно включать способности студентов мыслить интеллектуально, выносить моральные суждения и [принять меры в ответ на эти суждения] ... Свободные общества не будут процветать, если колледжи, аспирантуры и профессиональные школы не поймут, что гражданское здоровье нации является одной из их основных обязанностей. [LL] : 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] Эта статья сопровождала более ранний технический отчет Aiken Computation Laboratory "Анализ конечных состояний асинхронных цепей с ограниченной временной неопределенностью", где он впервые предложил представление асинхронной цепи с ограниченной временной неопределенностью в событиях перехода вентилей в виде конечного автомата . Эта статья была самой ранней работой по проверке свойств синхронизации, которая моделировала время как асинхронно, так и непрерывно, не дискретизируя время и не навязывая глобальные часы. [53]
Некоторые из других часто цитируемых исследовательских работ Льюиса выходят за рамки логики. Его статья «Символическая оценка и глобальный граф значений» (1977, совместно со своим студентом Джоном Рейфом ) касалась анализа потока данных и символического выполнения в компиляторах . [RL] А его статья «Симметричные вычисления с ограничением пространства» (1982, совместно с Христосом Пападимитриу ) [LP82] была первой, в которой были определены симметричные машины Тьюринга и симметричные классы сложности пространства , такие как SL ( ненаправленный или обратимый аналог недетерминированной сложности пространства , который, как позже было показано, совпадает с детерминированным логарифмическим пространством ). [54] В 1982 году он возглавлял программный комитет Симпозиума по теории вычислений [STOC] одной из двух ведущих исследовательских конференций в области теоретической информатики , рассматриваемой в широком смысле. [55]
Льюис является гостем колледжа Ралстон и пожизненным попечителем латинской школы Роксбери . [56] С 1995 по 2003 год он был попечителем благотворительного фонда Эдварда Хопкинса . [7] Журналист New York Times Дэвид Фарентольд является его зятем; [57] еще будучи студентом Гарварда, Фарентольд писал о своем будущем тесте:
Я слышал, что если вы достаточно долго сидите у реки [т. е. у реки Чарльз ], то декан колледжа Гарри Р. Льюис 1968 года рождения придет и раздаст вам наборы задач по информатике, чтобы вы вернулись к работе. [58]
Мой отец, сын немецкого лютеранского иммигранта с одной стороны и русского еврейского иммигранта с другой, должно быть, задавался вопросом, кем именно были побежденные и спасенные люди, с которыми он столкнулся, когда служил в армии в Европе.
Он также написал программу, которую назвал «Шесть степеней Гарри Льюиса», в память о любимом профессоре компьютерных наук.
{{cite book}}: CS1 maint: DOI неактивен по состоянию на август 2024 г. ( ссылка )