Anatolii Alexeievitch Karatsuba

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Translation Latin Alphabet.svg
Este artigo ou secção está a ser traduzido de ru:Карацуба,_Анатолий_Алексеевич. Ajude e colabore com a tradução.
Question book.svg
Esta página ou secção não cita nenhuma fonte ou referência, o que compromete sua credibilidade (desde setembro de 2012).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoYahoo!Bing. Veja como referenciar e citar as fontes.
Ambox grammar.svg
Esta página ou secção precisa de correção ortográfico-gramatical.
Pode conter incorreções textuais, podendo ainda necessitar de melhoria em termos de vocabulário ou coesão, para atingir um nível de qualidade superior conforme o livro de estilo da Wikipédia. Se tem conhecimentos linguísticos, sinta-se à vontade para ajudar.
Anatolii Alexeievitch Karatsuba
Matemática
A.A.Karatsuba on lecture.jpg
Dados gerais
Nacionalidade Rússia Russa
Nascimento 31 de janeiro de 1937
Local União das Repúblicas Socialistas Soviéticas Grózni, União Soviética
Morte 28 de setembro de 2008 (71 anos)
Local Rússia Moscou, Rússia
Cônjuge Diana V. Sentchenko
Atividade
Campo(s) Matemática
Instituições Universidade Estatal de Moscou, Instituto Steklov
Alma mater Universidade Estatal de Moscou
Tese "Soma de razões trigonométricas de uma forma especial e suas aplicações" (Doutorado - 1962)
Orientador(es) N.M. Korobov
Orientado(s) Gennadii Arkhipov, Sergei Voronin, Vladimir Tchubarikov
Conhecido(a) por Algoritmo de Karatsuba, Algoritmos de Divisão e Conquista
Influenciado(s) Teoria de Algoritmos, Teoria de Autômatos
Prêmio(s) Chebyshev (1981), Trabalhador Honrado da Ciência da Federação Russa (1999), Vinogradov (2001)

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

Vida[editar | editar código-fonte]

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 | editar código-fonte]

O artigo de Edward Moore «experimentos em máquinas seqüenciais»[3] (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 (n; m; p), com estados distintos dois a dois, há uma duração da experiência de no máximo (n-1)(n-2)/2 + 1, que identifica essa máquina de estados S.
Teorema B (Karatsuba). Existem (n; m; p) sa máquina, distintos dois a dois, 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 [4] .. Até a presente data (12/04/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 | editar código-fonte]

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. Anatolii 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_23}) = 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 [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 idéia 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 | editar código-fonte]

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 | editar código-fonte]

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 papers e monografias de pesquisa de A.A.Karatsuba.[11] [12]

Livros[editar | editar código-fonte]

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

Prémios[editar | editar código-fonte]

Karatsuba recebeu as seguintes premiações em vida:

Ver também[editar | editar código-fonte]

Referências

  1. a b Knuth, D.E.. The Art of Computer Programming. V.2.. 3 ed. [S.l.]: Addison-Wesley Publ.Co., 1998. 762 pp. vol. 2. Seminumerical Algorithms.
  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 (15:3): 157–159.
  5. Karatsuba, A.A.. (1995). "A complexidade da computação em russo" 211.
  6. Karatsuba, A.A.; Ofman Yu.P.. (fevereiro 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".
  8. Schönhage A., V. Strassen. (1971). "Multiplikation Schnelle großer Zahlen" (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 2000). "Mathématiques et philosophie". Pour la science (277): 100-104.
  11. Publicações de A.A.Karatsuba em inglês, Anatolii Karatsuba, Instituto de Matemática Steklov (acessada em Abril de 2012).
  12. Publicações de A.A.Karatsuba em russo, Anatolii 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 | editar código-fonte]

Ícone de esboço Este artigo sobre um(a) matemático(a) é um esboço. Você pode ajudar a Wikipédia expandindo-o.


O Commons possui uma categoria contendo imagens e outros ficheiros sobre Anatolii Alexeievitch Karatsuba