No description available.

O TESTE baseado em modelos visa a possibilitar a derivação de conjuntos de casos de teste a partir de especificações formais, tais como Máquinas de Estados Finitos. Os conjuntos de teste podem ser obtidos tanto pelos métodos clássicos de geração quanto por alguma abordagem ad hoc. Procura-se obter um conjunto de teste que consiga detectar todos os possíveis defeitos de uma implementação e possua tamanho reduzido para que a sua aplicação seja factível. Por questões de ordem prática, pode não ser possível a aplicação de todo o conjunto de teste gerado. Desse modo, um subconjunto de casos de teste deve ser selecionado, ou seja, uma minimização do conjunto de teste deve ser realizada. No entanto, é fundamental que a minimização reduza o custo de aplicação dos testes, mas mantenha a efetividade em revelar defeitos. Neste trabalho, propõe-se um algoritmo de minimização de conjuntos de teste para Máquinas de Estados Finitos. O algoritmo baseia-se em condições de suficiência para que a completude em relação à detecção de defeitos seja mantida. O algoritmo foi utilizado em dois diferentes contextos. Utilizou-se o algoritmo com conjuntos de teste gerados de forma aleatória para verificar a minimização obtida. O algoritmo também foi utilizado para reduzir o esforço em se obter um conjunto completo em relação à detecção de defeitos / THE Model-based testing aims at generating test suites from formal specifications, such as Finite State Machines. Test suites can be obtained either from classical test derivation methods or from some ad-hoc approach. It is desirable to produce a test suite which detects all possible faults of an implementation and has small size, so that its application can be feasible. For practical reasons, the application of the generated test suite may not be possible. Therefore, a subset of test cases should be selected, i.e., a test suite minimization should be performed. However, it is important that the minimization reduces the test application cost, but keeps the effectiveness in revealing faults. In this work, an algorithm is proposed for the minimization of test suites generated from Finite State Machines. The algorithm is based on sufficient conditions, so that test suite completeness can be maintained. The algorithm was used in two different contexts. It was used with randomly generated test suites to verify the minimization obtained. The algorithm was also used to reduce the effort of obtaining a test suite with full fault coverage

O TESTE baseado em modelos visa a possibilitar a derivação de conjuntos de casos de teste a partir de especificações formais, tais como Máquinas de Estados Finitos. Os conjuntos de teste podem ser obtidos tanto pelos métodos clássicos de geração quanto por alguma abordagem ad hoc. Procura-se obter um conjunto de teste que consiga detectar todos os possíveis defeitos de uma implementação e possua tamanho reduzido para que a sua aplicação seja factível. Por questões de ordem prática, pode não ser possível a aplicação de todo o conjunto de teste gerado. Desse modo, um subconjunto de casos de teste deve ser selecionado, ou seja, uma minimização do conjunto de teste deve ser realizada. No entanto, é fundamental que a minimização reduza o custo de aplicação dos testes, mas mantenha a efetividade em revelar defeitos. Neste trabalho, propõe-se um algoritmo de minimização de conjuntos de teste para Máquinas de Estados Finitos. O algoritmo baseia-se em condições de suficiência para que a completude em relação à detecção de defeitos seja mantida. O algoritmo foi utilizado em dois diferentes contextos. Utilizou-se o algoritmo com conjuntos de teste gerados de forma aleatória para verificar a minimização obtida. O algoritmo também foi utilizado para reduzir o esforço em se obter um conjunto completo em relação à detecção de defeitos / THE Model-based testing aims at generating test suites from formal specifications, such as Finite State Machines. Test suites can be obtained either from classical test derivation methods or from some ad-hoc approach. It is desirable to produce a test suite which detects all possible faults of an implementation and has small size, so that its application can be feasible. For practical reasons, the application of the generated test suite may not be possible. Therefore, a subset of test cases should be selected, i.e., a test suite minimization should be performed. However, it is important that the minimization reduces the test application cost, but keeps the effectiveness in revealing faults. In this work, an algorithm is proposed for the minimization of test suites generated from Finite State Machines. The algorithm is based on sufficient conditions, so that test suite completeness can be maintained. The algorithm was used in two different contexts. It was used with randomly generated test suites to verify the minimization obtained. The algorithm was also used to reduce the effort of obtaining a test suite with full fault coverage

En astronautique, une question importante est de contrôler le mouvement d’un satellite soumis à la gravitation des corps célestes de telle sorte que certains indices de performance soient minimisés (ou maximisés). Dans cette thèse, nous nous intéressons à la minimisation de la norme L¹ du contrôle pour le problème circulaire restreint des trois corps. Les conditions nécessaires à l’optimalité sont obtenues en utilisant le principe du maximum de Pontryagin, révélant l’existence de contrôles bang-bang et singuliers. En s’appuyant sur les résultats de Marchal [1] et Zelikin et al. [2], la présence du phénomène de Fuller est mise en évidence par l’analyse des es extrêmales singulières. La contrôlabilité pour le problème à deux corps (un cas dégénéré du problème circulaire restreint des trois corps) avec un contrôle prenant des valeurs dans une boule euclidienne est caractérisée dans le chapitre 2. Le résultat de contrôlabilité est facilement étendu au problème des trois corps puisque le champ de vecteurs correspondant à la dérive est récurrent. En conséquence, si les trajectoires contrôlées admissibles restent dans un compact fixé, l’existence des solutions du problème de minimisation L¹ peut être obtenu par une combinaison du théorème de Filippov (voir [4, chapitre 10]) et une procédure appropriée de convexification (voir [5]). En dimension finie, le problème de minimisation L¹ est bien connu pour générer des solutions où le contrôle s’annule sur certains intervalles de temps. Bien que le principe du maximum de Pontryagin soit un outil puissant pour identifier les solutions candidates pour le problème de minimisation L¹, il ne peut pas garantir que ces candidats sont au moins localement optimaux sauf si certaines conditions d’optimalité suffisantes sont satisfaites. En effet, il est une condition préalable pour établir (et pour être capable de vérifier) les conditions d’optimalité nécessaires et suffisantes pour résoudre le problème de minimisation L¹. Dans cette thèse, l’idée cruciale pour obtenir de telles conditions est de construire une famille paramétrée d’extrémales telle que l’extrémale de référence peut être intégrée dans un champ d’extrémales. Deux conditions de non-pliage pour la projection canonique de la famille paramétrée d’extrémales sont proposées. En ce qui concerne le cas de points terminaux fixés, ces conditions de non-pliage sont suffisantes pour garantir que l’extrémale de référence est localement minimisante tant que chaque point de commutation est régulier (cf. chapitre 3). Si le point terminal n’est pas fixe mais varie sur une sous-variété lisse, une condition suffisante supplémentaire impliquant la géométrie de variété de cible est établie (cf. chapitre 4). Bien que diverses méthodes numériques, y compris celles considérées comme directes [6, 7], indirectes [5, 8], et hybrides [11], dans la littérature sont en mesure de calculer des solutions optimales, nous ne pouvons pas attendre d’un satellite piloté par le contrôle optimal précalculé (ou le contrôle nominal) de se déplacer sur la trajectoire optimale précalculée (ou trajectoire nominale) en raison de perturbations et des erreurs inévitables. Afin d’éviter de recalculer une nouvelle trajectoire optimale une fois que la déviation de la trajectoire nominale s’est produite, le contrôle de rétroaction optimale voisin, qui est probablement l’application pratique la plus importante de la théorie du contrôle optimal [12, Chapitre 5], est obtenu en paramétrant les extrémales voisines autour de la nominale (cf. chapitre 5). Étant donné que la fonction de contrôle optimal est bang-bang, le contrôle optimal voisin comprend non seulement la rétroaction sur la direction de poussée, mais aussi celle sur les instants de commutation. En outre, une analyse géométrique montre qu’il est impossible de construire un contrôle optimal voisin une fois que le point conjugué apparaisse ou bien entre ou bien à des instants de commutation. / In astronautics, an important issue is to control the motion of a satellite subject to the gravitation of celestial bodies in such a way that certain performance indices are minimized (or maximized). In the thesis, we are interested in minimizing the L¹-norm of control for the circular restricted three-body problem. The necessary conditions for optimality are derived by using the Pontryagin maximum principle, revealing the existence of bang-bang and singular controls. Singular extremals are analyzed, and the Fuller phenomenon shows up according to the theories developed by Marchal [1] and Zelikin et al. [2, 3]. The controllability for the controlled two-body problem (a degenerate case of the circular restricted three-body problem) with control taking values in a Euclidean ball is addressed first (cf. Chapter 2). The controllability result is readily extended to the three-body problem since the drift vector field of the three-body problem is recurrent. As a result, if the admissible controlled trajectories remain in a fixed compact set, the existence of the solutions of the L¹-minimizaion problem can be obtained by a combination of Filippov theorem (see [4, Chapter 10], e.g.) and a suitable convexification procedure (see, e.g., [5]). In finite dimensions, the L¹-minimization problem is well-known to generate solutions where the control vanishes on some time intervals. While the Pontryagin maximum principle is a powerful tool to identify candidate solutions for L1-minimization problem, it cannot guarantee that the these candidates are at least locally optimal unless sufficient optimality conditions are satisfied. Indeed, it is a prerequisite to establish (as well as to be able to verify) the necessary and sufficient optimality conditions in order to solve the L¹-minimization problem. In this thesis, the crucial idea for establishing such conditions is to construct a parameterized family of extremals such that the reference extremal can be embedded into a field of extremals. Two no-fold conditions for the canonical projection of the parameterized family of extremals are devised. For the scenario of fixed endpoints, these no-fold conditions are sufficient to guarantee that the reference extremal is locally minimizing provided that each switching point is regular (cf. Chapter 3). If the terminal point is not fixed but varies on a smooth submanifold, an extra sufficient condition involving the geometry of the target manifold is established (cf. Chapter 4). Although various numerical methods, including the ones categorized as direct [6, 7], in- direct [5, 8, 9], and hybrid [10], in the literature are able to compute optimal solutions, one cannot expect a satellite steered by the precomputed optimal control (or nominal control) to move on the precomputed optimal trajectory (or nominal trajectory) due to unavoidable perturbations and errors. In order to avoid recomputing a new optimal trajectory once a deviation from the nominal trajectory occurs, the neighboring optimal feedback control, which is probably the most important practical application of optimal control theory [11, Chapter 5], is derived by parameterizing the neighboring extremals around the nominal one (cf. Chapter 5). Since the optimal control function is bang-bang, the neighboring optimal control consists of not only the feedback on thrust direction but also that on switching times. Moreover, a geometric analysis shows that it is impossible to construct the neighboring optimal control once a conjugate point occurs either between or at switching times.

No description available.

Title: Application of Calculus of Variations Author: Anton'ın Bohata Department: Department of Mathematics Education Supervisor: doc. RNDr. Jana Star'a, CSc., Department of Mathematical Analysis Abstract: The thesis deals with the calculus of variation and its applica- tions. We recall the basic concepts from functional analysis that are needed to formulation of variational problems. Further, the simplest variational prob- lem is discussed. In particular, we present well-known Euler's equation which is a necessary condition of a local extremum of the given functional. The re- sults are then applied to solve various examples from geometry, physics, and economy. Some of these examples can be used to teach at secondary school. Keywords: Euler's equation, functionals, local extrema, calculus of variation

Les systèmes descripteurs incertains sont convenables pour la représentation des incertitudes d’un modèle, du comportement impulsif et des contraintes algébriques entre les variables d’état. Ils peuvent décrire bien plus de phénomènes qu’un système dynamique standard, mais, en conséquence, l’analyse des systèmes descripteurs incertains est aussi plus complexe. Des recherches sont menées de façon à réduire le degré de conservatisme dans l’analyse des systèmes descripteurs incertains. L’utilisation des fonctions de Lyapunov qui sont en mesure de générer des conditions nécessaires et suffisantes pour une telle évaluation y figurent. Les fonctions de Lyapunov polynomiales homogènes font partie de ces classes, mais elles n’ont jamais été employées pour les systèmes descripteurs incertains. Dans cette thèse, nous comblons ce vide dans la littérature en étendant l’usage des fonctions de Lyapunov polynomiales homogènes du cas incertain standard vers les systèmes descripteurs incertains. / Uncertain descriptor systems are a convenient framework for simultaneously representing uncertainties in a model, as well as impulsive behavior and algebraic constraints. This is far beyond what can be depicted by standard dynamic systems, but it also means that the analysis of uncertain descriptor systems is more complex than the standard case. Research has been conducted to reduce the degree of conservatism in the analysis of uncertain descriptor systems. This can be achieved by using classes of Lyapunov functions that are known to be able to provide necessary and sufficient conditions for this evaluation. Homogeneous polynomial Lyapunov functions constitute one of such classes, but they have never been employed in the context of uncertain descriptor systems. In this thesis, we fill in this scientific gap, extending the use of homogeneous polynomial Lyapunov functions from the standard uncertain case for the uncertain descriptor one.

Orientador: Valeriano Antunes de Oliveira / Resumo: Neste trabalho, primeiramente, serão apresentados problemas de otimização nos quais a função objetivo é de múltiplas variáveis e de valor intervalar e as restrições de desigualdade são dadas por funcionais clássicos, isto é, de valor real. Serão dadas as condições de otimalidade usando a E−diferenciabilidade e, depois, a gH−diferenciabilidade total das funções com valor intervalar de várias variáveis. As condições necessárias de otimalidade usando a gH−diferenciabilidade total são do tipo KKT e as suficientes são do tipo de convexidade generalizada. Em seguida, serão estabelecidos problemas de controle ótimo nos quais a funçãao objetivo também é com valor intervalar de múltiplas variáveis e as restrições estão na forma de desigualdades e igualdades clássicas. Serão fornecidas as condições de otimalidade usando o conceito de Lipschitz para funções intervalares de várias variáveis e, logo, a gH−diferenciabilidade total das funções com valor intervalar de várias variáveis. As condições necessárias de otimalidade, usando a gH−diferenciabilidade total, estão na forma do célebre Princípio do Máximo de Pontryagin, mas desta vez na versão intervalar. / Abstract: In this work, firstly, it will be presented optimization problems in which the objective function is interval−valued of multiple variables and the inequality constraints are given by classical functionals, that is, real−valued ones. It will be given the optimality conditions using the E−differentiability and then the total gH−differentiability of interval−valued functions of several variables. The necessary optimality conditions using the total gH−differentiability are of KKT−type and the sufficient ones are of generalized convexity type. Next, it will be established optimal control problems in which the objective function is also interval−valued of multiple variables and the constraints are in the form of classical inequalities and equalities. It will be furnished the optimality conditions using the Lipschitz concept for interval−valued functions of several variables and then the total gH−differentiability of interval−valued functions of several variables. The necessary optimality conditions using the total gH−differentiability is in the form of the celebrated local Pontryagin Maximum Principle, but this time in the intervalar version. / Doutor

Text in Afikaans / In this thesis contributions to the solution of the generalised knapsack problem are given and discussed. Attention is given to problems with functions that are calculable but not necessarily in a closed form. Algorithms and test problems can be used for problems with closed-form functions as well. The focus is on the development of good heuristics and not on exact algorithms. Heuristics must be investigated and good test problems must be designed. A measure of convexity for convex functions is developed and adapted for concave functions. A test problem generator makes use of this measure of convexity to create challenging test problems for the concave, convex and mixed knapsack problems. Four easy-to-interpret characteristics of an S-function are used to create test problems for the S-shaped as well as the generalised knapsack problem. The in uence of the size of the problem and the funding ratio on the speed and the accuracy of the algorithms are investigated. When applicable, the in uence of the interval length ratio and the ratio of concave functions to the total number of functions is also investigated. The Karush-Kuhn-Tucker conditions play an important role in the development of the algorithms. Suf- cient conditions for optimality for the convex knapsack problem with xed interval lengths is given and proved. For the general convex knapsack problem, the key theorem, which contains the stronger necessary conditions, is given and proved. This proof is so powerful that it can be used to proof the adapted key theorems for the mixed, S-shaped and the generalised knapsack problems as well. The exact search-lambda algorithm is developed for the concave knapsack problem with functions that are not in a closed form. This algorithm is used in the algorithms to solve the mixed and S-shaped knapsack problems. The exact one-step algorithm is developed for the convex knapsack problem with xed interval length. This algorithm is O(n). The general convex knapsack problem is solved by using the pivot algorithm which is O(n2). Optimality cannot be proven but in all cases the optimal solution was found and for all practical reasons this problem will be considered as being concluded. A good heuristic is developed for the mixed knapsack problem. Further research can be done on this heuristic as well as on the S-shaped and generalised knapsack problems. / Mathematical Sciences / D. Phil. (Operasionele Navorsing)

Text in Afikaans / In this thesis contributions to the solution of the generalised knapsack problem are given and discussed. Attention is given to problems with functions that are calculable but not necessarily in a closed form. Algorithms and test problems can be used for problems with closed-form functions as well. The focus is on the development of good heuristics and not on exact algorithms. Heuristics must be investigated and good test problems must be designed. A measure of convexity for convex functions is developed and adapted for concave functions. A test problem generator makes use of this measure of convexity to create challenging test problems for the concave, convex and mixed knapsack problems. Four easy-to-interpret characteristics of an S-function are used to create test problems for the S-shaped as well as the generalised knapsack problem. The in uence of the size of the problem and the funding ratio on the speed and the accuracy of the algorithms are investigated. When applicable, the in uence of the interval length ratio and the ratio of concave functions to the total number of functions is also investigated. The Karush-Kuhn-Tucker conditions play an important role in the development of the algorithms. Suf- cient conditions for optimality for the convex knapsack problem with xed interval lengths is given and proved. For the general convex knapsack problem, the key theorem, which contains the stronger necessary conditions, is given and proved. This proof is so powerful that it can be used to proof the adapted key theorems for the mixed, S-shaped and the generalised knapsack problems as well. The exact search-lambda algorithm is developed for the concave knapsack problem with functions that are not in a closed form. This algorithm is used in the algorithms to solve the mixed and S-shaped knapsack problems. The exact one-step algorithm is developed for the convex knapsack problem with xed interval length. This algorithm is O(n). The general convex knapsack problem is solved by using the pivot algorithm which is O(n2). Optimality cannot be proven but in all cases the optimal solution was found and for all practical reasons this problem will be considered as being concluded. A good heuristic is developed for the mixed knapsack problem. Further research can be done on this heuristic as well as on the S-shaped and generalised knapsack problems. / Mathematical Sciences / D. Phil. (Operasionele Navorsing)