Harry R. Lewis - Harry R. Lewis
Harry R. Lewis | |
---|---|
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
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
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:
- Uma introdução à programação de computadores e estruturas de dados usando MACRO-11 (1981). MACRO-11 era uma linguagem assembly para computadores PDP-11 .
- Elementos da Teoria da Computação (1981, com Christos H. Papadimitriou ) cobre a teoria dos autômatos , a teoria da complexidade computacional e a teoria das linguagens formais ; sua inclusão da teoria da complexidade e da lógica matemática foi inovadora para a época. Tem sido chamado de "excelente texto tradicional", mas cujo estilo conciso e altamente matemático pode ser intimidante. Embora destinado a alunos de graduação, também tem sido usado para cursos introdutórios de pós-graduação.
- Estruturas de dados e seus algoritmos (1991, com Larry Denenberg).
Lewis também ministra um curso sobre atletismo amador e história social dos esportes na América.
Reitor do Harvard College
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
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 . |
- Börger, Egon (1981). Revisão de classes insolúveis de fórmulas quantificacionais . MR 0544668 .
- Gurevich, Yuri (1982). "Resenha de livro: O problema de decisão: classes resolvíveis de fórmulas quantificacionais. Resenha de livro: classes insolúveis de fórmulas quantificacionais " . Boletim da American Mathematical Society . Nova série. 7 (1): 273–277. doi : 10.1090 / S0273-0979-1982-15033-9 . MR 1567367 .
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. |
- Gasarch, William (2009). "Revisão de Blown to Bits " (PDF) . A coluna da resenha do livro. Notícias ACM SIGACT . 40 (1): 10–13. doi : 10.1145 / 1515698.1515701 . S2CID 8505768 .
- Tanaka Okopnik, Kat (31 de agosto de 2008). "Resenha de livro: Blown to Bits" . Linux Gazette . No. 154.
- "Disponível na prateleira: livros recentes com conexões de Harvard" . Harvard Magazine . Julho a agosto de 2008.
- Entrevista com autores , Stanford Center for Internet and Society
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. |
- Sleeper, Jim (28 de maio de 2006). "Examinando o slide cívico do Crimson" . Boston Globe .
- Shea, Christopher (2 de julho de 2006). "Poison Ivy: Um homem de Harvard exorta a escola a redefinir sua missão" . Washington Post .
- Gasarch, William (2007). "Review of Excellence Without a Soul " (PDF) . A coluna da resenha do livro. Notícias ACM SIGACT . 38 (1): 9–13. doi : 10.1145 / 1233481.1233486 . S2CID 7768602 .
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 . |
- Ream, Todd C. (primavera de 2013). "Para que serve a faculdade? A finalidade pública do ensino superior" . The Review of Higher Education . 36 (3): 427–429. doi : 10.1353 / rhe.2013.0035 . S2CID 143896301 .
- Cecil, Kyle (2014). "Para que serve a faculdade? A finalidade pública do ensino superior" . Journal of Higher Education Outreach and Engagement . 18 (2): 307–312.
- Bettencourt, Genia M .; Kimball, Ezekial (2015). "Resenha de livro: para que serve a faculdade? A finalidade pública do ensino superior". Journal of Student Affairs Research and Practice . 52 (2): 234–236. doi : 10.1080 / 19496591.2015.1018271 . S2CID 155677946 .
- Rawls, Kristin (12 de outubro de 2012). "10. 'What Is College For? The Public Purpose of Higher Education,' editado por Ellen Condliffe Lagemann e Harry Lewis" . 10 livros de leitura obrigatória sobre educação superior na América. Christian Science Monitor .
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
- "Bits and Pieces" blog de Lewis
- "Blown to Bits" antigo blog de Lewis