Este trabalho propõe um módulo básico de aquisição e pré-processamento de imagem colorida aplicado a robôs móveis, implementado em hardware reconfigurável, dentro do conceito de sistemas SoC (System-on-a-Chip). O módulo básico é apresentado em conjunto com funções mais específicas de pré-processamento de imagem, que são utilizadas como base para a verificação das funcionalidades implementadas no trabalho proposto. As principais funções realizadas pelo módulo básico são: montagem de frames a partir dos pixels obtidos da câmera digital CMOS, controle dos diversos parâmetros de configuração da câmera e conversão de padrões de cores. Já as funções mais específicas abordam as etapas de segmentação, centralização, redução e interpretação das imagens adquiridas. O tipo de dispositivo reconfigurável utilizado neste trabalho é o FPGA (Field-Programmable Gate Array), que permite maior adequação das funções específicas às necessidades das aplicações, tendo sempre como base o módulo proposto. O sistema foi aplicado para reconhecer gestos e obteve a taxa 99,57% de acerto operando a 31,88 frames por segundo. / This work proposes a basic module for a mobile robot color image capture and pre-processing, implemented in reconfigurable hardware based on SoC (System-on-a-Chip). The basic module is presented with a specifics image pre-processing function that are used as a base for verify the functionalities implemented in this research. The mains functions implemented on this basic module are: to read the pixels provide by the CMOS camera for compose the frame, to adjust the parameters of the camera control and to convert color space. The specifics image pre-processing functions are used to do image segmentation, centralization, reduction and image classification. The reconfigurable dispositive used in this research is the FPGA (Field-Programmable Gate Array) that permit to adapt the specific function according to the application needs. The system was applied to recognize gesture and had 99,57% rate of true recognition at 31,88 frames per second.

Mapas pedológicos são importantes fontes de informação necessárias à agricultura, mas praticamente inexistentes em escalas adequadas para o Brasil, e seu levantamento pelo método convencional para a demanda brasileira é inviável. Como alternativa ao problema, mapeamento pedológico digital apresenta-se como uma área do conhecimento que envolve as relações das informações de campo, laboratório e pontuais de solos com métodos quantitativos via imagens de satélite e atributos do relevo para inferir atributos e classes. A literatura destaca, portanto, a importância do estudo da posição espacial de pontos amostrais na estimativa de atributos do solo a partir dos valores espectrais de imagens de satélite, aliado a isso, faz-se importante o cruzamento dos atributos do solo estimados e espacializados para chegar a classes de solo. Face ao exposto, o objetiva-se o desenvolvimento de uma técnica via imagem de satélite, dados espectrais e atributos do relevo, integrados por lógica booleana, para determinar mapas pedológicos. O trabalho foi realizado no município de Rio das Pedras, SP e entornos, numa área total de 47.882 ha. Onde, realizou-se processamento de imagens de satélites multitemporais, para obtenção da informação espectral da superfície de solo exposto. Esta informação foi correlacionada com espectro de laboratório de pontos amostrais em subsuperfície (profundidade 80-100 cm) e estimou-se os espectros simulando bandas de satélite para locais desconhecidos. Elaborou-se uma chave de classificação de solos por cruzamento de mapas de atributos via lógica booleana, onde definiu os seguintes atributos a serem mapeados: argila, V% e matéria orgânica (M.O) na profundidade 0-20 cm e argila, CTC, V%, m%, Al, ferro total, matiz, valor e croma na profundidade 80-100 cm. As estimativas de espectros em subsuperfície e dos atributos dos solos nas duas profundidades foram realizadas pela técnica multivariada regressão geograficamente ponderada (GWR), que teve seu desempenho preditivo avaliado pela comparação com desempenho preditivo da técnica de regressão linear múltipla (MRL). Os resultados mostraram correlação entre os espectros das duas profundidades, com R2 de validação acima 0.6. Argila (0-20 e 80-100 cm), matiz, valor e croma foram os atributos do solo que obtiveram as melhores estimativas com R2 acima 0.6. A técnica multivariada GWR obteve-se desempenho superior ao MRL. O mapa pedológico digital comparado aos mapas de solos detalhados de levantamentos convencionais obteve índice kappa de 34.65% e acurácia global de 54,46%. Tal resultado representa um nível regular de classificação. Por outro lado, deve se considerar que se trata de uma região de alta complexidade geológica e compreendendo heterogeneidade de solos. A técnica desenvolvida mostra-se com potencial de evolução no mapeamento digital de solos à medida que forem evoluindo as estimativas de atributos de solos e ajustes nos critérios da chave de classificação. / Soil maps are important sources of information necessary for agriculture, but practically absent in appropriate scales for Brazil, and its mapping by the conventional method for the brazilian demand is impracticable. How an alternative to the problem, digital pedological mapping appears as an area of knowledge that involves the relationship of field information, laboratory and point of soils with quantitative methods by satellite images and relief attributes to predict attributes and classes. The literature highlights therefore the importance of studying the spatial position of sampling points in the estimation of soil attributes from spectral values of satellite images, combined to this, is an important the crossing of the estimated and spatialized soil attributes to get the soil classes. In view of exposed, the objective is the development of a technique satellite image, spectral data and attributes of relief, integrated by boolean logic to determine soil maps. The work was carried out in Rio das Pedras county, SP, and surroundings, in a total area of 47,882 ha. Which was held processing multitemporal satellite images, to obtain spectral information of exposed soil surface. This information was correlated with laboratory spectra of sample points in the subsurface (depth 80-100 cm) and was estimated spectra simulating satellite bands to unknown locations. Produced is a soil classification key for cross attribute maps by boolean logic, which defines the following attributes to be mapped: clay, cation saturation and organic matter (OM) in the 0-20 cm depth and clay, CEC, cation saturation, aluminiu saturation, Al, total iron, hue, value and chroma in depth 80-100 cm. The estimates spectra subsurface and soil attributes in two depths were performed by multivariate technique geographically weighted regression (GWR), which had its predictive performance is evaluated by comparison with predictive performance of multiple linear regression (MRL). The results showed a correlation between the spectra of the two depths, with validation R2 above 0.6. Clay (0-20 and 80-100 cm), hue, value and chroma were the soil attributes obtained the best estimates R2 above 0.6. The GWR multivariate technique yielded better performance than MRL. The digital soil map compared to the detailed soil maps of conventional surveys obtained kappa index of 34.65% and overall accuracy of 54.46%. This result is a regular level of classification. On the other hand, it must be considered that it is a highly complex geological region and comprising heterogeneity of soils. The technique developed shows with potential developments in digital soil mapping as they evolve estimates of soil attributes and adjustments to the classification key criteria.

Le sujet abordé dans cette thèse concerne la contrôlabilité d’une classe de systèmes spatio-temporels, entièrement discrets de type automates cellulaires (AC). Le but de cette étude est de mettre en lumière de nouvelles pistes pour prouver la contrôlabilité des systèmes complexes. Plus spécifiquement, cette thèse se focalise sur la contrôlabilité régionale qui consiste à se restreindre à une région du domaine où le système devra atteindre un objectif donné à travers des actions ciblées. Le cas d’AC Booléens a été particulièrement examiné tout au long de cette thèse. La première partie est consacrée à l’étude du problème de la contrôlabilité régionale des AC déterministes lorsque les actions sont exercées sur la frontière de la régioncontrôlée. Une première démarche que nous avons utilisée s’appuie sur les chaines de Markov et la contrôlabilité est caractérisée en établissant une matrice similaire à leur matrice de transition en utilisant les définitions d’une chaîne ergodique et régulière. Cette étude a été étendue au cas des AC probabilistes qui sont largement utilisés pour modéliser de nombreux phénomènes réels. Le même problème a été appréhendé en utilisant des outils de la théorie des graphes. Nous proposons des conditions nécessaires et suffisantes pour la contrôlabilité régionale des AC déterministes en utilisant les notions de circuit hamiltonien et de composante fortement connexe. Le contrôle qui assure la contrôlabilité régionale est défini à travers un algorithme préimages. La deuxième partie est dédiée au problème de la contrôlabilité régionale frontière des AC Booléens qui consiste à agir sur la frontière du domaine pour atteindre un objectif sur une région cible. Nous considérons d’abord des AC linéaires pour lesquels nousdonnons un résultat de caractérisation grâce à la condition de Kalman. Nous proposons un algorithme pour déterminer le contrôle qui permet de forcer l’apparition d’une configuration désirée dans la région d’étude. Le cas des AC non linéaires a été également considéré en utilisant un algorithme de recherche des préimages. / The issue addressed in this thesis concerns the controllability of a class of discrete spatio-temporal systems named cellular automata (CA). The purpose of this study is to highlight new ways to prove the controllability of complex systems. Morespecifically, this thesis focuses on regional controllability which consists in restricting the study to a subregion of the domain where the system will have to achieve a given objective through targeted actions. The case of Boolean CA have been particularly examined throughout this thesis. The first part is devoted to the study of the problem of the regional controllability of deterministic CAs when the actions are exerted on the boundaries of the controlled region. A first approach that we used relies on Markov chains and controllability is characterized by establishing a matrix similar to their transition matrix using the definitions of a regular and ergodic chain. This study has been extended to the case of probabilistic CAs that are widely used tomodel many real phenomena. The same problem has been apprehended using tools of graph theory. We proposenecessary and sufficient conditions for the regional controllability of deterministic CAs using the notions of Hamiltonian circuit and strongly connected component. The control that ensures regional controllability is defined through a preimage algorithm.The second part is devoted to the problem of the boundary regional controllability of Boolean CAs, which consists of acting on the boundary of the domain in order to reach a desired goal in a target region. We first consider linear CAs for which we givea characterization result using the Kalman condition. We propose an algorithm to determine the control that allows to force the appearance of a desired configuration in the study area. The case of nonlinear CAs was also considered using a preimagesearch algorithm.

This master's thesis introduces the Random Boolean Networks as a developmental model in the evolutionary design. The representation of the Random Boolean Networks is described. This representation is combined with an evolutionary algorithm. The genetic operators are described too. The Random Boolean Networks are used as the developmental model for  the evolutionary design of the combinational circuits and the sorting networks. Moreover a representation of the Random Boolean Networks for the design of image filters is introduced. The proposed methods are evaluated in different case-studies. The results of the experiments are discussed together with the potential improvements  and topics of the next research.

Title: Boolean techniques in Knowledge representation Author: Miloš Chromý Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor: Doc. RNDr. Ondřej Čepek, Ph.D., Department of Theoretical Com- puter Science and Mathematical Logic Abstract: In this thesis we will investigate switch-list representations of Boolean function and we will explore the biclique satisfiable formulas. Given a truth table representation of a Boolean function f the switch-list rep- resentation of f is a list of Boolean vectors from the truth table which have a different function value than the preceding Boolean vector in the truth table. We include this type of representation in the Knowledge Compilation Map [Dar- wiche and Marquis, 2002] and argue that switch-lists may in certain situations constitute a reasonable choice for a target language in knowledge compilation. First, we compare switch-list representations with a number of standard repre- sentations (such as CNF, DNF, and OBDD) with respect to their relative suc- cinctness. As a by-product of this analysis we also give a short proof of a long standing open question from [Darwiche and Marquis, 2002], namely the incom- parability of MODS (models) and PI (prime implicates) representations. Next, using the succinctness result between...

Despite spectacular progress in biophysics, molecular biology and biochemistry our ability to predict the dynamic behavior of multicellular systems under different conditions is very limited. An important reason for this is that still not enough is known about how cells change their physical and biological properties by genetic or metabolic regulation, and which of these changes affect the cell behavior. For this reason, it is difficult to predict the system behavior of multicellular systems in case the cell behavior changes, for example, as a consequence of regulation or differentiation. The rules that underlie the regulation processes have been determined on the time scale of evolution, by selection on the phenotypic level of cells or cell populations. We illustrate by detailed computer simulations in a multi-scale approach how cell behavior controlled by regulatory networks may emerge as a consequence of an evolutionary process, if either the cells, or populations of cells are subject to selection on particular features. We consider two examples, migration strategies of single cells searching a signal source, or aggregation of two or more cells within minimal multiscale models of biological evolution. Both can be found for example in the life cycle of the slime mold Dictyostelium discoideum. However, phenotypic changes that can lead to completely different modes of migration have also been observed in cells of multi-cellular organisms, for example, as a consequence of a specialization in stem cells or the de-differentiation in tumor cells. The regulatory networks are represented by Boolean networks and encoded by binary strings. The latter may be considered as encoding the genetic information (the genotype) and are subject to mutations and crossovers. The cell behavior reflects the phenotype. We find that cells adopt naturally observed migration strategies, controlled by networks that show robustness and redundancy. The model simplicity allow us to unambiguously analyze the regulatory networks and the resulting phenotypes by different measures and by knockouts of regulatory elements. We illustrate that in order to maintain a cells' phenotype in case of a knockout, the cell may have to be able to deal with contradictory information. In summary, both the cell phenotype as well as the emerged regulatory network behave as their biological counterparts observed in nature.

Interface balance laws are derived to describe transport across a phase interface. This is used to derive generalized conditions for phase nucleation and growth, valid even for solids with inhomogeneous surface stress.<div><br></div><div>An explicit interface tracking approach called Enriched Isogeometric Analysis (EIGA) is used to simulate phase evolution. Algebraic level sets are used as a measure of distance and for point projection, both necessary operations in EIGA. Algebraic level sets are observed to often fail for surfaces. Rectification measures are developed to make algebraic level sets more robust and applicable for general surfaces. The proposed methods are demonstrated on electromigration problems. The simulations are validated by modeling electromigration experiments conducted on Cu-TiN line structures.</div><div><br></div><div>To model topological changes, common in phase evolution problems, Boolean operations are performed on the algebraic level sets using R-functions. This is demonstrated on electromigration simulations on solids with multiple voids, and on a bubble coalescence problem. </div>

Dans cette thèse, nous étudions la sécurité de primitives cryptographiques. Ces systèmes sont fondés sur des transformations utilisant des objets mathématiques représentés de multiples manières. Nous utilisons alors certaines structures inhérentes à leurs composantes, et jusqu'alors non prises en compte, pour mettre en évidence de nouvelles vulnérabilités. Par l'exploitation de diverses représentations, nous avons ainsi cryptanalysé des chiffrements authentifiés de la compétition CAESAR, des chiffrements à flot spécifiques et des constructions génériques. Nous avons donné des critères de conception en vue de la standardisation par le NIST de chiffrements à bas coût. Dans le cas des chiffrements à flot, nous avons défini de nouveaux critères cryptographiques plus pertinents que les critères usuels. Plus précisément, nous analysons la sécurité des chiffrements par bloc légers au regard des récentes attaques par invariant, et nous montrons comment les éviter par un choix approprié de la couche linéaire de diffusion et des constantes de tour. Nous proposons une nouvelle cryptanalyse des registres filtrés, grâce à la décomposition des éléments dans les sous-groupes multiplicatifs du corps fini à 2^n éléments. L'analyse du chiffrement FLIP, mais aussi du générateur pseudo-aléatoire de Goldreich a mis en évidence des faiblesses exploitables dans des attaques de type ``supposer et déterminer'', qui nécessitent la prise en compte de nouveaux critères sur les fonctions booléennes utilisées dans ce contexte. Enfin, nous cryptanalysons une version simplifiée du chiffrement authentifié Ketje en utilisant plusieurs techniques, permettant ainsi d'affiner l'évaluation de sa sécurité. / In this thesis, we study the security of symmetric cryptographic primitives. These systems are based on transformations relying on mathematical objects that can be represented in multiple ways. We then exploit different induced structures to highlight new vulnerabilities. By exploiting various representations, we cryptanalyzed some schemes submitted to the CAESAR competition, and also some dedicated and generic stream ciphers. We exhibited design criteria for lightweight block ciphers in view of the NIST standardization process and in the case of stream ciphers we defined new cryptographic criteria more relevant than the usual ones. More precisely, we study the security of lightweight block ciphers with respect to the recent invariant attacks, and we show how to avoid them with an appropriate choice of the linear layer and the round constants. We propose a new cryptanalysis of the filtered registers, by decomposing elements in the multiplicative subgroups of the finite field with 2^n elements. The analysis of the FLIP cipher, but also of the Goldreich pseudo-random generator, revealed weaknesses that are exploitable in ``guess and determine'' attacks. This leads to new criteria on the Boolean functions used in this context. Finally, we cryptanalyze a weaker version of the authenticated encryption scheme Ketje using several techniques, in order to refine the security evaluation of this cipher.

We extend the study of learning and generalization in feed forward Boolean networks to random Boolean networks (RBNs). We explore the relationship between the learning capability and the network topology, the system size, the training sample size, and the complexity of the computational tasks. We show experimentally that there exists a critical connectivity Kc that improves the generalization and adaptation in networks. In addition, we show that in finite size networks, the critical K is a power-law function of the system size N and the fraction of inputs used during the training. We explain why adaptation improves at this critical connectivity by showing that the network ensemble manifests maximal topological diversity near Kc. Our work is partly motivated by self-assembled molecular and nanoscale electronics. Our findings allow to determine an automata network topology class for efficient and robust information processing.

Les problèmes de séquencement et d'ordonnancement forment une famille de problèmes combinatoires qui implique la programmation dans le temps d'un ensemble d'opérations soumises à des contraintes de capacités et de ressources. Nous contribuons dans cette thèse à la résolution de ces problèmes dans un contexte de satisfaction de contraintes et d'optimisation combinatoire. Nos propositions concernent trois aspects différents: comment choisir le prochain nœud à explorer (recherche)? comment réduire efficacement l'espace de recherche (propagation)? et que peut-on apprendre des échecs rencontrés lors de la recherche (apprentissage)? Nos contributions commencent par une étude approfondie des heuristiques de branchement pour le problème de séquencement de chaîne d'assemblage de voitures. Cette évaluation montre d'abord les paramètres clés de ce qui constitue une bonne heuristique pour ce problème. De plus, elle montre que la stratégie de branchement est aussi importante que la méthode de propagation. Deuxièmement, nous étudions les mécanismes de propagation pour une classe de contraintes de séquencement à travers la conception de plusieurs algorithmes de filtrage. En particulier, nous proposons un algorithme de filtrage complet pour un type de contrainte de séquence avec une complexité temporelle optimale dans le pire cas. Troisièmement, nous investiguons l'impact de l'apprentissage de clauses pour résoudre le problème de séquencement de véhicules à travers une nouvelle stratégie d'explication réduite pour le nouveau filtrage. L'évaluation expérimentale montre l'importance de l'apprentissage de clauses pour ce problème. Ensuite, nous proposons une alternative pour la génération retardée de variables booléennes pour encoder les domaines. Finalement, nous revisitons les algorithmes d'analyse de conflits pour résoudre les problèmes d'ordonnancement disjonctifs. En particulier, nous introduisons une nouvelle procédure d'analyse de conflits dédiée pour cette famille de problèmes. La nouvelle méthode diffère des algorithmes traditionnels par l'apprentissage de clauses portant uniquement sur les variables booléennes de disjonctions. Enfin, nous présentons les résultats d'une large étude expérimentale qui démontre l'impact de ces nouveaux mécanismes d'apprentissage. En particulier, la nouvelle méthode d'analyse de conflits a permis de découvrir de nouvelle bornes inférieures pour des instances largement étudiées de la littérature / Sequencing and scheduling involve the organization in time of operations subject to capacity and resource constraints. We propose in this dissertation several improvements to the constraint satisfaction and combinatorial optimization methods for solving these problems. These contributions concern three different aspects: how to choose the next node to explore (search)? how much, and how efficiently, one can reduce the search space (propagation)? and what can be learnt from previous failures (learning)? Our contributions start with an empirical study of search heuristics for the well known car-sequencing problem. This evaluation characterizes the key aspects of a good heuristic and shows that the search strategy is as important as the propagation aspect in this problem. Second, we carefully investigate the propagation aspect in a class of sequencing problems. In particular, we propose an algorithm for filtering a type of sequence constraints which worst case time complexity is lower than the best known upper bound, and indeed optimal. Third, we investigate the impact of clause learning for solving the car-sequencing problem. In particular, we propose reduced explanations for the new filtering. The experimental evaluation shows compelling evidence supporting the importance of clause learning for solving efficiently this problem. Next, we revisit the general approach of lazy generation for the Boolean variables encoding the domains. Our proposition avoids a classical redundancy issue without computational overhead. Finally, we investigate conflict analysis algorithms for solving disjunctive scheduling problems. In particular, we introduce a novel learning procedure tailored to this family of problems. The new conflict analysis differs from conventional methods by learning clauses whose size are not function of the scheduling horizon. Our comprehensive experimental study with traditional academic benchmarks demonstrates the impact of the novel learning scheme that we propose. In particular, we find new lower bounds for a well known scheduling benchmark