Vitani, Paul

Paul Vitani
Paul Vitany

Paul Vitani 2005
Födelsedatum 21 juni 1944 (78 år)( 1944-06-21 )
Födelseort budapest
Land
Vetenskaplig sfär Informatik
Arbetsplats CWI , UVA
Alma mater Fria universitetet i Amsterdam
Akademisk examen Filosofie doktor (PhD) i matematik [1]
Akademisk titel Professor
vetenskaplig rådgivare Jako de Bakker ,
Arto Salomaa [2]
Studenter Ronald Kramer ,
Peter Grunwald ,
Ronald de Wolf [2]
Utmärkelser och priser Knight Grand Cross , akademiker , CWI-stipendiat
Autograf Tillgänglig i dokument relaterade till Paul Vitani i akademiker Yershovs arkiv
Hemsida homepages.cwi.nl/~paulv

Paul Michael Béla Vitányi är en framstående nederländsk forskare inom området teoretisk datavetenskap , teorin om algoritmer och beräkningskomplexitet , professor vid universitetet i Amsterdam och forskare vid Centrum för matematik och informatik . Vitani är holländare av mamma och ungerska av pappa.

Paul Vitani fick en ingenjörsexamen 1971 från Delfts tekniska universitet , samma år gick han in på forskarskolan vid Mathematical Center i Amsterdam, där han fortfarande arbetar (nu kallas detta forskningsinstitut "Center for Mathematics and Informatics") . Han försvarade sin doktorsavhandling om " Lindenmeier- system : struktur, språk och tillväxtfunktioner" [2] 1978 vid Free University of Amsterdam och blev snart chef för den nyskapade avdelningen, som han förde till världen nivå inom området kvantberäkning, distribuerade algoritmer, algoritmisk teoriinformation och reversibla adiabatiska beräkningar. 2003 fick han en överföring till positionen som hedersforskare (CWI Fellow) [3] . 2005 fick han den högsta professuren (hoogleraar 1 [4] ) vid det största universitetet i Nederländerna. 2007 adlades han i Nederländska lejonorden [5] . 2011 valdes han till medlem av European Academy of Sciences [4] . Liksom många vetenskapsmän på hans nivå gjorde Paul Vitani mycket redaktionellt arbete i stora tidskrifter inom sitt område och blev ofta inbjuden till konferenser och workshops för plenarpresentationer [6] .

Bidrag till vetenskapen

Lindenmeier-system, även kallade L-system, som Paul Vitani arbetade med som doktorand, är omskrivningssystem som är relaterade till formell grammatik [7] och skiljer sig främst genom att regeln vid varje slutledningssteg tillämpas inte på en utvald (icke -terminal) symbol, men till alla tecken i strängen samtidigt. Inledningsvis föreslogs L-system av botanikern Aristide Lindenmeier för att modellera utvecklingen av encelliga organismer och andra grenstrukturer. Vitani betraktade dem från en formell synvinkel och klargjorde många punkter angående språkklasserna som genereras av L-system, såväl som användningen av icke -terminaler och homomorfismer . Speciellt visade han att om vi i deterministiska L-system (det vill säga de där härledningsträdet inte förgrenar sig) betraktar en familj av tillägg (språk som genereras av icke-terminaler), så kommer den inte att helt innehålla klassen av reguljära språk , men dess stängning genom bokstav för bokstav homomorfism som motsvarar klassen av rekursivt uppräknade språk [8] . Han visade också att att ta en förlängning, som faktiskt kokar ner till en mängdteoretisk skärning av ett språk med en uppsättning terminaler (ett alfabet), i många fall är likvärdigt i praktiken med att överväga omskrivnings-invarianta strängar - det vill säga, han visade kopplingen mellan stabiliserande morfogenes och teorin om formella språk [9] .

Paul Vitani, tillsammans med sin kollega Ming Li, gjorde ett betydande bidrag till teorin om Kolmogorovs komplexitet , inklusive att skriva boken "Introduktion till Kolmogorovs komplexitet och dess tillämpningar" [10] (publicerad 1993, 1997, 2008). Själva konceptet med Kolmogorovs komplexitet existerade långt före honom (föreslog oberoende av Solomonoff och Kolmogorov på 1960-talet) och kokar ner till påståendet att det finns någon abstrakt beskrivande komplexitet för varje sträng som är lika med längden på det minsta programmet som kan producera denna sträng (för enkelhetens skull kan vi betrakta det som ett programspråk Turing-maskin , även om detta inte är nödvändigt: du behöver bara fixa någon form av universell beskrivning eller kodningsspråk). En sådan komplexitet hos en sträng, och faktiskt för alla andra objekt, representerar den absoluta, ofta ouppnåeliga, minsta mängden information som en sträng eller objekt kan uppta utan speciella knep, som att ge upp universalitet. Kolmogorovs komplexitet är en praktisk teoretisk abstraktion, ofta värdelös i praktiken eftersom den bevisligen är oberäkningsbar . Paul Vitani var en av de första som hittade praktiska tillämpningar för det inom automatteori eller algoritmanalys. Boken föregicks av hans separata arbete med att färga grafer med begränsad precision, algoritmisk jämförelse av band, kö och stack , revidering av Chomsky-hierarkin , kopplingen av värsta tänkbara scenarier med medelvärden, etc. Principen om kortaste beskrivning formulerades av Vitani, Lee och deras elever som en abstraktion baserad på Bayes teorem och Kolmogorovs komplexitet erhölls ett antal slutsatser av praktisk karaktär - till exempel att datakomprimering är den bästa strategin för att närma sig den kortaste längden av en databeskrivning eller överförd meddelande [11] . I praktiken låter detta dig ersätta det abstrakta, komplexa och icke-beräknbara konceptet med beskrivande komplexitet med dess approximation i form av längden på ett meddelande komprimerat av någon tillgänglig arkiverare .

I beräkningsteorin introducerade Paul Vitani begreppet lokalitet för beräkningar och visade att undvikande av von Neumanns sekventiella beräkningar inte löser det allmänna problemet, eftersom beräkningen i sig äger rum på en viss plats, och dess resultat måste överföras till en annan plats för att lagra eller fortsätt beräkningarna - och denna kommunikation tar tid och utrymme, vilket bör återspeglas i realistiska modeller för inkonsekvent beräkning [12] . Kolmogorovs komplexitet var också användbar för att uppskatta belastningen på nätverk av olika topologier från olika algoritmer med hjälp av den så kallade inkompressibilitetsmetoden [13] . Metoden liknar den mycket enklare Dirichlet-principen och bygger i första hand på att det finns så många fler grafer med hög Kolmogorov-komplexitet än grafer med låg komplexitet att slumpmässiga grafer blir Kolmogorov-komplex med en sannolikhet nära enhet [14] . I allmänhet är informationen i alla objekt för Vitani uppdelad i två delar: väsentlig (som anger objektets regelbundenhet) och icke väsentlig (stokastiska tillägg). Han kallar den relativa mängden väsentlig information för ett mått på sofistikering, och objekt för vilka den är maximalt absolut icke-stokastisk [15] .

Studier av informationsteori, komplexitet och komprimering ledde oundvikligen Paul Vitani till mått som mäter informationsavståndet mellan objekt (strängar, dokument, språk, bilder, etc.): han och hans elever föreslog en klusteranalysmetod baserad på datakomprimering [16] ; föreslog ett normaliserat informationsavstånd [17] och ett normaliserat squeeze-avstånd [18] som mått på hur svårt det är att omvandla ett objekt till ett annat; implementerade det så kallade Google likhetsmått som ett semantiskt mått baserat på antalet träffar i Google för en term, en annan och deras kombination [19] ; utvidgade begreppet informationsavstånd från ordpar till ändliga listor (som faktiskt övergav relationer till förmån för hypergrafer ) [20] ; utvecklat ett antal metoder för att automatiskt härleda betydelsen av okända ord baserat på deras informationsmässiga likhet med kända ord [21] [22] . Vissa av de klusteranalysmetoder som han föreslagit är så bra att de fungerar många gånger snabbare än deras analoger - till exempel kräver hierarkisk klusterbildning med hjälp av klättringsalgoritmen och parallell genetisk programmering endast en distansmatris och bygger ett dendrogram av 60-80 objekt i några timmar, medan alternativa tillvägagångssätt är begränsade till 20-30 objekt eller kräver flera år för beräkningar [23] . Samma metoder för klusteranalys som tillämpas på musik kan bestämma genren med hög tillförlitlighet och klassificera verk av kompositörer [24] .

Inom genetisk programmering föreslog Paul Vitani en metod baserad på att snabbt blanda Markov-kedjor som konvergerar med sannolikhet nära en även på små populationer, medan alternativa metoder lider av slumpmässigt divergerande evolution [25] . I reversibla beräkningar  bevisade han möjligheten till reversibel simulering av irreversibla beräkningar i subexponentiell tid och i subkvadratiska minneskostnader [26] . I spelteorin  generaliserade han problemet med att förstöra en spelare till ett större antal spelare [27] . I diskret geometri  löste han problemet med Heilbronn-triangeln i fallet med en slumpmässig enhetlig fördelning av punkter längs en cirkel [28] [29] .

Paul Vitani ingår i listan över de mest produktiva forskarna i DBLP- katalogen som författare och medförfattare till nästan 250 vetenskapliga refererade publikationer [30] .

Lärlingar

Under ledning av Paula Vitani försvarade [2] [31] :

Anteckningar

  1. ↑ Paul Vitányi: Lindenmayer Systems: Structure, Languages, and Growth Functions, 1978.
  2. ↑ 1 2 3 4 Paul Michael Bela Vitanyi Arkiverad 22 januari 2015 på Wayback Machine vid Mathematics Genealogy Project .
  3. ↑ Paul Vitányi har utsetts till CWI Fellow Arkiverad 1 december 2014 på Wayback Machine , ERCIM News No. 53 april 2003.
  4. ↑ 1 2 Academy of Europe: Vitanyi Paul Arkiverad 22 januari 2015 på Wayback Machine .
  5. ↑ Paul Vitányi mottar koninklijke onderscheiding Arkiverad 22 januari 2015 på Wayback Machine .
  6. ↑ Några framstående föreläsningar, keynote-föreläsningar, inbjudna föreläsningar, handledningar Arkiverade 1 december 2014 på Wayback Machine .
  7. ↑ L-Systems - The Mathematical Beauty of Plants Arkiverad 22 januari 2015 på Wayback Machine .
  8. ↑ Paul M. B. Vitányi: Deterministiska Lindenmayer-språk, icke-terminala och homomorfismer . Theoretical Computer Science 2(1): 49-71 (1976).
  9. ↑ Paul M. B. Vitányi, Adrian Walker: Stable String Languages ​​of Lindenmayer Systems . Information and Control 37(2): 134-149 (1978).
  10. ↑ En introduktion till Kolmogorovs komplexitet och dess tillämpningar (Texter i datavetenskap) Arkiverad 29 augusti 2018 på Wayback Machine på Amazon .
  11. ↑ Paul MB Vitányi, Ming Li: Minsta beskrivningslängdinduktion, Bayesianism och Kolmogorov-komplexitet . IEEE Transactions on Information Theory 46(2): 446-464 (2000)
  12. ↑ Paul M. B. Vitányi: Lokalitet, kommunikation och sammankopplingslängd i multidatorer . SIAM J Comput. 17(4): 659-672 (1988)
  13. ↑ Tao Jiang, Ming Li, Paul M. B. Vitányi: Inkompressibilitetsmetoden . SOFSEM 2000: 36-53
  14. ↑ Harry Buhrman, Ming Li, John Tromp, Paul M. B. Vitányi: Kolmogorov Random Graphs and the Incompressibility Method . SIAM J Comput. 29(2): 590-599 (1999).
  15. ↑ Paul M. B. Vitányi: Meningsfull information . IEEE Transactions on Information Theory 52(10): 4617-4626 (2006)
  16. ↑ Rudi Cilibrasi, Paul MB Vitányi: Clustering genom komprimering Arkiverad 13 oktober 2008 på Wayback Machine . IEEE Transactions on Information Theory 51(4): 1523–1545 (2005)
  17. ↑ Charles H. Bennett, Péter Gács, Ming Li, Paul M. B. Vitányi, Wojciech H. Zurek: Informationsavstånd . IEEE Transactions on Information Theory 44(4): 1407-1423 (1998)
  18. ↑ Sebastiaan A. Terwijn, Leen Torenvliet, Paul M. B. Vitányi: Nonapproximability of the normalized information distance . Journal of Computer and System Sciences 77(4): 738-742 (2011)
  19. ↑ Rudi Cilibrasi, Paul MB Vitányi: Googles likhetsavstånd . IEEE Trans. Knowl. DataEng. 19(3): 370-383 (2007)
  20. ↑ Paul M. B. Vitányi: Informationsavstånd i multiplar . IEEE Transactions on Information Theory 57(4): 2451–2456 (2011)
  21. ↑ Rudi Cilibrasi, Paul MB Vitányi: Likhet mellan objekt och betydelsen av ord Arkiverad 11 oktober 2008 på Wayback Machine . TAMC 2006: 21-45
  22. ↑ Rudi Cilibrasi, Paul MB Vitányi: Automatic Meaning Discovery Using Google Arkiverad 22 januari 2015 på Wayback Machine . Kolmogorov komplexitet och tillämpningar 2006
  23. ↑ Rudi Cilibrasi, Paul MB Vitányi: A New Quartet Tree Heuristic for Hierarchical Clustering Arkiverad 22 januari 2015 på Wayback Machine . Theory of Evolutionary Algorithms 2006
  24. ↑ Rudi Cilibrasi, Paul M. B. Vitányi, Ronald de Wolf: Algorithmic Clustering of Music . WEDELMUSIC 2004: 110-117
  25. ↑ Paul M. B. Vitányi: En disciplin av evolutionär programmering . Teoretisk datavetenskap 241(1-2): 3-23 (2000)
  26. ↑ Harry Buhrman, John Tromp, Paul M. B. Vitányi: Tids- och rumsgränser för reversibel simulering . ICALP 2001: 1017-1027
  27. ↑ Kazuyuki Amano, John Tromp, Paul M. B. Vitányi, Osamu Watanabe: On a Generalized Ruin Problem . Slumpmässigt-ungefär 2001: 181-191
  28. ↑ Tao Jiang, Ming Li, Paul M. B. Vitányi: Den förväntade storleken på Heilbronns trianglar . IEEE Conference on Computational Complexity 1999: 105-113
  29. ↑ Tao Jiang, Ming Li, Paul MB Vitányi: Den genomsnittliga arean av trianglar av Heilbronn-typ . Random Structures and Algorithms 20(2): 206-219 (2002)
  30. ↑ Mest produktiva DBLP-författare arkiverade 13 februari 2009. .
  31. ↑ Tidigare Ph.D. Studenter arkiverade 1 december 2014 på Wayback Machine .
  Gå till Wikidata-objektet  Tematiska platser