Vitani, Paul

Paul Michael Béla Vitányi az elméleti számítástechnika , az algoritmusok elmélete és a számítási komplexitás kiemelkedő holland tudósa, az Amszterdami Egyetem professzora és a Matematikai és Informatikai Központ kutatója . Vitani anyja holland, apja magyar.

Paul Vitani 1971-ben szerzett mérnöki diplomát a Delfti Műszaki Egyetemen, ugyanebben az évben az amszterdami Matematikai Központba lépett posztgraduális iskolába, ahol jelenleg is dolgozik (a kutatóintézetet ma "Matematikai és Informatikai Központnak" hívják). . 1978-ban az Amszterdami Szabadegyetemen védte meg Ph.D. disszertációját " Lindenmeier rendszerek : szerkezet, nyelvek és növekedési funkciók" [2] címmel, majd hamarosan az újonnan létrehozott tanszék vezetője lett, amelyet világgá hozott. szinten a kvantumszámítás, az elosztott algoritmusok, az algoritmuselméleti információk és a reverzibilis adiabatikus számítások területén. 2003-ban tiszteletbeli kutatói munkatársi (CWI Fellow) pozícióba helyezték át [3] . 2005-ben megkapta a legmagasabb professzori címet (hoogleraar 1 [4] ) Hollandia legnagyobb egyetemén. 2007-ben a Holland Oroszlán Lovagrendjébe ütötték [5] . 2011-ben az Európai Tudományos Akadémia tagjává választották [4] . Mint sok hasonló szintű tudós, Paul Vitani is sok szerkesztői munkát végzett a szakterülete jelentős folyóirataiban, és gyakran hívták meg konferenciákra és workshopokra plenáris előadások alkalmával [6] .

Hozzájárulás a tudományhoz

A Lindenmeier-rendszerek, más néven L-rendszerek, amelyeken Paul Vitani végzős hallgatóként dolgozott, olyan újraíró rendszerek , amelyek a formális nyelvtanokhoz [7] kapcsolódnak, és elsősorban abban különböznek egymástól, hogy minden következtetési lépésnél a szabály nem egy kiválasztottra vonatkozik (nem -terminal) szimbólum, hanem a karakterlánc összes karakterére egyszerre. Kezdetben Aristide Lindenmeier botanikus javasolta az L-rendszereket az egysejtű szervezetek és más elágazó struktúrák fejlődésének modellezésére . Vitani formális szempontból vizsgálta őket, és sok pontot tisztázott az L-rendszerek által generált nyelvosztályokkal, valamint a nem terminálok és homomorfizmusok használatával kapcsolatban . Konkrétan megmutatta, hogy ha a determinisztikus L-rendszerekben (vagyis azokban, ahol a származási fa nem ágazik el) egy kiterjesztések családját tekintjük (nem terminálok által generált nyelvek), akkor az nem fogja teljesen tartalmazni az osztályt. reguláris nyelvek közül, de a lezárása betűről betűre homomorfizmussal egyenértékű a rekurzívan felsorolható nyelvek osztályával [8] . Azt is megmutatta, hogy egy kiterjesztést, amely tulajdonképpen egy nyelv halmazelméleti metszéspontjába vezet egy terminálkészlettel (ábécével), a gyakorlatban sok esetben egyenértékű az invariáns karakterláncok átírásával – vagyis bemutatta. a stabilizáló morfogenezis kapcsolata a formális nyelvek elméletével [9] .

Paul Vitani kollégájával , Ming Li- vel együtt jelentős mértékben hozzájárult a Kolmogorov-komplexitás elméletéhez , többek között megírta a "Bevezetés a Kolmogorov-komplexitásba és annak alkalmazásaiba" című könyvet [10] (megjelent 1993-ban, 1997-ben, 2008-ban). Maga a Kolmogorov-komplexitás fogalma már jóval előtte létezett (ezt Solomonoff és Kolmogorov egymástól függetlenül javasolta az 1960-as években), és abból az állításból fakad, hogy bármely karakterláncnak van valamiféle absztrakt leíró összetettsége, amely megegyezik annak a minimális programnak a hosszával, amely ezt a karakterláncot létrehozhatja. (az egyszerűség kedvéért programnyelvnek tekinthetjük Turing-gépnek , bár ez nem szükséges: csak ki kell javítani valami univerzális leírást vagy kódoló nyelvet). Egy karakterlánc, sőt bármely más objektum ilyen összetettsége az abszolút, gyakran elérhetetlen minimális információmennyiséget jelenti, amelyet egy karakterlánc vagy objektum különleges trükkök, például az egyetemesség feladása nélkül elfoglalhat. A Kolmogorov-komplexitás egy kényelmes elméleti absztrakció, amely gyakran haszontalan a gyakorlatban, mert bizonyíthatóan kiszámíthatatlan . Paul Vitani volt az egyik első, aki gyakorlati alkalmazást talált rá az automataelméletben vagy az algoritmuselemzésben. A könyvet külön munkája előzte meg a grafikonok korlátozott pontosságú színezéséről, a szalag, a sor és a verem algoritmikus összehasonlításáról, a Chomsky-hierarchia felülvizsgálatáról, a legrosszabb forgatókönyvek átlagokkal való összekapcsolásáról stb. A legrövidebb leírás elvét Vitani, Lee és tanítványaik Bayes-tételén és Kolmogorov-féle komplexitásán alapuló absztrakcióként számos gyakorlati jellegű következtetést vontak le – például, hogy az adattömörítés a legjobb stratégia egy adatleírás vagy továbbított adat legrövidebb hosszának megközelítésére. üzenet [11] . A gyakorlatban ez lehetővé teszi, hogy a leíró összetettség elvont, összetett és nem kiszámítható fogalmát felváltsa annak közelítésével az üzenet hosszának formájában, amelyet valamilyen elérhető archiváló tömörít .

A számításelméletben Paul Vitani bevezette a számítások lokalitásának fogalmát, és megmutatta, hogy a Neumann -féle szekvenciális számítások elkerülése nem oldja meg az általános problémát, mert maga a számítás egy bizonyos helyen zajlik, és az eredményeit át kell vinni egy másik helyre, ahol tárolni kell. vagy folytassa a számításokat – és ez a kommunikáció időt és helyet foglal el, aminek tükröződnie kell az inkonzisztens számítások reális modelljeiben [12] . A Kolmogorov-komplexitás az úgynevezett tömöríthetetlenségi módszerrel [13] is hasznos volt a különböző topológiájú hálózatok terhelésének becslésében különböző algoritmusok alapján . A módszer hasonló a jóval egyszerűbb Dirichlet-elvhez , és elsősorban azon a tényen alapul, hogy annyival több nagy Kolmogorov-komplexitású gráf létezik, mint alacsony komplexitású gráf, hogy a véletlenszerű gráfok egységhez közeli valószínűséggel Kolmogorov-komplexek lesznek [14] . Általánosságban elmondható, hogy a Vitani számára bármely objektumban található információ két részre oszlik: lényeges (amely meghatározza az objektum szabályosságát) és nem lényeges (sztochasztikus kiegészítések). A lényeges információ relatív mennyiségét a kifinomultság mértékének nevezi, és azokat az objektumokat, amelyeknél ez maximum abszolút nem sztochasztikus [15] .

Az információelmélet, a komplexitás és a tömörítés tanulmányozása elkerülhetetlenül elvezette Paul Vitanit olyan metrikákhoz , amelyek az objektumok (karakterláncok, dokumentumok, nyelvek, képek stb.) közötti információs távolságot mérik: ő és tanítványai egy adattömörítésen alapuló klaszterelemzési módszert javasoltak [16]. ; normalizált információs távolságot [17] és normalizált összenyomási távolságot [18] javasolt annak mértékére , hogy mennyire nehéz az egyik objektumot egy másikká átalakítani; az úgynevezett Google hasonlósági mérőszámot szemantikai mérőszámként valósította meg, amely egy kifejezésre, egy másik kifejezésre és ezek kombinációjára vonatkozó találatok számán alapul [ 19 ] ; kiterjesztette az információs távolság fogalmát a szópárokról a véges listákra (valójában elhagyta a kapcsolatokat a hipergráfok javára ) [20] ; számos módszert fejlesztettek ki az ismeretlen szavak jelentésének automatikus levezetésére az ismert szavakkal való információs hasonlóságuk alapján [21] [22] . Az általa javasolt klaszterelemzési módszerek némelyike ​​annyira jó, hogy sokszor gyorsabban működnek, mint analógjaik – például a mászóalgoritmust használó hierarchikus klaszterezés és a párhuzamos genetikai programozás mindössze távolságmátrixot igényel, és 60-80 objektumból álló dendrogramot épít fel. néhány óra, míg az alternatív megközelítések 20-30 objektumra korlátozódnak, vagy a számításokhoz több év szükséges [23] . A zenére alkalmazott klaszterelemzési módszerek nagy megbízhatósággal határozhatják meg a műfajt és osztályozhatják a zeneszerzők műveit [24] .

A genetikai programozásban Paul Vitani egy olyan Markov-láncok gyors keveredésére épülő módszert javasolt, amely kis populációk esetén is egyhez közeli valószínűséggel konvergál , míg az alternatív módszerek véletlenszerűen eltérő evolúcióban szenvednek [25] . Reverzibilis számítások során bebizonyította az irreverzibilis számítások reverzibilis szimulációjának lehetőségét szubexponenciális  időben és szubquadratikus memóriaköltségekben [26] . A játékelméletben a játékos tönkretételének problémáját nagyobb számú játékosra  általánosította [27] . A diszkrét geometriában  megoldotta a Heilbronn-háromszög feladatát a pontok véletlenszerű egyenletes eloszlása ​​esetén egy kör mentén [28] [29] .

Paul Vitani a DBLP katalógusának legtermékenyebb tudósainak listáján szerepel, mint közel 250 tudományos referált publikáció szerzője és társszerzője [30] .

Tanoncok

Paula Vitani vezetésével megvédte [2] [31] :

• John Tromp, Aspects of Algorithms and Complexity, 1993
• Jap-Henk Hupman, "Kommunikációs szinkronizálás és hibatűrés", 1996
• Ronald Kramer, "Biztonságos, de praktikus kriptográfiai protokollok moduláris tervezése ", 1997
• Peter Grunwald, "A legrövidebb leírás és bizonytalanság elve", 1998
• Barbara Terhal, "Kvantum algoritmusok és kvantumösszefonódás " , 1999
• Ronald de Wolf, Quantum Computing and Communication Complexity, 2001
• Wim van Dam, "A számítás kvantumelméletéről", 2002
• Hein Roehrig, "Quantum Query Complexity and Distributed Computing ", 2004
• Rudy Kilibrasi, "Static Inference by Data Compression ", 2007
• Staven de Rooy, "A legrövidebb leírás modell kiválasztása: Kihívások és komplikációk", 2008
• Wouter Kolen-Weikstra: „A stratégiák hatékony kombinációja. Kiváló minőségű megoldások ellentmondásos tanácsok alapján”, 2011

Jegyzetek

1. ↑ Vitányi Pál: Lindenmayer Systems: Structure, Languages, and Growth Functions, 1978.
2. ↑ 1 2 3 4 Paul Michael Bela Vitanyi Archivált : 2015. január 22., a Wayback Machine at the Mathematics Genealogy Project .
3. ↑ Paul Vitányit kinevezték CWI -taggá archiválva 2014. december 1-én a Wayback Machine -nál , ERCIM News No. 2003. április 53.
4. ↑ 1 2 Academy of Europe: Vitanyi Paul Archivált : 2015. január 22. a Wayback Machine -nél .
5. ↑ Paul Vitányi ontvangt koninklijke onderscheiding Archivált 2015. január 22. at the Wayback Machine .
6. ↑ Néhány előkelő előadás, vitaindító előadás, meghívott előadás, oktatóanyag Archiválva : 2014. december 1. a Wayback Machine -nél .
7. ↑ L-Systems - The Mathematical Beauty of Plants Archivált : 2015. január 22. a Wayback Machine -nál .
8. ↑ Vitányi Paul M. B.: Determinisztikus Lindenmayer-nyelvek, nemterminálisok és homomorfizmusok . 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. ↑ Bevezetés a Kolmogorov-komplexitásba és alkalmazásaiba (Szövegek a számítástechnikában) Archiválva : 2018. augusztus 29. az Amazon Wayback Machine -jén .
11. ↑ Paul MB Vitányi, Ming Li: Minimális leírási hossz indukció, Bayesianizmus és Kolmogorov-komplexitás . IEEE Transactions on Information Theory 46(2): 446-464 (2000)
12. ↑ Paul M. B. Vitányi: Lokalitás, kommunikáció és összeköttetések hossza többszámítógépben . 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. ↑ Vitányi Paul M. B.: Értelmes információk . IEEE Transactions on Information Theory 52(10): 4617-4626 (2006)
16. ↑ Rudi Cilibrasi, Paul MB Vitányi: Clustering by compression Archivált : 2008. október 13. a Wayback Machine -nél . 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: Nonapproximability of the normalized information distance . Journal of Computer and System Sciences 77(4): 738-742 (2011)
19. ↑ Rudi Cilibrasi, Paul MB Vitányi: A Google hasonlósági távolsága . IEEE Trans. Tud. DataEng. 19(3): 370-383 (2007)
20. ↑ Vitányi Paul M. B.: Információs távolság többszörösen . IEEE Transactions on Information Theory 57(4): 2451–2456 (2011)
21. ↑ Rudi Cilibrasi, Paul MB Vitányi: Tárgyak hasonlósága és szavak jelentése Archivált 2008. október 11. a Wayback Machine -nél . TAMC 2006: 21-45
22. ↑ Rudi Cilibrasi, Paul MB Vitányi: Automatic Meaning Discovery Using Google Archived 2015. január 22. at the Wayback Machine . Kolmogorov-komplexitás és alkalmazások 2006
23. ↑ Rudi Cilibrasi, Paul MB Vitányi: A New Quartet Tree Heuristic for Hierarchical Clustering Archivált 2015. január 22-én a Wayback Machine -nél . Az evolúciós algoritmusok elmélete 2006
24. ↑ Rudi Cilibrasi, Paul M. B. Vitányi, Ronald de Wolf: Algorithmic Clustering of Music . WEDELMUSIC 2004: 110-117
25. ↑ Vitányi Paul M. B.: Az evolúciós programozás diszciplínája . Theoretical Computer Science 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 . VÉLETLENSZERŰ-KÖZELÍTÉS 2001: 181-191
28. ↑ Tao Jiang, Ming Li, Paul M. B. Vitányi: The Expected Size of Heilbronn's Triangles . IEEE Conference on Computational Complexity 1999: 105-113
29. ↑ Tao Jiang, Ming Li, Paul MB Vitányi: A Heilbronn-típusú háromszögek átlagos esetterülete . Random Structures and Algorithms 20(2): 206-219 (2002)
30. ↑ A legtöbb termékeny DBLP szerző archiválva : 2009. február 13. .
31. ↑ Elmúlt Ph.D. Hallgatók archiválva 2014. december 1-én a Wayback Machine -n .

Tematikus oldalak	Google ösztöndíjas Matematikai genealógia ORCID zbMATH Nyitva Össz-orosz matematikai portál
Bibliográfiai katalógusokban BIBSYS: 90290589 BNF : 124933863 ISNI : 0000 0001 1578 4969 J9U : 987007447082805171 LCCN : n81091576 NTA : 06767884X NUKAT : n95207712 SUDOC : 034146601 VIAF : 94523542 WorldCat VIAF : 94523542