Vitani, Paul

Paul Michael Béla Vitányi este un om de știință olandez eminent în domeniul informaticii teoretice , al teoriei algoritmilor și al complexității computaționale , profesor la Universitatea din Amsterdam și cercetător la Centrul de Matematică și Informatică . Vitani este olandeză de mamă și maghiară de tată.

Paul Vitani a obținut o diplomă de inginer în 1971 de la Universitatea de Tehnologie Delft , în același an a intrat în școala absolventă la Centrul de Matematică din Amsterdam, unde lucrează și acum (acum acest institut de cercetare se numește „Centrul de Matematică și Informatică”). . Și-a susținut teza de doctorat pe tema „ Sisteme Lindenmeier : structură, limbi și funcții de creștere” [2] în 1978 la Universitatea Liberă din Amsterdam și în curând a devenit șeful departamentului nou creat, pe care l-a adus în lume. nivel în domeniul calculului cuantic, algoritmi distribuiți, informații despre teoria algoritmică și calcule adiabatice reversibile. În 2003, a primit un transfer în funcția de cercetător onorific (CWI Fellow) [3] . În 2005 a primit cea mai înaltă profesoară (hoogleraar 1 [4] ) la cea mai mare universitate din Olanda. În 2007 a fost numit cavaler în Ordinul Leului Olandez [5] . În 2011 a fost ales membru al Academiei Europene de Științe [4] . La fel ca mulți oameni de știință de nivelul său, Paul Vitani a lucrat foarte mult în reviste importante din domeniul său și a fost adesea invitat la conferințe și ateliere pentru prezentări în plen [6] .

Contribuție la știință

Sistemele Lindenmeier, numite și sisteme L, la care Paul Vitani a lucrat ca student absolvent, sunt sisteme de rescrie care sunt legate de gramatica formală [7] și diferă în primul rând prin aceea că la fiecare pas de inferență regula se aplică nu unuia ales (non -terminal), dar la toate caracterele șirului în același timp. Inițial, sistemele L au fost propuse de botanistul Aristide Lindenmeier pentru a modela dezvoltarea organismelor unicelulare și a altor structuri ramificate. Vitani le-a considerat din punct de vedere formal și a clarificat multe puncte privind clasele de limbi generate de sistemele L, precum și utilizarea non -terminalelor și homomorfismelor . În special, el a arătat că dacă în sistemele L deterministe (adică cele în care arborele de derivare nu se ramifică) luăm în considerare o familie de extensii (limbi generate de non-terminale), atunci aceasta nu va conține complet clasa a limbilor obișnuite , dar închiderea sa prin homomorfism literă cu literă echivalent cu clasa limbilor enumerabile recursiv [8] . El a arătat, de asemenea, că luarea unei extensii, care de fapt se rezumă la o intersecție teoretică a unei limbi cu un set de terminale (un alfabet), este în multe cazuri echivalentă în practică cu luarea în considerare a șirurilor de caractere invariante de rescriere - adică, el a demonstrat legătura morfogenezei stabilizatoare cu teoria limbajelor formale [9] .

Paul Vitani, împreună cu colegul său Ming Li, au adus o contribuție semnificativă la teoria complexității Kolmogorov , inclusiv scrierea cărții „Introduction to Kolmogorov complexity and its applications” [10] (publicată în 1993, 1997, 2008). Însuși conceptul de complexitate Kolmogorov a existat cu mult înaintea lui (propus independent de Solomonoff și Kolmogorov în anii 1960) și se rezumă la afirmația că există o complexitate descriptivă abstractă a oricărui șir egală cu lungimea programului minim care poate produce acest șir. (Pentru simplitate, îl putem considera un limbaj de program mașină Turing , deși acest lucru nu este necesar: trebuie doar să remediați un fel de descriere universală sau limbaj de codare). O astfel de complexitate a unui șir, și într-adevăr a oricărui alt obiect, reprezintă cantitatea minimă absolută, adesea de neatins, pe care o poate ocupa un șir sau obiect fără trucuri speciale, cum ar fi renunțarea la universalitate. Complexitatea Kolmogorov este o abstractizare teoretică convenabilă, adesea inutilă în practică, deoarece este dovedit incalculabilă . Paul Vitani a fost unul dintre primii care i-au găsit aplicații practice în teoria automatelor sau analiza algoritmilor. Cartea a fost precedată de lucrarea sa separată privind colorarea graficelor cu precizie limitată, compararea algoritmică a benzii, coada și stiva , revizuirea ierarhiei Chomsky , conectarea scenariilor cele mai defavorabile cu medii etc. Principiul celei mai scurte descrieri a fost formulat de către Vitani, Lee și studenții lor, ca o abstractizare bazată pe teorema lui Bayes și complexitatea lui Kolmogorov, s-au obținut o serie de concluzii de natură practică - de exemplu, că compresia datelor este cea mai bună strategie pentru abordarea celei mai scurte durate a unei descrieri de date sau transmise. mesajul [11] . În practică, acest lucru vă permite să înlocuiți conceptul abstract, complex și necalculabil al complexității descriptive cu aproximarea acestuia sub forma lungimii unui mesaj comprimat de un arhivator disponibil .

În teoria computațională, Paul Vitani a introdus conceptul de localitate a calculelor și a arătat că evitarea calculelor secvențiale von Neumann nu rezolvă problema generală, deoarece calculul în sine are loc într-un anumit loc, iar rezultatele sale trebuie transferate în alt loc pentru a fi stocate. sau continuați calculele.- iar această comunicare ocupă timp și spațiu, ceea ce ar trebui să se reflecte în modele realiste de calcul inconsistent [12] . Complexitatea Kolmogorov a fost, de asemenea, utilă în estimarea încărcării pe rețele de diferite topologii din diferiți algoritmi folosind așa-numita metodă de incompresibilitate [13] . Metoda este similară cu principiul Dirichlet mult mai simplu și se bazează în primul rând pe faptul că există atât de mult mai multe grafice cu complexitate mare Kolmogorov decât grafice cu complexitate scăzută încât graficele aleatoare vor fi complexe Kolmogorov cu o probabilitate apropiată de unitate [14] . În general, informațiile din orice obiect pentru Vitani sunt împărțite în două părți: esențiale (care stabilește regularitatea obiectului) și neesențiale (adăugiri stocastice). El numește cantitatea relativă de informații esențiale o măsură a sofisticarii, iar obiectele pentru care este maxim absolut non-stohastică [15] .

Studiile despre teoria informației, complexitatea și compresia l-au condus inevitabil pe Paul Vitani la metrici care măsoară distanța informațională dintre obiecte (șiruri, documente, limbaje, imagini etc.): el și studenții săi au propus o metodă de analiză a clusterelor bazată pe compresia datelor [16] ; a propus o distanță de informație normalizată [17] și o distanță de strângere normalizată [18] ca măsurători a cât de dificil este transformarea unui obiect în altul; a implementat așa-numita măsură de similaritate Google ca metrică semantică bazată pe numărul de accesări din Google pentru un termen, altul și combinația acestora [19] ; a extins conceptul de distanță informațională de la perechi de cuvinte la liste finite (abandonând de fapt relațiile în favoarea hipergrafelor ) [20] ; a dezvoltat o serie de metode pentru derivarea automată a sensului cuvintelor necunoscute pe baza asemănării lor informaționale cu cuvintele cunoscute [21] [22] . Unele dintre metodele de analiză a clusterelor propuse de el sunt atât de bune încât funcționează de multe ori mai rapid decât analogii lor - de exemplu, gruparea ierarhică folosind algoritmul de urcare și programarea genetică paralelă necesită doar o matrice de distanță și construiește o dendrogramă de 60-80 de obiecte în câteva ore, în timp ce abordările alternative sunt limitate la 20-30 de obiecte sau necesită câțiva ani pentru calcule [23] . Aceleași metode de analiză a clusterelor aplicate muzicii pot determina genul cu mare fiabilitate și pot clasifica lucrări ale compozitorilor [24] .

În programarea genetică, Paul Vitani a propus o metodă bazată pe amestecarea rapidă a lanțurilor Markov care converge cu probabilitate apropiată de unu chiar și pe populații mici, în timp ce metodele alternative suferă de evoluție divergentă aleatoriu [25] . În calcule reversibile  , el a demonstrat posibilitatea simulării reversibile a calculelor ireversibile în timp subexponențial și în costuri de memorie subquadratică [26] . În teoria jocurilor  , el a generalizat problema ruinării unui jucător la un număr mai mare de jucători [27] . În geometrie discretă  , el a rezolvat problema triunghiului Heilbronn în cazul unei distribuții uniforme aleatoare a punctelor de-a lungul unui cerc [28] [29] .

Paul Vitani este inclus în lista celor mai productivi oameni de știință ai catalogului DBLP ca autor și coautor a aproape 250 de publicații științifice arbitrate [30] .

Ucenici

Sub conducerea Paulei Vitani a apărat [2] [31] :

• John Tromp, Aspecte ale algoritmilor și complexității, 1993
• Jap-Henk Hupman, „Sincronizarea comunicațiilor și toleranța la erori”, 1996
• Ronald Kramer, „Proiectarea modulară a protocoalelor criptografice sigure, dar practice ”, 1997
• Peter Grunwald, „Principiul celei mai scurte descrieri și dovezi în condiții de incertitudine”, 1998
• Barbara Terhal, „Algoritmi cuantici și încrucișarea cuantică ”, 1999
• Ronald de Wolf, Computing Quantum and Communication Complexity, 2001
• Wim van Dam, „Despre teoria cuantică a calculului”, 2002
• Hein Roehrig, „Complexitatea interogărilor cuantice și calculul distribuit ”, 2004
• Rudy Kilibrasi, „Inferența statică prin compresia datelor ”, 2007
• Staven de Rooy, „Choice of Shortest Description Model: Challenges and Complications”, 2008
• Wouter Kolen-Weikstra, „Combinație eficientă de strategii. Soluții de înaltă calitate bazate pe sfaturi controversate”, 2011

Note

1. ↑ Paul Vitányi: Lindenmayer Systems: Structure, Languages, and Growth Functions, 1978.
2. ↑ 1 2 3 4 Paul Michael Bela Vitanyi Arhivat 22 ianuarie 2015 la Wayback Machine la Mathematics Genealogy Project .
3. ↑ Paul Vitányi a fost numit CWI Fellow Arhivat la 1 decembrie 2014 la Wayback Machine , ERCIM News No. 53 aprilie 2003.
4. ↑ 1 2 Academy of Europe: Vitanyi Paul Arhivat 22 ianuarie 2015 la Wayback Machine .
5. ↑ Paul Vitányi ontvangt koninklijke onderscheiding Arhivat la 22 ianuarie 2015 la Wayback Machine .
6. ↑ Câteva prelegeri distinse, prelegeri principale, prelegeri invitate, tutoriale Arhivate la 1 decembrie 2014 la Wayback Machine .
7. ↑ L-Systems - The Mathematical Beauty of Plants Arhivat 22 ianuarie 2015 la Wayback Machine .
8. ↑ Paul M. B. Vitányi: Limbi Lindenmayer deterministe, nonterminale și homomorfisme . 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. ↑ An Introduction to Kolmogorov Complexity and Its Applications (Texte in Computer Science) Arhivat 29 august 2018 la Wayback Machine de pe Amazon .
11. ↑ Paul MB Vitányi, Ming Li: Minimum description length induction, Bayesianism, and Kolmogorov complexity . IEEE Transactions on Information Theory 46(2): 446-464 (2000)
12. ↑ Paul M. B. Vitányi: Localitate, comunicare și lungime de interconectare în multicomputer . SIAM J Comput. 17(4): 659-672 (1988)
13. ↑ Tao Jiang, Ming Li, Paul M. B. Vitányi: The Incompressibility Method . 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: Informații semnificative . IEEE Transactions on Information Theory 52(10): 4617-4626 (2006)
16. ↑ Rudi Cilibrasi, Paul MB Vitányi: Clustering by compression Arhivat la 13 octombrie 2008 la 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: Information Distance . IEEE Transactions on Information Theory 44(4): 1407-1423 (1998)
18. ^ Sebastiaan A. Terwijn , Leen Torenvliet, Paul M. B. Vitányi: Nonaproximability of the normalized information distance . Journal of Computer and System Sciences 77(4): 738-742 (2011)
19. ↑ Rudi Cilibrasi, Paul MB Vitányi: The Google Similarity Distance . IEEE Trans. Cunoaștere. DataIng. 19(3): 370-383 (2007)
20. ↑ Paul M. B. Vitányi: Information Distance in Multiples . IEEE Transactions on Information Theory 57(4): 2451–2456 (2011)
21. ^ Rudi Cilibrasi , Paul MB Vitányi: Similarity of Objects and the Meaning of Words Arhivat la 11 octombrie 2008 la Wayback Machine . TAMC 2006: 21-45
22. ↑ Rudi Cilibrasi, Paul MB Vitányi: Automatic Meaning Discovery Using Google Arhivat 22 ianuarie 2015 la Wayback Machine . Complexitatea și aplicațiile Kolmogorov 2006
23. ↑ Rudi Cilibrasi, Paul MB Vitányi: A New Quartet Tree Euristic for Hierarchical Clustering Arhivat 22 ianuarie 2015 la Wayback Machine . Teoria algoritmilor evoluționari 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: A Discipline of Evolutionary Programming . Informatică teoretică 241(1-2): 3-23 (2000)
26. ↑ Harry Buhrman, John Tromp, Paul M. B. Vitányi: Time and Space Bounds for Reversible Simulation . ICALP 2001: 1017-1027
27. ↑ Kazuyuki Amano, John Tromp, Paul M. B. Vitányi, Osamu Watanabe: On a Generalized Ruin Problem . RANDOM-APROX. 2001: 181-191
28. ↑ Tao Jiang, Ming Li, Paul M. B. Vitányi: Dimensiunea așteptată a triunghiurilor lui Heilbronn . IEEE Conference on Computational Complexity 1999: 105-113
29. ↑ Tao Jiang, Ming Li, Paul MB Vitányi: Aria medie a cazului a triunghiurilor de tip Heilbronn . Structuri aleatorii și algoritmi 20(2): 206-219 (2002)
30. ↑ Cei mai prolifici autori DBLP , arhivat 13 februarie 2009. .
31. ↑ Doctorat trecut. Studenți arhivat la 1 decembrie 2014 la Wayback Machine .

Site-uri tematice	Google Academic Genealogie matematică ORCID zbMATH Deschide Portal de matematică integral rusesc
În cataloagele bibliografice BIBSYS: 90290589 BNF : 124933863 ISNI : 0000 0001 1578 4969 J9U : 987007447082805171 LCCN : n81091576 NTA : 06767884X NUKAT : n95207712 SUDOC : 034146601 VIAF : 94523542 WorldCat VIAF : 94523542