Παρακαλώ χρησιμοποιήστε αυτό το αναγνωριστικό για να παραπέμψετε ή να δημιουργήσετε σύνδεσμο προς αυτό το τεκμήριο:
http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/14036
Πλήρες αρχείο μεταδεδομένων
Πεδίο DC | Τιμή | Γλώσσα |
---|---|---|
dc.contributor.author | Μαυρακάκης Ιωάννης | |
dc.date.accessioned | 2018-07-23T14:26:03Z | - |
dc.date.available | 2018-07-23T14:26:03Z | - |
dc.date.issued | 2004-7-12 | |
dc.date.submitted | 2004-12-12 | |
dc.identifier.uri | http://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/14036 | - |
dc.description.abstract | Ο σκοπός της παρούσας διπλωματικής εργασίας είναι η μελέτη του NP-Hard προβλήματος του $Bin$ $Packing$. Η εργασία ξεκινάει με μία εισαγωγή στη θεωρία της πολυπλοκότητας και τον ορισμό κάποιων πολύ βασικών εννοιών. Στη συνέχεια γίνεται μία εισαγωγή στο πρόβλημα και η αναφορά των κυριότερων κατηγοριών αλγορίθμων που το επιλύουν. Γίνεται αναλυτική μελέτη ενός πλήθους προσσεγγίστικων αλγορίθμων που επιλύουν το Bin Packing. Η μελέτη αυτή περιλαμβάνει ανάλυση των χειρότερων (worst-case) αλλά και των μέσων επιδόσεων (average-case) τους. Αναφέρονται πολλά θεωρήματα με τις αποδείξεις τους. Γίνεται επίσης εφαρμογή αρκετών αλγορίθμων για συγκεκριμένη είσοδο και σύγκριση των αποδόσεων τους. Υπάρχει αναλυτική αναφορά σε ένα PTAS μεαποδείξεις όλων των θεωρημάτων που το συνοδεύουν. Τέλοςαναφέρονται δύο πολύ πρόσφατοι αλγόριθμοι και μελετώνται οιεπιδόσεις τους. | |
dc.language | Greek | |
dc.subject | bin packing | |
dc.subject | πολυπλοκότητα | |
dc.subject | προσσεγγιστικοί αλγόριθμοι | |
dc.subject | average-case ανάλυση | |
dc.subject | worst-case ανάλυση | |
dc.subject | offline αλγόριθμοι | |
dc.subject | online αλγόριθμοι | |
dc.subject | bounded-space αλγόριθμοι | |
dc.subject | pταs | |
dc.subject | αλυσίδες markov. | |
dc.title | Μέση Και Χειρότερη Επίδοση Online Και Offline Αλγόριθμων Για Το Bin Packing. | |
dc.type | Diploma Thesis | |
dc.description.pages | 111 | |
dc.contributor.supervisor | Αφράτη Φώτω | |
dc.department | Τομέας Επικοινωνιών, Ηλεκτρονικής & Συστημάτων Πληροφορικής | |
dc.organization | ΕΜΠ, Τμήμα Ηλεκτρολόγων Μηχανικών & Μηχανικών Υπολογιστών | |
Εμφανίζεται στις συλλογές: | Διπλωματικές Εργασίες - Theses |
Αρχεία σε αυτό το τεκμήριο:
Αρχείο | Μέγεθος | Μορφότυπος | |
---|---|---|---|
DT2004-0075.ps | 893.23 kB | Postscript | Εμφάνιση/Άνοιγμα |
Όλα τα τεκμήρια του δικτυακού τόπου προστατεύονται από πνευματικά δικαιώματα.