Anatoli Alexeievitch Karatsuba

Anatoli Alexeievitch Karatsuba (em russo: Анато́лий Алексе́евич Карацу́ба — Grózni, 31 de janeiro de 1937 — Moscou, 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) 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)

Vida

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.

Autômatos

Ver artigo principal: Autômato

O artigo de Edward Moore «experimentos em máquinas sequenciais» $(n;m;p)$. Um autômato $S$ é definido como tendo $n$ estados, $m$ símbolos de entrada e $p$ símbolos de saída do dispositivo. Foram provados nove teoremas sobre estrutura e experimentos com $S$. Mais tarde, as tais máquinas de $S$ 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 $S$ com uma definição $(n;m;p)$ arbitrária, cada um dos estados são distintos dois a dois, então existe uma experiência de comprimento $n(n-1)/2$, que determina a máquina de estados $S$.

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 $S$ é uma máquina $(n;m;p)$, 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 $(n-1)(n-2)/2+1$, por meio do qual se pode encontrar o estado $S$ no final do experimento.

Teorema B (Karatsuba). Existe uma máquina $(n;m;p)$, 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 $(n-1)(n-2)/2+1$

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. 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

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 $0$ e $1$ 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 $M(n)$ é definida como o número de operações de bits suficientes para calcular o produto de dois números de $n$ dígitos através de um algoritmo dado.

Multiplicando-se dois números de $n$ dígitos pelo "método convencional" aprendido em escola "em uma coluna," temos um limite superior $M(n)=O(n^{2})$. Em 1956, Kolmogorov suspeitado que o limite inferior $M(n)$ para qualquer método de multiplicação é também a ordem de $n^{2}$, que é impossível calcular o produto de dois números de $n$ dígitos mais rápidamente que $n^{2}$ operações (como chamada de "hipótese de $n^{2}$"). Dado o fato de que por toda a História da Matemática as pessoas usaram a complexidade da multiplicação da ordem $O(n^{2})$, 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 $n^{2}$, 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 $M(n)$, encontrou um novo método para multiplicar dois números de $n$ dígitos, agora conhecido como multiplicação de Karatsuba, com uma estimativa de

$M(n)=O(n^{\log _{2}3})=O(n^{1,58496\ldots })$

Assim, foi rechaçada a hipótese de $n^{2}$, 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 . 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

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. O mais famoso dos quais é a sua generalização direta, como o O método de multiplicação Schönhage - Strassen, o algoritmo de multiplicação de matrizes de Strassen 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'

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

Últimos anos

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

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.

Livros

• 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

Karatsuba recebeu as seguintes premiações em vida:

• Prêmio P. L. Chebyshev (1981)
• Prêmio Trabalhador Científico Meritório da Rússia (1999)
• Prêmio I. M. Vinogradov (2001).

Ver também

• Algoritmo
• Algoritmo de Karatsuba
• Algoritmo Schönhage–Strassen
• Autômato
• Máquina de Moore
• Função Zeta de Riemann
• Jean-Paul Delahaye
• Teoria dos Números
• Yuri Ofman

Referências

• G. I. Archipov; V. N. Tchubarikov (1997). «On the mathematical works of professor A. A. Karatsuba». Proc. Steklov Inst. Math. 218 

Ligações externas

• Anatoli Alexeievitch Karatsuba (em inglês) no Mathematics Genealogy Project
• «Karatsuba Anatoli Alexeevitch (Página Pessoal)». Consultado em 28 de abril de 2012 
• «Publicações». em Instituto de Matemática Steklov