Mostrar código-fonte de Anatoli Alexeievitch Karatsuba

{{Mais notas|data=setembro de 2021}}
{{Info/Biografia
 |nome              = Anatoli Alexeievitch Karatsuba
 |imagem            = A.A.Karatsuba on lecture.jpg
 |tamanho           = 200px
 |nascimento_data   = {{dni|lang=br|31|01|1937|si}}
 |nascimento_local  = [[Grózni]], [[União Soviética]]
 |morte_data        = {{morte|lang=br|28|9|2008|31|1|1937}}
 |morte_local       = [[Moscou]], [[Rússia]]
 |nacionalidade     = {{RUSn|o}}
 |campo             = [[Matemática]]
 |local_trabalho    = [[Universidade Estatal de Moscou]], [[Instituto de Matemática Steklov|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        = [[Nikolai Mikhailovitch Korobov|N.M. Korobov]]
 |orientado         = [[Gennadii Andreievitch Arkhipov|Gennadii Arkhipov]], [[Sergei Mikhailovitch Voronin|Sergei Voronin]], [[Vladimir Nikolaievitch Tchubarikov|Vladimir Tchubarikov]]
 |conhecido_por     = [[Algoritmo de Karatsuba]], [[divisão e conquista|Algoritmos de Divisão e Conquista]]
 |influenciou       = [[Algoritmo|Teoria de Algoritmos]], [[autômato|Teoria de Autômatos]]
 |prêmio            = [[Pafnuti Tchebychev|Chebyshev]] (1981), [[Trabalhador Honrado da Ciência da Federação Russa]] (1999), [[Ivan Vinogradov|Vinogradov]] (2001)
 |cônjuge           = [[Diana Vasilievna Sentchenko|Diana V. Sentchenko]]
}}
'''Anatoli Alexeievitch Karatsuba''' ({{lang-ru|Анато́лий Алексе́евич Карацу́ба}}  —  [[Grózni]], [[31 de janeiro]] de [[1937]] — [[Moscou]], [[28 de setembro]] de [[2008]]) foi um [[matemático]] [[Rússia|russo]] que criou o primeiro método para uma multiplicação de números (especialmente números grandes)<ref name="Knuth 1998 762">{{citar livro |último =Knuth |primeiro =D.E. |título= [[The Art of Computer Programming| The Art of Computer Programming. V.2.]] |edição= 3 |publicado= [[Addison-Wesley|Addison-Wesley Publ.Co.]] | volume = 2. Seminumerical Algorithms |ano= 1998 |páginas= 762 | isbn = 9780201896848 }}</ref> 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 [[divisão e conquista|algoritmos de divisão e conquista]]. O algoritmo de Karatsuba foi ultrapassado em performance pelo [[Algoritmo Schönhage-Strassen]].

== 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 Mikhailovitch Korobov|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 de Matemática Steklov|Instituto Steklov]], [[Academia de Ciências da URSS]].

A partir de [[1970]] foi professor de [[Teoria dos Números|Teoria dos números]] na [[Universidade Estatal de Moscou]]; e a partir de [[1980]] professor do Departamento de [[Análise matemática|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 de Matemática Steklov|Instituto Steklov]] (fundado no mesmo ano). Suas investigações centraram-se em somas e integrais trigonométricas, na [[Função zeta de Riemann|Função Zeta de Riemann]], [[Caráter de Dirichlet]], [[autômato finito|Autômatos Finitos]], [[problema de Hua Luogeng]] e algoritmos eficientes. Karatsuba supervisionou 15 [[doutorado]]s.<ref>Página pessoal de A.A.Karatsuba [http://www.mi.ras.ru/~karatsuba/index_e.html <sup>em inglês</sup>] [http://www.mi.ras.ru/~karatsuba/index.html <sup>em russo</sup>], Instituto de Matemática Steklov (acessada em abril de 2012).</ref>

== Autômatos ==
{{artigo principal|Autômato}}

O artigo de [[Edward F. Moore|Edward Moore]] «experimentos em máquinas sequenciais»<ref>{{citar periódico|último =Moore|primeiro = E. F. |título=Gedanken-experiments on Sequential Machines.|páginas=129–153|periódico= Automata Studies, Annals of Mathematical Studies, Princeton University Press, Princeton, N.J.,|número=34|ano=1956}}</ref> <math>(n; m; p)</math>. Um [[autômato]] <math>S</math> é definido como tendo <math>n</math> estados, <math>m</math> símbolos de entrada e <math>p</math> símbolos de saída do dispositivo. Foram provados nove teoremas sobre estrutura e experimentos com <math>S</math>. Mais tarde, as tais máquinas de <math>S</math> 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 <math>S</math> com uma definição <math>(n; m; p)</math> arbitrária, cada um dos estados são distintos dois a dois, então existe uma experiência de comprimento <math> n (n-1) / 2 </math>, que determina a máquina de estados <math>S</math>.''

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

: '''Teorema ''B'' (Karatsuba).''' Existe uma máquina <math>(n; m; p)</math>, 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 {{nobr|<math>(n-1)(n-2)/2 + 1</math>}}''

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.<ref>{{citar periódico|último =Karatsuba|primeiro =A.A.|título=Solução para um problema na teoria de autômatos finitos |páginas=157–159|periódico=Uspekhi Matematitcheskikh Nauk|número=15:3|ano=1960 |língua=russo}}</ref> 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 ==
{{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 <math>0</math> e <math>1</math> 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 [[Andrei Kolmogorov|Kolmogorov]]. A complexidade da multiplicação de <math>M (n)</math> é definida como o número de operações de bits suficientes para calcular o produto de dois números de <math>n</math> dígitos através de um algoritmo dado.

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

: <math>M(n) = O(n^{\log_23}) = O(n^{1,58496\ldots})</math>

Assim, foi rechaçada a '''hipótese de <math> n ^ 2 </math>''', 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 <ref>{{Citar periódico |ultimo= Karatsuba | primeiro=A.A. | titulo = A complexidade da computação <sup>em russo</sup>| ano = 1995 | edição = Tr. Instituto de Matemática Steklov | volume = 211 | páginas = 186-202 | url=http://mi.mathnet.ru/tm1120}}</ref>. 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 <ref>{{Citar periódico |ultimo=Karatsuba|primeiro=A.A.|coautores= Ofman Yu.P. |data=fevereiro de 1962|titulo=Multiplicação de números de vários dígitos sobre autômatos |jornal=Relatos de Academia de Ciências da URSS |volume=145 |numero=2 }}</ref>

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 "[[divisão e conquista|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.<ref name="Knuth 1998 762"/><ref>{{Citar periódico | ultimo=Karatsuba|primeiro=A.A. | titulo = Berechnungen und die Kompliziertheit von Beziehungen | ano = 1975 | edição = Elektronische Informationsverarbeitung und Kybernetik | volume = 11 }}</ref> O mais famoso dos quais é a sua generalização direta, como o [[Algoritmo Schönhage-Strassen|O método de multiplicação Schönhage - Strassen]],<ref>{{Citar periódico| autor = Schönhage A., V. Strassen | titulo = Multiplikation Schnelle großer Zahlen | ano = 1971 | edição = Informática | número = 7 | paginas = 281-292 }}</ref> o [[algoritmo Strassen|algoritmo de multiplicação de matrizes de Strassen]] <ref>Strassen, Volker,'' Eliminação de Gauss não é'' Optimal, Numer. Math. 13, p. 354-356, 1969</ref> e o [[FFT|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 [[Algoritmo de Karatsuba|multiplicação de Karatsuba]]'' 'um dos resultados mais úteis de matemática''' <ref>{{Citar periódico |ultimo=Delahaye |primeiro=Jean-Paul|data=fevereiro de 2000|titulo=Mathématiques et philosophie |jornal=Pour la science|numero=277 |paginas=100-104}}</ref>

O [[Algoritmo de Karatsuba]] é implementado em quase todos os [[computador]]es 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 [[Teorema ATS|ATS]], obteve novos resultados usando de novas abordagens teóricas baseadas no [[modelo de Jaynes-Cummings]] em [[Óptica Quântica|ó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 [[Gennadii Andreievitch Arkhipov|G. I. Arkhipov]] e [[Vladimir Nikolaievitch Tchubarikov|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.<ref>{{citar web | url=http://www.mi.ras.ru/~karatsuba/list_e.html | título=Publicações de A.A.Karatsuba <sup>em inglês</sup> }} Anatoli Karatsuba, Instituto de Matemática Steklov (acessada em abril de 2012).</ref><ref>{{citar web | url=http://www.mi.ras.ru/~karatsuba/list.html | título=Publicações de A.A.Karatsuba <sup>em russo</sup> }} Anatoli Karatsuba, Instituto de Matemática Steklov (acessada em abril de 2012).</ref>

=== Livros ===
* {{Citar livro|autor=Karatsuba, A. A. |coautor= Voronin, Sergei|título=The Riemann Zetafunction <sup>em alemão</sup>| editora=De Gruyter |ano=1992}}
* {{Citar livro|autor=Karatsuba, A. A. |coautor= Arkhipov,Gennadii. Tchubarikhov, Vladimir|título=Trigonometric sums in analysis and number theory <sup>em alemão</sup>| editora=De Gruyter |ano=2004}}
* {{Citar livro|autor=Karatsuba, A. A.|título=Multiple trigonometric sums| editora=American Mathematical Society |ano=1982}}
* {{Citar livro|autor=Karatsuba, A. A.|título=Complex analysis in number theory| editora=CRC Press |ano=1995}}
* {{Citar livro|autor=Karatsuba, A. A.|título=Basic analytic number theory| editora=Springer |ano=1993}}

== Prêmios ==
Karatsuba recebeu as seguintes premiações em vida:

* Prêmio [[Pafnuti Tchebychev|P. L. Chebyshev]] (1981)
* Prêmio Trabalhador Científico Meritório da Rússia (1999)
* Prêmio [[Ivan Vinogradov|I. M. Vinogradov]] (2001).

== Ver também ==
* [[Algoritmo]]
* [[Algoritmo de Karatsuba]]
* [[Algoritmo Schönhage-Strassen|Algoritmo Schönhage–Strassen]]
* [[Autômato]]
* [[Máquina de Moore]]
* [[Função zeta de Riemann|Função Zeta de Riemann]]
* [[Jean-Paul Delahaye]]
* [[Teoria dos Números]]
* [[Yuri Petrovitch Ofman|Yuri Ofman]]

{{referências}}
* {{citar periódico|autor = G. I. Archipov |coautor= V. N. Tchubarikov |título= On the mathematical works of professor A. A. Karatsuba |periódico= Proc. [[Instituto de Matemática Steklov|Steklov Inst. Math]].| volume = 218 |ano= 1997}}

== Ligações externas ==
* {{MathGenealogy |id=87931}}
* {{Citar web| url = http://www.mi.ras.ru/~karatsuba/index_e.html | título = Karatsuba Anatoli Alexeevitch (Página Pessoal) | acessodata = 28 de abril de 2012}}
* {{Link||2=http://www.mi.ras.ru/~karatsuba/list_e.html |3=Publicações |4=em [[Instituto de Matemática Steklov]]}}

{{Commonscat|Anatoli Alexeevitch Karatsuba}}
{{Teoria dos números}}
{{Portal3|Biografias|Matemática}}

{{DEFAULTSORT:Karatsuba, Anatoli Alexeevitch}}
[[Categoria:Matemáticos da Rússia do século XX]]
[[Categoria:Matemáticos do século XXI]]
[[Categoria:Matemáticos da União Soviética]]
[[Categoria:Matemáticos da Rússia]]
[[Categoria:Teoristas dos números]]