Search

Η παρούσα διπλωµατική εργασία ασχολείται με το θέμα των Αλγορίθμων Επίλυσης Προβληµάτων SAT. Η εργασία αυτή εκπονήθηκε στα πλαίσια του Εργαστηρίου Ενσύρµατης Επικοινωνίας του Τµήματος Ηλεκτρολόγων Μηχανικών και Τεχνολογίας Υπολογιστών της Πολυτεχνικής Σχολής του Πανεπιστηµίου Πατρών. Σκοπός της είναι η δημιουργία ενός Προσομοιωτή των αλγορίθμων αυτών, ο οποίος να μπορεί να προσπελαστεί από οποιονδήποτε μέσω του διαδικτύου. Αρχικά έγινε µία εισαγωγή στο αντικείμενο της Τεχνητής Νοημοσύνης και πιο συγκεκριµένα στην Προτασιακή Λογική, ενώ δόθηκε και το απαραίτητο υπόβαθρο για να κατανοηθεί το πρόβληµμα και οι τεχνικές λύσης του. Τέλος, επιλέχθηκε να γίνει η υλοποίηση του Προσωμοιωτή σε Java. This diploma dissertation deals with SAT solvers, algorithms for the Boolean satisfiability problem. It was produced in the Wire Communications Laboratory of the Electrical and Computer Engineering Department of the University of Patras. Its aim is to create a simulator for these algorithms, accessible to anyone via the Internet. An introduction to the field of Artificial Intelligence and more specifically to Propositional Calculus was given as well as the necessary groundwork to understand the problem and its solution approaches. The simulation implementation was developed in Java

H Ενοποιημένη Γλώσσα Μοντελοποίησης (Unified Modeling Language) αποτελεί την πρότυπη και πλέον δημοφιλή γλώσσα για την οπτικοποίηση, προσδιορισμό, ανάπτυξη και τεκμηρίωση συστημάτων λογισμικού και όχι μόνο. Η πλούσια γραφική σημειολογία της UML σε συνδυασμό με τις δυνατότητες μοντελοποίησης που παρέχει, την καθιστούν ικανή να χρησιμοποιηθεί στην ανάπτυξη ενσωματωμένων συστημάτων. Ωστόσο, στα ενσωματωμένα συστήματα, αλλά και γενικότερα σε συστήματα συγκεκριμένου πεδίου υπάρχουν κάποιοι επιπλέον παράγοντες που πρέπει να ληφθούν υπόψη. Οι επεκτάσεις της UML δίνουν τη δυνατότητα αναπαράστασης των βασικών χαρακτηριστικών των ενσωματωμένων συστημάτων. Επιπλέον, παρέχουν νέες μεθόδους σχεδιασμού που επιτρέπουν τον διαμερισμό εφαρμογής και αρχιτεκτονικής, για ένα πιο αποδοτικό και επαναχρησιμοποιήσιμο σύστημα. Στην παρούσα εργασία μελετώνται τα βασικά στοιχεία της UML καθώς και η χρήση της στην ανάπτυξη ενσωματωμένων συστημάτων. Στη συνέχεια, χρησιμοποιώντας τη UML μοντελοποιείται και αναπτύσσεται η εφαρμογή ελέγχου ενός συστήματος γραμμής παραγωγής, του Festo MPS. Επιπλέον, αναπτύσσεται και υλοποιείται εφαρμογή εξομοίωσης του φυσικού συστήματος Festo MPS για την επιβεβαίωση της σωστής λειτουργίας της εφαρμογής ελέγχου. The Unified Modeling Language (UML) constitutes the most popular standardized language for visualizing, specifying and documenting all the artefacts of a software system. Its rich graphical notation, in combination with the modelling facilities it provides, makes it possible for UML to be used in the development of embedded systems. However, in embedded system design, as well as in specific domain problems, there are some additional factors that should be taken into consideration. The extensions of UML provide the opportunity for representing the basic features of embedded systems. In addition, these extensions provide new design methods which allow the separation of the application from the architecture, leading to a more efficient and reusable system. At this thesis the basic elements of UML as well as its use in the development of embedded systems are studied. Moreover, using UML, the control application of a linear production system, Festo MPS is modelled and developed. Finally, a simulator application of the physical system Festo MPS is developed, in order to verify that the constructed control application works properly.

Στην παρούσα διατριβή αντιμετωπίζεται το πρόβλημα της παροχής επιστημονικού λογισμικού σαν υπηρεσία διαδικτύου, με έμφαση στις εφαρμογές χρονοπρογραμματισμού ανθρώπινων πόρων. Οι εφαρμογές αυτές χαρακτηρίζονται από ειδικές ανάγκες ως προς το περιβάλλον υλικού και λογισμικού, ανήκοντας στο γενικότερο χώρο των NP-hard προβλημάτων βελτιστοποίησης. Δημιουργήθηκαν και παρουσιάζονται δύο πλατφόρμες παροχής υπηρεσιών, SchedSP και SchedSP-WS, με στόχο να παρέχουν υπηρεσίες λειτουργικού συστήματος στους δημιουργούς εφαρμογών ιστού, ενώ παρέχονται ειδικές υπηρεσίες για την υποστήριξη εφαρμογών χρονοπρογραμματισμού. Η απαιτούμενη υπολογιστική χωρητικότητα εξασφαλίστικε αρχικά από το σύστημα PLEIADES, που επίσης παρουσιάζεται ως πάροχος υπολογιστικής υποδομής σαν υπηρεσιά, το οποίο αργότερα αντικαταστάθηκε από την υποδομή του ευρωπαϊκού έργου υποδομής EGEE. Επίσης, παρουσιάζεται ένα μοντέλο κατανεμημένης εφαρμογής χρονοπρογραμματισμού, το οποίο αποτελεί τη βάση του πλαισίου SchedScripter. Το πλαίσιο SchedScripter που επίσης παρουσιάζεται, επιτρέπει τη δημιουργία κατανεμημένων εφαρμογών χρονοπρογραμματισμού, βασισμένων στο υπολογιστικό πλέγμα. This PhD dissertation deals with the provision of scientific software as Internet service, with emphasis on human resources scheduling applications. These applications have special needs from the computational environment, in terms of software and hardware, as they are NP-hard optimization problems. Two application service provider platforms have been created and presented, SchedSP and SchedSP-WS, aiming to offer operating system like services to web application developers, while they offer special support for scheduling applications. The required computational capacity initially was provided by PLEADES, which is also presented as a computational infrastructure service provider, to be substituded later by the EU infrastructures project EGEE. A distributed scheduling application model is presented, which is the foundation of the SchedScripter framework. The SchedScripter framework, which is also presented, enables the creation of distributed scheduling applications, running on a computational grid.

Το διάνυσμα προτύπων αποτελεί σύνθεση ενός συνόλου χαρακτηριστικών γνωρισμάτων και ταξινομείται σε δύο κατηγορίες: τα αρχικά χαρακτηριστικά γνωρίσματα και ένα σύνολο μη γραμμικών προβολών των αρχικών χαρακτηριστικών γνωρισμάτων. Στην ταξινόμηση, η κατασκευή χαρακτηριστικών γνωρισμάτων είναι ένα βήμα προ-επεξεργασίας στο οποίο ένα ή περισσότερα γνωρίσματα κατασκευάζονται από ένα αρχικό σύνολο. Ο αριθμός και ο τύπος των χαρακτηριστικών γνωρισμάτων είναι κρίσιμα για την ακρίβεια ταξινόμησης και την υπολογιστική πολυπλοκότητα. Καθώς ο αριθμός των χαρακτηριστικών γνωρισμάτων αυξάνει, απαιτούνται πρόσθετα παραδείγματα για να ολοκληρώσουν μια αξιόπιστη διαδικασία κατάρτισης, επιτρέποντας περισσότερες δυνατότητες αξιόπιστης γενίκευσης χωρίς υπέρ-εκπαίδευση αποτελεσμάτων. Σε αυτή τη διπλωματική εργασία εξετάζουμε και αναλύουμε τη χρήση του Γενετικού προγραμματισμού για την προ-επεξεργασία δεδομένων έτσι ώστε να κατασκευάσουμε μη γραμμικά, ιδιαίτερα προφητικά, χαρακτηριστικά γνωρίσματα από τα αρχικά. Για το σκοπό αυτό χρησιμοποιούμε γενετικούς αλγορίθμους και συγκεκριμένα τον C4.5 αλγόριθμο εκμάθησης δέντρων απόφασης, τον G-Net, ένα διανεμημένο εξελικτικό αλγόριθμο ικανό να συμπεράνει τους ταξινομητές από τα προ-συγκεντρωμένα στοιχεία καθώς και τη μέθοδο που βασίζεται στο συνδυασμό της καθιερωμένης τεχνικής της γραμματικής εξέλιξης και των τεχνητών νευρικών δικτύων. Εφαρμόζοντας τον γενετικό προγραμματισμό σε διάφορα σύνολα δεδομένων ταξινόμησης επιτυγχάνουμε μεγαλύτερη ακρίβεια ταξινόμησης. Όλοι οι αλγόριθμοι που χρησιμοποιήθηκαν έδωσαν πολύ καλύτερη απόδοση στα σύνολα δεδομένων όταν συμπεριλήφθηκε μια ενιαία εξελιγμένη μεταβλητή, επιλύοντας προβλήματα που βρίσκονται πολύ συχνά στις εφαρμογές υπολογιστών όπως Ιατρική και ελαττωματική διάγνωση, πρόγνωση, αναγνώριση εικόνας, κατηγοριοποίηση κειμένων, προσαρμοστική σκιαγράφηση χρηστών.