|
Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://al.cs.msu.su/static/seminars/catfl/reports/019_chinatheo/abstract.html
Дата изменения: Fri Apr 28 00:15:35 2006 Дата индексирования: Mon Oct 1 20:09:48 2012 Кодировка: koi8-r |
Александр Алексеев, 25.04.2006
Доклад состоит из 2х частей. В первой части доклада освещена оригинальная формулировка Китайской теоремы об остатках, альтернативная (с доказательством) и обобщенная. Также изложены области применения данной теоремы. Во второй части рассмотрен метод умножения двух чисел (или полиномов), которой в отличии от стандартного способа, уменьшает сложность умножения до O(nlogn) при помощи быстрого преобразования Фурье (Fourier Jean Baptiste Joseph). Рассмотрен алгоритм быстрого преобразование Фурье, обоснование его сложности и графическое отображение эффективности алгоритма.
Материалы к докладу: