Μονάδα:
Τομέας Θεωρητικής ΠληροφορικήςΒιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2016-07-08
Συγγραφέας:
Δαβιλάς Κωνσταντίνος
Στοιχεία επιβλεπόντων καθηγητών:
Βασίλειος Ζησιμόπουλος
Πρωτότυπος Τίτλος:
Αναλυση bin packing problem
Γλώσσες εργασίας:
Ελληνικά
Περίληψη:
Στο πλαίσιο αυτής της εργασίας θα μελετήσουμε το NP-complete Bin Packing
Problem.
Δεδομένου ενός συνόλου αριθμών/βαρών και ενός συνόλου από κάδους (bins)
δεδομένης χωρητικότητας, να βρεθεί ο ελάχιστος αριθμός bins που απαιτούνται,
ώστε
να περιέχονται όλα τα βάρη/αριθμοί σε bins και κανένα bin να μην ξεπερνά την
χωρητικότητά του. Θα δούμε τις κυριότερες πρακτικές εφαρμογές του Bin Packing
Problem. Θα αναφέρουμε και θα μελετήσουμε τους σημαντικότερους αλγόριθμους που
χρησιμοποιούνται για την λύση του προβλήματος και τις σημαντικότερες εφαρμογές
του. Επιπλέον θα μελετήσουμε το πρόβλημα του Bin Packing Problem σε αντιστοιχία
με
το MapReduce καθώς μπορεί να μας δώσει λύσεις στην μελέτη του προβλήματος σε
κλίκες και θα δούμε ακόμα το πρόβλημα σε μονοπάτι όπου κάθε στοιχείο Χι οφείλει
να
βρίσκεται στον ίδιο κάδο με το Χι+1 προτείνοντας κάποιους αλγόριθμους που
λύνουν το
πρόβλημα μελετώντας τα θετικά και τα αρνητικά τους.
Λέξεις-κλειδιά:
ΝP-δυσκολία, Bin Packing, Ακριβείς Αλγόριθμοι, Προσεγγιστικοί Αλγόριθμοι, MapReduce
Αρ. σελίδων ευρετηρίου:
6-7
Αρ. βιβλιογραφικών αναφορών:
24
