Ronald Graham - Ronald Graham

Ronald Graham
Graham v roce 1998
narozený	Ronald Lewis Graham (1935-10-31)31. října 1935 Taft, Kalifornie, USA
Zemřel	6. července 2020(2020-07-06) (ve věku 84) San Diego, Kalifornie, USA
Alma mater	Univ. Aljašky (BS) UC Berkeley (PhD)
Známý jako	Coffman – Grahamův algoritmus Erdős – Grahamův problém Grahamovo číslo Grahamovo skenování Graham – Pollakova věta
Manžel (y)	Fan Chung
Ocenění	Cena Pólya (1971) Nat. Acad. Sci. (1985) Steele Prize (2003)
Vědecká kariéra
Pole	Matematika Počítačová věda
Instituce	Bell Labs Laboratoře AT&T UC San Diego
Teze	O konečných součtech racionálních čísel (1962)
Doktorský poradce	Derrick Henry Lehmer

Ronald Lewis Graham (31. října 1935 - 6. července 2020)^[1] byl Američan matematik připsána Americká matematická společnost jako "jeden z hlavních architektů rychlého celosvětového rozvoje města diskrétní matematika v posledních letech".^[2]

Odvedl důležitou práci teorie plánování, výpočetní geometrie, Ramseyova teorie, a kvazi náhodnost.^[3] Pracoval mnoho let v Bell Labs a později na University of California, San Diego, a byl prezidentem obou Americká matematická společnost a Mathematical Association of America.

Graham byl uveden v Ripley věří tomu nebo ne! za to, že byl nejen „jedním z předních světových matematiků“, ale také uznávaným trampolinistou a žonglérem, a v roce 1972 byl zvolen prezidentem Mezinárodní asociace žonglérů.^[4][5][3]

Životopis

Graham se narodil v roce Taft, Kalifornie, dne 31. října 1935,^[6] syn pracovníka ropného pole a později obchodní lodi. Navzdory pozdějšímu zájmu o gymnastiku byl malý a neatletický.^[7] Vyrůstal často v pohybu mezi Kalifornií a Gruzií, přeskakoval v těchto směrech několik ročníků školy a nikdy nezůstal na žádné škole déle než rok.^[1][7] Jako teenager se přestěhoval na Floridu se svou nyní rozvedenou matkou, kam šel, ale nedokončil střední školu. Místo toho ve věku 15 let vyhrál a Fordova nadace stipendium na University of Chicago, kde se naučil gymnastika ale žádná matematika.^[1]

Po třech letech, kdy jeho stipendium skončilo, se přestěhoval do University of California, Berkeley, oficiálně jako student elektrotechniky, ale také studující teorie čísel pod Derrick Henry Lehmer,^[1] a získání titulu kalifornského státního trampolínového šampiona.^[7] Narukoval United States Air Force v roce 1955, kdy dosáhl věku způsobilosti,^[8] opustil Berkeley bez titulu a byl umístěný dovnitř Fairbanks na Aljašce, kde v roce 1959 nakonec dokončil bakalářský titul z fyziky na Univerzitě Palackého v Olomouci University of Alaska Fairbanks.^[1] Po návratu na Kalifornskou univerzitu v Berkeley získal postgraduální studium Ph.D. v matematice v roce 1962. Jeho disertační práce, vedená Lehmerem, byla O konečných součtech racionálních čísel.^[9] Jako postgraduální student se živil vystupováním na trampolíně v cirkuse,^[8] a oženil se s Nancy Youngovou, vysokoškolskou studentkou matematiky v Berkeley; měli dvě děti.^[1]

Ronald Graham, jeho manželka Fan Chung, a Paul Erdős, Japonsko 1986

Po dokončení doktorátu začal Graham pracovat v roce 1962 v Bell Labs a (jak se to později stalo) Laboratoře AT&T, v New Jersey, jako ředitel informačních věd. V roce 1963 se na konferenci v Coloradu setkal s plodným maďarským matematikem Paul Erdős (1913−1996),^[1] který se stal blízkým přítelem a častým spolupracovníkem výzkumu. Graham byl rozčarovaný, aby byl zbit ping-pong Erdős, tehdy již středního věku; vrátil se do New Jersey s odhodláním vylepšit svou hru a nakonec se stal šampiónem Bell Labs a získal ve hře státní titul.^[1] Graham později popularizoval koncept Erdőovo číslo, míra vzdálenosti od Erdőse v síti spolupráce matematiků;^[10][8] Mezi jeho mnoho děl s Erdősem patří dvě knihy otevřené problémy^[B1][B5] a Erdősův poslední posmrtný papír.^[A15] Graham se rozvedl v 70. letech; v roce 1983 se oženil se svým kolegou z Bell Labs a častým spoluautorem Fan Chung.^[1]

Zatímco v Bell Labs, Graham také zaujal pozici v Rutgersova univerzita jako univerzitní profesor matematických věd v roce 1986 a působil ve funkci prezidenta Americká matematická společnost od roku 1993 do roku 1994. V roce 1995 se stal vedoucím laboratoří.^[1] V roce 1999 odešel z AT&T po 37 letech služby,^[11] a přestěhoval se do University of California, San Diego (UCSD), jako Irwin a Joan Jacobs obdařeni profesorem výpočetní a informační vědy.^[1][8] Na UCSD se také stal hlavním vědeckým pracovníkem Kalifornský institut pro telekomunikace a informační technologie.^[8][5] V letech 2003-04 byl prezidentem Mathematical Association of America.^[1]

Graham zemřel bronchiektázie^[12] dne 6. července 2020 ve věku 84 let La Jolla, Kalifornie.^[6][13]

Příspěvky

Ronald Graham žongloval se čtyřmi míčky kašna (1986)

Graham významně přispěl do různých oblastí matematiky a teoretické informatiky. Publikoval asi 400 prací, z toho čtvrtinu Fan Chung,^[14] a šest knih, včetně Konkrétní matematika s Donald Knuth a Oren Patashnik.^[B4] Erdősův číselný projekt uvádí, že má téměř 200 spoluautorů.^[15]

Pozoruhodná témata v matematice pojmenovaná po Grahamovi zahrnují Erdős – Grahamův problém na Egyptské zlomky, Graham – Rothschildova věta v Ramseyova teorie z slova parametrů a Grahamovo číslo z toho odvozeno Graham – Pollakova věta a Grahamova oblázková domněnka v teorie grafů, Coffman – Grahamův algoritmus pro přibližné plánování a kreslení grafů a Grahamovo skenování algoritmus pro konvexní trupy. Začal také studovat primefree sekvence, Boolean Pythagorean ztrojnásobuje problém, největší malý mnohoúhelník, a čtvercové balení ve čtverci.

Kromě publikace pod svým vlastním jménem se Graham podílel na publikacích časopisu G. W. Peck, pseudonymní matematická spolupráce pojmenovaná pro iniciály jejích členů, s Grahamem jako „G“.^[16]

Teorie čísel

Grahamova disertační práce byla v teorie čísel, na Egyptské zlomky,^[7][9] a Erdős – Grahamův problém úzce souvisí. Požádal o důkaz, že když jsou celá čísla rozdělena do konečně mnoha tříd, jedna z tříd má podmnožinu, jejíž vzájemné součty se rovnají jedné. Důkaz zveřejnil Ernie Croot v roce 2003.^[17] Další z Grahamových prací o egyptských frakcích byl publikován v roce 2015 s Steve Butler a (téměř 20 let posmrtně) Paul Erdős; byl to poslední z Erdősových článků, který byl publikován, čímž se Butler stal jeho 512. spoluautorem.^[A15][18]

V článku z roku 1964 začal Graham studovat primefree sekvence pozorováním toho, že existují posloupnosti čísel, definované stejnými relace opakování jako Fibonacciho čísla, ve kterém žádný z prvků sekvence není prvočíslo.^[A64] Výzvy konstruovat více takových sekvencí se později chopil Donald Knuth a další.^[19] Grahamova kniha z roku 1980 s Paul Erdős, Staré a nové výsledky v kombinatorické teorii čísel, poskytuje sbírku otevřené problémy ze široké škály podoblastí v rámci teorie čísel.^[B1]

Ramseyova teorie

The Graham – Rothschildova věta v Ramseyova teorie byl publikován Grahamem a Bruce Rothschild v roce 1971 a aplikuje Ramseyovu teorii na kombinatorické kostky v kombinatorika slov.^[A71a] Graham dal velké číslo jako horní mez pro instanci této věty, nyní známou jako Grahamovo číslo, který byl uveden v seznamu Guinnessova kniha rekordů jako největší počet, jaký kdy byl použit v matematickém důkazu,^[20] ačkoli to bylo od té doby překonáno ještě větším počtem, jako je STROM (3).^[21]

Graham nabídl peněžní cenu za řešení Boolean Pythagorean ztrojnásobuje problém, další problém v Ramseyově teorii; cena byla získána v roce 2016.^[22]Graham také vydal dvě knihy o Ramseyově teorii.^[B2][B3]

Teorie grafů

Rozdělení okrajů kompletní graf ${ displaystyle K_ {6}}$ do pěti úplných bipartitních podgrafů, podle Graham – Pollakova věta

The Graham – Pollakova věta, kterou Graham publikoval s Henry O. Pollak ve dvou dokumentech v letech 1971 a 1972,^[A71b][A72a] uvádí, že pokud okraje ${ displaystyle n}$-vrchol kompletní graf jsou rozděleny do kompletní bipartitní podgrafy, tedy alespoň ${ displaystyle n-1}$ jsou zapotřebí podgrafy. Graham a Pollak poskytli jednoduchý důkaz lineární algebra, a přes kombinatorickou povahu výroku a navzdory několika publikacím alternativních důkazů od jejich práce, všechny známé důkazy vyžadují lineární algebru.^[23]

Brzy po výzkumu v kvazi-náhodné grafy začal prací Andrewa Thomasona, Grahama a jeho spoluautorů Fan Chung a R. M. Wilson publikoval v roce 1989 výsledek, který byl nazýván „základní teorémem kvazi náhodných grafů“ a uvedl, že mnoho různých definic těchto grafů je ekvivalentních.^[A89a][24]

Grahamova oblázková domněnka, který se objevil v příspěvku z roku 1989 Fan Chung, týká se oblázkové číslo z Kartézské produkty grafů. Od roku 2019^{[Aktualizace]}, zůstává nevyřešen.^[25]

Balicí, plánovací a aproximační algoritmy

Grahamova raná práce plánování pracovního obchodu^[A66][A69] představil nejhorší případ přibližný poměr do studia aproximační algoritmy, a položil základy pro pozdější vývoj konkurenční analýza z online algoritmy.^[26] Tato práce byla později uznána jako důležitá také pro teorii balení koše,^[27] v této oblasti Graham později pracoval explicitněji.^[A74]

The Coffman – Grahamův algoritmus, kterou Graham publikoval s Edward G. Coffman Jr. v roce 1972,^[A72b] poskytuje optimální algoritmus pro plánování dvou strojů a zaručený aproximační algoritmus pro větší počet strojů. Bylo také použito v vrstvený graf.^[28]

V článku průzkumu o plánování článků publikovaném v roce 1979 představil Graham a jeho spoluautoři a tříznakový zápis pro klasifikaci teoretických problémů s plánováním podle systému strojů, na kterých mají běžet, charakteristik úkolů a zdrojů, jako jsou požadavky na synchronizaci nebo nepřerušování, a měřítko výkonu, které má být optimalizováno.^[A79] Tato klasifikace byla někdy nazývána „Grahamova notace“ nebo „Grahamova notace“.^[29]

Diskrétní a výpočetní geometrie

The Grahamovo skenování algoritmus pro konvexní trupy

Grahamovo skenování je široce používaný a praktický algoritmus pro konvexní trupy dvojrozměrných množin bodů na základě třídění body a poté je vložit do trupu v seřazeném pořadí.^[30] Graham publikoval algoritmus v roce 1972.^[A72c]

The největší malý mnohoúhelník Problém požaduje polygon největší plochy pro daný průměr. Jak překvapivě poznamenal Graham, odpověď není vždy pravidelný mnohoúhelník.^[A75a] Grahamova domněnka o tvaru těchto polygonů z roku 1975 byla nakonec prokázána v roce 2007.^[31]

V další publikaci z roku 1975 to Graham a Erdős poznamenali pro balení čtverců jednotek do většího čtverce s nečíselnými délkami stran lze použít nakloněné čtverce k ponechání nezakryté oblasti, která je v délce strany většího čtverce sublearní, na rozdíl od zřejmého balení s osami zarovnanými čtverci.^[A75b] Klaus Roth a Bob Vaughan prokázal, že někdy může být zapotřebí nekrytá plocha alespoň úměrná druhé odmocnině délky strany; otevřeným problémem zůstává prokázání těsné vazby na nekrytou oblast.^[32]

Pravděpodobnost a statistika

v neparametrické statistiky, příspěvek z roku 1977 Persi Diaconis a Graham studoval statistické vlastnosti Pearsonova stupačka, míra hodnostní korelace který porovnává dva obměny sečtením vzdálenosti mezi pozicemi položky ve dvou permutacích přes každou položku.^[A77]Porovnali toto opatření s jinými metodami korelace pozic, což mělo za následek „Diaconis – Grahamovy nerovnosti“

${ displaystyle I + E leq D leq 2I}$

kde ${ displaystyle D}$ je Pearsonova stupačka, ${ displaystyle I}$ je počet inverze mezi těmito dvěma permutacemi (nenormalizovaná verze Kendallův koeficient korelace ), a ${ displaystyle E}$ je minimální počet dvouprvkových swapů potřebných k získání jedné permutace od druhé.^[33]

The Náhodný proces Chung – Diaconis – Graham je náhodná procházka na celá čísla modulo liché celé číslo ${ displaystyle p}$, ve kterém v každém kroku jeden zdvojnásobí předchozí číslo a poté náhodně přidá nulu, ${ displaystyle 1}$nebo ${ displaystyle -1}$ (modulo ${ displaystyle p}$). V článku z roku 1987 Fan Chung, Diaconis a Graham studovali doba míchání tohoto procesu, motivováno studiem generátory pseudonáhodných čísel.^[A87][34]

Ceny a vyznamenání

V roce 2003 Graham vyhrál Americká matematická společnost je roční Cena Leroye P. Steele za celoživotní dílo. Cena citovala jeho příspěvky k diskrétní matematika, jeho popularizace matematiky prostřednictvím jeho rozhovorů a psaní, jeho vedení na Bell Labs a jeho služba prezidenta společnosti.^[35] Byl jedním z pěti inauguračních vítězů Cena George Pólyi z Společnost pro průmyslovou a aplikovanou matematiku, sdílení s ostatními Ramseyho teoretici Klaus Leeb, Bruce Rothschild, Alfred Hales a Robert I. Jewett.^[36] Byl také jedním ze dvou inauguračních vítězů Eulerova medaile z Ústav kombinatoriky a jeho aplikací, druhá bytost Claude Berge.^[37]

Graham byl zvolen do Národní akademie věd v roce 1985.^[38] V roce 1999 byl uveden jako Člen ACM „za klíčové příspěvky k analýze algoritmů, zejména k analýze heuristiky v nejhorším případě, teorii plánování a výpočetní geometrii“.^[39] Stal se členem Společnost pro průmyslovou a aplikovanou matematiku v roce 2009; Cena kolegy citovala jeho „příspěvky do diskrétní matematiky a jejích aplikací“.^[40] V roce 2012 se stal členem Americká matematická společnost.^[41]

Graham byl pozvaným řečníkem v roce 1982 Mezinárodní kongres matematiků (koná se ve Varšavě v roce 1983),^[13] na téma „Poslední vývoj v Ramseyově teorii“.^[A84] Byl dvakrát Přednášející Josiah Willard Gibbs, v letech 2001 a 2015.^[13]The Mathematical Association of America udělil mu oba Cena Carla Allendoerfera za jeho příspěvek "Steinerovy stromy na šachovnici" s Fan Chungem a Martin Gardner v Matematický časopis (1989),^[A89b][42] a Cena Lestera R. Forda za jeho příspěvek „Vichřice po výpočetní geometrii“ s Frances Yao v Americký matematický měsíčník (1990).^[A90][43] Jeho kniha Magická matematika s Persi Diaconis^[B6] vyhrál Cena Euler Book.^[44]

Jednání Celá čísla 2005 konference byla vydána jako slavnostní svátek k 70. narozeninám Rona Grahama.^[45] Další svátek, který vycházel z konference konané v roce 2015 na počest Grahamových 80. narozenin, byl vydán v roce 2018 jako kniha Spojení v diskrétní matematice: oslava práce Rona Grahama.^[46]

Vybrané publikace

Knihy

Upravené svazky

Články

Reference

externí odkazy

• Grahamův UCSD fakultní výzkumný profil
• Papíry Rona Grahama - komplexní archiv příspěvků napsaných Ronem Grahamem
• O Ronovi Grahamovi - stránka shrnující některé aspekty Grahamova života a matematiky - část Web společnosti Fan Chung
• „Simonsova nadace: Ronald Graham (1935–2020)“. Simonsova nadace. 11. ledna 2016. - Rozšířený video rozhovor.
• Ronald Graham publikace indexované podle Google Scholar