Zobrazenie zdroja stránky Anatolij Alexejevič Karacuba

{{Infobox Osobnosť
   |Meno             = Anatolij Alexejevič Karacuba
   |Portrét          = A.A.Karatsuba.jpg
   |Popis            = [[Rusko|ruský]] [[matematik]]
   |Dátum narodenia  = [[31. január]] [[1937]]
   |Miesto narodenia = [[Groznyj]], [[Rusko]], vtedy [[Ruská SSR]], [[ZSSR]]
   |Dátum úmrtia     = {{dúv|2008|9|28|1937|1|31}}
   |Miesto úmrtia    = [[Moskva]], Rusko
}}

'''Anatolij Alexejevič Karacuba''' ({{rus|Анатолий Алексеевич Карацуба}}; [[31. január]] [[1937]], [[Groznyj]], [[Rusko]], vtedy [[Ruská SSR]], [[ZSSR]] — [[28. september]] [[2008]], [[Moskva]], Rusko) bol ruský matematik, autor prvého efektívneho [[Algoritmus|algoritmu]] na násobenie veľkých čísiel.

== Štúdium a práca ==
[[Súbor:A.A.Karatsuba graduate.jpg|thumb|left|Karacuba za mlada]]
Anatolij Karacuba študoval v rokoch [[1944]] - [[1954]] na chlapčenskej strednej škole v [[Groznyj|Groznom]], ktorú ukončil s vyznamenaním. Už v mladých rokoch preukázal neobyčajný [[matematika|matematický]] talent. Ako žiak prvých ročníkov riešil úlohy zadávané študentom posledných ročníkov. 

V roku [[1959]] dokončil úspešne štúdium na [[Moskovská štátna univerzita M. V. Lomonosova|Lomonosovovej Moskovskej štátnej univerzite]], na Katedre matematiky a mechaniky. Titul [[kandidát vied]] získal v roku [[1962]] vypracovaním dizertácie na tému ''Špeciálne racionálne trigonometrické sumy a ich aplikácie''. Vedúcim jeho práce bol N. M. Korobov. Po jej obhájení začal Karacuba pracovať na Katedre matematiky a mechaniky Moskovskej štátnej univerzity. V roku [[1966]] získal titul [[doktor vied]] v odbore matematika s prácou ''Metóda trigonometrických súm a vety o stredných hodnotách'' a stal sa členom [[Matematický ústav V. A. Steklova AV ZSSR|matematického ústavu V. A. Steklova AV ZSSR]]. 

Po roku [[1983]] bol Anatolij Karacuba považovaný za jedného z popredných [[ZSSR|sovietskych]] odborníkov a výskumníkov v oblasti [[Teória čísel|teórie čísiel]]. Bol vedúcim oddelenia teórie čísiel Steklovovho inštitútu, [[profesor]]om na oddelení teórie čísiel [[Moskovská štátna univerzita M. V. Lomonosova|Moskovskej štátnej univerzity]] (od roku [[1970]]) a profesorom na oddelení [[Matematická analýza|matematickej analýzy]] Moskovskej štátnej univerzity (od roku 1980). Jeho výskum bol zameraný na [[trigonometrický rad|trigonometrické rady]] a integrály, [[Riemannova zeta funkcia|Riemannovu zeta funkciu]], [[konečný automat|konečné automaty]] a efektívne [[algoritmus|algoritmy]]. 

A. Karacuba vyškolil 15 [[Doktorand|doktorandov]], sedem z nich neskôr získalo titul doktor vied.

== Ocenenia ==
* [[1981]]: [[Pafnutij Ľvovič Čebyšev|Čebyševova]] cena Sovietskej akadémie vied 
* [[1999]]: Vynikajúci ruský vedec 
* [[2001]]: [[Ivan Matvejevič Vinogradov|Vinogradovova]] cena Ruskej akadémie vied 

== Prvé práce z informatiky ==
Ako študent [[Moskovská štátna univerzita M. V. Lomonosova|Moskovskej štátnej univerzity]] navštevoval Anatolij Karacuba seminár vedený [[Andrej Nikolajevič Kolmogorov|Andrejom Nikolajevičom Kolmogorovom]] a vyriešil dva problémy, ktoré Kolmogorov formuloval. Tieto problémy boli podstatné pre rozvoj [[Teória automatov|teórie automatov]] a ich vyriešenie odštartovalo nový smer v matematike, teóriu efektívnych algoritmov.  

=== Automaty ===
[[Edward F. Moore]] definuje vo svojom článku „Gedanken-experiments on Sequential Machines“ [[Automat (teória automatov)|automat]] <math>S</math> typu <math>(n; m;p)</math> ako zariadenie, ktoré má <math>n</math> stavov, reaguje na <math>m</math> vstupných symbolov a dáva na výstupe <math>p</math> symbolov.<ref>{{cite journal|last=Moore| first= E. F.| title= Gedanken-experiments on Sequential Machines.| pages=129–153| journal= Automata Studies, Annals of Mathematical Studies, Princeton University Press, Princeton, N.J.,| issue=34| year=1956}}</ref> V spomínanej práci je vyslovených a dokázaných 9 viet o štruktúre <math>S</math>. Takéto automaty dostali neskôr meno Moorove automaty. V závere svojho článku formuluje problém týkajúci sa zlepšenia odhadov zo svojich viet 8 a 9: 

: '''Veta 8 (Moore).''' Majme ľubovoľný <math>(n; m; p)</math> automat <math>S</math>, ktorého každé dva stavy sú rozlíšiteľné, potom existuje experiment dĺžky <math>n(n-1)/2</math>, ktorý určí stav automatu <math>S</math>.'' 

Karacuba dokázal v roku 1957 dve vety, ktoré dávajú úplnú odpoveď na Moorov problém týkajúci sa zlepšenia odhadu v jeho '''Vete 8'''. 

: '''Veta ''A'' (Karacuba).''' Ak <math>S</math> je <math>(n; m; p)</math> - automat ktorého každé dva stavy sú rozlíšiteľné, tak existuje experiment dĺžky nanajvýš <math>(n-1)(n-2)/2 + 1</math>, ktorý identifikuje stav automatu <math>S</math>. 

: '''Veta ''B'' (Karacuba).''' Existuje <math>(n; m; p)</math> automat, ktorého každé dva stavy sú rozlíšiteľné, taký, že dĺžka najkratšieho experimentu, ktorým je možné zistiť jeho stav je rovná  <math>(n-1)(n-2)/2 + 1</math>.''

Tieto dve vety dokázal Karacuba v štvrtom ročníku univerzity v rámci ročníkového projektu. Príslušný článok bol publikovaný v júni 1960.<ref>{{cite journal| last=Karatsuba| first=A. A.| title=Solution of one problem from the theory of finite automata | pages=157– 59| journal=Usp. Mat. Nauk| issue=15:3| year=1960}}</ref> Až do dnes (12.04.2010) táto tzv. Moore-Karacubova veta ostáva jediným presným nelineárnym odhadom v teórii automatov a podobných problémoch teórie [[Výpočtová zložitosť|výpočtovej zložitosti]].

=== Efektívne algoritmy ===
Efektívne algoritmy predstavujú časť výpočtovej matematiky, ktorá študuje algoritmy vyčísľovania danej funkcie s danou presnosťou za podmienky použitia čo najmenšieho počtu bitových operácií. Za predpokladu, že je číslo zadané v [[dvojková sústava|dvojkovej sústave]], sa znaky 0 a 1 nazývajú [[bit]]y (analógia cifier v [[desiatková sústava|desiatkovej sústave]]). Jedna bitová operácia je definovaná ako zapísanie niektorého zo znakov 0, 1, plus, mínus alebo zátvorka, ďalej zreťazenie, odčítanie a súčet dvoch bitov. [[Andrej Nikolajevič Kolmogorov]] ako prvý sformuloval problém o bitovej zložitosti vyčíslenia. "Zložitosť násobenia <math>M(n)</math> je definovaná ako počet bitových operácií postačujúcich na vyčíslenie súčinu dvoch <math>n</math>-ciferných čísiel podľa zadaného algoritmu."

Ak uvažujeme násobenie dvoch <math>n</math>-ciferných celých čísiel bežnou školskou metódou "pod seba" dostaneme horný odhad <math>M(n) = O(n^2)</math>. [[Andrej Nikolajevič Kolmogorov|Andrej Kolmogorov]] vyslovil v roku 1956 [[Hypotéza|hypotézu]], že dolný odhad zložitosti <math>M(n)</math> je pre každý algoritmus násobenia tiež rádu <math>n^2</math>. Čiže, že nie je možné vyčísliť súčin dvoch <math>n</math>-ciferných celých čísiel rýchlejšie ako s pomocou <math>n^2</math> operácií. 
Táto ''<math>n^2</math> hypotéza'' sa zdala byť prijateľnou, nakoľko v celej histórii nebol známy žiadny rýchlejší algoritmus násobenia a zdalo sa, že ak by nejaký rýchlejší algoritmus existoval, už by ho niekto objavil. 

A. Karacuba však našiel v roku 1960 novú metódu násobenia dvoch <math>n</math>-ciferných čísiel dnes známu ako [[Karacubov algoritmus]]. Jeho zložitosť je <math>M(n) = O(n^{\log_23}) = O(n^{1,58496\ldots}),</math> čo vyvracia ''<math>n^2</math> hypotézu''. Tento svoj výsledok prezentoval Karacuba na Kolmogorovom seminári na Moskovskej štátnej univerzite, čím sa aj zavŕšila činnosť tohoto semináru. Prvú prácu, ktorá vysvetľovala nový algoritmus pripravil sám Kolmogorov,<ref>Karatsuba A., Ofman Yu.: ''Multiplication of multidigit numbers on automata''. Soviet Physics-Doklady, 7, 595–596 (1963); translation from Dokl. Akad. Nauk SSSR, 145:2, 293–294, (1962)</ref> kde prezentoval dva medzi sebou nesúvisiace výsledky dvoch svojich študentov. Kolmogorov presne uvádza, že jedna z viet (nezaoberajúca sa rýchlym násobením) patrí J. Ofmanovi a druhá veta (opisujúca prvý rýchly algoritmus násobenia) patrí A. Karacubovi. Karacubov algoritmus sa zvykne nazývať aj ''metóda rozdeľuj a panuj'', ''binárne rozštiepenie'', či ''princíp dichotómie''. 

Na základe Karacubovej myšlienky bolo neskôr nájdené množstvo ďalších rýchlych algoritmov. Z nich najznámejšie sú priame zovšeobecnenia Karacubovho algoritmu, ako sú Schönhage–Strassenov algoritmus 
<ref>Schonhage A., Strassen V.: ''Schnelle Multiplikation grosser Zahlen'', 1971, Computing, Vol. 7,pages=281–292</ref> a Strassenov algoritmus násobenia [[Matica (matematika)|matíc]].<ref>Strassen, Volker, ''Gaussian Elimination is not Optimal'', Numer. Math. 13, p. 354—356, 1969</ref> V posledných rokoch sa termín ''rozdeľuj a panuj'' používa pre algoritmy, pri ktorých sa problém rozdelí na časti; nemusí nutne ísť o priame spojenie s algoritmom rýchleho násobenia. 

Francúzsky matematik a filozof [[Jean-Paul Delahaye]] sa odvoláva na Karacubov algoritmus ako na ''«jeden z najužitočnejších výsledkov matematiky».''<ref>{{cite journal| last=Delahaye| first=Jean-Paul|title=Mathematiquest philosophie | pages=100–104| journal=Pour la Science| issue=277| year=2000}}</ref> 

Karacubov algoritmus je implementovaný v každom modernom počítači a to nielen ako [[softvér]] ale aj ako [[hardvér]]. 

== Práce v teórii čísiel ==
A. Karacuba publikoval výsledky svojej vedeckej práce vo viac ako 160 odborných článkoch a napísal 5 [[Monografia|monografií]].<ref>{{cite book|first=
A. A. |last=Karatsuba| title= Principles of analytic number
theory.| location= Moscow|publisher= Nauka| year= 1975}}</ref><ref>{{cite book|author=G. I. Archipov, A. A. Karatsuba, V. N.
Chubarikov| title= Theory of multiple trigonometric
sums.|location= Moscow|publisher= Nauka| year=
1987}}</ref><ref>{{cite book|author=A. A. Karatsuba, S. M.
Voronin| title=  The Riemann Zeta Function.|location=
Moscow|publisher= Fiz.Mat.Lit.|year= 1994}}</ref><ref>{{cite
book|first= A. A. |last=Karatsuba| title= Complex analysis in
number theory.|location= London, Tokyo: C.R.C.| year= 1995}}</ref><ref>{{cite book|author=A. A. Karatsuba, M. A. Korolev| title=
Encyclopedia of Number Theory.|location= Moscow|publisher= Nauka|
year=... }}</ref> 

=== Trigonometrické sumy a integrály ===
==== ''p''-adická metóda v odhade trigonometrických súm ====
A. Karacuba objavil tzv. <math>p</math>-adickú metódu pre odhad istých trigonometrických súčtov, tzv. <math>L</math>-súm<ref>{{cite journal| first=A. A.|
last=Karatsuba|title=  Estimates of trigonometric sums of a
special form and their applications| pages=513–514| journal= Dokl.
Akad. Nauk SSSR| issue=137:3| year= 1961}}</ref> 

: <math>S = \sum_{x=1}^P e^{2\pi i (a_1x/p^n+ \dots a_nx^n/p)},
\quad (a_s,p) = 1, \quad 1 \le s \le n,</math> 

Význam jeho odhadov spočíva najmä v tom, že umožňujú presnejšiu lokalizáciu núl tzv. Dirichletových ''L''-radov.

==== Viacnásobné trigonometrické sumy ====
V rokoch 1960 - 1980 sa A. Karacuba venoval teórii viacnásobných trigonometrických súm,<ref>{{cite journal|first=A.
A.|last=Karatsuba| title= The mean value theorems and complete
trigonometric sums|pages=183–206| journal= Izv. Akad. Nauk SSSR,
Ser. Mat.| issue=30:1| year=1966}}</ref><ref>{{cite
journal|author= I. M. Vinogradov, A. A. Karatsuba| title= The
method of trigonometric sums in number theory| pages=4–30|
journal= Proc. Steklov Inst. Math.| issue=168|
year=1984}}</ref><ref>{{cite journal|author= G. I. Archipov, A. A.
Karatsuba, V. N. Chubarikov| title= Theory of multiple
trigonometric sums| journal= M.: Nauka| year=1987}}</ref> teda súm tvaru 

: <math>S = S(A) =
\sum_{x_1=1}^{P_1}\dots\sum_{x_r=1}^{P_r}e^{2\pi i
F(x_1,\dots,x_r)}</math> , ãäå <math>F(x_1,\dots,x_r) =
\sum_{t_1=1}^{n_1}\dots\sum_{t_r=1}^{n_r}\alpha(t_1,\dots,t_r)x_1^{t_1}\dots
x_r^{t_r}</math>

Kľúčovým výsledkom Karacubovej teórie je istá [[Veta (matematika)|veta]] o strednej hodnote, podobne ako je to aj vo [[Ivan Matvejevič Vinogradov|Vinogradovovej]] teórii trigonometrických súm. Tvrdenie vety je nasledovné 

: Nech <math>n_1,\dots,n_r,P_1,\dots,P_r</math> sú prirodzené čísla, <math>P_1 = \min(P_1,\dots,P_r)</math>,<math>m = (n_1+1)\dots(n_r+1)</math>. Nech ďalej <math>\Omega</math> je <math>m</math>-rozmerná kocka: <math>0 \le\alpha(t_1,\dots,t_r) < 1</math>, <math>0 \le t_1 \le n_1, \dots,0 \le t_r \le n_r</math>, v ''n''-rozmernom Euklidovom priestore a <math>J = J(P_1,\dots,P_r;n_1,\dots,n_r;K,r) =
\underset{\Omega}{\int\dots\int}|S(A)|^{2K} dA</math>. Potom pre každé <math>\tau \ge 0</math> and <math>K \ge K_{\tau} = m\tau</math> platí pre strednú hodnotu <math>J</math> nasledovný odhad: <math>J \le
K_{\tau}^{2m\tau}\varkappa^{4\varkappa^2\Delta(\tau)}2^{8m\varkappa\tau}(P_1\dots P_r)^{2K}P^{-\varkappa\Delta(\tau)}</math>, kde <math>\varkappa = n_1\nu_1+ \dots + n_r\nu_r</math>, <math>\gamma\varkappa = 1</math>, <math>\Delta(\tau) = \frac{m}{2}(1-(1-\gamma)^{\tau})</math>, <math>P = (P_1^{n_1}\dots P_r^{n_r})^{\gamma}</math>, a prirodzené čísla <math>\nu_1, \dots , \nu_r</math> sú takéto: <math>-1 < \frac{P_s}{P_1} - \nu_s \le 0</math> , <math>s= 1,\dots , r</math>. 

Táto veta o strednej hodnote spolu s [[Lemma|lemmou]] o počte priesekov s mnohorozmerným rovnobežnostenom sú základom pre Karacubov odhad veľkosti násobnej trigonometrickej sumy. Označme znakom <math>Q_0</math> [[najmenší spoločný násobok]] čísiel <math>q(t_1,\dots,t_r)</math> s podmienkou <math>t_1 + \dots t_r \ge 1</math>, pre <math>Q_0\ge P^{1/6}</math>. Potom platí odhad 

: <math>|S(A)| \le (5n^{2n})^{r\nu(Q_0)}(\tau(Q_0))^{r-1}P_1\dots
P_rQ^{-0.1\mu} + 2^{8r}(r\mu^{-1})^{r-1}P_1\dots
P_rP^{-0.05\mu}</math>,

kde <math>\tau(Q)</math> je počet deliteľov čísla <math>Q</math> a <math>\nu(Q)</math> je počet rôznych prvočíselných deliteľov čísla <math>Q</math>. 

==== Odhad Hardyho funkcie vo Waringovom probléme ====
Na základe <math>p</math>-adickej modifikácie [[Godfrey Harold Hardy|Hardy]]-[[John Edensor Littlewood|Littlewood]]-[[Srínivása Ajjangár Rámánudžan|Ramanujan]]-[[Ivan Matvejevič Vinogradov|Vinogradovovej]] metódy odhadu trigonometrických súm získal Karacuba nový odhad známej [[Godfrey Harold Hardy|Hardyho]] funkcie z tzv. Waringovho problému:<ref>{{cite journal|first=A. A.|last=Karatsuba|title=On the function G(n) in Waring's problem|pages=935–947| journal= Izv. Akad. Nauk SSSR, Ser. Math.|issue=49:5|year=1985}}</ref> 

: <math>\! G(n) < 2 n\log n + 2 n\log\log n + 12 n.</math> 

==== Viacrozmerná verzia Waringovho problému ====
A Karacuba získal aj nasledovný výsledok vo viacrozmernom analógu Waringovho problému:<ref>{{cite journal| author=G. I. Archipov, A. A.
Karatsuba|title= A multidimensional analogue of Waring's problem|
pages=521–523| journal= Dokl. Akad. Nauk SSSR| issue=295:3|
year=1987}}</ref><ref>{{cite journal|first=A.
A.|last=Karatsuba|title= Waring's problem in several dimension|
pages=5–6| journal= Mathem. Forschungs, Oberwolfach,
Tagungsbericht| issue=42| year=1988}}</ref> 

Uvažujme systém [[Rovnica (matematika)|rovníc]]  

: <math>x_1^{n-i}y_1^i + \dots + x_k^{n-i}y_k^i = N_i</math>,
<math>i = 0,1,\dots, n</math>, 

kde <math>N_i</math> sú dané celé kladné čísla rovnakého rádu <math>N_0 \to +\infty</math>. Nech ďalej <math>x_{\varkappa},y_{\varkappa}</math> sú neznáme, taktiež však kladné celé čísla. Potom uvedená sústava rovníc má riešenie ak <math>k >cn^2\log n</math> a, z druhej strany, ak <math>k < c_1n^2</math>, tak existujú čísla <math>N_i</math>, že sústava riešenie nemá.

=== Riemannova zeta-funkcia ===
==== Selbergova hypotéza ====
V roku 1984 A. Karacuba dokázal,<ref>{{cite journal| first=A. A.|
last=Karatsuba| title= On the zeros of the function ?(s) on short
intervals of the critical line| pages=569–584| journal= Izv. Akad.
Nauk SSSR, Ser. Mat.| issue=48:3| year=1984}}</ref><ref>{{cite
journal| first=A. A.| last=Karatsuba|title= The distribution of
zeros of the function ?(1/2+it)| pages=1214–1224 | journal= Izv.
Akad. Nauk SSSR, Ser. Mat.| issue=48:6|
year=1984}}</ref><ref>{{cite journal| first=A. A.| last=Karatsuba|
title= On the zeros of the Riemann zeta-function on the critical
line| pages=167–178| journal= Proc. Steklov Inst. Math.|
issue=167| year=1985}}</ref> že pre každé pevné <math>\varepsilon</math>, spĺňajúce podmienku <math>0<\varepsilon < 0.001</math> a pre dostatočne veľké <math>T</math> a <math>H = T^{a+\varepsilon}</math>, <math>a = \tfrac{27}{82} = \tfrac{1}{3} -\tfrac{1}{246}</math> je pravda, že interval <math>(T,T+H)</math> obsahuje najmenej <math>cH\ln T</math> núl funkcie <math>\zeta\Bigl(\tfrac{1}{2}+it\Bigr)</math>, kde <math>z\mapsto \zeta(z)</math> je [[Riemannova zeta funkcia|Riemannova zeta-funkcia]]. 

Uvedené tvrdenie vyslovil ako hypotézu [[Atle Selberg|A. Selberg]] v roku 1942 a sám ho aj dokázal pre prípad <math>H\ge T^{1/2+\varepsilon}</math>. Vie sa, že Selbergov a Karacubov odhad sa už nedajú zlepšiť, čo sa týka rádu rastu pri <math>T\to +\infty</math>. 

==== Rozloženie núl Riemannovej zeta-funkcii na krátkych úsekoch na kritickej priamke ====
A. Karacuba získal viaceré výsledky týkajúce sa početnosti núl Riemannovej zeta-funkcie na krátkych intervaloch ležiacich na kritickej priamke.<ref>{{cite journal| first=A. A.|
last=Karatsuba| title= On the number of zeros of the Riemann
zeta-function lying in almost all short intervals of the critical
line | pages=372–397| journal= Izv. Ross. Akad. Nauk, Ser. Mat.|
issue=56:2| year=1992}}</ref> Dokázal, že analóg Selbergovej hypotézy platí pre takmer všetky intervaly <math>(T,T+H]</math>, <math>H = T^{\varepsilon}</math>, kde <math>\varepsilon</math> je ľubovoľné malé kladné číslo. V roku 1992 objavil novú metódu skúmania núl Riemannovej zeta-funkcie na ''superkrátkych'' intervaloch na kritickej priamke, <math>(T, T+H]</math>, ktorých dĺžka <math>H</math> rastie s <math>T</math> pomalšie ako akákoľvek kladná mocnina <math>T</math>. Špeciálne dokázal, že pre každé čísla <math>\varepsilon</math>, <math>\varepsilon_{1}</math> spĺňajúce podmienky <math>0<\varepsilon, \varepsilon_{1}<1</math> platí, že takmer všetky intervaly <math>(T,T+H]</math> s <math>H\ge\exp{\{(\ln T)^{\varepsilon}\}}</math> obsahujú aspoň <math>H(\ln T)^{1-\varepsilon_{1}}</math> núl Riemannovej zeta-funkcie. Tento odhad je blízky dôležitého odhadu plynúceho z Riemannovej hypotézy.

== Referencie ==
{{Referencie|2}}

== Iné projekty ==
{{projekt|commons=Category:Anatolii Alexeevitch Karatsuba}}

{{Autoritné údaje}}

{{DEFAULTSORT:Karacuba, Anatolij Alexejevič}}

[[Kategória:Narodenia v 1937]]
[[Kategória:Úmrtia v 2008]]
[[Kategória:Ruskí matematici]]