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

Освіта і робота

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

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

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

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

Премії та звання

• 1981: Премія ім. П. Л. Чебишева АН СРСР
• 2001: Премія ім. І. М. Виноградова РАН
• 1999: Заслужений діяч науки РФ

Ранні роботи з інформатики

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

Автомати

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

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

Ці дві теореми стали основою курсової роботи Карацуби 4-го курсу«Про одну проблеми з теорії автоматів»яка була відзначена похвальним відгуком (тобто, не дуже високо) на конкурсі студентських робіт механіко-математичного факультету МДУ ім. Ломоносова в 1958 році. Стаття була подана Карацубой в журнал Успіхи математичних наук у грудні 1958 року, а опублікована лише в червні 1960 року. Однак, до 2009 року цей результат Карацуби, який згодом став називатися теоремою Мура-Карацуби, є єдиним точним (єдино точний нелінійний порядок оцінки) нелінійним результатом як в теорії автоматів, так і в аналогічних задачах теорії складності обчислень.

Швидкі алгоритми

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

Комментарии