Эдгар Гилберт - Edgar Gilbert

Для Киттитянского игрока в крикет см. Эдгар Гилберт (игрок в крикет).

Эдгар Нельсон Гилберт (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]

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

Центральное место в теории случайные графы это Модель Эрдеша – Реньи, в котором ребра выбираются случайным образом для фиксированного набора п вершины. Он был представлен в двух формах в 1959 году Гилбертом: Пол Эрдёш, и Альфред Реньи.[G59][9] У Гилберта грамм(п, п) форме каждое потенциальное ребро выбирается для включения в граф или исключения из него, независимо от других ребер, с вероятностью п. Таким образом, ожидаемое количество ребер равно пн(п − 1)/2, но фактическое количество ребер может варьироваться случайным образом, и все графы имеют ненулевую вероятность быть выбранными. Напротив, в грамм(п, M) модель, введенная Эрдешем и Реньи, граф выбирается равномерно случайным образом среди всех M-реберные графы; количество кромок фиксировано, но кромки не являются независимыми друг от друга, поскольку наличие кромки в одной позиции отрицательно коррелирует с наличием кромки в другой позиции. Хотя эти две модели в конечном итоге обладают схожими свойствами, грамм(п, п) Модель зачастую удобнее работать из-за независимости ее краев.[10]

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

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

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

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

Прочие взносы

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

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

Избранные публикации

G52.Гилберт, Э. Н. (1952), "Сравнение сигнальных алфавитов", Технический журнал Bell System, 31: 504–522, Дои:10.1002 / j.1538-7305.1952.tb01393.x
G55.Гилберт, Э. Н. (1955), Теория перетасовки, Технический меморандум, Bell Laboratories. Как цитирует Байер и Диаконис (1992).[11]
G59.Гилберт, Э. Н. (1959), "Случайные графы", Анналы математической статистики, 30: 1141–1144, Дои:10.1214 / aoms / 1177706098
G60.Гилберт, Э. Н. (1960), "Пропускная способность канала импульсного шума", Технический журнал Bell System, 39: 1253–1265, Дои:10.1002 / j.1538-7305.1960.tb03959.x
G65.Гилберт, Э. Н. (1965), «Латинские квадраты, не содержащие повторяющихся биграмм», SIAM Обзор, 7 (2): 189–198, Дои:10.1137/1007035, JSTOR  2027267
G67.Гилберт, Э. Н. (1967), "Случайные плоские сети и игольчатые кристаллы", в Noble, B. (ed.), Применение математики в инженерии, Нью-Йорк: Macmillan
G68.Гилберт, Э. Н. (1968), "Минимальные деревья Штейнера", Журнал SIAM по прикладной математике, 16 (1): 1–29, Дои:10.1137/0116001, JSTOR  2099400
CGG.Чанг, Ф. Р. К.; Gilbert, E.N .; Грэм, Р. Л.; Shearer, J. B .; ван Линт, Дж. Х. (1982), «Мозаика прямоугольников с прямоугольниками» (PDF), Математический журнал, 55 (5): 286–291, Дои:10.2307/2690096

Рекомендации

  1. ^ Биография автора от Borst, S.C .; Коффман, Э.; Gilbert, E.N .; Whiting, P.A .; Винклер, П.М. (2000), «Распределение временных интервалов в беспроводной TDMA», в Геленбе, Э. (ред.), Оценка производительности системы: методологии и приложения, CRC Press, стр. 203–214, ISBN  978-0-8493-2357-7
  2. ^ Эдгар Нельсон Гилберт на Проект "Математическая генеалогия"
  3. ^ "Некролог Эдгара Нельсона Гилберта: см. Некролог Эдгара Гилберта от Star-Ledger". Obits.nj.com. Получено 2013-06-21.
  4. ^ Варшамов, Р. Р. (1957), "Оценка количества сигналов в кодах с исправлением ошибок", Докл. Акад. АН СССР, 117: 739–741
  5. ^ Луна, Тодд К. (2005), «Граница Гилберта – Варшамова», Исправление ошибок Кодирование: математические методы и алгоритмы, John Wiley and Sons, стр. 409–410, ISBN  978-0-471-64800-0
  6. ^ Хаффман, Уильям Кэри; Плесс, Вера (2003), «Новый взгляд на границу Гилберта – Варшамова», Основы кодов с исправлением ошибок, Cambridge University Press, стр.541, ISBN  978-0-521-78280-7
  7. ^ Эллиотт, Э. О. (1963), "Оценки частоты ошибок для кодов на каналах пакетного шума", Технический журнал Bell System, 42: 1977–1997, Дои:10.1002 / j.1538-7305.1963.tb00955.x
  8. ^ Петрауш, Стефан; Сёргель, Вольфганг; Кауп, Андре (2004), "Последовательно подключенные каналы: сценарий приложения емкости и потоковой передачи видео для раздельного и совместного кодирования каналов", 5-я Международная конференция ITG по кодированию источников и каналов (SCC): 14–16 января 2004 г., Эрланген: протокол конференции, Маргрет Шнайдер, стр. 271–278, ISBN  978-3-8007-2802-2
  9. ^ Erdős, P .; Реньи, А. (1959), «На случайных графах I» (PDF), Publicationes Mathematicae, 6: 290–297
  10. ^ Уоттс, Дункан Дж. (2003), Маленькие миры: динамика сетей между порядком и случайностью, Принстонские исследования сложности, Princeton University Press, стр. 36–37, ISBN  978-0-691-11704-1
  11. ^ а б Байер, Дэйв; Диаконис, Перси (1992), «Отслеживание шарканья ласточкиного хвоста к его логову», Анналы прикладной вероятности, 2 (2): 294–313, Дои:10.1214 / aoap / 1177005705, JSTOR  2959752
  12. ^ Gray, N.H .; Андерсон, Дж. Б .; Дивайн, Дж. Д .; Квасник, Дж. М. (1976), "Топологические свойства случайных сетей трещин", Математическая геология, 8 (6): 617–628, Дои:10.1007 / BF01031092; Шрайбер, Томаш; Соя, Наталья (2010). "Предельная теория для плоских мозаик Гилберта". arXiv:1005.0023.
  13. ^ Гилберт, Эдвард N (1961). «Случайные плоские сети». Журнал Общества промышленной и прикладной математики. 9.4: 533–543.
  14. ^ Хван, Франк; Ричардс, Дана; Зима, Павел (1992), Проблема дерева Штейнера, Анналы дискретной математики (математические исследования Северной Голландии), 53, Elsevier, стр. 80–83, ISBN  978-0-444-89098-6
  15. ^ Независимое открытие массивов Костаса, Аарон Стерлинг, 9 октября 2011 г.
  16. ^ Гарднер, Мартин (2001), Колоссальная книга по математике: классические головоломки, парадоксы и проблемы: теория чисел, алгебра, геометрия, вероятность, топология, теория игр, бесконечность и другие темы развлекательной математики., W. W. Norton & Company, стр. 18, ISBN  978-0-393-02023-6