Эдгар Нельсон Гилберт (25 июля 1923 - 15 июня 2013) был американским математиком и теоретиком кодирования , давним исследователем в Bell Laboratories , чьи достижения включают границу Гилберта-Варшамова в теории кодирования , модель Гилберта-Эллиотта пакетных ошибок в сигнале. передача и модель Эрдеша-Реньи для случайных графов .
Гилберт родился в 1923 году в Вудхейвене, штат Нью-Йорк . Он учился на бакалавриате по физике в Куинс-колледже Городского университета Нью-Йорка , который окончил в 1943 году. Некоторое время он преподавал математику в Университете Иллинойса в Урбане-Шампейне, но затем перешел в радиационную лабораторию Массачусетского технологического института , где проектировал радиолокационные антенны с 1944 по 1946 год. Он защитил докторскую диссертацию. получил степень доктора физики в Массачусетском технологическом институте в 1948 году, защитив диссертацию под названием « Асимптотическое решение проблем релаксационных колебаний» под руководством Нормана Левинсона , и устроился на работу в Bell Laboratories , где оставался до конца своей карьеры. Он вышел на пенсию в 1996 году. [1] [2]
Он умер после падения в 2013 году в Баскин-Ридж, штат Нью-Джерси . [3]
Граница Гилберта -Варшамова , независимо доказанная в 1952 году Гилбертом и в 1957 году Ромом Варшамовым, [G52] [4] представляет собой математическую теорему, гарантирующую существование кодов с исправлением ошибок , которые имеют высокую скорость передачи в зависимости от их длины. , размер алфавита и расстояние Хэмминга между кодовыми словами (параметр, контролирующий количество ошибок, которые можно исправить). Основная идея состоит в том, что в максимальном коде (к которому нельзя добавить дополнительное кодовое слово) шары Хэмминга заданного расстояния должны покрывать все кодовое пространство, поэтому количество кодовых слов должно, по крайней мере, равняться общему объему разделенного кодового пространства. по объему одного шара. [5] В течение 30 лет, до изобретения кодов алгебраической геометрии в 1982 году, коды, построенные таким образом, были лучшими из известных. [6]
Модель Гилберта -Эллиотта , разработанная Гилбертом в 1960 году и Э.О. Эллиотом в 1963 году, [G60] [7] представляет собой математическую модель для анализа каналов передачи, в которых ошибки возникают пакетно. Он утверждает, что канал может находиться в одном из двух разных состояний с разной частотой ошибок, что ошибки возникают независимо друг от друга, когда состояние известно, и что переходы от одного состояния к другому управляются цепью Маркова . Он «очень удобен и часто используется» при анализе современных систем связи, таких как каналы передачи данных на мобильные телефоны. [8]
Центральное место в теории случайных графов занимает модель Эрдеша-Реньи , в которой ребра выбираются случайным образом для фиксированного набора из n вершин. Он был представлен в двух формах в 1959 году Гилбертом, Полем Эрдешем и Альфредом Реньи . [G59] [9] В форме Гилберта G ( n , p ) каждое потенциальное ребро выбирается для включения в граф или исключения из него, независимо от других ребер, с вероятностью p . Таким образом, ожидаемое количество ребер равно pn ( n − 1)/2 , но фактическое количество ребер может меняться случайным образом, и все графы имеют ненулевую вероятность быть выбранными. Напротив, в модели G ( n , M ) , представленной Эрдёшем и Реньи, граф выбирается равномерно случайным образом среди всех M -реберных графов; количество ребер фиксировано, но ребра не являются независимыми друг от друга, поскольку наличие ребра в одной позиции отрицательно коррелирует с наличием ребра в другой позиции. Хотя эти две модели в конечном итоге имеют схожие свойства, с моделью G ( n , p ) часто удобнее работать из-за независимости ее ребер. [10]
В математике перетасовки игральных карт модель Гилберта -Шеннона-Ридса , разработанная в 1955 году Гилбертом и Клодом Шенноном [G55] и независимо в неопубликованной работе 1981 года Джимом Ридсом, представляет собой распределение вероятностей перестановок набора из n предметов . который, согласно экспериментам Перси Диакониса , точно моделирует человеческую перетасовку винтовок. В этой модели колода карт разбивается в точке, выбранной случайно в соответствии с биномиальным распределением , и две части объединяются с порядком слияния, выбранным равномерно случайным образом среди всех возможных слияний. Эквивалентно, это обратная перестановка, образованная путем независимого случайного выбора для каждой карты, следует ли положить ее в одну из двух стопок (сохраняя исходный порядок карт в каждой стопке), а затем складывания двух стопок поверх каждой. другой. [11]
Тесселяции Гилберта — это математическая модель образования трещин , введенная Гилбертом в 1967 году. [G67] В этой модели трещины начинаются в наборе случайных точек со случайной ориентацией, выбранной в соответствии с процессом Пуассона , а затем растут с постоянной скоростью до тех пор, пока они заканчиваются, набегая на ранее образовавшиеся трещины. [12]
В 1961 году Гилберт представил сеть случайных плоскостей [13] (сейчас чаще называемую случайным геометрическим графом (RGG) или моделью диска Гилберта), в которой точки размещаются на бесконечной плоскости с использованием подходящего точечного процесса, и узлы соединяются, если и только если они находятся в пределах некоторого критического диапазона связи R; В качестве основного приложения для данной работы были предложены сети беспроводной связи. Из этой формулировки следует простой результат: для стационарного точечного процесса Пуассона в ℝ 2 с плотностью λ ожидаемая степень каждого узла равна числу точек, найденных в пределах диапазона связности, а именно πλR 2 . После построения такого графика возникает естественный вопрос: какова критическая средняя степень, обеспечивающая наличие гигантской компоненты; по существу этот вопрос породил область теории перколяции континуума . Используя процесс ветвления, Гилберт смог предоставить начальную нижнюю границу критической средней степени (что эквивалентно критическому диапазону передачи). Выбрав произвольную точку в процессе (назовем это нулевым поколением), найдите все точки на расстоянии соединения R (первое поколение). Повторите процесс для всех точек первого поколения, игнорируя все найденные ранее, и продолжайте этот процесс, пока они не исчезнут. Соответствующий ветвящийся процесс — это процесс, в котором среднее число потомков является случайной величиной Пуассона с интенсивностью, равной средней степени в исходной RGG (πλR 2 ). Отсюда для получения нижней границы необходимо применять только стандартные методы процесса ветвления. Более того, Гилберт показал, что, переформулировав проблему в задачу о перколяции связей, можно получить верхнюю границу гигантского компонента. Метод состоит в дискретизации плоскости таким образом, чтобы любые два узла в соседних квадратах были соединены; и позволяя каждому квадрату представлять собой край решетки. По своей конструкции, если в проблеме просачивания связей есть гигантская компонента, то должна быть гигантская компонента и в РГГ.
Гилберт проделал важную работу над проблемой дерева Штейнера в 1968 году, сформулировав ее таким образом, чтобы объединить ее с задачами сетевых потоков . [G68] В модели Гилберта дана потоковая сеть , в которой каждому ребру заданы как стоимость, так и пропускная способность, а также матрица величин потоков между различными парами конечных вершин; задача состоит в том, чтобы найти подсеть минимальной стоимости, мощности которой достаточны для поддержания потока с заданными объемами потоков между любой парой терминалов. Когда все объемы потоков равны, это сводится к классической проблеме дерева Штейнера. [14]
Гилберт открыл массивы Костаса независимо и в тот же год, что и Костас , [G65] [15] , а также известен своей работой с Джоном Риорданом по подсчету ожерелий в комбинаторике . [16] Он сотрудничал с Фэном Чунгом , Роном Грэмом и Джеком ван Линтом над разбиением прямоугольников на меньшие прямоугольники. [КГГ]