MacTutor

biografia

os pais de Leslie Valiant eram Leslie Valiant e Eva Julia Ujlaki. Ele foi criado na Inglaterra, frequentando a Tynemouth High School, North Shields. Esta escola foi renomeada em 1969, vários anos após a partida de Valiant, quando ficou conhecida como Norham High School. Valiant completou sua educação escolar na Latymer Upper School, em King Street, Hammersmith, Londres. Esta foi (e ainda é) uma famosa escola independente seletiva com uma grande reputação que remonta à sua fundação por Edward Latymer em 1624. Depois de se formar na Latymer Upper School, ele estudou no King’s College, Cambridge, então, após o prêmio de seu primeiro grau, um BA em matemática, ele entrou no Imperial College, Londres para estudar ciência da Computação Teórica. Após a concessão do Diploma do Imperial College em Ciência da Computação, Valiant foi para a Universidade de Warwick, onde realizou uma pesquisa para um doutorado em Ciência da computação com Michael Stewart Paterson como seu conselheiro.
antes da concessão de seu Ph. D., Valiant passou o ano de 1973-74 nos Estados Unidos como professor assistente visitante na Carnegie Mellon University em Pittsburgh, Pensilvânia. Ele recebeu seu doutorado pela Universidade de Warwick em 1974 por seus procedimentos de decisão de tese para famílias de autômatos determinísticos. Em colaboração com seu orientador de tese M S Paterson, Valiant apresentou o artigo autômatos determinísticos de balcão único ao Erste Fachtagung der Gesellschaft für Informatik über Automatentheorie und Formale Sprachen in em Bonn em 1973. Wilfried Brauer revisou o artigo, escrevendo:-

um autômato determinístico de um contador (doca) é um autômato determinístico de pushdown com um alfabeto de pilha de um elemento. É fácil ver que a inclusão e os problemas de nulidade de interseção para docas são indecidíveis. Em contraste com isso, os autores dão um processo de decisão para a equivalência da doca e mostrar que a sua complexidade de tempo é limitado acima por uma função exponencial em sobre a raiz quadrada do número de membros da testado doca do. Eles conjectura de que a equivalência é decidível para a classe de todas as determinista pushdown automata.Valiant publicou o artigo the equivalence problem for deterministic finite-turn pushdown automata em 1974. S A Greibach aponta a importância deste artigo: –

um autômato de loja de pushdown (pda) é finito-gire se houver um limite uniforme no número de vezes que ele pode mudar de empurrar (aumentando o comprimento da loja de pushdown) para estourar (diminuindo o comprimento da loja de pushdown) durante qualquer cálculo em qualquer entrada. O autor estabelece a decidibilidade do problema de equivalência (duas máquinas aceitam a mesma linguagem?) para determinístico finito-vire pda. O significado do resultado reside na prova de técnicas usadas na criação e no fato de que ele representa um dos grandes avanços no sentido de se estabelecer as longas excelente conjectura de que a equivalência problema para determinista pda (dpda) é decidível (o correspondente problema é conhecido para ser indecidíveis para não determinístico pda é ainda muito restrito de casos).Depois de retornar dos Estados Unidos em 1974, Valiant assumiu um lectureship na Universidade de Leeds, onde trabalhou para os dois anos 1974-76. Vamos dar outro exemplo de seus primeiros artigos, Este novamente escrito em colaboração com M S Paterson,. Este artigo de 1975 Deterministic one-counter automata começa com a introdução dos seguintes autores:-

apresentamos uma análise de autômatos determinísticos de um contador, a fim de mostrar que o problema de equivalência para eles é decidível. Todos os nossos argumentos e resultados podem ser traduzidos diretamente em termos teóricos do esquema. O corolário que se segue é que a equivalência é decidível para esquemas de Janov, mesmo quando estes são permitidos um contador auxiliar.Valiant mudou-se para a Escócia em 1975 para assumir um lectureship na Universidade de Edimburgo. Em 1977 ele se casou com Gayle Lynne Dyckhoff; eles tiveram dois filhos Gregory John Valiant e Paul a Valiant. Em Edimburgo, ele foi promovido a Leitor em 1981, mas foi para os Estados Unidos em 1982, quando era professor visitante em Harvard. Mais tarde naquele ano, ele foi nomeado Gordon McKay Professor de Ciência da Computação e Matemática Aplicada em Harvard. Ele permaneceu em Harvard, embora tenha passado o ano de 1987-88 como bolsista visitante na Universidade de Oxford, na Inglaterra. Em 2001 foi nomeado T Jefferson Coolidge Professor de Ciência da Computação e Matemática Aplicada na Harvard School of Engineering and Applied Sciences.As contribuições que Valiant fez são bastante notáveis e ele recebeu as mais altas honras por suas realizações. Ele foi um Guggenheim Fellow em 1985-86 e recebeu o Prêmio Nevanlinna em 1986. Ele foi eleito membro da Royal Society of London em 1991 e, no ano seguinte, membro da American Association for Artificial Intelligence. Ele foi premiado com o Prêmio Knuth da Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory e do Institute of Electrical and Electronics Engineers Technical Committee on the Mathematical Foundations of Computing em 1997. Ele foi eleito para a Academia Nacional de Ciências dos Estados Unidos em 2001, recebeu o Prêmio European Association for Theoretical Computer Science e o prêmio A Turing de 2010 da Association for Computing Machinery, que será apresentado à Valiant no banquete anual de prêmios da Associação em San Jose, Califórnia, em 4 de junho de 2011. O prêmio também inclui um prêmio em dinheiro de US $250.000.
não explicamos as contribuições da Valiant que o levaram a receber os maiores prêmios possíveis. Para fazer isso, citamos o comentário que acompanha o anúncio do Prêmio Turing (os artigos de 2011 referenciados abaixo citam esse comentário). Nos últimos 30 anos, Leslie Valiant fez contribuições fundamentais para muitos aspectos da ciência da Computação Teórica. Seu trabalho abriu novas fronteiras, introduziu novos conceitos engenhosos e apresentou resultados de grande originalidade, profundidade e beleza. Repetidamente, o trabalho de Valiant literalmente definiu ou transformou o cenário da pesquisa em Ciência da computação.

em seguida, continua a dar detalhes de várias áreas para as quais Valiant fez contribuições impressionantes. Damos alguns extratos curtos de cada uma das quatro áreas:

  1. teoria da aprendizagem computacional. A maior contribuição única de Valiant pode ser seu artigo ‘a theory of the learnable’ (1984), que lançou as bases da teoria da aprendizagem computacional. … O modelo “provavelmente aproximadamente correto” (PAC) da Valiant forneceu belos fundamentos para o próprio conceito de aprendizagem.
  2. complexidade da enumeração. No início da década de 1970, a complexidade computacional geralmente lidava com a dificuldade de problemas de decisão, como se um gráfico tem uma correspondência perfeita ou se um vendedor ambulante pode encontrar uma rota de no máximo um certo comprimento. … Uma das descobertas mais notáveis de Valiant é que os problemas de contagem são muito mais sutis do que a experiência anterior sugerida. Um problema de contagem pede o número de alguns objetos combinatórios: por exemplo, quantas combinações perfeitas existem em um gráfico? Não estamos apenas perguntando o problema da decisão de saber se esse número é positivo, mas também o quão grande é. Se o problema da decisão é difícil, então o problema da contagem também deve ser, mas a surpreendente percepção de Valiant foi que o inverso falha. Em seu artigo “A complexidade de computação permanente” (1979), ele mostrou que, embora haja um algoritmo eficiente para dizer se um grafo tem uma perfeita correspondência, não há nenhum algoritmo eficiente para contar perfeito matchings (a menos que P = NP), e no fato de contagem perfeito matchings é tão difícil quanto qualquer problema de contagem. Isso foi um choque para a comunidade de complexidade computacional, que se acostumou com a ideia de que os problemas de decisão capturariam facilmente as principais características de um problema.
  3. computação algébrica. Outra contribuição fundamental para a complexidade computacional foi a teoria da computação algébrica de Valiant, na qual ele estabeleceu uma estrutura para entender quais fórmulas algébricas podem ser avaliadas de forma eficiente. … Em seu artigo “classes de Completude em álgebra” (1979), Valiant caracterizou a dificuldade da computação algébrica em termos de duas funções fundamentais e intimamente relacionadas da álgebra linear, a saber, o determinante e o permanente.
  4. Computação Paralela e distribuída. Além da teoria da aprendizagem computacional e da complexidade computacional, uma terceira área ampla na qual a Valiant fez contribuições importantes é a teoria da computação paralela e distribuída. Seus resultados aqui variam de insights simples, mas poderosos e elegantes, para reexaminar as próprias fundações. Um exemplo de uma visão simples é seu esquema de roteamento paralelo, descrito no artigo “um esquema para comunicação paralela rápida” (1982).

terminamos esta biografia citando na íntegra a conclusão da citação do Prêmio Turing: –

raramente se vê uma combinação tão marcante de profundidade e amplitude como na obra de Valiant. Ele é verdadeiramente uma figura heróica na ciência da computação teórica e um modelo para sua coragem e criatividade na abordagem de alguns dos problemas não resolvidos mais profundos da ciência.

Deixe uma resposta

O seu endereço de email não será publicado.