Η εύρεση γεννητικών δέντρων ελάχιστου-κόστους αποτελεί ένα κλασικό επιστημονικό πρόβλημα με σημαντικές εφαρμογές στη σχεδίαση δικτύων. Δοθέντος ενός γραφήματος, όπου κάθε πλευρά σχετίζεται με ένα βάρος (κριτήριο) το πρόβλημα της εύρεσης ενός Ελάχιστου Γεννητικού Δέντρου ανέρχεται στο πρόβλημα της εύρεσης ενός γεννητικού δέντρου με το ελάχιστο συνολικό κόστος. Το πρόβλημα ΕΓΔ έχει αποτελέσει αντικείμενο ενδιαφέροντος πολλών μελετητών με αποτέλεσμα την ανάπτυξη αλγορίθμων πολυωνυμικού-χρόνου, όπως είναι ο αλγόριθμος του Prim, του Sollin και του Kruskal. Στον πραγματικό κόσμο όμως υπάρχουν περιπτώσεις όπου πρέπει να λάβουμε ταυτόχρονα υπόψη πολλά κριτήρια προκειμένου να καθορίσουμε ένα ΕΓΔ. Αυτό συμβαίνει γιατί κάθε πλευρά του γραφήματος σχετίζεται με παραπάνω από ένα κόστη. Για παράδειγμα, στη σχεδίαση ενός τηλεπικοινωνιακού δικτύου, πέρα από το κόστος κατασκευής των συνδέσεων μεταξύ των πόλεων ή των τερματικών μας ενδιαφέρουν και άλλοι παράγοντες. Ο χρόνος που απαιτείται για την κατασκευή, η δυσκολία και πολυπλοκότητα της κατασκευής, η καθυστέρηση μετάδοσης της πληροφορίας αλλά και η αξιοπιστία του συστήματος αποτελούν σημαντικούς παράγοντες που πρέπει να ληφθούν υπόψη στην σχεδίαση του δικτύου. Αλλά και στην καθημερινή ζωή, πολλές φορές χρειάζεται να ληφθούν σημαντικές αποφάσεις οι οποίες εξαρτώνται από περισσότερα από ένα κριτήρια. Παραδείγματος χάριν, άνθρωποι που ταξιδεύουν θέλουν να βελτιστοποιήσουν τη διανυόμενη απόσταση, το κόστος, και το χρόνο μετακίνησης. Το ζητούμενο είναι πως μπορεί να οδηγηθεί κανείς στη λήψη μιας βέλτιστης για αυτόν απόφασης, που κάτω από δεδομένες συνθήκες μπορεί να είναι περισσότερες από μία. Δηλαδή, δεν οδηγούμαστε σε μία μοναδική βέλτιστη λύση αλλά σε ένα σύνολο από «βέλτιστες» λύσεις και ο ενδιαφερόμενος, ανάλογα με τα ιδιαίτερα χαρακτηριστικά του προβλήματος, κάνει την τελική επιλογή. Το πρόβλημα ΕΓΔ, στο οποίο ζητείται η ελαχιστοποίηση περισσοτέρων του ενός κριτηρίων είναι γνωστό ως το πρόβλημα ΕΓΔ πολλαπλών κριτηρίων (multi-criteria minimum spanning tree problem). Η συνεισφορά της παρούσας διπλωματικής λοιπόν αποτελείται από δύο μέρη: Το πρώτο, εστιάζεται στην κριτική επισκόπηση και περιγραφή των υπαρχόντων μεθόδων επίλυσης του προβλήματος ΕΓΔ δύο κριτηρίων. Το δεύτερο, αφορά την υλοποίηση και πειραματική αξιολόγηση δύο βασικών αλγορίθμων για την επίλυση του εν λόγω προβλήματος. Συγκεκριμένα, υλοποιήθηκε η τροποποιημένη εκδοχή (για το πρόβλημα ΕΓΔ πολλαπλών κριτηρίων) του αλγορίθμου του Prim καθώς και μία προσεγγιστική μέθοδος επίλυσης του προβλήματος ΕΓΔ πολλαπλών κριτηρίων. / The minimum spanning tree problem (MST) is of high importance in network optimization. Given a connected graph G where each edge has a weight, the goal is to find the spanning tree with the least cost among all spanning trees of G. Due to its many practical applications, the MST problem has been studied in depth and many efficient polynomial-time algorithms have been developed by Sollin, Kruskal, Prim etc. But in real life, there cases where one has to take simultaneously into consideration many criteria in order to determine a MST because there are multiple weights defined on each edge of the graph. For example, when designing the layout of a telecommunication network, besides the cost for connections between cities or terminals we are interested in other factors too. The time for communication and construction, the difficulty of the construction or the reliability of the system are also important factors and need to be taken into consideration. But also in everyday life, in many cases we need to take decisions that depend on multiple criteria. For instance, people who travel want to minimize simultaneously the cost, the distance and the time. The problem is that in these cases there is not only one optimal solution but rather a set of optimal solutions and the decision maker depending on the characteristics of each case will make the final call. The MST problem in which we want to minimize more than one criteria is known as the multi-criteria minimum spanning tree problem. The contribution of this thesis is composed of two parts. The first part focuses on the critical survey and description of various methods for solving the bi-criteria case of the MST problem. The other part focuses on the implementation and the experimental evaluation of two known and important algorithms. More precisely, we have implemented the modified version of the Prim’s algorithm (for the multi-criteria MST problem) and one approximate algorithm as proposed by Hamacher & Ruhe.

Τo Gene Expression Programming - GEP (Προγραμματισμός Γονιδιακής Έκφρασης - ΠΓΕ) είναι μια μέθοδος αυτόματης παραγωγής προγραμμάτων η οποία ανήκει στη γενική κατηγορία των Εξελικτικών Αλγορίθμων, εκείνων των τεχνικών δηλαδή που εμπνέονται από τις φυσικές διεργασίες της βιολογικής εξέλιξης. Συγκεκριμένα ο ΠΓΕ χρησιμοποιεί πληθυσμούς από άτομα, επιλέγει τα άτομα σύμφωνα με την καταλληλότητά τους (fitness) και εισάγει νέα σημεία (άτομα, πιθανές λύσεις) στον πληθυσμό χρησιμοποιώντας έναν ή περισσότερους γενετικούς τελεστές. Στόχος αυτής της Μεταπτυχιακής Διπλωματικής Εργασίας ήταν ο σχεδιασμός και η υλοποίηση ενός Ολοκληρωμένου Γραφικού Περιβάλλοντος για τον Προγραμματισμό Γονιδιακής Έκφρασης καθώς και η υλοποίηση ορισμένων καινοτομιών. Στα πλαίσια της διπλωματικής εργασίας, σχεδιάσθηκε και αναπτύχθηκε ένας καινοτόμος τελεστής για την μέθοδο του ΠΓΕ. Ο συγκεκριμένος τελεστής πραγματοποιεί μια τοπική αναζήτηση στις μεταβλητές που χρησιμοποιούνται στη μοντελοποίηση του εκάστοτε προβλήματος και επιλέγει εκείνες τις μεταβλητές για τις οποίες η απόδοση του αλγορίθμου βελτιστοποιείται. Η απόδοση του καινούργιου τελεστή ελέγχθηκε και πειραματικά. Μια επιπλέον καινοτομία που εφαρμόστηκε είναι η αυξομείωση του αριθμού των μεταλλάξεων. Συγκεκριμένα, επιλέγουμε να μειώνουμε τον αριθμό των μεταλλάξεων καθώς ο πληθυσμός εξελίσσεται, ενώ τον αυξάνουμε όταν έχουμε μικρή διαφορά ανάμεσα στη βέλτιστη και τη μέση απόδοση του πληθυσμού. Ο μεταβλητός αριθμός μεταλλάξεων σε συνδυασμό με την ικανότητα της μεθοδολογίας του ΠΓΕ να αποφεύγει τα τοπικά ακρότατα βελτιώνει σημαντικά την προσαρμοστικότητα του αλγορίθμου. Επιπλέον, για την αντιμετώπιση της αυξημένης υπολογιστικής πολυπλοκότητας που παρουσιάζει η μέθοδος, εισήχθη η έννοια του παραλληλισμού. Τέλος, η τροποποιημένη μέθοδος του ΠΓΕ εφαρμόστηκε σε πληθώρα προβλημάτων όπως η μοντελοποίηση συμπεριφοράς μιας χρονοσειράς μαγνητοεγκεφαλογραφήματος, η μοντελοποίηση της συμπεριφοράς κόπωσης υλικών, η πρόβλεψη ισοτιμίας δολαρίου – ευρώ, η πρόβλεψη πρωτεϊνικών αλληλεπιδράσεων και η πρόβλεψη του βαθμού υδατοκορεσμού ελαιοκαλλιεργειών. Τα αποτελέσματα που προέκυψαν είναι ιδιαίτερα ενθαρρυντικά. / Gene Expression Programming (GEP) is one method of automatic generation of programs that belongs to a wider class of Evolutionary Algorithms. Evolutionary Algorithms are inspired by biological mechanisms of evolution. Specifically, GEP uses populations of individuals, select the individuals according to their fitness, and introduce genetic variation using one or more genetic operators. The purpose of this Master's Thesis was to design and implement an Integrated Graphical Environment for Gene Expression Programming and the implementation of certain innovations. Ιn the context of this thesis an innovative operator was designed and developed for the GEP method. This particular operator is conducting a local search on the variables used in modeling of a problem and chooses those variables for which the performance of the algorithm is optimized. The performance of the new operator was experimentally tested. Another innovation implemented was the fluctuation in the number of mutations. Specifically, we choose to reduce the number of mutations as the population evolves, while we increase it when the performance of the best individual found is very close to the average performance of the population. The variable number of mutations in combination with the ability of the methodology of GEP to avoid local extrema significantly improves the adaptability of the algorithm. Moreover, in order to face the increased computational complexity of the method, we introduce parallelism. Finally, the modified method of GEP was applied to many problems such as modeling behavior of a MEG’s time series, modeling of fatigue behavior of materials, forecasting Euro - United States Dollar exchange rate, predicting protein interactions and predicting the degree of saturation of olive crops. The results are very encouraging.

Τα τελευταία χρόνια, αν και η Περιββαλοντική Εκπαίδευση στην προσχολική ηλικία εντάσσεται στην ευέλικτη ζώνη, αποτελεί αναπόσπαστο κομμάτι της εκπαιδευτικής θεματολογίας. Στην παρούσα διπλωματική εργασία σκοπός είναι να διερευνηθεί το κατά πόσο τα παιδιά προσχολικής ηλικίας καταννοούν τις τροφικές σχέσεις που αναπτύσσονται σε ένα οικοσύστημα και συγκεκριμένα στο δέντρο. Ταυτόχρονα, εστιάζουμε στις στάσεις που αναπτύσσουν τα παιδιά ως προς τις ανθρώπινες παρεμβάσεις στο οικοσύστημα. Τέλος, μέσω της διδακτικής παρέμβασης που αποτελείται από 10 δραστηριότητες,επιδιώκουμε να αναπτύξουμε ή και να βελτιώσουμε τις γνώσεις και τις στάσεις που έχουν τα παιδιά σχετικά με τα παραπάνω θέματα. / In recent years, although Environmental Education in early childhood is part of the flexible zone is an integral part of education topics. In this thesis, the goal is to investigate whether preschool children understand food chains that are developed in a specific ecosystem and especially the tree. Simultaneously, we focus on attitudes that children develop towards the human intervention in the ecosystem. Finally, through an instructional intervention that consists of 10 activities, we try to develop or improve their knowledge and attitudes that have children on these issues.

H σύγχρονη μεταναστευτική κίνηση προς στην Ελλάδα αποτελεί μέρος του ευρύτερου φαινομένου της διεθνούς μετανάστευσης. Στο τέλος της δεκαετίας του 1980 παρατηρείται ένα μεγάλο κύμα εισροής και εκροής μεταναστών από και προς τη χώρα. Η παραπάνω κινητικότητα επέφερε αλλαγές και ανακατατάξεις στη δομή της ελληνικής κοινωνίας προβάλλοντας ζητήματα ηθικά, κοινωνικά και πολιτικά όπως είναι το θέμα των ατομικών δικαιωμάτων των μεταναστών, η ανάγκη ανάπτυξης νέων πολιτισμικών ταυτοτήτων, ο ρατσισμός και η βία. Η παρούσα διπλωματική διατριβή αποσκοπεί μέσα από την αποδελτίωση των λογοτεχνικών περιοδικών Διαβάζω, Εντευκτήριο, Η Λέξη, Νέα Εστία, Πλανόδιον και Το Δέντρο (Μάιος 1989 – Μάιος 2009) καθώς και του ειδικού αφιερώματος του τεύχους 35 – 36 του περιοδικού Απόπλους Σαμιακών Γραμμάτων και Τεχνών Περιήγηση να καταγράψει και να συστηματοποιήσει τους τρόπους με τον οποίους η λογοτεχνική κοινότητα αντέδρασε στο φαινόμενο. Πιο συγκεκριμένα στοχεύει να παρουσιάσει τις στάσεις της λογοτεχνίας απέναντι στους μετανάστες καθώς και απέναντι στο λεγόμενο «μεταναστευτικό πρόβλημα». / --

Στο πρόβλημα της ταξινόμησης μιας κλάσης μία από τις κλάσεις, που ονομάζεται target κλάση, πρέπει να διαχωριστεί από όλα τα άλλα πιθανά αντικείμενα. Αυτά θεωρούνται σαν outliers (ή non-targets). Η ανάγκη για τη λύση ενός τέτοιου προβλήματος προκύπτει σε πολλές πρακτικές εφαρμογές, π.χ. στη μηχανική ανίχνευση λάθους, στην αναγνώριση προσώπου, στην επαλήθευση συγγραφικών δικαιωμάτων, στην αναγνώριση απάτης ή στη ταυτοποίηση ατόμου με βάση βιομετρικά δεδομένα. Στη συγκεκριμένη διπλωματική γίνεται ταξινόμηση μιας κλάσης ηλεκτροεγκεφαλικών σημάτων. Με αυτό τον τρόπο επιτυγχάνεται η ανίχνευση ενός πυραύλου μέσα σε δορυφορικές εικόνες, χρησιμοποιώντας τα ηλεκτροεγκεφαλικά σήματα ενός υποκειμένου το οποίο βλέπει δορυφορικές εικόνες σε μια LCD οθόνη. Για να γίνει η ταξινόμηση δημιουργήθηκε ένα σετ target και ένα σετ outlier αντικειμένων(δεδομένα).Τα target αντικείμενα είναι τα τμήματα από τα αρχικά ηλεκτροεγκεφαλικά σήματα τα οποία συνδέονται με την παρατήρηση πυραύλου μέσα σε μία δορυφορική εικόνα από το υποκείμενο, ενώ τα outlier αντικείμενα είναι άλλα τμήματα(ίδιου μεγέθους με τα target) των αρχικών ηλεκτροεγκεφαλικών σημάτων. Tα αντικείμενα μεταφέρονται σε ένα χώρο χαρακτηριστικών λιγότερων διαστάσεων από τον αρχικό τους χώρο, χρησιμοποιώντας τη γραμμική μέθοδο MCA (Minor Component Analysis). Για τη ταξινόμηση μιας κλάσης των αντικειμένων μελετώνται και χρησιμοποιούνται οι ταξινομητές MST_CD (Minimum Spanning Tree Class Descriptor), k-NNDD (k Nearest Neighbors Data Description) και SVDD (Support Vector Domain Description). Η εκπαίδευση των ταξινομητών αυτών γίνεται με ένα μικρό ποσοστό των target αντικειμένων (αντικείμενα εκπαίδευσης). Υπολογίζεται η απόδοση ταξινόμησης για κάθε έναν από αυτούς χρησιμοποιώντας τα υπόλοιπα target αντικείμενα μαζί με τα outlier αντικείμενα. Τέλος συγκρίνονται οι αποδόσεις και εξάγονται τα συμπεράσματα για τις υψηλές τιμές τους. Στο παράρτημα Α φαίνεται ο εκτελέσιμος στο matlab κώδικας με τον οποίο έγιναν όλα τα παραπάνω. Ο κώδικας γράφτηκε αποκλειστικά για τη συγκεκριμένη διπλωματική εργασία. / In the problem of one-class classification one of the classes, called the target class, has to be distinguished from all other possible objects. These are considered as outliers (or non-targets). The need for solving such a task arises in many practical applications, e.g. in fault detection, face recognition, authorship verification, fraud recognition or person identification based on biometric data. In this thesis a one-class classification of EEG (Electroencephalographic) data is being done. By this way, the detection of an air missile is achieved by using the EEG data of a subject, which is watching satellite images in a LCD monitor. For the classification a set of target and a set of outlier objects (data) were created. The target objects are parts of the original EEG data that are event-related with the detection of an air missile in a satellite image by the subject and the outlier objects are other parts (of the same size with target) of the original EEG data. The objects are mapped in a feature space of fewer dimensions than their original space, by using the linear method MCA (Minor Component Analysis). For the one-class classification of the objects, the classifiers that are studied and used are MST_CD (Minimum Spanning Tree Class Descriptor), k-NNDD (k Nearest Neighbors Data Description) and SVDD (Support Vector Domain Description). For the training of these classifiers a small percentage of target objects (training objects) are used. The performance of the classification is calculated for every classifier by using the rest target objects and the outlier objects. Finally the performances are compared and conclusions for their high values are made. In the appendix A there is the executable code in matlab which does all the above. The code created just for the purposes of this thesis.