La optimización de problemas es un terreno fértil en un mundo que se caracteriza por contar con recursos escasos (naturales, económicos, tecnológicos, infraestructura, sociales, tiempo, etc.). Hacer el mejor uso posible de estos recursos en una tarea, a la vez, importante y difícil. Ofrecer soluciones de calidad, aunque no necesariamente sean las mejores, implica que los recursos excedentes, frutos de la optimización, puedan utilizarse en nuevos productos o servicios. La gran mayoría del software que utilizan las empresas tiene como misión principal la automatización de tareas repetitivas. Una minoría de aplicaciones de software se utiliza como soporte a la toma de decisiones de un decisor humano. Una porción ínfima de artefactos de software son capaces de ofrecer cual es la decisión adecuada para un problema complejo. Es en este último grupo donde se encuentran las técnicas estudiadas en esta tesis. La implementación en el mundo real de algoritmos de búsqueda y optimización se hace necesaria y evidente a medida que aumenta la complejidad de los procesos, las empresas y gobiernos sufren una presión constante para ser más competitivos y eficientes, y los recursos disponibles se presentan como escasos ante una demanda en permanente aumento. Las metaheurísticas están pensadas para ofrecer una solución a este tipo de problemas pertenecientes a la clase de complejidad NP. Si bien son soluciones aproximadas, no exactas, en general son lo suficientemente buenas como para que su utilidad sea valiosa.

The Thompson groups $F, T$ and $V$ are important groups in geometric group theory: $T$ and $V$ being the first discovered examples of finitely presented infinite simple groups. There are many generalisations of these groups including, for $n$ and $r$ natural numbers and $1 < r < n$, the groups $F_{n}$, $T_{n,r}$ and $G_{n,r}$ ($T ≅ T_{2,1}$ and $V ≅ G_{2,1}$). Automorphisms of $F$ and $T$ were characterised in the seminal paper of Brin ([16]) and, later on, Brin and Guzman ([17]) investigate automorphisms of $T_{n, n-1}$ and $F_{n}$ for $n > 2$. However, their techniques give no information about automorphisms of $G_{n,r}$. The second chapter of this thesis is dedicated to characterising the automorphisms of $G_{n,r}$. Presenting results of the author's article [10], we show that automorphisms of $G_{n,r}$ are homeomorphisms of Cantor space induced by transducers (finite state machines) which satisfy a strong synchronizing condition. In the rest of Chapter 2 and early sections of Chapter 3 we investigate the group $\out{G_{n,r}}$ of outer automorphisms of $G_{n,r}$. Presenting results of the forthcoming article [6] of the author's, we show that there is a subgroup $\hn{n}$ of $\out{G_{n,r}}$, independent of $r$, which is isomorphic to the group of automorphisms of the one-sided shift dynamical system. Most of Chapter 3 is devoted to the order problem in $\hn{n}$ and is based on [44]. We give necessary and sufficient conditions for an element of $\hn{n}$ to have finite order, although these do not yield a decision procedure. Given an automorphism $\phi$ of a group $G$, two elements $f, g ∈ G$ are said to be $\phi$-twisted conjugate to one another if for some $h ∈ G$, $g = h−1 f (h)\phi$. This defines an equivalence relation on $G$ and $G$ is said to have the $\rfty$ property if it has infinitely many $\phi$-twisted conjugacy classes for all automorphisms $\phi ∈ \aut{G}$. In the final chapter we show, using the description of $\aut{G_{n,r}}$, that for certain automorphisms, $G_{n,r}$ has infinitely many twisted conjugacy classes. We also show that for certain $\phi ∈ \aut{G_{2,1}}$ the problem of deciding when two elements of $G_{2,1}$ are $\phi$-twisted conjugate to one another is soluble.

Dans cette thèse, on se propose d'étudier les automates de Mealy, c'est-à-dire des transducteurs complets déterministes lettre à lettre ayant même alphabet d'entrée et de sortie. Ces automates sont utilisés depuis les années 60 pour engendrer des (semi-)groupes qui ont parfois des propriétés remarquables, permettant ainsi de résoudre plusieurs problèmes ouverts en théorie des (semi-)groupes. Dans ce travail, on s’intéresse plus particulièrement aux apports possibles de l'informatique théorique à l'étude de ces (semi-)groupes engendrés par automate. La thèse présentée s'articule autours de deux grands axes. Le premier, qui correspond aux chapitres II et III, traite des problèmes de décision et plus spécifiquement du problème de Burnside dans le chapitre II et des points singuliers dans le chapitre III. Dans ces deux chapitres on met en lien des propriétés structurelles de l'automate avec des propriétés du groupe engendré ou de son action. Le second axe, représenté par le chapitre IV, se rapporte à la génération aléatoire de groupes finis. On cherche, en tirant des automates de Mealy aléatoirement dans des classes spécifiques, à engendrer des groupes finis, et on aboutit à un résultat de convergence pour la distribution ainsi obtenue. Ce résultat fait écho au théorème de Dixon pour les groupes de permutations aléatoires / In this thesis, we study Mealy automata, i.e. complete, deterministic, letter-to-letter transducers which have same input and output alphabet. These automata have been used since the 60s to generate (semi)groups that sometimes have remarkable properties, that were used to solve several open problems in (semi)group theory. In this work, we focus more specifically on the possible contributions that theoretical computer science can bring to the study of these automaton (semi)groups.The thesis consists of two main axis. The first one, which corresponds to the Chapters II and III, deals with decision problems and more precisely with the Burnside problem in Chapter II and with singular points in Chapter III. In these two chapters, we link structural properties of the automaton with properties of the generated group or of its action. The second axis, which comprises the Chapter IV, is related with random generation of finite groups. We seek, by drawing random Mealy automata in specific classes, to generate finite groups, and obtain a convergence result for the obtained distribution. This result echoes Dixon's theorem on random permutation groups

Many professions occasionally involve the selection of an alternative from among many problem solutions which have impacts in multiple-interest areas; however, due to the very nature of his work, the practicing engineer, regardless of specialty, is unavoidably engaged in this selection process. The emergence of national concern for environmental and social consequences of technical enterprises, as reflected through legislative action, has accentuated the need for multicriteria design methodologies in some areas of engineering (i.e., automotive). Consequently, interest in the development of pragmatic and theoretically sound approaches to multi-impact design situations has been keen. Any approach to multicriteria design/decision problems involves two fundamental aspects: (1) generating information regarding the range of possible designs and their associated impacts; and (2) generating relative value information which is used to compare the relative imp-cats leading to the selection of a "preferred" or "best compromise" alternative. The methodology developed herein is the integration of a formal mathematical programming technique for generating the full range of feasible alternatives with a pragmatic and well-accepted group-interaction technique for extracting value information regarding alternatives. The integration results in an iterative group-interaction process which leads to successive reductions in the preferred range of alternatives until the most preferred alternative is identified. The methodology developed in this research represents an improvement over other methodologies reported in the literature in two areas: 1) The noninferior set is explicitly identified insuring selection of a group decision point which is noninferior, 2) a least squared error mathematical filtering technique is developed for smoothing relative value data obtained from the decision making body. In addition, a convergence proof is developed which not only indicates the theoretically sound and robust nature of the algorithm developed in this work but in addition provides a basis for an improved class of algorithms for solving classical nonlinear constrained problems. The technique was developed for and implemented in an interactive software package. The multiobjective decision problem is solved in a single encounter with a cooperative decision making group.

This work presents a systematic investigation of two topics. One is in stochastic dynamic general equilibrium. It incorporates private information into dynamic general equilibrium framework. An existence of competitive equilibrium is established. Quantitative analysis is provided for health insurance problem. The other topic is in decision problems under ambiguity. Lack of precise information regarding a decision problem is represented by a set of probabilities. Descriptive richness of the set of probabilities is defi ned. It is used to generalize Skorohod's theorem to sets of probabilities. The latter is used to show the constancy of the coefficient in alpha-maximin multiple prior preferences. Examples illustrate: the implications of this representation; and the restrictions arising from the failure of descriptive richness. / text

This master thesis is devoted to the elements and principles of management. The master thesis deals with the management of field workers of a selected company and subsequent optimization of this procedure. The main aim of master thesis is to optimize the selected decision problem. Based on the analysis of field workers activities is determined significant managerial decision problem. To solve this decision problem is compiled mathematical model and the individual alternative solutions are determined. Based on the individual steps of managerial decision the final recommendations of variant for solving this decision problem is made. The work is devided into two parts, theoretical and practical part. In the theoretical part we acquaint ourselves with the problems with the help of scientific literature. The practical part deals with the use of the scientific literature in practice in order to optimize decision-making problem and management field workers of a selected company.

In the presented work we focus on applications of decision problems from combinatorial group theory. Namely we analyse the Shpilrain-Zapata pro- tocol. We give formal proof that small cancellation groups are good platform for the protocol because the word problem is solvable in linear time and they are generic. We also analyse the complexity of the brute force attack on the protocol and show that in a theoretical way the protocol is immune to attack by adversary with arbitrary computing power.

In this thesis, we will discuss the construction of algorithms for solving Constraint Satisfaction Problems (CSPs), and describe two new ways of approaching them. Both approaches are based on the idea that it is sometimes faster to solve a large number of restricted problems than a single, large, problem. One of the strong points of these methods is that the intuition behind them is fairly simple, which is a definite advantage over many techniques currently in use. The first method, the covering method, can be described as follows: We want to solve a CSP with n variables, each having a domain with d elements. We have access to an algorithm which solves problems where the domain has size e &lt; d, and we want to cover the original problem using a number of restricted instances, in such a way that the solution set is preserved. There are two ways of doing this, depending on the amount of work we are willing to invest; either we construct an explicit covering and end up with a deterministic algorithm for the problem, or we use a probabilistic reasoning and end up with a probabilistic algorithm. The second method, called the partitioning method, relaxes the demand on the underlying algorithm. Instead of having a single algorithm for solving problems with domain less than d, we allow an arbitrary number of them, each solving the problem for a different domain size. Thus by splitting, or partitioning, the domain of the large problem, we again solve a large number of smaller problems before arriving at a solution. Armed with these new techniques, we study a number of different problems; the decision problems (d, l)-CSP and k-Colourability, together with their counting counterparts, as well as the optimisation problems Max Ind CSP, Max Value CSP, Max CSP, and Max Hamming CSP. Among the results, we find a very fast, polynomial space algorithm for determining k-colourability of graphs.

In this Thesis, we first deploy Gittins index theory to establish the indexability of inter-alia general families of restless bandits that arise in problems of stochastic scheduling with switching penalties and machine maintenance. We also give formulae for the resulting indices. Numerical investigations testify the strong performance of the index heuristics.The second class of problems concerns two families of Markov decision problems. The spinning plates problem concerns the optimal management of a portfolio of assets whose yields grow with investment but otherwise decline. In the model of asset exploitation called the squad system, the yield from an asset declines when it is utilised but will recover when the asset is at rest. Simply stated conditions are given which guarantee general indexability of the problem together with necessary and sufficient conditions for strict indexability. The index heuristics, which emerge from the analysis, are assessed numerically and found to perform strongly.

Thesis (MSc)--Stellenbosch University, 2004. / ENGLISH ABSTRACT: Multi-criteria decision-making (MCDM) is a set of techniques designed specifically for the analysis of complex problems. Geographical Information Systems (GIS) focus on spatial problem-solving and spatial analysis. The integration of these methodologies offers a powerful approach to decision making. Despite the fact that most spatial decision problems are multi-criteria problems by nature, the process of MCDM is not well established or effectively integrated into the field of spatial analysis and GIS. This research focuses on bridging the gap between MCDM and GIS. To this end, a generic MCDM extension was designed and implemented in ArcView. As a result, a first version MCDM extension is offered. The extension expands ArcView's functionality with a limited set of MCDM methods. This functionality is illustrated on two problems involved with developing the tourism potential at Coutada 16 Wildlife Reserve in Mozambique. The MCDM extension facilitates procedures that allow the evaluation of spatial problems and includes the ability to deal with both raster and vector data. This system offers a generic problemsolving environment, which can be used to evaluate geographical problems of any nature. This research identifies a number of improvements to the developed functionality and successfully illustrates the potential problem-solving capabilities associated with MCDM integrated with ArcView. / AFRIKAANSE OPSOMMING: Multi Kriteria Besluitneming (MKBN) is n versameling metodes vir die analise van komplekse probleme. Geografiese Inligtingstelsels (GIS) fokus op geografiese probleemoplossing en analise. Die integrasie van hierdie twee metodologieë bied 'n kragtige benadering tot besluitneming. Ten spyte daarvan dat die meeste geografiese probleme in wese meerveranderlik van aard is, is MKBN nie effektiefbinne die raamwerk van GIS geïntegreer nie. Hierdie studie fokus op die oorbrugging van die gaping tussen MKBN en GIS. Met hierdie doel voor oë is 'n generiese MKBN-uitbreiding vir ArcView ontwerp en geïmplementeer. Die resultaat is 'n eerste- weergawe MKBN-uitbreiding. Die uitbreiding brei ArcView se funksionaliteit uit om 'n beperkte versameling MKBN-metodes in te sluit. Die nuut ontwikkelde funksies word geïllustreer aan die hand van twee probleme wat die ontwikkeling van die toerismepotensiaal vir die Coutada 16 Wildreservaat in Mosambiek aanspreek. Die uitbreiding maak voorsiening vir 'n MKBN-evaluasie van geografiese probleme en besit die vermoë om beide vektor- en roosterdata te analiseer. Hierdie stelsel verskaf 'n generiese omgewing vir probleemoplossing wat gebruik kan word om byna enige geografiese probleem te analiseer. Die studie identifiseer verbeteringe op en uitbreidings van die ontwikkelde funksies en slaag daarin om die potensiaal van probleemoplossing wat deur die integrasie van MKBN-tegnieke met ArcView moontlik gemaak word, te illustreer.