Метод «разделяй и властвуй»

Среда, 16 октября 2013
ФМЛ 239, Актовый зал

Описание

Основные идеи метода; алгоритм Карацубы: умножение $n$-битовых чисел за $O(n^{1.6})$; основная теорема о рекуррентных соотношениях; бинарный поиск; алгоритм Штрассена умножения матриц; сортировка слиянием.