Αλγόριθμοι επίλυσης προβλημάτων σακιδίου

Abstract

Στην πτυχιακή εργασία "Αλγόριθμοι Επίλυσης Προβλημάτων Σακιδίου" μελετήθηκαν θέματα του κλάδου της θεωρητικής πληροφορικής. Αρχικά, αναφέρθηκαν ορισμένες έννοιες για την ομαλή εισαγωγή στο κυρίως θέμα της εργασίας. Έγινε αναφορά στην θεωρία υπολογισμού όπου αναπτύχθηκε η έννοια του υπολογιστικού μοντέλου, δόθηκαν οι ορισμοί του προβλήματος, του αλγορίθμου της χρονικής πολυπλοκότητας καθώς και κλάσεις προβλημάτων που υπάρχουν. Στη συνέχεια, μελετήθηκαν βασικές αρχές της θεωρίας βελτιστοποίησης όπου ορίστηκαν τα προβλήματα βελτιστοποίησης γραμμικού, μη γραμμικού και κυρτού προγραμματισμού. Επίσης τέθηκε και η έννοια της βέλτιστης λύσης ενός προβλήματος η οποία χαρακτηρίζεται είτε ως ολική είτε τοπική. Η μεγαλύτερη βαρύτητα δόθηκε στο τελευταίο κομμάτι της εργασίας όπου έγινε μία εισαγωγή στα προβλήματα σακιδίου, στις κατηγορίες αυτών και στην πολυπλοκότητα της καθεμιάς. Λόγω του ότι αυτά τα προβλήματα αποδεικνύονται αρκετά δύσκολα ορίζονται οι έννοιες της απλοποίησης των προβλημάτων (γραμμική και κατά Lagrange), των άνω και κάτω ορίων. Δίνεται και εξηγείται η έννοια και ο αλγόριθμος του κρίσιμου αντικειμένου καθώς και η σημασία των βελτιωμένων άνω ορίων (από επιπρόσθετους περιορισμούς, από απλοποιήσεις κατά Lagrange, από μερική απαρίθμηση). Τέλος, αναλύθηκαν τα χαρακτηριστικά του άπληστου αλγορίθμου επίλυσης προβλημάτων σακιδίου καθώς και η ευρετική μέθοδος που χρησιμοποιεί μαζί με τη διαδικασία των βημάτων για την εύρεσή της.