Σε αυτήν την εργασία μελετάται ο Επαγωγικός Λογικός Προγραμματισμός μέσα απο το πρίσμα της μάθησης της Γραμματικής της αγγλικής γλώσσας. Ο λόγος που επιλέχθηκε αυτό το πρόβλημα είναι ότι εξομοιώνει, μέχρι ενός σγημείου, τον τρόπο που τα παιδιά μαθαίνουν να μιλούν κάποια γλώσσα, υπό την έννοια ότι μαθαίνουν να μιλάνε χωρίς να έρθουν σε επαφή με τους κανόνες – τη γραμματική – της γλώσσας, αλλά από την επαφή τους με τα με τα ερεθίσματα – τα παραδείγματα – που έχουν από τον περίγυρό τους. / This paper is about Inductive Logic Programming through the prism of a problem. In our case Grammar Learning.

Στην παρούσα Διπλωματική Εργασία, παρουσιάζεται η πολύ γνωστή μέθοδος Simplex. Με τη βοήθεια της μεθόδου Simplex, μπορούμε να επιλύσουμε προβλήματα γραμμικού προγραμματισμού, ακέραιου γραμμικού προγραμματισμού καθώς και διάφορες παραλλαγές των παραπάνω. Ειδικότερα για τον ακέραιο γραμμικό προγραμματισμό, παρουσιάζονται κάποιες από τις πιο γνωστές μεθόδους αναζήτησης, οι οποίες ανήκουν στην οικογένεια μεθόδων “Branch And Bound”. Επίσης κάποιες τεχνικές αναζήτησης των βέλτιστων λύσεων στο δένδρο που δημιουργείται από τις προηγούμενες τεχνικές. Τα παραπάνω υλοποιήθηκαν σε ένα λογισμικό με γραφικό περιβάλλον (GUI), το οποίο είναι συμβατό με τις περισσότερες εκδόσεις του Λειτουργικού Συστήματος, Windows της Microsoft και χωρίς να χρειάζονται κάτι επιπλέον σε έναν Προσωπικό Υπολογιστή. / This thesis presents the well-known method Simplex. With method Simplex, we can solve problems of linear programming, integer linear programming and several variants of the above. Especially for the integer linear programming, presented some of the most known search methods, which belong to the family of methods "Branch And Bound". Also presented some search techniques for optimal solutions in the tree, generated by the same techniques. These were implemented in a software with graphical interface (GUI), which is compatible with most versions of the Microsoft Windows OS, with a simple installation.

Ο Επαγωγικός Λογικός Προγραμματισμός (Inductive Logic Programming ή, σε συντομογραφία ILP) είναι ο ερευνητικός τομέας της Τεχνητής Νοημοσύνης (Artificial Intelligence) που δραστηριοποιείται στη τομή των γνωστικών περιοχών της Μάθησης Μηχανής (Machine Learning) και του Λογικού Προγραμματισμού (Logic Programming).Ο όρος επαγωγικός εκφράζει την ιδέα του συλλογισμού από το επί μέρους στο γενικό. Μέσω της επαγωγικής μάθησης μηχανής ο ILP επιτυγχάνει το στόχο του που είναι η δημιουργία εργαλείων και η ανάπτυξη τεχνικών για την εξαγωγή υποθέσεων από παρατηρήσεις (παραδείγματα) και η σύνθεση-απόκτηση νέας γνώσης από εμπειρικές παρατηρήσεις. Σε αντίθεση με της περισσότερες άλλες προσεγγίσεις της επαγωγικής μάθησης ο ILP ενδιαφέρεται για της ιδιότητες του συμπερασμού με κανόνες για την σύγκλιση αλγορίθμων και για την υπολογιστική πολυπλοκότητα των διαδικασιών. Ο ILP ασχολείται με την ανάπτυξη τεχνικών και εργαλείων για την σχεσιακή ανάλυση δεδομένων. Εφαρμόζεται απευθείας σε δεδομένα πολλαπλών συσχετισμών για την ανακάλυψη προτύπων. Τα πρότυπα που ανακαλύπτονται από τα συστήματα στον ILP εκφράζονται ως λογικά προγράμματα. Τα λογικά προγράμματα αποτελούνται από ειδικούς κανόνες, οι οποίοι χωρίζονται στις προϋποθέσεις και στα συμπεράσματα. Ο ILP έχει χρησιμοποιηθεί εκτεταμένα σε προβλήματα που αφορούν τη μοριακή βιολογία, την βιοχημεία και την χημεία. Τα παραδείγματα, οι κανόνες εκφράζουν την γνώση υποβάθρου εκφράζονται σε μια γλώσσα λογικού προγραμματισμού όπως η Prolog. Ο Επαγωγικός Λογικός Προγραμματισμός διαφοροποιείται από τις άλλες μορφές Μάθησης Μηχανής, αφ’ ενός μεν λόγω της χρήσης μιας εκφραστικής γλώσσας αναπαράστασης και αφ’ ετέρου από τη δυνατότητά του να χρησιμοποιεί τη γνώση υποβάθρου. Διάφορες εφαρμογές έχουν αναπτυχθεί, εκ των οποίων η πιο πρόσφατη είναι η Progol, που αποτελείται από ένα διερμηνέα της Prolog ο οποίος συνοδεύεται από έναν αλγόριθμο Αντίστροφης Συνεπαγωγής (Inverse Entailment) που κατασκευάζει νέες προτάσεις με τη γενίκευση των παραδειγμάτων που περιέχονται στη βάση δεδομένων της Prolog. Η θεωρία του Επαγωγικού Λογικού Προγραμματισμού εγγυάται ότι η Progol θα διεξάγει μια αποδεκτή αναζήτηση στο διάστημα των γενικεύσεων, βρίσκοντας το ελάχιστο σύνολο προτάσεων, από το οποίο όλα τα παραδείγματα μπορούν να προκύψουν. Στην συγκεκριμένη εργασία η Progol είναι το εργαλείο που χρησιμοποιείται για την ανάπτυξη των παραδειγμάτων εφαρμογής του ILP. / The Inductive Reasonable Planning (Inductive Logic Programming or, in abbreviation ILP) is the inquiring sector Artificial Intelligence that is activated in the section of cognitive regions of Learning of Machine (Machine Learning) and Reasonable Planning (Logic Programming). The term inductive expresses the idea of reasoning from on part in general. Via the inductive learning of machine the ILP achieves his objective that is the creation of tools and the growth of techniques for the export of affairs from observations (examples) and composition of new knowledge from empiric observations. Contrary to more other approaches of inductive learning the ILP is interested for its inference attributes with rules on the convergence of algorithms and on the calculating complexity of processes. The ILP deals with the growth of techniques and tools for the relational analysis of data. It is applied directly in data of multiple correlations on the discovery of models. The models that are discovered by the systems in the ILP are expressed as reasonable programs. The reasonable programs are constituted by special rules, which are separated in the conditions and in the conclusions. The ILP has been used extensive in problems that concern the molecular biology, the biochemistry and the chemistry. The examples, the rules express the knowledge of background are expressed in a language of reasonable planning as the Prolog. The Inductive Reasonable Planning is differentiated by the other forms of Learning of Machine, on the one hand men because the use of expressive language of representation and on the other hand by his possibility of using the knowledge of background. Various applications have been developed, from which most recent is Progol, that is constituted from interpreter of Prolog which is accompanied by a algorithm of Inverse Entailment that manufactures new proposals with the generalisation of examples that is contained in the base of data of Prolog. theory of Inductive Reasonable Planning guarantees that the Progol will carry out a acceptable search in the interval of generalisations, finding the minimal total of proposals, from which all the examples can result. In the particular work the Progol is the tool that is used for the growth of examples of application of ILP.

Η παρούσα μεταπτυχιακή εργασία πραγματεύεται το πρόβλημα του σχεδιασμού του ωρολογίου προγράμματος μαθημάτων ενός εκπαιδευτικού ιδρύματος και πιο συγκεκριμένα ενός πανεπιστημίου. Λόγω της πολυπλοκότητας και της ύπαρξης πολυάριθμων μεταβλητών και παραμέτρων το πρόβλημα ανήκει στην κατηγορία των NP-complete προβλημάτων, γεγονός που κάνει την εξεύρεση της βέλτιστης λύσης μία πολύ δύσκολη υπόθεση. Η βιβλιογραφική ανασκόπηση έδειξε ότι έχουν προταθεί και εφαρμόζονται πολλές και διαφορετικές μεθοδολογίες επίλυσης του προβλήματος. Οι τεχνικές προέρχονται από πολλούς και διαφορετικούς τομείς όπως για παράδειγμα το μαθηματικό προγραμματικό, τον ακέραιο γραμμικό προγραμματισμό, τις μετα-ευρετικές μεθόδους, αλλά και από τον χώρο της Τεχνητής Νοημοσύνης. Η μέθοδος επίλυσης, που προτείνεται από την παρούσα εργασία, είναι η πολυκριτηριακή ανάλυση βασιζόμενη στον συναινετικό προγραμματισμό (compromise programming). Η εφαρμογή της μεθόδου σε δεδομένα προβλημάτων ωρολογίου προγραμματισμού, είχε πολύ ικανοποιητικά αποτελέσματα, καθώς προεκύψαν ποιοτικά ωρολόγια προγράμματα, που ικανοποιούσαν όλους τους περιορισμούς. / The timetabling problem constists in scheduling a sequence of lectures between teachers and students in a prefixed period of time, satisfying a set of constraints of various type. Due to the complexity and the existence of many variables and parameters, the problem belongs in the category of NP-complete problems, fact that makes the discovery of an optimal solution, a very difficult affair. The bibliographic search, showed that have been proposed and are applied many and different solving techniques, which are based on Mathematical programming (Integer Linear Programming), on Graph Colouring, on Meta-Heuristics Methods, on Multicriteria approaches, on Case-based approaches, but also belonging to Artificial Intelligence. In this paper, the multicriteria approach based on Compromise programming is suggested. The application of technique in timetable data of an educational institute, had very good results, and provided qualitative timetables, satisfying all constraints.

- / -

An important and challenging problem that Process Engineers frequently encounter is the determination of appropriate control structures that minimize the loss of process performance under the effect of uncertainties. This can be achieved by selecting subsets of controlled and manipulated variables and designing their interconnection (controller synthesis). This is known as the Control Structure Selection Problem (CSSP) In this Thesis, a systematic optimization methodology, based on the back-off concept proposed by Prof J. D. Perkins and co-workers, is presented for the CSSP. The proposed formulation offers the following improvements: a) improves the accuracy of calculations and b) reduces computational time and effort. Specifically, the error involved in the approximation of the nonlinear constraint that defines the magnitude of the back-off vector (needed for control structure selection) is reduced by the introduction of a more accurate linear approximation. In addition, the methodology is able to track the effect of simultaneously occurring disturbances at the same time and estimate their worst impact on process economics. The reduction of computational time is achieved by eliminating the state variables from the final formulation. In this way, the number of equations needed for the CSSP solution is significantly reduced and allows the algorithm to locate the solution faster without affecting the performance. The proposed methodology is firstly applied in a classical distillation column (medium scale) and in a complex and highly nonlinear reactive distillation column (large scale). The results obtained from these case studies made the way for the application of the methodology on the plantwide problem of the benchmark Vinyl Acetate monomer production plant in order to demonstrate the benefits of the proposed algorithm. / Η παρούσα εργασία παρουσιάζει μια συστηματική μεθοδολογία για την εύρεση βέλτιστων δομών ρύθμισης σε συστήματα μεγάλης κλίμακας, όπως για παράδειγμα ολοκληρωμένες μονάδες παραγωγής και βασίζεται στην ελαχιστοποίηση των επιπτώσεων των διαταραχών στην οικονομική απόδοση μιας διεργασίας. Το κύριο στοιχείο της μεθοδολογίας είναι το διάνυσμα υποχώρησης από τους ενεργούς περιορισμούς (μ), το οποίο προτάθηκε από τον Prof. J.D. Perkins και την ερευνητική του ομάδα. Η προτεινόμενη μεθοδολογία ενσωματώνει τα κύρια χαρακτηριστικά της μεθοδολογίας του διανύσματος (μ) και παρουσιάζει μια σειρά βελτιώσεων με στόχο τον περιορισμό των μειονεκτημάτων που απέτρεπαν την εφαρμογή της σε συστήματα μεγάλης κλίμακας. Οι βελτιώσεις επικεντρώνονται σε δύο ζητήματα: α) αύξηση της ακρίβειας των υπολογισμών και β) μείωση του υπολογιστικού φόρτου και χρόνου. Η αύξηση της ακρίβειας των υπολογισμών εντοπίζεται στην κατασκευή ενός βελτιωμένου προσεγγιστικού προβλήματος για την κατασκευή κάτω φραγμάτων για τη βέλτιστη λύση. Η βασική ιδέα πίσω από τη προτεινόμενη βελτίωση βασίζεται στη προσέγγιση των μη γραμμικών όρων που εμφανίζονται με ένα σύνολο γραμμικών εξισώσεων. Επίσης για πιο ακριβείς υπολογισμούς, εξετάζεται κάθε διαταραχή ξεχωριστά σε ένα εύρος συχνοτήτων και στη συνέχεια η μέγιστη επίδραση της καθεμίας χρησιμοποιείται από τον αλγόριθμο έτσι ώστε να υπολογιστεί η μέγιστη δυνατή επίπτωση τους στην οικονομική απόδοση της διεργασίας Η μείωση του υπολογιστικού φόρτου και χρόνου επιτυγχάνεται μέσω της απαλοιφής των μεταβλητών κατάστασης. Με αυτό τον τρόπο, ο αριθμός των εξισώσεων που απαιτείται για την επίλυση του προβλήματος μειώνεται σημαντικά και εντοπίζει τη βέλτιστη λύση σε μικρότερο αριθμό επαναλήψεων της μεθόδου, γεγονός που επιτρέπει την εφαρμογή της σε προβλήματα μεγάλης κλίμακας. Τέλος, η προτεινόμενη μεθοδολογία έχει εφαρμοστεί σε δύο αποστακτικές στήλες και τα αποτελέσματα άνοιξαν το δρόμο για την εφαρμογή της μεθόδου σε μια μονάδα παραγωγής οξικού μεθυλεστέρα, όπου τα πλεονεκτήματα της μεθόδου είναι περισσότερο ορατά και πρακτικά χρήσιμα.

Η ανάγκη για την επίλυση μεγάλων προβλημάτων και η εξέλιξη της τεχνολογίας του διαδικτύου, είχε ως αποτέλεσμα την διαρκή ανάγκη για την εύρεση όλο και περισσότερων πόρων. Η ανάγκη αυτή οδήγησε στην δημιουργία δομών συνεργαζόμενων υπολογιστικών συστημάτων, με απώτερο σκοπό την επίλυση προβλημάτων που απαιτούν μεγάλη υπολογιστική ισχύ ή την αποθήκευση μεγάλου όγκου δεδομένων. Η ύπαρξη τέτοιων δομών αλλά και κεντρικών μονάδων επεξεργασίας με περισσότερους από έναν επεξεργαστές, δημιούργησε πρωτόκολλα για την δημιουργία εφαρμογών που θα εκτελούνται και θα επιλύουν ένα πρόβλημα σε περισσότερους από έναν επεξεργαστές, ώστε να επιτευχθεί η μείωση του χρόνου εκτέλεσης. Ένα παράδειγμα τέτοιου πρωτοκόλλου είναι αυτό της ανταλλαγής μηνυμάτων (MPI). Σκοπός της παρούσας διπλωματικής εργασίας είναι η τροποποίηση μιας υπάρχουσας εφαρμογή, που απαιτεί σημαντική υπολογιστική ισχύ, με σκοπό την εκμετάλλευση συστημάτων όπως αυτά που περιγράφηκαν προηγούμενα. Μέσα από αυτή την διαδικασία θα γίνει ανάλυση των πλεονεκτημάτων και των μειονεκτημάτων του παράλληλου προγραμματισμού. / The need to solve large problems and the development of internet technology, has resulted in the need to find more and more resources. This need led to the creation of structures collaborating systems, with a view to solving problems that require large computing power or storage of large amounts of data. The existence of such structures and central processing units with more than one processor, created protocols for the develop applications that will run and will solve a problem in more than one processor in order to achieve the reduction in execution time. An example of such a protocol is that of messaging (MPI). The purpose of this diploma thesis is to modify an existing application that requires significant computing power to exploit systems such as those described above. Through this process will analyze the advantages and disadvantages of parallel programming.

Στην παρούσα διπλωματική εργασία σχεδιάστηκε και υλοποιήθηκε ένα δίκτυο πραγματικού χρόνου με σκοπό την διασύνδεση μιας ομάδας μικροελεγκτών. Bασισμένος στο δίκτυο, αναπτύχθηκε ένας δικτυακός bootloader για μικροελεγκτές AVR και σχεδιάστηκε desktop εφαρμογή για την διεπαφή του χρήστη με το δίκτυο. Απώτερος σκοπός του εγχειρήματος αυτού είναι η χρήση του συστήματος από φοιτητές στο πλαίσιο των μαθημάτων μικροϋπολογιστών και συγκεκριμένα να διευκολύνει την ανάπτυξη δικτυακών εφαρμογών με μικροελεγκτές. / At this diploma thesis a real-time network protocol was designed and implemented in order to interconnect a group of microcontrollers. Based at this protocol, a network bootloader was developed for AVR microcontrollers and a desktop application for the interface of the user with the network was developed. Ultimate goal of this work is to be used from students of microcomputer courses and specifically to facilitate the development of network applications with microcontrollers.

Ο τραπεζικός τομέας υφίσταται σημαντικές αλλαγές τα τελευταία χρόνια σε διεθνές επίπεδο, ως απόρροια των αλλαγών στο γενικότερο οικονομικό γίγνεσθαι. Ειδικότερα στη χώρα μας είναι έκδηλη τα τελευταία χρόνια η ανάγκη για αναπροσαρμογή του τρόπου λειτουργίας των πιστωτικών ιδρυμάτων, ώστε να προσαρμοστούν στις μεταβαλλόμενες απαιτήσεις της πελατειακής τους βάσης. Στόχος της παρούσας εργασίας είναι να προσεγγιστεί το ζήτημα της αναδιάρθρωσης των τραπεζικών δικτύων, όπως αυτά έχουν προκύψει μετά από εξαγορές ή συγχωνεύσεις, με απώτερο στόχο την βέλτιστη εξυπηρέτηση των πελατών με το μικρότερο δυνατό κόστος λειτουργίας. Για να επιτευχθεί η αναδιάρθρωση προτείνονται δύο μαθηματικά μοντέλα χωροθέτησης εγκαταστάσεων, που εξετάζουν το πρόβλημα με βάση δύο διαφορετικούς άξονες: το ένα στοχεύοντας στην ελαχιστοποίηση του κόστους και το δεύτερο στην μεγιστοποίηση της καλυπτόμενης ζήτησης με δεδομένο προϋπολογισμό. Για την επίλυση των μαθηματικών μοντέλων αξιοποιήθηκαν δεδομένα μεγάλου τραπεζικού ομίλου που δραστηριοποιείται στην Ελλάδα, επικεντρώνοντας στο υπάρχον εγκατεστημένο δίκτυο εντός του Δήμου Πατρέων. Από την εμπειρική εφαρμογή διαπιστώθηκε σαφής πλεονασμός του υπάρχοντος δικτύου σε μονάδες και προσωπικό, ενώ παράλληλα τα μοντέλα καταλήγουν σε διαφορετικές λύσεις χωροθέτησης για κάθε εκδοχή του προβλήματος. Με όποιο τρόπο όμως και να προσεγγιστεί το πρόβλημα της αναδιάρθρωσης, φαίνεται ότι τα αποτελέσματα αναφορικά με το πλήθος των μονάδων και του απασχολούμενου προσωπικού συγκλίνουν, εξασφαλίζοντας ταυτόχρονα σημαντική μείωση του κόστους λειτουργίας. / The banking sector is undergoing significant changes recently at an international level, as a consequence of changes in the general economic status. Especially in our country, the need for adjusting the operation of credit institutions to adapt to the changing demands of their customer base is obvious. The aim of this paper is to approach the issue of restructuring of banking networks, as they have arisen after mergers or acquisitions, aiming to optimal customer service at the lowest possible operating cost. To achieve the restructuring we propose two mathematical models of facility location, considering the problem on two different axes: firstly aiming at minimizing the cost and secondly at maximizing the demand covered with pre-given budget. To solve the mathematical models we utilized data from a large banking group operating in Greece, focusing on existing established network within the Municipality of Patras. The empirical application showed a clear redundancy of the present network units and personnel, while models result in different solutions of facility location for each version of the problem. Whichever way used to approach the problem of restructuring, it seems that the results regarding the number of units and personnel converge, while ensuring a significant reduction in operating costs.

Η διπλωµατική εργασία αποτελεί συνέχεια της µελέτης προβληµάτων χρονοπρογραµµατισµού µε αυστηρές προθεσµίες που ξεκίνησε η Αµαλία Στούµπου στην δικιά της διπλωµατική εργασία µε όνοµα "Προβλήµατα Επιτάχυνσης ∆ιεργασιών σε Grid Computing: Αλγόριθµοι και Πολυπλοκότητα". Εξετάζονται προβλήµατα δροµολόγησης διεργασιών σε περισσότερους από έναν, ίδιους µεταξύ τους, επεξεργαστές. ∆ίνονται αλγόριθµοι που λύνουν το πρόβληµα ελαχιστοποίησης του συνολικού χρόνου εκτέλεσης, µε αυστηρές προθεσµίες, αρχικά για 2 και στη συνέχεια για m επεξεργαστές. Οι αλγόριθµοι αυτοί έχουν ψευδοπολυωνυµική πολυπλοκότητα. Στη συνέχεια εξετάζονται προβλήµατα δροµολόγησης και επιτάχυνσης διεργασιών µε ίδιο χρόνο εκτέλεσης, σε περιβάλλοντα µε ίδιους µεταξύ τους επεξεργαστές και δίνονται πολυωνυµικοί αλγόριθµοι που τα λύνουν. Τέλος αναφέρονται συνοπτικά ορισµένα προβλήµατα του ευρύτερου χώρου προϐληµάτων χρονοπρογραµµατισµού που µπορούν να προσεγγιστούν ή να λυθούν µε τεχνικές που εφαρµόστηκαν για τη λύση των προηγούµενων προβληµάτων που αναφέρθηκαν. / This thesis is a continuation of the study of scheduling problems with strict deadlines that begun in the thesis "Προβλήµατα Επιτάχυνσης ∆ιεργασιών σε Grid Computing : Αλγόριθµοι και Πολυπλοκότητα" by Amalia Stoumpou. We study scheduling problems on more than one parallel processors. Algorithms are given that solve the problem of minimizing the makespan with strict deadlines, first for 2 and then for m processors. These algorithms are pseudopolynomial in complexity. We also study problems of scheduling and speedup of processes with the same execution time in parallel processor environments and we give pseudopolynomial algorithms that solve them. Finally, we mention briefly other problems that can be solved or approached using the techniques that we applied to solve the previous problems.