Эдгар Гилберт

Эдгар Нельсон Гилберт (25 июля 1923 - 15 июня 2013) был американским математиком и теоретиком кодирования, давним исследователем в Bell Laboratories, чьи достижения включают границу Гилберта – Варшамова в теории кодирования, модель Гилберта – Эллиотта скачкообразных ошибок при передаче сигнала и модель Эрдеша – Реньи для случайных графиков.

• 1 Биография
• 2 Исследования
  • 2.1 Теория кодирования
  • 2.2 Теория вероятностей
  • 2.3 Случайные геометрические графики
  • 2.4 Другие публикации
• 3 Избранные публикации
• 4 Ссылки

Гилберт был молодым человеком р-н в 1923 г. в Вудхейвен, Нью-Йорк. Он получил степень бакалавра физики в Куинс-колледже Городского университета Нью-Йорка, который окончил в 1943 году. Кратко преподавал математику в Университете штата Иллинойс в Урбана-Шампейн, но затем переехал в Радиационная лаборатория при Массачусетском технологическом институте, где с 1944 по 1946 год он разработал радары антенны. Он защитил докторскую диссертацию.. В 1948 году защитил диссертацию по физике в Массачусетском технологическом институте, защитив диссертацию на тему "Асимптотическое решение проблем релаксационных колебаний" под руководством Нормана Левинсона, и устроился на работу в Bell Laboratories, где оставался до конца его карьера. Он вышел на пенсию в 1996 году.

Он умер после падения в 2013 году в Баскинг-Ридж, Нью-Джерси.

Теория кодирования

The Гилберт - Граница Варшамова, независимо доказанная в 1952 году Гилбертом и в 1957 году Ромом Варшамовым, представляет собой математическую теорему, которая гарантирует существование кодов с исправлением ошибок, которые имеют высокую скорость передачи как функцию их длина, размер алфавита и расстояние Хэмминга между кодовыми словами (параметр, который контролирует количество ошибок, которые могут быть исправлены). Основная идея состоит в том, что в максимальном коде (к которому нельзя добавить дополнительное кодовое слово) шары Хэмминга данного расстояния должны покрывать все кодовое пространство, поэтому количество кодовых слов должно быть не менее общий объем кодового пространства, деленный на объем одного шара. В течение 30 лет, до изобретения кодов Гоппа в 1982 году, коды, построенные таким образом, были лучшими из известных.

Модель Гилберта – Эллиотта, разработанная Гилберт в 1960 г. и Э. О. Эллиот в 1963 г. представляют собой математическую модель для анализа каналов передачи, в которых ошибки возникают пачками. Он утверждает, что канал может находиться в любом из двух разных состояний с разной частотой ошибок, что ошибки возникают независимо друг от друга, когда состояние известно, и что переходы от одного состояния к другому регулируются марковским цепочка. Это «очень удобно и часто используется» при анализе современных систем связи, таких как каналы передачи данных к мобильным телефонам.

Теория вероятностей

Центральное место в теории случайных графов - это модель Эрдеша – Реньи, в которой ребра выбираются случайным образом для фиксированного набора из n вершин. Он был представлен в двух формах в 1959 году Гилбертом, Полем Эрдёшем и Альфредом Реньи. В форме G (n, p) Гилберта каждое потенциальное ребро выбирается для включения в граф или исключения из него, независимо от других ребер, с вероятностью p. Таким образом, ожидаемое количество ребер равно pn (n - 1) / 2, но фактическое количество ребер может варьироваться случайным образом, и все графы имеют ненулевую вероятность быть выбранными. Напротив, в модели G (n, M), введенной Эрдешем и Реньи, граф выбирается равномерно случайным образом среди всех M-реберных графов; количество кромок фиксировано, но кромки не являются независимыми друг от друга, поскольку наличие кромки в одной позиции отрицательно коррелирует с наличием кромки в другой позиции. Хотя эти две модели в конечном итоге имеют схожие свойства, модель G (n, p) часто более удобна для работы из-за независимости ее краев.

В математике перетасовки игральные карты, модель Гилберта-Шеннона-Ридса, разработанная в 1955 году Гилбертом и Клодом Шенноном и независимо в неопубликованной работе 1981 года Джима Ридса, является распределение вероятностей перестановок набора из n элементов, которое, согласно экспериментам Перси Диаконис, точно моделирует создаваемые человеком тасовки. В этой модели колода карт разделяется в точке, выбранной случайным образом в соответствии с биномиальным распределением, и две части объединяются вместе с порядком объединения, выбранным равномерно случайным образом среди все возможные слияния. Эквивалентно, это обратная перестановка, образованная путем независимого случайного выбора каждой карты, помещать ли ее в одну из двух стопок (сохраняя исходный порядок карт в каждой стопке), а затем складывания двух стопок поверх каждой. другое.

мозаика Гилберта представляет собой математическую модель образования трещин, введенную Гилбертом в 1967 году. В этой модели трещины начинаются в наборе случайных точек со случайными ориентациями, выбранными в соответствии с Пуассоновский процесс, а затем они растут с постоянной скоростью, пока не закончатся столкновением с ранее образованными трещинами.

Случайные геометрические графы

В 1961 году Эдгар Гилберт представил сеть случайных плоскостей (чаще называемый сейчас случайным геометрическим графом (RGG) или моделью диска Гилберта), где точки размещаются на бесконечной плоскости с использованием подходящего точечного процесса, а узлы соединяются тогда и только тогда, когда они находятся в пределах некоторого критический диапазон подключения R; В качестве основного приложения для данной работы были предложены сети беспроводной связи. Из этой формулировки следует простой результат, что для стационарного точечного процесса Пуассона в ℝ с плотностью λ ожидаемая степень каждого узла - это количество точек, найденных в пределах диапазона связности, а именно πλR. Естественный вопрос, который следует задать после построения такого графика, - какова критическая средняя степень, обеспечивающая наличие гигантской компоненты; по существу этот вопрос дал начало области теории перколяции континуума. Используя процесс ветвления , Гилберт смог обеспечить начальную нижнюю границу для критической средней степени (эквивалентно критическому диапазону передачи). Выбрав произвольную точку в процессе (назовем это нулевым поколением), найдите все точки в пределах расстояния соединения R (первое поколение). Повторите процесс для всех точек в первом поколении, игнорируя любые ранее найденные, и продолжайте этот процесс, пока он не погаснет. Связанный процесс ветвления - это процесс, в котором среднее число потомков является случайной величиной Пуассона с интенсивностью, равной средней степени в исходной RGG (πλR). Отсюда для получения нижней границы необходимо применять только стандартные методы процесса ветвления. Кроме того, Гилберт показал, что переформулируя проблему в проблему перколяции связей, можно получить верхнюю границу для гигантской компоненты. Метод состоит в дискритизации плоскости таким образом, чтобы любые два узла в соседних квадратах были соединены; и позволяя каждому квадрату представлять край решетки. По построению, если есть гигантский компонент в проблеме перколяции связей, то должен быть гигантский компонент в RGG.

Другие работы

Гилберт проделал важную работу над проблемой дерева Штейнера в 1968 году, сформулировав ее таким образом, чтобы объединить ее с проблемами сетевого потока. В модели Гилберта дается потоковая сеть, в которой каждому ребру заданы как стоимость, так и пропускная способность, а также матрица величин потоков между различными парами конечных вершин; задача состоит в том, чтобы найти подсеть минимальной стоимости, пропускная способность которой достаточна для поддержки потока с заданными объемами потока между любой парой терминалов. Когда объемы потока равны, это сводится к классической проблеме дерева Штейнера.

Гилберт обнаружил массивы Костаса независимо от и в том же году, что и Костас, и также известен своей работой с Джоном Риорданом по подсчету ожерелий в комбинаторике. Он сотрудничал с Фан Чанг, Роном Грэмом и Джеком ван Линтом над разделением прямоугольников на меньшие прямоугольники.