Προτεινόμενα θέματα εκπόνησης εργασίας 2012-2013

Διομήδης Σπινέλλης
Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Έλεγχος και βελτιστοποίηση της υλοποίησης OpenMIC

Ο μετρική MIC (maximal information coefficient) επιτρέπει την εύρεση μη προκαθορισμένων συσχετίσεων σε σύνολα δεδομένων πολλαπλών διαστάσεων. Η εργασία αυτή στοχεύει στον έλεγχο και τη βελτιστοποίηση μιας υλοποίησης της μετρικής αυτής που είναι διαθέσιμη ως λογισμικό ανοικτού κώδικα. Περισσότερες πληροφορίες σχετικά με τη μετρική αυτή υπάρχουν στην ιστοσελίδα που δημιουργήθηκε από την ομάδα που την ανακάλυψε (http://www.exploredata.net/) καθώς και το αντίστοιχο άρθρο (http://dx.doi.org/10.1126/science.1205438) που δημοσιεύτηκε στο περιοδικό Science.

Ως βάση της εργασίας παρέχεται κώδικας (https://github.com/dspinellis/OpenMIC) που υλοποιεί τους αλγόριθμους που αναφέρονται στο άρθρο, μεταγλωττίζεται, και περνά όλους τους ελέγχους μονάδας, καθώς και η αρχική εφαρμογή (http://www.exploredata.net/Downloads) ως πλαίσιο αναφοράς.

Πράγματα που πρέπει να κάνετε είναι τα παρακάτω.

Να διορθώστε την εφαρμογή ώστε να παράγει αποτελέσματα κοντά σε αυτά της αρχικής εφαρμογής.
Να βελτιστοποιήστε τον αλγόριθμο με επιθετική χρήση βοηθητικής μνήμης (caching).
Να εξετάσετε άλλες μεθόδους για να επιτύχετε καλύτερα αποτελέσματα σε μικρότερο χρόνο.

Βιβλιογραφία

D. Reshef, Y. Reshef, H. Finucane, S. Grossman, G. McVean, P. Turnbaugh, E. Lander, M. Mitzenmacher, P. Sabeti. Detecting novel associations in large datasets. Science 334, 6062 (2011).

Εργαλεία του Unix στο περιβάλλον Eclipse

Τα εργαλεία που παρέχει μέσω της γραμμής εντολών το λειτουργικό σύστημα Unix (και Linux) είναι εξαιρετικά ισχυρά, αλλά για πολλούς δύσχρηστα. Έτσι αρκετοί προγραμματιστές χρησιμοποιούν ολοκληρωμένα περιβάλλοντα ανάπτυξης, όπως το Eclipse και το Visual Studio, τα οποία παρέχουν εύκολες στη χρήση, αλλά σε πολλούς τομείς περιορισμένες δυνατότητες. Στόχος της εργασίας είναι η ανάπτυξη στο περιβάλλον Eclipse μιας εύχρηστης διεπαφής για την εκτέλεση εργασιών με τα εργαλεία του Unix. Παραδείγματα τέτοιων εργαλείων είναι τα find, grep, sort, uniq, wc, sed, awk, stat, jot, tar, nm, diff, comm, head, tail, fmt, και xargs. Μέσω της διεπαφής αυτής θα μπορούν οι χρήστες να επιλέγουν εργαλεία, να καθορίζουν τις παραμέτρους τους, να τα συνδέουν μεταξύ τους, να τους παρέχουν δεδομένα από το περιβάλλον Eclipse, και να βλέπουν τα παραγόμενα αποτελέσματα.

Βιβλιογραφία

Diomidis Spinellis. Working with Unix tools (http://www.dmst.aueb.gr/dds/pubs/jrnl/2005-IEEESW-TotT/html/v22n6.html). IEEE Software, 22(6):9–11, November/December 2005. (doi:10.1109/MS.2005.170 (http://dx.doi.org/10.1109/MS.2005.170))
Diomidis Spinellis. Outwit: Unix tool-based programming meets the Windows world (http://www.dmst.aueb.gr/dds/pubs/conf/2000-Usenix-outwit/html/utool.html). In Christopher Small, editor, USENIX 2000 Technical Conference Proceedings, pages 149–158, Berkeley, CA, June 2000. USENIX Association.
Erich Gamma and Kent Beck. Contributing to Eclipse: Principles, Patterns, and Plug-Ins. Addison-Wesley, Boston, MA, 2004.
Brian W. Kernighan and Rob Pike. The UNIX Programming Environment. Prentice Hall, Englewood Cliffs, NJ, 1984.
Brian W. Kernighan. Sometimes the Old Ways are Best. IEEE Software, 25(6), November/December 2008.
Diomidis Spinellis. Unix tools as visual programming components in a GUI-builder environment. Software: Practice & Experience, 32(1):57–71, January 2002. (doi:10.1002/spe.428 (http://dx.doi.org/10.1002/spe.428))

Διαδικτυακή διεπαφή αποσφαλματωτή

Η διεπαφή κειμένου που προσφέρει ο αποσφαλματωτής gdb δεν είναι ιδιαίτερα εύχρηστη. Πολλές λειτουργίες, όπως η τοποθέτηση σημείων διακοπής και η παρακολούθηση ροής του προγράμματος, πραγματοποιούνται με τρόπο που δεν είναι διαισθητικός. Από την άλλη πλευρά οι περισσότερες γραφικές διεπαφές διορθωτών δεν είναι μεταφέρσιμες ανάμεσα σε διαφορετικές πλατφόρμες. Η εργασία περιλαμβάνει το σχεδιασμό και την υλοποίηση μιας διαδικτυακής διεπαφής στον αποσφαλματωτή gdb, αντίστοιχης με αυτή που παρέχεται από την εφαρμογή RStudio (http://rstudio.org/) για το έργο R (http://www.r-project.org/). Η υλοποίηση θα μπορούσε να βασιστεί στη χρήση της υπάρχουσας διεπαφής GDB/MI (machine interface), στη βιβλιοθήκη SWILL και στη τεχνολογία AJAX (asynchronous Javascript and XML). Η βιβλιοθήκη SWILL επιτρέπει την λειτουργία εφαρμογών ως διαδικτυακών εξυπηρετητών. Έτσι, ο προτεινόμενος συνδυασμός παρέχει μια μεταφέρσιμη γραφική διεπαφή μέσω ενός οποιουδήποτε φυλλομετρητή, η οποία μάλιστα έχει ως πρόσθετο πλεονέκτημα να είναι προσβάσιμη από το διαδίκτυο.

Βιβλιογραφία

Sotiria Lampoudi and David M. Beazley. SWILL: A simple embedded web server library. In USENIX Technical Conference Proceedings, Monterey, CA, USA, June 2002. Usenix Association. FREENIX Track Technical Program.
Even Adams and Steven S. Muchnick. Dbxtool: A window-based symbolic debugger for sun workstations. Software: Practice & Experience, 16(7):653-669, July 1986.
Dave Crane, Eric Pascarello, and Darren James. Ajax in Action. Manning, Greenwich, CT, 2006.

Το πρόβλημα της διαδοχικής τρωτότητας στις υπηρεσίες του παγκοσμίου ιστού

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

Η ανάκτηση ξεχασμένων συνθηματικών μέσω διαδικτυακής υπηρεσίας ηλεκτρονικού ταχυδρομείου (π.χ. GMail).
Οι εξουσιοδοτήσεις σε εφαρμογές τρίτων που παρέχονται μεταξύ υπηρεσιών όπως Facebook, LinkedIn, Twitter.
Η δυνατότητα επαναχρησιμοποίησης δεδομένων από τις προσφερόμενες υπηρεσίες για την πραγματοποίηση επιθέσεων κοινωνικής μηχανικής (social engineering attacks).

Βιβλιογραφία

Stefanos Gritzalis and Diomidis Spinellis. The cascade vulnerability problem for open distributed systems: A review. In IFIP TC5 WG5.4 3rd International Conference on Reliability, Quality & Safety of Software-Intensive Systems, ENCRESS '97, pages 175–185. IFIP, Chapman & Hall, May 1997.

Αξιολόγηση του έργου της μετάβασης λογισμικού στο πρότυπο IPv6

Αργά ή γρήγορα όλο το λογισμικό που έχει διαδικτυακές διεπαφές θα χρειαστεί να προσαρμοστεί στην επόμενη γενιά του διαδικτυακού πρωτοκόλλου IP, την έκδοση 6 (IPv6). Η μετάβαση αυτή βρίσκεται σε εξέλιξη και είναι απαραίτητο να ολοκληρωθεί, διότι ο αριθμός των διαθέσιμων διευθύνσεων της τρέχουσας έκδοσης IPv4 κοντεύει να εξαντληθεί. Αυτό έχει ως αποτέλεσμα να τίθενται εμπόδια στη διάδοση του διαδικτύου, ειδικά στις αναπτυσσόμενες χώρες. Στόχος της εργασίας είναι η αξιολόγηση του απαιτούμενου έργου, μέσω της άντλησης εμπειρικών δεδομένων από υπάρχοντα έργα ανοικτού λογισμικού.

Στα πλαίσια της εργασία θα εξεταστούν τα παρακάτω δύο στοιχεία:

Το ποσοστό των εφαρμογών που είναι συμβατές με το πρότυπο IPv6.
Το έργο που απαιτήθηκε για την προσαρμογή της κάθε εφαρμογής στο πρότυπο IPv6.

Βιβλιογραφία

Carlos E. Caicedo, James B.D. Joshi, Summit R. Tuladhar, IPv6 Security Challenges, Computer, vol. 42, no. 2, pp. 36-42, Feb. 2009.
Chen, A., Chou, E., Wong, J., Yao, A. Y., Zhang, Q., Zhang, S., and Michail, A. CVSSearch: Searching through Source Code using CVS Comments in Proceedings of IEEE International Conference on Software Maintenance (ICSM'01) (2001), 364–373.
German, D. M. An Empirical Study of Fine-Grained Software Modifications in Proceedings of 20th IEEE International Conference on Software Maintenance (ICSM'04) (2004), 316–25.
Zimmermann, T., Zeller, A., Weissgerber, P., and Diehl, S. Mining Version Histories to Guide Software Changes. IEEE Transactions on Software Engineering, 31, 6 (2005), 429–445.
Van Rysselberghe, F. and Demeyer, S. Mining Version Control Systems for FACs (Frequently Applied Changes) in Proceedings of International Workshop on Mining Software Repositories (MSR'04) (May 25, 2004), 48–52.
[6] Dinh-Trong, T. T. and Bieman, J. M. The FreeBSD Project: a Replication Case Study of Open Source Development. IEEE Transactions on Software Engineering, 31, 6 (2005), 481–494.
Bieman, J. M., Andrews, A. A., and Yang, H. J. Understanding Change-Proneness in OO Software Through Visualization in Proceedings of 11th IEEE International Workshop on Program Comprehension (IWPC'03) (2003), 44–53.
Hassan, A. E. and Holt, R. C. Predicting Change Propagation in Software Systems in Proceedings of 20th IEEE International Conference on Software Maintenance (ICSM'04) (2004), 284–93.

Μετρικές ποιότητας λογισμικού κατά τον Christopher Alexander

O αρχιτέκτων Christopher Alexander έχει ορίσει μια σειρά από σχεδιαστικές ιδιότητες που περιστρέφονται γύρω από τον ορισμό κέντρων. Η ικανοποίηση των αντικειμενικών αυτών ιδιοτήτων συνιστά κατά τον Alexander μια έκφραση ποιότητας. Οι ιδιότητες αυτές είναι η κλίμακα σε διάφορα επίπεδα, ένα ισχυρό κέντρο, τα όρια, η εναλλασσόμενη επανάληψη, ο θετικός χώρος, το Καλό σχήμα, η βαθιά αλληλοσύνδεση, η αντίθεση, η κλιμάκωση, η τραχύτητα, η ηχώ, το κενό, η απλότητα και εσωτερική ηρεμία και το ένα με τον κόσμο. Στόχος της εργασίας είναι ο ορισμός και η υλοποίηση μετρικών που θα βρίσκουν χαρακτηριστικά της ποιότητας σύμφωνα με τους ορισμούς του Alexander.

Βιβλιογραφία

Christopher Alexander. The Nature of Order. Center for Environmental Structure, 2003–2006.
Richard P. Gabriel. Designed as designer (http://doi.acm.org/10.1145/1449955.1449813). ACM SIGPLAN Notices 43(10):617–632. September 2008. OOSPLA 2008 Conference Proceedings.

Η ροή σκέψης της Wikipedia

H ελεύθερη εγκυκλοπαίδεια Wikipedia (http://www.wikipedia.org) παρέχει στον παγκόσμιο ιστό πάνω από ένα εκατομύριο άρθρα δομημένα σε μορφή πλούσιου υπερκειμένου. Το περιεχόμενο της εγκυκλοπαίδειας είναι διαθέσιμο σε μορφή βάσης δεδομένων.

Στόχος της εργασίας είναι η ανάλυση των ιδιοτήτων της Wikipedia ως γράφου και η αποδοτική δημιουργία οπτικοποίησης των συνδέσμων κάθε λήμματος με τρόπο που να επιτρέπει στο χρήση να πλοηγείται οπτικά ανάμεσα στα λήμματα. Για να είναι χρήσιμη η παράσταση αυτή θα πρέπει να φαίνονται όχι μόνο οι σύνδεσμοι των άμεσα συνδεδεμένων λημμάτων, αλλά και αρκετές επόμενες σειρές. Η οπτικοποίηση θα βοηθά το χρήστη να πλοηγείται προς λήμματα-κόμβους με ικανό αριθμό υπερσυνδέσμων.

Εναλλακτικά, το περιεχόμενο της Wikipedia μπορεί να παρουσιαστεί σε εικαστική μορφή (π.χ. screen saver). Άρθρα που περιέχουν εικόνες καλής ποιότητας συνδέονται μεταξύ τους σε γράφο τον οποίο το πρόγραμμα ακολουθεί, δείχοντας την κάθε εικόνα στην οθόνη του υπολογιστή. Παλαιότερες εικόνες θα μπορούσαν να απομακρύνονται και να μικραίνουν σε μέγεθος, π.χ. κινούμενες σε σχήμα σπείρας προς το κέντρο της οθόνης.

Βιβλιογραφία

Wikipedia, the free encyclopedia (http://en.wikipedia.org)
TouchGraph (http://www.touchgraph.com/TGAmazonBrowser.html)
Visualizing Everything. Communications of the ACM 44:8 August 2001.
Stephen C. North. Neato User's Guide. Technical Report 59113-921014-14TM, AT&T Bell Laboratories, Murray Hill, NJ, 1992. Available online http://www.research.att.com/sw/tools/graphviz/neatoguide.pdf.
Thomas M. J. Fruchterman and Edward M. Reingold. Graph Drawing by Force-directed Placement. Software: Practice and Experience, 21(11):1129{1164, November 1991.
Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North, and Kiem-Phong Vo. A Technique for Drawing Directed Graphs. IEEE Trans. Sofware Eng., 19(3):214{230, May 1993.
Neal W. Johnston. Documenting a scientific visualization tool (http://www.acm.org/pubs/articles/proceedings/doc/122778/p83-johnston/p83-johnston.pdf). In Ninth Annual ACM International Conference on Systems Documentation, pages 83–87. ACM, ACM Press, October 1991.

Ελέγχος διεπαφών σε προγράμματα Java

Σύγχρονα προγράμματα όλο και συχνότερα υλοποιούν τη λειτουργικότητά τους μέσω διεπαφών έτοιμων κλάσεων. Ο μεγάλος αριθμός των έτοιμων κλάσεων έχει ως αποτέλεσμα προγράμματα στατικού ελέγχου του κώδικα να χρειάζονται εξειδικευμένο κώδικα για να βρουν λάθη στις κλήσεις των μεθόδων τους. Για το λόγο αυτό προτείνουμε ο έλεγχος διεπαφών να αποτελεί τμήμα της διεπαφής και όχι του προγράμματος στατικού ελέγχου. Η δυνατότητα αυτή έχει ήδη υλοποιηθεί (http://www.dmst.aueb.gr/dds/sw/api-verify/) (Spinellis and Louridas) στο πρόγραμμα FindBugs (http://findbugs.sourceforge.net/) (Hovemeyer and Pugh, 2004). Η εργασία έχει ως στόχο να προσθέσει ελέγχους σε σημαντικές κλάσεις της Java και να μετρήσει την αποτελεσματικότητα της μεθόδου με την εφαρμογή της σε μεγάλες βάσεις ανοικτού κώδικα.

Βιβλιογραφία

David Hovemeyer and William Pugh. Finding bugs is easy. ACM SIGPLAN Notices, 39(12):92–106, December 2004. OOPSLA 2004 Onward! Track.
Diomidis Spinellis and Panagiotis Louridas. A framework for the static verification of API calls. The Journal of Systems and Software. To appear.

Επεκτάσεις UML στο περιβάλλον AT&T Graphviz

Το περιβάλλον Graphviz της AT&T επιτρέπει το δηλωτικό καθορισμό γραφημάτων χωρίς τη χρήση γραφικού περιβάλλοντος. Με τον τρόπο αυτό τα γραφήματα μπορούν εύκολα να παραχθούν αυτόματα από άλλα εργαλεία, να ελεχθούν ως προς τις αλλαγές και τις διαμορφώσεις τους, να επαναχρησιμοποιηθούν και να τεκμηριωθούν. Για παράδειγμα η περιγραφή αριστερά δημιουργεί αυτόματα το διάγραμμα που εμφανίζεται δεξιά:

digraph G {
	main->usage;
	main->fprintf;
	main->exit;
	usage->fprintf;
	usage->exit;
}

Δύο ξεχωριστά εργαλεία, το dot και το neato επιτρέπουν το σχεδιασμό κατευθυνόμενων ή μη γράφων. Το περιβάλλον Graphviz είναι διαθέσιμο από το Internet σε μορφή ανοικτού κώδικα.

Το σύστημα UMLGraph (http://www.umlgraph.org) επιτρέπει το σχεδιασμό διαγραμμάτων κλάσεων και ακολουθίας με δηλωτικό τρόπο. Στόχος της εργασίας αυτής είναι η προσθήκη στο περιβάλλον Graphviz πρόσθετων εντολών για το σχεδιασμό και άλλων γραφημάτων UML. Μερικά διαγράμματα που θα μπορούσαν να υποστηρίζονται είναι:

Διάγραμμα αντικειμένων
Διάγραμμα περιπτώσεων χρήσης
Διαγράμματα συνεργασίας
Διαγράμματα κατάστασης
Διαγράμματα δραστηριότητας
Διαγράμματα υλοποίησης

Βιβλιογραφία

Diomidis Spinellis. On the declarative specification of models. IEEE Software, 20(2):94-96, March/April 2003.
UMLGraph home page
Graphviz home page (http://www.research.att.com/sw/tools/graphviz/)
Eleftherios Koutsofios and Stephen North. Drawing graphs with dot. Technical Report 910904-59113-08TM, AT&T Bell Laboratories, Murray Hill, NJ, September 1991. Available online http://www.research.att.com/sw/tools/graphviz/leftyguide.pdf.
Stephen C. North. Neato User's Guide. Technical Report 59113-921014-14TM, AT&T Bell Laboratories, Murray Hill, NJ, 1992. Available online http://www.research.att.com/sw/tools/graphviz/neatoguide.pdf.
Thomas M. J. Fruchterman and Edward M. Reingold. Graph Drawing by Force-directed Placement. Software: Practice and Experience, 21(11):1129{1164, November 1991.
Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North, and Kiem-Phong Vo. A Technique for Drawing Directed Graphs. IEEE Trans. Sofware Eng., 19(3):214{230, May 1993.
Grady Booch, James Rumbaugh, and Ivar Jacobson. The Unified Modeling Language User Guide. Addison-Wesley, 1999.

Υποστήριξη scalable vector graphics στη σουίτα Outwit

Η σουίτα εργαλείων Outwit επιτρέπει την αλληλεπίδραση εργαλείων του Unix στο περιβάλλον των Windows. Περιέχει εργαλεία για πρόσβαση στο πρόχειρο (clipboard), στο registry, της ιδιότητες εγγράφων και σε σχεσιακές βάσεις δεδομένων. Στόχος της εργασίας αυτής είναι η προσθήκη στο πρόγραμμα πρόσβασης στο πρόχειρο (winclip) της δυνατότητας αντιγραφής και επικόλλησης διανυσματικών γραφημάτων με τη μορφή Windows Metafile και Scalable Vector Graphics αντίστοιχα.

Βιβλιογραφία

Outwit home page
Outwit: Unix tool-based programming meets the Windows world. In USENIX 2000 Technical Conference Proceedings, pages 149-158, San Diego, CA, USA, June 2000. Usenix Association.
Word Wide Web Consortium. Scalable Vector Graphics (http://www.w3.org/Graphics/SVG/). Available online http://www.w3.org/Graphics/SVG/.

Έλεγχος λαθών σε λογιστικά φύλλα

Σύμφωνα με στοιχεία ερευνών 21-80% των λογιστικών φύλλων και 1-5% των κελιών τους περιέχουν λάθη. Η εργασία αυτή αρχικά θα διερευνήσει με εμπειρικό τρόπο (ερωτηματολόγια) συχνά λάθη που εμφανίζονται σε λογιστικά φύλλα. Στη συνέχεια θα προταθούν ευρηστικές μέθοδοι και αλγόριθμοι για τον εντοπισμό των λαθών. Με βάση τις μεθόδους αυτές θα υλοποιηθεί εργαλείο εντοπισμού λαθών με βάση τη γλώσσα ενός προγράμματος λογιστικών φύλλων (π.χ. Excel Basic).

Βιβλιογραφία

Doug Bell and Mike Parr. Spreadsheets: a research agenda. ACM SIGPLAN Notices, 28(9):26-28, September 1993.
Judith A. Ross. Spreadsheet Risk. Harvard Business Review, 74(5):10-12, September-October 1996.
Spreadsheet Research (http://panko.cba.hawaii.edu/ssr/)
Stephen C. Johnson. Lint, a C program checker. Computer Science Technical Report 65, Bell Laboratories, Murray Hill, NJ, USA, December 1977.
Gregg Rothermel, Margaret Burnett, Lixin Li, Christopher Dupuis and Andrei Sheretov A methodology for testing spreadsheets ACM Transactions on Software Engineering and Methodology Volume 10 (2001) Pages 110 - 147

Μαθηματικοί υπολογισμοί σε δηλωτικά συστήματα διαμόρφωσης κειμένου

Δηλωτικά συστήματα διαμόρφωσης κειμένου (SGML, TeX, troff) παρέχουν ευέλικτες και εξελίξιμες πλατφόρμες για τη συγγραφή επιστημονικών και τεχνικών κειμένων. Ένα στοιχείο που απουσιάζει από τα συστήματα αυτά είναι η δυνατότητα δηλωτικής εισαγωγής παραμετρικών μαθηματικών υπολογισμών. Η δυνατότητα αυτή η οποία παρέχεται από τους σύγχρονους επεξεργαστές κειμένου μέσω της εισαγωγής λογιστικών φύλλων (MS-Word / Excel) μπορεί να υποστηριχτεί με τον ορισμό κατάλληλης γλώσσας και την υλοποίηση ενός ανάλογου προ-επεξεργαστή.

Βιβλιογραφία

Doug Bell and Mike Parr. Spreadsheets: a research agenda. ACM SIGPLAN Notices, 28(9):26-28, September 1993.
Donald E. Knuth. The TeXbook. Addisson-Wesley, 1989.

Εργαλειοθήκη βελτιστοποίησης

Οι μη-αιτιοκρατικοί αλγόριθμοι βελτιστοποίησης όπως αυτοί που βασίζονται στην εξομοιούμενη ανόπτηση (simulated annealing) και τις γενετικές μεθόδους συχνά απαιτούν πειραματισμό για την εξεύρεση των βέλτιστων παραμέτρων και τεχνικών υλοποίησης. Η εργασία αυτή περιλαμβάνει την υλοποίηση μιας εργαλειοθήκης βελτιστοποίησης η οποία εμπεριέχοντας την υλοποίηση των παραπάνω αλγορίθμων θα επιτρέπει στο χρήστη την επιλογή και αξιολόγηση διαφορετικών αλγορίθμων, τεχνικών, και παραμέτρων τους.

Βιβλιογραφία

Diomidis D. Spinellis and Chrissoleon T. Papadopoulos. Production line buffer allocation: Genetic algorithms versus simulated annealing. In Second International Aegean Conference on the Analysis and Modelling of Manufacturing Systems, pages 89-101, Tinos, Greece, May 1999. University of the Aegean, Department of Business Administration.
Diomidis Spinellis and Chrissoleon T. Papadopoulos. ExPLOre: A modular architecture for production line optimisation. In Proceedings of the 5th International Conference of the Decision Sciences Institute, Athens, Greece, July 1999.
V. Cerny. Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. Journal of Optimization Theory and Applications, 45:41-51, 1985.
David E. Goldberg. Genetic Algorithms: In Search of Optimization & Machine Learning. Addison-Wesley, 1989.
L. Ingber. Simulated annealing: Practice versus theory. Journal of Mathematical Computation Modelling, 18(11):29-57, 1993.

Ασφαλής και διαφανής βελτιστοποίηση σκληρού δίσκου

Τα προγράμματα βελτιστοποίησης σκληρών δίσκων μεταφέρουν τα περιεχόμενα των αρχείων έτσι ώστε να καταλαμβάνουν συνεχή χώρο στην επιφάνεια του δίσκου. Ο συνηθισμένος τρόπος υλοποίησης τέτοιων προγραμμάτων είναι με απευθείας πρόσβαση στα αδόμητα δεδομένα του δίσκου. Ο τρόπος αυτός εγκυμονεί κινδύνους για την ασφάλεια των δεδομένων στην περίπτωση που η βελτιστοποίηση διακοπεί από κάποιον απρόβλεπτο εξωτερικό παράγοντα, εξαρτάται άμεσα από τη δομή του δίσκου και δεν επιτρέπει την εκτέλεση του προγράμματος παράλληλα με άλλα. Προτείνουμε την υλοποίηση προγράμματος βελτιστοποίησης το οποίο - σύμφωνα άλλωστε και με την αρχιτεκτονική λειτουργικών προγραμμάτων μικροπυρήνα - θα εργάζεται μετακινώντας αρχεία στο παρασκήνιο με βάση ευρηστικές μεθόδους προσδιορισμού αρχείων που δεν επηρεάζουν τη λειτουργία του συστήματος.

Βιβλιογραφία

Chris Ruemmler and John Wilkes, UNIX Disk Access Patterns. USENIX Technical Conference Proceedings. p. 405-420, winter 1993. USENIX, San Diego, CA.

Περιεχόμενα