Στα πλαίσια της διατριβής αναπτύξαμε δύο από τους πρώτους αλγορίθμους υπολογισμού μιας ε-προσεγγιστικής ισορροπίας Nash για την περίπτωση όπου το ε είναι κάποια σταθερά. Οι προσεγγίσεις που επιτυγχάνουν οι αλγόριθμοί μας είναι ε=3/4 και ε=(2+λ)/4 αντίστοιχα, όπου λ είναι το ελάχιστο, μεταξύ όλων των ισορροπιών Nash, κέρδος για έναν παίκτη. Επιπλέον, μελετήσαμε μια ευρεία κλάση τυχαίων παιγνίων δύο παικτών, για την οποία υπολογίσαμε μια πολύ καλή ε-προσεγγιστική ισορροπία Nash, με το ε να τείνει στο 0 καθώς το πλήθος των διαθέσιμων στρατηγικών των παικτών τείνει στο άπειρο. Οι αρχές της θεωρίας παιγνίων είναι χρήσιμες στην ανάλυση της επίδρασης που έχει στην καθολική απόδοση ενός συστήματος διαμοιραζόμενων πόρων η εγωιστική και ανταγωνιστική συμπεριφορά των χρηστών του. Προς την κατεύθυνση αυτή, εστιάσαμε στο πρόβλημα της εξισορρόπησης φορτίου. Μελετήσαμε διάφορα μοντέλα πληροφόρησης (π.χ. όταν όλα τα φορτία είναι άγνωστα ή όταν κάθε παίκτης γνωρίζει το μέγεθος του δικού του φορτίου) και αναλύσαμε για το καθένα το σύνολο και τις ιδιότητες των ισορροπιών Nash. Yπολογίσαμε επίσης φράγματα στο λόγο απόκλισης, ο οποίος εκφράζει την επίδραση που έχει στην απόδοση του συστήματος η εγωιστική συμπεριφορά των χρηστών του. Εκτός από τα υπολογιστικά θέματα που σχετίζονται με τη θεωρία παιγνίων, έχει ενδιαφέρον να μελετηθεί κατά πόσο μπορεί η θεωρία παιγνίων να βοηθήσει στην ανάπτυξη και ανάλυση αλγορίθμων για υπολογιστικά δύσκολα προβλήματα συνδυαστικής βελτιστοποίησης. Προς αυτήν την κατεύθυνση, μελετήσαμε από παιγνιοθεωρητική σκοπιά το πρόβλημα χρωματισμού των κορυφών ενός γραφήματος. Ορίσαμε κατάλληλα το παίγνιο χρωματισμού γραφήματος και αποδείξαμε ότι κάθε παίγνιο χρωματισμού γραφήματος έχει πάντα μια αγνή ισορροπία Nash, και ότι κάθε αγνή ισορροπία Nash αντιστοιχεί σε ορθό χρωματισμό του γραφήματος. Δείξαμε επίσης ότι υπάρχει πάντα μια αγνή ισορροπία Nash που χρησιμοποιεί βέλτιστο αριθμό χρωμάτων, δηλαδή ίσο με το χρωματικό αριθμό του γραφήματος. Επιπλέον, περιγράψαμε και αναλύσαμε έναν πολυωνυμικό αλγόριθμο που υπολογίζει μια αγνή ισορροπία Nash για ένα οποιοδήποτε παίγνιο χρωματισμού γραφήματος και χρησιμοποιεί συνολικά ένα πλήθος χρωμάτων που ικανοποιεί ταυτόχρονα τα περισσότερα κλασικά γνωστά φράγματα στο χρωματικό αριθμό. / We developed two algorithms for computing an e-approximate Nash equilibrium for the case where e is an absolute constant. The approximations achieved by our algorithms are e=3/4 and e=(2+l)/4 respectively, where $\lambda$ is the minimum, among all Nash equilibria, payoff of either player. Furthermore, we studied a wide class of random two player games, for which we showed how to compute an e-approximate Nash equilibrium, where e tends to zero as the number of strategies of the players tends to infinity. Game theoretic concepts are useful in determining the impact that selfish behavior plays on the global performance of a system involving selfish entities. Towards this direction, we focused on the problem of load balancing. We studied the case where the agents are not necessarily fully informed about the exact values of their loads. We focused on several models of information (e.g. when all agents know nothing about the loads, or when each agents knows her own load) and, for each model, we characterized the set of Nash equilibria and analyzed their properties. Moreover, we bounded the coordination ratio, a measure which captures the impact that selfish behavior has to the global performance of the system, in contrast to the performance achieved by an optimum centralized algorithm. Besides the computational issues related to game theory, it is interesting to investigate whether game theory can help us in developing and analyzing algorithms for computationally difficult combinatorial optimization problems. Towards this direction, we studied from a game theoretic point of view the problem of vertex coloring. In particular, we properly defined the graph coloring game and we proved that every graph coloring game has a pure Nash equilibrium, and each pure Nash equilibrium corresponds to a proper coloring of the graph. We also showed that there exists a pure Nash equilibrium that uses an optimum number of colors, i.e. equal to the chromatic number. Furthermore, we developed and analyzed a polynomial time algorithm that computes a pure Nash equilibrium for any graph coloring game, using a number of colors satisfying most of the known classical bounds on the chromatic number.

Στη συγκεκριμένη εργασία ασχολήθηκα με την εκτίμηση της συνάρτησης πυκνότητας πιθανότητας παραμέτρων που προέρχονται από σήματα πηγών ακουστικής εκπομπής που επεξεργάστηκα. Στο θεωρητικό κομμάτι το μεγαλύτερο ενδιαφέρον παρουσίασαν ο Μη Καταστροφικός Έλεγχος και η Ακουστική Εκπομπή, καθώς και οι εφαρμογές τους. Τα δεδομένα που επεξεργάστηκα χωρίζονται σε δύο κατηγορίες: σε εκείνα που μου δόθηκαν έτοιμα και σε εκείνα που λήφθηκαν μετά από μετρήσεις. Στην επεξεργασία των πειραματικών δεδομένων χρησιμοποιήθηκε ο αλγόριθμος πρόβλεψης-μεγιστοποίησης, τον οποίο μελέτησα θεωρητικά και με βάση τον οποίο εξάχθηκαν οι παράμετροι για κάθε σήμα. Έχοντας βρει τις παραμέτρους, προχώρησα στην ταξινόμηση των σημάτων σε κατηγορίες με βάση τη θεωρία της αναγνώρισης προτύπων. Στο τέλος της εργασίας παρατίθεται το παράρτημα με τα αναλυτικά αποτελέσματα, καθώς και η βιβλιογραφία που χρησιμοποίησα. / In this diploma paper the subject was the calculation of the probability density function of parameters which come from signals of sources of acoustic emission. In the theoritical part, the chapters with the greatest interest were Non Destructive Control and Acoustic Emission and their applications. The data which were processed are divided in two categories: those which were given without requiring any laboratory research and those which demanded laboratory research. The expectation-maximization algorithm, which was used in the process of the laboratory data, was the basis for the calculation of the parameters of each signal. Having calculated the parameters, the signals were classified in categories according to the theory of pattern recognition. In the end of the paper, the results and the bibliography which was used are presented.

H παρούσα εργασία , έγινε στα πλαίσια της Διπλωματικής εργασίας, με θέμα : «Aλγοριθμική επίλυση προβλήματος» Στην εργασία επιχειρείται, η κατάθεση εμπειριών, προβληματισμών και προτάσεων σχετικών με την εισαγωγή και αξιοποίηση Logo περιβάλλοντος στη διδακτική πράξη και συγκεκριμένα του Microworlds pro, με σκοπό την ανάδειξη σημαντικών πτυχών της σχεδίασης, ανάπτυξης, εφαρμογής και αξιολόγησης εκπαιδευτικών σεναρίων και δραστηριοτήτων, στο πλαίσιο της αποτελεσματικής ένταξης των εκπαιδευτικών λογισμικών, στη διδακτική της Πληροφορικής. Η διαδικασία που ακολουθεί περιλαμβάνει τρία βήματα: α) δημιουργία κινήτρου, β) οικοδόμηση της γνώσης μέσω της διερεύνησης και συνεργασίας, γ) εφαρμογή-αναδόμηση της γνώσης. Σκοπός των μαθημάτων, που πραγματοποιήθηκαν σε μαθητές της Γ΄ Γυμνασίου, ήταν να αποκτήσουν οι μαθητές ,ευχέρεια στη χρήση συμβολικών μέσων έκφρασης, για την αναπαράσταση της διαδικασίας επίλυσης προβλημάτων, να αναπτύξουν αναλυτική συνθετική σκέψη και να ασκηθούν στα βασικά δομικά στοιχεία και τις έννοιες του προγραμματισμού. Στόχος, δεν ήταν να μάθουν μια γλώσσα προγραμματισμού, αλλά να κατανοήσουν την έννοια του Αλγόριθμου, δηλαδή ,να μπορούν να αναλύσουν ένα απλό πρόβλημα σε ακολουθία σαφώς ορισμένων και πεπερασμένων βημάτων. / The present work , became in the frames of Diplomatic work, on the subject: " Algorithmic resolution of problem " In the work is attempted, the deposit of experiences, reflections and proposals relative with the import and exploitation Reason of environment in the instructive practice and concretely the Microworlds prο, aiming at the appointment of important aspects of designing, growth, application and evaluation of educational scripts and activities, in the frame of effective integration of educational softwares, in the didactics of Information technology. The process that follows includes three steps: a) creation of motive, v) construction of knowledge via the investigation and collaboration, c) application of knowledge. Aim of courses, that were realised in students of c class, of High school, was acquires the students, occasion in the use of symbolic means of expression, for the representation of process of resolution of problems, to develop analytic synthetic thought and to practise itself in the basic structural elements and the significances of planning. Objective, was not they learn a language of planning, but they comprehend the significance of Algorithm, that is to say, they can analyze a simple problem in sequence of course certain and finite steps.

Τα τελευταία χρόνια χαρακτηρίζονται από μια αλματώδη ανάπτυξη των προϊόντων και υπηρεσιών που βασίζονται στα δίκτυα ασύρματης επικοινωνίας, ενώ προκύπτουν σημαντικές ερευνητικές προκλήσεις. Τα συστήματα πολλαπλών κεραιών στον πομπό και στο δέκτη, γνωστά και ως συστήματα MIMO (multi-input multi-output), καθώς και η τεχνολογία πολλαπλής προσπέλασης με χρήση κωδικών (code division multiple access, CDMA) αποτελούν δύο από τα βασικά μέτωπα ανάπτυξης των ασύρματων τηλεπικοινωνιών. Στα πλαίσια της παρούσας διδακτορικής διατριβής, ασχοληθήκαμε με την ανάπτυξη και μελέτη αλγορίθμων επεξεργασίας σήματος για τα δύο παραπάνω συστήματα, όπως περιγράφεται αναλυτικά παρακάτω. Σχετικά με τα συστήματα MIMO, η πρωτοποριακή έρευνα που πραγματοποιήθηκε στα Bell Labs γύρω στα 1996, όπου αναπτύχθηκε η αρχιτεκτονική BLAST (Bell Labs Layered Space-Time), απέδειξε ότι η χρήση πολλαπλών κεραιών μπορεί να οδηγήσει σε σημαντική αύξηση της χωρητικότητας των ασύρματων συστημάτων. Προκειμένου να αξιοποιηθούν οι παραπάνω δυνατότητες, απαιτείται η σχεδίαση σύνθετων δεκτών MIMO. Προς αυτήν την κατεύθυνση, έχει προταθεί ένας μεγάλος αριθμός μεθόδων ισοστάθμισης του καναλιού. Ωστόσο, οι περισσότερες από αυτές υποθέτουν ότι το ασύρματο κανάλι είναι: 1) χρονικά σταθερό, 2) συχνοτικά επίπεδο (δεν εισάγει διασυμβολική παρεμβολή), και κυρίως 3) ότι είναι γνωστό στο δέκτη. Δεδομένου ότι σε ευρυζωνικά συστήματα μονής φέρουσας οι παραπάνω υποθέσεις είναι δύσκολο να ικανοποιηθούν, στραφήκαμε προς τις προσαρμοστικές μεθόδους ισοστάθμισης. Συγκεκριμένα, αναπτύξαμε τρεις βασικούς αλγορίθμους. Ο πρώτος αλγόριθμος αποτελεί έναν προσαρμοστικό ισοσταθμιστή ανάδρασης αποφάσεων (decision feedback equalizer, DFE) για συχνοτικά επίπεδα κανάλια ΜΙΜΟ. Ο προτεινόμενος MIMO DFE ακολουθεί την αρχιτεκτονική BLAST, και ανανεώνεται με βάση τον αλγόριθμο αναδρομικών ελαχίστων τετραγώνων (RLS) τετραγωνικής ρίζας. Ο ισοσταθμιστής μπορεί να παρακολουθήσει ένα χρονικά μεταβαλλόμενο κανάλι, και, από όσο γνωρίζουμε, έχει τη χαμηλότερη πολυπλοκότητα από όλους τους δέκτες BLAST που έχουν προταθεί έως σήμερα. Ο δεύτερος αλγόριθμος αποτελεί την επέκταση του προηγούμενου σε συχνοτικά επιλεκτικά κανάλια. Μέσω κατάλληλης μοντελοποίησης του προβλήματος ισοστάθμισης, οδηγηθήκαμε σε έναν αποδοτικό DFE για ευρυζωνικά κανάλια MIMO. Τότε, η διαδικασία της ισοστάθμισης εμφανίζει προβλήματα αριθμητικής ευστάθειας, που λόγω της υλοποίησης RLS τετραγωνικής ρίζας αντιμετωπίστηκαν επιτυχώς. Κινούμενοι προς την κατεύθυνση περαιτέρω μείωσης της πολυπλοκότητας, προτείναμε έναν προσαρμοστικό MIMO DFE που ανανεώνεται με βάση τον αλγόριθμο ελαχίστων μέσων τετραγώνων (LMS) υλοποιημένο εξ ολοκλήρου στο πεδίο της συχνότητας. Με χρήση του ταχύ μετασχηματισμού Fourier (FFT), μειώνεται η απαιτούμενη πολυπλοκότητα. Παράλληλα, η μετάβαση στο πεδίο των συχνοτήτων έχει ως αποτέλεσμα την προσεγγιστική διαγωνοποίηση του συστήματος, προσφέροντας ανεξάρτητη ανανέωση των φίλτρων ανά συχνοτική συνιστώσα και επιτάχυνση της σύγκλισης του αλγορίθμου. Ο προτεινόμενος ισοσταθμιστής πετυχαίνει μια καλή ανταλλαγή μεταξύ απόδοσης και πολυπλοκότητας. Παράλληλα με τα παραπάνω, ασχοληθήκαμε με την εκτίμηση του ασύρματου καναλιού σε ένα ασύγχρονο σύστημα CDMA. Το βασικό σενάριο είναι ότι ο σταθμός βάσης γνωρίζει ήδη τους ενεργούς χρήστες, και καλείται να εκτιμήσει τις παραμέτρους του καναλιού ανερχόμενης ζεύξης ενός νέου χρήστη που εισέρχεται στο σύστημα. Το πρόβλημα περιγράφεται από μια συνάρτηση ελαχίστων τετραγώνων, η οποία είναι γραμμική ως προς τα κέρδη του καναλιού, και μη γραμμική ως προς τις καθυστερήσεις του. Αποδείξαμε ότι το πρόβλημα έχει μια προσεγγιστικά διαχωρίσιμη μορφή, και προτείναμε μια επαναληπτική μέθοδο υπολογισμού των παραμέτρων. Ο προτεινόμενος αλγόριθμος δεν απαιτεί κάποια ειδική ακολουθία διάχυσης και λειτουργεί αποδοτικά ακόμη και για περιορισμένη ακολουθία εκπαίδευσης. Είναι εύρωστος στην παρεμβολή πολλαπλών χρηστών και περισσότερο ακριβής από μια υπάρχουσα μέθοδο εις βάρος μιας ασήμαντης αύξησης στην υπολογιστική πολυπλοκότητα. / Over the last decades, a dramatic progress in the products and services based on wireless communication networks has been observed, while, at the same time, new research challenges arise. The systems employing multiple antennas at the transmitter and the receiver, known as MIMO (multi-input multi-output) systems, as well as code division multiple access (CDMA) systems, are two of the main technologies employed for the evolution of wireless communications. During this PhD thesis, we worked on the design and analysis of signal processing algorithms for the two above systems, as it is described in detail next. Concerning the MIMO systems, the pioneering work performed at Bell Labs around 1996, where the BLAST (Bell Labs Layered Space-Time) architecture has been developed, proved that by using multiple antennas can lead to a significant increase in wireless systems capacity. To exploit this potential, sophisticated MIMO receivers should be designed. To this end, a large amount of channel equalizers has been proposed. However, most of these methods assume that the wireless channel is: 1) static, 2) frequency flat (no intersymbol interference is introduced), and mainly 3) it is perfectly known at the receiver. Provided that in high rate single carrier systems these assumptions are difficult to be met, we focused our attention on adaptive equalization methods. More specifically, three basic algorithms have been developed. The first algorithm is an adaptive decision feedback equalizer (DFE) for frequency flat MIMO channels. The proposed MIMO DFE implements the BLAST architecture, and it is updated by the recursive least squares (RLS) algorithm in its square root form. The new equalizer can track time varying channels, and, to the best of our knowledge, it has the lowest computational complexity among the BLAST receivers that have been proposed up to now. The second algorithm is an extension of the previous one to the frequency selective channel case. By proper modeling of the equalization problem, we arrived at an efficient DFE for wideband MIMO channels. In this case, the equalization process encounters numerical instability problems, which were successfully treated by the square root RLS implementation employed. To further reduce complexity, we proposed an adaptive MIMO DFE that is updated by the least mean square (LMS) algorithm, fully implemented in the frequency domain. By using the fast Fourier transform (FFT), the complexity required is considerably reduced. Moreover, the frequency domain implementation leads to an approximate decoupling of the equalization problem at each frequency bin. Thus, an independent update of the filters at each frequency bin allows for a faster convergence of the algorithm. The proposed equalizer offers a good performance - complexity tradeoff. Furthermore, we worked on channel estimation for an asynchronous CDMA system. The assumed scenario is that the base station has already acquired all the active users, while the uplink channel parameters of a new user entering the system should be estimated. The problem can be described via a least squares cost function, which is linear with respect to the channel gains, and non linear to its delays. We proved that the problem is approximately decoupled, and a new iterative parameter estimation method has been proposed. The suggested method does not require any specific pilot sequence and performs well even for a short training interval. It is robust to multiple access interference and more accurate compared to an existing method, at the expense of an insignificant increase in computational complexity.

Η παρούσα διατριβή εισάγει μεθόδους για τον αυτόματο τεμαχισμό σημάτων ομιλίας. Συγκεκριμένα παρουσιάζονται τέσσερις νέες μέθοδοι για τον αυτόματο τεμαχισμό σημάτων ομιλίας, τόσο για γλωσσολογικά περιορισμένα όσο και μη προβλήματα. Η πρώτη μέθοδος κάνει χρήση των σημείων του σήματος που αντιστοιχούν στα ανοίγματα των φωνητικών χορδών κατά την διάρκεια της ομιλίας για να εξάγει όρια ψευδό-φωνημάτων με χρήση του αλγορίθμου δυναμικής παραμόρφωσης χρόνου. Η δεύτερη τεχνική εισάγει μια καινοτόμα υβριδική μέθοδο εκπαίδευσης κρυμμένων μοντέλων Μαρκώφ, η οποία τα καθιστά πιο αποτελεσματικά στον τεμαχισμό της ομιλίας. Η τρίτη μέθοδος χρησιμοποιεί αλγορίθμους μαθηματικής παλινδρόμησης για τον συνδυασμό ανεξαρτήτων μηχανών τεμαχισμού ομιλίας. Η τέταρτη μέθοδος εισάγει μια επέκταση του αλγορίθμου Βιτέρμπι με χρήση πολλαπλών παραμετρικών τεχνικών για τον τεμαχισμό της ομιλίας. Τέλος, οι προτεινόμενες μέθοδοι τεμαχισμού χρησιμοποιούνται για την βελτίωση συστημάτων στο πρόβλημα της σύνθεσης ομιλίας, αναγνώρισης ομιλίας και αναγνώρισης γλώσσας. / The present dissertation introduces methods for the automatic segmentation of speech signals. In detail, four new segmentation methods are presented both in for the cases of linguistically constrained or not segmentation. The first method uses pitchmark points to extract pseudo-phonetic boundaries using dynamic time warping algorithm. The second technique introduces a new hybrid method for the training of hidden Markov models, which makes them more effective in the speech segmentation task. The third method uses regression algorithms for the fusion of independent segmentation engines. The fourth method is an extension of the Viterbi algorithm using multiple speech parameterization techniques for segmentation. Finally, the proposed methods are used to improve systems in the task of speech synthesis, speech recognition and language recognition.

Η ραγδαία εξάπλωση του Internet έχει προκαλέσει σημαντικές αλλαγές σε πολλούς κλάδους της οικονομίας και της κοινωνίας παγκόσμια. Με τη ραγδαία ανάπτυξη των Τεχνολογιών της Πληροφορικής και της Τεχνολογίας, μια νέα μορφή εκπαίδευσης εμφανίστηκε, που δεν είναι άλλη από το e-learning (εκπαίδευση από απόσταση), που έφερε την επανάσταση στο εκπαιδευτικό γίγνεσθαι. Επιπρόσθετα ο Παγκόσμιος Ιστός σταδιακά μετεξελίσσεται στο Σημασιολογικό Παγκόσμιο Ιστό (Semantic Web) νέα μοντέλα και πρότυπα (XML, RDF, OWL) αναπτύσσονται για την προώθηση αυτής της διαδικασίας. Η έκφραση, μετάδοση και αναζήτηση πληροφοριών με χρήση αυτών των προτύπων ανοίγει νέους ορίζοντες στη χρήση του Διαδικτύου. Οι οντολογίες κερδίζουν ολοένα έδαφος για την αναπαράσταση γνώσης. Σε μια μεγάλη οντολογία που περιέχει χρήσιμα δεδομένα για ένα σύστημα εξ’ αποστάσεως εκπαίδευσης, αξίζει κάποιος να ερευνήσει την «κρυμμένη γνώση», δηλαδή να ανακαλύψει πιθανές συσχετίσεις ή συνειρμούς, να βρει πρότυπα ή μορφές που επαναλαμβάνονται ή ακραία φαινόμενα. Η παρούσα διπλωματική εργασία αποτελεί μια επίδειξη τεχνολογίας για την έγκυρη και έγκαιρη πρόβλεψη της απόδοσης των φοιτητών σε ένα σύστημα εξ’ αποστάσεως εκπαίδευσης. Η βασική ιδέα προκύπτει από την ανάγκη να σχεδιαστεί μία οντολογία η οποία θα μπορεί να αποθηκεύσει τη γνώση σχετικά με τις ικανότητες φοιτητών (user profile) σε σχέση με ένα συγκεκριμένο εκπαιδευτικό αντικείμενο (ΠΛΗ23 – Τηλεματική, Διαδίκτυο του Ελληνικού Ανοικτού Πανεπιστημίου (ΕΑΠ) )η οποία έχει πολύ συγκεκριμένη ύλη και 4 υποχρεωτικές γραπτές εργασίες ανά έτος). Στη συνέχεια παρουσιάζονται τα αποτελέσματα μελέτης της ανάλυσης των δεδομένων των φοιτητών με τεχνικές εξόρυξης γνώσης. Η εύρεση των κανόνων πραγματοποιήθηκε μέσω του εργαλείου Weka. Το αποτέλεσμα που προέκυψε είναι μία βάση γνώσης βάσει της οποίας γίνεται έγκαιρα και έγκυρα η πρόβλεψη της συμπεριφοράς του φοιτητή, δηλαδή αν θα καταφέρει να ολοκληρώσει επιτυχώς ή μη τη Θεματική Ενότητα που έχει αναλάβει στο ΕΑΠ, ώστε ο διδάσκων να μπορεί από πολύ νωρίς να υποστηρίξει το φοιτητή με επιπλέον υλικό αν απαιτείται. / The rapid spread of Internet has caused significant changes in many sectors of the economy and society worldwide. From those changes could not be left out of education. With the rapid development of information technologies and technology, a new form of education appears, e-learning (distance education), which revolutionized the educational process. Furthermore, while the World Wide Web gradually transforms into Semantic Web, new standards and models (XML, RDF, OWL) are evolving in order to launch this inquiry. The storage, presentation, transmission and search of information according to those standards open up new horizons in the utilization of the Web. Ontologies are increasingly get used for knowledge representation. A large ontology contains useful data for a system of distance education, deserves someone to investigate the "hidden knowledge", i.e. to discover possible associations or to find patterns or forms that are repeated or extreme events. This thesis is a demonstration of technology for accurate and timely prediction of the performance of students in a system of distance education. The basic idea was to design an ontology that can store knowledge about the students’ skills (user profile) in relation to a specific educational purpose (PLI23 - Telematics, Internet of the Hellenic Open University, which has a very specific matter and 4 mandatory projects per year). Then we present the results of a study analyzing student data mining techniques (data mining-classification). The discovery rules took place via the tool Weka. The result is a knowledge base which is the appropriate tool (Interface teacher) may provide that a student needs on a particular topic (in addition to material help from the teacher), etc.

Η παρούσα διδακτορική διατριβή πραγματεύεται το θέμα της εκπαίδευσης εμπρόσθιων τροφοδοτούμενων τεχνητών νευρωνικών δικτύων και τις εφαρμογές τους. Η παρουσίαση των θεμάτων και των αποτελεσμάτων της διατριβής οργανώνεται ως εξής: Στο Κεφάλαιο 1 παρουσιάζονται τα τεχνητά νευρωνικά δίκτυα , τα οφέλη της χρήσης τους, η δομή και η λειτουργία τους. Πιο συγκεκριμένα, παρουσιάζεται πως από τους βιολογικούς νευρώνες μοντελοποιούνται οι τεχνητοί νευρώνες, που αποτελούν το θεμελιώδες στοιχείο των τεχνητών νευρωνικών δικτύων. Στη συνέχεια αναφέρονται οι βασικές αρχιτεκτονικές των εμπρόσθιων τροφοδοτούμενων τεχνητών νευρωνικών δικτύων. Το κεφάλαιο ολοκληρώνεται με μια ιστορική αναδρομή για τα τεχνητά νευρωνικά δίκτυα και με την παρουσίαση κάποιων εφαρμογών τους. Στο Κεφάλαιο 2 παρουσιάζονται μερικοί από τους υπάρχοντες αλγορίθμους εκπαίδευσης τεχνητών νευρωνικών δικτύων. Γίνεται μια περιληπτική αναφορά του προβλήματος της εκπαίδευσης των τεχνητών νευρωνικών δικτύων με επίβλεψη και δίνεται η μαθηματική μοντελοποίηση που αντιστοιχεί στην ελαχιστοποίηση του κόστους. Στην συνέχεια γίνεται μια περιληπτική αναφορά στις μεθόδους που βασίζονται στην κατεύθυνση της πιο απότομης καθόδου, στις μεθόδους δευτέρας τάξεως όπου απαιτείται ο υπολογισμός του Εσσιανού πίνακα της συνάρτησης κόστους, στις μεθόδους μεταβλητής μετρικής, και στις μεθόδους συζυγών κλίσεων. Κατόπιν, παρουσιάζεται ο χώρος των βαρών, η επιφάνεια σφάλματος και οι διάφορες τεχνικές αρχικοποίησης των βαρών των τεχνητών νευρωνικών δικτύων και περιγράφονται οι επιπτώσεις που έχουν στην εκπαίδευση τους. Στο Κεφάλαιο 3 παρουσιάζεται ένας νέος αλγόριθμος εκπαίδευσης τεχνητών νευρωνικών δικτύων βασισμένος στον αλγόριθμο της οπισθοδιάδοσης του σφάλματος και στην αυτόματη προσαρμογή του ρυθμού εκπαίδευσης χρησιμοποιώντας πληροφορία δυο σημείων. Η κατεύθυνση αναζήτησης του νέου αλγορίθμου είναι η κατεύθυνση της πιο απότομης καθόδου, αλλά για τον προσδιορισμό του ρυθμού εκπαίδευσης χρησιμοποιούνται προσεγγίσεις δυο σημείων της εξίσωσης χορδής των μεθόδων ψεύδο-Newton. Επιπλέον, παράγεται ένας νέος ρυθμός εκπαίδευσης προσεγγίζοντας την νέα εξίσωση χορδής, που προτάθηκε από τον Zhang, η οποία χρησιμοποιεί πληροφορία παραγώγων και συναρτησιακών τιμών. Στη συνέχεια, ένας κατάλληλος μηχανισμός επιλογής του ρυθμού εκπαίδευσης ενσωματώνεται στον αλγόριθμο εκπαίδευσης ώστε να επιλέγεται κάθε φορά ο κατάλληλος ρυθμός εκπαίδευσης. Τέλος, γίνεται μελέτη της σύγκλισης του αλγορίθμου εκπαίδευσης και παρουσιάζονται τα πειραματικά αποτελέσματα για διάφορα προβλήματα εκπαίδευσης. Στο Κεφάλαιο 4 παρουσιάζονται μερικοί αποτελεσματικοί αλγόριθμοι εκπαίδευσης οι οποίοι βασίζονται στις μεθόδους βελτιστοποίησης συζυγών κλίσεων. Στους υπάρχοντες αλγόριθμους εκπαίδευσης συζυγών κλίσεων προστίθεται ένας αλγόριθμος εκπαίδευσης που βασίζεται στη μέθοδο συζυγών κλίσεων του Perry. Επιπρόσθετα, προτείνονται νέοι αλγόριθμοι συζυγών κλίσεων που προκύπτουν από τις ίδιες αρχές που προέρχονται οι γνωστοί αλγόριθμοι συζυγών κλίσεων των Hestenes-Stiefel, Fletcher-Reeves, Polak-Ribiere και Perry, και ονομάζονται κλιμακωτοί αλγόριθμοι συζυγών κλίσεων. Αυτή η κατηγορία αλγορίθμων βασίζεται στην φασματική παράμετρο κλιμάκωσης του προτάθηκε από τους Barzilai και Borwein. Επιπλέον, ενσωματώνεται στους αλγόριθμους εκπαίδευσης συζυγών κλίσεων μια αποδοτική τεχνική γραμμικής αναζήτησης, που βασίζεται στις συνθήκες του Wolfe και στην διασφαλισμένη κυβική παρεμβολή. Ακόμη, η παράμετρος του αρχικού ρυθμού εκπαίδευσης προσαρμόζεται αυτόματα σε κάθε επανάληψη σύμφωνα με ένα κλειστό τύπο. Στη συνέχεια, εφαρμόζεται μια αποτελεσματική διαδικασία επανεκκίνησης, έτσι ώστε να βελτιωθούν περαιτέρω οι αλγόριθμοι εκπαίδευσης συζυγών κλίσεων και να αποδειχθεί η ολική τους σύγκλιση. Τέλος, παρουσιάζονται τα πειραματικά αποτελέσματα για διάφορα προβλήματα εκπαίδευσης. Στο τελευταίο Κεφάλαιο της παρούσας διδακτορικής διατριβής, απομονώνεται και τροποποιείται ο κλιμακωτός αλγόριθμος του Perry, που παρουσιάστηκε στο προηγούμενο κεφάλαιο. Πιο συγκεκριμένα, ενώ διατηρούνται τα κύρια χαρακτηριστικά του αλγορίθμου εκπαίδευσης, εφαρμόζεται μια διαφορετική τεχνική γραμμικής αναζήτησης η οποία βασίζεται στις μη μονότονες συνθήκες του Wolfe. Επίσης προτείνεται ένας νέος αρχικός ρυθμός εκπαίδευσης για χρήση με τον κλιμακωτό αλγόριθμο εκπαίδευσης συζυγών κλίσεων, ο οποίος φαίνεται να είναι αποδοτικότερος από τον αρχικό ρυθμό εκπαίδευσης που προτάθηκε από τον Shanno όταν χρησιμοποιείται σε συνδυασμό με την μη μονότονη τεχνική γραμμικής αναζήτησης. Στη συνέχεια παρουσιάζονται τα πειραματικά αποτελέσματα για διάφορα προβλήματα εκπαίδευσης. Τέλος, ως εφαρμογή εκπαιδεύεται ένα πολυεπίπεδο εμπρόσθια τροφοδοτούμενο τεχνητό νευρωνικό δίκτυο με τον προτεινόμενο αλγόριθμο για το πρόβλημα της ταξινόμησης καρκινικών κυττάρων του εγκεφάλου και συγκρίνεται η απόδοση του με την απόδοση ενός πιθανοτικού τεχνητού νευρωνικού δικτύου. Η διατριβή ολοκληρώνεται με το Παράρτημα Α’, όπου παρουσιάζονται τα προβλήματα εκπαίδευσης τεχνητών νευρωνικών δικτύων που χρησιμοποιήθηκαν για την αξιολόγηση των προτεινόμενων αλγορίθμων εκπαίδευσης. / In this dissertation the problem of the training of feedforward artificial neural networks and its applications are considered. The presentation of the topics and the results are organized as follows: In the first chapter, the artificial neural networks are introduced. Initially, the benefits of the use of artificial neural networks are presented. In the sequence, the structure and their functionality are presented. More specifically, the derivation of the artificial neurons from the biological ones is presented followed by the presentation of the architecture of the feedforward neural networks. The historical notes and the use of neural networks in real world problems are concluding the first chapter. In Chapter 2, the existing training algorithms for the feedforward neural networks are considered. First, a summary of the training problem and its mathematical formulation, that corresponds to the uncostrained minimization of a cost function, are given. In the sequence, training algorithms based on the steepest descent, Newton, variable metric and conjugate gradient methods are presented. Furthermore, the weight space, the error surface and the techniques of the initialization of the weights are described. Their influence in the training procedure is discussed. In Chapter 3, a new training algorithm for feedforward neural networks based on the backpropagation algorithm and the automatic two-point step size (learning rate) is presented. The algorithm uses the steepest descent search direction while the learning rate parameter is calculated by minimizing the standard secant equation. Furthermore, a new learning rate parameter is derived by minimizing the modified secant equation introduced by Zhang, that uses both gradient and function value information. In the sequece a switching mechanism is incorporated into the algorithm so that the appropriate stepsize to be chosen according to the status of the current iterative point. Finaly, the global convergence of the proposed algorithm is studied and the results of some numerical experiments are presented. In Chapter 4, some efficient training algorithms, based on conjugate gradient optimization methods, are presented. In addition to the existing conjugate gradient training algorithms, we introduce Perry's conjugate gradient method as a training algorithm. Furthermore, a new class of conjugate gradient methods is proposed, called self-scaled conjugate gradient methods, which are derived from the principles of Hestenes-Stiefel, Fletcher-Reeves, Polak-Ribiere and Perry's method. This class is based on the spectral scaling parameter. Furthermore, we incorporate to the conjugate gradient training algorithms an efficient line search technique based on the Wolfe conditions and on safeguarded cubic interpolation. In addition, the initial learning rate parameter, fed to the line search technique, was automatically adapted at each iteration by a closed formula. Finally, an efficient restarting procedure was employed in order to further improve the effectiveness of the conjugate gradient training algorithms and prove their global convergence. Experimental results show that, in general, the new class of methods can perform better with a much lower computational cost and better success performance. In the last chapter of this dissertation, the Perry's self-scaled conjugate gradient training algorithm that was presented in the previous chapter was isolated and modified. More specifically, the main characteristics of the training algorithm were maintained but in this case a different line search strategy based on the nonmonotone Wolfe conditions was utilized. Furthermore, a new initial learning rate parameter was introduced for use in conjunction with the self-scaled conjugate gradient training algorithm that seems to be more effective from the initial learning rate parameter, proposed by Shanno, when used with the nonmonotone line search technique. In the sequence the experimental results for differrent training problems are presented. Finally, a feedforward neural network with the proposed algorithm for the problem of brain astrocytomas grading was trained and compared the results with those achieved by a probabilistic neural network. The dissertation is concluded with the Appendix A', where the training problems used for the evaluation of the proposed training algorithms are presented.

Ο στόχος αυτής της εργασίας ήταν η αναγνώριση έξι βασικών κινήσεων του χεριού με χρήση δύο συστημάτων. Όντας θέμα διεπιστημονικού επιπέδου έγινε μελέτη της ανατομίας των μυών του πήχη, των βιοσημάτων, της μεθόδου της ηλεκτρομυογραφίας (ΗΜΓ) και μεθόδων αναγνώρισης προτύπων. Παράλληλα, το σήμα περιείχε αρκετό θόρυβο και έπρεπε να αναλυθεί, με χρήση του EMD, να εξαχθούν χαρακτηριστικά αλλά και να μειωθεί η διαστασιμότητά τους, με χρήση των RELIEF και PCA, για βελτίωση του ποσοστού επιτυχίας ταξινόμησης. Στο πρώτο μέρος γίνεται χρήση συστήματος ΗΜΓ της Delsys αρχικά σε ένα άτομο και στη συνέχεια σε έξι άτομα με το κατά μέσο όρο επιτυχημένης ταξινόμησης, για τις έξι αυτές κινήσεις, να αγγίζει ποσοστά άνω του 80%. Το δεύτερο μέρος περιλαμβάνει την κατασκευή αυτόνομου συστήματος ΗΜΓ με χρήση του Arduino μικροελεγκτή, αισθητήρων ΗΜΓ και ηλεκτροδίων, τα οποία είναι τοποθετημένα σε ένα ελαστικό γάντι. Τα αποτελέσματα ταξινόμησης σε αυτή την περίπτωση αγγίζουν το 75%. / The aim of this work was to identify six basic movements of the hand using two systems. Being an interdisciplinary topic, there has been conducted studying in the anatomy of forearm muscles, biosignals, the method of electromyography (EMG) and methods of pattern recognition. Moreover, the signal contained enough noise and had to be analyzed, using EMD, to extract features and to reduce its dimensionality, using RELIEF and PCA, to improve the success rate of classification. The first part uses an EMG system of Delsys initially for an individual and then for six people with the average successful classification, for these six movements at rates of over 80%. The second part involves the construction of an autonomous system EMG using an Arduino microcontroller, EMG sensors and electrodes, which are arranged in an elastic glove. Classification results in this case reached 75% of success.

Στη παρούσα διπλωματική εργασία ασχολούμαστε με την αποδοτική επίλυση ταινιακών και γενικών, αραιών γραμμικών συστημάτων σε παράλληλες αρχιτεκτονικές μέσω της οικογένειας αλγορίθμων Spike. Ζητούμενο είναι η βελτίωση (μείωση) του χρόνου επίλυσης μέσω τεχνικών επίλυσης γραμμικών συστημάτων με πολλά δεξιά μέλη. Πιο συγκεκριμένα, επικεντρωνόμαστε στην επίλυση της εξίσωσης μητρώου $AX=F$ (1) όπου $A\in \mathbb{R}^{n\times n}$ είναι το μητρώο συντελεστών και το οποίο είναι αραιό ή/και ταινιακό, $F\in \mathbb{R}^{n\times s}$ είναι ένα μητρώο με $s$ στήλες το οποίο ονομάζεται μητρώο δεξιών μελών και $X\in \mathbb{R}^{n\times s}$ είναι η λύση του συστήματος. Μια σημαντική μέθοδος για την παράλληλη επίλυση της παραπάνω εξίσωσης, είναι η μέθοδος Spike και οι παραλλαγές της. Η μέθοδος Spike βασίζεται στη τεχνική διαίρει και βασίλευε και αποτελείται από δυο φάσεις: α) επίλυση ανεξάρτητων υπο-προβλημάτων τοπικά σε κάθε επεξεργαστή, και β) επίλυση ενός πολύ μικρότερου προβλήματος το οποίο απαιτεί επικοινωνία μεταξύ των επεξεργαστών. Οι δύο φάσεις συνδυάζονται ώστε να παραχθεί η τελική λύση $X$. Η συνεισφορά της διπλωματικής εργασίας έγκειται στην επιτάχυνση της οικογένειας αλγορίθμων Spike για την επίλυση της εξίσωσης (1) μέσω της μελέτης, το σχεδιασμό και την υλοποίηση νέων, περισσότερο αποδοτικών αλγοριθμικών σχημάτων τα οποία βασίζονται σε τεχνικές επίλυσης γραμμικών συστημάτων με πολλά δεξιά μέλη. Αυτά τα νέα αλγοριθμικά σχήματα έχουν ως στόχο τη βελτίωση του χρόνου επίλυσης των γραμμικών συστημάτων καθώς και άλλα οφέλη όπως η αποδοτικότερη χρήση μνήμης. / In this thesis we focus on the efficient solution of general banded and general sparse linear systems on parallel architectures by exploiting the Spike family of algorithms. The equation of interest can be written in matrix form as $ AX = F $ (1) where $ A \ in \ mathbb {R} ^ {n \ times n} $ is the coefficient matrix, which is also sparse and / or banded, $ F \ in \ mathbb {R} ^ {n \ times s} $ is a matrix with $ s $ columns called matrix of the right hand sides and $ X \ in \ mathbb {R} ^ {n \ times s} $ is the solution of the system. An important method for the parallel solution of the above equation, is the Spike method and its variants. The Spike method is based on the divide and conquer technique and consists of two phases: a) solution of local, independent sub-problems in each processor, and b) solution of a much smaller problem which requires communication among the processors. The two phases are combined to produce the final solution $ X $. The contribution of this thesis is the acceleration of the Spike method for the solution of the matrix equation in (1) by studying, designing and implementing new, more efficient algorithmic schemes which are based on techniques used for the effective solution of linear systems with multiple right hand sides. These new algorithmic schemes were designed to improve the solving time of the linear systems as well as to provide other benefits such as more efficient use of memory.

Η τεχνολογία των DNA μικροσυστοιχιών είναι μια υψηλής απόδοσης τεχνική που καθορίζει το κατά πόσο ένα κύτταρο μπορεί να ελέγξει, ταυτόχρονα, την έκφραση ενός πολύ μεγάλου αριθμού γονιδίων. Οι DNA μικροσυστοιχίες χρησιμοποιούνται για την παρακολούθηση και τον έλεγχο των αλλαγών που υφίστανται τα επίπεδα της γονιδιακής έκφρασης λόγω περιβαλλοντικών συνθηκών ή των αλλαγών που λαμβάνουν χώρα σε ασθενή κύτταρα σε σχέση με τα υγιή, χρησιμοποιώντας εξελιγμένες μεθόδους επεξεργασίας πληροφοριών. Εξαιτίας του τρόπου με τον οποίον παράγονται οι μικροσυστοιχίες, κατά την πειραματική επεξεργασία τους, εμφανίζεται ένας μεγάλος αριθμός διαδικασιών που εισάγουν σφάλματα, γεγονός που αναπόφευκτα οδηγεί στην δημιουργία υψηλού επιπέδου θορύβου και σε κατασκευαστικά προβλήματα στα προκύπτοντα δεδομένα. Κατά την διάρκεια των τελευταίων δεκαπέντε ετών, έχουν προταθεί από αρκετούς ερευνητές, πολλές και ικανές μέθοδοι που δίνουν λύσεις στο πρόβλημα της ενίσχυσης και της βελτίωσης των εικόνων μικροσυστοιχίας. Παρά το γεγονός της ευρείας ενασχόλησης των ερευνητών με τις μεθόδους επεξεργασίας των εικόνων μικροσυστοιχίας, η διαδικασία βελτίωσης τους αποτελεί ακόμη, ένα θέμα που προκαλεί ενδιαφέρον καθώς η ανάγκη για καλύτερα αποτελέσματα δεν έχει μειωθεί. Στόχος της διδακτορικής διατριβής είναι να συνεισφέρει σημαντικά στην προσπάθεια βελτίωσης των αποτελεσμάτων προτείνοντας μεθόδους ψηφιακής επεξεργασίας εικόνας που επιφέρουν βελτίωση της ποιότητας των εικόνων μέσω της μείωσης των συνιστωσών του θορύβου και της τεμαχιοποίησης της εικόνας. Πιο συγκεκριμένα, στα πλαίσια εκπόνησης της διατριβής παρουσιάζεται μια νέα αυτόματη μέθοδος εντοπισμού της θέσης των υπομικροσυστοιχιών σκοπός της οποίας είναι να καλυφθεί εν μέρει το κενό που υπάρχει στην βιβλιογραφία των μικροσυστοιχιών για το βήμα της προεπεξεργασίας που αφορά στην αυτόματη εύρεση της θέσης των υπομικροσυστοιχιών σε μια μικροσυστοιχία. Το βήμα αυτό της προεπεξεργασίας, σπανίως, λαμβάνεται υπόψιν καθώς στις περισσότερες εργασίες σχετικές με τις μικροσυστοιχίες, γίνεται μια αυθαίρετη υπόθεση ότι οι υπομικροσυστοιχίες έχουν με κάποιον τρόπο ήδη εντοπιστεί. Στα πραγματικά συστήματα αυτόματης ανάλυσης της εικόνας μικροσυστοιχίας, την αρχική εκτίμηση της θέσης των υπομικροσυστοιχιών, συνήθως, ακολουθεί η διόρθωση που πραγματοποιείται σε κάθε μια από τις θέσεις αυτές από τους χειριστές των συστημάτων. Η αυτοματοποίηση της εύρεσης θέσης των υπομικροσυστοιχιών οδηγεί σε πιο γρήγορους και ακριβείς υπολογισμούς που αφορούν στην πληροφορία που προσδιορίζεται από την εικόνα μικροσυστοιχίας. Στην συνέχεια της διατριβής, παρουσιάζεται μια συγκριτική μελέτη για την αποθορυβοποίηση των εικόνων μικροσυστοιχίας χρησιμοποιώντας τον μετασχηματισμό κυματιδίου και τα χωρικά φίλτρα ενώ επιπλέον με την βοήθεια τεχνικών της μαθηματικής μορφολογίας πραγματοποιείται δραστική μείωση του θορύβου που έχει την μορφή «αλάτι και πιπέρι». Τέλος, στα πλαίσια της εκπόνησης της διδακτορικής διατριβής, παρουσιάζεται μια μέθοδος κατάτμησης των περιοχών των spot των μικροσυστοιχιών, βασιζόμενη στον αλγόριθμο Random Walker. Κατά την πειραματική διαδικασία επιτυγχάνεται επιτυχής κατηγοριοποίηση των spot, ακόμα και στην περίπτωση εικόνων μικροσυστοιχίας με σοβαρά προβλήματα (θόρυβος, κατασκευαστικά λάθη, λάθη χειρισμού κατά την διαδικασία κατασκευής της μικροσυστοιχίας κ.α.), απαιτώντας σαν αρχική γνώση μόνο ένα μικρό αριθμό από εικονοστοιχεία προκειμένου να επιτευχθεί υψηλής ποιότητας κατάτμηση εικόνας. Τα πειραματικά αποτελέσματα συγκρίνονται ποιοτικά με αυτά που προκύπτουν με την εφαρμογή του μοντέλου κατάτμησης Chan-Vese το οποίο χρησιμοποιεί μια αρχική υπόθεση των συνόρων που υπάρχουν μεταξύ των ομάδων προς ταξινόμηση, αποδεικνύοντας ότι η ακρίβεια με την οποία η προτεινόμενη μέθοδος ταξινομεί τις περιοχές των spot στην σωστή κατηγορία σε μια μικροσυστοιχία, είναι σαφώς καλύτερη και πιο ακριβής. / DNA microarray technology is a high-throughput technique that determines how a cell can control the expression of large numbers of genes simultaneously. Microarrays are used to monitor changes in the expression levels of genes in response to changes in environmental conditions or in healthy versus diseased cells by using advanced information processing methods. Due to the nature of the acquisition process, microarray experiments involve a large number of error-prone procedures that lead to a high level of noise and structural problems in the resulting data. During the last fifteen years, robust methods have been proposed by many researchers resulting in several solutions for the enhancement of the microarray images. Though microarray image analysis has been elaborated quite enough, the enhancement process is still an intriguing issue as the need for even better results has not decreased. The goal of this PhD thesis is to significantly contribute to the above effort by proposing enhancing methods (denoising, segmentation) for the microarray image analysis. More specifically, a novel automated subgrid detection method is presented introducing a pre-processing step of the subgrid detection. This step is rarely taken into consideration as in most microarray enhancing methods it is arbitrarily assumed that the subgrids have been already identified. The automation of the subgrid detection leads to faster and more accurate information extraction from microarray images. Consequently, the PhD thesis presents a comparative denoising framework for microarray image denoising that includes wavelets and spatial filters while on the other hand uses mathematical morphology methods to reduce the “salt&pepper”-like noise in microarray images. Finally, a method for microarray spot segmentation is proposed, based on the Random Walker algorithm. During the experimental process, accurate spot segmentation is obtained even in case of relatively-high distorted images, using only an initial annotation for a small number of pixels for high-quality image segmentation. The experimental results are qualitatively compared to the Chan-Vese segmentation model, showing that the accuracy of the proposed microarray spot detection method is more accurate than the spot borders defined by the compared method.