MacTutor

biografia

rodzicami Leslie Valiant byli Leslie Valiant i Eva Julia Ujlaki. Wychowywał się w Anglii, uczęszczał do Tynemouth High School w North Shields. Szkoła ta została przemianowana w 1969 roku, kilka lat po odejściu Valianta, kiedy stała się znana jako Norham High School. Valiant ukończył szkołę średnią Latymer Upper School NA King Street w Hammersmith w Londynie. Była to (i nadal jest) słynna niezależna szkoła selektywna o wielkiej renomie sięgającej jej założenia przez Edwarda Latymera w 1624 roku. Po ukończeniu Latymer Upper School studiował w King ’ s College w Cambridge, a następnie, po uzyskaniu pierwszego stopnia, licencjatu z matematyki, wstąpił do Imperial College w Londynie, aby studiować teoretyczną informatykę. Po przyznaniu Dyplomu Imperial College in Computer Science, Valiant udał się na University of Warwick, gdzie podjął badania nad doktoratem z informatyki z Michaelem Stewartem Patersonem jako jego doradcą.
przed przyznaniem doktoratu, Valiant spędził rok 1973-74 w Stanach Zjednoczonych jako Visiting Assistant professor na Carnegie Mellon University w Pittsburghu w Pensylwanii. Doktoryzował się na Uniwersytecie w Warwick w 1974 za pracę „Decision Procedures for Families of Deterministic Pushdown Automata”. We współpracy ze swoim promotorem pracy magisterskiej M S Patersonem Valiant przedstawił w 1973 roku pracę deterministyczny automat jednotarczowy na Erste Fachtagung der Gesellschaft für Informatik über Automatentheorie und Formale Sprachen w Bonn. Wilfried Brauer recenzował artykuł, pisząc:-

deterministyczny automat z jednym licznikiem (doca) jest deterministycznym automatem pushdown posiadającym jednoelementowy alfabet stosu. Łatwo zauważyć, że problemy dotyczące włączenia i nieważności przecięcia dla doca są nierozstrzygalne. W przeciwieństwie do tego, autorzy dają procedurę decyzyjną dla równoważności doca i pokazują, że jego złożoność czasowa jest ograniczona powyżej przez funkcję wykładniczą w około pierwiastka kwadratowego z liczby stanów testowanych doca. przypuszczają, że równoważność jest decydująca dla klasy wszystkich deterministycznych automatów wypychania.

Valiant opublikował artykuł the equivalence problem for deterministic finite-turn pushdown automata w 1974 roku. S a Greibach zwraca uwagę na znaczenie tego artykułu: –

automat sklepowy pushdown (pda) jest skończony-skręć, jeśli istnieje jednolita granica liczby razy, może przełączyć się z pchania (zwiększając długość magazynu pushdown) na popping (zmniejszając długość magazynu pushdown) podczas dowolnego obliczenia na dowolnym wejściu. Autor ustala zasadność problemu równoważności (czy dwie maszyny akceptują ten sam język?) dla deterministycznych pda skończonych obrotów. Znaczenie wyniku polega na technikach dowodowych stosowanych w jego ustanowieniu oraz na tym, że stanowi on jeden z głównych przełomów w kierunku rozstrzygnięcia długo nierozstrzygniętych hipotez, że problem równoważności dla deterministycznych pda (dpda) jest rozstrzygalny (odpowiedni problem jest znany jako nierozstrzygalny dla nondeterministycznych pda nawet w bardzo ograniczonych przypadkach).

po powrocie ze Stanów Zjednoczonych w 1974 roku Valiant podjął pracę wykładowcy na Uniwersytecie w Leeds, gdzie pracował przez dwa lata 1974-76. Podajmy kolejny przykład jego wczesnych prac, Ten ponownie napisany we współpracy z M S Paterson,. Ten artykuł z 1975 roku deterministyczny automat z jednym licznikiem zaczyna się od następującego wprowadzenia autorów: –

przedstawiamy analizę deterministycznych automatów z jednym licznikiem w celu wykazania, że problem równoważności jest dla nich decydujący. Wszystkie nasze argumenty i wyniki można bezpośrednio przetłumaczyć na schema pojęć teoretycznych. Następstwem tego jest to, że równoważność jest decydująca dla schematów Janowa, nawet jeśli są one dozwolone jako licznik pomocniczy.

Valiant przeniósł się do Szkocji w 1975 roku, aby podjąć wykłady na Uniwersytecie w Edynburgu. W 1977 ożenił się z Gayle Lynne Dyckhoff; mieli dwóch synów Gregory ’ ego Johna Valianta i Paula Valianta. W Edynburgu został promowany na czytelnika w 1981 roku, ale wyjechał do Stanów Zjednoczonych w 1982 roku, kiedy był profesorem wizytującym na Harvardzie. W tym samym roku został mianowany przez Gordona McKaya profesorem informatyki i Matematyki Stosowanej na Harvardzie. Pozostał na Harvardzie, chociaż rok 1987-88 spędził jako visiting fellow na Uniwersytecie Oksfordzkim w Anglii. W 2001 został mianowany profesorem informatyki i Matematyki Stosowanej w Harvard School of Engineering and Applied Sciences.
wkład, jaki Valiant wniósł, jest dość niezwykły i otrzymał najwyższe wyróżnienia za swoje osiągnięcia. Był stypendystą Guggenheima w latach 1985-86, a w 1986 otrzymał Nagrodę Nevanlinna. W 1991 został wybrany członkiem Royal Society of London, a w roku następnym członkiem American Association for Artificial Intelligence. W 1997 otrzymał Nagrodę Knutha od Stowarzyszenia maszyn obliczeniowych Special Interest Group on Algorithms and Computation Theory oraz Komitetu Technicznego Instytutu Inżynierów Elektryków i Elektroników ds. matematycznych podstaw informatyki. Został wybrany do Narodowej Akademii Nauk Stanów Zjednoczonych w 2001 roku, otrzymał nagrodę European Association for Theoretical Computer Science Award oraz Nagrodę Turinga Association for Computing Machinery 2010, która zostanie wręczona Valiantowi na dorocznym bankiecie nagród Stowarzyszenia w San Jose w Kalifornii 4 czerwca 2011 roku. Nagroda obejmuje również nagrodę pieniężną w wysokości 250 000 USD.
nie wyjaśniliśmy wkładu Valianta, który doprowadził go do otrzymania najwyższych możliwych nagród. W tym celu cytujemy z komentarza towarzyszącego ogłoszeniu nagrody Turinga (przytoczone poniżej artykuły z 2011 roku cytują z tego komentarza). Komentarz zaczyna się: –

w ciągu ostatnich 30 lat Leslie Valiant wniosła zasadniczy wkład w wiele aspektów teoretycznej informatyki. Jego prace otworzyły nowe granice, wprowadziły nowe pomysłowe koncepcje i prezentowały wyniki o wielkiej oryginalności, głębi i pięknie. Wielokrotnie prace Valianta dosłownie definiowały lub przekształcały krajobraz badań informatycznych.

potem idzie na szczegóły kilku obszarów, do których Valiant wniósł oszałamiający wkład. Podajemy kilka krótkich wyciągów z każdego z czterech obszarów:

  1. teoria obliczeniowego uczenia się. Największym pojedynczym wkładem valianta może być jego praca „a theory of the learnable” (1984), która położyła podwaliny teorii obliczeniowego uczenia się. … Model „prawdopodobnie w przybliżeniu poprawny” (PAC) valianta dostarczył pięknych podstaw dla samej koncepcji uczenia się.
  2. Na początku lat 70-tych złożoność obliczeniowa na ogół zajmowała się trudnością problemów decyzyjnych, takich jak to, czy Wykres ma idealne dopasowanie, czy też podróżujący sprzedawca może znaleźć trasę o co najwyżej określonej długości. … Jednym z najbardziej godnych uwagi odkryć Valianta jest to, że problemy z liczeniem są znacznie bardziej subtelne niż sugerowały poprzednie doświadczenia. Problem z liczeniem pyta o liczbę niektórych obiektów kombinatorycznych: na przykład, ile doskonałych dopasowań jest na wykresie? Pytamy nie tylko o to, czy ta liczba jest dodatnia, ale także o to, jak duża jest. Jeśli problem decyzyjny jest trudny, to również musi być problem liczenia, ale zaskakujące było to, że converse zawodzi. W swojej pracy „the complexity of computing the permanent” (1979) wykazał, że chociaż istnieje skuteczny algorytm do określania, czy Wykres ma idealne dopasowanie, nie ma skutecznego algorytmu do liczenia doskonałych dopasowań (chyba że P = NP), a w rzeczywistości liczenie doskonałych dopasowań jest tak trudne, jak każdy problem liczenia. Było to szokiem dla społeczności złożoności obliczeniowej, która przyzwyczaiła się do idei, że problemy decyzyjne z łatwością uchwycą kluczowe cechy problemu.
  3. obliczenia algebraiczne. Innym kluczowym wkładem w złożoność obliczeniową była teoria obliczeń algebraicznych Valianta, w której ustanowił ramy dla zrozumienia, które formuły algebraiczne mogą być efektywnie oceniane. … W pracy „completion classes in algebra” (1979) Valiant scharakteryzował trudność obliczeń algebraicznych w kategoriach dwóch podstawowych i ściśle powiązanych funkcji z algebry liniowej, a mianowicie wyznacznika i stałej.
  4. obliczenia równoległe i rozproszone. Oprócz teorii obliczeniowego uczenia się i złożoności obliczeniowej, trzecim szerokim obszarem, w którym Valiant wniósł istotny wkład, jest teoria obliczeń równoległych i rozproszonych. Jego wyniki sięgają od prostych, ale potężnych i eleganckich spostrzeżeń po ponowne zbadanie samych podstaw. Przykładem prostego wglądu jest jego schemat trasowania równoległego, opisany w pracy” a scheme for fast parallel communication ” (1982).

kończymy tę biografię cytując w całości zakończenie cytatu z nagrody Turinga:-

rzadko widzi się tak uderzające połączenie głębi i szerokości, jak w twórczości Valianta. Jest naprawdę bohaterską postacią w informatyce teoretycznej i wzorem do naśladowania dla swojej odwagi i kreatywności w rozwiązywaniu niektórych najgłębszych nierozwiązanych problemów w nauce.

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany.