Peter Gacs

Peter Gács (Macar tələffüzü: ['pe:ter 'ga:tʃ]; 9 may 1947, Budapeş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.

Peter Gacs
Doğum tarixi 9 may 1947(1947-05-09) (77 yaş)
Doğum yeri
Təhsili

Karyera

[redaktə | mənbəni redaktə et]

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

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ər[4] . 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[5] 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[6][7] . 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[8][9] .

O, alqoritmik statistikaya əsaslanan alqoritmik mürəkkəbliyin kvant versiyalarından birini təqdim etmişdir[10],[11] ümumi sahələr və ümumi ölçü sinifləri üçün alqoritmik təsadüfiliyin xassələrini öyrənmişdir[12][13][14] . 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[15][16] . 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ə)[17] . Rudolf Ahlswede və Körner ilə birlikdə partlayış lemmasını sübut etdi[18] .

İstinadlar

[redaktə | mənbəni redaktə et]
  1. ↑ 1 2 Mathematics Genealogy Project (ing.). 1997.
  2. ↑ "The list of people that worked at the Renyi Institute". Alfréd Rényi Institute of Mathematics. March 2, 2022 tarixində arxivləşdirilib. İstifadə tarixi: December 5, 2020.
  3. ↑ "Bio". Boston University Computer Science Department. February 26, 2021 tarixində arxivləşdirilib. İstifadə tarixi: December 5, 2020.
  4. ↑ Shenitzer, Abe, and John Stillwell, eds. Mathematical evolutions. MAA, 2002.
  5. ↑ Peter Gacs. On the symmetry of algorithmic information. Doklady Akademii Nauk SSSR, 218(6):1265–1267, 1974. In Russian.
  6. ↑ Peter Gacs. Exact expressions for some randomness tests. Z. Math. Log. Grdl. M., 26:385–394, 1980.
  7. ↑ Downey, Rodney G., and Denis R. Hirschfeldt. Algorithmic randomness and complexity. Springer, 2010
  8. ↑ 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
  9. ↑ Li, Ming, and Paul Vitányi. An introduction to Kolmogorov complexity and its applications. Vol. 3. New York: Springer, 2008.
  10. ↑ 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.
  11. ↑ 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.
  12. ↑ 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.
  13. ↑ Peter Gacs. Uniform test of algorithmic randomness over a general space. Theoretical Computer Science, 341(1–3):91–137, 2005.
  14. ↑ 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.
  15. ↑ 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.
  16. ↑ 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.
  17. ↑ Peter Gacs and Janos Korner. Common information is far less than mutual information. Problems of Control and Inf. Th., 2:149–162, 1973.
  18. ↑ Ahlswede, Gacs, Körner Bounds on conditional probabilities with applications in multiuser communication, Z. Wahrsch. und Verw. Gebiete 34, 1976, 157–177

Xarici keçidlər

[redaktə | mənbəni redaktə et]