Thesis (MPhil)--University of Stellenbosch, 2007. / ENGLISH ABSTRACT: Many variations of Systems Development Life Cycle models have evolved over the last fifty years of systems engineering and software science, yet not enough knowledge is available to better understand these as Complex Adaptive Systems by studying chaos and complexity theories. The primary application domain of the thesis is focused on the development of electronic hardware and software products. There is a great need for innovation to reach all corners of the development ecosystem; however a large cognitive distance exists between the concept of systematic product development and that of value creation. Instruments are needed to aid process agility, for defusing imminent problems as they mount, and for making effective decisions to sustain maximum productivity. Many of these objectives are neglected in systems development practices. As with so many management fads, it appears that no single one of these models lived up to all of the expectations and in many cases ended up being recipes for disaster. The statistics available on failed projects are concerning but has not stopped the scientific and engineering communities from trying over, and over again, to make progress. The goal of the thesis is therefore to identify the most viable model that supports the sustainability of systems development team performance. The research draws insights from extant literature, by applying a knowledge management theory based analysis on the various models with specific attention given to complexity theory. The dominant metric discovered is to measure the Value Velocity of a Systems Development Team. This metric is determined by two independent variables, being Value Created and Delivery Delay. Complex Adaptive Systems simply requires a guiding vision and a carefully selected set of generative rules for increasing and sustaining the Value Velocity. / AFRIKAANSE OPSOMMING: Menige variasies van stelselsontwikkelingsmodelle het ontwikkel oor die afgelope vyftig jaar in stelselsingenieurswese en sagtewarewetenskap, en steeds is daar nie genoegsame kennis beskikbaar om beter begrip te kry oor hoe hierdie stelsels as Komplekse Aanpassende Sisteme bestudeer kan word nie, ten einde die bestuur daarvan te verbeter. Die primêre toepassingsgebied in die tesis is gespits op die ontwikkeling van rekenaarhardeware en - sagteware. Die behoefte vir innovasie moet al die fasette van die ontwikkelingsekosisteem bereik. Die bewusheidsgaping tussen sistemiese produkontwikkeling en waardeskepping, is te wyd. Instumentasie word benodig om te help met ratsheid in prosesuitvoering, om dreigende probleme te ontlont, en effektief besluitneming toe te pas, en sodoende produktiwiteit op ‘n maksimum vlak te hou. Hierdie doelwitte word tot ’n meerdere mate in die huidige praktyk verontagsaam. Net soos somige bestuursadvies oneffektief is, blyk dit dat daar nog steeds geen stelselsmodelle is wat alle verwagtinge bevredig nie. In baie gevalle eindig die toepassing daarvan in waan en mislukking. Die statistiek beskikbaar op mislukte projekte is onrusbarend, tog het dit nie vooruitgang gekelder nie, en die behoefte na verbetering bestaan steeds. Die doelwit van die tesis is dus om die mees lewensvatbare model wat die voortbestaan van stelselsontwikkelingsgroepe sal kan handhaaf, uit te sonder. Die navorsing neem insigte uit hedendagse literatuur en is gebasseer op ’n analiese van verskeide kennisbestuursteorieё teenoor die bestaande stelselsontwikkelingsmodelle. Die fokus is meer spesifiek toegespits op kompleksiteitsteorie. Die hoofmaatstaaf is om die Waardesnelheid van ’n stelselsontwikkelingspan te bepaal. Hierdie maatstaaf word gepyl deur twee onafhanklike veranderlikes, naamlik die Waarde Geskep en die Afleweringsvertraging. Ten slotte, vereis Kompleks Aanpassende Sisteme slegs die aanwesigheid van 'n leidende visie tesame met 'n goeddeurdagte stel ontwikkelingsreëls, wat aanleiding sal gee tot die verhoging en behoud van die Waardesnelheid.

Submitted by Reinaldo Kagi (reinaldo.kagi@gmail.com) on 2014-03-07T16:23:26Z No. of bitstreams: 1 KAGI, Reinaldo Kenji. (2014) - Fragmentos da Complexidade Aplicados ao Mercado Financeiro.pdf: 976757 bytes, checksum: 053f1bfa52560a1fc533f8c2860a3caa (MD5) / Rejected by JOANA MARTORINI (joana.martorini@fgv.br), reason: prezado Reinaldo, boa tarde A numerações das paginas não podem ficar visíveis antes da introdução, existem paginas em branco que devem ser retiradas e o titulo não está de acordo com o titulo apresentado na Ata de Dissertação conforme segue abaixo: Fragmentos DE complexidade aplicados ao mercado financeiro Fragmentos DA complexidade aplicados ao mercado financeiro Por gentileza fazer os ajustes listados acima. on 2014-03-07T18:20:57Z (GMT) / Submitted by Reinaldo Kagi (reinaldo.kagi@gmail.com) on 2014-03-07T19:05:43Z No. of bitstreams: 1 KAGI, Reinaldo Kenji. (2014) - Fragmentos de Complexidade Aplicados ao Mercado Financeiro.pdf: 953573 bytes, checksum: d484fb79cf4de8d48c79d7b72dd959a0 (MD5) / Rejected by JOANA MARTORINI (joana.martorini@fgv.br), reason: Prezado Reinaldo, boa tarde. Tem um único ponto a ser ajustado, na folha de assinatura a data está errada, o correto seria 07/02/2014 (data de sua apresentação de dissertação. por gentileza ajustar. on 2014-03-07T19:25:51Z (GMT) / Submitted by Reinaldo Kagi (reinaldo.kagi@gmail.com) on 2014-03-07T19:31:16Z No. of bitstreams: 1 KAGI, Reinaldo Kenji. (2014) - Fragmentos de Complexidade Aplicados ao Mercado Financeiro.pdf: 975473 bytes, checksum: 955bb2b02ccec9d2b6a97da997eb9af3 (MD5) / Approved for entry into archive by JOANA MARTORINI (joana.martorini@fgv.br) on 2014-03-07T19:32:30Z (GMT) No. of bitstreams: 1 KAGI, Reinaldo Kenji. (2014) - Fragmentos de Complexidade Aplicados ao Mercado Financeiro.pdf: 975473 bytes, checksum: 955bb2b02ccec9d2b6a97da997eb9af3 (MD5) / Made available in DSpace on 2014-03-07T19:50:04Z (GMT). No. of bitstreams: 1 KAGI, Reinaldo Kenji. (2014) - Fragmentos de Complexidade Aplicados ao Mercado Financeiro.pdf: 975473 bytes, checksum: 955bb2b02ccec9d2b6a97da997eb9af3 (MD5) Previous issue date: 2014-03-10 / The rise of complexity in financial markets has been reported by Rajan (2005), Gorton (2008) and e Haldane & May (2011) as one of the main features that led to the increase of systemic risk, which climaxed in the financial crisis of 2007/08. The Bank for International Settlements (2013) covers the matters of complexity in the context of banking regulation and discusses the comparability of capital adequacy among banks and jurisdictions. Nonetheless, definitions for concepts such as complexity and complex adaptive systems are omitted from the major discussions. This paper elucidates some concepts related to the Theories of Complexity, how this phenomenon arises, how they may be applied to financial markets. We discuss the use of two tools in the context of complex adaptive systems: Agent Based Models (ABMs) and entropy. We come to the conclusion that although the complexity research agenda still leaves us some gaps, it most definitely contributes to the economic research in understanding the mechanisms that trigger systemic risks, as well as adding tools that allows us model interacting heterogeneous agents, which leads to the rise of emergent phenomena in the system. Some research hypotheses are suggested for later development. / O aumento da complexidade do mercado financeiro tem sido relatado por Rajan (2005), Gorton (2008) e Haldane e May (2011) como um dos principais fatores responsáveis pelo incremento do risco sistêmico que culminou na crise financeira de 2007/08. O Bank for International Settlements (2013) aborda a questão da complexidade no contexto da regulação bancária e discute a comparabilidade da adequação de capital entre os bancos e entre jurisdições. No entanto, as definições dos conceitos de complexidade e de sistemas adaptativos complexos são suprimidas das principais discussões. Este artigo esclarece alguns conceitos relacionados às teorias da Complexidade, como se dá a emergência deste fenômeno, como os conceitos podem ser aplicados ao mercado financeiro. São discutidas duas ferramentas que podem ser utilizadas no contexto de sistemas adaptativos complexos: Agent Based Models (ABMs) e entropia e comparadas com ferramentas tradicionais. Concluímos que ainda que a linha de pesquisa da complexidade deixe lacunas, certamente esta contribui com a agenda de pesquisa econômica para se compreender os mecanismos que desencadeiam riscos sistêmicos, bem como adiciona ferramentas que possibilitam modelar agentes heterogêneos que interagem, de forma a permitir o surgimento de fenômenos emergentes no sistema. Hipóteses de pesquisa são sugeridas para aprofundamento posterior.

A realidade das organizações atualmente faz com que os desafios apresentados sejam enfrentados procurando-se a maior eficácia para suas soluções e com isso surjam as adaptações necessárias as constantes mudanças de maneira que os entraves sejam solucionados levando em consideração toda a amplitude que apresentarem. A Teoria da Complexidade por sua essência pode propiciar uma visão mais próxima da realidade, auxiliando na busca pelo entendimento de processos relacionados a gestão dos sistemas. Essa abordagem pode proporcionar uma maior efetividade nas ações das organizações, podendo servir de suporte para o melhor entendimento dos relacionamentos e das necessidades dos atores tanto internos como dos atores externos envolvidos nas organizações. Este trabalho foi construído a partir da necessidade do entendimento de como acontecem os relacionamentos entre os integrantes da cadeia produtiva da maçã para a partir disso propor mecanismos que possam auxiliar na melhoria das inter-relações. Assim, utilizou-se a abordagem do anel tetralógico para auxiliar na identificação das ações decorrentes da implementação da PIM na cadeia produtiva da maçã nos estados do Rio Grande do Sul e Santa Catarina. Trata-se de uma pesquisa qualitativa, operacionalizada através de um estudo de caso. Para que os objetivos fossem atingidos foi realizada uma revisão teórica a cerca dos pilares que sustentam o estudo, cadeia produtiva, relacionamento e teoria da Complexidade. Baseando-se na revisão teórica foram construídos os procedimentos metodológicos para a coleta e análise dos dados. A realização do estudo de caso realizou-se a partir de entrevistas com especialistas integrantes da cadeia produtiva da maçã brasileira. A análise dos dados proporcionou a evidencia de resultados como: identificação dos conceitos do anel tetralógico na implementação da Produção Integrada de Maçã; verificação das estratégias que a cadeia produtiva da maçã utiliza como norteadores do sistema; presença nos relacionamentos de ações e atitudes que trazem ao sistema a necessidade de trabalho voltado para o comportamento de cooperação e trabalho em equipe; além da necessidade de uma reorganização voltada para o cumprimento dos processos de certificação por parte do elo compradores atacadistas e varejistas, assim como a conscientização dos consumidores finais para a exigência de controle de qualidade no momento da compra. / Submitted by Marcelo Teixeira (mvteixeira@ucs.br) on 2014-05-28T19:54:25Z No. of bitstreams: 1 Dissertacao Marcia Rohr da Cuz.pdf: 556190 bytes, checksum: a8d9e8fb44293b0763108a51bc83715c (MD5) / Made available in DSpace on 2014-05-28T19:54:25Z (GMT). No. of bitstreams: 1 Dissertacao Marcia Rohr da Cuz.pdf: 556190 bytes, checksum: a8d9e8fb44293b0763108a51bc83715c (MD5) / The reality of the organizations at present does so that the presented challenges are faced looking for the biggest efficiency for his solutions and the necessary adaptations appear for the constant changes so that the hamper are solved taking into account the whole breadth what to present. The Theory of the Complexity for his essence can give a vision more near the reality, helping in the search for the understanding of processes related of the systems of management. This approach can provide a bigger effectiveness in the actions of the organizations, being able to serve of support for the best understanding of the relationships and of the necessities of the actors so the internal as the external actors wrapped in the organizations. This work was fulfilled from the necessity of the understanding of how the relationships happen between the integrants of the productive chain of the apple for from that to propose mechanisms that could help in the improvement of the inter-relations. So, there was suggested the use of the approach of the tetralogic ring for help in the identification of the actions resulting from the implementation of the PIM in the productive chain of the apple in the states of Rio Grande do Sul and Santa Catarina. So that the objectives being reached it was carried out a theoretical revision around the pillars that support the study, productive chain, relationship and theory of the Complexity. Being based on the theoretical revision there was built proceedings for the collection and analysis of the data. The realization of the study case happened from interviews with specialists, integrant of the productive chain of the Brazilian apple. The analysis of the data provided shows up of results like: identification of the concepts of the tetralógic ring in the implementation of the Integrated Production of Apple; checking of the strategies that the productive chain of the apple uses how direction of the system; presence in the relationships of actions and attitudes that bring to the system the necessity of work turned to the behavior of cooperation and work in team; besides the necessity of a reorganization turned to the fulfillment of the processes of certification for part of the link wholesale and retail buyers, as well as the conscience of the final consumers for the demand of quality control at the moment of the purchase.

Dans cette thèse, nous cherchons à comparer la complexité booléenne classique et la complexité algébrique, en étudiant des problèmes sur les polynômes. Nous considérons les modèles de calcul algébriques de Valiant et de Blum, Shub et Smale (BSS). Pour étudier les classes de complexité algébriques, il est naturel de partir des résultats et des questions ouvertes dans le cas booléen, et de regarder ce qu'il en est dans le contexte algébrique. La comparaison des résultats obtenus dans ces deux domains permet ainsi d'enrichir notre compréhension des deux théories. La première partie suit cette approche. En considérant un polynôme canoniquement associé à toute formule booléenne, nous obtenons un lien entre les questions de complexité booléenne sur la formule booléenne et les questions de complexité algébrique sur le polynôme. Nous avons étudié la complexité du calcul de ce polynôme dans le modèle de Valiant en fonction de la complexité de la formule booléenne, et avons obtenu des analogues algébriques à certains résultats booléens. Nous avons aussi pu utiliser des méthodes algébriques pour améliorer certains résultats booléens, en particulier de meilleures réductions de comptage. Une autre motivation aux modèles de calcul algébriques est d'offrir un cadre pour l‘analyse d’algorithmes continus. La seconde partie suit cette approche. Nous sommes partis d’algorithmes nouveaux pour la recherche de zéros approchés d'un système de n polynômes complexes à n inconnues. Jusqu'à présent il s'agissait d'algorithmes pour le modèle BSS. Nous avons étudié l'implémentabilité de ces algorithmes sur un ordinateur booléen et proposons un algorithme booléen. / In the present thesis, we try to compare the classical boolean complexity with the algebraic complexity, by studying problems related to polynomials. We consider the algebraic models from Valiant and from Blum, Shub and Smale (BSS). To study the algebraic complexity classes, one can start from results and open questions from the boolean case, and look at their translation in the algebraic context. The comparison of the results obtained in the two settings will then boost our understanding of both complexity theories. The first part follows this framework. By considering a polynomial canonically associated to a boolean formula, we get a link between boolean complexity issues on the formula and algebraic complexity problems on the polynomial. We studied the complexity of computing the polynomial in Valiant's model, as a function of the complexity of the boolean formula. We found algebraic counterparts to some boolean results. Along the way, we could also use some algebraic methods to improve boolean results, in particular by getting better counting reductions. Another motivation for algebraic models of computation is to offer an elegant framework to the study of numerical algorithms. The second part of this thesis follows this approach. We started from new algorithms for the search of approximate zeros of complex systems of n polynomials in n variables. Up to now, those were BSS machine algorithms. We studied the implementation of these algorithms on digital computers, and propose an algorithm using floating arithmetic for this problem.

A realidade das organizações atualmente faz com que os desafios apresentados sejam enfrentados procurando-se a maior eficácia para suas soluções e com isso surjam as adaptações necessárias as constantes mudanças de maneira que os entraves sejam solucionados levando em consideração toda a amplitude que apresentarem. A Teoria da Complexidade por sua essência pode propiciar uma visão mais próxima da realidade, auxiliando na busca pelo entendimento de processos relacionados a gestão dos sistemas. Essa abordagem pode proporcionar uma maior efetividade nas ações das organizações, podendo servir de suporte para o melhor entendimento dos relacionamentos e das necessidades dos atores tanto internos como dos atores externos envolvidos nas organizações. Este trabalho foi construído a partir da necessidade do entendimento de como acontecem os relacionamentos entre os integrantes da cadeia produtiva da maçã para a partir disso propor mecanismos que possam auxiliar na melhoria das inter-relações. Assim, utilizou-se a abordagem do anel tetralógico para auxiliar na identificação das ações decorrentes da implementação da PIM na cadeia produtiva da maçã nos estados do Rio Grande do Sul e Santa Catarina. Trata-se de uma pesquisa qualitativa, operacionalizada através de um estudo de caso. Para que os objetivos fossem atingidos foi realizada uma revisão teórica a cerca dos pilares que sustentam o estudo, cadeia produtiva, relacionamento e teoria da Complexidade. Baseando-se na revisão teórica foram construídos os procedimentos metodológicos para a coleta e análise dos dados. A realização do estudo de caso realizou-se a partir de entrevistas com especialistas integrantes da cadeia produtiva da maçã brasileira. A análise dos dados proporcionou a evidencia de resultados como: identificação dos conceitos do anel tetralógico na implementação da Produção Integrada de Maçã; verificação das estratégias que a cadeia produtiva da maçã utiliza como norteadores do sistema; presença nos relacionamentos de ações e atitudes que trazem ao sistema a necessidade de trabalho voltado para o comportamento de cooperação e trabalho em equipe; além da necessidade de uma reorganização voltada para o cumprimento dos processos de certificação por parte do elo compradores atacadistas e varejistas, assim como a conscientização dos consumidores finais para a exigência de controle de qualidade no momento da compra. / The reality of the organizations at present does so that the presented challenges are faced looking for the biggest efficiency for his solutions and the necessary adaptations appear for the constant changes so that the hamper are solved taking into account the whole breadth what to present. The Theory of the Complexity for his essence can give a vision more near the reality, helping in the search for the understanding of processes related of the systems of management. This approach can provide a bigger effectiveness in the actions of the organizations, being able to serve of support for the best understanding of the relationships and of the necessities of the actors so the internal as the external actors wrapped in the organizations. This work was fulfilled from the necessity of the understanding of how the relationships happen between the integrants of the productive chain of the apple for from that to propose mechanisms that could help in the improvement of the inter-relations. So, there was suggested the use of the approach of the tetralogic ring for help in the identification of the actions resulting from the implementation of the PIM in the productive chain of the apple in the states of Rio Grande do Sul and Santa Catarina. So that the objectives being reached it was carried out a theoretical revision around the pillars that support the study, productive chain, relationship and theory of the Complexity. Being based on the theoretical revision there was built proceedings for the collection and analysis of the data. The realization of the study case happened from interviews with specialists, integrant of the productive chain of the Brazilian apple. The analysis of the data provided shows up of results like: identification of the concepts of the tetralógic ring in the implementation of the Integrated Production of Apple; checking of the strategies that the productive chain of the apple uses how direction of the system; presence in the relationships of actions and attitudes that bring to the system the necessity of work turned to the behavior of cooperation and work in team; besides the necessity of a reorganization turned to the fulfillment of the processes of certification for part of the link wholesale and retail buyers, as well as the conscience of the final consumers for the demand of quality control at the moment of the purchase.

<div>The internal and external interactions between the complex structural and behavioral characteristics of the system of interest and the surrounding environment result in unpredictable emergent behaviors. These emergent behaviors are not well understood, especially when modeled using the traditional top-down systems engineering approach. The intrinsic nature of current complex systems has called for an elegant solution that provides an integrated framework in Model-Based Systems Engineering. A considerable gap exists to integrate system engineering activities and engineering analysis, which results in high risk and cost. This thesis presents a framework that incorporates indefinite and definite modeling aspects that are developed to determine the complexity that arises during the development phases of the system. This framework provides a workflow for modeling complex systems using Systems Modeling Language (SysML) that captures the system’s requirements, behavior, structure, and analytical aspects at both problem definition and solution levels. This research introduces a new level/dimension to the framework to support engineering analysis integrated with the system architecture model using FMI standards. A workflow is provided that provides the enabling methodological capabilities. It starts with a statement of need and ends with system requirement verification. Detailed traceability is established that glues system engineering and engineering analysis together. Besides, a method is proposed for predicting the system’s complexity by calculating the complexity index that can be used to assess the complexity of the existing system and guide the design and development of a new system. To test and demonstrate this framework, a case study consisting of a complex district cooling system is implemented. The case study shows the framework’s capabilities in enabling the successful modeling of a complex district cooling system. The system architecture model was developed using SysML and the engineering analysis model using Modelica. The proposed framework supports system requirements verification activity. The analysis results show that the district chiller model developed using Modelica produces chilled water below 6.6 degrees Celsius, which satisfies the system requirement for the district chiller system captured in the SysML tool. Similarly, many such requirement verification capabilities using dynamic simulation integration with the high-level model provides the ability to perform continuous analysis and simulation during the system development process. The systems architecture complexity index is measured for the district cooling case study from the black-box and white box-perspective. The measured complexity index showed that the system architecture’s behavioral aspect increases exponentially compared to the structural aspect. The systems architecture’s complexity index at black-box and white-box was 4.998 and 67.3927, respectively.</div>

Studien har som syfte att tolka och förstå det som pågår i lärarens vardag med hjälp av komplexitetsteorier. Komplexitetsteorier utgör de specifika delarna i komplexitetstänkande som är en resurs för att diskutera relationen mellan skolan som komplext system, vetenskaplig grund och evidens. En förståelse bestående av att lärares vardag är mång- och tvetydig till dess innehåll är väl känt och beskrivet genom exempelvis framställningar av vad en lärares görande består av. För att tolka lärarens vardag är komplexitetsteorier inte vanligt förekommande. Komplexitetsteorier studerar mönster av självorganisering och det pågående med fokus på relationer. Komplexa system är icke-linjära och kausaliteten är cirkulär. Intentionen med komplexitetstänkande är att beskriva, tolka och förstå mönster av komplexitet. För att visa på en helhet och mönster har studien en narrativ ansats. Ett narrativt förhållningssätt ligger nära vardagens hantering av en rad paradoxer där det kända och okända samtidigt förekommer. För att samla in rika berättelser om lärarens vardag användes kvalitativa intervjuer som metod. Resultat visar på att det är det mångsidiga innehållet i relationerna som bland annat skapar komplexiteten i lärares vardag. Lärarens vardag består av många delar och ett komplexitetstänkande sätter fokus på att sätta ihop delarna till helhet och se mönster. Resultatet visar också på att en rad olika paradoxer måste hanteras. I berättelserna framträder hur lärarna hanterar en rad olika processer i relationen mellan kontroll och icke-kontroll, mellan på förhand det kända och okända där överraskningar är en del av vardagen, en del av interaktionen mellan människor. I en evidensbaserad praktik framträder att lärarens hantering av en rad paradoxer begränsas eftersom idén om evidensbaserad praktik innebär generaliserbara metoder där utfallet anses vara givet. Komplexitetstänkande innebär att det ställs andra krav på användning av vetenskaplig grund. Aktörer som rektorer, huvudmän och Skolverket bör i utformning av stöd till skolor inkludera tanken om att praktiken är ett komplext system. / The purpose is to use complexity theories to describe, interpret and understand teacher's everyday life. An everyday life where the predictable and the unpredictable exist in parallel. In relation to the teacher's everyday life and complexity theories, scientific basis and evidence are discussed. To show a cohesive complexity, the study has a narrative approach. A narrative approach is close to the structure of everyday life where the known and the unknown exist in symbiosis. To collect rich stories about the teacher's everyday life, qualitative interviews were used as a method. The result shows the circular causality that exists in non-linear systems. The teacher's everyday life contains many different processes that create a high degree of complexity. Some key processes are communication, relationships and complexity that are closely linked. Words that have in common the local interaction that includes the social as well as material things where there are possibilities of action. It is the multilateral job description that, among other things, creates the complexity of teachers' everyday lives. Structures and routines are important in order to be able to reduce the complexity of everyday life to a certain extent. Further on to deal with the paradox between control and non-control. Based on complexity theories, structures must contain the opportunity to be interpreted, adapted and translated to the practice. The school is a non-linear system and evidence-based practice is based on a linear system. In order to be able to interact with the practice, government investment in school to increase a more scientific ground. One of these projects is called, “läslyftet”. These projects need to take into account the processes and the unique in the practice. The study's contribution is to use complexity theories to show other perspectives on how change can take place in school. Specifically, how scientific basis and evidence can interact in the complex practice. Furthermore, show how complexity theories can help to make it possible to find new paths to development within school.

In der klassischen Komplexitätstheorie unterscheiden wir zwischen der Klasse P von in Polynomialzeit lösbaren Problemen, und der Klasse NP-schwer von Problemen bei denen die allgemeine Annahme ist, dass diese nicht in Polynomialzeit lösbar sind. Allerdings sind viele Probleme, die wir lösen möchten, NP-schwer. Gleichzeitig besteht eine große Diskrepanz zwischen den empirisch beobachteten und den festgestellten worst-case Laufzeiten. Es ist bekannt, dass Vorverarbeitung oder Datenreduktion auf realen Instanzen zu Laufzeitverbesserungen führt. Hier stoßen wir an die Grenze der klassischen Komplexitätstheorie. Der Fokus dieser Arbeit liegt auf Vorverarbeitungsalgorithmen für NP-schwere Probleme. Unser Ziel ist es, bestimmte Instanzen eines NP-schweren Problems vorverarbeiten zu können, indem wir die Struktur betrachten. Genauer gesagt, für eine gegebene Instanz und einen zusätzlichen Parameter l, möchten wir in Polynomialzeit eine äquivalente Instanz berechnen, deren Größe und Parameterwert nur durch eine Funktion im Parameterwert l beschränkt ist. In der parametrisierten Komplexitätstheorie heißen diese Algorithmen Kernelisierung. Wir werden drei NP-schwere Graphenprobleme betrachten, nämlich Vertex Cover, Edge Dominating Set und Subset Feedback Vertex Set. Für Vertex Cover werden wir bekannte Ergebnisse für Kernelisierungen vereinheitlichen, wenn der Parameter die Größe einer Entfernungsmenge zu einer gegebenen Graphklasse ist. Anschließend untersuchen wir die Kernelisierbarkeit von Edge Dominating Set. Es stellt sich heraus, dass die Kernelisierbarkeit deutlich komplexer ist. Dennoch klassifizieren wir die Existenz einer polynomiellen Kernelisierung, wenn jeder Graph in der Graphklasse eine disjunkte Vereinigung von konstant großen Komponenten ist. Schließlich betrachten wir das Subset Feedback Vertex Set Problem und zeigen, dass es eine randomisierte polynomielle Kernelisierung hat, wenn der Parameter die Lösungsgröße ist. / In classical complexity theory, we distinguish between the class P, of polynomial-time solvable problems, and the class NP-hard, of problems where the widely-held belief is that we cannot solve these problems in polynomial time. Unfortunately, many of the problems we want to solve are NP-hard. At the same time, there is a large discrepancy between the empirically observed running times and the established worst-case bounds. Using preprocessing or data reductions on real-world instances is known to lead to huge improvements in the running time. Here we come to the limits of classical complexity theory. In this thesis, we focus on preprocessing algorithms for NP-hard problems. Our goal is to find ways to preprocess certain instances of an NP-hard problem by considering the structure of the input instance. More precisely, given an instance and an additional parameter l, we want to compute in polynomial time an equivalent instance whose size and parameter value is bounded by a function in the parameter l only. In the field of parameterized complexity, these algorithms are called kernelizations. We will consider three NP-hard graph problems, namely Vertex Cover, Edge Dominating Set, and Subset Feedback Vertex Set. For Vertex Cover, we will unify known results for kernelizations when parameterized by the size of a deletion set to a specified graph class. Afterwards, we study the existence of polynomial kernelizations for Edge Dominating Set when parameterized by the size of a deletion set to a graph class. We point out that the existence of polynomial kernelizations is much more complicated than for Vertex Cover. Nevertheless, we fully classify the existence of polynomial kernelizations when every graph in the graph class is a disjoint union of constant size components. Finally, we consider graph cut problems, especially the Subset Feedback Vertex Set problem. We show that this problem has a randomized polynomial kernelization when the parameter is the solution size.

Indiana University-Purdue University Indianapolis (IUPUI) / The internal and external interactions between the complex structural and behavioral characteristics of the system of interest and the surrounding environment result in unpredictable emergent behaviors. These emergent behaviors are not well understood, especially when modeled using the traditional top-down systems engineering approach. The intrinsic nature of current complex systems has called for an elegant solution that provides an integrated framework in Model-Based Systems Engineering. A considerable gap exists to integrate system engineering activities and engineering analysis, which results in high risk and cost. This thesis presents a framework that incorporates indefinite and definite modeling aspects that are developed to determine the complexity that arises during the development phases of the system. This framework provides a workflow for modeling complex systems using Systems Modeling Language (SysML) that captures the system’s requirements, behavior, structure, and analytical aspects at both problem definition and solution levels. This research introduces a new level/dimension to the framework to support engineering analysis integrated with the system architecture model using FMI standards. A workflow is provided that provides the enabling methodological capabilities. It starts with a statement of need and ends with system requirement verification. Detailed traceability is established that glues system engineering and engineering analysis together. Besides, a method is proposed for predicting the system’s complexity by calculating the complexity index that can be used to assess the complexity of the existing system and guide the design and development of a new system. To test and demonstrate this framework, a case study consisting of a complex district cooling system is implemented. The case study shows the framework’s capabilities in enabling the successful modeling of a complex district cooling system. The system architecture model was developed using SysML and the engineering analysis model using Modelica. The proposed framework supports system requirements verification activity. The analysis results show that the district chiller model developed using Modelica produces chilled water below 6.6 degrees Celsius, which satisfies the system requirement for the district chiller system captured in the SysML tool. Similarly, many such requirement verification capabilities using dynamic simulation integration with the high-level model provides the ability to perform continuous analysis and simulation during the system development process. The systems architecture complexity index is measured for the district cooling case study from the black-box and white box-perspective. The measured complexity index showed that the system architecture’s behavioral aspect increases exponentially compared to the structural aspect. The systems architecture’s complexity index at black-box and white-box was 4.998 and 67.3927, respectively.

No description available.