MacTutor

életrajz

Leslie Valiant szülei Leslie Valiant és Eva Julia Ujlaki voltak. Angliában nevelkedett, részt vett Tynemouth Középiskola, North Shields. Ezt az iskolát 1969-ben, néhány évvel a Valiant távozása után nevezték át, amikor Norham High School néven vált ismertté. Valiant iskolai tanulmányait a Latymer felső iskolában, a King Streeten, Hammersmith, London. Ez volt (és még ma is) egy híres szelektív független iskola, amelynek nagy hírneve Edward Latymer 1624-es alapításáig nyúlik vissza. A Latymer felső iskola elvégzése után a Cambridge-i King ‘ s College-ban tanult, majd első fokozatának, a matematika BA-jának odaítélése után belépett a londoni Imperial College-ba, hogy elméleti számítástechnikát tanuljon. Odaítélése után a Diploma az Imperial College in Computer Science, Valiant ment a University of Warwick, ahol vállalta a kutatás a doktori Számítástechnika Michael Stewart Paterson, mint a tanácsadója.
a Ph. D., Valiant az 1973-74-es évet az Egyesült Államokban töltötte vendégprofesszorként Carnegie Mellon Egyetem ban ben Pittsburgh, Pennsylvania. Doktorátusát a Warwicki Egyetem 1974-ben diplomamunkájáért döntési eljárások a determinisztikus Pushdown automaták családjai számára. Együttműködve a szakdolgozat tanácsadója M s Paterson, Valiant bemutatta a papír determinisztikus egyszámláló automaták az Erste Fachtagung der Gesellschaft F enterprisetheorie und Formale sprachenetheoretheorie 1973-ban Bonnban. Wilfried Brauer áttekintette a papírt, írás:-

a determinisztikus egyszámláló automata (doca) egy determinisztikus pushdown automata, amelynek egyelemes verem ábécéje van. Könnyen belátható, hogy az inclusion és a nullity-of-intersection problémák a doca-k számára eldönthetetlenek. Ezzel szemben a szerzők döntési eljárást adnak a doca-k ekvivalenciájára, és megmutatják, hogy az idő komplexitását fent egy exponenciális függvény határolja a tesztelt doca-k állapotának négyzetgyökében. feltételezik, hogy az ekvivalencia eldönthető az összes determinisztikus pushdown automata osztályára.

Valiant 1974-ben publikálta a determinisztikus véges fordulatú pushdown automaták ekvivalenciaproblémája című cikket. S a Greibach rámutat ennek a cikknek a fontosságára: –

a pushdown store automata (pda) véges fordulatú, ha egyenletesen kötődik ahhoz, hogy hányszor válthat a tolásról (a pushdown store hosszának növelése) a poppingra (a pushdown store hosszának csökkentése) bármely bemeneten végzett számítás során. A szerző megállapítja az ekvivalencia probléma eldönthetőségét (két gép elfogadja-e ugyanazt a nyelvet?) determinisztikus véges fordulatú pda – khoz. Az eredmény jelentősége az annak megállapításához használt bizonyítási technikákban rejlik, és abban a tényben, hogy ez jelenti az egyik legnagyobb áttörést annak a régóta fennálló sejtésnek a rendezésében, miszerint a determinisztikus pda-k (dpda-k) ekvivalenciaproblémája eldönthető (a megfelelő probléma köztudottan még nagyon korlátozott esetekben is eldönthetetlen a nemdeterminisztikus pda-k esetében).

miután 1974-ben visszatért az Egyesült Államokból, Valiant előadást tartott a Leeds Egyetemen, ahol 1974-76-ban két évig dolgozott. Adjunk még egy példát korai cikkeire, ezt ismét M s Patersonnal együttműködve írták,. Ez az 1975-ös determinisztikus egyszámláló automata a következő szerzők bevezetésével kezdődik:-

bemutatjuk a determinisztikus egyszámláló automaták elemzését annak bemutatása érdekében, hogy számukra az ekvivalencia probléma eldönthető. Minden érvünk és eredményünk közvetlenül sémaelméleti kifejezésekre fordítható. A következmény az, hogy az ekvivalencia eldönthető a Janov-sémák esetében, még akkor is, ha ezek megengedettek egy kiegészítő számlálót.

Valiant 1975-ben Skóciába költözött, hogy előadást tartson az Edinburgh-i Egyetemen. 1977-ben feleségül vette Gayle Lynne Dyckhoffot, két fiuk született, Gregory John Valiant és Paul A Valiant. Edinburgh-ban 1981-ben előléptették olvasóvá, de 1982-ben az Egyesült Államokba ment, amikor vendégprofesszor volt a Harvardon. Még ebben az évben kinevezték Gordon McKay-nek a számítástechnika és az Alkalmazott Matematika professzorává a Harvardon. A Harvardon maradt, bár az 1987-88-as évet vendégmunkásként töltötte a Oxfordi Egyetem Angliában. 2001-ben Jefferson Coolidge a Harvard School of Engineering and Applied Sciences számítástechnika és Alkalmazott matematika professzora lett.
a hozzájárulás, hogy Valiant tett meglehetősen figyelemre méltó, és ő kapta a legmagasabb kitüntetéssel az ő eredményeit. 1985-86-ban Guggenheim ösztöndíjas volt, 1986-ban megkapta a Nevanlinna-díjat. 1991-ben a Royal Society of London tagjává választották, majd a következő évben az American Association for Artificial Intelligence tagjává. 1997-ben elnyerte a Knuth-Díjat az Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory és az Institute of Electrical and Electronics Engineers Technical Committee on the Mathematical Foundations of Computing-tól. Ő választották az Egyesült Államok Nemzeti Tudományos Akadémia 2001-ben megkapta az Európai Szövetség elméleti Computer Science Award, valamint az Association for Computing Machinery 2010 A M Turing-díjat, amelyet be kell mutatni, hogy Valiant az Egyesület éves awards bankett San Jose, Kalifornia június 4-én 2011. A díj 250 000 dolláros pénzdíjat is tartalmaz.
nem magyaráztuk el a Valiant hozzájárulásait, amelyek a lehető legmagasabb díjakat kapták. Ehhez idézünk a Turing-díj kihirdetését kísérő kommentárból (az alábbiakban hivatkozott 2011.évi cikkek idézik ezt a kommentárt). A kommentár kezdődik: –

az elmúlt 30 évben Leslie Valiant alapvető hozzájárulást tett az elméleti Számítástechnika számos aspektusához. Munkája új határokat nyitott, ötletes új koncepciókat vezetett be, és nagyszerű eredetiség, mélység és szépség eredményeit mutatta be. Valiant munkája időről időre szó szerint meghatározta vagy átalakította a számítástechnikai kutatási tájat.

ezután folytatja számos olyan terület részletezését, amelyekhez Valiant lenyűgöző hozzájárulást tett. Adunk néhány rövid kivonatok mind a négy területen:

  1. számítási tanulási elmélet. Valiant legnagyobb egyetlen hozzájárulás lehet a papír’ a theory of the learnable ‘ (1984), amely megalapozta a számítógépes tanulás elmélete. … Valiant” valószínűleg megközelítőleg helyes ” (PAC) modellje gyönyörű alapokat adott a tanulás fogalmához.
  2. a felsorolás összetettsége. Az 1970-es évek elején a számítási komplexitás általában a döntési problémák nehézségével foglalkozott, például azzal, hogy egy grafikon tökéletesen illeszkedik-e, vagy egy utazó eladó megtalálja-e a legfeljebb egy bizonyos hosszúságú útvonalat. … Valiant egyik legfigyelemreméltóbb felfedezése az, hogy a számlálási problémák sokkal finomabbak, mint azt a korábbi tapasztalatok sugallták. A számlálási probléma néhány kombinatorikus objektum számát kéri: például hány tökéletes illesztés van egy grafikonon? Nem csak azt a döntési problémát kérdezzük, hogy ez a szám pozitív-e, hanem azt is, hogy mekkora. Ha a döntési probléma nehéz, akkor a számlálási problémának is annak kell lennie, de Valiant meglepő felismerése az volt, hogy az ellenkezője kudarcot vall. A “the complexity of computing the permanent” (1979) című cikkében megmutatta, hogy bár létezik hatékony algoritmus annak megállapítására, hogy egy gráf tökéletesen illeszkedik-e, nincs hatékony algoritmus a tökéletes egyezések számlálására (kivéve, ha P = NP), és valójában a tökéletes egyezések számlálása ugyanolyan nehéz, mint bármely számlálási probléma. Ez sokkot okozott a számítási komplexitás közösség, amely megszokta azt az elképzelést, hogy a döntési problémák könnyen megragadják a probléma legfontosabb jellemzőit.
  3. algebrai számítás. A számítási komplexitás másik kulcsfontosságú hozzájárulása Valiant algebrai számításelmélete volt, amelyben keretet hozott létre annak megértéséhez, hogy mely algebrai képletek értékelhetők hatékonyan. … Az ő papír “teljesség osztályok algebra” (1979), Valiant jellemezte a nehéz algebrai számítás szempontjából két alapvető és szorosan kapcsolódó funkciók lineáris algebra, nevezetesen a determináns és az állandó.
  4. párhuzamos és elosztott számítástechnika. A számítási tanulási elmélet és a számítási komplexitás mellett egy harmadik széles terület, amelyben a Valiant fontos hozzájárulást tett, a párhuzamos és elosztott számítástechnika elmélete. Eredményei itt az egyszerű, de erőteljes és elegáns betekintéstől az alapok újbóli vizsgálatáig terjednek. Az egyszerű betekintésre példa a párhuzamos útválasztási sémája, amelyet a “gyors párhuzamos kommunikáció sémája” (1982) című cikk ír le.

ezt az életrajzot azzal zárjuk, hogy teljes egészében idézjük a Turing-díj idézetének következtetését: –

ritkán látunk olyan mélységet és szélességet, mint Valiant munkájában. Ő valóban egy hősi alakja az elméleti számítástechnika és példakép az ő bátorsága és kreativitása kezelésében néhány legmélyebb megoldatlan problémák a tudomány.

Vélemény, hozzászólás?

Az e-mail-címet nem tesszük közzé.