Σκοπός της πτυχιακής αυτής εργασίας είναι να παρουσιάσουμε, στην πράξη, την εφαρμογή μιας από τις πιο γνωστές και αποδοτικές τεχνικές προγραμματισμού, σε στοχαστικά προβλήματα, δηλαδή σε προβλήματα όπου μία ή περισσότερες παράμετροι είναι κάποια τυχαία μεταβλητή, η οποία μοντελοποιείται με κάποια γνωστή κατανομή πιθανοτήτων. Αυτή η τεχνική προγραμματισμού δεν είναι άλλη από τον Δυναμικό Προγραμματισμό. Αφού παρουσιάσουμε τι ακριβώς είναι ο ΔΠ και αναφέρουμε κάποια στοιχεία για την πολυπλοκότητα αλγορίθμων, αφού ο ΔΠ χρησιμοποιείται κυρίως για την επίλυση πολύπλοκων υπολογιστικά προβλημάτων, προχωράμε και μελετάμε κάποια παραδείγματα από τις κυριότερες κατηγορίες στοχαστικών προβλημάτων. Στη συνέχεια επιλέγουμε μια ειδική κατηγορία προβλημάτων, τα προβλήματα του σάκου, και αφού εξετάσουμε την ντετερμινιστική και τη στοχαστική έκδοση των προβλημάτων αυτών και αναφέρουμε τις διάφορες υποκατηγορίες που υπάρχουν προχωράμε στην παρουσίαση κάποιων αλγορίθμων από την υπάρχουσα βιβλιογραφία, οι οποίοι επιλύουν κάποιες εκδόσεις των προβλημάτων αυτών. Τέλος, γίνεται μια αναφορά σε διάφορα προβλήματα που προκύπτουν κατά την εφαρμογή του στοχαστικού δυναμικού προγραμματισμού καθώς και κάποιοι τρόποι αντιμετώπισης αυτών.
TEI of West Macedonia
