Σε αυτή τη διπλωματική εργασία μελετάμε το πρόβλημα εύρεσης ενός Nash σημείου ισορροπίας για παίγνια δύο παικτών. Παρουσιάζεται ο αλγόριθμος Lemke - Howson, η πολυπλοκότητα του αλγορίθμου καθώς και η κλάση πολυπλοκότητας PPAD, όπου και αποδεικνύεται ότι το πρόβλημα εύρεσης ενός Nash σημείου ισορροπίας είναι πλήρες για την κλάση αυτή. Αναλυτικότερα, στο πρώτο κεφάλαιο γίνεται μία σύντομη ιστορική αναδρομή της θεωρίας παιγνίων, παρουσιάζονται κάποιες βασικές έννοιες και προτείνονται κάποιες καταστάσεις ως λύσεις ενός παιγνίου, με κύρια αυτή του Nash σημείου ισορροπίας. Το δεύτερο κεφάλαιο ασχολείται με τα παίγνια δύο παικτών ή παίνγια διπίνακα. Αρχικά ορίζονται τα στοιχεία που συνιστούν το παίγνιο, δηλαδή οι παίκτες, οι στρατηγικές τους, η βέλτιστη απόκριση και το Νash σημείο ισορροπίας και παρουσιάζονται με τη βοήθεια ενός παραδείγματος. Στη συνέχεια, ορίζονται τα πολύεδρα και τα πολύτοπα βέλτιστης απόκρισης με βάση τους πίνακες κερδών των δύο παικτών, που αποτελούν και βάση του αλγορίθμου Lemke - Howson. Στο τρίτο κεφάλαιο παρουσιάζεται αναλυτικά ο αλγόριθμος Lemkle - Howson στη γεωμετρική και στην αριθμητική του μορφή και εφαρμόζεται για ένα συγκεκριμένο παίγνιο. Η γεωμετρική εφαρμογή γίνεται με τη βοήθεια των πολυτόπων βέλτιστης απόκρισης και η αριθμητική μέσω του ακέραιου pivoting, που είναι μια παραλλαγή της μεθόδου simplex. Στο τέταρτο κεφάλαιο μελετάται μία κατηγορία παιγνίων όπου ο αλγόριθμος δεν είναι αποδοτικός. Για την κατασκευή των παιγνίων της κατηγορίας αυτής χρειάζεται πρώτα να δούμε τα κυκλικά πολύτοπα και να παρουσίασουμε κάποιες ιδιότητές τους. Στη συνέχεια αποδεικνύεται ότι ο αλγόριθμος απαιτεί εκθετικό χρόνο μέχρι να καταλήξει σε ένα Nash σημείο ισορροπίας του παιγνίου, σε σχέση με το μέγεθος του παιγνίου. Στο πέμπτο κεφάλαιο παρουσιάζεται μία αναγωγή του προβλήματος της εύρεσης ενός Nash σημείου ισορροπίας ενός παιγνίου δύο παικτών σε αυτό του πλήρους ταιριάσματος ενός γραφήματος, όπου και πάλι χρησιμοποιούμε ιδιότητες των πολυτόπων βέλτιστης απόκρισης καθώς και των δεικτοδοτημένων συμβολοσειρών Gale. Το έκτο και τελευταίο κεφάλαιο ασχολούμαστε με την κλάση πολυπλοκότητας PPAD. Αρχικά, ορίζουμε την κλάση και δίνουμε το πλήρες πρόβλημα οδηγό για την κλάση αυτη, το END OF LINE. Στη συνέχεια, δίνουμε μια διαισθητική αναγωγή του παραπάνω προβλήματος στο πρόβλημα SPERNER και έπειτα του SPERNER στο πρόβλημα BROUWER που πρόκειται για μία διακριτοποιημένη και απλόποιημένη εκδοχή της εύρεσης ενός σταθερού σημείου μίας συνάρτησης f. H τελευταία αναγωγή είναι αυτή του BROUWER στο 2NASH, δηλαδή την εύρεση ενός Nash σημείου ισορροπίας σε ένα παίγνιο δύο παικτών. Με αυτό τον τρόπο αποδεικνύεται ότι το 2NASH είναι PPAD πλήρες και δεν υπάρχει πολυωνυμικός αλγόριθμος για το πρόβλημα αυτό εκτός και αν P = PPAD. Στο τέλος της εργασίας υπάρχουν δύο παραρτήματα, όπου στο πρώτο παρουσιάζονται τα μονοπάτια που κατασκευάζει ο αλγόριθμος Lemke - Howson και κάποιες ιδιότητες αυτού και στο δεύτερο παράρτημα παρουσιάζεται ένα παράδειγμα κατασκευής ενός παιγνίου όπου ο αλγόριθμος δεν είναι αποδοτικός, παρατίθεται ο κώδικας σε MATLAB για την παραγωγή των παιγνίων της κλάσης αυτής και παρουσιάζονται τα μήκη των μονοπατιών που κατασκευάζει ο αλγόριθμος παίγνια της κλάσης. / In this thesis we study the problem of finding a Nash equilibrium for bimatrix games. We describe Lemke - Howson algorithm and its complexity. Also we study the PPAD complexity class and we give the reduction which shows that the problem of finding a Nash equilibrium (NASH) is PPAD complete even for bimatrix games. In section 1, we give a short history view of game theory and some essential notions about games, players and game solutions such as Nash equilibrium. In section 2, we define bimatrix games: each player's strategies, payoffs, mixed strategies, best response, Nash equilibria and we demonstrate all of them with an example. After that, we present best response polyhedra and best response polyhedra in which the Lemke - Howson algorithm is based. In section 3, we discribe in detail Lemke - Howson algorithm intuitively, by mones on best response polytopes, and arithmetically, by integer pivoting, which is a variant of simplex method. In section 4, is described a class of games where Lemke - Howson needs exponetial time to find a Nash equilibrium. For the construction of the games we use cyclic polytopes and the Gale evenness condition and their properties. We show in detail the Lemke - Howson paths and we compute their lengths for each dropped label. In section 5, we give a reduction from Perfect Matching to Nash equilibrium for a special case of games and we show that at these games a Nash equilibrium can be computed in polynomial time. In the final section we study the complexity class PPAD. First of all, we define formally the class and we give the first complete problem for this class, END OF LINE. After that, we reduce END OF LINE to SPERNER and SPERNER to BROUWER which is a simplified, discretized version of finding a fixed point for a continuous function f . Finally, we give in detail the reduction from BROUWER to 2NASH and we show that 2NASH is PPAD-complete which means that there is no polynomial time algorithm for 2NASH unless P = PPAD. At the end there are two appendices: At the first one we demonstrate the LH paths and at the second we give the source code in MATLAB for the construction of payoff tables for the LH worst case.

Η παρούσα διδακτορική διατριβή ασχολείται με την εφαρμογή της υπολογιστικής νοημοσύνης στη μουσική, επιχειρώντας ταπεινά να συνεισφέρει, έστω και κατ' ελάχιστο, στην μακραίωνη πορεία της σύζευξης των μουσικών εννοιών με τα μαθηματικά. Οι τρεις πυλώνες πάνω στους οποίους στηρίζεται αυτή η διατριβή αφορούν τη χρήση μεθόδων υπολογιστικής νοημοσύνης για α) την εξέταση των μαθηματικών μουσικών χαρακτηριστικών με στόχο την επιτυχή κατηγοριοποίηση, αναγνώριση και χαρακτηρισμό περιεχομένου σε μουσικά κομμάτια, β) την ευφυή αυτόματη σύνθεση μουσικής βάσει μαθηματικών μουσικών χαρακτηριστικών και γ) τη διαδραστική ευφυή σύνθεση μουσικής και τις επεκτάσεις της. Ενώ οι τρεις αυτοί πυλώνες φαίνονται επιφανειακά ασύνδετοι, το κοινό τους θεμέλιο είναι τα μαθηματικά μουσικά χαρακτηριστικά και ο ρόλος που αυτά διαδραματίζουν έτσι ώστε να αναπτυχθούν μοντέλα υπολογιστικής νοημοσύνης που τελικά προσομοιάζουν τον τρόπο που οι άνθρωποι ``αντιλαμβάνονται'' τη μουσική. Το γεγονός ότι όλοι οι δίαυλοι έρευνας που παρουσιάζονται σε αυτή τη διατριβή διοχετεύονται στο ίδιο κανάλι, γίνεται φανερό στο τελευταίο κεφάλαιο (Κεφάλαιο 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.

Στην εργασία περιγράφεται η διαδικασία εξοικείωσης των μαθητών με το εκπαιδευτικό πακέτο της Αλγοριθμικής και τον προγραμματισμό μέσω μελέτης περίπτωσης ενός τμήματος ενιαίου Λυκείου. Η Αλγοριθμική είναι ένα ολοκληρωμένο πακέτο προγραμματιστικών περιβαλλόντων και εργαλείων για τη διδακτική υποστήριξη σεναρίων και δραστηριοτήτων ενταγμένων στα μαθήματα Πληροφορικής της Γ’ Γυμνασίου και των Α’, Β’ και Γ’ Λυκείου. Το περιβάλλον αυτό χρησιμοποιήθηκε για τη διδασκαλία της αλγοριθμικής σκέψης και του προγραμματισμού σε ένα τμήμα της Α’ τάξης ενιαίου Λυκείου. Στην εργασία παρουσιάζονται τα κυριότερα λάθη των μαθητών τόσο στο Δημιουργό Διαγραμμάτων Ροής όσο και στο Διερμηνευτή της Γλώσσας σε αρχικό στάδιο διδασκαλίας όσο και σε πιο προχωρημένο με τη χρήση της δομής επιλογής και συγκεκριμένα εμφωλευμένων ΑΝ. Κρίνεται η αποδοτικότητα των σεναρίων χρήσης της Αλγοριθμικής και γίνονται ορισμένες προτάσεις για τη βελτίωσή τους, καθώς και τη βελτίωση των εργαλείων ΔΔΡ και Διερμηνευτής της Γλώσσας για την καλύτερη χρήση από τους μαθητές. Τέλος, παρουσιάζονται κάποιες υλοποιήσεις μαθητών που είχαν καλή δομή κώδικα και ιδιαίτερη εφευρετικότητα. / The work describes the process of introducing students to computer programming and in particular with the educational package “Algorithmic”, through case study of a single Secondary School classroom. “Algorithmic” is a complete package of programming environments and tools to support teaching scenarios and integrated activities in Secondary School computer classrooms. This package was used in teaching algorithmic thinking and computer programming in a classroom of first grade Secondary School. The paper describes the main errors of students when creating flowcharts as well as computer programs using the software tool “GLOSSA”, in earlier teaching stages and later with the use of more advanced decision structures like nested IF statements. This work studies the efficiency of the usage scenarios of “Algorithmic” and makes suggestions for improving the software tools “flowchart” and “GLOSSA” to be more suitable to the level of students and to the course goals. Finally, the paper presents some well structured programming implementations of students.