Harry R. Lewis - Harry R. Lewis

Harry R. Lewis
Harry Lewis em Harvard Student Meeting 2002 cropped.jpg
Nascer 1947 (idade 73-74)
Boston
Nacionalidade americano
Título Gordon McKay Professor de Ciência da Computação (1981 - presente)
Reitor do Harvard College (1995–2003)
Professor do Harvard College (2003–2008)
Cônjuge (s) Marlyn McGrath (1968 até o presente)
Formação acadêmica
Educação Roxbury Latin School
Harvard University
Tese Expansões e reduções de Herbrand do problema de decisão  (1974)
Orientador de doutorado Burton Dreben
Trabalho acadêmico
Disciplina Ciência da computação
Lógica matemática
Subdisciplina Teoria da Decidibilidade
da Computação
Instituições Escola Harvard de Engenharia e Ciências Aplicadas
Alunos de doutorado
Alunos notáveis
Local na rede Internet http://people.seas.harvard.edu/~lewis/

Harry Roy Lewis (nascido em 1947) é um cientista da computação, matemático e administrador universitário americano conhecido por sua pesquisa em lógica computacional , livros de ciência da computação teórica e escritos sobre computação, ensino superior e tecnologia. Ele é Gordon McKay Professor de Ciência da Computação na Harvard University e foi Reitor do Harvard College de 1995 a 2003.

Lewis foi homenageado por suas "contribuições particularmente ilustres para o ensino de graduação"; entre seus alunos estão os futuros empresários Bill Gates e Mark Zuckerberg , e vários futuros membros do corpo docente em Harvard e outras escolas. O site "Six Degrees to Harry Lewis", criado por Zuckerberg enquanto estava em Harvard, foi um precursor do Facebook .

Uma nova cátedra em Engenharia e Ciências Aplicadas, concedida por um ex-aluno, será nomeada em homenagem a Lewis e sua esposa após a aposentadoria.

Educação e carreira

Um jovem está sentado segurando um microfone com a mão esquerda enquanto manipula o console de um aparelho com a direita.  À sua esquerda, uma grande câmera de televisão é apontada para um grande display circular de tubo de raios catódicos.
Lewis demonstrando seu projeto de tese sênior, SHAPESHIFTER, via link de vídeo para uma classe em outra sala

Lewis nasceu em Boston e cresceu em Wellesley, Massa-chu-setts . Seus pais eram médicos - seu pai, chefe de anestesiologia de um hospital, e sua mãe, chefe da Escola Estadual Dever para crianças com deficiência intelectual . Seu pai era um veterano da Segunda Guerra Mundial e filho de pai luterano alemão e mãe judia russa . Depois de se formar summa cum laude no final da décima primeira série na Roxbury Latin School de Boston, ele entrou na Harvard College, onde foi por um tempo goleiro de lacrosse da terceira série .

Lewis disse que descobriu "Eu não era um matemático de verdade [uma vez] que saí das ligas amadoras da matemática do ensino médio", mas estava "tremendamente animado" com as oportunidades de pesquisa em ciência da computação em Harvard. Quando estava no último ano, ele deu uma aula de pós-graduação usando um programa de computação gráfica, SHAPESHIFTER, que ele desenvolveu para exibir transformações de planos complexos em um tubo de raios catódicos . O SHAPESHIFTER reconhecia automaticamente fórmulas e comandos inseridos manualmente por meio de uma caneta em um tablet RAND e poderia ser "treinado" para reconhecer a escrita à mão de usuários individuais. Não havendo nenhum programa de graduação em ciência da computação per se em Harvard na época, em 1968 Lewis recebeu seu BA ( summa , Quincy House ) em matemática aplicada e foi eleito Phi Beta Kappa .

Após dois anos como matemático e cientista da computação para o National Institutes of Health em Bethesda, Maryland , ele passou um ano na Europa como Frederick Sheldon Traveller Fellow . Ele então voltou para Harvard, onde obteve seu MA em 1973 e PhD em 1974, após o qual foi imediatamente nomeado Professor Assistente de Ciência da Computação. Ele se tornou professor associado em 1978 e é professor de ciência da computação Gordon McKay desde 1981.

Lewis planeja se aposentar em 2020, quando uma nova cátedra em Engenharia e Ciências Aplicadas, do ex-aluno Larry Lebowitz, será nomeada em homenagem a Lewis e por sua esposa Marlyn McGrath, que é a diretora de admissões de Harvard.

Ensino

Ensino em 2012

Lewis apontou que - em grande parte porque sua carreira começou quando o campo da ciência da computação "mal existia" e Harvard quase não oferecia cursos de ciência da computação no nível de graduação - ele originou quase todos os cursos que ministrou. Foi sua proposta, no final dos anos 1970, que Harvard criasse uma especialização especificamente para ciência da computação (que até então tinha sido um ramo do programa de matemática aplicada de Harvard).

De 2003 a 2008, ele foi designado Professor do Harvard College em reconhecimento a "contribuições particularmente ilustres para o ensino de graduação". Seis de seus professores assistentes são agora membros do corpo docente de Harvard e muitos outros são professores de ciência da computação (ou disciplinas relacionadas) em outros lugares; muitos já ganharam prêmios de ensino, incluindo Eric Roberts ( Prêmio Karlstrom da Association for Computing Machinery ), Nicholas Horton ( Prêmio Robert V. Hogg ), Joseph A. Konstan ( Distinguido Professor de Ensino da Universidade de Minnesota, Prêmio de Graduação / Ensino Profissional ), e Margo Seltzer ( Herchel Smith Professor de Ciência da Computação em Harvard, prêmio de ensino Phi Beta Kappa , Prêmio de Ensino Abramson).

Seus alunos de graduação incluíram Mark Zuckerberg (cujo site "Six Degrees to Harry Lewis" foi um precursor do Facebook  - seis graus sendo uma referência à hipótese do mundo pequeno ), o fundador da Microsoft Bill Gates (que resolveu um problema teórico aberto que Lewis havia descrito em turma) e nove futuros professores de Harvard.

Lewis é o autor ou co-autor de três livros didáticos de graduação:

Lewis também ministra um curso sobre atletismo amador e história social dos esportes na América.

Reitor do Harvard College

No Halloween de 1982, os professores assistentes de Lewis apareceram em sua casa com o traje de "Harry Lewis", incluindo seu bigode e cachimbo, sua marca registrada na época. A futura professora de Harvard, Margo Seltzer, está à esquerda.

Em 1994, Lewis foi co-autor do Relatório "abrangente" sobre a estrutura do Harvard College e, em 1995, foi nomeado reitor do Harvard College, responsável pelos aspectos não acadêmicos da vida universitária. Nessa função, ele supervisionou uma série de mudanças de política às vezes controversas, incluindo mudanças no tratamento de alegações de agressão sexual, reorganização dos programas de serviço público da faculdade, repressão ao uso de álcool por menores de idade e atribuição aleatória de alunos a casas de classe alta ( combater a segregação social encontrada no sistema anterior de atribuição de acordo com a preferência do aluno). Ele também pressionou melhorias para aconselhamento e cuidados de saúde. Um colega disse que Lewis "reformulou a vida universitária de maneira mais poderosa do que qualquer outra pessoa na memória recente".

Após a posse do vigésimo sétimo presidente da Universidade de Harvard em 2001 , Lawrence Summers , Lewis e Summers entraram em conflito sobre a direção do Harvard College e sua filosofia educacional. Lewis, por exemplo, enfatizou a importância das atividades extracurriculares, aconselhando os calouros que "flexibilidade em sua programação, tempo não estruturado em seu dia e noites passadas com seus amigos em vez de seus livros são, em um sentido mais amplo, essenciais para sua educação ", enquanto Summers reclamava de um" Camp Harvard "insuficientemente intelectual e advertia os alunos de que" Vocês estão aqui para trabalhar e seu negócio aqui é aprender ". Depois que Lewis publicou o que The Harvard Crimson chamou de "uma crítica contundente da visão de que o aumento do rigor intelectual deve ser a prioridade [da faculdade]" - apontando que os empregadores em potencial mostram menos interesse nas notas do que nas qualidades pessoais construídas fora da sala de aula - ele foi removido peremptoriamente como reitor em março de 2003.

Lewis continuou a ensinar durante todo o seu tempo como reitor. Em 2015, ele atuou como Reitor interino da Escola de Engenharia e Ciências Aplicadas de Harvard .

Escritos sobre educação e tecnologia

Lewis é professor associado do Berkman Center for Internet & Society de Harvard . Além de suas publicações de pesquisa e livros didáticos, ele escreveu uma série de trabalhos sobre o ensino superior e o impacto dos computadores na sociedade.

Baseando-se fortemente em sua experiência como reitor do Harvard College, seu Excellence Without A Soul: How a Great University Forgot Education (2006) critica o que ele vê como o abandono pelas universidades americanas, incluindo Harvard, do

trabalho fundamental do ensino de graduação  ... transformar jovens de dezoito e dezenove em vinte e um e vinte e dois anos, ajudá-los a crescer, a aprender quem são, a buscar um propósito maior por suas vidas, e para deixar a faculdade como seres humanos melhores.

Em "Renovando a Missão Cívica da Educação Superior Americana" (com Ellen Condliffe Lagemann, 2012) Lewis avisa que "uma multiplicidade florescente de agendas dignas, mas descoordenadas, excluiu o compromisso do ensino superior com o bem comum":

A contínua erosão das preocupações cívicas dentro da educação superior americana é alarmante e perigosa  ... [As faculdades] são um lugar natural para os cidadãos aprenderem valores além de seu próprio bem-estar pessoal, para se verem como parte de uma sociedade de direitos e responsabilidades mútuos. Devem ser ambientes nos quais o envolvimento com questões relativas à justiça e à bondade seja essencial para as rotinas diárias  ... A educação cívica eficaz deve envolver simultaneamente as capacidades dos alunos de pensar intelectualmente, de fazer julgamentos morais e de [agir em resposta a esses julgamentos]  ... As sociedades livres não prosperarão a menos que as faculdades, escolas de pós-graduação e escolas profissionais compreendam que a saúde cívica da nação é uma de suas responsabilidades centrais.

Desenvolvido a partir de um curso ministrado por seus autores, Blown to Bits: Your Life, Liberty, and Happiness After the Digital Explosion (2008, com Hal Abelson e Ken Ledeen ) explora as origens e consequências da explosão do século 21 em informação digital, incluindo seu impacto na cultura e na privacidade:

Agora é possível, em princípio, lembrar tudo o que alguém diz, escreve, canta, desenha ou fotografa. Tudo  ... As redes globais de computadores podem disponibilizá-lo para qualquer lugar do mundo, quase que instantaneamente. E os computadores são poderosos o suficiente para extrair significado de todas essas informações, para encontrar padrões e fazer conexões em um piscar de olhos.

Nos séculos passados, outros podem ter sonhado que essas coisas poderiam acontecer, em fantasias utópicas ou em pesadelos. Mas agora eles estão acontecendo.

Beisebol como uma segunda língua: explicando o jogo que os americanos usam para explicar tudo mais (publicado pela própria empresa como um experimento em acesso aberto em 2011) discute as muitas maneiras pelas quais os conceitos e imagens do beisebol chegaram ao inglês americano. Foi inspirado nas experiências de Lewis explicando o beisebol para estudantes internacionais.

Pesquisar

Lewis em seu escritório (2016)

A tese de graduação de Lewis descrevendo SHAPESHIFTER, "Duas aplicações de entrada de computador bidimensional impressa à mão", foi escrita pelo pioneiro da computação gráfica Ivan Sutherland e apresentada na 23ª Conferência Nacional da Association for Computing Machinery em 1968. Foi seguida por vários artigos sobre tópicos relacionados.

Grande parte da pesquisa subsequente de Lewis preocupou-se com a complexidade computacional de problemas em lógica matemática . Sua tese de doutorado, "Expansões e reduções de Herbrand do problema de decisão ", foi supervisionada por Burton Dreben e lidou com o teorema de Herbrand . Seu livro de 1979, Unsolvable classes of quantificational formulas complementou The Decision Problem: Solvable classes of quantificational formula de Dreben e Warren Goldfarb .

Seu artigo de 1978 "Renomeando um conjunto de cláusulas como um conjunto de Horn" abordou o problema de satisfatibilidade booleana , de determinar se uma fórmula lógica na forma normal conjuntiva pode ser tornada verdadeira por uma atribuição adequada de suas variáveis. Em geral, esses problemas são difíceis, mas existem duas subclasses principais de satisfatibilidade para as quais as soluções de tempo polinomial são conhecidas: 2-satisfatibilidade (onde cada cláusula da fórmula tem dois literais) e Horn-satisfatibilidade (onde cada cláusula tem no máximo um literal positivo). Lewis expandiu a segunda dessas subclasses, mostrando que o problema ainda pode ser resolvido em tempo polinomial quando a entrada ainda não está na forma de Horn, mas pode ser colocada na forma de Horn substituindo algumas variáveis ​​por suas negações. O problema de escolher quais variáveis ​​negar para fazer cada cláusula obter dois literais positivos, tornando a instância reassinada em um conjunto de Horn, acaba sendo expressável como uma instância de 2-satisfatibilidade, o outro caso solucionável do problema de satisfatibilidade. Resolvendo uma instância de 2-satisfatibilidade para transformar a entrada fornecida em um conjunto de Horn, Lewis mostra que as instâncias que podem ser transformadas em conjuntos de Horn também podem ser resolvidas em tempo polinomial. O tempo para a mudança de sinal na versão original do que Lindhorst e Shahrokhi chamado "este resultado elegante" foi O  ( mn 2 ) para uma instância com m cláusulas e n variáveis, mas pode ser reduzida para o tempo linear por quebrar cláusulas de entrada longos em cláusulas menores e aplicando um algoritmo de 2-satisfatibilidade mais rápido.

O artigo de Lewis "Resultados da complexidade para classes de fórmulas quantificacionais" (1980) trata da complexidade computacional de problemas na lógica de primeira ordem . Tais problemas são indecidíveis em geral, mas existem várias classes especiais desses problemas, definidas pela restrição da ordem em que seus quantificadores aparecem, que eram sabidamente decidíveis. Uma dessas classes especiais, por exemplo, é a classe Bernays – Schönfinkel . Para cada uma dessas classes especiais, Lewis estabelece limites de tempo exponenciais estreitos para complexidade de tempo determinística ou não-determinística . Por exemplo, ele mostra que a classe Bernays-Schönfinkel é NEXPTIME -completa, e mais especificamente que sua complexidade de tempo não determinística é limitada tanto superior quanto inferior por uma função exponencial única do comprimento de entrada. Börger , Grädel e Gurevich escrevem que "este artigo iniciou o estudo da complexidade das classes decidíveis do problema de decisão".

"Uma lógica de intervalos de tempo concretos" (1990) dizia respeito à lógica temporal . Este artigo acompanhou um relatório técnico anterior do Laboratório de Computação Aiken, "Análise de estado finito de circuitos assíncronos com incerteza temporal limitada", onde ele propôs pela primeira vez a representação de um circuito assíncrono , com incerteza temporal limitada em eventos de transição de porta, como um estado finito máquina . Este artigo foi o primeiro trabalho na verificação de propriedades de tempo que modelam o tempo tanto de forma assíncrona quanto contínua, sem discretizar o tempo nem impor um relógio global.

Alguns dos outros artigos de pesquisa fortemente citados de Lewis vão além da lógica. Seu artigo "Avaliação simbólica e o gráfico de valor global" (1977, com seu aluno John Reif ) tratava da análise do fluxo de dados e da execução simbólica em compiladores . E seu artigo "Symmetric space-bounded computation" (1982, com Christos Papadimitriou ) foi o primeiro a definir máquinas de Turing simétricas e classes de complexidade de espaço simétrica , como SL (um análogo não direcionado ou reversível da complexidade do espaço não determinístico , mais tarde mostrado para coincidir com o determinístico espaço logarítmico ). Em 1982, ele presidiu o comitê de programa do Simpósio de Teoria da Computação , uma das duas principais conferências de pesquisa em ciência da computação teórica , considerada de forma ampla.

Pessoal

Lewis é visitante do Ralston College e curador vitalício da Roxbury Latin School . De 1995 a 2003, ele foi Curador da Caridade de Edward Hopkins . O jornalista do Washington Post David Fahrenthold é seu genro; quando ainda era estudante de Harvard, Fahrenthold escreveu sobre seu futuro sogro:

Ouvi dizer que, se você ficar sentado à beira do rio [ou seja, o Charles River ], por tempo suficiente, o Reitor do College Harry R. Lewis '68 chega e distribui conjuntos de problemas de ciência da computação para que você volte ao trabalho.

Notas

Publicações selecionadas

Pesquisa em ciência da computação

L68. Lewis, Harry R. (1968). Duas aplicações de entrada de computador bidimensional impressa à mão (Tese). Universidade de Harvard.
RL. Reif, John H .; Lewis, Harry R. (1977). "Avaliação simbólica e o gráfico de valor global". Anais do 4º Simpósio ACM SIGACT-SIGPLAN sobre Princípios de Linguagens de Programação (POPL '77) . Nova York: ACM. pp. 104-118. doi : 10.1145 / 512950.512961 .
L78. Lewis, Harry R. (1978). "Renomeando um conjunto de cláusulas como um conjunto de trompa". Jornal do ACM . 25 (1): 134–135. doi : 10.1145 / 322047.322059 . MR  0468315 . S2CID  3071958 .
L79. —— (1979). Classes insolúveis de fórmulas quantificacionais . Addison-Wesley .
L80. —— (1980). "Resultados de complexidade para classes de fórmulas quantificacionais" . Journal of Computer and System Sciences . 21 (3): 317–353. doi : 10.1016 / 0022-0000 (80) 90027-6 . MR  0603587 .Uma versão preliminar, "Complexidade de casos solucionáveis ​​do problema de decisão para o cálculo de predicados", foi apresentada no Symposium on Foundations of Computer Science , 1978.
LP82. ——; Papadimitriou, Christos H. (1982). "Computação simétrica limitada pelo espaço" . Ciência da Computação Teórica . 19 (2): 161–187. doi : 10.1016 / 0304-3975 (82) 90058-5 . MR  0666539 .Uma versão preliminar foi apresentada no International Colloquium on Automata, Languages ​​and Programming , 1980.
STOC. ——, ed. (1982). Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing . Association for Computing Machinery .
L90. —— (1990). "Uma lógica de intervalos de tempo concretos (resumo estendido)". Quinto Simpósio Anual do IEEE em Lógica em Ciência da Computação (Filadélfia, PA, 1990) . Los Alamitos: IEEE Computer Society Press. pp. 380–389. doi : 10.1109 / LICS.1990.113763 . MR  1099190 .

Computadores e sociedade

TUDO. ——; Abelson, Hal ; Ledeen, Ken (2008). Explodido em pedaços: sua vida, liberdade e felicidade após a explosão digital . Addison-Wesley. Também traduzido para chinês e russo.
L09. —— (2009). "Livros digitais". Jornal Internacional de Humanidades . 7 (8): 59–66.
L11a. —— (2011). Shephard, Jennifer M .; Kosslyn, Stephen Michael ; Hammonds, Evelynn Maxine (eds.). "A Internet e Hieronymus Bosch: medo, proteção e liberdade no ciberespaço" . The Harvard Sampler: Liberal Education for the Twenty-First Century . Harvard University Press. pp. 57–90. ISBN 978-0-674-05902-3.

Livros didáticos

L81. —— (1981). Uma introdução à programação de computadores e estruturas de dados usando MACRO-11 . Reston Publishing Company.
LP81. ——; Papadimitriou, Christos H. (1981). Elementos da Teoria da Computação . Prentice-Hall . 2ª ed., 1997. Várias traduções.
  • Gallier, Jean H. (setembro de 1984). "Revisão: Elementos da Teoria da Computação por Harry R. Lewis; Christos H. Papadimitriou". Journal of Symbolic Logic . 49 (3): 989–990. doi : 10.2307 / 2274157 . JSTOR  2274157 .
  • Greenleaf, Newcomb. "Trazendo a educação matemática para a era algorítmica". Em Myers, J. Paul, Jr .; O'Donnell, Michael J. (eds.). Constructivity in Computer Science: Summer Symposium San Antonio, TX, 19-22 de junho de 1991, Proceedings . Notas de aula em Ciência da Computação. 613 . Springer. pp. 199–217. doi : 10.1007 / bfb0021092 .Veja em particular p. 205 .
LD. ——; Denenberg, Larry (1991). Estruturas de dados e seus algoritmos . HarperCollins .

Ensino superior

L1. ——. "Slow Down: Obtendo mais de Harvard fazendo menos" (PDF) . (Conselhos aos novos alunos da Harvard College.)
L2. ——. Jacobson, Matthew (ed.). "Harry Lewis, professor de ciência da computação e ex-reitor da faculdade, Universidade de Harvard" . O Projeto de Educação .
L06. —— (2006). Excelência sem alma: como uma grande universidade esqueceu a educação . PublicAffairs . Trans. Chinês, coreano.
LL. ——; Lagemann, Ellen Condliffe (2011). Lewis, Harry R .; Ellen Condliffe, Lagemann (eds.). "Renovando a Missão Cívica da Educação Superior Americana". Para que serve a faculdade? O objetivo público do ensino superior . Teachers College Press .
L11b. —— (2011). Educação, livros e sociedade na era da informação: as palestras de Hong Kong . Chameleon Press.

Outro

L11c. —— (2011). Beisebol como segunda língua: explicando o jogo que os americanos usam para explicar tudo o mais . Auto-publicado.

Referências

links externos