Anatoli Alexeievitch Karatsuba

Anatoli Alexeievitch Karatsuba (em russo: Анато́лий Алексе́евич Карацу́баGrózni, 31 de janeiro de 1937Moscou, 28 de setembro de 2008) foi um matemático russo que criou o primeiro método para uma multiplicação de números (especialmente números grandes)[1] mais rápida, chamado agora de algoritmo de Karatsuba. A multiplicação de Karatsuba foi o primeiro exemplo de uma nova classe de algoritmos conhecidos agora por algoritmos de divisão e conquista. O algoritmo de Karatsuba foi ultrapassado em performance pelo Algoritmo Schönhage-Strassen.

Anatoli Alexeievitch Karatsuba
Anatoli Alexeievitch Karatsuba
Conhecido(a) por Algoritmo de Karatsuba, Algoritmos de Divisão e Conquista
Nascimento 31 de janeiro de 1937
Grózni, União Soviética
Morte 28 de setembro de 2008 (71 anos)
Moscou, Rússia
Nacionalidade russo
Cônjuge Diana V. Sentchenko
Alma mater Universidade Estatal de Moscou
Prêmios Chebyshev (1981), Trabalhador Honrado da Ciência da Federação Russa (1999), Vinogradov (2001)
Orientador(es)(as) N.M. Korobov
Orientado(a)(s) Gennadii Arkhipov, Sergei Voronin, Vladimir Tchubarikov
Instituições Universidade Estatal de Moscou, Instituto Steklov
Campo(s) Matemática
Tese "Soma de razões trigonométricas de uma forma especial e suas aplicações" (Doutorado - 1962)

Enquanto era estudante na Universidade Estatal de Moscou, Karatsuba participou das atividades propostas por Andrei Kolmogorov e encontrou a solução de dois problemas levantados por este, que deu impulso para o desenvolvimento da teoria de autômatos, e deu início a uma nova direção em matemática e computação: a teoria de algoritmos rápidos.

Karatsuba obteve sua graduação em Matemática pela Faculdade de Mecânica e Matemática da Universidade Estatal de Moscou em 1953. Em 1962 obteve seu doutorado em Matemática com sua tese "Soma de razões trigonométricas de uma forma especial e suas aplicações", supervisionado por Nikolai Korobov e pela faculdade. Em 1966, graças a sua tese "O método de somas trigonométricas e do teorema do valor médio", e tornou-se Fellow do Instituto Steklov, Academia de Ciências da URSS.

A partir de 1970 foi professor de Teoria dos números na Universidade Estatal de Moscou; e a partir de 1980 professor do Departamento de Análise Matemática. Desde 1983, ele foi um dos principais especialistas no campo da teoria dos números na URSS e na Rússia, sendo o chefe do departamento de teoria dos números no Instituto Steklov (fundado no mesmo ano). Suas investigações centraram-se em somas e integrais trigonométricas, na Função Zeta de Riemann, Caráter de Dirichlet, Autômatos Finitos, problema de Hua Luogeng e algoritmos eficientes. Karatsuba supervisionou 15 doutorados.[2]

Autômatos

editar
 Ver artigo principal: Autômato

O artigo de Edward Moore «experimentos em máquinas sequenciais»[3]  . Um autômato   é definido como tendo   estados,   símbolos de entrada e   símbolos de saída do dispositivo. Foram provados nove teoremas sobre estrutura e experimentos com  . Mais tarde, as tais máquinas de   foram chamadas Máquina de Moore. No final do artigo, no capítulo sobre "Novos Desafios", Moore formula o problema de melhorar as estimativas obtidas por ele dadas nos Teoremas 8 e 9:

Teorema 8 (Moore). Seja o autômato   com uma definição   arbitrária, cada um dos estados são distintos dois a dois, então existe uma experiência de comprimento  , que determina a máquina de estados  .

Em 1957 Karatsuba provou dois teoremas que resolviam por completo o problema de Moore para melhorar a estimativa de duração do experimento em seu oitavo teorema.

Teorema A (Karatsuba). Se o autômato   é uma máquina  , tal que cada dois seus estados podem ser distinguidos um do outro, então existe um experimento ramificado de duração de no máximo  , por meio do qual se pode encontrar o estado   no final do experimento.
Teorema B (Karatsuba). Existe uma máquina  , em que todos os estados podem ser distinguidos uns dos outros, de modo que o comprimento mais curto do experimento, que pode determinar o estado é igual a  

Estes dois teoremas são a base do trabalho de 4º ano de curso de Karatsuba, "Sobre um problema da teoria de autômatos", que foi premiado com elogios (ou seja, nada muito grandioso) na competição de trabalhos de estudantes da Faculdade de Matemática e Mecânica da Universidade Estatal de Moscou.

Posterior publicação foi enviada para a revista Успехи математических наук (algo como "Sucessos das Ciências Matemáticas") em 17 de dezembro de 1958 e foi publicado em junho de 1960.[4] Até a presente data (12 de abril de 2010) este resultado de Karatsuba, que mais tarde recebeu o nome de "Teorema Karatsuba-Moore", continua sendo o único resultado exato não-linear em teoria e problemas semelhantes na teoria da complexidade dos cálculos.

Teoria da Complexidade Computacional

editar
 Ver artigo principal: Complexidade computacional

Complexidade computacional é a área da matemática computacional que estuda algoritmos para calcular uma dada função com uma dada precisão possível, usando um menor número de operações de bit. Assume-se que os números são escritos em notação binária, onde os sinais   e   são chamados de bits. Uma "operação de bit" é definida como um registro de marcas 0, 1, adição, subtração, entre parênteses, adição, subtração e multiplicação de dois bits. A primeira formulação de complexidade de computação pertence a Kolmogorov. A complexidade da multiplicação de   é definida como o número de operações de bits suficientes para calcular o produto de dois números de   dígitos através de um algoritmo dado.

Multiplicando-se dois números de   dígitos pelo "método convencional" aprendido em escola "em uma coluna," temos um limite superior  . Em 1956, Kolmogorov suspeitado que o limite inferior   para qualquer método de multiplicação é também a ordem de  , que é impossível calcular o produto de dois números de   dígitos mais rápidamente que   operações (como chamada de "hipótese de  "). Dado o fato de que por toda a História da Matemática as pessoas usaram a complexidade da multiplicação da ordem  , então se houvesse um método mais rápido de multiplicação, então provavelmente já teria sido encontrado .

Em 1960, iniciaram-se os trabalhos em problemas matemáticos de cibernética liderados por Kolmogorov na Faculdade de Mecânica e Matemática, que foi formulada pela chamada hipótese  , e uma série de tarefas relativas à avaliação dos outros cálculos similares. Anatoli Karatsuba, na esperança de obter uma estimativa mais baixa para  , encontrou um novo método para multiplicar dois números de   dígitos, agora conhecido como multiplicação de Karatsuba, com uma estimativa de

 

Assim, foi rechaçada a hipótese de  , conforme relatado por Kolmogorov após a reunião ordinária do seminário. Na próxima sessão do seminário, este método foi narrado por Kolmogorov, encerrando-se o seminário [5]. O primeiro artigo descreve a multiplicação Karatsuba foi preparado por Kolmogorov, onde apresentou duas diferentes e não relacionados a cada outros resultados de dois dos seus discípulos [6]

Embora claramente Kolmogorov tenha apontado no artigo que um teorema (não relacionados com a multiplicação rápida) pertença a Yuri Petrovitch Ofman e um outro teorema (o primeiro teorema na história da multiplicação rápida) a Karatsuba, este último teorema foi atribuído aos dois autores por um longo período e confundiu os leitores, que creditaram a ambos os autores a criação de um método de multiplicação rápida, e até mesmo chamando este método como Karatsuba-Ofman. O Método de Karatsuba foi posteriormente generalizado para a teoria do "Paradigma de Divisão e Conquista" e outros exemplos importantes, como Busca Binária, método da bissecção, etc

Posteriormente foram construídos muitos algoritmos rápidos com base na ideia de Karatsuba.[1][7] O mais famoso dos quais é a sua generalização direta, como o O método de multiplicação Schönhage - Strassen,[8] o algoritmo de multiplicação de matrizes de Strassen [9] e o algoritmo de Transformada Rápida de Fourier.

O matemático e filósofo francês Jean-Paul Delahaye disse que o chamado método de multiplicação de Karatsuba 'um dos resultados mais úteis de matemática' [10]

O Algoritmo de Karatsuba é implementado em quase todos os computadores modernos, não apenas como software, mas também como hardware.

Últimos anos

editar

Nos últimos anos, a investigação ainda estava no campo da teoria dos números, porém estava envolvido em alguns problemas de Física Teórica, inclusive no campo da Teoria Quântica de Campos. Pela aplicação de seu teorema, e vários outros da teoria das ATS, obteve novos resultados usando de novas abordagens teóricas baseadas no modelo de Jaynes-Cummings em óptica quântica.

Publicações

editar

Na ocasião do 60º aniversário de Karatsuba, foi publicado um artigo intitulado «Sobre as obras de matemática do professor A.A Karatsuba.», onde seus ex-alunos G. I. Arkhipov e V. N. Tchubarikov descreviam as características especiais de trabalhos de pesquisa AAKaratsuba da seguinte maneira:

"Ao se descrever obras de destacados cientistas, é natural enfatizar algumas características e particularidades de seu trabalho criativo. Tais características distintivas do trabalho científico Professor Karatsuba são criatividade combinatória, de caráter fundamental, e maior completude nos resultados."

Foram publicados mais de 160 estudos e monografias sobre a pesquisa de A.A.Karatsuba.[11][12]

Livros

editar
  • Karatsuba, A. A.; Voronin, Sergei (1992). The Riemann Zetafunction em alemão. [S.l.]: De Gruyter 
  • Karatsuba, A. A.; Arkhipov,Gennadii. Tchubarikhov, Vladimir (2004). Trigonometric sums in analysis and number theory em alemão. [S.l.]: De Gruyter 
  • Karatsuba, A. A. (1982). Multiple trigonometric sums. [S.l.]: American Mathematical Society 
  • Karatsuba, A. A. (1995). Complex analysis in number theory. [S.l.]: CRC Press 
  • Karatsuba, A. A. (1993). Basic analytic number theory. [S.l.]: Springer 

Prêmios

editar

Karatsuba recebeu as seguintes premiações em vida:

Ver também

editar

Referências

  1. a b Knuth, D.E. (1998). The Art of Computer Programming. V.2. 2. Seminumerical Algorithms 3 ed. [S.l.]: Addison-Wesley Publ.Co. 762 páginas. ISBN 9780201896848 
  2. Página pessoal de A.A.Karatsuba em inglês em russo, Instituto de Matemática Steklov (acessada em abril de 2012).
  3. Moore, E. F. (1956). «Gedanken-experiments on Sequential Machines.». Automata Studies, Annals of Mathematical Studies, Princeton University Press, Princeton, N.J., (34): 129–153 
  4. Karatsuba, A.A. (1960). «Solução para um problema na teoria de autômatos finitos». Uspekhi Matematitcheskikh Nauk (em russo) (15:3): 157–159 
  5. Karatsuba, A.A. (1995). «A complexidade da computação em russo» Tr. Instituto de Matemática Steklov ed. 211: 186-202 
  6. Karatsuba, A.A.; Ofman Yu.P. (fevereiro de 1962). «Multiplicação de números de vários dígitos sobre autômatos». Relatos de Academia de Ciências da URSS. 145 (2) 
  7. Karatsuba, A.A. (1975). «Berechnungen und die Kompliziertheit von Beziehungen» Elektronische Informationsverarbeitung und Kybernetik ed. 11 
  8. Schönhage A., V. Strassen (1971). «Multiplikation Schnelle großer Zahlen» Informática ed. (7): 281-292 
  9. Strassen, Volker, Eliminação de Gauss não é Optimal, Numer. Math. 13, p. 354-356, 1969
  10. Delahaye, Jean-Paul (fevereiro de 2000). «Mathématiques et philosophie». Pour la science (277): 100-104 
  11. «Publicações de A.A.Karatsuba em inglês»  Anatoli Karatsuba, Instituto de Matemática Steklov (acessada em abril de 2012).
  12. «Publicações de A.A.Karatsuba em russo»  Anatoli Karatsuba, Instituto de Matemática Steklov (acessada em abril de 2012).
  • G. I. Archipov; V. N. Tchubarikov (1997). «On the mathematical works of professor A. A. Karatsuba». Proc. Steklov Inst. Math. 218 

Ligações externas

editar
 
O Commons possui uma categoria com imagens e outros ficheiros sobre Anatoli Alexeievitch Karatsuba