Peter Gacs

Peter Gács (Macar tələffüzü: ['pe:ter 'ga:tʃ]; ) — həm də peşəkar olaraq Peter Gács kimi tanınır, macar- amerikalı riyaziyyatçı və kompüter alimi, professor və Macarıstan Akademiyasının xarici üzvüdür. Elmlər üzrə. O, etibarlı hesablama, hesablama təsadüfiliyi, alqoritmik mürəkkəblik, alqoritmik ehtimal və məlumat nəzəriyyəsi sahələrindəki işi ilə tanınır.

 Karyera 
Peter Gacs doğma şəhərində orta məktəbdə oxuyub və daha sonra 1970-ci ildə Budapeştdəki Lorand Eötvös Universitetini bitirib. Qacs əmək fəaliyyətinə Macarıstan Elmlər Akademiyasının Tətbiqi Riyaziyyat İnstitutunda elmi işçi kimi başlamışdır . 1978-ci ildə Frankfurt Höte Universitetində doktorluq dərəcəsi almışdır. Təhsil aldığı müddətdə o, Moskva Dövlət Universitetində olmaq, Andrey Kolmoqorov və tələbəsi Leonid A. Levinlə işləmək imkanı qazanıb. 1979-cu ilə qədər Stanford Universitetində tədqiqatçı vəzifəsində çalışıb. O, 1985-ci ildə Boston Universitetinə köçməzdən əvvəl 1980–1984-cü illərdə Rochester Universitetində dosent olub. 1992-ci ildən professordur .

Gacs kompüter elminin bir çox sahələrinə töhfə verdi. Qacs və László Lovász ilk dəfə 1979-cu ilin avqustunda beynəlxalq ictimaiyyətin diqqətini ellipsoid metoduna çəkdilərShenitzer, Abe, and John Stillwell, eds. Mathematical evolutions. MAA, 2002. . Gacs Sipser-Lautemann nəzəriyyəsi də öz töhfəsini verdi . Onun əsas töhfələri və tədqiqatları mobil avtomatlara və Kolmoqorov mürəkkəbliyinə yönəlib.

GKL qaydasından (Gacs-Kurdyumov-Levin qaydası) başqa, onun hüceyrə avtomatları sahəsinə verdiyi ən mühüm töhfə müsbət sürət konyukturasına əks-nümunə verməklə etibarlı birölçülü hüceyrə avtomatının qurulmasıdır. Onun təklif etdiyi tikinti həcmli və mürəkkəbdir . Daha sonra oxşar üsuldan aperiodik mərc dəstləri qurmaq üçün istifadə edilmişdir.

Gacs alqoritmik məlumat nəzəriyyəsi və Kolmogorov mürəkkəbliyi sahəsində bir neçə mühüm məqalənin müəllifidir. Leonid A. Levin ilə birlikdə o, prefiks mürəkkəbliyinin əsas xüsusiyyətlərini, o cümlədən cüt mürəkkəblik düsturunu Peter Gacs. On the symmetry of algorithmic information. Doklady Akademii Nauk SSSR, 218(6):1265–1267, 1974. In Russian. və təsadüfi qüsurların nəticələrini, o cümlədən sonradan yenidən kəşf edilmiş və indi kifayət qədər artıqlıq lemması adlandırılan 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 . O göstərdi ki, mürəkkəblik və aprior ehtimal arasındakı uyğunluq, prefiks mürəkkəbliyi üçün keçərlidir, monoton mürəkkəblik və sabit aprior ehtimal üçün etibarsızdır 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. .

O, alqoritmik statistikaya əsaslanan alqoritmik mürəkkəbliyin kvant versiyalarından birini təqdim etmişdir 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., 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. ümumi sahələr və ümumi ölçü sinifləri üçün alqoritmik təsadüfiliyin xassələrini öyrənmişdir 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. 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.  . Bu nəticələrin bəziləri onun alqoritmik informasiya nəzəriyyəsi üzrə tədqiqatında işıqlandırılmışdır 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.  . O, həmçinin klassik və alqoritmik məlumat nəzəriyyəsi arasındakı sərhəddə nəticələri sübut etdi: paylaşılan və qarşılıqlı məlumat arasındakı fərqi göstərən mühüm nümunə (János Körner ilə) 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 və Körner ilə birlikdə partlayış lemmasını sübut etdi Ahlswede, Gacs, Körner Bounds on conditional probabilities with applications in multiuser communication, Z. Wahrsch. und Verw. Gebiete 34, 1976, 157–177 .

 İstinadlar 

 Xarici keçidlər