Many real world problems are naturally distributed, whether they are spatially, cognitively, or otherwise. Distributed problems naturally lend themselves to solutions using multi-agent paradigms. Distributed Constraint Satisfaction Problems (DisCSPs) are a class of such distributed problems. In DisCSPs, variables and constraints are distributed between agents. Most distributed algorithms, although exponential in the worst-case, can have a good performance in the average case. The main purpose of this research is to statistically assess difference between the empirical performances of major state of the art DisCSP algorithms including Multi-Sectioned Constraint Network (MSCN) based algorithms, that have never been empirically compared against other DisCSP algorithms. In this thesis, we select a set of state of the art DisCSP algorithms and compare them on randomly generated instances of binary DisCSPs with a wide range of characteristics. Distributed algorithms ADOPT, DSA, DPOP, and MSCN based algorithms were selected based on a set of high level criteria. We explore how these algorithms relatively compare with each other on a range of DisCSPs with different parameters. Their performances are evaluated according to computation time (in the form of non-concurrent computational steps or NCCCs) and communication load (in the form of number of messages as well as volume of messages). Statistical parametric tests are used to aid interpretation of the performance results. In addition, this thesis discusses privacy issues associated with these DisCSP algorithms.

Analog to digital converters (ADCs) are the fundamental building blocks in communication systems. The need to design ADCs, which are area and/or power efficient, has been common. Various ADC architectures, constrained by resolution capabilities, can be used for this purpose. The cyclic algorithmic architecture of ADC with moderate number of bits comes out to be probably best choice for the minimum area implementation. In this thesis a cyclic ADC is designed using CMOS 65 nm technology. The ADC high-level model is thoroughly explored and its functional blocks are modelled to attain the best possible performance. In particular, the nonlinearities which affect the cyclic/algorithmic converter are discussed. This ADC has been designed for built-in-self-testing (BiST) on a chip. It is only functional during the testing phase, so power dissipation is not a constraint while designing it. As it is supposed to be integrated as an extra circuitry on a chip, its area really matters. The ADC is designed as 10-bit fully differential switch-capacitor (SC) circuit using 65nm CMOS process with 1.2V power supply. A two stage Operational Transconductance Amplifier (OTA) is used in this design to provide sufficient voltage gain. The first stage is a telescopic OTA whereas the second is a common source amplifier. The bottom plate sampling is used to minimize the charge injection effect which is present in the switches.

CADSYN (Computer Aided Design SYNthesis) is a visual, interactive computer program working under Computer Aided Design (CAD) enviroment, which accomplishes the synthesis and analysis of planar four-bar mechanisms. The synthesis tasks are motion generation, path generation and function generation. During synthesis, the dyadic approach is utilized which introduces vector pairs and complex number algebra to model the motion. The possible solutions can be limited for link dimensions, the center circle point curves within a certain region, transmission angle characteristics, branch and order defects. The designed mechanism can be analyzed for velocity, acceleration and transmission angle and any of the data can be exported to Excel&reg / for further analysis. The software is designed to provide the user maximum feasible number of solutions. In four multiply separated position synthesis, if there is flexibility in the value(s) of one or any number of input parameter(s), designer can obtain different Burmester curves by changing those parameter(s). Designer can also simulate the kinematics of the mechanism by using drawing functions that are available from the CAD iv enviroment at any time. Drawing parts in the design plane can be attached to any link of the mechanism and can be simulated throughout the motion as part of the link it is attached. As a whole, this computer program is designed to satisfy the needs of mechanism designers while working in CAD enviroment.

Este trabalho trata de estimativas inferiores para o primeiro autovalor de Dirichlet para dom nios multiplamente conexos contidos em variedades riemannianas. Essas estimativas consideram o supremo da curvatura seccional da variedade e a curvatura do bordo do domínio. Para obter os resultados, usa-se uma estimativa C0 para solucões da equação de Poisson. / Lower bounds for the rst Dirichlet eigenvalue are presented. We consider multiply connected domains in riemannian manifolds. The estimates are obtained using hypothesis on the supremum of the manifold's sectional curvature and on the domain's boundary curvature. C0 estimates for solutions of Poissons equation are used to prove the results.

Este trabalho trata de estimativas inferiores para o primeiro autovalor de Dirichlet para dom nios multiplamente conexos contidos em variedades riemannianas. Essas estimativas consideram o supremo da curvatura seccional da variedade e a curvatura do bordo do domínio. Para obter os resultados, usa-se uma estimativa C0 para solucões da equação de Poisson. / Lower bounds for the rst Dirichlet eigenvalue are presented. We consider multiply connected domains in riemannian manifolds. The estimates are obtained using hypothesis on the supremum of the manifold's sectional curvature and on the domain's boundary curvature. C0 estimates for solutions of Poissons equation are used to prove the results.

Les systèmes à canaux non fiables ont été introduits à l'origine comme un modèle de communication. Ils ont donné naissance à une classe de complexité restée mal comprise pendant longtemps. Dans cette thèse, nous étudions et comblons certaines des plus importantes lacunes dans la connaissance de cette classe. Nous fournissons entre autres des bornes inférieure et supérieure qui se rejoignent pour la complexité en temps. Puis nous proposons un nouvel outil de preuve : le Problème de Sous Mot de Post (PEP). C'est un problème simple, inspiré du Problème de Correspondance de Post, et complet pour cette classe de complexité. Nous étudions ensuite PEP et ses variantes, ainsi que les langages de solutions de PEP sur lesquels nous avons fourni des résultats de complexité et des outils de preuve tels que des lemmes de pompage. / Lossy channel systems were originally introduced to model communication protocols. It gave birth to a complexity class wich remained scarcely undersood for a long time. In this thesis we study some of the most important gaps. In particular, we bring matching upper and lower bounds for the time complexity. Then we describe a new proof tool : the Post Embedding Problem (PEP) which is a simple problem, closely related to the Post Correspondence Problem, and complete for this complexity class. Finally, we study PEP, its variants and the languages of solutions of PEP on which we provide complexity results and proof tools like pumping lemmas.

京都大学 / 新制・課程博士 / 博士(情報学) / 甲第23323号 / 情博第759号 / 新制||情||129(附属図書館) / 京都大学大学院情報学研究科数理工学専攻 / (主査)教授 中村 佳正, 教授 矢ヶ崎 一幸, 准教授 辻本 諭 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

The constant endeavor to measure and record neural signals from the human brain and anticipate the results to figure out the mechanism which governs the functionality of our brain and its true behavior is the major driving force behind this thesis. Neural recording integrated circuits (ICs) are often inserted directly into the brain, with a set of probes for sensing these action potentials (and local field potentials), and appropriate circuitry for amplifying the neural signals (Pre-Amp), sampling and converting the analog signals to digital (ADC) and transmitting the resulting digital signal (Transmitter) to a nearby reader instrument (Receiver). Action potentials are comprised of signals typically looking like spikes having a peak voltage of 1-2mV, whereas local field potentials are continuous signals generally having an amplitude of around 100-200μV often with a dc component of several mV. Fourier analysis of action potentials and local field potentials show frequency components in the range of 0.1 Hz up to 10kHz. This thesis proposes a low-power 5-bit algorithmic A/D converter to feed a 5-stage serial shift register for use in sampling and converting a presumed neuron action potential signal at the rate of 20k samples/sec. In addition to that, a low-power preamp with at least 40dB gain and a low-pass type spectrum having a unity-gain frequency of at least 20MHz is used to amplify the input signal. The algorithmic A/D converter includes a sample-and-hold circuit for sampling the analog action potential spike at a rate of 20kHz. The ADC utilizes an X2 gain circuit based on a capacitive redistribution technique. A less complex circuit in terms of dependency on Capacitor sizing and their non-ideal effects is the key factor for selecting this type of ADC which can be used for neural recording applications. All the circuits are designed based on the IBM/Global Foundries 8HP 130nm BiCMOS technology.

In this thesis, the Omega-k algorithm used for processing stripmap synthetic aperture radar (SAR) data is explored in detail. While the original Omega-k algorithm does not achieve the same SNR as a matched filter, a modification is presented which enables the algorithm to nearly achieve that SNR. It is shown that the focused point spread function obtained when the Omega-k algorithm is used differs in important ways from the output of a modified version of the matched filter. Spread out sidelobes and a stretched mainlobe are observed when the data is processed by the Omega-k algorithm. These differences may increase the potential interference between some nearby scatterers; however, the amplitude of the resulting sidelobes is lower than that observed for the matched filter, and the potential interference between other nearby scatterers is reduced. The details of a discrete implementation of the algorithm are also presented. Two methods for mixing the frequency domain signal to baseband are compared, and one is shown to potentially reduce the required accuracy of the interpolation kernel. Finally, the errors associated with the key approximation used by the algorithm are explored through simulation, and it is shown that the approximation is sufficiently accurate for a particularly demanding configuration.

No description available.