Harry R. Lewis - Harry R. Lewis

Harry R. Lewis
Né	1947 (73-74 ans) Boston
Nationalité	américain
Titre	Gordon McKay Professeur d'informatique (1981-présent) Doyen du Harvard College (1995-2003) Professeur de Harvard College (2003-2008)
Conjoint(s)	Marlyn McGrath (1968-présent)
Formation universitaire
Éducation	Roxbury Latin School Université Harvard
Thèse	Extensions et réductions d'Herbrand du problème de la décision  (1974)
Conseiller de doctorat	Burton Dreben
Travail académique
La discipline	Informatique Logique mathématique
Sous-discipline	Décidabilité Théorie du calcul
Établissements	École d'ingénierie et de sciences appliquées de Harvard
Doctorants
Étudiants notables
Site Internet	http://people.seas.harvard.edu/~lewis/

Harry Roy Lewis (né en 1947) est un informaticien, mathématicien et administrateur universitaire américain connu pour ses recherches en logique informatique , ses manuels d' informatique théorique et ses écrits sur l'informatique, l'enseignement supérieur et la technologie. Il est professeur Gordon McKay d'informatique à l'Université Harvard et doyen du Harvard College de 1995 à 2003.

Lewis a été honoré pour ses « contributions particulièrement distinguées à l'enseignement de premier cycle » ; ses étudiants ont inclus les futurs entrepreneurs Bill Gates et Mark Zuckerberg , et de nombreux futurs membres du corps professoral de Harvard et d'autres écoles. Le site Web "Six Degrees to Harry Lewis", créé par Zuckerberg alors qu'il était à Harvard, était un précurseur de Facebook .

Une nouvelle chaire en ingénierie et sciences appliquées, dotée par un ancien étudiant, portera le nom de Lewis et de sa femme à leur retraite.

Éducation et carrière

Lewis démontrant son projet de thèse senior, SHAPESHIFTER, via une liaison vidéo à une classe dans une autre pièce​

Lewis est né à Boston et a grandi à Wellesley, Massa-chu-setts . Ses parents étaient médecins – son père était chef d'hôpital en anesthésiologie et sa mère directrice de la Dever State School pour enfants handicapés mentaux . Son père était un vétéran de la Seconde Guerre mondiale et le fils d'un père luthérien allemand et d'une mère juive russe . Après avoir obtenu son diplôme summa cum laude à la fin de la onzième année à la Roxbury Latin School de Boston, il entra au Harvard College, où il fut pendant un certain temps un gardien de but de crosse de troisième corde .

Lewis a déclaré qu'il avait découvert "Je n'étais pas un vrai mathématicien [une fois] sorti des ligues amateurs de mathématiques au lycée", mais était "extrêmement excité" par les opportunités de recherche en informatique à Harvard. En tant que senior, il a enseigné à une classe d'études supérieures en utilisant un programme d'infographie, SHAPESHIFTER, qu'il avait développé pour afficher des transformations de plans complexes sur un tube à rayons cathodiques . SHAPESHIFTER reconnaissait automatiquement les formules et les commandes saisies à la main via un stylet sur une tablette RAND , et pouvait être "entraîné" pour reconnaître l'écriture manuscrite des utilisateurs individuels. Il n'y avait pas de programme d'études en informatique en soi à Harvard à l'époque, en 1968 Lewis a reçu son BA ( summa , Quincy House ) en mathématiques appliquées et a été élu à Phi Beta Kappa .

Après deux ans en tant que mathématicien et informaticien pour les National Institutes of Health à Bethesda, Maryland , il a passé un an en Europe en tant que Frederick Sheldon Travelling Fellow . Il est ensuite retourné à Harvard, où il a obtenu sa maîtrise en 1973 et son doctorat en 1974, après quoi il a été immédiatement nommé professeur adjoint d'informatique. Il est devenu professeur agrégé en 1978 et est professeur Gordon McKay d'informatique depuis 1981.

Lewis prévoit de prendre sa retraite en 2020, date à laquelle une nouvelle chaire d'ingénierie et de sciences appliquées, dotée par l'ancien étudiant Larry Lebowitz, sera nommée en l'honneur de Lewis et de son épouse Marlyn McGrath, directrice des admissions à Harvard.

Enseignement

Enseignement en 2012

Lewis a souligné que - en grande partie parce que sa carrière a commencé lorsque le domaine de l'informatique " existait à peine " et que Harvard n'offrait presque aucun cours d'informatique au niveau du premier cycle - il est à l'origine de presque tous les cours qu'il a enseignés. C'était sa proposition, à la fin des années 1970, que Harvard crée une majeure spécifiquement pour l'informatique (qui jusqu'alors était une branche du programme de mathématiques appliquées de Harvard).

De 2003 à 2008, il a été nommé professeur au Harvard College en reconnaissance de « contributions particulièrement distinguées à l'enseignement de premier cycle ». Six de ses assistants d'enseignement sont maintenant membres de la faculté de Harvard et beaucoup d'autres sont professeurs d'informatique (ou de disciplines connexes) ailleurs ; beaucoup ont eux-mêmes remporté des prix d'enseignement, notamment Eric Roberts (prix de l' Association for Computing Machinery Karlstrom), Nicholas Horton (prix Robert V. Hogg ), Joseph A. Konstan ( professeur émérite d'enseignement universitaire de l'Université du Minnesota, prix d'enseignement supérieur/professionnel ) et Margo Seltzer ( professeur Herchel Smith d'informatique à Harvard, prix d'enseignement Phi Beta Kappa , prix d'enseignement Abramson).

Parmi ses étudiants de premier cycle figuraient Mark Zuckerberg (dont le site Web "Six Degrees to Harry Lewis" était un précurseur de Facebook  - six degrés étant une référence à l' hypothèse du petit monde ), le fondateur de Microsoft Bill Gates (qui a résolu un problème théorique ouvert que Lewis avait décrit dans classe) et neuf futurs professeurs de Harvard.

Lewis est l'auteur ou le coauteur de trois manuels de premier cycle :

• Une introduction à la programmation informatique et aux structures de données à l'aide de MACRO-11 (1981). MACRO-11 était un langage d'assemblage pour les ordinateurs PDP-11 .
• Les éléments de la théorie de calcul (1981, avec Christos H. Papadimitriou ) couvre la théorie des automates , théorie de la complexité de calcul , et la théorie des langues officielles ; son inclusion de la théorie de la complexité et de la logique mathématique était innovante pour l'époque. On l'a qualifié d'« excellent texte traditionnel », mais dont le style laconique et fortement mathématique peut être intimidant. Bien que destiné aux étudiants de premier cycle, il a également été utilisé pour les cours d'introduction aux cycles supérieurs.
• Structures de données et leurs algorithmes (1991, avec Larry Denenberg).

Lewis enseigne également un cours sur l'athlétisme amateur et l'histoire sociale du sport en Amérique.

Doyen du Harvard College

Le jour d'Halloween 1982, les assistants d'enseignement de Lewis sont apparus chez lui dans le costume de "Harry Lewis", y compris sa moustache et sa pipe de marque de l'époque. La future professeure de Harvard Margo Seltzer est à gauche.

En 1994, Lewis a co-écrit le rapport "complet" sur la structure du Harvard College et en 1995, il a été nommé doyen du Harvard College, responsable des aspects non académiques de la vie de premier cycle. À ce titre, il a supervisé un certain nombre de changements de politique parfois controversés, notamment des changements dans le traitement des allégations d'agression sexuelle, la réorganisation des programmes de la fonction publique du collège, la répression de la consommation d'alcool chez les mineurs et l'affectation aléatoire d'étudiants dans des maisons de la classe supérieure ( contrer la ségrégation sociale constatée sous le système antérieur d'affectation selon la préférence des étudiants). Il a également insisté sur l'amélioration des conseils et des soins de santé. Un collègue a déclaré que Lewis "a remodelé la vie de premier cycle plus puissamment que quiconque dans la mémoire récente".

Après l'investiture en 2001 du vingt-septième président de l'Université Harvard , Lawrence Summers , Lewis et Summers sont entrés en conflit au sujet de la direction du Harvard College et de sa philosophie éducative. Lewis, par exemple, a souligné l'importance des activités parascolaires, informant les étudiants de première année entrants que « la flexibilité dans votre horaire, le temps non structuré de votre journée et les soirées passées avec vos amis plutôt que vos livres sont tous, dans un sens plus large, essentiels pour votre éducation. ", tandis que Summers se plaignait d'un " Camp Harvard " insuffisamment intellectuel et réprimandait les étudiants que " Vous êtes ici pour travailler, et votre affaire ici est d'apprendre ". Après que Lewis a publié ce que The Harvard Crimson a appelé "un acte d'accusation cinglant de l'opinion selon laquelle l'augmentation de la rigueur intellectuelle devrait être la priorité [du Collège]" - soulignant que les employeurs potentiels montrent moins d'intérêt pour les notes que pour les qualités personnelles construites en dehors de la salle de classe - il a été destitué péremptoirement de son poste de doyen en mars 2003.

Lewis a continué à enseigner tout au long de son mandat de doyen. En 2015, il a été doyen par intérim de la Harvard School of Engineering and Applied Sciences .

Écrits sur l'éducation et la technologie

Lewis est membre du corps professoral du Berkman Center for Internet & Society de Harvard . En plus de ses publications de recherche et de ses manuels, il a écrit un certain nombre d'ouvrages sur l'enseignement supérieur et l'impact des ordinateurs sur la société.

S'inspirant largement de son expérience en tant que doyen du Harvard College, son ouvrage Excellence Without A Soul: How a Great University Forgot Education (2006) critique ce qu'il considère comme l'abandon par les universités américaines, dont Harvard, de la

travail fondamental de l' enseignement de premier cycle  ... transformer des jeunes de dix-huit et dix-neuf ans en jeunes de 21 et 22 ans, les aider à grandir, apprendre qui ils sont, rechercher un objectif plus large pour leur vie et de quitter l'université en tant qu'êtres humains meilleurs.

Dans « Renewing the Civic Mission of American Higher Education » (avec Ellen Condliffe Lagemann, 2012), Lewis avertit qu'« une multiplicité florissante d'agendas dignes mais non coordonnés a évincé l'engagement de l'enseignement supérieur pour le bien commun » :

L'érosion continue des préoccupations civiques au sein de l'enseignement supérieur américain est alarmante et dangereuse  ... [Les collèges] sont un lieu naturel pour les citoyens d'apprendre des valeurs au-delà de leur propre bien-être personnel, de se considérer comme faisant partie d'une société de droits et de responsabilités mutuels. Ils devraient être des cadres dans lesquels l'engagement avec des questions concernant la justice et la bonté est essentiel aux routines quotidiennes  ... Une éducation civique efficace doit simultanément impliquer les capacités des élèves à penser intellectuellement, à porter des jugements moraux et à [prendre des mesures en réponse à ces jugements]  … Les sociétés libres ne prospéreront que si les collèges, les écoles supérieures et les écoles professionnelles comprennent que la santé civique de la nation est l'une de leurs responsabilités centrales.

Développé à partir d'un cours enseigné par ses auteurs, Blown to Bits: Your Life, Liberty, and Happiness After the Digital Explosion (2008, avec Hal Abelson et Ken Ledeen ) explore les origines et les conséquences de l'explosion de l'information numérique au 21e siècle, notamment son impact sur la culture et la vie privée :

Il est désormais possible, en principe, de se souvenir de tout ce que quelqu'un dit, écrit, chante, dessine ou photographie. Tout  ... Les réseaux informatiques mondiaux peuvent le rendre disponible partout dans le monde, presque instantanément. Et les ordinateurs sont suffisamment puissants pour extraire un sens de toutes ces informations, pour trouver des modèles et établir des connexions en un clin d'œil.

Au cours des siècles passés, d'autres ont peut-être rêvé que ces choses pouvaient arriver, dans des fantasmes utopiques ou dans des cauchemars. Mais maintenant, ils se produisent.

Baseball as a Second Language: Explaining the Game Americans Use to Explain Everything Else (auto-publié en tant qu'expérience en libre accès en 2011) traite des nombreuses façons dont les concepts et l'imagerie du baseball ont fait leur chemin dans l'anglais américain. Il a été inspiré par les expériences de Lewis expliquant le baseball aux étudiants internationaux.

Recherche

Lewis dans son bureau (2016)

La thèse de premier cycle de Lewis décrivant SHAPESHIFTER, "Deux applications de l'entrée informatique bidimensionnelle imprimée à la main", a été rédigée par le pionnier de l' infographie Ivan Sutherland et présentée à la 23e Conférence nationale de l' Association for Computing Machinery en 1968. Elle a été suivie par plusieurs articles sur des sujets connexes.

Une grande partie des recherches ultérieures de Lewis concernaient la complexité informatique des problèmes de logique mathématique . Sa thèse de doctorat, "Herbrand Expansions and Reductions of the Decision Problem ", a été dirigée par Burton Dreben et portait sur le théorème de Herbrand . Son livre de 1979, Unsolvable classes of quantificational formulas a complété The Decision Problem: Solvable classes of quantificational formula par Dreben et Warren Goldfarb .

Son article de 1978 "Renommer un ensemble de clauses en ensemble de Horn" a abordé le problème de satisfiabilité booléenne, consistant à déterminer si une formule logique sous forme normale conjonctive peut être rendue vraie par une affectation appropriée de ses variables. En général, ces problèmes sont difficiles, mais il existe deux sous-classes principales de satisfiabilité pour lesquelles des solutions en temps polynomial sont connues : la 2-satisfiabilité (où chaque clause de la formule a deux littéraux) et la satisfiabilité Horn (où chaque clause a au plus un littéral positif). Lewis a développé la seconde de ces sous-classes, en montrant que le problème peut encore être résolu en temps polynomial lorsque l'entrée n'est pas déjà sous forme Horn, mais peut être mis sous forme Horn en remplaçant certaines variables par leurs négations. Le problème du choix des variables à nier pour que chaque clause obtienne deux littéraux positifs, transformant l'instance re-signée en un ensemble de Horn, s'avère être exprimable comme une instance de 2-satisfiabilité, l'autre cas résoluble du problème de satisfiabilité. En résolvant une instance de 2-satisfiabilité pour transformer l'entrée donnée en un ensemble de Horn, Lewis montre que les instances qui peuvent être transformées en ensembles de Horn peuvent également être résolues en temps polynomial. Le temps pour la réaffectation des signes dans la version originale de ce que Lindhorst et Shahrokhi appelaient "ce résultat élégant" était O  ( mn ² ) pour une instance avec m clauses et n variables, mais il peut être réduit à un temps linéaire en cassant de longues clauses d'entrée en clauses plus petites et en appliquant un algorithme de 2-satisfiabilité plus rapide.

L'article de Lewis "Complexity results for classes of quantificational formulas" (1980) traite de la complexité computationnelle des problèmes en logique du premier ordre . De tels problèmes sont indécidables en général, mais il existe plusieurs classes spéciales de ces problèmes, définies en restreignant l'ordre dans lequel leurs quantificateurs apparaissent, qui étaient connues pour être décidables. L'une de ces classes spéciales, par exemple, est la classe Bernays-Schönfinkel . Pour chacune de ces classes spéciales, Lewis établit des limites temporelles exponentielles serrées pour la complexité temporelle déterministe ou non déterministe . Par exemple, il montre que la classe Bernays-Schönfinkel est NEXPTIME -complète, et plus précisément que sa complexité temporelle non déterministe est à la fois supérieure et inférieure par une fonction exponentielle unique de la longueur d'entrée. Börger , Grädel et Gurevich écrivent que « cet article a initié l'étude de la complexité des classes décidables du problème de décision ».

« Une logique d'intervalles de temps concrets » (1990) concernait la logique temporelle . Cet article accompagnait un rapport technique antérieur du laboratoire de calcul d'Aiken, "Analyse à l'état fini des circuits asynchrones avec incertitude temporelle bornée", où il proposait pour la première fois la représentation d'un circuit asynchrone , avec une incertitude temporelle bornée sur les événements de transition de porte, en tant qu'état fini machine . Cet article était le premier travail sur la vérification des propriétés temporelles qui modélisait le temps de manière asynchrone et continue, sans discrétiser le temps ni imposer une horloge globale.

Certains des autres articles de recherche largement cités de Lewis vont au-delà de la logique. Son article "Symbolic evaluation and the global value graph" (1977, avec son élève John Reif ) concernait l'analyse des flux de données et l'exécution symbolique dans les compilateurs . Et son article "Symetric space-bounded computing" (1982, avec Christos Papadimitriou ) a été le premier à définir des machines de Turing symétriques et des classes de complexité spatiale symétrique telles que SL (un analogue non orienté ou réversible de la complexité spatiale non déterministe , dont il a été démontré plus tard qu'elle coïncide avec la complexité déterministe). espace logarithmique ). En 1982, il a présidé le comité de programme du Symposium on Theory of Computing , l'une des deux conférences de recherche les plus importantes en informatique théorique , considérée au sens large.

Personnel

Lewis est un visiteur du Ralston College et un administrateur à vie de la Roxbury Latin School . De 1995 à 2003, il a été administrateur de la Charity of Edward Hopkins . Le journaliste du Washington Post , David Fahrenthold, est son gendre ; alors qu'il était encore étudiant à Harvard, Fahrenthold a écrit à propos de son futur beau-père :

J'ai entendu dire que si vous vous asseyez au bord de la rivière [c'est-à-dire la rivière Charles ] assez longtemps, le doyen du Collège Harry R. Lewis '68 arrive et distribue des ensembles de problèmes informatiques afin que vous puissiez vous remettre au travail.

Remarques

Publications sélectionnées

Les références

Liens externes

• Le blog de "Bits and Pieces" Lewis
• "Blown to Bits" Ancien blog de Lewis