Peter Gacs

Vikipediya, ochiq ensiklopediya

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 | manbasini tahrirlash]

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 | manbasini tahrirlash]

  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