Βάτσλαβ Χβάταλ

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Βάτσλαβ Χβάταλ
Γενικές πληροφορίες
Γέννηση20 Ιουλίου 1946
Πράγα[1][2]
Χώρα πολιτογράφησηςΚαναδάς
Τσεχοσλοβακία[2]
Εκπαίδευση και γλώσσες
Ομιλούμενες γλώσσεςΑγγλικά[3][4]
Τσεχικά[4]
ΣπουδέςΠανεπιστήμιο του Γουοτερλού
Πανεπιστήμιο του Καρόλου[5]
Πληροφορίες ασχολίας
Ιδιότηταμαθηματικός[6]
διδάσκων πανεπιστημίου
επιστήμονας υπολογιστών
ΕργοδότηςΠανεπιστήμιο Κονκόρντια
Πανεπιστήμιο του Μόντρεαλ[7]
Αξιώματα και βραβεύσεις
Βραβεύσειςβραβείο Φρέντερικ Γουίλιαμ Λάντσεστερ (2007)
Commons page Σχετικά πολυμέσα
δεδομένα

Ο Βάτσλαβ Χβάταλ (τσεχικά: Václav Chvátal) είναι ομότιμος καθηγητής στο Τμήμα Επιστήμης Υπολογιστών και Τεχνολογίας Λογισμικού του Πανεπιστημίου Κονκόρντια στο Μόντρεαλ του Κεμπέκ στον Καναδά και επισκέπτης καθηγητής στο Πανεπιστήμιο του Καρόλου στην Πράγα. Έχει δημοσιεύσει εκτενώς σε θέματα που αφορούν τη Θεωρία γραφημάτων, Συνδυαστική και συνδυαστική βελτιστοποίησης.

Βιογραφία[Επεξεργασία | επεξεργασία κώδικα]

Ο Χβάταλ γεννήθηκε το 1946 στην Πράγα και σπούδασε μαθηματικά στο Πανεπιστήμιο του Καρόλου στην Πράγα, όπου σπούδασε υπό την επίβλεψη του Ζντένεκ Χέντρλιν[8]. Έφυγε από την Τσεχοσλοβακία το 1968, τρεις ημέρες μετά τη σοβιετική εισβολή[9], και ολοκλήρωσε το διδακτορικό του στα Μαθηματικά στο Πανεπιστήμιο του Γουότερλου, υπό την επίβλεψη του Κρίσπιν Σεντ Τζέι Νας-Γουίλιαμς, το φθινόπωρο του 1970.[8][10] Στη συνέχεια, ανέλαβε θέσεις στο Πανεπιστήμιο McGill (1971 και 1978-1986), στο Πανεπιστήμιο του Στάνφορντ (1972 και 1974-1977), στο Πανεπιστήμιο του Μοντρεάλ (1972-1974 και 1977-1978) και στο Πανεπιστήμιο του Ράτγκερς (1986-2004), προτού επιστρέψει στο Μόντρεαλ για την έδρα Καναδικής Έρευνας στη Συνδυαστική Βελτιστοποίηση [11][9] στο Κονκόρντια (2004-2011) και την έδρα Καναδικής Έρευνας στα Διακριτά Μαθηματικά (2011-2014) μέχρι τη συνταξιοδότησή του.

Έρευνα[Επεξεργασία | επεξεργασία κώδικα]

Το γράφημα Χβάταλ

Ο Χβάταλ έμαθε για πρώτη φορά για τη θεωρία γραφημάτων το 1964, όταν βρήκε ένα βιβλίο του Κλοντ Μπερζέ σε ένα βιβλιοπωλείο του Πίλσεν[12] και μεγάλο μέρος της έρευνάς του αφορά τη θεωρία γραφημάτων:

  • Η πρώτη του μαθηματική δημοσίευση, σε ηλικία 19 ετών, αφορούσε κατευθυνόμενα γραφήματα που δεν μπορούν να αντιστοιχηθούν στον εαυτό τους με οποιοδήποτε μη τετριμμένο ομομορφισμό γραφήματος[13].
  • Ένα άλλο γραφοθεωρητικό αποτέλεσμα του Χβάταλ ήταν το 1970 η κατασκευή του μικρότερου δυνατού γραφήματος χωρίς τρίγωνα που είναι και 4-χρωματικό και 4-κανονικό, γνωστό πλέον ως γράφημα Χβάταλ[8][14]
  • A 1972 paper [15].
  • Μια εργασία του 1972[16] που συσχετίζει τους Χαμιλτονιανούς κύκλους με τη συνδεσιμότητα και το μέγεθος του μέγιστου ανεξάρτητου συνόλου ενός γράφου, χάρισε στον Χβάταλ τον αριθμό Έρντος 1. Συγκεκριμένα, αν υπάρχει ένα s τέτοιο ώστε ένας δεδομένος γράφος να είναι συνδεδεμένος με s κορυφές και να μην έχει ανεξάρτητο σύνολο (s + 1)-κορυφών, ο γράφος πρέπει να είναι Χαμιλτονιανός. Οι Avis et al.[8] διηγούνται την ιστορία των Χβάταλ και Έρντος που επεξεργάστηκαν αυτό το αποτέλεσμα κατά τη διάρκεια ενός μεγάλου οδικού ταξιδιού και αργότερα ευχαρίστησαν τη Λουίζ Γκάι "για τη σταθερή οδήγηση".
  • Σε μια εργασία του 1973,[17] ο Χβάταλ εισήγαγε την έννοια της σκληρότητας του γραφήματος, ένα μέτρο της συνδεσιμότητας του γραφήματος που συνδέεται στενά με την ύπαρξη Χαμιλτονιανών κύκλων. Ένας γράφος είναι t-tough αν, για κάθε k μεγαλύτερο από 1, η αφαίρεση λιγότερων από tk κορυφών αφήνει λιγότερες από k συνδεδεμένες συνιστώσες στον υπογράφο που απομένει. Για παράδειγμα, σε ένα γράφημα με Χαμιλτονιανό κύκλο, η αφαίρεση οποιουδήποτε μη κενού συνόλου κορυφών χωρίζει τον κύκλο σε το πολύ τόσα κομμάτια όσα και ο αριθμός των κορυφών που αφαιρούνται, οπότε τα Χαμιλτονιανά γραφήματα είναι 1-tough. Ο Χβάταλ υπέθεσε ότι τα 3/2-σκληρά γραφήματα, και αργότερα ότι τα 2σκληρά γραφήματα, είναι πάντα Χαμιλτονιανά- παρά το γεγονός ότι μεταγενέστεροι ερευνητές βρήκαν αντιπαραδείγματα σε αυτές τις εικασίες, παραμένει ακόμη ανοιχτό αν κάποιο σταθερό όριο στη σκληρότητα του γραφήματος είναι αρκετό για να εγγυηθεί τη Χαμιλτονιανικότητα[18].

Ορισμένες από τις εργασίες του Χβάταλ αφορούν οικογένειες συνόλων, ή ισοδύναμα υπεργραφήματα, ένα θέμα που είχε ήδη εμφανιστεί στη διδακτορική του διατριβή, όπου μελέτησε επίσης τη θεωρία Ramsey.

  • Σε μια εικασία του 1972, την οποία ο Erdős αποκάλεσε «εκπληκτική» και «όμορφη»[19] και η οποία παραμένει ανοιχτή (με ένα βραβείο 10 δολαρίων που προσέφερε ο Χβάταλ για τη λύση της)[20][21] πρότεινε ότι, σε οποιαδήποτε οικογένεια συνόλων κλειστή υπό την πράξη της λήψης υποσυνόλων, η μεγαλύτερη υποοικογένεια που τέμνεται κατά ζεύγη μπορεί πάντα να βρεθεί επιλέγοντας ένα στοιχείο ενός από τα σύνολα και κρατώντας όλα τα σύνολα που περιέχουν αυτό το στοιχείο.
  • Το 1979,[22] μελέτησε μια σταθμισμένη εκδοχή του προβλήματος κάλυψης συνόλων και απέδειξε ότι ένας άπληστος αλγόριθμος παρέχει καλές προσεγγίσεις της βέλτιστης λύσης, γενικεύοντας προηγούμενα μη σταθμισμένα αποτελέσματα των Ντέιβιντ Σ. Τζόνσον (J. Comp. Sys. Sci. 1974) και Λάσλο Λοβάς (Discrete Math. 1975).

Ο Χβάταλ ενδιαφέρθηκε για πρώτη φορά για τον γραμμικό προγραμματισμό μέσω της επιρροής του Τζακ Έντμοντς, ενώ ο Χβάταλ ήταν φοιτητής στο Γουότερλου[8]. Γρήγορα αναγνώρισε τη σημασία των επιπέδων κοπής για την επίθεση σε προβλήματα συνδυαστικής βελτιστοποίησης, όπως ο υπολογισμός μέγιστων ανεξάρτητων συνόλων και, συγκεκριμένα, εισήγαγε την έννοια της απόδειξης του επιπέδου κοπής[23][24][25][26] Στο Στάνφορντ τη δεκαετία του 1970, άρχισε να γράφει το δημοφιλές εγχειρίδιο του, Γραμμικός Προγραμματισμός, το οποίο εκδόθηκε το 1983[11].

Τα επίπεδα κοπής βρίσκονται στο επίκεντρο της μεθόδου διακλάδωσης και αποκοπής που χρησιμοποιείται από αποτελεσματικούς λύτες για το πρόβλημα του πλανόδιου πωλητή. Μεταξύ 1988 και 2005, η ομάδα των Ντέιβιντ Λ. Απλεγκέιτ, Ρόμπερτ Ε. Μπίξμπι, Βάσεκ Τσβάταλ και Γουίλιαμ Τζ. Κουκ ανέπτυξε έναν τέτοιο επιλύτη, το Κονκόρντ.[27][28] Η ομάδα τιμήθηκε με το βραβείο Beale-Orchard-Hays για την αριστεία στον υπολογιστικό μαθηματικό προγραμματισμό το 2000 για τη δεκασέλιδη εργασία τους[29] που απαριθμούσε ορισμένες από τις βελτιώσεις του Κονκόρντ στη μέθοδο διακλάδωσης και αποκοπής που οδήγησαν στην επίλυση μιας περίπτωσης 13.509 πόλεων και τιμήθηκε με το βραβείο Φρέντερικ Λάντσεστερ το 2007 για το βιβλίο τους, The Traveling Salesman Problem: A Computational Study (Το πρόβλημα του πλανόδιου πωλητή: μια υπολογιστική μελέτη).

Ο Χβάταλ είναι επίσης γνωστός για την τεκμηρίωση του θεωρήματος της γκαλερί τέχνης,[30][31][32][33] για την έρευνα μιας αυτοπεριγραφόμενης ψηφιακής ακολουθίας,[34][35] για την εργασία του με τον Ντέιβιντ Σάνκοφ σχετικά με τις σταθερές Χβάταλ -Sankoff που ελέγχουν τη συμπεριφορά του προβλήματος της μεγαλύτερης κοινής υποακολουθίας σε τυχαίες εισόδους,[36] και για την εργασία του με τον Έντρε Σεμερέντι σχετικά με δύσκολες περιπτώσεις για την απόδειξη θεωρημάτων επίλυσης[37].

Βιβλία[Επεξεργασία | επεξεργασία κώδικα]

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

  1. ↑ Τσεχική Εθνική Βάση Δεδομένων Καθιερωμένων Όρων. jcu2017956904. Ανακτήθηκε στις 23  Νοεμβρίου 2019.
  2. ↑ 2,0 2,1 «Evidence zájmových osob StB». Records of persons of interest.
  3. ↑ «Identifiants et Référentiels». (Γαλλικά) IdRef. Agence bibliographique de l'enseignement supérieur. Ανακτήθηκε στις 12  Μαΐου 2020.
  4. ↑ 4,0 4,1 Τσεχική Εθνική Βάση Δεδομένων Καθιερωμένων Όρων. jcu2017956904. Ανακτήθηκε στις 1  Μαρτίου 2022.
  5. ↑ Ανακτήθηκε στις 8  Ιουλίου 2019.
  6. ↑ Εθνική Βιβλιοθήκη της Γερμανίας: (Γερμανικά) Gemeinsame Normdatei. Ανακτήθηκε στις 26  Ιουνίου 2015.
  7. ↑ Ανακτήθηκε στις 3  Ιουλίου 2019.
  8. ↑ 8,0 8,1 8,2 8,3 8,4 Avis, D.; ; Cook, W.«Vasek Chvatal: A Short Introduction». Graphs and Combinatorics 23: 41–66. 2007. doi:10.1007/s00373-007-0721-4. http://www.math.uwaterloo.ca/~bico//papers/vasek_gc.pdf. 
  9. ↑ 9,0 9,1 Vasek Chvátal is ‘the travelling professor’, Concordia's Thursday Report, Feb. 10, 2005.
  10. ↑ The Mathematics Genealogy Project – Václav Chvátal
  11. ↑ 11,0 11,1 Vasek Chvatal awarded Canada Research Chair, Concordia's Thursday Report, Oct. 23, 2003.
  12. ↑ Chvátal, Vašek «In praise of Claude Berge», Discrete Mathematics 165-166: 3–9, 1997, doi:10.1016/s0012-365x(96)00156-2 ,
  13. ↑ Chvátal, Václav «On finite and countable rigid graphs and tournaments», Commentationes Mathematicae Universitatis Carolinae 6: 429–438, 1965, http://dml.cz/dmlcz/105034 .
  14. ↑ Weisstein, Eric W., "Chvátal Graph" από το MathWorld.
  15. ↑ V. Chvátal «A note on Hamiltonian circuits», Discrete Mathematics 2 (2): 111–113, 1972, doi:10.1016/0012-365x(72)90079-9, http://www.math-inst.hu/~p_erdos/1972-02.pdf ,
  16. ↑ V. Chvátal «A note on Hamiltonian circuits», Discrete Mathematics 2 (2): 111–113, 1972, doi:10.1016/0012-365x(72)90079-9, http://www.math-inst.hu/~p_erdos/1972-02.pdf ,
  17. ↑ V. Chvátal «Tough graphs and hamiltonian circuits», Discrete Mathematics 5 (3): 215–228, 1973, doi:10.1016/0012-365x(73)90138-6 ,
  18. ↑ Lesniak, Linda, Chvátal's t0-tough conjecture, http://faculty.nps.edu/rgera/Conjectures/jmm2012/Linda-Lesniak.pdf 
  19. ↑ Mathematical Reviews MR0369170
  20. ↑ V. Chvátal; David A. Klarner; «Selected combinatorial research problems», Computer Science Department, Stanford University Stan-CS-TR-72-292, 1972, http://users.encs.concordia.ca/~chvatal/Stan-CS-TR-72-292.pdf : Problem 25
  21. ↑ Chvátal, Vašek, A conjecture in extremal combinatorics, http://users.encs.concordia.ca/~chvatal/conjecture.html 
  22. ↑ "A greedy heuristic for the set-covering problem", Mathematics of Operations Research, 1979
  23. ↑ Chvátal, Václav «Edmonds polytopes and weakly hamiltonian graphs», Mathematical Programming 5: 29–40, 1973, doi:10.1007/BF01580109 ,
  24. ↑ Chvátal, Václav «Edmonds polytopes and a hierarchy of combinatorial problems», Discrete Mathematics 4 (4): 305–337, 1973, doi:10.1016/0012-365x(73)90167-2 ,
  25. ↑ Chvátal, Václav «Some linear programming aspects of combinatorics», Congressus Numerantium 13: 2–30, 1975, http://i.stanford.edu/pub/cstr/reports/cs/tr/75/505/CS-TR-75-505.pdf ,
  26. ↑ Chvátal, V. «On certain polytopes associated with graphs», Journal of Combinatorial Theory, Series B 18 (2): 138–154, 1975, doi:10.1016/0095-8956(75)90041-6 .
  27. ↑ Math Problem, Long Baffling, Slowly Yields. New York Times, Mar. 12, 1991.
  28. ↑ Artful Routes, Science News Online, Jan. 1, 2005.
  29. ↑ Chvátal, Vašek; Cook, William Applegate, David; Bixby, Robert (1998), «On the Solution of Traveling Salesman Problems», Documenta Mathematica Extra Volume ICM III, https://www.math.uni-bielefeld.de/documenta/xvol-icm/17/Cook.MAN.html 
  30. ↑ Weisstein, Eric W. "Art Gallery Theorem." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/ArtGalleryTheorem.html
  31. ↑ Diagonals: Part I 4. Art gallery problems, AMS Feature Column by Joseph Malkevitch
  32. ↑ Chvatal's Art Gallery Theorem in Alexander Bogomolny's Cut the Knot
  33. ↑ Obsession Αρχειοθετήθηκε 2017-03-20 στο Wayback Machine., Numb3rs, Episode 3, Season 2
  34. ↑ Chvátal, Vašek «Notes on the Kolakoski Sequence», DIMACS Technical Reports TR: 93-84, 1993, http://dimacs.rutgers.edu/TechnicalReports/abstracts/1993/93-84.html 
  35. ↑ Dangerous Problems, Science News Online, Jul. 13, 2002.
  36. ↑ Chvátal, Václav; Sankoff, David «Longest common subsequences of two random sequences», Journal of Applied Probability 12 (2): 306–315, 1975, doi:10.2307/3212444 .
  37. ↑ Chvátal, Vašek; Szemerédi, Endre «Many hard examples for resolution», Journal of the ACM 35 (4): 759–768, 1988, doi:10.1145/48014.48016 .
  38. ↑ Borchers, Brian (25 Μαρτίου 2007). «Review of The Traveling Salesman Problem: A Computational Study». MAA Reviews, Mathematical Association of America. 

Εξωτερικοί σύνδεσμοι[Επεξεργασία | επεξεργασία κώδικα]


Καθιερωμένοι όροι
Ανακτήθηκε από "https://el.wikipedia.org/w/index.php?title=Βάτσλαβ_Χβάταλ&oldid=10105568"