Στην παρούσα εργασία προσεγγίζονται τα Sudoku puzzles χρησιμοποιώντας μαθηματικές έννοιες κυρίως από την θεωρία γραφημάτων, την άλγεβρα, τη θεωρία πινάκων αλλά και την κρυπτογραφία και τη θεωρία ανάπτυξης αλγορίθμων, oυσιαστικά χρησιμοποιούνται διάφορες οπτικές γωνίες προκειμένου να απεικονιστεί η μελέτη αυτών των puzzles μέσω των μαθηματικών. Η εργασία χωρίζεται σε έξι βασικά κεφάλαια: Το πρώτο κεφάλαιο περιέχει βασικές έννοιες της άλγεβρας και της θεωρίας γραφημάτων, όπως ο ορισμός της ομάδας, του συνεκτικού γραφήματος, ο βαθμός κορυφής και άλλα, οι οποίες χρησιμοποιούνται επανειλημμένα στην εργασία, έτσι ώστε να μπορεί να γίνει κατανοητή χωρίς να απαιτείται η χρήση άλλων επιστημονικών πηγών. Χωρίζεται σε τέσσερεις βασικές ενότητες οι οποίες παρουσιάζονται με την ακόλουθη σειρά. Η πρώτη ενότητα είναι οι Βασικές Έννοιες Γραφημάτων, η οποία ουσιαστικά αναφέρεται στην βασική ορολογία των γραφημάτων. Η δεύτερη ενότητα είναι τα Βασικά Είδη Γραφημάτων και περιέχει γραφήματα με συγκεκριμένα χαρακτηριστικά και ιδιότητες, οι οποίες είναι απαραίτητες για την ανάλυση της παρούσας εργασίας. Στη συνέχεια η τρίτη ενότητα είναι οι Βασικές Έννοιες Γραμμικής Άλγεβρας, η οποία περιέχει συγκεκριμένους ορισμούς κυρίως των ομάδων και των συμμετριών που χρησιμοποιούνται για την απαρίθμηση των Sudoku. Τέλος η τελευταία ενότητα είναι οι Αλγεβρικές Ιδιότητες Γραφημάτων, η οποία περιέχει ορισμούς και αλγεβρικές αλληλεπιδράσεις πάνω στα γραφήματα. Για περισσότερες λεπτομέρειες σχετικά με την άλγεβρα και τη θεωρία γραφημάτων, παραπέμπουμε στα [6], [7] και [29]. Το δεύτερο κεφάλαιο περιέχει τους ορισμούς του Sudoku puzzle και των λατινικών τετραγώνων, τα οποία είναι μια γενίκευση των Sudoku puzzles, όπως θα αναφερθεί παρακάτω. Για εκτενέστερη έρευνα πάνω στα λατινικά τετράγωνα παραπέμπουμε στα [3], [10], [11], [12],[13], [15], [16], [17], [18] και [29]. Στο τρίτο κεφάλαιο απαριθμούνται οι κλάσεις ισοδυναμίας των λατινικών τετραγώνων αρχικά και στη συνέχεια γίνεται απαρίθμηση τριών ειδών Sudoku puzzles, τα οποία είναι τα junior Sudoku puzzles τάξης 44, τα Sudoku puzzles τάξης 9x9 και τα 2-Quasi-μαγικά Sudoku, τα οποία έχουν έναν παραπάνω περιορισμό σε σχέση με τα συνήθη Sudoku. Τέλος, απαριθμούνται οι συμμετρίες των Sudoku puzzles τάξης 9x9 και γίνεται μια σύντομη ανάλυση των μητρώων μετάθεσής τους. Περαιτέρω πληροφορίες βρίσκονται στα [1], [2], [4], [5], [9], [14], [19], [20], [21], [22], και [26]. Στο τέταρτο κεφάλαιο αλλάζει η αυστηρά αλγεβρική προσέγγιση που υπάρχει στις παραπάνω ενότητες. Εδώ παρουσιάζεται το Sudoku puzzle με μια ισοδύναμη μορφή γραφήματος και γίνεται μια σύντομη παρουσίαση βασικών εννοιών της κρυπτογραφίας, καθώς και μια θεωρητική προσέγγιση της κρυπτογράφησης του Sudoku puzzle, με τη βοήθεια του πρωτοκόλλου της μηδενικής γνώσης. Περαιτέρω πληροφορίες βρίσκονται στα [8], [23] και [24]. Στο πέμπτο κεφάλαιο αλλάζει πάλι ο επιστημονικός κλάδος, μέσω του οποίου εξετάζουμε τα Sudoku puzzles και επικεντρώνεται στην απεικόνιση ενός στιγμιοτύπου του puzzle Sudoku σε ένα στιγμιότυπο του προβλήματος SAT. Όλοι οι περιορισμοί του Sudoku θα μπορέσουν να διατηρηθούν μέσω των κανονικών συζευκτικών προτάσεων του προβλήματος SAT, οι οποίες έχουν χωριστεί σε πέντε ενότητες. Η καταμέτρηση των κανονικών συζευκτικών προτάσεων του προβλήματος SAT μέσω αναδρομικών τύπων, αποτελεί το πρωτότυπο τμήμα της διπλωματικής καθώς και η ανάλυση των τύπων αυτών, την οποία περιέχει το επισυναπτόμενο CD. Για πιο θεωρητική προσέγγιση προτείνονται τα [25], [26], [27], [30]. Το έκτο κεφάλαιο της εργασίας περιέχει μια διασκεδαστική εφαρμογή κρυπτογράφησης οποιουδήποτε Sudoku puzzle τάξης 99 . Η εφαρμογή υλοποιείται με τραπουλόχαρτα, έτσι ώστε ο αναγνώστης να είναι σε θέση να κρυπτογραφήσει οποιοδήποτε λύση puzzle Sudoku, χωρίς να είναι υποχρεωμένος να παρουσιάσει τη λύση του στον αντίπαλο, χρησιμοποιώντας μόνο τρείς τράπουλες. Ο στόχος του τελευταίου κεφαλαίου είναι να κάνει τον επίλογο της εργασίας πιο ευχάριστο και πιο ανάλαφρο ακόμα και για νέους επιστήμονες στο χώρο της κρυπτογραφίας, της θεωρίας γραφημάτων και της άλγεβρας. / The essay is about the complexity of the Sudoku puzzles and how you can numarated them.

Στην παρούσα Διπλωματική Εργασία θα ασχοληθούμε με το πασίγνωστο πρόβλημα της Παραγοντοποίησης Ακεραίων. Η προσέγγιση μας είναι από τη μεριά της Επιστήμης των Υπολογιστών και της Υπολογιστικής Πολυπλοκότητας. Προσπαθούμε να κατανοήσουμε γιατί η Παραγοντοποίηση Ακεραίων θεωρείται ένα υπολογιστικά δύσκολο πρόβλημα και να δούμε τις πρακτικές εφαρμογές και συνέπειες αυτής της θεώρησης. / In the present Diploma Thesis we are going to deal with the very well known problem of Integer-Factoring. Our approach is from the side of Computer Science and Computational Complexity. We are trying to understand why Integer-Factoring is widely considered as a hard problem to solve and see the practical applications of this consideration.

Σκοπός της παρούσας εργασίας είναι η αξιοποίηση και ο οδηγός χρήσης του συστήματος ανάλυσης εικόνας σε περιβαλλοντικές, ορυκτολογικές και πετρογραφικές εφαρμογές. Για να δείξουμε την αξιοποίηση του συστήματος ανάλυσης εικόνας εφαρμόστηκαν μέθοδοι ανάλυσης εικόνας σε εικόνες ηλεκτρονικού και πολωτικού μικροσκοπίου, από λεπτές και στιλπνές τομές, με σκοπό την υποβοήθηση στην επίλυση διαφόρων περιβαλλοντικών ορυκτολογικών και πετρογραφικών προβλημάτων όπως εντοπισμός αμιάντου, υπολογισμός ποσοστιαίας συμμετοχής ορυκτών, υπολογισμός περιφέρειας και εμβαδού κρυστάλλου, υπολογισμός πολυπλοκότητας των ορίων των κρυστάλλων σε λεπτή τομή καθώς και υπολογισμός πορώδους πετρωμάτων. Δόθηκε επίσης οδηγός χρήσης του συστήματος ανάλυσης εικόνας βασιζόμενος στο λογισμικό που χρησιμοποιείται στο Γεωλογικό Τμήμα του Πανεπιστημίου Πατρών. Έγινε αναφορά και δόθηκαν παραδείγματα με εικόνες όλων των μενού και υπομενού του λογισμικού. / Aim of present work is the exploitation and the manual of use of Image analysis in environmental, mineralogical and petrographic applications. In order to show the exploitation Image analysis, applied methods of analysis of picture in pictures of electronic and polotic microscope,from thin and glossy sections, aiming at the assistance in the resolution of various environmental mineralogical and petrographic problems as localisation of asbestos, calculation of percentage attendance mining, calculation of region and area of crystal, calculation of complexity of limits of crystals in thin section as well as calculation porosities of rocks. Also was given a manual of Image analysis based on the software that is used in the Geological Department of Patras University. Reported and given examples with pictures all the menus and submenus of the software.

Objective of the present study is the development of methods for the assessment of manufacturing systems complexity and the investigation of flexibility and complexity relationship. Towards this target, a complete approach based on information theory permitting the analytical, quantitative and systematic modeling and quantification of both static and dynamic manufacturing complexity is proposed. Static complexity concerns the structure of the manufacturing systems, namely the products, the processes, the resources that constitute the systems as well as their interconnections. Static complexity is treated as the information that is required for the description of a manufacturing system. Multi domain matrices modeling the relationships between products, processes and resources are formalized as networks following the notions of graph theory. The information content of each matrix is assessed employing Shannon entropy measure and their aggregation yields the static complexity. Dynamic complexity is related to the uncertainty in the behaviour of a manufacturing system and in the present study is associated with the unpredictability of the performance indicators timeseries. The unpredictability of the performance indicators timeseries, which are provided by computer simulation, is captured employing the Lempel Ziv algorithm that calculates the Kolmogorov complexity. The dynamic complexity is either the unpredictability of a specific timeseries or the weighted mean of a series of performance indicators timeseries produced under different product demand scenarios. The relationship between flexibility and complexity is investigated for a group of 19 different configurations of a manufacturing system. In particular, operation flexibility that refers to the system’s ability to produce a set of products through different machines, materials, operations and sequences of operations and total complexity, and both static and dynamic are examined employing a utility function. As a case study, two assembly lines producing three car floor model types at three different product mixes are investigated. The dynamic complexity of each assembly line is assessed and the relationship between product mix and dynamic complexity is studied. The evaluation of the case study revealed the efficiency of the suggested approach validated its applicability to industrial environments. / Αντικείμενο της παρούσας διατριβής είναι η ανάπτυξη μεθόδων για την εκτίμηση πολυπλοκότητας συστημάτων παραγωγής και η διερεύνηση της σχέσης ευελιξίας και πολυπλοκότητας. Προς αυτή την κατεύθυνση προτείνεται μια ολοκληρωμένη προσέγγιση βασισμένη στην θεωρία της πληροφορίας που επιτρέπει μια αναλυτική, ποσοτικοποιημένη και συστηματική προτυποποίηση και εκτίμηση τόσο της στατικής όσο και της δυναμικής πολυπλοκότητας των συστημάτων παραγωγής. Η στατική πολυπλοκότητα αφορά την δομή των συστημάτων παραγωγής, και σχετίζεται με τα προϊόντα, τις διεργασίες, τους παραγωγικούς πόρους που αποτελούν το σύστημα καθώς και τις μεταξύ τους σχέσεις. Η στατική πολυπλοκότητα αντιμετωπίζεται ως η πληροφορία που απαιτείται για να περιγραφεί ένα σύστημα παραγωγής. Πολυ-πεδιακοί πίνακες αναπαριστούν τις σχέσεις μεταξύ προϊόντων, διεργασιών και πόρων και προτυποποιούνται ως δίκτυα ακολουθώντας την θεωρία γράφων. Το πληροφοριακό περιεχόμενο κάθε πίνακα εκτιμάται με την χρήση της εντροπίας Shannon και το άθροισμα για όλους τους πίνακες δίνει την στατική πολυπλοκότητα. Η δυναμική πολυπλοκότητα σχετίζεται με την αβεβαιότητα της συμπεριφοράς των συστημάτων παραγωγής και στην παρούσα διατριβή συνδέεται με την απροβλεψιμότητα των χρονοσειρών δεικτών απόδοσης ενός συστήματος. Οι χρονοσειρές των δεικτών απόδοσης προκύπτουν από υπολογιστική προσομοίωση και η απροβλεψιμότητα τους εκτιμάται με των αλγόριθμο Lempel Ziv ο οποίος υπολογίζει την πολυπλοκότητα Kolmogorov. Η δυναμική πολυπλοκότητα είναι η απροβλεψιμότητα είτε μιας συγκεκριμένης χρονοσειράς είτε ο σταθμισμένος μέσος όρος ενός συνόλου χρονοσειρών δεικτών απόδοσης. Η σχέση ευελιξίας – πολυπλοκότητας διερευνάται για 19 διαμορφώσεις ενός συστήματος παραγωγής. Συγκεκριμένα, η ευελιξία λειτουργίας που αναφέρεται στην ικανότητα ενός συστήματος να παράγει ένα σύνολο προϊόντων χρησιμοποιώντας διαφορετικές μηχανές και διεργασίες και πολυπλοκότητα τόσο η στατική όσο και η δυναμική μελετώνται με μια συνάρτηση χρησιμότητας. Ως περίπτωση μελέτης εξετάζονται δύο γραμμές συναρμολόγησης που παράγουν τρία δάπεδα αμαξιού σε τρία μείγματα παραγωγής. Η δυναμική πολυπλοκότητα κάθε γραμμής και η σχέση μείγματος παραγωγής και δυναμικής πολυπλοκότητα μελετώνται. Η αξιολόγηση της περίπτωσης μελέτης αποδεικνύει την αποτελεσματικότητα των προτεινόμενων μεθόδων σε βιομηχανικό περιβάλλον.

Στην εργασία αυτή ασχοληθήκαμε με το πρόβλημα της Πιθανοτικής Ικανοποιησιμότητας. Παρουσιάσαμε ανάλυση της πολυπλοκότητας του προβλήματος και το επιλύσαμε με την βοήθεια του λογισμικού πακέτου CPLEX. Περιγράψαμε προσεγγιστικούς αλγόριθμους για το πρόβλημα της Μέγιστης Ικανοποιησιμότητας που χρησιμοποιείται στην διαδικασία της Column Generation. Τέλος, πριγράψαμε το αντίστροφο πρόβλημα των συχνών στοιχειοσυνόλων και την σχέση του με το πρόβλημα της Μέγιστης Ικανοποιησιμότητας. / This thesis is about the problem of probabilistic satisfiability. We describe its computational complexity, we solve the problem using CPLEX, we discribe some approximations on Maximum Satisfiability. Finally, we describe the connection between the problem of Probabilistic Satisfiability and the inverse frequent itemset mining.

Η παρούσα διδακτορική διατριβή ασχολείται με την εφαρμογή της υπολογιστικής νοημοσύνης στη μουσική, επιχειρώντας ταπεινά να συνεισφέρει, έστω και κατ' ελάχιστο, στην μακραίωνη πορεία της σύζευξης των μουσικών εννοιών με τα μαθηματικά. Οι τρεις πυλώνες πάνω στους οποίους στηρίζεται αυτή η διατριβή αφορούν τη χρήση μεθόδων υπολογιστικής νοημοσύνης για α) την εξέταση των μαθηματικών μουσικών χαρακτηριστικών με στόχο την επιτυχή κατηγοριοποίηση, αναγνώριση και χαρακτηρισμό περιεχομένου σε μουσικά κομμάτια, β) την ευφυή αυτόματη σύνθεση μουσικής βάσει μαθηματικών μουσικών χαρακτηριστικών και γ) τη διαδραστική ευφυή σύνθεση μουσικής και τις επεκτάσεις της. Ενώ οι τρεις αυτοί πυλώνες φαίνονται επιφανειακά ασύνδετοι, το κοινό τους θεμέλιο είναι τα μαθηματικά μουσικά χαρακτηριστικά και ο ρόλος που αυτά διαδραματίζουν έτσι ώστε να αναπτυχθούν μοντέλα υπολογιστικής νοημοσύνης που τελικά προσομοιάζουν τον τρόπο που οι άνθρωποι ``αντιλαμβάνονται'' τη μουσική. Το γεγονός ότι όλοι οι δίαυλοι έρευνας που παρουσιάζονται σε αυτή τη διατριβή διοχετεύονται στο ίδιο κανάλι, γίνεται φανερό στο τελευταίο κεφάλαιο (Κεφάλαιο 9) όπου τα μαθηματικά μουσικά χαρακτηριστικά, η ευφυής σύνθεση μουσικής και η διαδραστική ευφυής σύνθεση μουσικής, ενσωματώνονται σε ένα καινοτόμο σύστημα που περιγράφεται λεπτομερώς στο εν λόγω κεφάλαιο. Επίσης, βασική μέριμνα των μελετών που παρουσιάζονται στης έρευνες που αποτελούν την παρούσα διατριβή ήταν η απόδοση αντικειμενικών, λεπτομερών και αμερόληπτων αποτελεσμάτων, μέσα από εξαντλητικές πειραματικές διαδικασίες, πολλές από τις οποίες περιείχαν και καθεαυτές νεοτερισμούς. Η επισήμανση της παραπάνω πρότασης θέλει να καταδείξει τη διαφοροποίηση της παρούσας διατριβής από την εν πολλοίς καθεστηκυία αντίληψη για τον τρόπο παρουσίασης των αποτελεσμάτων για τις μεθόδους αυτόματης σύνθεσης μουσικής, μέσα από την εμφάνιση τμημάτων από συνθέσεις (σε μορφή παρτιτούρας ή ήχου). Το πρώτο μέρος της διατριβής περιλαμβάνει τα Κεφάλαια 2 και 3, όπου μελετάται η κατηγοριοποίηση μουσικών κομματιών σε συμβολική μορφή, καθώς και η αναγνώριση και ο χαρακτηρισμός περιεχομένου από ηχογραφήσεις. Στόχος του μέρους αυτού είναι η παρουσίαση της καθοριστικότητας αφενός του χώρου του προφίλ τονικής τάξης για την ανάπτυξη μαθηματικών μουσικών χαρακτηριστικών που ενσωματώνουν την ανθρώπινη μουσική αντίληψη μέχρι ενός βαθμού, και αφετέρου η ανάδειξη της αποτελεσματικότητας των μεθόδων υπολογιστικής νοημοσύνης ως εργαλεία αποτελεσματικού εντοπισμού αυτής της ιδιότητας των προαναφερθέντων χαρακτηριστικών. Η συνεισφορά του πρώτου μέρους αφορά κυρίως την πρόταση νέων μεθοδολογιών που επιτελούν αποτελεσματικά προσομοιώσεις κατηγοριοποίησης κομματιών ανά συνθέτη ή είδος, αναγνώρισης περιεχομένου ηχογράφησης τυμπάνων και χαρακτηρισμού μουσικού ηχητικού υλικού με τμηματοποίηση σε περιοχές με διαφορετικό κλειδί σύνθεσης. Επίσης, στη συνεισφορά του μέρους αυτού μπορεί να ενταχθεί και η εισαγωγή και ανάλυση του πρωτεύοντος χρωματικού ιδιοχώρου. Το δεύτερο μέρος περιλαμβάνει τα Κεφάλαια 4, 5, 6 και 7, στα οποία αναλύεται η συνεισφορά της διατριβής στον τομέα της ευφυούς αυτόματης σύνθεσης μουσικής. Συγκεκριμένα, η συνεισφορά του Κεφαλαίου 4 είναι η πρόταση μιας κατηγοριοποίησης των ευφυών μεθόδων σύνθεσης σύμφωνα με το αποτέλεσμα που επιδιώκουν, προτείνοντας δηλαδή τις κατηγορίες των μη επιβλεπόμενων, των επιβλεπόμενων και των διαδραστικών συστημάτων ευφυούς σύνθεσης. Με αυτή την κατηγοριοποίηση ο αναγνώστης εισάγεται στα επόμενα κεφάλαια όπου περιγράφονται τα καινοτόμα συστήματα που προτάθηκαν, κυρίως για επιβλεπόμενη σύνθεση βάσει χαρακτηριστικών, για την ευφυή παραγωγή ρυθμών (Κεφάλαιο 5), τόνων (Κεφάλαιο 6), καθώς και για την ολοκλήρωση των συνθέσεων μέσω της έννοιας της οριζόντιας αντιγραφής ενορχήστρωσης και την ευφυή συνοδεία αυτοσχεδιαστή (Κεφάλαιο 7). Τα αποτελέσματα που παρέχονται για όλα τα συστήματα αυτού του μέρους εξετάζουν ενδελεχώς πολλές πτυχές των συνθετικών τους ιδιοτήτων, αποκαλύπτοντας τα σημεία υπεροχής τους αλλά και τις αδυναμίες τους. Στο τρίτο μέρος γίνεται η περιγραφή των διαδραστικών συστημάτων που μελετήθηκαν στη διατριβή, αναλύοντας όχι μόνο την ανάπτυξη των αλγόριθμων πίσω από τα συστήματα αυτά, αλλά εστιάζοντας κυρίως στα ουσιώδη ζητήματα που άπτονται της αντίληψης της ανθρώπινης μουσικής και της σύνδεσής της με την ευφυή-αυτόματη σύνθεση. Συγκεκριμένα, στο Κεφάλαιο 8 γίνεται αρχικά η παρουσίαση ενός καινοτόμου υπολογιστικού συστήματος που εξελίσσει διαδραστικά (με βαθμολογίες παρεχόμενες από τον χρήστη) συναρτήσεις με τη μέθοδο του γενετικού προγραμματισμού. Σκοπός του συστήματος αυτού είναι η παραγωγή κυματομορφών που ακούγονται γενιά με τη γενιά όλο και πιο ευχάριστες για την προσωπική του αισθητική του χρήστη. Μέσω αυτού του συστήματος προτάθηκε το ενδεχόμενο της άντλησης πληροφοριών για τα ηχητικά χαρακτηριστικά των μελωδιών σε διαφορετικά εξελικτικά στάδια - από τις μη εξελιγμένες και χαμηλά βαθμολογημένες στις εξελιγμένες και υψηλά βαθμολογημένες μελωδίες - έτσι ώστε να μελετηθεί το κατά πόσο τα ηχητικά χαρακτηριστικά αυτά μπορεί να παρέχουν ενδείξεις για την αισθητική αρτιότητα μιας μελωδίας. Αυτό το σύστημα επίσης αξιοποιήθηκε για την ανάπτυξη των γενετικών τελεστών προσαρμοσμένου βάθους, οι οποίοι, συνδυαζόμενοι με την παράμετρο ``παράγοντα ρίσκου'', δίνουν στον χρήστη έναν επιπλέον έλεγχο στην εξελικτική διαδικασία, απαλλάσσοντάς τον από ένα μέρος του φαινομένου της κόπωσης του χρήστη. Το τρίτο μέρος, και η ερευνητική διαδρομή αυτής της διατριβής, κλείνει με το Κεφάλαιο 9, όπου παρουσιάζεται ένα διαδραστικό σύστημα εξελικτικής σύνθεσης μουσικής σε δύο επίπεδα, το οποίο πέρα από το ότι συνδυάζει την έρευνα που έγινε σχεδόν σε ολόκληρη τη διατριβή, περιέχει επίσης νεοτερισμούς σε πολλά επίπεδα: από την κεντρική σύλληψη, την υλοποίηση, ως και τη διαδικασία εξαγωγής αποτελεσμάτων. Η κεντρική σύλληψη αφορά την εξέλιξη των μαθηματικών μουσικών χαρακτηριστικών που περιγράφουν μια μελωδία αντί για τη μελωδία καθεαυτή (ή το μοντέλο που την παράγει). Η υλοποίηση έγινε σε δύο επίπεδα, τον πάνω επίπεδο εξέλιξης χαρακτηριστικών και το κάτω επίπεδο ευφυούς επιβλεπόμενης σύνθεσης μουσικής με καινοτόμους αλγόριθμους και στα δύο επίπεδα. Τέλος, η πειραματική διαδικασία που ακολουθήθηκε, στην οποία προτάθηκε και υλοποιήθηκε η χρήση αυτόματων βαθμολογητών που προσομοιάζουν τη βαθμολογική συμπεριφορά των ανθρώπων, επέτρεψε την πλήρως αντικειμενική εξέταση των δυνατοτήτων του συστήματος να συγκλίνει στις βέλτιστες μελωδίες του χρήστη. / The PhD thesis at hand discusses the employment of computational intelligence in music, attempting to humbly commit a minimal contribution to the deep history of studies that relate music to mathematics. The three cornerstones upon which the thesis at hand is founded, discuss the employment of computational intelligence methods for a) the examination of musical-mathematical features towards classifying, identifying and characterising music content, b) intelligent music composition based on musical-mathematical features and c) interactive intelligent music composition and further developments. While at a first glance these three parts seem unrelated, their common keystone is the music-mathematical features and the role that these features play towards developing computational intelligence models which at some extent simulate the human ``perception’’ of music. The fact that all the research channels that are presented in this thesis, are finally led to a single stream, becomes evident in the final chapter of the thesis (Chapter 9) where the music-mathematical features, the intelligent music composition and the interactive music composition are embodied in an innovative system that is thoroughly described. Additionally, a main concern of the studies that comprise this thesis was the presentation of objective, detailed and unbiased results, achieved through exhaustive experimental processes, many of which were by themselves innovative. The latter comment intents to highlight the different approach that the research in this thesis follows, in comparison to the most common approaches concerning the presentation of experimental results for automatic music composition methods - which simply include small score or audio parts of automatically composed music. The first part of the thesis includes the Chapters 2 and 3, where the categorisation of music pieces in symbolic form is examined, as well as the identification and characterisation of music recordings. Aim of this part is on the hand to present the rich quality of information that can be extracted by several pitch class space-related features regarding human perception of music, while on the other hand to pinpoint the effectiveness of computational intelligence methods as tools to extract the aforementioned rich information. The first part’s contribution is primarily the presentation of novel methodologies that achieve effective categorisation of music pieces per composer or style, identify the content of drums recordings and characterise the content of recorded pieces by recognising locations of composition key changes. An additionally contribution of this part is the presentation and study of the principal chroma eigenspace. The second part encompasses Chapters 4, 5, 6 and 7, which discuss the contribution of this thesis in intelligent music composition. Specifically, the contribution of Chapter 4 includes a proposed categorisation of intelligent music composition methods based on their intended result, proposing their segregation to unsupervised, supervised and interactive intelligent music composition methodologies. Through this categorisation, an introduction to the subsequent chapters is achieved, which mainly discuss supervised intelligent music composition based on music-mathematical features for the generation of rhythmic sequences (Chapter 5), tonal sequences (Chapter 6), as well as integrated synthesis through the concept of horizontal orchestration replication and intelligent improviser accompaniment (Chapter 7). The results of the presented studies in this part constitute of exhausted research processes that examine different compositional aspects of the proposed methodologies, revealing their strengths and weaknesses over other methodologies presented in the literature. In the third part the interactive systems that were studied in the thesis are presented, not only by analysing the algorithmic development of the underlying methodologies, but mostly focussing on matters that pertain to the human perception and intelligent music composition. Specifically, in the beginning of Chapter 8 an innovative system is presented that evolves mathematical functions interactively (through user ratings), through genetic programming. Aim of this system is the generation and evolution of waveforms that sound more pleasant to the user, according to hers/his subjective criteria. This system allowed the proposition to obtain information about several audio features of the melodies in different evolutionary stages - from non evolved and low rated melodies to evolved and highly rated ones - in order to study whether these features incorporate indications about the aesthetic integrity of a melody. This system was also utilised towards the development of fitness-adaptive genetic operators, which, combined with the ``risk factor’’ parameter, gave the user additional control over the evolutionary process, alleviating user fatigue at a considerable extent. The third part, along with the research conducted in the context of this thesis, concludes with Chapter 9, where an interactive evolutionary intelligent music composition system is presented, that combines almost all research presented in the thesis up to that point. This chapter includes also several innovative research propositions in many levels: the core concept, the implementation and the experimental process. The core concept discusses the evolution of music-mathematical features that describe a melody, rather than evolving the melody per se (or the model that generates it). The implementation incorporated two levels of serial evolution: the upper level of feature evolution and the lower level of supervised intelligent music composition, with novel algorithms in both levels. Finally, the experimental process that was developed - in the context of which the utilisation of automatic raters that simulate human behaviour was proposed - allowed a completely subjective evaluation of the systems capabilities, regarding its convergence to the optimal melodies of the user’s subjective preference.

Η χρήση πολλαπλών κεραιών παίζει πλέον ένα πολύ σημαντικό ρόλο στη βελτίωση των ραδιοτηλεπικοινωνιών. Για το λόγο αυτό, ο τομέας των τηλεπικοινωνιακών συστημάτων πολλαπλών κεραιών μετάδοσης – λήψης (συστήματα ΜΙΜΟ) βρίσκεται στο προσκήνιο της ασύρματης έρευνας. Πρόσφατα, αποτελέσματα ερευνών έδειξαν ότι υπάρχει δυνατότητα αύξησης της χωρητικότητας στα ασύρματα τηλεπικοινωνιακά συστήματα χρησιμοποιώντας τεχνικές διαφοροποίησης μεταξύ πομπού – δέκτη (antenna diversity), δηλαδή δημιουργίας πολλαπλών ανεξάρτητων καναλιών ανάμεσα τους. Στην παρούσα εργασία μελετούνται τεχνικές κωδικοποίησης που εκμεταλλεύονται τη χωρική διαφοροποίηση κάνοντας χρήση χωροχρονικών κωδικών (space – time coding). Η μελέτη εστιάζεται στη χρήση χωροχρονικών κωδικών ανά μπλοκ από την πλευρά του πομπού, εξαιτίας της απλότητας υλοποίησης τους καθώς και της ικανότητας υποστήριξης πολλαπλών κεραιών από τη πλευρά του σταθμού βάσης. Η ανάλυσή τους γίνεται με βάση την εφαρμογή τους σε συστήματα που χρησιμοποιούν διαμόρφωση με πολυπλεξία ορθογώνιων φερουσών (OFDM). Η διαμόρφωση αυτή επιλέχθηκε γιατί υποστηρίζει υψηλούς ρυθμούς δεδομένων στα ασύρματα συστήματα και δείχνει άριστη συμπεριφορά σε κανάλια με επιλεκτική παραμόρφωση στη συχνότητα. Στη συνέχεια μελετώνται αλγόριθμοι επαναληπτικής αποκωδικοποίησης, δίνοντας έμφαση σε ένα ευρέως διαδεδομένο αλγόριθμο, τον Μέγιστο εκ των Υστέρων (MAP). Αναλύονται διεξοδικά τα βήματα του, καθώς και διάφορες τροποποιήσεις – βελτιστοποιήσεις του. Οι επαναληπτικοί αλγόριθμοι αποκωδικοποίησης αποτελούν πλέον ένα πολύ ισχυρό εργαλείο για την αποκωδικοποίηση Forward Error Correction κωδικοποιήσεων με χρήση συνελικτικών κωδικών, προσδίδοντας στα συστήματα αποδόσεις κοντά στο όριο του Shannon. Τέλος, πραγματοποιούνται κατάλληλες υλοποιήσεις που προέκυψαν από το συνδυασμό των εν λόγω αλγορίθμων επαναληπτικής αποκωδικοποίησης με τους χωροχρονικούς κώδικες ανά μπλοκ πάνω σε ένα σύστημα κεραιών με χρήση OFDM. Γίνεται σύγκριση της απόδοσης των συστημάτων αυτών με βάση την αντίστοιχη υλοποίηση του εκάστοτε αλγορίθμου επαναληπτικής αποκωδικοποίησης και μελετούνται σε βάθος διάφορες τροποποιήσεις που μπορούν δεχθούν με κριτήριο τη χαμηλή πολυπλοκότητα υλοποίησης. Για την αξιολόγηση της απόδοσης, γίνεται μία περαιτέρω σύγκριση με χρήση αναπαράστασης σταθερής υποδιαστολής και εξάγονται σειρά συμπερασμάτων από τις πειραματικές μετρήσεις που προέκυψαν. / The use of multiple antennas is an essential issue in telecommunications, nowadays. So, multiple input – multiple output systems (MIMO) has attracted a lot of attention in wireless research. Lately, it has been shown that it can be an improvement in the capacity of wireless communication systems by using antenna diversity, that’s different independent channels between transmitter and receiver. In this thesis, we study coding techniques that exploit space diversity by using space – time codes. Particularly, we focus on space – time block coding (STBC) from the transmitter’s point of view, because of the simplicity of its implementation and the ability to support multiple antennas at the base stations. The analysis is based on the systems that use Orthogonal Frequency Division Multiplexing Systems (OFDM). This technique was chosen because it can support high data rates and it behaves very well in a frequency selective fading channel. Moreover, we study iterative decoding algorithms and we focus on a very well known algorithm, the Maximum A Posteriori (MAP). There, we analyze its steps and its modifications and improvements. The iterative decoding algorithms are a cornerstone on decoding Forward Error Correction codes, such as Convolutional codes, almost reaching the Shannon limit. Finally, there are different kinds of implementations using suitable iterative decoding algorithms in concatenation with space – time block coding with antennas and ODFM. We compare the performance of the corresponding systems and investigate the complexity trying to maintain it in a low level. For a thorough investigation, we also use fixed point arithmetic in these implementations.

Τα Ασύρματα Δίκτυα Αισθητήρων (ΑΔΑ) αποτελούν μία αρκετά πρόσφατη και πολλά υποσχόμενη νέα τεχνολογία που βρίσκει πληθώρα εφαρμογών. Λόγω της ευρύτατης εφαρμοσιμότητάς της και της προφανούς θέσης που βρίσκει στο σύγχρονο κατανεμημένο υπολογιστικό κόσμο, η επιστημονική τυπική θεμελίωση των νόμων που διέπουν αυτή τη νέα τεχνολογία καθίσταται απαραίτητη. Έτσι, έχουν προταθεί πολλά νέα υπολογιστικά μοντέλα για ΑΔΑ. Μία ειδική κατηγορία τέτοιων συστημάτων είναι τα Πρωτόκολλα Πληθυσμών (ΠΠ). Αυτά διέπονται από τρία ιδιαίτερα χαρακτηριστικά: Οι κόμβοι αίσθησης (πράκτορες) κινούνται παθητικά, δηλαδή δε μπορούν να ελέγξουν την κίνηση στην οποία υπόκεινται, η διαθέσιμη μνήμη κάθε κόμβου είναι πολύ περιορισμένη και οι πράκτορες αλληλεπιδρούν κατά ζεύγη. Έχει αποδειχθεί ότι ένα κατηγόρημα είναι υπολογίσιμο από το μοντέλο των ΠΠ εάν και μόνο εάν είναι ημιγραμμικό. Η κλάση των ημιγραμμικών κατηγορημάτων αποτελεί μία αρκετά μικρή κλάση. Στην παρούσα εργασία, βασικός μας στόχος είναι η επέκταση του μοντέλου των πρωτοκόλλων πληθυσμών με σκοπό το κέρδος σε υπολογιστική ισχύ. Πρώτα κάνουμε την παραδοχή ότι, πέρα των κόμβων αίσθησης, και οι ακμές του γραφήματος μπορούν να διατηρούν περιορισμένες καταστάσεις. Έτσι, σε ένα πλήρες γράφημα n κόμβων είναι σα να έχουμε προσθέσει Ο(n^2) επιπλέον θέσεις μνήμης οι οποίες διαβάζονται και γράφονται μόνο από τα άκρα της αντίστοιχης ακμής. Αποδεικνύουμε ότι το νέο μοντέλο, το οποίο καλούμε μοντέλο Πρωτοκόλλων Πληθυσμών με Διαμεσολαβητή, μπορεί να λειτουργήσει ως μία κατανεμημένη ανταιτιοκρατική μηχανή Turing (ΜΤ) που χρησιμοποιεί όλη τη διαθέσιμη μνήμη. Η μόνη διαφορά από μία συνήθη ΜΤ είναι ότι η συγκεκριμένη μηχανή υπολογίζει μόνο συμμετρικές γλώσσες. Πιο τυπικά, δείχνουμε ότι ένα κατηγόρημα είναι υπολογίσιμο από το νέο μοντέλο εάν και μόνο εάν είναι συμμετρικό και ανήκει στην NSPACE(n^2). Επιπλέον, μελετάμε και τη δυνατότητα του νέου μοντέλου να διαγιγνώσκει γλώσσες γραφημάτων (για γενικά γραφήματα). Εν συνεχεία, αγνοούμε τις καταστάσεις των ακμών και δίνουμε μία νέα βελτίωση και πάλι απευθείας απ' το μοντέλο των ΠΠ. Η υπόθεση που κάνουμε τώρα είναι ότι οι πράκτορες είναι πολυταινιακές ΜΤ με άπειρη μνήμη, που μπορούν τόσο να εκτελούν εσωτερικό υπολογισμό όσο και να αλληλεπιδρούν με άλλους πράκτορες και ορίζουμε χωρικά φραγμένους υπολογισμούς. Καλούμε το νέο αυτό μοντέλο, μοντέλο Παθητικά κινούμενων Μηχανών. Αποδεικνύουμε ότι αν χρησιμοποιείται σε κάθε πράκτορα μνήμη το πολύ f(n) για f(n)=Ω(log n) τότε ένα κατηγόρημα είναι υπολογίσιμο από το νέο μοντέλο εάν και μόνο εάν είναι συμμετρικό και ανήκει στην NSPACE(nf(n)). Δείχνουμε επίσης ότι αυτό δεν ισχύει για f(n)=o(log n). Βασιζόμενοι σε αυτά, δείχνουμε ότι για f(n)=Ω(log n) υπάρχει μία χωρική ιεραρχία ακριβώς όπως και για τις συνήθεις (συμμετρικές) ΜΤ. Δείχνουμε επίσης ότι αυτό δεν ισχύει για f(n)=o(loglog n), καθώς στην τελευταία περίπτωση η αντίστοιχη κλάση καταρρέει μέσα στην κλάση των ημιγραμμικών κατηγορημάτων, και τέλος ότι για f(n)=Ω(loglog n) η κλάση γίνεται αυστηρά μεγαλύτερη των ημιγραμμικών κατηγορημάτων. Αφήνουμε ανοικτό το πρόβλημα του τι ακριβώς συμβαίνει για χωρικά φράγματα f(n) τέτοια ώστε f(n)=Ω(loglog n) και f(n)=o(log n). / Wireless Sensor Networks (WSNs) constitute a recent and promising new technology that is widely applicable. Due to the applicability of this technology and its obvious importance for the modern distributed computational world, the formal scientific foundation of its inherent laws becomes essential. As a result, many new computational models for WSNs have been proposed. Population Protocols (PPs) are a special category of such systems. These are mainly identified by three distinctive characteristics: the sensor nodes (agents) move passively, that is, they cannot control the underlying mobility pattern, the available memory to each agent is restricted, and the agents interact in pairs. It has been proven that a predicate is computable by the PP model iff it is semilinear. The class of semilinear predicates is a fairly small class. In this work, our basic goal is to enhance the PP model in order to improve the computational power. We first make the assumption that not only the nodes but also the edges of the communication graph can store restricted states. In a complete graph of n nodes it is like having added O(n^2) additional memory cells which are only read and written by the endpoints of the corresponding edge. We prove that the new model, called Mediated Population Protocol model, can operate as a distributed nondeterministic Turing machine (TM) that uses all the available memory. The only difference from a usual TM is that this one computes only symmetric languages. More formally, we establish that a predicate is computable by the new model iff it is symmetric and belongs to NSPACE(n^2). Moreover, we study the ability of the new model to decide graph languages (for general graphs). The next step is to ignore the states of the edges and provide another enhancement straight away from the PP model. The assumption now is that the agents are multitape TMs equipped with infinite memory, that can perform internal computation and interact with other agents, and we define space-bounded computations. We call this the Passively mobile Machines model. We prove that if each agent uses at most f(n) memory for f(n)=Ω(log n) then a predicate is computable iff it is symmetric and belongs to NSPACE(nf(n)). We also show that this is not the case for f(n)=o(log n). Based on these, we show that for f(n)=Ω(log n) there exists a space hierarchy like the one for classical symmetric TMs. We also show that the latter is not the case for f(n)=o(loglog n), since here the corresponding class collapses in the class of semilinear predicates and finally that for f(n)=Ω(loglog n) the class becomes a proper superset of semilinear predicates. We leave open the problem of characterizing the classes for f(n)=Ω(loglog n) and f(n)=o(log n).

Ο στόχος της παρούσας διατριβής είναι η ανάπτυξη μιας νέας κλάσης εξωτερικά εξαρτώμενων στοχαστικών συναρτησιακών μοντέλων για την αναγνώριση (identification) δυναμικών συστημάτων που παρουσιάζουν πολλαπλά σημεία λειτουργίας, τα οποία καθορίζονται από μετρήσιμη εξωτερική μεταβλητή (όπως για παράδειγμα, η θερμοκρασία, η υγρασία, κ.λ.π.). Επιπλέον, στόχος είναι η ανάπτυξη καινοτόμου μεθοδολογίας διάγνωσης (ανίχνευσης, προσδιορισμού και εκτίμησης) βλαβών σε δυναμικά συστήματα βάσει των στοχαστικών συναρτησιακών μοντέλων. Η διατριβή αρχικά πραγματεύεται την ανάπτυξη κατάλληλης μεθοδολογίας που αντιμετωπίζει τα επιμέρους προβλήματα της ανίχνευσης, του προσδιορισμού και της εκτίμησης βλαβών στη σύνθετη περίπτωση όπου η κατασκευή διεγείρεται υπό σεισμική διέγερση. Η αποτίμηση της μεθόδου αποτέλεσε και το έναυσμα για τη διαμόρφωση καινοτόμου μεθοδολογίας, η οποία βασίζεται σε μια νέα κλάση εξωτερικά εξαρτώμενων στοχαστικών συναρτησιακών μοντέλων. Τα μοντέλα αυτά έχουν την ικανότητα να αναπαριστούν, με μεγάλη ακρίβεια, μια κατασκευή για συγκεκριμένο τύπο βλάβης και συνεχές εύρος μεγεθών, χρησιμοποιώντας μοναδική μαθηματική αναπαράσταση παραμετροποιημένη ως προς το μέγεθος της βλάβης. Επισημαίνεται ότι τέτοιου τύπου συναρτησιακά μοντέλα δεν αναφέρονται στην βιβλιογραφία. Οι πιο συγγενείς οικογένειες μοντέλων προέρχονται από τις επιστήμες της στατιστικής και της οικονομετρίας, οι οποίες όμως δεν παρουσιάζουν συναρτησιακή μορφή και δεν μπορούν να καλύψουν συνεχή εύρη τιμών. Εξαιτίας αυτού του γεγονότος στη συνέχεια της διατριβής ορίζεται η νέα κλάση εξωτερικά εξαρτώμενων στοχαστικών Συναρτησιακών (F) μοντέλων Αυτοπαλινδρόμησης (AR) με Εξωγενή (X) είσοδο, των οποίων οι παράμετροι και η διασπορά του θορύβου είναι συναρτήσεις μετρήσιμης εξωτερικής μεταβλητής. Αυτή η συναρτησιακή εξάρτηση δίνει τη σημαντική ικανότητα στη νέα κλάση μοντέλων να μπορούν να χρησιμοποιηθούν: α) για τη δυναμική αναγνώριση συστημάτων με πολλαπλά σημεία λειτουργίας που καθορίζονται από μετρήσιμη εξωτερική μεταβλητή και, β) για την ανίχνευση, τον προσδιορισμό και την εκτίμηση βλαβών σε στοχαστικά δυναμικά συστήματα όπου η εξωτερική μεταβλητή είναι το μέγεθος της βλάβης. Επιπλέον, για τα μοντέλα αυτά αναπτύσσονται κατάλληλες μέθοδοι εκτίμησης των οποίων τα χαρακτηριστικά μελετώνται, και η αποτίμηση τους πραγματοποιείται μέσω προσομοιώσεων Monte Carlo. Στη συνέχεια ορίζεται η νέα κλάση εξωτερικά εξαρτώμενων στοχαστικών Συναρτησιακών (F) μοντέλων Αυτοπαλινδρόμησης (AR) και Κινητού Μέσου Όρου (ΜΑ) με Εξωγενή (X) είσοδο των οποίων επίσης οι παράμετροι και η διασπορά του θορύβου εκφράζονται ως συναρτήσεις μετρήσιμης εξωτερικής μεταβλητής. Τα μοντέλα FARΜΑX προσφέρουν επιπλέον ευελιξία σε σχέση με τα μοντέλα FARX εξαιτίας της εισαγωγής του πολυωνύμου ΜΑ. Για τα μοντέλα αυτά αναπτύσσονται επίσης κατάλληλες μεθοδολογίες εκτίμησης που βασίζονται στη μέγιστη πιθανοφάνεια και στην αρχή του σφάλματος πρόβλεψης. Επιπλέον, διαμορφώνονται δύο ακόμη μέθοδοι εκτίμησης που βασίζονται στην ελαχιστοποίηση του σφάλματος πρόβλεψης μέσω διαδοχικών γραμμικών σταδίων, οι οποίες παρουσιάζουν κάποια πρακτικά πλεονεκτήματα σε σχέση με τις προηγούμενες, μπορούν να συνδυαστούν με αυτές, αλλά απαιτούν την ανάπτυξη κατάλληλης άλγεβρας για τα μοντέλα FARΜΑX. Επίσης, μελετώνται ζητήματα όπως η συνέπεια και η ασυμπτωτική κατανομή της εκτιμήτριας σφάλματος πρόβλεψης. Η αποτίμηση όλων των μεθόδων εκτίμησης πραγματοποιείται μέσω προσομοιώσεων Monte Carlo. Τέλος, στα πλαίσια της παρούσας διατριβής αναπτύσσεται καινοτόμος μεθοδολογία ανίχνευσης, προσδιορισμού και εκτίμησης βλαβών σε δυναμικά συστήματα, η οποία βασίζεται στις νέες κλάσεις στοχαστικών συναρτησιακών μοντέλων των προηγούμενων κεφαλαίων. Η αποτίμηση της μεθοδολογίας πραγματοποιείται μέσω πειραματικής εφαρμογής σε διεθνές πρότυπο σκελετού αεροσκάφους υπό κλίμακα, όπου επιτυγχάνει με μεγάλη ακρίβεια, ανίχνευση, προσδιορισμό και εκτίμηση όλων των τύπων και μεγεθών βλάβης και επιπλέον ξεπερνά δυσκολίες που αντιμετωπίζουν άλλες τεχνικές της βιβλιογραφίας. / The aim of the present dissertation is the development of a new class of externally dependent stochastic functional models for the identification of dynamical systems under multiple operating conditions, which are defined by an external measurable variable (i.e. temperature, humidity, etc). The development of a novel methodology for fault diagnosis (fault detection, identification and estimation) in dynamical systems based upon the stochastic functional models is also an additional aim. The development of a proper method for fault detection, identification and estimation in structures under earthquake excitation is initially achieved. The method’s assessment was the motivation for the development of a novel methodology, which is based upon a new class of externally dependent stochastic functional models. These models are capable of accurately representing a structure for a certain type of fault in a continuous range of magnitudes by using a single mathematical representation parameterized in terms of the fault magnitude. It is noticed that such models are not referred in the literature until now. The most related families of models are found in sciences of statistics and econometrics. These models are mathematical representations without functional form and they are incapable of covering continuous ranges of values. Due to this fact, the new class of externally dependent stochastic Functional (F) AutoRegressive (AR) with eXogenous (X) excitation models, with parameters and innovations variance expressed as functions of a measurable external variable, is defined in the sequel of the dissertation. This functional dependence offers to the new class of models the important advantage of being used for: a) the identification of dynamical systems under multiple operating conditions which are defined by an external measurable variable and, b) fault detection, identification and estimation in stochastic dynamical systems where the external variable is the fault magnitude. Proper methods for FARX estimation are also developed and studied and their assessment is achieved via Monte Carlo simulations. In the following, the new class of externally dependent stochastic Functional (F) AutoRegressive (AR) Moving Average (MA) with eXogenous (X) excitation models, with parameters and innovations variance expressed as functions of a measurable external variable, is defined. The FARMAX models offer extra flexibility due to the MA part. Proper methods for FARMAX estimation, which are based upon the Maximum Likelihood and the Prediction Error principles, are also developed. Two further estimation methods are also formulated which are based upon minimization of the prediction error via successive linear stages. These methods offer some practical advantages comparing with the previous methods, they can be combined with the latter but they require the development of a proper algebra for FARMAX models. Additionally, the consistency and the asymptotic distribution of the prediction error estimator are considered. The assessment of all estimation methods is achieved via Monte Carlo simulations. In the last part of the dissertation a novel methodology for fault detection, identification and estimation in dynamical systems, which is based upon the new class of stochastic functional models of the previous chapters, is developed. The methodology’s assessment is accomplished via an experimental application in a prototype scale aircraft skeleton structure, where it achieves accurate fault detection, identification and estimation of several kinds and magnitudes of faults and also overcomes difficulties that are referred by other methods.