This purpose of this thesis is to explore the relationship between idiomatic knowledge and second language proficiency. As the amount of research directly related to this topic is sparse, an in-depth discussion of relevant research and definitions comprises the first part of this paper. Two studies are then presented here that test the relationship between idiomatic knowledge and second language proficiency. A new definition for idioms proposes that all non-compositional phrases, popularized by usage, that is stored, retrieved, and employed as a single lexical unit. The results from more than 400 participants across two studies indicate that the two constructs are strongly correlated, but that the observable relationship between them is only modest. Additional results from the two studies also indicate that idiomatic knowledge is more strongly correlated with speaking skill than with writing or reading skills. The impacts of this study on existing research are discussed and directions for new research is suggested.

Spectral properties of integral operators on spaces of analytic functions on the unit disk of the complex plane have been studied since 1918. In this dissertation we determine spectral pictures and resolvent estimates for Ces`aro-like operators on the weighted Bergman spaces and show in particular that some of these operators are subdecomposable. Moreover, in a special case, we show that some of these operators are subnormal, some are normaloid, and some are subscalar. We also determine the spectrum and essential spectrum as well as resolvent estimates for a class of integral operators acting on Banach spaces of analytic functions on the unit disk, including the classical Hardy and weighted Bergman spaces, analytic Besov spaces as well as certain Dirichlet spaces and generalized Bloch spaces. Our results unify and extend recent work by Aleman and Persson, [4], Ballamoole, Miller and Miller, [6], and Albrecht and Miller, [3]. In [3], another class of integral operators were investigated in the setting of the analytic Besov spaces and the little Bloch space where the spectra, essential spectra together with one sided analytic resolvents in the Fredholm regions of these operators were obtained along with an explicit strongly decomposable operator extending one of these operator and simultaneously lifting the other. In this disseration, we extend this spectral analysis to nonseparable generalized Bloch spaces using a modification of a construction due to Aleman and Persson, [4].

Field observation and manipulative experiments were carried out to describe and test important processes affecting the plant succession on Sokolov post-mining sites. Examined was mainly effect of dominant tree species (which are planted or spontaneously established) on understory plants, litter decomposability and effect of earthworms (Lumbricidae) on late successional plant species.

京都大学 / 0048 / 新制・課程博士 / 博士(理学) / 甲第21531号 / 理博第4438号 / 新制||理||1638(附属図書館) / 京都大学大学院理学研究科数学・数理解析専攻 / (主査)准教授 COLLINS Benoit Vincent Pierre, 教授 堤 誉志雄, 教授 泉 正己 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DFAM

This dissertation is concerned with problem-solving in platform development. A problem isconceived of as an obstacle that needs to be overcome in order to reach a desired outcome,whereas a solution is denoted by the set of activities required to reach such an outcome. Aplatform is conceived of as the technological foundation made up of a number of elements thatare purposely planned and developed to form a common structure from which a stream ofderivative products can be developed. Problem-solving in platform development is a non-trivialtask since platforms need to cater for both commonality and distinctiveness across a number ofderivative products. Further, several design architectures are intertwined in the development ofplatforms, giving rise to increased complexity. The purpose of this dissertation is to exploreplatform development from a problem-solving perspective, with the purpose of answering whatproblem-solving activities are carried out in platform development processes, how are differentapproaches to the search for solutions related to problem-solving in platform development, andhow can problem-solving in platform development be conceptualized? This dissertation is basedon two empirical studies of platform development processes from the telecommunication andautomotive industry, and draws upon a qualitative research methodology. The result of this studyis an iterative and dynamic model of solution search in problem-solving. This dissertationimplies a distinction between problems and errors in platform development. Solution searchemerge as a matter of choice of whether to engage in problem-solving activities and/or errorcorrection activities during the development of platforms. Solution search also surface as anintermingled process of search for required inputs, outputs, or governing laws (i.e. solutions) forreaching a desired goal. In this process, analytical search, directional search, and synthesizedsearch and the facilitation and management of both feed-back and feedforward is important. / Denna avhandling berör problemlösning i plattformsutvecklingsprocesser. Ett problem avser etthinder som måste övervinnas för att nå ett önskat resultat, medan en lösning betecknas med deaktiviteter som krävs för att nå ett sådant resultat. Med plattform avses den teknologiska grund,bestående av ett antal element, som är avsiktligt planerade och utvecklade för att bilda engemensam struktur via vilken en ström av olika produkter kan utvecklas. Problemlösning iutvecklandet av plattformar är en icke-trivial uppgift eftersom plattformar måste tillgodose bådegemensamhet och särprägel i ett antal produkter. Vidare så är flera designarkitekturersammanflätade i utvecklandet av plattformar, vilket ger upphov till ökad komplexitet. Syftet meddenna avhandling är att undersöka plattformsutveckling från ett problemlösningsperspektiv, isyfte att svara på vilka problemlösningsaktiviteter som bedrivs i plattformutvecklingsprocesser,hur olika strategier för att söka efter lösningar i samband med problemlösning iplattformsutveckling är relaterade till varandra, samt hur problemlösning i plattformsutvecklingkan föreställas. Denna avhandling bygger på två empiriska studier av plattformsutvecklingsprocesseri telekommunikation och fordonsindustrin, och bygger på en kvalitativforskningsmetodik. Resultatet av denna undersökning är en iterativ och dynamisk modell förlösningsökning. Denna avhandling föreslår en skillnad mellan ett problem och ett fel iutvecklandet av telekommunikationsplattformar och fordonsplattformar. Lösningssökandeframstår som ett val mellan att engagera sig i problemlösning eller/och felkorrigering underutvecklandet av plattformar. Lösningssökande framstår också som en sammansmält process avsökande efter nödvändig input, output och de styrande lagar (dvs. lösningar) för att nå ett önskatmål. I denna process är analytisk sökande, riktat sökande, syntetiserad sökande, ochförvaltningen av både återkoppling och framåtkopplingning viktig.

Σκοπός της παρούσας διπλωματικής εργασίας είναι η μελέτη της θεωρίας της Near Complete Decomposability (NCD) και η εφαρμογή της στην ανάλυση της απόδοσης ενός υπολογιστικού συστήματος, του οποίου η μοντελοποίηση με παραδοσιακές τεχνικές οδηγεί σε απαγορευτικά μεγάλο χώρο κατάστασης. Αρχικά, παραθέτουμε τα βασικά σημεία της θεωρίας όπως αυτή θεμελιώνεται μαθηματικά από τον Courtois στην κλασική του μονογραφία (Courtois, 1977), ενώ στη συνέχεια προβαίνουμε στη μοντελοποίηση ενός υποθετικού σταθμού εργασίας κάποιου πολυεπεξεργαστικού συστήματος, στο οποίο εκτελούνται ανά πάσα στιγμή το πολύ Κ έργα. Ο σταθμός εργασίας που μελετάμε διαθέτει buffer πεπερασμένου μεγέθους και είναι επιφορτισμένος με τη συγκέντρωση και το συνδυασμό των επιμέρους υποέργων κάθε έργου και την αποθήκευση του στη μνήμη. Οι κλασικές τεχνικές μοντελοποίησης του buffer οδηγούν σε ένα μοντέλο με πολύ μεγάλο χώρο κατάστασης. Ωστόσο εμείς μοντελοποιούμε μία συναθροιστική εκδοχή του αρχικού μοντέλου, η οποία υπό αρκετά ρεαλιστικές συνθήκες χαίρει της NCD ιδιότητας. Την ιδιότητα αυτή του μοντέλου μας τη δικαιολογούμε τόσο διαισθητικά, όσο και μαθηματικά. Επίσης, επιβεβαιώνουμε πως το NCD μοντέλο πετυχαίνει υψηλής ποιότητας εκτίμηση των πιθανοτήτων μόνιμης κατάστασης και μίας σειράς άλλων χρήσιμων μετρικών, με σημαντικά μικρότερο υπολογιστικό κόστος σε σχέση με το αρχικό μοντέλο, εκτελώντας μία σειρά μετρήσεων στο περιβάλλον Matlab. Παράλληλα, η αξιοποίηση του NCD μοντέλου αυξάνει σημαντικά την ικανότητά μας να ερμηνεύσουμε τη δυναμική συμπεριφορά του συστήματος καθώς αυτό οδεύει προς μια κατάσταση στατιστικής ισορροπίας. Τέλος, επιχειρούμε μία σειρά από “educated guesses” για πιθανές κλάσεις συστημάτων τα οποία θα μπορούσαν να αναλυθούν με μεθοδολογία αντίστοιχη με αυτήν που ακολουθήσαμε εμείς στο παρόν κείμενο. / The purpose of this diploma dissertation is, on one hand the brief study of the theory of Near Complete Decomposability (NCD), and on the other hand the application of NCD in the analysis of a system, the modeling of which leads to a prohibitively large state space. First, we point out the fundamental mathematical principles of NCD as established by Courtois in his classic monograph (Courtois, 1977). Then, we proceed to the modeling of a hypothetical service station (R) of a multiprocessing computer system, which executes at most K jobs simultaneously. R has a finite buffer and its duty is to combine the arriving tasks into a single job and store it to memory. The usual modeling techniques applied to this “task buffer”, lead to a model with extremely large state space. So, we construct a lumped model instead, which enjoys the property of NCD. We prove this, using intuitive arguments as well as mathematical ones. Then, we confirm that the NCD model achieves a reliable estimation of the steady state probability vector and other important metrics, with significantly reduced computational complexity in comparison with the initial model. Furthermore, the exploitation of the NCD model increases significantly our ability to understand the dynamics of our system and to interpret aspects of its transient behavior towards statistical equilibrium. Finally, we make a number of “educated guesses” about possible classes of systems that could be analyzed using the same kind of techniques we used in this dissertation.

Le but de cette thèse était de comprendre les liens entre deux processus de dégradation de la matière organique : la digestibilité du fourrage par les herbivores domestiques et la décomposabilité de la litière par la microfaune du sol. Nous avons fait les hypothèses suivantes : (i) les pratiques de gestion affectent la digestibilité et la décomposabilité des espèces, et (ii) en accord avec l’hypothèse de dominance, celles des communautés via des changements de leur structure fonctionnelle ; (iii) digestibilité et décomposabilité peuvent être estimées par un même « marqueur fonctionnel » facile à mesurer aux niveaux d’organisation de l’espèce et de la communauté. Ce travail a été réalisé dans des parcours du domaine expérimental de La Fage situés sur le Causse du Larzac (Aveyron). Nos résultats ont montré un effet des pratiques de gestion sur la digestibilité et la décomposabilité des différents organes (feuille, tige, partie reproductrice) : les espèces de parcours pâturés et fertilisés ont présenté une digestibilité et décomposabilité supérieures à celles des espèces de parcours uniquement pâturés. Des mesures effectuées à deux dates de récolte ont permis de mettre en évidence une baisse de digestibilité au cours du printemps dans les différents organes, principalement causée par une augmentation de leur teneur en fibre. Une relation positive entre digestibilité et décomposabilité a été montrée pour les feuilles et les tiges dans les deux types de parcours. Cette relation était fortement dépendante de la teneur en fibres des organes, qui peut être estimée de façon fiable par la teneur en matière sèche de ceux-ci : plus la teneur en fibres était élevée, plus la teneur en matière sèche était forte, induisant une faible digestibilité et une faible décomposabilité. Ces résultats ont également été démontrés à l’échelle des communautés pour la digestibilité et la décomposabilité, confirmant l’hypothèse de dominance : les propriétés des écosystèmes peuvent être prédites à partir de traits des espèces dominantes des différents parcours, et en particulier de leur teneur en matière sèche. La teneur en matière sèche est donc un marqueur puissant et facile à mesurer pour estimer la digestibilité et la décomposabilité de systèmes complexes. L’approche fonctionnelle de la diversité biologique basée sur les traits peut donc être utilisée comme un outil de diagnostic du fonctionnement des prairies permanentes afin d’adapter les pratiques de gestion selon les objectifs des éleveurs. / The aim of this thesis was to understand links between two degradation processes of organic matter: the forage digestibility by domestic herbivores and the decomposability of litter by soil microfauna. We hypothesized that: (i) management regimes influenced species digestibility and decomposability, and (ii) in agreement with the dominance hypothesis, those of communities through changes in their functional structure; (iii) digestibility and decomposability can be estimated by the same “functional marker” both at the species and community levels. This study was conducted in rangelands from the La Fage research station located on the Larzac Causse (Aveyron). Our results showed an effect of management regimes on the digestibility and decomposability of different organs (leaf, stem, reproductive part): species from grazed and fertilized grasslands had higher digestibility and decomposability than those from grasslands solely grazed. Measurements conducted at two harvest dates showed a decrease of digestibility of the different organs during spring, mostly due to an increase in fibre concentration. A positive relationship between digestibility and decomposability was found for leaves and stems in both management regimes. This relationship was strongly dependent on organ fibre content, which could be safely estimated by the dry matter content of these different organs: the higher their concentration in structural tissues, the higher their dry matter content, and the lower their digestibility and decomposability. These results were also found at the community level for both properties, thereby validating the dominance hypothesis: the digestibility and decomposability of communities could be predicted from the traits of dominant species found in each management regime, in particular their dry matter content. Dry matter content therefore appears as a powerful and easy to measure marker to estimate the digestibility and decomposability of complex systems. The trait-based approach to plant functional diversity can be used as a diagnostic tool to assess rangeland functioning, so as to modulate management practices according to farmer’s objectives.

Σκοπός της παρούσας διπλωματικής διατριβής είναι η μελέτη και ανάπτυξη ενός νέου αλγοριθμικού πλαισίου Συνεργατικής Διήθησης(CF) για την παραγωγή συστάσεων. Η μέθοδος που προτείνουμε, βασίζεται στην εκμετάλλευση της ιεραρχικής διάρθρωσης του χώρου αντικειμένων και πατά διαισθητικά στην ιδιότητα της ``Σχεδόν Πλήρης Αναλυσιμότητας'' (NCD) η οποία είναι συνυφασμένη με τη δομή της πλειοψηφίας των ιεραρχικών συστημάτων. Η Συνεργατική Διήθηση αποτελεί ίσως την πιο πετυχημένη οικογένεια τεχνικών για την παραγωγή συστάσεων. Η μεγάλη απήχησή της στο διαδίκτυο αλλά και η ευρεία εφαρμογή της σε σημαντικά εμπορικά περιβάλλοντα, έχουν οδηγήσει στη σημαντική ανάπτυξη της θεωρίας την τελευταία δεκαετία, όπου μια ευρεία ποικιλία αλγορίθμων και μεθόδων έχουν προταθεί. Ωστόσο, παρά την πρωτοφανή τους επιτυχία οι CF μέθοδοι παρουσιάζουν κάποιους σημαντικούς περιορισμούς συμπεριλαμβανομένης της επεκτασιμότητας και της αραιότητας των δεδομένων. Τα προβλήματα αυτά επιδρούν αρνητικά στην ποιότητα των παραγόμενων συστάσεων και διακυβεύουν την εφαρμοσιμότητα πολλών CF αλγορίθμων σε ρεαλιστικά σενάρια. Χτίζοντας πάνω στη διαίσθηση πίσω από τον αλγόριθμο NCDawareRank - μίας γενικής μεθόδου υπολογισμού διανυσμάτων κατάταξης ιεραρχικά δομημένων γράφων - και της σχετικής με αυτόν έννοιας της NCD εγγύτητας, προβαίνουμε σε μία μοντελοποίηση του συστήματος με τρόπο που φωτίζει τα ενδημικά του χαρακτηριστικά και προτείνουμε έναν νέο αλγοριθμικό πλαίσιο συστάσεων, τον Αλγόριθμο 1. Στο επίκεντρο της προσέγγισής μας είναι η προσπάθεια να συνδυάσουμε τις άμεσες με τις NCD, ``γειτονιές'' των αντικειμένων ώστε να πετύχουμε μεγαλύτερης ακρίβειας χαρακτηρισμό των πραγματικών συσχετισμών μεταξύ των στοιχείων του χώρου αντικειμένων, με σκοπό την βελτίωση της ποιότητας των συστάσεων αλλά και την αντιμετώπιση της εγγενούς αραιότητας και των προβλημάτων που αυτή συνεπάγεται. Για να αξιολογήσουμε την απόδοση της μεθόδου μας υλοποιούμε και εφαρμόζουμε τον Αλγόριθμο 1 στο κλασικό movie recommendation πρόβλημα και παραθέτουμε μια σειρά από πειράματα χρησιμοποιώντας τo MovieLens Dataset. Τα πειράματά μας δείχνουν πως ο Αλγόριθμος 1 με την εκμετάλλευση της ιδέας της NCD εγγύτητας καταφέρνει να πετύχει λίστες συστάσεων υψηλότερης ποιότητας σε σύγκριση με τις άλλες state-of-the-art μεθόδους που έχουν προταθεί στη βιβλιογραφία, σε ευρέως χρησιμοποιούμενες μετρικές (micro- και macro-DOA), αποδεικνύοντας την ίδια στιγμή πως είναι λιγότερο επιρρεπής στα προβλήματα που σχετίζονται με την αραιότητα και έχοντας παράλληλα ανταγωνιστικό προφίλ πολυπλοκότητας και απαιτήσεις αποθήκευσης. / The purpose of this master's thesis is to study and develop a new algorithmic framework for collaborative filtering (CF) to generate recommendations. The method we propose is based on the exploitation of the hierarchical structure of the item space and intuitively ``stands'' on the property of Near Complete Decomposability (NCD) which is inherent in the structure of the majority of hierarchical systems. Collaborative Filtering is one of the most successful families of recommendations methods. The great impact of CF on Web applications, and its wide deployment in important commercial environments, have led to the significant development of the theory, with a wide variety of algorithms and methods being proposed. However, despite their unprecedented success, CF methods present some important limitations including scalability and data sparsity. These problems have a negative impact of the quality of the recommendations and jeopardize the applicability of many CF algorithms in realistic scenarios. Building on the intuition behind the NCDawareRank algorithm and its related concept of NCD proximity, we model our system in a way that illuminates its endemic characteristics and we propose a new algorithmic framework for recommendations, called Algorithm 1. We focus on combining the direct with the NCD `` neighborhoods'' of items to achieve better characterization of the inter-item relations, in order to improve the quality of recommendations and alleviate sparsity related problems. To evaluate the merits of our method, we implement and apply Algorithm 1 in the classic movie recommendation problem, running a number of experiments on the standard MovieLens dataset. Our experiments show that Algorithm 1 manages to create recommendation lists with higher quality compared with other state-of-the-art methods proposed in the literature, in widely used metrics (micro- and macro- DOA), demonstrating at the same time that it is less prone to low density related problems being at the same time very efficient in both complexity and storage requirements.

Το θέμα της παρούσας μεταπτυχιακής διπλωματικής εργασίας είναι η εφαρμογή της θεωρίας των Σχεδόν Πλήρως Αναλυόμενων Στοχαστικών Συστημάτων (Nearly Completely Decomposable) σε μία σειρά προβλημάτων στα οποία παραδοσιακές προσεγγίσεις αποδεικνύονται ερμηνευτικά στείρες και υπολογιστικά κοστοβόρες. Στο πρώτο μέρος της διπλωματικής αφού κάνουμε μία διαισθητικού τύπου παρουσίαση της ιδέας της decomposability και συνοψίσουμε τα απαραίτητα στοιχεία του θεωρητικού υποβάθρου που χρησιμοποιούμε στα πλαίσια της εργασίας, παραθέτουμε τονπυρήνα της θεωρίας της decomposability, όπως αυτή θεμελιώνεται μαθηματικά από τον Courtois στην κλασική του μονογραφία. Τέλος, παραθέτουμε και μία υλοποίηση του KMS αλγορίθμου Συσσωμάτωσης/Αποσυσσωμάτωσης, για τη λύση NCD συστημάτων. Το δεύτερο μέρος του συγγράμματος, είναι αφιερωμένο στην εφαρμογή της NCD σε δύο ενδιαφέροντα προβλήματα εκτίμησης απόδοσης υπολογιστικών συστημάτων. Συγκεκριμένα, μελετούμε μία ιδιότυπη ουρά που εξυπηρετεί πελάτες διαφορετικών κλάσεων, με τις ανά κλάση αφίξεις να χαρακτηρίζονται από εναλλαγές μεταξύ περιόδων ηρεμίας και κινητικότητας και την εξυπηρέτηση να γίνεται σε δέσμες πελατών της ίδιας κλάσης. Το κίνητρο για τη μελέτη αυτής της ουράς εντοπίζεται στη bursty φύση της μεταγωγής πακέτων στα σύγχρονα δίκτυα αλλά και στους reassembly buffers των multicluster πολυεπεξεργαστικών συστημάτων. Η ανάλυση της ουράς με παραδοσιακές τεχνικές οδηγεί αναπόφευκτα σε μαρκοβιανή αλυσίδα πολύ μεγάλου χώρου κατάστασης. Εμείς, ξεκινάμε από το πλήρες στοχαστικό μητρώο και αφού διαμερίσουμε κατάλληλα το χώρο καταστάσεων, αποδεικνύουμε ικανές συνθήκες υπό τις οποίες το αρχικό σύστημα είναι δυνατόν να αναλυθεί σε πολλαπλά επίπεδα υποσυστημάτων, η αυτόνομη ανάλυση των οποίων δίνει μία πολύ καλή προσέγγιση της στάσιμης κατανομής του αρχικού συστήματος. Επίσης, παραθέτουμε και αποδεικνύουμε μία ικανή συνθήκη για μηδενικό σφάλμα προσέγγισης και την ερμηνεύουμε σε όρους προδιαγραφών του προβλήματος. Τέλος, θεωρούμε μία ειδική συμμετρική εκδοχή για την οποία καταφέρνουμε να δώσουμε μία κλειστή έκφραση της κατανομής πληρότητας της ουράς συναρτήσει της λύσης των υποσυστημάτων. Για να δείξουμε την απλοποίηση της ανάλυσης που επιφέρει η χρήση του NCD μοντέλου θεωρούμε ένα σενάριο για το οποίο προχωρούμε την ανάλυση σε βάθος και καταφέρνουμε να εξάγουμε χρήσιμες μετρικές στις οποίες, σε αντίθετη περίπτωση, θα ήταν ιδιαίτερα επίπονο να καταλήξει κανείς. Συγκεκριμένα, υπολογίζουμε την πιθανότητα blocking και δείχνουμε πως αυτή μειώνεται σχεδόν εκθετικά με το μέγεθος της ουράς. Βλέπουμε τελικά πως η εκμετάλλευση της NCD ιδιότητας από τη μία διευκολύνει την ανάλυση και από την άλλη παρέχει ανεκτίμητη διαίσθηση σχετικά με τη μεταβατική συμπεριφορά του συστήματος προς την κατάσταση στατιστικής ισορροπίας. Το δεύτερο μέρος της διπλωματικής κλείνει με τη μελέτη κριτηρίων υπό τα οποία, πολυεπεξεργαστικά συστήματα που χωρίζονται σε ομάδες ισχυρά αλληλεπιδρώντων επεξεργαστών, μπορούν να αναλυθούν με χρήση της θεωρίας NCD. Είναι γνωστό πως στα δίκτυα ουρών αναμονής συγκρίσιμων ρυθμών εξυπηρέτησης, η NCD του μητρώου πιθανοτήτων δρομολόγησης συνεπάγεται την NCD του δικτύου. Εμείς, θεωρούμε μία ειδική περίπτωση τέτοιων συστημάτων για την οποία δείχνουμε ένα, εύκολο να ελεγχθεί, κριτήριο για NCD. Τέλος, εξετάζουμε βαθύτερα το σφάλμα της προσέγγισης, και χρησιμοποιώντας ένα πρόσφατο αποτέλεσμα της θεωρίας των σχεδόν ασύζευκτων μαρκοβιανών αλυσίδων δίνουμε έναν επιπλέον ποιοτικό περιορισμό που πρέπει να ικανοποιούν τα εν λόγω συστήματα για να πάρει κανείς ικανοποιητική προσέγγιση από την ανάλυσή τους σε ανεξάρτητα block. Στο τρίτο μέρος της παρούσας εργασίας, εξετάζουμε την εφαρμογή της NCD στο πρόβλημα της κατάταξης ιστοσελίδων. Η πρόσφατη έρευνα έχει σχολιάσει την ειδική δομή του στοχαστικού μητρώου που προκύπτει από το γράφο του διαδικτύου· συγκεκριμένα, οι τοπολογικές ιδιότητες της αυτοoργάνωσης του Ιστού φαίνεται να παράγουν ένα στοχαστικό μητρώο με NCD δομή. Εμείς, αφού παραθέσουμε μία σύνοψη των μαθηματικών πίσω από τον αλγόριθμο PageRank, σχολιάζουμε και δικαιολογούμε διαισθητικά την NCD δομή του Ιστού αλλά και τη φύση των υποσυστημάτων. Τέλος, προτείνουμε έναν νέο αλγόριθμο κατάταξης με το όνομα NCDawareRank, o οποίος εκμεταλλεύεται την NCD ιδιότητα για να πετύχει ποιοτικότερο και ταχύτερο ranking. Μάλιστα, δίνουμε δύο εκδοχές του αλγορίθμου, μία σειριακή και μία παράλληλη, η οποία εκμεταλλεύεται την NCD του Ιστού και υπολογιστικά. Τα οφέλη που υπόσχεται ο NCDawareRank τα επιβεβαιώνουμε και πειραματικά εκτελώντας μία σειρά από πειράματα τόσο σε τεχνητά όσο και σε πραγματικά δεδομένα, αντιπαραβάλλοντας τα αποτελέσματα μας με αυτά του αλγορίθμου PageRank. O NCDawareRank φαίνεται μάλιστα να δίνει λύση σε ένα γνωστό πρόβλημα του PageRank: αυτό της μεροληψίας εναντίον νεοεισερχομένων σελίδων. Άλλο ένα, τέλος, παράπλευρο όφελος του αλγορίθμου NCDawareRank είναι αυτό της Levelwise κατάταξης, η οποία εκτός της σημασίας που έχει αφεαυτής, μπορεί να υποδείξει εξυπνότερο crawling ή ακόμα και αποδοτικότερα σχήματα ευρετηριοποίησης του Ιστού. Στο τέταρτο και τελευταίο μέρος της διπλωματικής εφαρμόζουμε την NCD στην εύρεση των στοχαστικά ευσταθών καταστάσεων μίας κατηγορίας εξελικτικών παιγνίων στα οποία εμφανίζονται πολυεπίπεδες στρατηγικές δυναμικές. Αφού παραθέσουμε κάποιες πρόσφατες παρατηρήσεις από τη βιβλιογραφία της οικονομετρίας σχετικά με την αξιοποίηση της NCD στην προσεγγιστική ανάλυσή τους, αποδεικνύουμε συνθήκες υπό τις οποίες είναι δυνατόν να πετύχει κανείς ακριβή ανάλυση. / The purpose of this master’s thesis is the application of the theory of Nearly Completelely Decomposable stochastic systems to a number of interesting problems for which tra- ditional techniques turn out to be both intuitively unappealing and computationally in- tractable. In the first part of this work, after introducing, the concept of decomposability in an intuitive way and summarizing the essential elements of the theoretical background that is necessary to follow the rest of the text, we present the fundamental mathematical principles of NCD as established by Courtois in his classic monograph. Finally, we give an implementation of the KMS iterative aggregation/disaggregation algorithm which is commonly used for the solution of NCD systems. The second part of the dissertation is devoted to the application of NCD to two inter- esting problems of Computer Systems Performance Evaluation. Specifically, we study an uncommon discrete time queue that serves customers from different classes, with the ar- rivals of each class characterized by alternating busy and idle periods. The service is done in batches of customers of the same class. The motivation behind the study of this queue, lies in the bursty nature of packet switching, as well as in the modern reassembly buffers of multicluster multiprocessor systems. The traditional analysis techniques of this queue inevitably lead to Markov chains with very large state space. We begin with the complete stochastic matrix and after careful partitioning of the state space, we give sufficient condi- tions under which the original system can be analysed through multi level decomposition into subsystems, the autonomous analysis of which results in a very good approximation to the stationary distribution of the original system. Furthermore, we present and prove a sufficient condition for an error-free approximation and we give an interpretation of this condition in terms of the specifications of the problem. Finally, we consider a special sym- metric version of the problem, for which we manage to derive a closed-form expression for the queue’s occupancy distribution as a function of the steady state probabilities of the subsystems. To demonstrate the simplification of the analysis brought by the NCD model, we con- sider a scenario in which we proceed to an in depth analysis and we manage to extract useful metrics the derivation of which, would be considerably harder without exploiting 13 Abstract 14 NCD. Specifically, we calculate the blocking probability and we show that it decreases almost exponentially with the size of the queue. From our analysis, it is clear that the exploitation of the NCD model increases significantly our ability to understand the dy- namics of our system and to interpret aspects of its transient behaviour towards statistical equilibrium. The second part of this work ends with the study of criteria under which multipro- cessing systems, that can be divided into groups of strongly interacting processors, can be analysed using the theory of NCD. It is known that in queueing networks with servers of comparable service rates, the NCD of the routing probability matrix implies the NCD of the network. We consider a special case of such systems and we derive an easy to check criterion for NCD. Finally, we look deeper into the error analysis of this approach, and using a recent result from the theory of nearly uncoupled Markov chains, we give an addi- tional qualitative constrain to be met by these systems in order to get a good approximation of their analysis into independent blocks. In the third part of this paper, we examine the application of NCD to the problem of ranking websites. Recent research has commented on the special structure of the stochastic matrix which corresponds to the web-graph. In particular, the topological properties of the Web seems to produce a NCD stochastic matrix. Here, after presenting briefly the mathe- matical basis of PageRank, we give a linear algebraic as well as an intuitive justification of the NCD Web structure and we discuss the nature of the subsystems. Finally, we propose a new ranking algorithm named NCDawareRank, which exploits NCD in order to achieve a fairer and faster ranking. Indeed, we give two versions of the algorithm, one serial and one parallel, in which we take advantage of the computational benefits of NCD as well. The advantages of NCDawareRank are then confirmed experimentally through a series of tests on both, artificial and real data. NCDawareRank seems to solve a known problem of PageRank: the bias against new websites. Finally, another side benefit of our algorithm is that it makes it easy to extract a level-wise ranking, which besides its importance in itself, may indicate smarter crawling or even more sophisticated and efficient indexing schemes of the Web. Finally, in the fourth part of this work we apply NCD to the problem of finding the stochastically stable states of a class of evolutionary games which involve multilevel strategic dynamics. After presenting some interesting recent results coming from the lit- erature of econometrics, we give conditions under which it is possible to get the exact stochastically stable states through the use of NCD.

L'objet de cette thèse est de proposer et de développer les différentes mesures multidimensionnelles de la pauvreté. La multidimensionnalité de la pauvreté fait aujourd'hui consensus. Scientifiques, décideurs politiques et professionnels du développement s'accordent pour dire que la seule dimension monétaire (le manque de revenu) ne suffit pas à représenter la pauvreté. En se basant sur les travaux de Sen (Prix Nobel d'Economie) en particulier sur l'approche des capacités, nous proposons quatre mesures différentes de la pauvreté. La première est une mesure monétaire basée sur l'approche utilitaire ; la seconde est une mesure subjective basée sur les expériences des ménages ; la troisième est une mesure multidimensionnelle axiomatique et enfin la dernière est une mesure non axiomatique basée sur la théorie des ensembles flous. Elles sont toutes mises en oeuvre en utilisant les données d'enquêtes EDAM3-IS (Enquête Djiboutienne Auprès des Ménages 2012). Les résultats s'inscrivent dans un contexte de croissance économique que connait Djibouti. Cependant, toutes les mesures utilisées ont montré des grandes disparités régionales entre la capitale et les régions en termes d'infrastructure de base et de bien-être des ménages. Chacune de ses méthodes a fourni des résultats avec différentes interprétations des déterminants de la pauvreté. Cela ne signifie pas qu'il existe une méthode bien meilleure que l'autre, mais chaque approche, dans un contexte particulier, peut-être plus pertinente. Ainsi, l'identification des pauvres en appliquant les différentes mesures de la pauvreté nous a donné un profil différencié. Par conséquent, le décideur doit définir au préalable l'objectif poursuivi dans les politiques de lutte contre la pauvreté. Nous pouvons souligner que l'intégration d'une pondération subjective dans la mesure de la pauvreté est une de nos contributions au développement de mesures multidimensionnelles de la pauvreté. / The aim of this thesis is to propose and develop the various multidimensional measures of poverty. There is a consensus on the multidimensional nature of poverty. Scientists, policy makers and development professionals agree that the monetary dimension (lack of income) is inadequate to represent poverty. On the basis of the work of Sen (Nobel Proze of Economics), particularly on the capability approach, we propose four different measures of poverty. The first one is a monetary measure based on the utilitarian approach ; the second is a subjective measure founded on household experience ; the third is a multidimensional axiomatic measure and the final one is a non-axiomatic measure based on the theory of fuzzy sets. They are implemented using survey data EDAM3-IS (Djiboutian Survey of Households 2012). The esults fall within the framework of economic growth in Djibouti. However, all the measures used have shown great disparities between the capital and the regions in terms of basic infrastructure and household welfare. Each method produced results with different interpretations of the determinants of poverty. This does not mean that there is one method being better than the other but rather each approach, in a particular context, may be more relevant. Thus, identifying the poor by applying the different measures of poverty gave us a clear-cut profile, which implies that the decision-maker must first set the aim in view in the implementation of anti-poverty policies. It can be emphasized that the inclusion of a subjective weighting in the process of measuring of poverty is one of our contributions towards the development of multidimensional measures of poverty.