Карацуба Анатолій Олексійович

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Карацуба Анатолій Олексійович
рос. Анатолий Алексеевич Карацуба
A.A.Karatsuba.jpg
Народився 31 січня 1937(1937-01-31)[1]
Грозний, РРФСР, СРСР[1]
Помер 28 вересня 2008(2008-09-28)[1] (71 рік)
Москва, Росія
Країна Flag of Russia.svg Росія
Flag of the Soviet Union.svg СРСР
Діяльність математик, викладач університету
Alma mater механіко-математичний факультет МДУd і МДУ[2]
Галузь математичний аналіз, теорія чисел, фізика і Теорія алгоритмів
Заклад Математичний інститут імені Стєклова і МДУ
Науковий ступінь доктор фізико-математичних наук
Науковий керівник Nikolay Korobovd
Відомі учні Sergei Mikhailovich Voronind
Діти Yekaterina Karatsubad
Нагороди
Заслужений діяч науки Російської Федерації

CMNS: Карацуба Анатолій Олексійович у Вікісховищі

Анатолій Олексійович Карацу́ба (31 січня 1937, Грозний — 28 вересня 2008, Москва) — радянський і російський математик. Творець першого швидкого методу в історії математики — методу множення великих чисел[3][4] (множення Карацуби).

Навчання і робота[ред. | ред. код]

А. А. Карацуба — випускник середньої школи

Анатолій Карацуба навчався в 1944—1954 роках у середній чоловічій школі № 6 міста Грозного і закінчив її зі срібною медаллю. Вже в ранні роки він виявив виняткові здібності до математики, розв'язуючи в молодших класах завдання, які давали в математичному гуртку старшокласникам.

1959 року закінчив механіко-математичний факультет МДУ ім. Ломоносова. 1962 року він став кандидатом фізико-математичних наук з дисертацією «Раціональні тригонометричні суми спеціального вигляду та їх застосування» (науковий керівник — Н. М. Коробов), і почав працювати на факультеті в МДУ. 1966 року він захистив докторську дисертацію «Метод тригонометричних сум і теореми про середнє» і став науковим співробітником Математичного інституту АН СССР.

Від 1983 року був провідним фахівцем у галузі теорії чисел в СРСР і Росії, і завідувачем відділу теорії чисел в МІАН, професором кафедри теорії чисел МДУ від 1970 року і професором кафедри математичного аналізу МДУ (створена 1962 року) від 1980 року. Його дослідницькі інтереси включали тригонометричні суми і тригонометричні інтеграли, дзета-функцію Рімана, характери Діріхле, скінченні автомати, ефективні алгоритми.

Карацуба був науковим керівником 15 аспірантів, які отримали ступінь кандидата наук; семеро з них стали згодом докторами наук.

Премії і звання[ред. | ред. код]

Ранні праці з інформатики[ред. | ред. код]

Студентом МДУ ім. Ломоносова, А. О. Карацуба брав участь у роботі семінару А. М. Колмогорова і розв'язав дві поставлені Колмогоровим задачі, що дало імпульс розвитку теорії автоматів і поклало початок новому напрямку в математиці — теорії швидких алгоритмів.

Автомати[ред. | ред. код]

У статті Едварда Мура «Умоглядні експерименти на послідовних машинах»[5] -автомат (або машина) визначається як пристрій, що має станів, вхідних символів і вихідних символів. Доводиться дев'ять теорем про структуру та експерименти з . Пізніше такі -машини почали називати автоматами Мура. Наприкінці статті, у главі «Нові проблеми» Мур формулює задачу про поліпшення оцінок отриманих ним у теоремах 8 і 9:

Теорема 8 (Мур). Нехай задано довільну -машину , таку, що кожні два її стани відрізняються один від іншого, тоді існує експеримент довжини , який встановлює (знаходить) стан в кінці цього експерименту.

1957 року Карацуба довів дві теореми, які повністю вирішили проблему Мура з поліпшення оцінки довжини експерименту в його Теоремі 8.

Теорема A (Карацуба). Якщо  — -машина така, що кожні два два її стани відрізняються один від дного, то існує експеримент довжини не більше, ніж , за допомогою якого можна встановити (знайти) стан в кінці експерименту.
Теорема B (Карацуба). Існує -машина, кожні два стани якої взаєморізні, така, що довжина найкоротшого експерименту, що встановлює стан машини в кінці експерименту, дорівнює .

Швидкі алгоритми[ред. | ред. код]

Швидкі алгоритми — галузь обчислювальної математики, яка вивчає алгоритми обчислення заданої функції з заданою точністю з застосуванням якомога меншої кількості бітових операцій. Вважається, що числа записано в двійковій системі числення, знаки якої 0 і 1 називають бітами. Одна бітова операція визначається як запис знаків 0, 1, плюс, мінус, дужка; додавання, віднімання і множення двох бітів. Перші постановки задач про бітову складність обчислення належать А. М. Колмогорову. Складність алгоритму множення визначається як кількість бітових операцій, достатня для обчислення добутку двох n-значних чисел за допомогою такого алгоритму.

Перемножуючи два n-значних числа звичайним шкільним способом «у стовпчик», ми маємо оцінку зверху . 1956 року А. М. Колмогоров висловив гіпотезу, що нижня оцінка будь-якого методу множення є також величина порядку , тобто не можна обчислити добуток двох n-значних чисел швидше, ніж за операцій (так звана «гіпотеза »). На правдоподібність гіпотези вказував той факт, що за весь час існування математики до того моменту люди виконували множення зі складністю порядку , і, якби був швидший метод множення, то його, імовірно, вже було б знайдено.

1960 року на механіко-математичному факультеті МДУ почав працювати під керівництвом А. М. Колмогорова семінар з математичних питань кібернетики, де було сформульовано «гіпотезу » і поставлено кілька задач про оцінку складності інших подібних обчислень. Анатолій Карацуба, сподіваючись отримати нижню оцінку величини , знайшов новий метод множення двох n-значних чисел, відомий тепер як множення Карацуби, з оцінкою складності

Таким чином він спростував гіпотезу , про що повідомив Колмогорову після чергового засідання семінару. На наступному засіданні семінару цей метод розказав сам Колмогоров, і семінар припинив свою роботу[6]. Першу статтю з описом множення Карацуби підготував Колмогоров, подавши в ній два різних, не пов'язаних між собою результати двох своїх учнів[7].

Хоча в статті Колмогоров чітко зазначив, що одна теорема (не пов'язана зі швидким множенням) належить Ю. Офману, а інша теорема (з першим в історії швидким множенням) належить А. Карацубі, однак, ця публікація двох авторів надовго збила з пантелику читачів, які вважали, що обидва автори відкрили метод швидкого множення разом, і навіть називали цей метод іменами обох дослідників. Метод Карацуби згодом узагальнено за допомогою парадигми «розділяй та володарюй», іншими важливими прикладами якої є метод двійкового розбиття[en], двійковий пошук, метод бісекції та інші.

Згодом на основі цієї ідеї А. Карацуби[6][8][9] побудовано багато швидких алгоритмів, найвідомішими з яких є його безпосередні узагальнення, такі як метод множення Шьонгаґе — Штрассена[en], метод матричного множення Штрассена[10], метод швидкого перетворення Фур'є. Французький математик і філософ Жан-Поль Делає[en] назвав метод множення Карацуби «одним з найкорисніших результатів математики»[11]. Алгоритм Анатолія Карацуби впроваджено практично в усіх сучасних комп'ютерах не лише на програмному, а й на апаратному рівні[джерело?].

Основні дослідження[ред. | ред. код]

У своїй статті «Про математичні роботи професора Карацуби»[12], присвяченій 60-річному ювілею А. О. Карацуби, його учні Г. І. Архипов і В. М. Чубариков[ru] так описують особливості наукових робіт А. О. Карацуби :

«При викладі праць чудових учених природно виділити якісь характерні і яскраві риси їхньої творчості. Такими визначальними рисами в науковій діяльності професора Карацуби є комбінаторна винахідливість, ґрунтовність і певна завершеність результатів.»

Основні дослідження А. О. Карацуби опубліковані більш ніж у 160 наукових статтях і монографіях.[13][14][15][16]

Тригонометричні суми та тригонометричні інтеграли[ред. | ред. код]

p-адичний метод[ред. | ред. код]

А. О. Карацуба побудував новий -адичний метод у теорії тригонометричних сум. Отримані ним оцінки[17] привели до нових меж нулів -рядів Діріхле за модулем, рівним степеню простого числа, до виведення асимптотичної формули для числа варінговського порівняння вигляду

вирішення проблеми розподілу дробових часток многочлена з цілими коефіцієнтами за модулем . А. О. Карацуба перший реалізує[18] в -адичній формі «принцип вкладення» Ейлера — Виноградова і будує -адичний аналог -чисел Виноградова при оцінці числа розв'язків порівняння варінговського типу.

Нехай

причому

де  — просте число. А. О. Карацуба довів, що в цьому випадку для будь-якого натурального числа існує таке, що для будь-якого будь-яке натуральне число подаване у вигляді (1) при , а при існують такі, що порівняння (1) нерозв'язне.

Цей новий підхід, знайдений А. О. Карацубою, привів до нового -адичного доведення теореми про середнє І. М. Виноградова, яка грає центральну роль у методі тригонометричних сум Виноградова.

Ще одним елементом -адичного методу А. О. Карацуби є перехід від неповних систем рівнянь до повних за рахунок локальної -адичної зміни невідомих.[19][20]

Нехай  — довільне натуральне число, , і ціле число визначається нерівностями . Розглянемо систему рівнянь

А. О. Карацуба довів, що для числа розв'язків цієї системи рівнянь при справедлива оцінка

Для неповних систем рівнянь, у яких змінні пробігають числа з малими простими дільниками, А. О. Карацуба застосував мультиплікативний зсув змінних. Це призвело до якісно нової оцінки тригонометричних сум і нової теореми про середнє для таких систем рівнянь.

Примітки[ред. | ред. код]

  1. а б в Deutsche Nationalbibliothek, Staatsbibliothek zu Berlin, Bayerische Staatsbibliothek et al. Record #1024789535 // Німецька нормативна база даних — 2012—2016.
  2. Математичний генеалогічний проєкт — 1997.
  3. С. А. Гриценко, Е. А. Карацуба, М. А. Королëв, И. С. Резвякова, Д. И. Толев, М. Е. Чанга. Научные достижения Анатолия Алексеевича Карацубы. Математика и информатика, 1. // К 75-летию со дня рождения Анатолия Алексеевича Карацубы. — Совр. пробл. матем. — 2012. — Т. 16. — С. 7–30.
  4. Кнут Д. Искусство программирования для ЭВМ. — 1-е изд. — М. : Мир (издательство), 1977. — Т. 2. — С. 315.
  5. Moore, E. F. (1956). Gedanken-experiments on Sequential Machines.. Automata Studies, Annals of Mathematical Studies, Princeton University Press, Princeton, N.J., (34): 129–153. 
  6. а б Карацуба А. А. Сложность вычислений // Тр. МИАН. — 1995. — Т. 211. — С. 186–202.
  7. Карацуба А., Офман Ю. Умножение многозначных чисел на автоматах // Доклады Академии Наук СССР. — 1962. — Т. 145, № 2.
  8. Karacuba A. Berechnungen und die Kompliziertheit von Beziehungen. — Elektronische Informationsverarbeitung und Kybernetik, 1975. — Bd. 11.
  9. Дональд Кнут. Искусство программирования. — 3-е изд. — 2007. — Т. 2. Получисленные алгоритмы. — P. 832. — ISBN 0-201-89684-2..
  10. Schönhage A., Strassen V. Schnelle Multiplikation großer Zahlen // Computing. — 1971. — № 7. — P. 281—292.
  11. Jean-Paul Delahaye. Mathematiques et philosophie : [фр.] // Pour la Science. — 2000. — № 277. — P. 100—104.
  12. Г. И. Архипов; В. Н. Чубариков. О математических работах профессора А. А. Карацубы // Труды МИАН. — 1997. — Т. 218. — С. 7—19.
  13. Карацуба А. А. (1975). Основы аналитической теории чисел.. М.: Наука. 
  14. Архипов Г. И., Карацуба А. А., Чубариков В. Н. (1987). Теория кратных тригонометрических сумм.. М.: Наука. 
  15. Воронин С. М., Карацуба А. А. (1994). Дзета-функция Римана.. М.: Физматлит. 
  16. Karatsuba A. A. (1995). Complex analysis in number theory.. London, Tokyo: C.R.C. 
  17. Карацуба, А. А. (1961). Оценки тригонометрических сумм особого вида и их приложения. Докл. АН СССР (137:3): 513–514. 
  18. Карацуба, А. А. (1962). Проблема Варинга для сравнения по модулю, равному степени простого числа. Вестн. МГУ (1:4): 28–38. 
  19. Карацуба, А. А. (1965). Об оценке числа решений некоторых уравнений. Докл. АН СССР (165:1): 31–32. 
  20. Карацуба, А. А. (1965). Системы сравнений и уравнения Варинговского типа. Докл. АН СССР (1:4): 274–276. 

Посилання[ред. | ред. код]