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

Эдгар Нельсон Гилберт (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; В качестве основного приложения для данной работы были предложены сети беспроводной связи. Из этой формулировки следует простой результат: для стационарного точечного процесса Пуассона в $\mathbb {R} ^{2}$ с плотностью λ ожидаемая степень каждого узла равна количеству точек, найденных в диапазоне связности, а именно πλR ². После построения такого графика возникает естественный вопрос: какова критическая средняя степень, обеспечивающая наличие гигантской компоненты; по существу этот вопрос породил область теории перколяции континуума . Используя процесс ветвления, Гилберт смог предоставить начальную нижнюю границу критической средней степени (что эквивалентно критическому диапазону передачи). Выбрав произвольную точку в процессе (назовем это нулевым поколением), найдите все точки на расстоянии соединения R (первое поколение). Повторите процесс для всех точек первого поколения, игнорируя все найденные ранее, и продолжайте этот процесс, пока они не исчезнут. Соответствующий ветвящийся процесс — это процесс, в котором среднее число потомков представляет собой случайную величину Пуассона с интенсивностью, равной средней степени в исходной RGG (πλR ²). Отсюда для получения нижней границы необходимо применять только стандартные методы процесса ветвления. Более того, Гилберт показал, что, переформулировав проблему в задачу о перколяции связей, можно получить верхнюю границу гигантского компонента. Метод состоит в дискретизации плоскости таким образом, чтобы любые два узла в соседних квадратах были соединены; и позволяя каждому квадрату представлять собой край решетки. По своей конструкции, если в проблеме просачивания связей существует гигантская компонента, то должна быть гигантская компонента и в РГГ.

Другие вклады [ править ]

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

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

Избранные публикации [ править ]

Г52.

Гилберт, EN (1952), «Сравнение сигнальных алфавитов», Технический журнал Bell System , 31 (3): 504–522, doi : 10.1002/j.1538-7305.1952.tb01393.x

Г55.

Гилберт, EN (1955), Теория перетасовки , Технический меморандум, Bell Laboratories . Цитируется Bayer & Diaconis (1992) . ^[11]

G59.

Гилберт, Э.Н. (1959), «Случайные графики», Анналы математической статистики , 30 (4): 1141–1144, doi : 10.1214/aoms/1177706098

G60.

Гилберт, EN (1960), «Пропускная способность канала пакетного шума», Bell System Технический журнал , 39 (5): 1253–1265, doi : 10.1002/j.1538-7305.1960.tb03959.x

Г65.

Гилберт, EN (1965), «Латинские квадраты, не содержащие повторяющихся биграмм», SIAM Review , 7 (2): 189–198, Bibcode : 1965SIAMR...7..189G , doi : 10.1137/1007035 , JSTOR 2027267

Г67.

Гилберт, Э.Н. (1967), «Случайные плоские сети и игольчатые кристаллы», в книге Нобл, Б. (редактор), « Применение студенческой математики в инженерии» , Нью-Йорк: Macmillan.

Г68.

Гилберт, EN (1968), «Минимальные деревья Штейнера», SIAM Journal on Applied Mathematics , 16 (1): 1–29, doi : 10.1137/0116001 , JSTOR 2099400

КГГ.

Чанг, Франция ; Гилберт, EN; Грэм, РЛ ; Ширер, Дж. Б.; ван Линт, Дж. Х. (1982), «Разбиение прямоугольников прямоугольниками» (PDF) , Mathematics Magazine , 55 (5): 286–291, doi : 10.2307/2690096 , JSTOR 2690096

Ссылки [ править ]

^ Биография автора из Борст, Южная Каролина; Коффман, Э.Г .; Гилберт, EN; Уайтинг, Пенсильвания; Винклер, П.М. (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
^ Эллиотт, Э.О. (1963), «Оценки частоты ошибок для кодов в каналах с пакетным шумом», Bell System Технический журнал , 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
^ Эрдеш, П.; Реньи, А. (2022), «О случайных графах I» (PDF) , Publicationes Mathematicae , 6 (3–4): 290–297, doi : 10.5486/PMD.1959.6.3-4.12 , S2CID 253789267
^ Уоттс, Дункан Дж. (2003), Маленькие миры: динамика сетей между порядком и случайностью , Принстонские исследования сложности, Princeton University Press, стр. 36–37, ISBN 978-0-691-11704-1
^ Jump up to: Перейти обратно: ^а ^б Байер, Дэйв ; Диаконис, Перси (1992), «Отслеживание перемещения ласточкиного хвоста к его логову», Annals of Applied Probability , 2 (2): 294–313, doi : 10.1214/aoap/1177005705 , JSTOR 2959752
^ Грей, Нью-Хэмпшир; Андерсон, Дж. Б.; Дивайн, Джей Ди; Квасник, Дж. М. (1976), «Топологические свойства случайных сетей трещин», Mathematical Geology , 8 (6): 617–628, doi : 10.1007/BF01031092 , S2CID 119949515 ; Шрайбер, Томаш; Соя, Наталья (2010). «Теория пределов для плоских мозаик Гилберта». arXiv : 1005.0023 [ мат.PR ].
^ Гилберт, Эдгар Н. (1961). «Случайные плоские сети». Журнал Общества промышленной и прикладной математики . 9 (4): 533–543. дои : 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

[tdma-1] Биография автора из Борст, Южная Каролина; Коффман, Э.Г .; Гилберт, EN; Уайтинг, Пенсильвания; Винклер, П.М. (2000), «Распределение временных интервалов в беспроводной TDMA», Геленбе, Э. (ред.), Оценка производительности системы: методологии и приложения , CRC Press, стр. 203–214, ISBN 978-0-8493-2357-7

[mg-2] Эдгар Нельсон Гилберт в проекте «Математическая генеалогия»

[obit-3] «Некролог Эдгара Нельсона Гилберта: посмотрите некролог Эдгара Гилберта от Star-Ledger» . Obits.nj.com . Проверено 21 июня 2013 г.

[varshamov-4] Варшамов Р. Р. (1957), "Оценка числа сигналов в кодах, исправляющих ошибки", Докл. Акад. Наук СССР , 117 : 739–741.

[moon-5] Мун, Тодд К. (2005), «Граница Гилберта-Варшамова», Кодирование с коррекцией ошибок: математические методы и алгоритмы , John Wiley and Sons, стр. 409–410, ISBN 978-0-471-64800-0

[hp-6] Хаффман, Уильям Кэри; Плесс, Вера (2003), «Возврат к границе Гилберта-Варшамова», Основы кодов, исправляющих ошибки , Cambridge University Press, стр. 541 , ISBN 978-0-521-78280-7

[elliott-7] Эллиотт, Э.О. (1963), «Оценки частоты ошибок для кодов в каналах с пакетным шумом», Bell System Технический журнал , 42 (5): 1977–1997, doi : 10.1002/j.1538-7305.1963.tb00955.x

[psk-8] Петрауш, Стефан; Зёргель, Вольфганг; Кауп, Андре (2004), «Последовательно соединенные каналы: сценарий применения пропускной способности и потокового видео для отдельного и совместного кодирования каналов», 5-я Международная конференция ITG по исходному и канальному кодированию (SCC): 14–16 января 2004 г., Эрланген: протокол конференции , Маргрет Шнайдер, стр. 271–278, ISBN. 978-3-8007-2802-2

[er-9] Эрдеш, П.; Реньи, А. (2022), «О случайных графах I» (PDF) , Publicationes Mathematicae , 6 (3–4): 290–297, doi : 10.5486/PMD.1959.6.3-4.12 , S2CID 253789267

[watts-10] Уоттс, Дункан Дж. (2003), Маленькие миры: динамика сетей между порядком и случайностью , Принстонские исследования сложности, Princeton University Press, стр. 36–37, ISBN 978-0-691-11704-1

[bd-11] Jump up to: Перейти обратно: ^а ^б Байер, Дэйв ; Диаконис, Перси (1992), «Отслеживание перемещения ласточкиного хвоста к его логову», Annals of Applied Probability , 2 (2): 294–313, doi : 10.1214/aoap/1177005705 , JSTOR 2959752

[gt-12] Грей, Нью-Хэмпшир; Андерсон, Дж. Б.; Дивайн, Джей Ди; Квасник, Дж. М. (1976), «Топологические свойства случайных сетей трещин», Mathematical Geology , 8 (6): 617–628, doi : 10.1007/BF01031092 , S2CID 119949515 ; Шрайбер, Томаш; Соя, Наталья (2010). «Теория пределов для плоских мозаик Гилберта». arXiv : 1005.0023 [ мат.PR ].

[13] Гилберт, Эдгар Н. (1961). «Случайные плоские сети». Журнал Общества промышленной и прикладной математики . 9 (4): 533–543. дои : 10.1137/0109045 .

[hrw-14] Хван, Фрэнк; Ричардс, Дана ; Винтер, Павел (1992), Проблема дерева Штейнера , Анналы дискретной математики (математические исследования Северной Голландии), том. 53, Elsevier, стр. 80–83, ISBN. 978-0-444-89098-6

[sterling-15] Независимое открытие массивов Костаса , Аарон Стерлинг, 9 октября 2011 г.

[gardner-16] Гарднер, Мартин (2001), Колоссальная книга по математике: классические головоломки, парадоксы и проблемы: теория чисел, алгебра, геометрия, вероятность, топология, теория игр, бесконечность и другие темы развлекательной математики , WW Norton & Company, стр. . 18, ISBN 978-0-393-02023-6

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]