Эдгар Нельсон Гилберт (25 июля 1923-15 июня 2013) был американским математиком и теоретиком кодирования , давним исследователем в Bell Laboratories, чьи достижения включают ограничение Гилберта – Варшамова в теории кодирования , модель Гилберта – Эллиотта взрывных ошибок в сигнале. трансмиссия и модель Эрдеша – Реньи для случайных графов .
биография
Гилберт родился в 1923 году в Вудхейвене, штат Нью-Йорк . Он сделал свои студенческие исследования в области физики в Квинс Колледж, Университет города Нью - Йорка , который окончил в 1943 г. Он преподавал математику кратко в Университете штата Иллинойс в Урбана-Шампань , но затем переехал в Радиационной лаборатории в Массачусетском технологическом институте , где он проектировал радиолокационные антенны с 1944 по 1946 год. Он защитил кандидатскую диссертацию. В 1948 году защитил диссертацию по физике в Массачусетском технологическом институте, защитив диссертацию на тему « Асимптотическое решение проблем релаксационных колебаний» под руководством Нормана Левинсона , и устроился на работу в Bell Laboratories, где оставался до конца своей карьеры. Он вышел на пенсию в 1996 году. [1] [2]
Он умер после падения в 2013 году в Баскинг-Ридж, штат Нью-Джерси . [3]
Исследовать
Теория кодирования
Гилберта-Варшамова , независимо доказана в 1952 году Гилберта и в 1957 году Rom Варшамова, [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 ). Отсюда для получения нижней границы необходимо применять только стандартные методы процесса ветвления. Более того, Гилберт показал, что, перефразируя проблему на проблему перколяции связей, можно получить верхнюю границу для гигантской компоненты. Метод состоит в дискритизации плоскости таким образом, чтобы любые два узла в соседних квадратах были соединены; и позволяя каждому квадрату представлять край решетки. По построению, если есть гигантский компонент в проблеме перколяции связей, то должен быть гигантский компонент в RGG.
Прочие взносы
Гилберт проделал важную работу над проблемой дерева Штейнера в 1968 году, сформулировав ее таким образом, чтобы объединить ее с проблемами сетевого потока . [G68] В модели Гилберта каждому дается сеть потоков, в которой каждому ребру заданы как стоимость, так и пропускная способность, а также матрица величин потоков между различными парами конечных вершин; задача состоит в том, чтобы найти подсеть минимальной стоимости, пропускная способность которой достаточна для поддержки потока с заданными объемами потока между любой парой терминалов. Когда объемы потока все равны, это сводится к классической проблеме дерева Штейнера. [14]
Гилберт открыл массивы Костаса независимо и в том же году, что и Костас , [G65] [15], а также известен своей работой с Джоном Риорданом по подсчету ожерелий в комбинаторике . [16] Он сотрудничал с Фань Чангом , Роном Грэхемом и Джеком ван Линтом над разделением прямоугольников на меньшие прямоугольники. [CGG]
Избранные публикации
G52. | Гилберта, Е. Н. (1952), "Сравнение сигналов алфавитов", Bell System Technical Journal , 31 (3): 504-522, DOI : 10.1002 / j.1538-7305.1952.tb01393.x |
G55. | Гилберт, EN (1955), Теория перетасовки , Технический меморандум, Bell Laboratories. Цитируется Bayer & Diaconis (1992) . [11] |
G59. | Gilbert, EN (1959), "Случайные графы", Анналы математической статистики , 30 (4): 1141-1144, DOI : 10,1214 / АОМ / 1177706098 |
G60. | Гилберт, EN (1960), "Пропускная способность канала импульсного шума", Bell System Technical Journal , 39 (5): 1253–1265, DOI : 10.1002 / j.1538-7305.1960.tb03959.x |
G65. | Гилберт, EN (1965), «Латинские квадраты, не содержащие повторяющихся биграмм», SIAM Review , 7 (2): 189–198, Bibcode : 1965SIAMR ... 7..189G , doi : 10.1137 / 1007035 , JSTOR 2027267 |
G67. | Гилберт, EN (1967), «Случайные плоские сети и игольчатые кристаллы», в Noble, B. (ed.), Applications of Undergraduate Mathematics in Engineering , New York: Macmillan |
G68. | Гилберта, Е. Н. (1968), "Steiner минимальные деревья", SIAM журнал по прикладной математике , 16 (1): 1-29, DOI : 10,1137 / 0116001 , JSTOR 2099400 |
CGG. | Чанг, ФРГ ; Гилберт, EN; Graham, RL ; Ширер, JB; ван Линт, JH (1982), "МОЗАИЧНЫЕ прямоугольники с прямоугольниками" (PDF) , математика Журнал , 55 (5): 286-291, DOI : 10,2307 / 2690096 , JSTOR 2690096 |
Рекомендации
- ^ Биография автора из Borst, SC; Коффман, EG ; Гилберт, EN; Whiting, PA; Винклер, PM (2000), «Распределение временных интервалов в беспроводной TDMA», в Геленбе, Э. (ред.), Оценка производительности системы: методологии и приложения , CRC Press, стр. 203–214, ISBN 978-0-8493-2357-7
- ↑ Эдгар Нельсон Гилберт в проекте « Математическая генеалогия»
- ^ «Некролог Эдгара Нельсона Гилберта: Просмотреть некролог Эдгара Гилберта от Star-Ledger» . Obits.nj.com . Проверено 21 июня 2013 .
- ^ Варшамов Р. Р. (1957) "Оценка числа сигналов в кодах с исправлением ошибок", Докл. Акад. АН СССР , 117 : 739–741.
- ^ Мун, Тодд К. (2005), «Граница Гилберта – Варшамова», Кодирование с исправлением ошибок: математические методы и алгоритмы , John Wiley and Sons, стр. 409–410, ISBN 978-0-471-64800-0
- ^ Хаффман, Уильям Кэри; Плесс, Вера (2003), «Пересмотр границы Гилберта – Варшамова», Основы кодов с исправлением ошибок , Cambridge University Press, стр. 541 , ISBN 978-0-521-78280-7
- ^ Эллиотт, EO (1963), "Оценки частоты ошибок для кодов на каналах пакетного шума", Bell System Technical Journal , 42 (5): 1977–1997, doi : 10.1002 / j.1538-7305.1963.tb00955.x
- ^ Петрауш, Стефан; Сёргель, Вольфганг; Кауп, Андре (2004), «Последовательно подключенные каналы: сценарий приложения пропускной способности и потокового видео для раздельного и совместного кодирования каналов», 5-я Международная конференция ITG по кодированию источников и каналов (SCC): 14–16 января 2004 г., Эрланген: запись конференции , Маргрет Шнайдер, стр. 271–278, ISBN 978-3-8007-2802-2
- ^ Erdős, P .; Реньи, А. (1959), "О случайных графах I" (PDF) , Publicationes Mathematicae , 6 : 290–297
- ^ Уоттс, Дункан Дж. (2003), Маленькие миры: динамика сетей между порядком и случайностью , Принстонские исследования сложности, Princeton University Press, стр. 36–37, ISBN 978-0-691-11704-1
- ^ а б Байер, Дэйв ; Диаконис, Перси (1992), «Отслеживание перемещения ласточкиного хвоста к его логову», Annals of Applied Probability , 2 (2): 294–313, doi : 10.1214 / aoap / 1177005705 , JSTOR 2959752
- ^ Серый, NH; Андерсон, JB; Дивайн, JD; Kwasnik, JM (1976), " О топологических свойствах случайных трещин сетей", Математическая геологии , 8 (6): 617-628, DOI : 10.1007 / BF01031092 , S2CID 119949515; Шрайбер, Томаш; Соя, Наталья (2010). "Предельная теория для плоских мозаик Гилберта". arXiv : 1005.0023 [ math.PR ].
- ^ Гилберт, Эдвард N (1961). «Случайные плоские сети». Журнал Общества промышленной и прикладной математики . 9 (4): 533–543. DOI : 10.1137 / 0109045 .
- ^ Хван, Франк; Ричардс, Дана; Винтер, Павел (1992), Проблема дерева Штейнера , Анналы дискретной математики (математические исследования Северной Голландии), 53 , Elsevier, стр. 80–83, ISBN 978-0-444-89098-6
- ↑ Независимое открытие массивов Костаса , Аарон Стерлинг, 9 октября 2011 г.
- ^ Гарднер, Мартин (2001), Колоссальная книга по математике: классические головоломки, парадоксы и проблемы: теория чисел, алгебра, геометрия, вероятность, топология, теория игр, бесконечность и другие темы развлекательной математики , WW Norton & Company, стр. . 18, ISBN 978-0-393-02023-6