Parameterized complexity is a part of computer science dealing with the computational complexity of problems measured not only by the length of their input but also some parameter of the input. Nei- ghborhood diversity is a recently introduced parameter describing a certain structure of a graph. is parameter is aractive for resear especially because some problems whi are hard with respect to other parameters that are incomparable with neighborhood diversity become fixed-parameter tractable with respect to neighborhood diversity. In this thesis we show fixed-parameter tractability for three problems that are hard with respect to treewidth. is constitutes the main part of this thesis and it is our original work. Next it contains an overview of other interesting problems and also a survey of the state of the art in the area of parameters for sparse and dense graphs. 1

The topic of this diploma thesis is the edge distance labeling problem with specified parametres p, q and λ. We found a dychotomy for p = 2 and q = 1. So the problem is polynomial if λ ≤ 4 and it is NP-complete for λ > 4. The boundary is shifted by one prior to the vertex distance labeling problem, which has already been solved. Polynomial cases are characterized as some special paths and cycles with a few additional vertices. To show NP-completeness we use a well-known NP-complete problem of Monotone not all equal 3-SAT. That section has four parts: One for odd λ, one for even λ and two more reductions for λ = 5 and λ = 6. 1

The goal of this thesis is to create a tool for an optimization of code for the task-based parallel framework called Bobox. The optimizer tool reduces a number of short and long running tasks based on a static code analysis. Some cases of short-running tasks cause an unnecessary scheduling overhead. The Bobox scheduler can schedule a task even though the task does not have all input data. Unless, the scheduler has enough information not to schedule such task. In order to remove such short-running task, the tool analyses its input usage and informs the scheduler. Long-running tasks inhibit a parallel execution in some cases. A bigger task granularity can significantly improve execution times in a parallel environment. In order to remove a long-running task, the tool has to be able to evaluate a runtime code complexity and yield a task execution in the appropriate place. Powered by TCPDF (www.tcpdf.org)

Teorie a praxe tvorby učebnic chemie pro střední školy Mgr. Milan Klečka Abstrakt: Disertační práce je zaměřena na problematiku teorie a praxe tvorby učebnic chemie pro střední školy. Východiskem práce je rozsáhlá rešerše naší a zahraniční literatury zaměřená na analýzu významu, pojetí, charakteristiky a hodnocení učebnic. Dále je uvedena příprava, realizace a výsledky rozsáhlého šetření v rámci České republiky, týkajícího se reálného používání učebnic chemie na středních školách. Formou dotazníkového šetření bylo zjištěno, jaké učebnice chemie jsou v současnosti v praxi nejpoužívanější. Nejvíce používané učebnice obecné a anorganické chemie byly pak vybrány k dalšímu hodnocení metodikou Nestlerová-Průcha-Pluskal. Byl proveden komplexní rozbor osmi nejpoužívanějších učebnic a učebnicových řad obecné a anorganické chemie a porovnány jejich parametry. V závěru disertační práce je uveden přehled jednotlivých parametrů pro každou učebnici a návrh kritérií pro tvorbu optimální učebnice chemie pro střední školy.

We investigate the unprovability of NP$\not\subseteq$P/poly in various fragments of arithmetic. The unprovability is usually obtained by showing hardness of propositional formulas encoding superpolynomial circuit lower bounds. Firstly, we discuss few relevant techniques and known theorems. Namely, natural proofs, feasible interpolation, KPT theorem, iterability, gadget generators etc. Then we prove some original results. We show the unprovability of superpolynomial circuit lower bounds for systems admitting certain forms of feasible interpolation (modulo a hardness assumption) and for systems roughly described as tree-like Frege systems working with formulas using only a small fraction of variables of the statement that is supposed to be proved. These results are obtained by proving the hardness of the Nisan-Wigderson generators in corresponding proof systems.

Nous considérons dans cette thèse la complexité algorithmique de problèmes émanant de deux formalismes de raisonnement non-monotone: l'abduction et l'argumentation. Le premier est destiné à formaliser le processus de trouver des explications pour une manifestation observée, le second (et plus récent) offre un cadre théorique pour formaliser le processus de l'argumentation. Nous nous concentrons sur le problème d'existence d'une explication pour l'abduction et sur le problème d'existence d'un argument pour l'argumentation. Dans le cadre de la logique propositionnelle dans son ensemble ces problèmes sont considérés comme étant des tâches algorithmiques difficiles (ils sont souvent situés au deuxième niveau de l'hiérarchie polynomial). Notre but est d'une part de comprendre les sources de difficulté, et d'autre part d'identifier des fragments de la logique propositionnelle dans lequels ces problèmes sont résolubles efficacement. Pour cela nous considérons ces problèmes d'abduction et d'argumentation dans deux cadres bien-établis qui permettent des classifications de complexité : Le cadre de Post et celui de Schaefer. Dans le cadre de Post, des restrictions sont faites sur les connecteurs autorisés dans les formules utilisées. Dans le cadre de Schaefer, on considère les formules en forme normale conjonctive généralisée, les "clauses" sont alors des applications de relations booléennes à des variables et on restreint le type des relations autorisées. / In this thesis we consider the computational complexity of problems from two central formalisms of nonmonotonic reasoning: abduction and argumentation. The first one is designed to formalize the process of finding explanations for some observed manifestation, the second (and more recent) one gives a theoretical framework to formalize the process of argumentation. We focus on the explanation-existence problem for abduction and on the argument-existence problem for argumentation. Considered in full propositional logic these problems are believed to be computationally costly tasks (they are often situated at the second level of the polynomial hierarchy). With the purpose of understanding sources of hardness and of identifying tractable fragments of propositional logic we consider several abduction and argumentation problems in two well-established settings allowing for complexity classifications. In the first one, Post's Framework, restrictions are made on the allowed connectives in the used formulae, whereas in the second one, Schaefer's Framework, one considers formulae in conjunctive normal form, where the clauses are generalized to applications of arbitrary Boolean relations to variables and one restricts the allowed type of relations. We discuss differences and common features between the explanation-existence and the argument-existence problem in function of the two chosen frameworks. Finally, we consider enumeration. In particular we consider the problem of enumerating all solutions (models) of a propositional formula by non-decreasing weight in Schaefer's framework (the weight of a model being the number of variables assigned to true).

La th´eorie de la complexit´e permet de classifier les probl`emes en fonction de leur difficult´e. Le cadre classique dans lequel elle s’applique est celui d’un algorithme centralis´e qui dispose de toutes les informations. Avec l’essor des r´eseaux et des architectures d´ecentralis´ees, l’algo- rithmique distribu´ee a ´et´e ´etudi´ee. Dans un grand nombre de probl`emes, en optimisation et en ´economie, les d´ecisions et les calculs sont effectu´es par des agents ind´ependants qui suivent des objectifs diff´erents dont la r´ealisation d´epend des d´ecisions des autres agents. La th´eorie des jeux est un cadre naturel pour analyser les solutions de tels probl`emes. Elle propose des concepts de stabilit´e, le plus classique ´etant l’´equilibre de Nash.Une mani`ere naturelle de calculer de telles solutions est de “ faire r´eagir “ les agents ; si un agent voit quelles sont les d´ecisions des autres joueurs ou plus g´en´eralement un “ ´etat du jeu “, il peut d´ecider de changer sa d´ecision pour atteindre son objectif faisant ainsi ´evoluer l’´etat du jeu. On dit que ces algorithmes sont des “ dynamiques “.On sait que certaines dynamiques convergent vers un concept de solution. On s’int´eresse `a la vitesse de convergence des dynamiques. Certains concepts de solutions sont mˆeme complets pour certaines classes de complexit´e ce qui rend peu vraisemblable l’existence de dynamiques simples qui convergent rapidement vers ces solutions. On a utilis´e alors trois approches pour obtenir une convergence rapide : am´eliorer la dynamique (en utilisant par exemple des bits al´eatoires), restreindre la structure du probl`eme, et rechercher une solution approch´ee.Sur les jeux de congestion, on a ´etendu les r´esultats de convergence rapide vers un ´equilibre de Nash approch´e aux jeux n´egatifs. Cependant, on a montr´e que sur les jeux sans contrainte de signe, calculer un ´equilibre de Nash approch´e est PLS-complet. Sur les jeux d ’appariement, on a ´etudi´e la vitesse de dynamiques concurrentes lorsque les joueurs ont une information partielle param´etr´ee par un r´eseau social. En particulier, on a am´elior´e des dynamiques naturelles afin qu’elles atteignent un ´equilibre enO(log(n)) tours (avec n le nombre de joueurs). / Complexity theory allows to classify problems by their algorithmic hardness. The classical framework in which it applies is the one of a centralized algorithm that knows every informa- tion. With the development of networks and decentralized architectures, distributed dynamics was studied. In many problems, in optimization or economy, actions and computations are made by independant agents that don’t share the same objective whose realization depends on the actions of other agents. Game theory is a natural framework to study solutions of this kind of problem. It provides solution concepts such as the Nash equilibrium.A natural way to compute these solutions is to make the agents “react” ; if an agent sees the actions of the other player, or more generally the state of the game, he can decide to change his decision to reach his objective and updates the state of the game. We call �dynamics� this kind of algorithms.We know some dynamics converges to a stable solution. We are interested by the speed of convergence of these dynamics. Some solution concepts are even complete for some complexity classes which make unrealistic the existence of fast converging dynamics. We used three ways to obtain a fast convergence : improving dynamics (using random bits), finding simple subcases, and finding an approximate solution.We extent fast convergence results to an approximate Nash equilibria in negative congestion games. However, we proved that finding an approximate Nash equilibrium in a congestion games without sign restriction is PLS-complete. On matching game, we studied the speed of concurrent dynamics when players have partial information that depends on a social network. Especially, we improved natural dynamics for them to reach an equilibrium inO(log(n)) rounds (with n is the number of players).

In the present work, we study the propositional proof complexity. First, we prove an exponential lower bound on the complexity of resolution applying directly Razborov's approximation method, which was previously used only for bounds on the size of monotone circuits. Next, we use the approximation method for a new proof of an exponential lower bound on the complexity of random resolution refutations. That should have further applications in separating some theories in bounded arithmetic. In both cases, we use a problem from the graph theory called Broken Mosquito Screens. Finally, we state a conjecture that the approximation method is applicable even for stronger propositional proof systems, for example Cutting Plane Proofs. Powered by TCPDF (www.tcpdf.org)

Depuis l’avènement des environnements dits turbulents, une réflexion a vu le jour puis s’est développée autour du type de comportement stratégique et de compétences clés à adopter afin d’en limiter les effets négatifs. Cette réflexion a élevé le débat sur les processus d’adaptation en continu des organisations par rapport aux fluctuations exogènes. Ces perturbations peuvent également provenir de facteurs endogènes qui remodèlent les activités et les trajectoires organisationnelles. Les organisations sont alors contraintes à reconfigurer leurs processus pour mieux intégrer les changements. Mieux appréhender les fluctuations amène les organisations à plus d’anticipation, à plus de rapidité d’exécution, à plus de flexibilité et à plus d’apprentissages pour soutenir leurs projets de développement sur la durée. L’ensemble de ces mutations amènent ainsi les décideurs de tous bords à reconsidérer les hommes, les structures et les capacités organisationnelles dans une visée « agile ». L'agilité organisationnelle, entendue comme l’aptitude à se mouvoir promptement et justement dans des environnements incertains nécessite selon nous une investigation qualitative dans une perspective de meilleure compréhension du concept, car l’incomplétude de la littérature évacue les limites d’une notion qui semble figée. Notre investigation explore ainsi les représentations différenciées de la part des acteurs du concept, son opérabilité –complexe- dans les organisations, et vise enfin à élargir l’existant en apportant de nouveaux éléments de compréhension tels que la proximité, l’entrepreneuriat, la redéfinition de l’articulation du triptyque réactivité-flexibilité-proactivité… / Since the beginning of the so-called turbulent environments, thought has appeared and has developed around the type of strategic behaviour and key skills to be adopted in order to limit their negative effects. This thinking process has lifted up the debate to the ongoing adaptation processes of organisations according to exogenous fluctuations. These disturbances can also stem from endogenous factors that remodel activities and organisational paths. Organisations are therefore compelled to rearrange their processes to better integrate changes. A better approach to fluctuations leads organisations to more anticipation, quicker implementation, more flexibility and more learning that will enable them to sustain their development projects in the long run. All these alterations bring decision makers from all spheres of activity to reconsider men, structures and organisational capacities from an “agile” point of view.Organisational agility understood as the ability to move swiftly and rightly within uncertain environments requires according to this research a qualitative examination leading to a better understanding of the concept since it appears from the review of literature that the theoretical object of agility is described as rigid whereas it has its limits. This research thus explores the differentiated representations that the actors of agility make of the concept, its effectiveness, its (complex) functioning inside organisations. Finally, it also aims at enlarging the state-of-the-art by bringing new elements of understanding as proximity, entrepreneurship, redefinition of the triptych articulation: reactivity-flexibility-pro-activity.

La profession de masseur-kinésithérapeute est située à un tournant de son histoire. Les réformes en cours conduisent à questionner les savoirs enseignés et les compétences des masseurs-kinésithérapeutes pour garantir la sécurité du patient et la qualité des soins. Il a été cherché à connaître l'origine des savoirs en masso-kinésithérapie et à évaluer les dispositifs d'enseignements et d'appropriation de ces savoirs par les étudiants et par les professionnels de santé. Les résultats des études montrent que les écarts aux compétences attendues sont liés aux modalités d'enseignement et d'évaluation utilisées par les formateurs en formation initiale et en formation continue. Il apparait que les modalités pédagogiques utilisées par les formateurs sont souvent basées sur un socle théorique behavioriste, un modèle d'évaluation contrôle et des pratiques dogmatiques qui empêchent l'accès à la pensée et à la pratique « complexe » du soin. La formation n'optimise pas le développement des compétences de réflexivité, d'esprit critique et d'innovation nécessaires à la relation humaine de soin et à la sécurité idéale du patient. Cette thèse montre l'intérêt majeur de réaliser les enseignements en masso-kinésithérapie par des enseignants-chercheurs qui pensent, écrivent, discourent, agissent différemment des formateurs en formation initiale et en formation continue. Il est donc indispensable pour la sécurité du patient et pour la qualité des soins que la formation initiale et la formation continue en masso-kinésithérapie soient réalisées dans le cadre d'une discipline en masso-kinésithérapie sous la responsabilité d'enseignants-chercheurs en masso-kinésithérapie. / The profession of physiotherapist is located at a crossroads. Ongoing reforms lead to questioning the knowledge and skills taught physiotherapists to ensure patient safety and quality of care. It was sought to know the origin of knowledge in physiotherapy devices and evaluate teaching and ownership of such knowledge by students and health professionals. The study results show that the differences are expected to skills related to teaching methods and assessment used by teachers in initial training and continuing education. It appears that the teaching methods used by teachers are often based on a theoretical foundation behaviorist model evaluation and control practices that prevent access dogmatic thinking and practice "complex" care. Training of physiotherapists does not optimize the skills development of reflexivity, critical thinking and innovation needed in the human relationship of care and patient safety ideal. This thesis shows the major interest to carry out physiotherapy lessons by teachers and researchers who think, write, discoursing, act differently trainers in initial training and continuing education. It is therefore essential for patient safety and quality of care that initial training and continuing education in physiotherapy are carried out within the framework of a discipline physiotherapy under the responsibility of teachers researchers in physiotherapy.