Peter Gacs

Peter Gács (Hongari tilidagi izoh: 'pe:ter 'ga:tʃ; 9 may 1947 yilda tugʻilgan), kasbda Peter Gacs deb ham tanilgan, Vengriyalik-Amerikalik matematik va kompyuter olim, professor va Vengriyalik Fanlar akademiyasining tashqi aʼzosi. U ishonchli hisoblash, hisoblashda tasodifiylik, algoritmik murakkablik, algoritmik ehtimollik va axborot nazariyasi sohasida ishlagani uchun taniqli.

 Karyerasi 
Peter Gacs oʻz shaharchasida oʻrta maktabga oʻqigan va keyinchalik 1970 yilda Budapeştdagi Loránd Eötvös universiteti diplom olgan. Gacs oʻz faoliyatini Vengriya fanlar akademiyasining Taqdim etilgan matematikasi institutida tadqiqotchi sifatida boshladi. 1978 yilda Goethe universiteti Frankfurt doktorlik darajasini oldi. Oʻqigan yillarida u Moskva davlat universiteti tashrif buyurish va Andrey Kolmogorov va uning talaba Leonid A Levin bilan ishlash imkoniyatiga ega boʻldi. 1979 yilgacha u Stanford universiteti tadqiqotchi boʻlib ishlagan. U 1980 yildan 1984 yilgacha Rochester universiteti yordamchisi boʻlib, 1985 yilda Boston universiteti oʻtadi. 1992 yildan buyon professor boʻlib kelmoqda.

Gacs kompyuter fanining koʻplab sohalarida hissa qoʻshgan. Gács va László Lovász 1979 yil avgust oyida ellipsoid usuli ilk bor xalqaro hamjamiyatning eʼtiborini jalb qilganShenitzer, Abe, and John Stillwell, eds. Mathematical evolutions. MAA, 2002.. Gacs Sipser-Lautemann nazariyasi ham hissa qoʻshdi. Uning asosiy hissasi va tadqiqotlari hujayra avtomatlari va Kolmogorov murakkabligiga qaratilgan.

GKL qoidasi (Gacs-Kurdyumov-Levin qoidasi) dan tashqari, hujayra avtomatlari sohasida uning eng muhim hissasi ishonchli bir oʻlchamli hujayra avtomati qurilishi boʻlib, ijobiy stavkalar taxminining qarshi misolini taqdim etadi. Uning taklif qilgan qurilishi koʻp hajmli va murakkabdir. Keyinchalik, shunga oʻxshash usul aperiod tikish setlarini qurish uchun ishlatilgan. 

Gacs algoritmik axborot nazariyasi va Kolmogorov murakkabligi sohasida bir nechta muhim maqolalar muallifidir. Leonid A. Levin bilan birgalikda u prefiks murakkabligining asosiy xususiyatlarini, shu jumladan juftlarning murakkabligi formulasi Peter Gacs. On the symmetry of algorithmic information. Doklady Akademii Nauk SSSR, 218(6):1265-1267, 1974. In Russian. va tasodifiylik kamchiliklari uchun, shu jumladan keyinchalik qayta topilgan va hozirda etarli ortiqcha lemma deb nomlangan natijalarni oʻrnatdi Peter Gacs. Exact expressions for some randomness tests. Z. Math. Log. Grdl. M., 26:385-394, 1980. Downey, Rodney G., and Denis R. Hirschfeldt. Algorithmic randomness and complexity. Springer, 2010. U komplekslik va a priori ehtimollik oʻrtasidagi moslik, prefiks kompleksligi uchun mavjud boʻlgan, monoton komplekslik va doimiy a priori ehtimoli uchun haqiqiy emasligini koʻrsatdi Peter Gacs. On the relation between descriptional complexity and algorithmic probability. Theoretical Computer Science, 22:71-93, 1983. Short version: Proc. 22nd
IEEE FOCS (1981) 296-303Li, Ming, and Paul Vitányi. An introduction to Kolmogorov complexity and its applications. Vol. 3. New York: Springer, 2008..

U algoritmik statistikaga asoslangan , Peter Gacs, John Tromp, and Paul M. B. Vitanyi. Algorithmic statistics. IEEE Transactions on Information Theory, 47:2443-2463, 2001. arXiv:math/0006233math. PR. Short version with similar title in Algorithmic Learning Theory, LNCS 1968/2000. algoritmik murakkablik uchun kvant versiyalaridan birini joriy etdi, Aditi Dhagat, Peter Gacs, and Peter Winkler. On playing „twenty questions“ with a liar. In Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, SODAʼ92, pages 16-22, Philadelphia, PA, USA, 1992. Society for Industrial and Applied Mathematics. umumiy maydonlar uchun algoritmik tasodifiylik xususiyatlarini va umumiy oʻlchov sinflarini Laurent Bienvenu, Peter Gacs, Mathieu Hoyrup, Cristobal Rojas, and Alexander Shen. Randomness with respect to a class of measures. Proceedings of the Steklov Institute of Mathematics, 274(1):34-89, 2011. In English and Russian, also in arXiv:1103.1529. oʻrgandi Peter Gacs. Uniform test of algorithmic randomness over a general space. Theoretical Computer Science, 341(1-3):91-137, 2005. Peter Gacs, Mathieu Hoyrup, and Cristobal Rojas. Randomness on computable probability spaces — a dynamical point of view. Theory of Computing Systems, 48:465-485, 2011. 10.1007/s00224-010-9263-x, arXiv:0902.1939. Appeared also in
STACS 2009. . Ushbu natijalarning baʼzilari uning algoritmik axborot nazariyasiga doir tadqiqotlarida qamrab olingan Peter Gacs. Lecture notes on descriptional complexity and randomness. Technical report, Boston University, Computer Science Dept., Boston, MA 02215, 2009.
www.cs.bu.edu/faculty/gacs/papers/ait-notes.pdf. Thomas M. Cover, Peter Gacs, and Robert M. Gray. Kolmogorov’s contributions to information theory and algorithmic complexity. The Annals of Probability, 17(3):840-865, 1989. . U shuningdek, klassik va algoritmik axborot nazariyasi oʻrtasidagi chegara boʻyicha natijalarni isbotladi: umumiy va oʻzaro axborot oʻrtasidagi farqni koʻrsatadigan muhim misol (János Körner bilan) Peter Gacs and Janos Korner. Common information is far less than mutual information. Problems of Control and Inf. Th., 2:149-162, 1973. . Rudolf Ahlswede va Körner bilan birgalikda u portlash lemmasi isbotlandi Ahlswede, Gacs, Körner Bounds on conditional probabilities with applications in multiuser communication, Z. Wahrsch. und Verw. Gebiete 34, 1976, 157-177. 

 

Turkum:Amerikalik informatiklar
Turkum:Yashayotgan insonlar
Turkum:1947-yilda tugʻilganlar