Τα γραμμικά διοφαντικά συστήματα μοντελοποιούν πολλά ενδιαφέροντα προβλήματα που προέρχονται τόσο από τα μαθηματικά (συνδυαστική, θεωρία αριθμών, κλπ.) όσο και από την πληροφορική (θεωρία γραφημάτων, δίκτυα, κλπ.). Η επίλυσή τους θεωρείται υπολογιστικά δύσκολη (NP-hard). Στις αρχές του προηγούμενου αιώνα ο MacMahon ανέπτυξε μια (αναλυτική) μέθοδο για την επίλυση γραμμικών διοφαντικών συστημάτων ώστε να υπολογίσει τις γεννήτριες συναρτήσεις ακέραιων διασπάσεων (integer partitions), την οποία ονόμασε Partition Analysis. Στα τέλη του προηγούμενου αιώνα οι Andrews και Paule, με τη χρήση συμβολικού υπολογισμού, ανέπτυξαν μια πλήρως αλγοριθμική έκδοση της μεθόδου την οποία υλοποίησαν και ονόμασαν Omega (από τον τελεστή ωμέγα που εισήγαγε ο MacMahon). Αν όμως δούμε γεωμετρικά το πρόβλημα, τότε οι γραμμικές ανισότητες ορίζουν ένα πολύεδρο και οι ακέραιες λύσεις αντιστοιχούν στα ακέραια σημεία
εντός του πολυέδρου αυτού. Σημαντική πρόοδο για τις γεωμετρικές μεθόδους προσέφερε η δουλειά του Lenstra και αργότερα του Barvinok. Συνδυάζοντας τις δύο παραδόσεις (αναλυτική και γεωμετρική) αναπτύσσουμε έναν αλγόριθμο (Polyhedral Omega) που εκμεταλλεύεται τα πλεονεκτήματα και των δύο κόσμων. Στην ομιλία
θα παρουσιάσουμε την γεωμετρική ερμηνεία των αναλυτικών μεθόδων και τον αλγόριθμο Polyhedral Omega. Πανεπιστήμιο Θεσσαλίας Σχολή Θετικών Επιστημών
Τμήμα Μαθηματικών Διάλεξη με θέμα:Polyhedral Omega: Γεωμετρώντας Παρασκευή 21 Μαΐου 2021 στις 13:00 Εικονική αίθουσα του MsTeams: 802yfg5 Ομιλητής: Δρ. Ζαφειράκης Ζαφειρακόπουλος Επίκουρος Καθηγητής, Gebze Technical University
