Βικιπαίδεια

Πίτερ Γκατς

Ο Πέτερ Γκατς (ουγγρικά: Péter Gács, γεννήθηκε στις 9 Μαΐου 1947), ευρέως γνωστός ως Peter Gacs, είναι ουγγρικής καταγωγής Αμερικανός μαθηματικός και επιστήμονας υπολογιστών, καθηγητής και εξωτερικό μέλος της Ουγγρικής Ακαδημίας Επιστημών. Είναι γνωστός για το έργο του σχετικά με την αξιόπιστη υπολογιστική, την τυχαιότητα στην υπολογιστική, την αλγοριθμική πολυπλοκότητα, την αλγοριθμική πιθανότητα και τη θεωρία της πληροφορίας.

Πίτερ Γκατς
Γενικές πληροφορίες
Γέννηση9 Μαΐου 1947
Βουδαπέστη
Εκπαίδευση και γλώσσες
ΣπουδέςΠανεπιστήμιο Γκαίτε της Φραγκφούρτης[1]
Πληροφορίες ασχολίας
Ιδιότηταεπιστήμονας υπολογιστών
μαθηματικός
δεδομένα

Σταδιοδρομία Επεξεργασία

Ο Πίτερ Γκατς φοίτησε στο γυμνάσιο της γενέτειράς του και στη συνέχεια πήρε δίπλωμα (M.S.) από το Πανεπιστήμιο Loránd Eötvös της Βουδαπέστης το 1970. Ο Γκατς ξεκίνησε τη σταδιοδρομία του ως ερευνητής στο Ινστιτούτο Εφαρμοσμένων Μαθηματικών της Ουγγρικής Ακαδημίας Επιστημών[2] και απέκτησε το διδακτορικό του δίπλωμα από το Πανεπιστήμιο Γκαίτε της Φρανκφούρτης το 1978. Κατά τη διάρκεια των σπουδών του είχε την ευκαιρία να επισκεφθεί το Κρατικό Πανεπιστήμιο της Μόσχας και να συνεργαστεί με τον Αντρέι Κολμογκόροφ και τον μαθητή του Λεονίντ Α Λεβίν. Μέχρι το 1979 ήταν επισκέπτης ερευνητικός συνεργάτης στο Πανεπιστήμιο του Στάνφορντ. Ήταν βοηθός καθηγητή στο Πανεπιστήμιο του Ρότσεστερ από το 1980 έως το 1984, οπότε μετακόμισε στο Πανεπιστήμιο της Βοστώνης, όπου και μονιμοποιήθηκε το 1985. Από το 1992 είναι τακτικός καθηγητής[3] .

Επιστημονική εργασία Επεξεργασία

Ο Γκατς συνεισέφερε σε πολλούς τομείς της επιστήμης των υπολογιστών. Ήταν ο Γκατς και ο Λάσλο Λόβαζ που έφεραν για πρώτη φορά την ελλειψοειδή μέθοδο στην προσοχή της διεθνούς κοινότητας τον Αύγουστο του 1979 δημοσιεύοντας τις αποδείξεις και κάποιες βελτιώσεις της.[4][5][6] Ο Γκατς έδωσε επίσης συμβολή στο θεώρημα Σίπσερ-Λάουτεμαν.[7] Η κύρια συμβολή του και η ερευνητική του εστίαση επικεντρώθηκαν στα κυψελοειδή αυτόματα και στην πολυπλοκότητα Κολμογκόροφ.

Εργασία στα κυτταρικά αυτόματα Επεξεργασία

Η σημαντικότερη συνεισφορά του στον τομέα των κυτταρικών αυτομάτων εκτός από τον κανόνα GKL (Γκατς-Kurdyumov-Levin rule) είναι η κατασκευή ενός αξιόπιστου μονοδιάστατου κυτταρικού αυτομάτου που παρουσιάζει έτσι ένα αντιπαράδειγμα στην εικασία των θετικών ποσοστών[8]. Η κατασκευή που προσέφερε είναι πολλαπλής κλίμακας και πολύπλοκη[9]. Αργότερα, η ίδια τεχνική χρησιμοποιήθηκε για την κατασκευή απεριόδιων συνόλων πλακιδίων[10].

Αλγοριθμική θεωρία πληροφοριών και στην πολυπλοκότητα Κολμογόροφ Επεξεργασία

Ο Γκατς συνέγραψε αρκετές σημαντικές εργασίες στον τομέα της αλγοριθμικής θεωρίας της πληροφορίας και της πολυπλοκότητας Κολμογόροφ Μαζί με τον Λεονίντ Α. Λέβιν, καθιέρωσε βασικές ιδιότητες της πολυπλοκότητας προθέματος, συμπεριλαμβανομένου του τύπου για την πολυπλοκότητα των ζευγαριών[11] και για τις ελλείψεις τυχαιότητας, συμπεριλαμβανομένου του αποτελέσματος που ανακαλύφθηκε εκ νέου αργότερα και είναι πλέον γνωστό ως λήμμα της άφθονης περίσσειας[12][13]. Έδειξε ότι η αντιστοιχία μεταξύ πολυπλοκότητας και εκ των προτέρων πιθανότητας που ισχύει για την πολυπλοκότητα προθέματος δεν ισχύει πλέον για μονοτονική πολυπλοκότητα και συνεχή εκ των προτέρων πιθανότητα.[14][15] Στη συναφή θεωρία της αλγοριθμικής τυχαιότητας απέδειξε ότι κάθε ακολουθία είναι αναγώγιμη κατά Turing σε μια τυχαία ακολουθία (το αποτέλεσμα που σήμερα είναι γνωστό ως θεώρημα Gacs-Kucera, καθώς είχε αποδειχθεί ανεξάρτητα από τον Antonin Kucera)[15] Αργότερα εισήγαγε (μαζί με τους συν-συγγραφείς του) την έννοια της αλγοριθμικής απόστασης και απέδειξε τη σύνδεσή της με την υπό συνθήκη πολυπλοκότητα[16][15] .

Ήταν ένας από τους πρωτοπόρους της αλγοριθμικής στατιστικής,[17] εισήγαγε μια από τις κβαντικές εκδοχές για την αλγοριθμική πολυπλοκότητα,[18] μελέτησε τις ιδιότητες της αλγοριθμικής τυχαιότητας για γενικούς χώρους[19][20] και γενικές κατηγορίες μέτρων[21] . Ορισμένα από αυτά τα αποτελέσματα καλύπτονται στις έρευνες του για την αλγοριθμική θεωρία της πληροφορίας.[22][23] Επίσης, απέδειξε αποτελέσματα στα όρια μεταξύ της κλασικής και της αλγοριθμικής θεωρίας πληροφορίας: το θεμελιώδες παράδειγμα που δείχνει τη διαφορά μεταξύ κοινής και αμοιβαίας πληροφορίας (με τον János Körner)[24]. Μαζί με τον Ρούντολφ Άλσβεντε και τον Körner απέδειξε το λήμμα της ανατίναξης (blowing-up lemma)[25].

Δημοσιεύσεις Επεξεργασία

  • Packing of convex sets in the plane with a large number of neighbors (1972)[26]
  • On the relation between descriptional complexity and algorithmic (1983)[27]
  • Deterministic computations whose history is independent of the order of ´ updating (1995)[28]
  • The angel wins (2006)[29]
  • A Turing machine resisting isolated bursts of faults (2013) - kun iu alia[30]

Παραπομπές Επεξεργασία

  1. ↑ (Αγγλικά) Mathematics Genealogy Project.
  2. ↑ «The list of people that worked at the Renyi Institute». Alfréd Rényi Institute of Mathematics. Ανακτήθηκε στις 5 Δεκεμβρίου 2020. 
  3. ↑ «Bio». Boston University Computer Science Department. Ανακτήθηκε στις 5 Δεκεμβρίου 2020. 
  4. ↑ Kolata, Gina Bari «Mathematicians Amazed by Russian's Discovery». Science 206 (4418): 545–546. November 2, 1979. doi:10.1126/science.206.4418.545. PMID 17759415. Bibcode: 1979Sci...206..545B. 
  5. ↑ Gács, Peter; Lovász, Laszlo (1981), König, H.; Korte, B.; Ritter, K., επιμ., Khachiyan's algorithm for linear programming, 14, Berlin, Heidelberg: Springer Berlin Heidelberg, σελ. 61–68, doi:10.1007/bfb0120921, ISBN 978-3-642-00805-4, http://link.springer.com/10.1007/BFb0120921, ανακτήθηκε στις 2020-11-27 
  6. ↑ Shenitzer, Abe, and John Stillwell, eds. Mathematical evolutions. MAA, 2002.
  7. ↑ Lautemann, Clemens (1983-11-08). «BPP and the polynomial hierarchy» (στα αγγλικά). 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. 
  8. ↑ Gács, Peter (2001-04-01). «Reliable Cellular Automata with Self-Organization» (στα αγγλικά). Journal of Statistical Physics 103 (1): 45–267. doi:10.1023/A:1004823720305. ISSN 1572-9613. Bibcode: 2001JSP...103...45G. https://doi.org/10.1023/A:1004823720305. 
  9. ↑ Gray, Lawrence F. (2001-04-01). «A Reader's Guide to Gacs's "Positive Rates" Paper» (στα αγγλικά). Journal of Statistical Physics 103 (1): 1–44. doi:10.1023/A:1004824203467. ISSN 1572-9613. Bibcode: 2001JSP...103....1G. https://doi.org/10.1023/A:1004824203467. 
  10. ↑ Durand, Bruno; Romashchenko, Andrei; Shen, Alexander (2012-05-01). «Fixed-point tile sets and their applications» (στα αγγλικά). 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. 
  11. ↑ Peter Gacs. On the symmetry of algorithmic information. Doklady Akademii Nauk SSSR, 218(6):1265–1267, 1974. In Russian.
  12. ↑ Peter Gacs. Exact expressions for some randomness tests. Z. Math. Log. Grdl. M., 26:385–394, 1980.
  13. ↑ Downey, Rodney G., and Denis R. Hirschfeldt. Algorithmic randomness and complexity. Springer, 2010
  14. ↑ 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
  15. ↑ 15,0 15,1 15,2 Li, Ming, and Paul Vitányi. An introduction to Kolmogorov complexity and its applications. Vol. 3. New York: Springer, 2008.
  16. ↑ Charles H. Bennett, Peter Gacs, Ming Li, Paul M. B. Vitanyi, and Woiciech Zurek. Information distance. IEEE Transactions on Information Theory, 44(4):1407–1423, 1998. (Preliminary version appeared in STOC’97, arXiv:1006.3520.) According to Google Scholar, this paper has been cited 687 times by April, 2021 [1]
  17. ↑ 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.
  18. ↑ 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.
  19. ↑ Peter Gacs. Uniform test of algorithmic randomness over a general space. Theoretical Computer Science, 341(1-3):91–137, 2005.
  20. ↑ 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.
  21. ↑ 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.
  22. ↑ 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.
  23. ↑ 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.
  24. ↑ Peter Gacs and Janos Korner. Common information is far less than mutual information. Problems of Control and Inf. Th., 2:149–162, 1973
  25. ↑ Ahlswede, Gacs, Körner Bounds on conditional probabilities with applications in multiuser communication, Z. Wahrsch. und Verw. Gebiete 34, 1976, 157–177
  26. ↑ «Packing of convex sets in the plane with a great number of neighbors (6 pages)» (PDF). 
  27. ↑ «On the relation between descriptional complexity and algorithmic (1983)» (PDF). 
  28. ↑ «Deterministic computations whose history is independent of the order of ´ updating» (PDF). 
  29. ↑ «The Angel Wins (28 pages)» (PDF). 
  30. ↑ «A Turing machine resisting isolated bursts of faults (with Çapuni) (46 pages)» (PDF). 


Ανακτήθηκε από "https://el.wikipedia.org/w/index.php?title=Πίτερ_Γκατς&oldid=10105590"