Vikipediya

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

tahrir

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[1]. 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[2].

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 qilgan[3][4][5]. Gacs Sipser-Lautemann nazariyasi ham hissa qoʻshdi[6]. 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, shu bilan birga ijobiy stavkalar taxminining qarshi misolini taqdim etadi. [7] Uning taklif qilgan qurilishi koʻp hajmli va murakkabdir[8]. Keyinchalik, shunga oʻxshash usul aperiod tikish setlarini qurish uchun ishlatilgan. [9]

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 [10] va tasodifiylik kamchiliklari uchun, shu jumladan keyinchalik qayta topilgan va hozirda etarli ortiqcha lemma deb nomlangan natijalarni oʻrnatdi[11][12]. 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[13][14].

U algoritmik statistikaga asoslangan , [15] algoritmik murakkablik uchun kvant versiyalaridan birini joriy etdi, [16] umumiy maydonlar uchun algoritmik tasodifiylik xususiyatlarini va umumiy oʻlchov sinflarini[17] oʻrgandi [18] [19] . Ushbu natijalarning baʼzilari uning algoritmik axborot nazariyasiga doir tadqiqotlarida qamrab olingan[20][21]. 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)[22]. Rudolf Ahlswede va Körner bilan birgalikda u portlash lemmasi isbotlandi[23].

Manbalar

tahrir
  1. ↑ „The list of people that worked at the Renyi Institute“. Alfréd Rényi Institute of Mathematics. Qaraldi: 2020-yil 5-dekabr.
  2. ↑ „Bio“. Boston University Computer Science Department. Qaraldi: 2020-yil 5-dekabr.
  3. ↑ Kolata, Gina Bari (November 2, 1979). "Mathematicians Amazed by Russian's Discovery". Science 206 (4418): 545–546. doi:10.1126/science.206.4418.545. PMID 17759415. https://archive.org/details/sim_science_1979-11-02_206_4418/page/545. 
  4. ↑ Gács, Peter; Lovász, Laszlo (1981), König, H.; Korte, B.; Ritter, K. (muh.), „Khachiyan's algorithm for linear programming“, Mathematical Programming at Oberwolfach, Berlin, Heidelberg: Springer Berlin Heidelberg, 14-jild, 61–68-bet, doi:10.1007/bfb0120921, ISBN 978-3-642-00805-4, qaraldi: 2020-11-27
  5. ↑ Shenitzer, Abe, and John Stillwell, eds. Mathematical evolutions. MAA, 2002.
  6. ↑ Lautemann, Clemens (1983-11-08). "BPP and the polynomial hierarchy" (en). Information Processing Letters 17 (4): 215–217. doi:10.1016/0020-0190(83)90044-3. ISSN 0020-0190. https://dx.doi.org/10.1016%2F0020-0190%2883%2990044-3. 
  7. ↑ Gács, Peter (2001-04-01). "Reliable Cellular Automata with Self-Organization" (en). Journal of Statistical Physics 103 (1): 45–267. doi:10.1023/A:1004823720305. ISSN 1572-9613. https://doi.org/10.1023/A:1004823720305. 
  8. ↑ Gray, Lawrence F. (2001-04-01). "A Reader's Guide to Gacs's "Positive Rates" Paper" (en). Journal of Statistical Physics 103 (1): 1–44. doi:10.1023/A:1004824203467. ISSN 1572-9613. https://doi.org/10.1023/A:1004824203467. 
  9. ↑ Durand, Bruno; Romashchenko, Andrei; Shen, Alexander (2012-05-01). "Fixed-point tile sets and their applications" (en). Journal of Computer and System Sciences. In Commemoration of Amir Pnueli 78 (3): 731–764. doi:10.1016/j.jcss.2011.11.001. ISSN 0022-0000. 
  10. ↑ Peter Gacs. On the symmetry of algorithmic information. Doklady Akademii Nauk SSSR, 218(6):1265-1267, 1974. In Russian.
  11. ↑ Peter Gacs. Exact expressions for some randomness tests. Z. Math. Log. Grdl. M., 26:385-394, 1980.
  12. ↑ Downey, Rodney G., and Denis R. Hirschfeldt. Algorithmic randomness and complexity. Springer, 2010
  13. ↑ 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-303
  14. ↑ Li, Ming, and Paul Vitányi. An introduction to Kolmogorov complexity and its applications. Vol. 3. New York: Springer, 2008.
  15. ↑ Peter Gacs, John Tromp, and Paul M. B. Vitanyi. Algorithmic statistics. IEEE Transactions on Information Theory, 47:2443-2463, 2001. arXiv:math/0006233[math. PR]. Short version with similar title in Algorithmic Learning Theory, LNCS 1968/2000.
  16. ↑ 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.
  17. ↑ 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.
  18. ↑ Peter Gacs. Uniform test of algorithmic randomness over a general space. Theoretical Computer Science, 341(1-3):91-137, 2005.
  19. ↑ 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.
  20. ↑ 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.
  21. ↑ 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.
  22. ↑ Peter Gacs and Janos Korner. Common information is far less than mutual information. Problems of Control and Inf. Th., 2:149-162, 1973.
  23. ↑ Ahlswede, Gacs, Körner Bounds on conditional probabilities with applications in multiuser communication, Z. Wahrsch. und Verw. Gebiete 34, 1976, 157-177 
"https://uz.wikipedia.org/w/index.php?title=Peter_Gacs&oldid=4285410" dan olindi