MacTutor

Biografie

părinții lui Leslie Valiant au fost Leslie Valiant și Eva Julia Ujlaki. A fost crescut în Anglia, urmând liceul Tynemouth, North Shields. Această școală a fost redenumită în 1969, la câțiva ani după plecarea lui Valiant, când a devenit cunoscută sub numele de Liceul Norham. Valiant și-a finalizat educația școlară la Latymer Upper School, în King Street, Hammersmith, Londra. Aceasta a fost (și este încă) o faimoasă școală independentă selectivă, cu o mare reputație care datează de la fondarea sa de către Edward Latymer în 1624. După absolvirea școlii superioare Latymer, a studiat la King ‘ s College, Cambridge, apoi, după acordarea primei sale diplome, o licență în matematică, a intrat în Imperial College, Londra pentru a studia Informatica teoretică. După acordarea diplomei Colegiului Imperial în informatică, Valiant a mers la Universitatea din Warwick unde a întreprins cercetări pentru un doctorat în informatică cu Michael Stewart Paterson în calitate de consilier al său.
înainte de acordarea doctoratului său., Valiant a petrecut anul 1973-74 în Statele Unite ca profesor asistent în vizită la Universitatea Carnegie Mellon în Pittsburgh, Pennsylvania. El a primit doctoratul de la Universitatea din Warwick în 1974 pentru procedurile sale de decizie a tezei pentru familiile de automate deterministe de împingere. În colaborare cu consilierul său de teză M s Paterson, Valiant a prezentat lucrarea Deterministic one-counter automata la Erste Fachtagung der Gesellschaft f Informatik oktimber Automatentheorie und Formale Sprachen XV din Bonn în 1973. Wilfried Brauer a revizuit lucrarea, scriind:-

un automat determinist cu un singur contor (doca) este un automat de împingere determinist care are un alfabet de stivă cu un singur element. Este ușor de văzut că incluziunea și problemele de nulitate de intersecție pentru doca sunt indecidabile. Spre deosebire de aceasta, autorii dau o procedură de decizie pentru echivalența lui doca și arată că complexitatea sa de timp este delimitată mai sus de o funcție exponențială în aproximativ rădăcina pătrată a numărului de stări ale lui Doca testate. ei presupun că echivalența este decidabilă pentru clasa tuturor automatelor deterministe de împingere.

Valiant a publicat lucrarea problema echivalenței pentru automatele deterministe de împingere cu viraj finit în 1974. S a Greibach subliniază importanța acestei lucrări: –

un automat pushdown store (pda) este finit-întoarce dacă există o legătură uniformă de câte ori poate trece de la împingere (creșterea lungimii magazinului pushdown) la popping (scăderea lungimii magazinului pushdown) în timpul oricărui calcul pe orice intrare. Autorul stabilește decidabilitatea problemei de echivalență (acceptă două mașini același limbaj?) pentru PDA-urile deterministe cu viraj finit. Semnificația rezultatului constă în tehnicile de probă utilizate în stabilirea acestuia și în faptul că reprezintă una dintre progresele majore în soluționarea lungii presupuneri remarcabile că problema echivalenței pentru PDA deterministe (dpda) este decidabilă (problema corespunzătoare este cunoscută a fi indecidabilă pentru PDA nedeterministe chiar și în cazuri foarte restrânse).

după ce s-a întors din Statele Unite în 1974, Valiant a preluat un lector la Universitatea Leeds, unde a lucrat timp de doi ani 1974-76. Să dăm un alt exemplu de lucrări sale timpurii, aceasta din nou scris în colaborare cu M S Paterson,. Această lucrare din 1975 Deterministic one-counter automata începe cu următoarea introducere a autorilor:-

prezentăm o analiză a automatelor deterministe one-counter pentru a arăta că problema echivalenței pentru ele este decidabilă. Toate argumentele și rezultatele noastre pot fi traduse direct în termeni teoretici ai schemei. Corolarul care urmează este că echivalența este decidabilă pentru schemele Janov chiar și atunci când acestea sunt permise un contor auxiliar.

Valiant s-a mutat în Scoția în 1975 pentru a prelua un lector la Universitatea din Edinburgh. În 1977 s-a căsătorit cu Gayle Lynne Dyckhoff; au avut doi fii Gregory John Valiant și Paul a Valiant. În Edinburgh a fost promovat cititor în 1981, dar a plecat în Statele Unite în 1982, când era profesor invitat la Harvard. Mai târziu în acel an a fost numit Gordon McKay profesor de informatică și Matematică Aplicată la Harvard. A rămas la Harvard, deși a petrecut anul 1987-88 ca bursier în vizită la Universitatea din Oxford în Anglia. În 2001 a fost numit T Jefferson Coolidge profesor de informatică și Matematică Aplicată la Harvard School of Engineering and Applied Sciences.
contribuțiile pe care Valiant le-a adus sunt destul de remarcabile și a primit cele mai înalte onoruri pentru realizările sale. A fost coleg Guggenheim în 1985-86 și a primit Premiul Nevanlinna în 1986. A fost ales membru al Societății Regale din Londra în 1991 și, în anul următor, membru al Asociației Americane pentru Inteligență Artificială. A primit Premiul Knuth de la Asociația pentru mașini de calcul grupul de interes special pentru algoritmi și teoria calculului și Institutul inginerilor electrici și electronici Comitetul Tehnic pentru fundamentele matematice ale calculului în 1997. A fost ales în Academia Națională de științe a Statelor Unite în 2001, a primit Premiul European Association for Theoretical Computer Science și Premiul A M Turing al Asociației pentru mașini de calcul din 2010, care va fi acordat lui Valiant la banchetul anual al Premiilor Asociației din San Jose, California, la 4 iunie 2011. Premiul include, de asemenea, un premiu în bani de 250.000 USD.
nu am explicat contribuțiile lui Valiant care l-au determinat să primească cele mai mari premii posibile. Pentru a face acest lucru, cităm din comentariul care însoțește anunțul Premiului Turing (articolele din 2011 la care se face referire mai jos citat din acel comentariu). Comentariul începe: –

în ultimii 30 de ani, Leslie Valiant a adus contribuții fundamentale la multe aspecte ale informaticii teoretice. Opera sa a deschis noi frontiere, a introdus noi concepte ingenioase și a prezentat rezultate de mare originalitate, profunzime și frumusețe. De nenumărate ori, munca lui Valiant a definit sau a transformat literalmente peisajul cercetării în informatică.

apoi continuă să ofere detalii despre mai multe domenii la care Valiant a adus contribuții uimitoare. Oferim câteva extrase scurte din fiecare dintre cele patru domenii:

  1. teoria învățării computaționale. Cea mai mare contribuție unică a lui Valiant poate fi lucrarea Sa ‘a theory of the learnable’ (1984), care a pus bazele teoriei învățării computaționale. … Modelul „probabil aproximativ corect” (PAC) al lui Valiant a furnizat fundații frumoase pentru însăși conceptul de învățare.
  2. complexitatea enumerării. La începutul anilor 1970, complexitatea computațională se ocupa în general de dificultatea problemelor de decizie, cum ar fi dacă un grafic are o potrivire perfectă sau dacă un vânzător călător poate găsi un traseu de cel mult o anumită lungime. … Una dintre cele mai remarcabile descoperiri ale lui Valiant este că problemele de numărare sunt mult mai subtile decât sugerează experiența anterioară. O problemă de numărare cere numărul unor obiecte combinatorii: de exemplu, câte potriviri perfecte există într-un grafic? Nu ne întrebăm doar problema deciziei dacă acest număr este pozitiv, ci și cât de mare este. Dacă problema deciziei este dificilă, atunci și problema numărării trebuie să fie la fel, dar realizarea surprinzătoare a lui Valiant a fost că inversul eșuează. În lucrarea sa „complexitatea calculării permanentului” (1979), el a arătat că, deși există un algoritm eficient pentru a spune dacă un grafic are o potrivire perfectă, nu există un algoritm eficient pentru a număra potrivirile perfecte (cu excepția cazului în care P = NP) și, de fapt, numărarea potrivirilor perfecte este la fel de grea ca orice problemă de numărare. Acest lucru a venit ca un șoc pentru comunitatea complexității computaționale, care s-a obișnuit cu ideea că problemele de decizie ar surprinde cu ușurință caracteristicile cheie ale unei probleme.
  3. calcul algebric. O altă contribuție cheie la complexitatea computațională a fost teoria calculului algebric a lui Valiant, în care a stabilit un cadru pentru înțelegerea formulelor algebrice care pot fi evaluate eficient. … În lucrarea sa „clase de completitudine în algebră” (1979), Valiant a caracterizat dificultatea calculului algebric în Termenii a două funcții fundamentale și strâns legate de algebra liniară, și anume determinantul și permanentul.
  4. calcul paralel și distribuit. Pe lângă teoria învățării computaționale și complexitatea computațională, un al treilea domeniu larg în care Valiant a adus contribuții importante este teoria calculului paralel și distribuit. Rezultatele sale aici variază de la simple, dar puternice și elegante, până la reexaminarea fundamentelor. Un exemplu de înțelegere simplă este schema sa de rutare paralelă, descrisă în lucrarea „o schemă pentru comunicare paralelă rapidă” (1982).

încheiem această biografie citând în întregime concluzia Premiului Turing citare:-

rareori se vede o combinație atât de izbitoare de profunzime și lățime ca în opera lui Valiant. Este cu adevărat o figură eroică în informatica teoretică și un model pentru curajul și creativitatea sa în abordarea unora dintre cele mai profunde probleme nerezolvate din știință.

Lasă un răspuns

Adresa ta de email nu va fi publicată.