Vitani, Paul

Paul Michael Béla Vitányi je významný nizozemský vědec v oblasti teoretické informatiky , teorie algoritmů a výpočetní složitosti , profesor na univerzitě v Amsterdamu a výzkumný pracovník Centra pro matematiku a informatiku . Vitani je po matce Holanďan a po otci Maďar.

Paul Vitani získal inženýrský titul v roce 1971 na Delft University of Technology , ve stejném roce nastoupil na postgraduální studium v ​​Matematickém centru v Amsterdamu, kde stále pracuje (nyní se tento výzkumný ústav nazývá „Centrum pro matematiku a informatiku“). . V roce 1978 obhájil doktorskou práci na téma " Lindenmeierovy systémy : struktura, jazyky a růstové funkce" [2] na Free University of Amsterdam a brzy se stal vedoucím nově vytvořené katedry, kterou přivedl do světa úrovně v oblasti kvantových výpočtů, distribuovaných algoritmů, informací z teorie algoritmů a reverzibilních adiabatických výpočtů. V roce 2003 byl přeložen na pozici čestného výzkumného pracovníka (CWI Fellow) [3] . V roce 2005 získal nejvyšší profesuru (hoogleraar 1 [4] ) na největší univerzitě v Nizozemsku. V roce 2007 byl povýšen na rytíře Řádu nizozemského lva [5] . V roce 2011 byl zvolen členem Evropské akademie věd [4] . Jako mnoho vědců jeho úrovně odvedl Paul Vitani mnoho redakční práce ve významných časopisech ve svém oboru a byl často zván na konference a workshopy k plenárním prezentacím [6] .

Příspěvek k vědě

Lindenmeierovy systémy, nazývané také L-systémy, na kterých Paul Vitani pracoval jako postgraduální student, jsou přepisovací systémy , které souvisejí s formálními gramatikami [7] a liší se především tím, že v každém inferenčním kroku je pravidlo aplikováno nikoli na jeden vybraný (ne -terminal) symbol, ale na všechny znaky řetězce současně. Zpočátku byly L-systémy navrženy botanikem Aristidem Lindenmeierem , aby modelovaly vývoj jednobuněčných organismů a dalších větvících se struktur. Vitani je zvážil z formálního hlediska a objasnil mnoho bodů týkajících se tříd jazyků generovaných L-systémy, stejně jako použití neterminálů a homomorfismů . Zejména ukázal, že pokud v deterministických L-systémech (tj. v těch, kde se derivační strom nevětví) uvažujeme rodinu rozšíření (jazyky generované neterminálem), pak nebude úplně obsahovat třídu regulárních jazyků , ale jeho uzavření písmenem po písmenu homomorfismem ekvivalentní třídě rekurzivně spočetných jazyků [8] . Ukázal také, že použití rozšíření, které se ve skutečnosti scvrkává na množinově teoretický průnik jazyka se množinou terminálů (abeceda), je v mnoha případech v praxi ekvivalentní uvažování o přepisování invariantních řetězců – to znamená, že předvedl spojení stabilizující morfogeneze s teorií formálních jazyků [9] .

Paul Vitani spolu se svým kolegou Ming Li významně přispěl k teorii Kolmogorovovy složitosti , včetně napsání knihy „Úvod do Kolmogorovovy složitosti a jejích aplikací“ [10] (vydáno v roce 1993, 1997, 2008). Samotný koncept Kolmogorovovy složitosti existoval dávno před ním (navržený nezávisle Solomonoffem a Kolmogorovem v 60. letech 20. století) a scvrkává se na tvrzení, že existuje určitá abstraktní popisná složitost jakéhokoli řetězce, která se rovná délce minimálního programu, který může tento řetězec vytvořit. (pro jednoduchost to můžeme považovat za programovací jazyk Turingův stroj , i když to není nutné: stačí opravit nějaký univerzální popis nebo kódovací jazyk). Taková složitost řetězce a vlastně jakéhokoli jiného objektu představuje absolutní, často nedosažitelné, minimální množství informací, které může řetězec nebo předmět obsadit bez speciálních triků, jako je vzdání se univerzality. Kolmogorovova složitost je příhodná teoretická abstrakce, v praxi často nepoužitelná, protože je prokazatelně nevyčíslitelná . Paul Vitani byl jedním z prvních, kdo pro něj našel praktické aplikace v teorii automatů nebo v analýze algoritmů. Knize předcházela jeho samostatná práce o vybarvování grafů s omezenou přesností, algoritmické porovnávání pásky, fronty a zásobníku , revize Chomského hierarchie , spojení nejhorších scénářů s průměry atd. Princip nejkratšího popisu formuloval Vitani, Lee a jejich studenti jako abstrakce založené na Bayesově teorému a Kolmogorovově složitosti byla získána řada závěrů praktického charakteru – například, že komprese dat je nejlepší strategií, jak se přiblížit co nejkratší délce popisu dat nebo přenášených dat. zpráva [11] . V praxi to umožňuje nahradit abstraktní, komplexní a nevyčíslitelný koncept popisné složitosti jeho aproximací v podobě délky zprávy komprimované některým dostupným archivátorem .

Ve výpočetní teorii zavedl Paul Vitani koncept lokality výpočtů a ukázal, že vyhýbání se von Neumannovým sekvenčním výpočtům neřeší obecný problém, protože samotný výpočet probíhá na určitém místě a jeho výsledky musí být přeneseny na jiné místo k uložení. nebo pokračovat ve výpočtech - a tato komunikace zabírá čas a prostor, což by se mělo odrazit v realistických modelech nekonzistentních výpočtů [12] . Kolmogorovova složitost byla také užitečná při odhadu zatížení sítí různých topologií z různých algoritmů pomocí tzv. metody nestlačitelnosti [13] . Metoda je podobná mnohem jednoduššímu Dirichletovu principu a je založena především na tom, že grafů s vysokou Kolmogorovovou složitostí je mnohem více než grafů s nízkou složitostí, že náhodné grafy budou Kolmogorovovým komplexem s pravděpodobností blízkou jednotě [14] . Obecně se informace v jakémkoli objektu pro Vitani dělí na dvě části: podstatnou (která určuje pravidelnost objektu) a nepodstatnou (stochastické doplňky). Relativní množství podstatných informací nazývá mírou sofistikovanosti a objekty, pro které je maximálně absolutně nestochastické [15] .

Studie teorie informace, složitosti a komprese nevyhnutelně přivedly Paula Vitaniho k metrikám , které měří informační vzdálenost mezi objekty (řetězci, dokumenty, jazyky, obrázky atd.): on a jeho studenti navrhli metodu shlukové analýzy založenou na kompresi dat [16]. ; navrhl normalizovanou informační vzdálenost [17] a normalizovanou vzdálenost sevření [18] jako měřítka toho, jak obtížné je transformovat jeden objekt na jiný; implementoval tzv. míru podobnosti Google jako sémantickou metriku založenou na počtu zásahů v Google pro jeden výraz, druhý a jejich kombinaci [19] ; rozšířil koncept informační vzdálenosti z dvojic slov na konečné seznamy (ve skutečnosti opouští vztahy ve prospěch hypergrafů ) [20] ; vyvinuli řadu metod pro automatické odvozování významu neznámých slov na základě jejich informační podobnosti se známými slovy [21] [22] . Některé metody shlukové analýzy, které navrhuje, jsou tak dobré, že fungují mnohonásobně rychleji než jejich analogy – například hierarchické shlukování pomocí algoritmu šplhání a paralelního genetického programování vyžaduje pouze matici vzdálenosti a vytváří dendrogram 60–80 objektů v několik hodin, zatímco alternativní přístupy jsou omezeny na 20-30 objektů nebo vyžadují několik let pro výpočty [23] . Stejné metody shlukové analýzy aplikované na hudbu mohou s vysokou spolehlivostí určit žánr a klasifikovat díla skladatelů [24] .

V genetickém programování Paul Vitani navrhl metodu založenou na rychlém míchání Markovových řetězců , které konvergují s pravděpodobností blízkou jedné i na malých populacích, zatímco alternativní metody trpí náhodně divergentní evolucí [25] . V reverzibilních výpočtech  prokázal možnost reverzibilní simulace nevratných výpočtů v subexponenciálním čase a v nákladech subkvadratické paměti [26] . V teorii her  zobecnil problém zničení hráče na větší počet hráčů [27] . V diskrétní geometrii  vyřešil problém Heilbronnského trojúhelníku v případě náhodného rovnoměrného rozložení bodů po kružnici [28] [29] .

Paul Vitani je zařazen do seznamu nejproduktivnějších vědců katalogu DBLP jako autor a spoluautor téměř 250 vědeckých recenzovaných publikací [30] .

Učni

Pod vedením Pauly Vitani obhajoval [2] [31] :

• John Tromp, Aspects of Algorithms and Complexity, 1993
• Jap-Henk Hupman, "Synchronizace komunikace a odolnost proti chybám", 1996
• Ronald Kramer, "Modulární návrh bezpečných, ale praktických kryptografických protokolů ", 1997
• Peter Grunwald, „Princip nejkratšího popisu a důkazu za nejistoty“, 1998
• Barbara Terhal, "Kvantové algoritmy a kvantové zapletení ", 1999
• Ronald de Wolf, Quantum Computing and Communication Complexity, 2001
• Wim van Dam, „O kvantové teorii počítání“, 2002
• Hein Roehrig, "Složitost kvantových dotazů a distribuované výpočty ", 2004
• Rudy Kilibrasi, "Statická inference kompresí dat ", 2007
• Staven de Rooy, "Volba nejkratšího popisu modelu: Výzvy a komplikace", 2008
• Wouter Kolen-Weikstra, „Efektivní kombinace strategií. Vysoce kvalitní řešení založená na kontroverzních radách“, 2011

Poznámky

1. ↑ Paul Vitanyi: Lindenmayer Systems: Structure, Languages, and Growth Functions, 1978.
2. ↑ 1 2 3 4 Paul Michael Bela Vitanyi Archivováno 22. ledna 2015 na Wayback Machine v Matematickém Genealogickém projektu .
3. ↑ Paul Vitányi byl jmenován členem CWI Archivováno 1. prosince 2014 na Wayback Machine , ERCIM News No. 53 dubna 2003.
4. ↑ 1 2 Akademie Evropy: Vitanyi Paul Archivováno 22. ledna 2015 na Wayback Machine .
5. ↑ Paul Vitányi ontvangt koninklijke onderscheiding Archivováno 22. ledna 2015 na Wayback Machine .
6. ↑ Některé významné přednášky, klíčové přednášky, zvané přednášky, tutoriály Archivováno 1. prosince 2014 na Wayback Machine .
7. ↑ L-Systems – The Mathematical Beauty of Plants Archivováno 22. ledna 2015 na Wayback Machine .
8. ↑ Paul M. B. Vitányi: Deterministické Lindenmayerovy jazyky, neterminály a homomorfismy . Teoretická informatika 2(1): 49-71 (1976).
9. ↑ Paul M. B. Vitanyi, Adrian Walker: Stable String Languages ​​of Lindenmayer Systems . Information and Control 37(2): 134-149 (1978).
10. ↑ Úvod do Kolmogorovovy složitosti a jejích aplikací (Texty v informatice) Archivováno 29. srpna 2018 na Wayback Machine na Amazonu .
11. ↑ Paul MB Vitanyi, Ming Li: Indukce minimální délky popisu, Bayesianismus a Kolmogorovova složitost . IEEE Transactions on Information Theory 46(2): 446-464 (2000)
12. ↑ Paul M. B. Vitányi: Lokalita, komunikace a délka propojení ve více počítačích . Počítač SIAM J. 17(4): 659-672 (1988)
13. ↑ Tao Jiang, Ming Li, Paul M. B. Vitanyi: Metoda nestlačitelnosti . SOFSEM 2000: 36-53
14. ↑ Harry Buhrman, Ming Li, John Tromp, Paul M. B. Vitányi: Kolmogorovovy náhodné grafy a metoda nestlačitelnosti . Počítač SIAM J. 29(2): 590-599 (1999).
15. ↑ Paul M. B. Vitanyi: Smysluplné informace . IEEE Transactions on Information Theory 52(10): 4617-4626 (2006)
16. ↑ Rudi Cilibrasi, Paul MB Vitányi: Shlukování kompresí Archivováno 13. října 2008 na 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: Neaproximovatelnost normalizované informační vzdálenosti . Journal of Computer and System Sciences 77(4): 738-742 (2011)
19. ↑ Rudi Cilibrasi, Paul MB Vitányi: The Google Similarity Distance . IEEE Trans. Knowl. DataEng. 19(3): 370-383 (2007)
20. ↑ Paul M. B. Vitányi: Informační vzdálenost v násobcích . IEEE Transactions on Information Theory 57(4): 2451–2456 (2011)
21. ↑ Rudi Cilibrasi, Paul MB Vitányi: Podobnost objektů a význam slov Archivováno 11. října 2008 na Wayback Machine . TAMC 2006: 21-45
22. ↑ Rudi Cilibrasi, Paul MB Vitányi: Automatické zjišťování významu pomocí Google Archivováno 22. ledna 2015 na Wayback Machine . Kolmogorov Složitost a aplikace 2006
23. ↑ Rudi Cilibrasi, Paul MB Vitányi: Heuristika nového stromu kvartetu pro hierarchické shlukování archivována 22. ledna 2015 na Wayback Machine . Teorie evolučních algoritmů 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: Disciplína evolučního programování . Teoretická informatika 241 (1-2): 3-23 (2000)
26. ↑ Harry Buhrman, John Tromp, Paul M. B. Vitanyi: Hranice času a prostoru pro reverzibilní simulaci . ICALP 2001: 1017-1027
27. ↑ Kazuyuki Amano, John Tromp, Paul M. B. Vitanyi, Osamu Watanabe: On a Generalized Ruin Problem . RANDOM-APPROX 2001: 181-191
28. ↑ Tao Jiang, Ming Li, Paul M. B. Vitanyi: Očekávaná velikost Heilbronnových trojúhelníků . IEEE Conference on Computational Complexity 1999: 105-113
29. ↑ Tao Jiang, Ming Li, Paul MB Vitányi: Průměrná oblast trojúhelníků typu Heilbronn . Random Structures and Algorithms 20(2): 206-219 (2002)
30. ↑ Nejplodnější autoři DBLP Archivováno 13. února 2009. .
31. ↑ Minulé Ph.D. Studenti archivováni 1. prosince 2014 na Wayback Machine .

Tematické stránky	Google Scholar Matematická genealogie ORCID zbMATH Otevřeno Všeruský matematický portál
V bibliografických katalozích BIBSYS: 90290589 BNF : 124933863 ISNI : 0000 0001 1578 4969 J9U : 987007447082805171 LCCN : n81091576 NTA : 06767884X NUKAT : n95207712 SUDOC : 034146601 VIAF : 94523542 WorldCat VIAF : 94523542