Thesis (Ph. D.)--Oregon State University, 2008. / Printout. Includes bibliographical references (leaves 137-141). Also available on the World Wide Web.

abstract: Gray codes are perhaps the best known structures for listing sequences of combinatorial objects, such as binary strings. Simply defined as a minimal change listing, Gray codes vary greatly both in structure and in the types of objects that they list. More specific types of Gray codes are universal cycles and overlap sequences. Universal cycles are Gray codes on a set of strings of length n in which the first n-1 letters of one object are the same as the last n-1 letters of its predecessor in the listing. Overlap sequences allow this overlap to vary between 1 and n-1. Some of our main contributions to the areas of Gray codes and universal cycles include a new Gray code algorithm for fixed weight m-ary words, and results on the existence of universal cycles for weak orders on [n]. Overlap cycles are a relatively new structure with very few published results. We prove the existence of s-overlap cycles for k-permutations of [n], which has been an open research problem for several years, as well as constructing 1- overlap cycles for Steiner triple and quadruple systems of every order. Also included are various other results of a similar nature covering other structures such as binary strings, m-ary strings, subsets, permutations, weak orders, partitions, and designs. These listing structures lend themselves readily to some classes of combinatorial objects, such as binary n-tuples and m-ary n-tuples. Others require more work to find an appropriate structure, such as k-subsets of an n-set, weak orders, and designs. Still more require a modification in the representation of the objects to fit these structures, such as partitions. Determining when and how we can fit these sets of objects into our three listing structures is the focus of this dissertation. / Dissertation/Thesis / Ph.D. Mathematics 2012

Modern computers employ a sophisticated hierarchy of caches to decrease the latency of memory accesses. This led to the development of cache-oblivious algorithms that strive to achieve the best possible performance on such memory hierarchies with minimal knowledge of the exact parameters of the hierarchy. A common technique used in the design of cache-oblivious algorithms is a recursion-based divide-and-conquer method. In this work, we show an alternative technique based on the Gray codes. We use the binary reflected Gray code to traverse arrays in the cache-oblivious way, allowing us to design algorithms for problems such as matrix transposition, naive matrix multiplication or naive convolution that match the asymptotic performance of their recursion-based counterparts. The advantage is that our algorithms can be implemented without recursion (or a stack that simulates it) by using a loopless algorithm. We also introduce a variant of the binary reflected Gray code tuned to certain applications of our technique and an almost loopless algorithm to generate it. Apart from the theoretical analysis of our technique's performance, we also examine its practical performance on the problem of matrix transposition.

Digital encoders are electro-mechanical sensors that measure linear or angular position using special binary patterns. The properties of these patterns influence the traits of the resulting encoders, such as their maximum speed, resolution, tolerance to error, or cost to manufacture. We describe a novel set of patterns that can be used in encoders that are simple and compact, but require some initial movement to register their position. Previous designs for such encoders, called absolute incremental encoders, tend to incorporate separate patterns for the functions of tracking incremental movement and determining the absolute position. The encoders in this work, however, use a single pattern that performs both functions, which maximizes information density and yields better resolution. Compared to existing absolute encoders, these absolute incremental encoders are much simpler with fewer pattern tracks and read heads, potentially allowing for lower-cost assembly of high resolution encoders. Furthermore, as the manufacturing requirements are less stringent, we expect such encoders may be suitable for use in D.I.Y. %27maker%27 projects, such as those undertaken recently by our lab.

An accurate and convenient system for calibrating projector-camera system is presented. A consumer-grade LCD panel is used in place of the traditional printed pattern as the calibration plane. While patterns shown on the panel are used for camera calibration, when we turn the panel off (with its pose kept in space), patterns illuminated by the projector and reflected from it and captured by the camera can be used for the calibration of the projector. This way, patterns for calibrating the camera will not overlap with patterns for calibrating the projector, avoiding confusion in the image data. In addition, even a household-quality LCD panel has industrial-grade planarity. Experiments show that a setup as affordable as this can still have the system parameters calibrated in far less images with much higher accuracy. / Finally, we explore how coding in structured light mechanism can be made even unnecessary. We adopt the above concept of recovering surface orientation from grid-lines, and show that by the use of a regular pattern, like a binary pattern with rhombic pattern elements, an orientation map about the imaged object can be recovered. Specifically, we show that here the correspondences over grid-lines between the projector's pattern panel and the camera's image plane can be approximated with a linear mapping and in turn boost the accuracy of surface normals calculation. We go on and show that, as long as no less than one reference point on the imaged object is available where absolute 3D is known, the above orientation map can even be converted to an absolute depth map by a simple integration process. (Abstract shortened by UMI.) / On the coding issue, we investigate a number of options. Coding can be established over time, and one widely used scheme in this direction is the adoption of Gray code in a series of binary patterns that are projected at different instants. We describe how the traditional Gray code patterns, if augmented by the use of strip shirting, can have the resolution of 3D reconstruction enhanced. The whole system setup of such a system is affordable, nonetheless experiments show that high accuracy can be achieved based on it. The disadvantage of such a system is mainly that multiple image captures are necessary for the operation. / On the image features for establishing correspondences between the projector's pattern panel and the camera's image plane, we propose to use rhombic pattern with binary (i.e., black and white) or colored elements as the projected pattern, and the grid-points between neighboring rhombic elements but not the centroids of the pattern elements themselves as the feature points. We show that, grid-point in the pattern owns the two-fold rotation symmetry, or so-called cmm symmetry, which is largely preserved on the image side after perspective projection and imaging. We propose a grid-point detector that exploits such a symmetry. By avoiding the direct use of raw image intensity, the detector is less sensitive to image noise and surface texture. Comparison with traditional operators shows its promising robustness and accuracy. / The adoption of structured light illumination has been proven an effective and accurate visual means for 3D reconstruction. The system consists of a projector that illuminates controlled pattern or patterns to the target object, and a camera grabbing image or images of the illuminated object. Once correspondences between positions on the projector's pattern panel and positions on the camera's image plane are established, simple triangulation over light rays from the projector and the corresponding light rays to the camera would recover 3D information about the target object. Key issues involved in the approach include (1) Calibration: how the projector and camera can be calibrated so that metric measures about the object can be extracted from the image data; (2) Image Feature Extraction: what image features to use and how to extract them accurately from the image data; and (3) Coding : how the illuminated pattern can be designed so that each position of it embeds in the pattern a unique code which is preserved on the image side, so that position correspondences between the projector's pattern panel and the camera's image plane can be easily established. Each of the issues can affect the accuracy of the system. This thesis aims at providing improved solutions to each of these issues. / Song, Zhan. / Adviser: Ronald Chung. / Source: Dissertation Abstracts International, Volume: 70-06, Section: B, page: 3615. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 149-160). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts in English and Chinese. / School code: 1307.

Darbe tiriamas kėlinių, derinių, poaibių ir Grėjaus kodų generavimo algoritmų sudėtingumas. Atliekama algoritmų analizė. Tyrimo tikslams sukurta programa realizuojanti minėtus algoritmus. / The complexity research of permutations, combinations, subsets and Gray codes generating algorithms is provided in this paper. Algorithms are analyzed and implemented in the application developed for research purposes.

One of the basic streams of modern statistical physics is an effort to understand the frustration and chaos. The basic model to study these phenomena is the finite dimensional Edwards-Anderson Ising model. We present a generalization of this model. We study set systems which are closed under symmetric differences. We show that the important question whether a groundstate in Ising model is unique can be studied in these set systems. Kreweras' conjecture asserts that any perfect matching of the $n$-dimensional hypercube $Q_n$ can be extended to a Hamiltonian cycle. We prove this conjecture. The {\it matching graph} $\mg{G}$ of a graph $G$ has a vertex set of all perfect matchings of $G$, with two vertices being adjacent whenever the union of the corresponding perfect matchings forms a Hamiltonian cycle. We prove that the matching graph $\mg{Q_n}$ is bipartite and connected for $n \ge 4$. This proves Kreweras' conjecture that the graph $M_n$ is connected, where $M_n$ is obtained from $\mg{Q_n}$ by contracting all vertices of $\mg{Q_n}$ which correspond to isomorphic perfect matchings. A fault-free path in $Q_n$ with $f$ faulty vertices is said to be \emph{long} if it has length at least $2^n-2f-2$. Similarly, a fault-free cycle in $Q_n$ is long if it has length at least $2^n-2f$. If all faulty vertices are...

Le cube de Fibonacci est un sous-graphe isométrique de l'hyper- cube ayant un nombre de Fibonacci de sommets. Le cube de Fibonacci a été initialement introduit par W-J. Hsu comme un réseau d'interconnexion et, comme l'hypercube, il a des propriétés topologiques très attractives, mais avec une croissance plus modérée. Parmi ces propriétés, nous discutons de l'hamiltonicité dans le cube de Fibonacci et aussi dans le cube de Lucas qui est obtenu à partir du cube de Fibonacci en supprimant toutes les chaînes qui commencent et nissent avec 1. Nous trouvons également le nombre de som- mets des cubes de Fibonacci et Lucas ayant une certaine excentricité. En n, nous présentons une étude de deux cubes du point de vue de la domination et du 2-packing. / The Fibonacci cube is an isometric subgraph of the hypercube having a Fibonacci number of vertices. The Fibonacci cube was originally proposed by W-J. Hsu as an interconnection network and like the hypercube it has very attractive topological properties but with a more moderated growth. Among these properties, we discuss the hamiltonicity in the Fibonacci cube and also in the Lucas cube which is obtained by removing all the strings that begin and end with 1 from the Fibonacci cube. We give also the eccentricity sequences of the Fibonacci and the Lucas cubes. Finally, we present a study of both cubes from the domination and the 2-packing points of view.

Cette thèse porte sur des classes d’objets combinatoires, qui modélisent des données en bio-informatique. Nous étudions notamment deux méthodes de mutation des gènes à l’intérieur du génome : la duplication et l’inversion. Nous étudions d’une part le problème de la duplication-miroir complète avec perte aléatoire en termes de permutations à motifs exclus. Nous démontrons que la classe de permutations obtenue avec cette méthode après p duplications à partir de l’identité est la classe de permutations qui évite les permutations alternées de longueur 2p + 1. Nous énumérons également le nombre de duplications nécessaires et suffisantes pour obtenir une permutation quelconque de longueur n à partir de l’identité. Nous proposons également deux algorithmes efficaces permettant de reconstituer deux chemins différents entre l’identité et une permutation déterminée. Nous donnons enfin des résultats connexes sur d’autres classes proches. La restriction de la relation d’ordre < induite par le code de Gray réfléchi à l’ensemble des compositions et des compositions bornées induit de nouveaux codes de Gray pour ces ensembles. La relation d’ordre < restreinte à l’ensemble des compositions bornées d’un intervalle fournit encore un code de Gray. L’ensemble des ncompositions bornées d’un intervalle généralise simultanément l’ensemble produit et l’ensemble des compositions d’un entier et donc la relation < définit de façon unifiée tous ces codes de Gray. Nous réexprimons les codes de Gray de Walsh et Knuth pour les compositions (bornées) d’un entier à l’aide d’une unique relation d’ordre. Alors, le code de Gray deWalsh pour des classes de compositions et de permutations devient une sous-liste de celui de Knuth, lequel est à son tour une sous-liste du code de Gray réfléchi. / This thesis considers classes of combinatorial objects that model data in bioinformatics. We have studied two methods of mutation of genes within the genome : duplication and inversion. At first,we study the problem of the whole mirror duplication-random lossmodel in terms of pattern avoiding permutations. We prove that the class of permutations obtained with this method after p duplications from the identity is the class of permutations avoiding alternating permutations of length 2p + 1.We also enumerate the number of duplications that are necessary and sufficient to obtain any permutation of length n from the identity. We also suggest two efficient algorithms to reconstruct two different paths between the identity and a specified permutation. Finally,we give related results on other classes nearby. The restriction of the order relation < induced by the reflected Gray code for the sets of compositions and bounded compositions gives new Gray codes for these sets. The order relation < restricted to the set of bounded compositions of an interval also yields a Gray code. The set of bounded n-compositions of an interval simultaneously generalizes product set and compositions of an integer, and so < puts under a single roof all theseGray codes.We re-expressWalsh’s and Knuth’sGray codes for (bounded) compositions of an integer in terms of a unique order relation, and so Walsh’s Gray code becomes a sublist of Knuth’s code, which in turn is a sublist of the Reflected Gray Code.