Στον κόσμο των μαθηματικών εξέχουσα θέση κατέχουν οι μέθοδοι επίλυσης προβλημάτων, καθώς το πρόβλημα αποτελεί την κινητήρια δύναμη από την οποία αφορμάται ο νους που αγαπά τη μαθηματική πορεία αναζήτησης και οργάνωσης της σκέψης. Σε αυτό το πλαίσιο εντάσσονται και οι προβληματισμοί σε σχέση με τις αλγοριθμικές και ευρετικές μεθόδους επίλυσης προβλημάτων.
Η παρούσα διπλωματική εργασία αποσκοπεί να διαλευκάνει, στο μέτρο του δυνατού, τον χώρο των αλγοριθμικών και ευρετικών μεθόδων, σε μια συγκριτική θεώρηση κατά την οποία και οι δυο καταθέτουν τις δυνατότητές τους με απώτερο στόχο την εξασφάλιση μιας ασφαλούς λογικής διεργασίας για την αντιμετώπιση των προβλημάτων.
Ειδικότερα, θεωρήθηκε προσφορότερο κατά τη σύνθεση της παρούσας εργασίας να διακριθεί η ενότητα που αφορά στο πρόβλημα από την ενότητα επίλυσης του προβλήματος.
Για το σκοπό αυτό στην πρώτη ενότητα εντάχθηκαν υποενότητες που ξεκινούν από τον ορισμό του προβλήματος γενικότερα και προσφέρουν επεξηγήσεις για την έννοια του μαθηματικού προβλήματος, δίνοντας τα στάδια αντιμετώπισης των προβλημάτων, τις τεχνικές κατανόησης και οριοθετώντας τον χώρο των προβλημάτων. Επιπρόσθετα, γίνεται προσπάθεια ανάλυσης της δομής των προβλημάτων και παρουσίασης των κατηγοριών τους, καταλήγοντας στα είδη των γενικών προβλημάτων.
Στη δεύτερη ενότητα διερευνάται η έννοια της επίλυσης προβλημάτων, των γενικών χαρακτηριστικών τους, των θεωριών επίλυσής τους και προβάλλεται η τεχνική αναζήτησης για την επίλυση προβλημάτων.
Το θέμα της τρίτης ενότητας αφορά, κατά κύριο λόγο, στους αλγορίθμους με προσπάθεια ενδελεχούς έρευνας των χαρακτηριστικών τους, με παράλληλη περιγραφή και αναπαράστασή τους και με παρουσίαση των δεδομένων, της πολυπλοκότητάς τους και, σαφώς, των δυνατοτήτων που προσφέρουν στην επίλυση των προβλημάτων.
Στην τέταρτη ενότητα της παρούσας εργασίας γίνεται προσπάθεια διαπραγμάτευσης των ευρετικών και μεθευρετικών μηχανισμών- μεθόδων, συμπεριλαμβανομένων και των ευρετικών αλγορίθμων.
Στην πέμπτη ενότητα καταγράφονται θεωρίες στρατηγικής λύσης γενικών προβλημάτων όπως αυτές του G. Polya, των Bransford και Stein, του Schoenfeld και του Sternberg.
Στην έκτη ενότητα περιέχονται παραδείγματα αλγορίθμων –Ευκλείδειος Αλγόριθμος, η μέθοδος της ανθυφαίρεσης, ο Δακτύλιος Πολυωνύμων, ο Αλγόριθμος για τα συνεχή κλάσματα και οι Αλγόριθμοι Επίλυσης Εξισώσεων.
Ιδιαίτερο ενδιαφέρον, από άποψη πρακτικής, κυρίως, εφαρμογής, παρουσιάζει η έβδομη ενότητα, καθώς καταγράφονται αλγοριθμικές τεχνικές και παρατίθενται παραδείγματα που βασίζονται σε αυτές.
Στην όγδοη γίνεται εκτενής λόγος για τις ευρετικές μεθόδους και, μέσω συγκριτικής θεώρησης, διαπιστώνονται τυχόν μειονεκτήματα και πλεονεκτήματα κατά την εφαρμογή τους, καταλήγοντας σε συμπεράσματα για την αποτελεσματικότητά τους.
Στην ένατη ενότητα παρουσιάζονται τρεις βασικές μοντέρνες ευρετικές μέθοδοι, όπως τα Νευρωνικά Δίκτυα, οι Γενετικοί Αλγόριθμοι και οι Εξελικτικοί Αλγόριθμοι.
Η παρούσα εργασία ολοκληρώνεται με τη μελέτη δύο περιπτώσεων εφαρμογής των αλγοριθμικών και ευρετικών μεθόδων- του προβλήματος των οκτώ (8) βασιλισσών και του προβλήματος του περιοδεύοντα πωλητή.
In the world of mathematics, problem solving methods hold a prominent place, as the problem is the driving force for the mind that loves the mathematic path of searching and organizing thought. In this framework we can include concerns regarding algorithmic and heuristic methods for solving problems.
Τhis dissertation aims to shed light, as much as possible, on algorithmic and heuristic methods, in a comparative assumption in which both methods’ potential is examined, aiming to acquire a safe logical process in order to handle mathematical problems.
More specifically, it was considered as more appropriate while composing this particular dissertation, to distinguish the chapter that examines the concept of the mathematical problem from the chapter that delves into mathematical problem solving.
With this aim in mind, the first chapter encompasses subsections that start with the definition of the problem in general, as well as elaboration on the concept of the mathematical problem, while presenting the stages of solving the problem, the comprehension techniques, and defining the space of the mathematical problem. In addition, this chapter attempts to analyse the structure of the problems and present their categories, concluding with the types of general problems.
In the second chapter, the concept of problem solving is investigated, along with their unanimous characteristics, the theories of solving and the research techniques used for problem solving.
For the most part the subject of the third chapter concerns algorithms, and the attempt of a thorough research of their characteristics, as well as a description and depiction of them, ending with a presentation of the data, of the algorithms’ complexity and, surely, the potential they offer in problem solving.
In the fourth chapter of this dissertation, a negotiation of the heuristic and post-heuristic mechanisms/methods, including heuristic algorithms, is attempted.
In the fifth chapter, theories of strategic solving for general mathematical problems such as those by G. Polya, Bransford and Stein, Schoenfeld and Sternberg, are recorded.
The sixth chapter includes examples of algorithms such as the Euclidean algorithm, the antiphairesis method, the polynomial annulus, the algorithm for continued fractions and the equation solving algorithms.
The seventh chapter is of particular interest, from a practical point of view, as algorithmic techniques are recorded and examples based on them are cited.
In the eighth chapter, there is extensive analysis of the heuristic methods, and through a comparative assumption possible disadvantages and advantages of using them are established, resulting in conclusions regarding their effectiveness.
In the ninth chapter, three modern heuristic methods are presented, Neural Networks, Genetic Algorithms and Evolutionary Algorithms.
The dissertation is completed with a study of two cases of applying algorithmic and heuristic methods: the problem of the eight (8) queens and the problem of the travelling salesman.
Items in Apothesis are protected by copyright, with all rights reserved, unless otherwise indicated.
Κύρια Αρχεία Διατριβής
Συγκριτική Μελέτη των Αλγοριθμικών και Ευρετικών Μεθόδων Επίλυσης Προβλήματος - Identifier: 75373
Internal display of the 75373 entity interconnections (Node labels correspond to identifiers)
