MacTutor

životopis

rodiče Leslie Valiant byli Leslie Valiant a Eva Julia Ujlaki. Byl vychován v Anglii, navštěvoval Tynemouth High School, North Shields. Tato škola byla přejmenována v roce 1969, několik let poté, co Valiant odešel, když se stala známou jako Norham High School. Valiant dokončil školní vzdělání na Latymer Upper School, v King Street, Hammersmith, Londýn. Toto byla (a stále je) slavná selektivní nezávislá škola s velkou pověstí sahající až do jejího založení Edwardem Latymerem v roce 1624. Po absolvování Latymer Upper School, studoval na King ‚ s College, Cambridge poté, po udělení jeho prvního stupně, BA v matematice, vstoupil Imperial College, Londýn studovat teoretickou informatiku. Po udělení diplomu Imperial College v informatice, Valiant šel na University of Warwick, kde podnikl výzkum pro doktorát z informatiky s Michaelem Stewartem Patersonem jako jeho poradcem.
před udělením titulu Ph.D., Valiant strávil rok 1973-74 ve Spojených státech jako hostující odborný asistent na Carnegie Mellon University v Pittsburghu v Pensylvánii. Doktorát získal v roce 1974 na univerzitě ve Warwicku za svou diplomovou práci pro rodiny deterministických Pushdownových automatů. Ve spolupráci se svým diplomovým poradcem M. S. Patersonem představil Valiant v roce 1973 v Bonnu papír Deterministic one-counter automata erste Fachtagung der Gesellschaft für Informatik über Automatentheorie und Formale SprachenⓉ. Wilfried Brauer recenzoval Noviny a psal:-

deterministický automat s jedním počítadlem (doca) je deterministický automat s jednoprvkovou abecedou zásobníku. Je snadné vidět, že začlenění a neplatnost průsečíku problémy pro doca jsou nerozhodnutelné. Na rozdíl od toho autoři předkládají rozhodovací postup pro ekvivalenci doca a ukazují, že jeho časová složitost je ohraničena funkcí exponenciální asi v druhé odmocnině počtu stavů testovaných doca. předpokládají, že ekvivalence je rozhodovatelná pro třídu všech deterministických pushdown automatů.

Valiant publikoval článek problém ekvivalence pro deterministické automaty s konečným otočením v roce 1974. S a Greibach poukazuje na důležitost tohoto článku: –

automat pushdown store (pda) je konečný-turn, pokud existuje jednotná vazba na počet, kolikrát může přejít z tlačení (zvýšení délky pushdown store) na praskání (snížení délky pushdown store) během jakéhokoli výpočtu na jakémkoli vstupu. Autor stanoví rozhodovatelnost problému ekvivalence(přijímají dva stroje stejný jazyk ?)pro deterministické PDA s konečným obratem. Význam výsledku spočívá v důkazních technikách použitých při jeho stanovení a v tom, že představuje jeden z hlavních průlomů k vyřešení dlouho nevyřešené domněnky, že problém ekvivalence pro deterministické pda (dpda) je rozhodnutelný (odpovídající problém je známo, že je nerozhodnutelný pro nedeterministické pda i ve velmi omezených případech).

po návratu ze Spojených států v roce 1974 nastoupil Valiant na přednášku na Leeds University, kde pracoval dva roky 1974-76. Uveďme další příklad jeho raných prací, tento znovu napsaný ve spolupráci s M S Patersonem,. Tento dokument deterministické jednočíselné automaty z roku 1975 začíná úvodem následujících autorů: –

předkládáme analýzu deterministických jednočíselných automatů, abychom ukázali, že problém ekvivalence pro ně je rozhodnutelný. Všechny naše argumenty a výsledky lze přeložit přímo do teoretických termínů schématu. Následkem toho je, že ekvivalence je pro janovova schémata rozhoditelná, i když jsou povoleny pomocné čítače.

Valiant se přestěhoval do Skotska v roce 1975, aby nastoupil na přednášku na univerzitě v Edinburghu. V roce 1977 se oženil s Gayle Lynne Dyckhoff; měli dva syny Gregory John Valiant a Paul a Valiant. V Edinburghu byl povýšen na čtenáře v roce 1981, ale odešel do Spojených států v roce 1982, když byl hostujícím profesorem na Harvardu. Později téhož roku byl jmenován Gordonem McKayem profesorem informatiky a aplikované matematiky na Harvardu. Zůstal na Harvardu, i když rok 1987-88 strávil jako hostující pracovník na Oxfordské univerzitě v Anglii. V roce 2001 byl jmenován profesorem informatiky a aplikované matematiky na Harvard School of Engineering and Applied Sciences.
příspěvky, které Valiant učinil, jsou pozoruhodné a za své úspěchy získal nejvyšší vyznamenání. V letech 1985-86 byl Guggenheimovým kolegou a v roce 1986 obdržel Cenu Nevanlinna. V roce 1991 byl zvolen členem Královské společnosti v Londýně a v následujícím roce členem Americké asociace pro umělou inteligenci. V roce 1997 získal Knuthovu cenu od Asociace pro výpočetní techniku speciální zájmovou skupinu pro algoritmy a teorii výpočtů a technického výboru Institutu elektrotechnických a elektronických inženýrů pro matematické základy výpočetní techniky. V roce 2001 byl zvolen do Národní akademie věd Spojených států, získal Cenu Evropské asociace pro teoretickou informatiku a cenu Asociace pro výpočetní techniku 2010 a M Turing Award, která bude předána Valiant na výroční hostině asociace v San Jose v Kalifornii dne 4. června 2011. Cena zahrnuje také peněžní odměnu ve výši $ 250,000.
nevysvětlili jsme příspěvky Valianta, které vedly k tomu, že získal nejvyšší možné ocenění. K tomu citujeme z Komentáře, který doprovází vyhlášení Turingovy ceny (články z roku 2011 odkazované níže citují z tohoto Komentáře). Komentář začíná: –

za posledních 30 let Leslie Valiant zásadně přispěl k mnoha aspektům teoretické informatiky. Jeho práce otevřela nové hranice, představil geniální nové koncepty, a představil výsledky velké originality, hloubka, a krása. Valiantova práce znovu a znovu doslova definovala nebo transformovala krajinu výzkumu informatiky.

pak jde o podrobnosti o několika oblastech, ke kterým Valiant ohromně přispěl. Uvádíme několik krátkých výňatků z každé ze čtyř oblastí:

  1. výpočetní teorie učení. Valiant je největší jediný příspěvek může být jeho práce „teorie learnable“ (1984), který položil základy výpočetní teorie učení. … Valiant“ pravděpodobně přibližně správný “ (PAC) model poskytl krásné základy pro samotný koncept učení.
  2. složitost výčtu. Na počátku roku 1970 se výpočetní složitost obecně zabývala obtížností rozhodovacích problémů, například zda má graf perfektní shodu nebo zda cestující prodavač může najít trasu maximálně určité délky. … Jedním z nejpozoruhodnějších objevů Valiantu je, že problémy s počítáním jsou mnohem jemnější, než naznačovaly předchozí zkušenosti. Problém s počítáním se ptá na počet některých kombinatorických objektů: například, kolik dokonalých zápasů je v grafu? Neptáme se jen na to, zda je toto číslo kladné, ale také na to, jak je velké. Pokud je problém s rozhodováním obtížný, pak musí být problém s počítáním také, ale Valiant překvapivě uvědomil, že konverzace selže. Ve své práci „složitost výpočtu trvalého“ (1979) ukázal, že ačkoli existuje účinný algoritmus, který říká, zda má graf perfektní shodu, neexistuje žádný účinný algoritmus pro počítání dokonalých shod (pokud P = NP), a ve skutečnosti počítání dokonalých shod je stejně těžké jako jakýkoli problém s počítáním. To přišlo jako šok pro komunitu výpočetní složitosti, která si zvykla na myšlenku, že problémy s rozhodováním snadno zachytí klíčové rysy problému.
  3. algebraické výpočty. Dalším klíčovým příspěvkem k výpočetní složitosti byla Valiantova teorie algebraického výpočtu, ve kterém vytvořil rámec pro pochopení toho, které algebraické vzorce lze efektivně vyhodnotit. … Ve své práci „třídy úplnosti v algebře“ (1979), Valiant charakterizoval obtížnost algebraického výpočtu z hlediska dvou základních a úzce souvisejících funkcí z lineární algebry, jmenovitě determinant a permanentní.
  4. paralelní a distribuované výpočty. Kromě teorie výpočetního učení a výpočetní složitosti je třetí širokou oblastí, ve které Valiant významně přispěl, teorie paralelního a distribuovaného počítání. Jeho výsledky zde sahají od jednoduchých, ale silných a elegantních poznatků až po přezkoumání samotných základů. Příkladem jednoduchého vhledu je jeho schéma paralelního směrování, popsané v článku „a scheme for fast parallel communication“ (1982).

tuto biografii ukončujeme úplným citováním závěru citace Turingovy ceny:-

zřídka člověk vidí tak nápadnou kombinaci hloubky a šířky jako v Valiantově díle. Je skutečně hrdinskou postavou teoretické informatiky a vzorem pro svou odvahu a kreativitu při řešení některých nejhlubších nevyřešených problémů ve vědě.

Napsat komentář

Vaše e-mailová adresa nebude zveřejněna.