Vitani, Paul

Paul Vitani
Paul Vitany

Paul Vitani vuonna 2005
Syntymäaika 21. kesäkuuta 1944 (78-vuotias)( 21.6.1944 )
Syntymäpaikka Budapest
Maa
Tieteellinen ala Informatiikka
Työpaikka CWI , UVA
Alma mater Amsterdamin ilmainen yliopisto
Akateeminen tutkinto Filosofian tohtori (PhD) matematiikan alalta [1]
Akateeminen titteli Professori
tieteellinen neuvonantaja Jako de Bakker ,
Arto Salomaa [2]
Opiskelijat Ronald Kramer ,
Peter Grunwald ,
Ronald de Wolf [2]
Palkinnot ja palkinnot Knight Grand Cross , akateemikko , CWI-stipendiaatti
Nimikirjoitus Saatavilla Paul Vitaniin liittyvissä asiakirjoissa akateemikko Yershovin arkistossa
Verkkosivusto kotisivut.cwi.nl/~paulv

Paul Michael Béla Vitányi on maineikas hollantilainen tietotekniikan teoreettisen tieteen , algoritmien ja laskennallisen monimutkaisuuden teoria , professori Amsterdamin yliopistossa ja tutkija Center for Mathematics and Informaticsissa . Vitani on äidiltä hollantilainen ja isältä unkarilainen.

Paul Vitani suoritti insinööritutkinnon vuonna 1971 Delftin teknillisestä yliopistosta , samana vuonna hän aloitti tutkijakoulun Amsterdamin Mathematical Centerissä, jossa hän työskentelee edelleen (nykyään tätä tutkimuslaitosta kutsutaan "Matematiikan ja informatiikan keskukseksi"). . Hän puolusti väitöskirjaansa aiheesta " Lindenmeier- järjestelmät : rakenne, kielet ja kasvufunktiot" [2] vuonna 1978 Amsterdamin vapaassa yliopistossa ja hänestä tuli pian äskettäin perustetun osaston johtaja, jonka hän toi maailmalle. tasolla kvanttilaskennan, hajautettujen algoritmien, algoritmisten teoriatietojen ja palautuvien adiabaattisten laskelmien alalla. Vuonna 2003 hänet siirrettiin kunniatutkijaksi (CWI Fellow) [3] . Vuonna 2005 hän sai korkeimman professuurin (hoogleraar 1 [4] ) Alankomaiden suurimmassa yliopistossa. Vuonna 2007 hänet valittiin Alankomaiden leijonan ritarikuntaan [5] . Vuonna 2011 hänet valittiin Euroopan tiedeakatemian jäseneksi [4] . Kuten monet hänen tasonsa tutkijat, Paul Vitani teki paljon toimituksellista työtä alansa suurissa aikakauslehdissä ja hänet kutsuttiin usein konferensseihin ja työpajoihin täysistuntojen esityksiä varten [6] .

Avustus tieteeseen

Lindenmeier-järjestelmät, joita kutsutaan myös L-järjestelmiksi ja joita Paul Vitani työskenteli jatko-opiskelijana, ovat uudelleenkirjoitusjärjestelmiä, jotka liittyvät muodollisiin kielioppiin [7] ja eroavat pääasiassa siinä, että jokaisessa päättelyvaiheessa sääntöä ei sovelleta yhteen valittuun (ei -pääte) symboli, mutta kaikkiin merkkijonon merkkeihin samanaikaisesti. Alun perin kasvitieteilijä Aristide Lindenmeier ehdotti L-järjestelmiä yksisoluisten organismien ja muiden haarautuvien rakenteiden kehityksen mallintamiseksi . Vitani tarkasteli niitä muodollisesta näkökulmasta ja selvensi monia kohtia L-järjestelmien luomista kieliluokista sekä ei -terminaalien ja homomorfismien käytöstä . Erityisesti hän osoitti, että jos deterministisissa L-järjestelmissä (eli niissä, joissa johdannaispuu ei haaraudu) tarkastellaan laajennusperhettä (ei-päätteiden luomia kieliä), se ei sisällä luokkaa kokonaan. säännöllisistä kielistä , mutta sen sulkeminen kirjain kirjaimelta homomorfismilla, joka vastaa rekursiivisesti numeroitavien kielten luokkaa [8] . Hän osoitti myös, että laajennuksen ottaminen, joka itse asiassa tiivistyy kielen joukkoteoreettiseen leikkauspisteeseen terminaalien (aakkosen) kanssa, vastaa monissa tapauksissa käytännössä invarianttien merkkijonojen uudelleenkirjoittamista - toisin sanoen hän osoitti stabiloivan morfogeneesin yhteys muodollisten kielten teoriaan [9] .

Paul Vitani antoi yhdessä kollegansa Ming Li: n kanssa merkittävän panoksen Kolmogorovin monimutkaisuuden teoriaan , mukaan lukien kirjan "Johdatus Kolmogorovin monimutkaisuuteen ja sen sovelluksiin" [10] (julkaistu 1993, 1997, 2008). Kolmogorovin monimutkaisuuden käsite oli olemassa kauan ennen häntä ( Solomonoff ja Kolmogorov ehdottivat itsenäisesti 1960-luvulla), ja se perustuu väitteeseen, että minkä tahansa merkkijonon abstrakti kuvaileva monimutkaisuus on yhtä suuri kuin tämän merkkijonon tuottavan vähimmäisohjelman pituus. (Yksinkertaisuuden vuoksi voimme pitää sitä ohjelmakielenä Turingin koneena , vaikka tämä ei ole välttämätöntä: sinun on vain korjattava jonkinlainen universaali kuvaus tai koodauskieli). Tällainen merkkijonon ja itse asiassa minkä tahansa muun objektin monimutkaisuus edustaa absoluuttista, usein saavuttamatonta, vähimmäismäärää informaatiota, jonka merkkijono tai esine voi viedä ilman erityisiä temppuja, kuten universaalisuudesta luopumista. Kolmogorovin kompleksisuus on kätevä teoreettinen abstraktio, joka on usein hyödytön käytännössä, koska se on todistetusti laskematon . Paul Vitani oli yksi ensimmäisistä, joka löysi sille käytännön sovelluksia automaatioteoriassa tai algoritmianalyysissä. Kirjaa edelsi hänen erillinen työnsä rajallisen tarkkuuden graafien värittämisestä, nauhan, jonon ja pinon algoritmisesta vertailusta, Chomsky-hierarkian tarkistamisesta , pahimpien skenaarioiden yhdistämisestä keskiarvoihin jne. Lyhyimmän kuvauksen periaatteen muotoili Vitani, Lee ja heidän opiskelijansa Bayesin lauseeseen ja Kolmogorovin monimutkaisuuteen perustuvana abstraktiona saatiin useita luonteeltaan käytännöllisiä johtopäätöksiä - esimerkiksi, että tietojen pakkaus on paras strategia lähestyä datakuvauksen tai lähetettävän datan lyhintä pituutta. viesti [11] . Käytännössä tämä mahdollistaa abstraktin, monimutkaisen ja laskemattoman kuvailevan monimutkaisuuden käsitteen korvaamisen sen approksimaatiolla viestin pituuden muodossa, joka on pakattu jollakin saatavilla olevalla arkistaattorilla .

Laskentateoriassa Paul Vitani esitteli laskelmien paikallisuuden käsitteen ja osoitti, että von Neumannin peräkkäisten laskelmien välttäminen ei ratkaise yleistä ongelmaa, koska itse laskenta tapahtuu tietyssä paikassa ja sen tulokset on siirrettävä toiseen paikkaan tallennettavaksi. tai jatkaa laskelmia - ja tämä viestintä vie aikaa ja tilaa, minkä pitäisi näkyä realistisissa epäjohdonmukaisen laskennan malleissa [12] . Kolmogorovin monimutkaisuus oli hyödyllinen myös arvioitaessa eri topologioiden verkkojen kuormitusta eri algoritmeilla käyttämällä ns. kompressoimattomuusmenetelmää [13] . Menetelmä on samanlainen kuin paljon yksinkertaisempi Dirichlet-periaate ja perustuu ensisijaisesti siihen tosiasiaan, että korkean Kolmogorov-monimutkaisuuden omaavia graafisia on niin paljon enemmän kuin matalan monimutkaisia ​​graafisia, että satunnaiset graafit ovat Kolmogorov-komplekseja todennäköisyydellä lähellä yksikköä [14] . Yleensä Vitanin minkä tahansa objektin tiedot on jaettu kahteen osaan: olennaiseen (joka määrittää kohteen säännöllisyyden) ja ei-olennaiseen (stokastiset lisäykset). Hän kutsuu olennaisen informaation suhteellista määrää hienostuneisuuden mittaksi ja objekteja, joille se on maksimissaan ehdottoman ei-stokastisia [15] .

Tietoteorian, monimutkaisuuden ja pakkaamisen tutkimukset johtivat väistämättä Paul Vitanin mittareihin , jotka mittaavat kohteiden (merkkijonot, asiakirjat, kielet, kuvat jne.) välistä informaatioetäisyyttä: hän ja hänen opiskelijansa ehdottivat tietojen pakkaamiseen perustuvaa klusterianalyysimenetelmää [16] . ; ehdotti normalisoitua informaatioetäisyyttä [17] ja normalisoitua puristusetäisyyttä [18] mittauksiksi, joilla mitataan, kuinka vaikeaa objektin muuntaminen toiseksi on; otti käyttöön ns. Googlen samankaltaisuusmitan semanttisena mittarina, joka perustuu Googlen osumien määrään yhdellä termillä, toisella ja niiden yhdistelmällä [19] ; laajensi tietoetäisyyden käsitettä sanapareista äärellisiin listoihin (itse asiassa hylkäämällä suhteet hypergraafien hyväksi ) [20] ; kehitti useita menetelmiä tuntemattomien sanojen merkityksen automaattiseen johtamiseen perustuen niiden informaation samankaltaisuuteen tunnettujen sanojen kanssa [21] [22] . Jotkut hänen ehdottamistaan ​​klusterianalyysimenetelmistä ovat niin hyviä, että ne toimivat monta kertaa nopeammin kuin niiden analogit - esimerkiksi hierarkkinen klusterointi kiipeilyalgoritmilla ja rinnakkaisgeneettinen ohjelmointi vaatii vain etäisyysmatriisin ja rakentaa 60-80 kohteen dendrogrammin . muutama tunti, kun taas vaihtoehtoiset lähestymistavat rajoittuvat 20-30 kohteeseen tai vaativat useita vuosia laskelmiin [23] . Samat musiikkiin sovelletut klusterianalyysimenetelmät voivat määrittää genren erittäin luotettavasti ja luokitella säveltäjien teoksia [24] .

Geneettisessä ohjelmoinnissa Paul Vitani ehdotti menetelmää , joka perustuu Markovin ketjujen nopeaan sekoittumiseen, joka konvergoi todennäköisyydellä lähellä yhtä jopa pienissä populaatioissa, kun taas vaihtoehtoiset menetelmät kärsivät satunnaisesti poikkeavasta evoluutiosta [25] . Käänteisissä laskelmissa  hän osoitti irreversiibelien laskelmien käänteisen simulaation mahdollisuuden subeksponentiaalisessa ajassa ja subquadraattisissa muistikustannuksissa [26] . Peliteoriassa  hän yleisti pelaajan tuhoamisen ongelman suurempaan määrään pelaajia [27] . Diskreetissä geometriassa  hän ratkaisi Heilbronnin kolmion ongelman, kun pisteet jakautuivat satunnaisesti tasaisesti ympyrää pitkin [28] [29] .

Paul Vitani on mukana DBLP -luettelon tuottavimpien tutkijoiden luettelossa lähes 250 tieteellisen referee-julkaisun kirjoittajana ja mukana kirjoittajana [30] .

Harjoittelijat

Paula Vitani puolusti [2] [31] :

Muistiinpanot

  1. ↑ Paul Vitányi: Lindenmayer Systems: rakenne, kielet ja kasvufunktiot, 1978.
  2. ↑ 1 2 3 4 Paul Michael Bela Vitanyi Arkistoitu 22. tammikuuta 2015, Wayback Machine at the Mathematics Genealogy Project .
  3. ↑ Paul Vitányi on nimitetty CWI Fellowiksi Arkistoitu 1. joulukuuta 2014 Wayback Machinessa , ERCIM News No. 53 huhtikuuta 2003.
  4. ↑ 1 2 Academy of Europe: Vitanyi Paul Arkistoitu 22. tammikuuta 2015 Wayback Machinessa .
  5. ↑ Paul Vitányi ontvangt koninklijke onderscheiding Arkistoitu 22. tammikuuta 2015 Wayback Machinessa .
  6. ↑ Joitakin arvostettuja luentoja, pääluentoja, kutsuttuja luentoja, tutoriaaleja Arkistoitu 1. joulukuuta 2014 Wayback Machinessa .
  7. ↑ L-Systems - The Mathematical Beauty of Plants Arkistoitu 22. tammikuuta 2015 Wayback Machinessa .
  8. ↑ Paul M. B. Vitányi: Deterministiset Lindenmayer-kielet, ei-terminaalit ja homomorfismit . Theoretical Computer Science 2(1): 49-71 (1976).
  9. ↑ Paul M. B. Vitányi, Adrian Walker: Lindenmayer Systemsin vakaat merkkijonokielet . Information and Control 37(2): 134-149 (1978).
  10. ↑ Johdatus Kolmogorov-monimutkaisuuteen ja sen sovelluksiin (Tekstit tietojenkäsittelytieteessä) Arkistoitu 29. elokuuta 2018 Wayback Machinessa Amazonissa .
  11. ↑ Paul MB Vitányi, Ming Li: Minimikuvauspituuden induktio, Bayesianismi ja Kolmogorov-kompleksisuus . IEEE Transactions on Information Theory 46(2): 446-464 (2000)
  12. ↑ Paul M. B. Vitányi: Locality , Communication ja Interconnect Length in Multicomputers . SIAM J Comput. 17(4): 659-672 (1988)
  13. ↑ Tao Jiang, Ming Li, Paul M. B. Vitányi: Kokoonpuristumattomuusmenetelmä . 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: Merkittävää tietoa . IEEE Transactions on Information Theory 52(10): 4617-4626 (2006)
  16. ↑ Rudi Cilibrasi, Paul MB Vitányi: Clustering by compression Arkistoitu 13. lokakuuta 2008 Wayback Machinessa . 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: Information Distance . IEEE Transactions on Information Theory 44(4): 1407-1423 (1998)
  18. ↑ Sebastiaan A. Terwijn, Leen Torenvliet, Paul M. B. Vitányi: Normalisoidun tietoetäisyyden ei-naapproximability . Journal of Computer and System Sciences 77(4): 738-742 (2011)
  19. ↑ Rudi Cilibrasi, Paul MB Vitányi: Googlen samankaltaisuusetäisyys . IEEE Trans. Tietää. DataEng. 19(3): 370-383 (2007)
  20. ↑ Paul M. B. Vitányi: Tietoetäisyys moninkertaisina . IEEE Transactions on Information Theory 57(4): 2451–2456 (2011)
  21. ↑ Rudi Cilibrasi, Paul MB Vitányi: Objektien samankaltaisuus ja sanojen merkitys Arkistoitu 11. lokakuuta 2008 Wayback Machinessa . TAMC 2006: 21-45
  22. ↑ Rudi Cilibrasi, Paul MB Vitányi: Automatic Meaning Discovery using Google Arkistoitu 22. tammikuuta 2015 Wayback Machinessa . Kolmogorov-kompleksi ja sovellukset 2006
  23. ↑ Rudi Cilibrasi, Paul MB Vitányi: New Quartet Tree Heuristic for Hierarchical Clustering Arkistoitu 22. tammikuuta 2015 Wayback Machinessa . Evoluutioalgoritmien teoria 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: Evoluutioohjelmoinnin tieteenala . Teoreettinen tietojenkäsittelytiede 241(1-2): 3-23 (2000)
  26. ↑ Harry Buhrman, John Tromp, Paul M. B. Vitányi: Aika- ja tilarajat käännettävälle simulaatiolle . ICALP 2001: 1017-1027
  27. ↑ Kazuyuki Amano, John Tromp, Paul M. B. Vitányi, Osamu Watanabe: On a Generalized Ruin Problem . SUUNTATUNNUS 2001: 181-191
  28. ↑ Tao Jiang, Ming Li, Paul M. B. Vitányi: Heilbronnin kolmioiden odotettu koko . IEEE Conference on Computational Complexity 1999: 105-113
  29. ↑ Tao Jiang, Ming Li, Paul MB Vitányi: Heilbronn-tyyppisten kolmioiden keskimääräinen tapausalue . Random Structures and Algorithms 20(2): 206-219 (2002)
  30. ↑ Useimmat DBLP-tekijät Arkistoitu 13. helmikuuta 2009. .
  31. ↑ Mennyt Ph.D. Opiskelijat arkistoitu 1. joulukuuta 2014 Wayback Machinessa .
  Siirry Wikidata-kohteeseen  Temaattiset sivustot