Про знаменитості
Карацуба Анатолій Олексійович: биография
перемножити дваn-значних числа звичайним шкільним способом «у стовпчик», ми маємо оцінку зверхуM(n) =O(n). У 1956 р. А. М. Колмогоров висловив гіпотезу, що нижня оцінкаM(n) при будь-якому методі множення є також величина порядкуn, тобто не можна обчислити добуток двохn-значних чисел швидше, ніж заnоперацій (так званагіпотезаnКолмогорова). На правдоподібністьгіпотезиnвказував той факт, що за весь час існування математики до того моменту люди виробляли множення зі складністю порядкуO(n), і якби був більш швидкий метод множення, то він, ймовірно, вже був би знайдений.
У 1960 році Анатолій Карацуба знайшов новий метод множення двохn-значних чисел, відомий тепер як алгоритм множення Карацуби, з оцінкою складності
і тим самим спростувавгіпотезуn. Цей результат був розказаний А. Карацубой на семінарі А. Н. Колмогорова в МДУ в 1960 р., після чого семінар був закритий Колмогоровим, який був розчарований тим фактом, що його гіпотеза виявилася невірною. Перша стаття з описом цього методу була підготовлена ??самим Колмогоровим, де він представив два різних і непов'язаних один з одним результату двох своїх учнів, і хоча в статті Колмогоров чітко зазначив, що одна теорема (не пов'язана зі швидким множенням) належить Ю. Офману, а інша теорема (з першим в історії швидким множенням) належить А. Карацубе, ця публікація, одночасно двох авторів, надовго збила з пантелику читачів, які вважали, що обидва автори зробили внесок у створення швидкого множення і навіть називали цей метод двома іменами. Метод Карацуби згодом був названий «розділяй і володарюй». Інші назви цього методу, залежно від сфери застосування -Binary Splitting(двійкове розбиття),принцип дихотоміїі т. п.
Згодом на основі цієї ідеї А. Карацуби були побудовані тисячі швидких алгоритмів, найвідомішими з яких є його безпосередні узагальнення, такі як метод множення Шенхаге-штрассе і метод матричного множення штрассе. В останні роки назвуDivide and Conquerвикористовується для дій з подразбіеніем завдання на частини, і це вже не завжди пов'язано зі швидкими обчислювальними алгоритмами.
Французький математик і філософ Жан-Поль Делаїних назвав метод множення Карацуби«одним з найбільш корисних результатів математики».
Алгоритм Анатолія Карацуби запроваджено практично у всі сучасні комп'ютери, і не тільки в якості software, але і як hardware.
Основні дослідження
У своїй статті «Про математичних роботах професора Карацуби», присвяченої 60-річному ювілею О. А. Карацуби, його учні Г. І. Архипов і В. Н. Чубарик так описують особливості наукових робіт А. А. Карацуби:
Основні дослідження А. А. Карацуби опубліковані більш ніж у 160 наукових статтях та монографіях. .
Тригонометричні суми та тригонометричні інтеграли
А. А. Карацуба побудував новийp-адічеськімі метод а теорії тригонометричних сум. Отримані ним оцінки так званихL-сум виду
призвели до нових кордонів нулівL-рядів Діріхле по модулю, рівному ступені простого числа, до висновку асимптотичної формули для числа варінговского порівняння виду
вирішення проблеми розподілу дробових часток многочлена з цілими коефіцієнтами по модулюpk. А. А. Карацуба перший реалізує вp-адічеськімі формі «принцип вкладення» Ейлера-Виноградова і будуєp-адічеськімі аналогu- чисел Виноградова при оцінці числа рішень порівняння варінговского типу.
Нехай
причому
деp- просте число. А. А. Карацуба довів, що в цьому випадку для будь-якого натурального числа існуєp0=p0(n) таке, що для будь-якогоp0>p0(n) всяке натуральне числоNпредставимо у вигляді (1) при, а приt<rіснуютьNтакі, що порівняння (1) нерозв'язною.
