Карта → город
Мюррей-Хилл (Bell Labs)
5 событий · 8 линий истории математики
-
11948Шеннон: вероятность становится информацией
Клод Шеннон определяет количество информации через энтропию распределения и доказывает, что у канала связи есть точная пропускная способность. Вероятность из инструмента расчёта шансов превращается в меру незнания.
-
21965БПФ: алгоритм, опередивший потребность
Ускорение в пятьдесят тысяч раз на миллионе точек — не «быстрее», а «стало возможным». Полный алгоритм есть у Гаусса в работе 1805 года, написанной раньше мемуара Фурье и пролежавшей непрочитанной сто восемнадцать лет: он опередил не публикацию, а потребность.
-
31988Добеши: всплеск, у которого есть и гладкость, и место
Фурье знает частоту, но не знает места; Хаар знает место, но не бывает гладким. Добеши строит ортонормированные базисы, у которых есть и то и другое, — ценой того, что записать их формулой нельзя.
-
4доклад на симпозиуме FOCS — ноябрь 1994; журнальная версия — 1997Шор: разложение на множители за полином — но не на этой машине
Разложить число на множители — то же самое, что найти период ряда его степеней, а искать период умеет преобразование Фурье. Питер Шор собрал из этого квантовый алгоритм, которому взлом ключа стоит куба его длины вместо астрономической величины. Машины нужного размера нет и, возможно, не будет — но записанное сегодня можно расшифровать через двадцать лет.
-
51996Скетчи: сосчитать, не запоминая
Данных больше, чем места, куда их положить: поток идёт мимо, и второй раз посмотреть нельзя. Точный подсчёт доказуемо невозможен, приближённый — требует логарифма памяти: миллиард различных элементов считается с ошибкой в два процента в полутора килобайтах.