Please use this identifier to cite or link to this item:
http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/14036
Full metadata record
DC Field | Value | Language |
---|---|---|
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 | ΕΜΠ, Τμήμα Ηλεκτρολόγων Μηχανικών & Μηχανικών Υπολογιστών | |
Appears in Collections: | Διπλωματικές Εργασίες - Theses |
Files in This Item:
File | Size | Format | |
---|---|---|---|
DT2004-0075.ps | 893.23 kB | Postscript | View/Open |
Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.