Dans cette thèse, nous exploitons les outils de la théorie des probabilités et de la géométrie stochastique pour analyser des algorithmes opérant sur les tessellations. Ce travail est divisé entre deux thèmes principaux, le premier traite de la navigation dans une tessellation de Delaunay et dans son dual, le diagramme de Voronoï avec des implications pour les algorithmes de localisation spatiales et de routage dans les réseaux en ligne. Nous proposons deux nouveaux algorithmes de navigation dans la triangulation de Delaunay, que nous appelons Pivot Walk et Cone Walk. Pour Cone Walk, nous fournissons une analyse en moyenne détaillée avec des bornes explicites sur les propriétés de la pire marche possible effectuée par l'algorithme sur une triangulation de Delaunay aléatoire d'une région convexe bornée. C'est un progrès significatif car dans l'algorithme Cone Walk, les probabilités d'utiliser un triangle ou un autre au cours de la marche présentent des dépendances complexes, dépendances inexistantes dans d'autres marches. La deuxième partie de ce travail concerne l'étude des propriétés extrémales de tessellations aléatoires. En particulier, nous dérivons les premiers et derniers statistiques d'ordre pour les boules inscrites dans les cellules d'un arrangement de droites Poissonnien; ce résultat a des implications par exemple pour le hachage respectant la localité. Comme corollaire, nous montrons que les cellules minimisant l'aire sont des triangles. / In this thesis, we leverage the tools of probability theory and stochastic geometry to investigate the behavior of algorithms on geometric tessellations of space. This work is split between two main themes, the first of which is focused on the problem of navigating the Delaunay tessellation and its geometric dual, the Voronoi diagram. We explore the applications of this problem to point location using walking algorithms and the study of online routing in networks. We then propose and investigate two new algorithms which navigate the Delaunay triangulation, which we call Pivot Walk and Cone Walk. For Cone Walk, we provide a detailed average-case analysis, giving explicit bounds on the properties of the worst possible path taken by the algorithm on a random Delaunay triangulation in a bounded convex region. This analysis is a significant departure from similar results that have been obtained, due to the difficulty of dealing with the complex dependence structure of localized navigation algorithms on the Delaunay triangulation. The second part of this work is concerned with the study of extremal properties of random tessellations. In particular, we derive the first and last order-statistics for the inballs of the cells in a Poisson line tessellation. This result has implications for algorithms involving line tessellations, such as locality sensitive hashing. As a corollary, we show that the cells minimizing the area are triangles.

Cette thèse s’articule autour de deux séries de travaux motivés par des expériences sur des fourmis. Bien qu’inspirés par labiologie, les modèles que nous développons utilisent une terminologie et une approche typique de l’informatique théorique.Le premier modèle s’inspire du transport collaboratif de nourriture au sein de l’espèce P. Longicornis. Certains aspectsfondamentaux du processus peuvent être décrits par un problème de recherche sur un graphe en présence d’un certain typed’indications bruitées à chaque noeud. Ces indications représentent de courtes traces de phéromones déposées devant l’objettransporté afin de faciliter la navigation. Dans cette thèse, nous donnons une analyse complète du problème lorsque le graphesous-jacent est un arbre, une hypothèse pertinente dans un cadre informatique. En particulier, notre modèle peut être vucomme une généralisation de la recherche binaire aux arbres, en présence de bruit. De manière surprenante, lescomportements des algorithmes optimaux dans ce cadre diffèrent suivant le type de garantie que l’on étudie : convergence enmoyenne ou avec grande probabilité.Le deuxième modèle présenté dans cette thèse a été conçu pour décrire la dissémination d’informations au sein de fourmis dudésert. Dans notre modèle, les échanges ont lieu uniformément au hasard, et sont sujets à du bruit. Nous prouvons une borneinférieure sur le nombre d’interactions requis en fonction de la taille du groupe. La borne, de même que les hypothèses dumodèle, semblent compatible avec les données expérimentales.Une conséquence théorique de ce résultat est une séparation dans ce cadre des variantes PUSH et PULL pour le problème du broadcast avec bruit. Nous étudions aussi une version du problème avec des garanties de convergence plus fortes. Dans cecas, le problème peut-être résolu efficacement, même si les échanges d’information au cours de chaque interaction sont très limités / This thesis is built around two series of works, each motivated by experiments on ants. We derive and analyse new models,that use computer science concepts and methodology, despite their biological roots and motivation.The first model studied in this thesis takes its inspiration in collaborative transport of food in the P. Longicornis species. Wefind that some key aspects of the process are well described by a graph search problem with noisy advice. The advicecorresponds to characteristic short scent marks laid in front of the load in order to facilitate its navigation. In this thesis, weprovide detailed analysis of the model on trees, which are relevant graph structures from a computer science standpoint. Inparticular our model may be viewed as a noisy extension of binary search to trees. Tight results in expectation and highprobability are derived with matching upper and lower bounds. Interestingly, there is a sharp phase transition phenomenon forthe expected runtime, but not when the algorithms are only required to succeed with high probability.The second model we work with was initially designed to capture information broadcast amongst desert ants. The model usesa stochastic meeting pattern and noise in the interactions, in a way that matches experimental data. Within this theoreticalmodel, we present in this document a strong lower bound on the number of interactions required before information can bespread reliably. Experimentally, we see that the time required for the recruitment process of even few ants increases sharplywith the group size, in accordance with our result. A theoretical consequence of the lower bound is a separation between theuniform noisy PUSH and PULL models of interaction. We also study a close variant of broadcast, without noise this time butunder more strict convergence requirements and show that in this case, the problem can be solved efficiently, even with verylimited exchange of information on each interaction.

Bakgrund: Bokföringslagen (1999:1078) och Årsredovisningslagen (1995:1554) är de två primära lagarna som finns inom området redovisning och revision. Dessa lagar är vad som kallas för ramlagar varför det förekommer hänvisningar i lagen till god redovisningssed. År 1976 myntades begreppet god redovisningssed (prop. 1975:104) sedan dess har god redovisningssed utvecklats med anledning av ett flertal myndigheter och organisationer. Uppsatsen fokuserar på tillgångsvärdering i relation till god redovisningssed. Vad som är intressant för uppsatsen är i de fall förenligheten med god redovisningssed blivit ifrågasatt av Skatteverket samt de fall det konstaterats att god redovisningssed inte förelegat och på vilket sett det påverkar revisorns ansvar. Syfte: Syftet är att belysa spänningen som uppstår mellan parterna i rättsprocesser vid skilda meningar om årsredovisningens förenlighet med god redovisningssed avseende tillgångsvärdering samt att belysa det ansvar revisorn bär när det görs gällande att god redovisningssed inte förelegat. Vidare syftar uppsatsen till att bidra med att klargöra vad som ansetts utgöra god redovisningssed vid tillgångsvärderingen och vilka ståndpunkter som varit mest centrala i perspektivet av prejudikatinstanser. Metod: Uppsatsen har genomförts med en kvalitativ metod. Vad som varit relevant är den text som återfinns i de rättsfall som utgör empirin däri det går att utläsa parternas tolkning, domstolens resonemang och avgörande varför dokument utgjort datakällan. Då rättsfall varit aktuella har även den traditionella rättskälleläran beaktats i syfte att kunna förstå de tolkningar som skett av domstolarna. Slutsats: Slutsatserna som presenteras i uppsatsen baseras på vad som framkommit av den använda analysmodellen i förhållande till respektive rättsfall. På så vis ges en skriftlig förklaring på vad som anses utgöra god redovisningssed vid tillgångsvärdering under vissa förutsättningar och omständigheter. Därtill beskrivs också vilket ansvar en revisor bär i fråga om felaktigheter vid utförandet av en revision. Bland samhälleliga och etiska aspekter lyfts ett resonemang kring redovisnings- och revisionsbranschen kopplat till förtroende. / Background:The Accounting Act (1999:1078) and the Annual Accounts Act (1995:1554) are the two primary laws that exist in accounting and auditing. These laws are what are called framework laws, which is why there are references in the law to generally accepted accounting principles (GAAP). In 1976, the concept GAAP was coined (prop. 1975: 104) since then, GAAP has been developed due to several authorities and organizations. The thesis focuses on asset valuation in relation to GAAP. What is interesting for the thesis is in cases where the compatibility with GAAP has been questioned by the Swedish Tax Agency and in cases where it has been established that GAAP did not exist and in what way it affects the auditor's responsibility. Purpose: The purpose is to shed light on the tension that arises between the parties in legal proceedings in different opinions about the annual report's compatibility with good accounting practice regarding asset valuation and to highlight the auditor's responsibility when it is claimed that GAAP did not exist. Furthermore, the thesis aims to help clarify what is considered as GAAP in asset valuation and which positions have been most central in the perspective of the judicial body. Method: The thesis has been carried out with a qualitative method. What has been relevant is the text that is found in the legal cases that constitute the empirical data in which it is possible to read the parties' interpretation, the court's reasoning and deciding therefore documents have been the data source. As lawsuits have been relevant, the traditional doctrine of legal sources has also been relevant to understand the interpretations made by the courts. Conclusion: The conclusions presented in the essay are based on what has emerged from the analysis model used in relation to the respective legal case. In this way, a written explanation is given of what is considered as GAAP in asset valuation under certain conditions and circumstances. In addition, it also describes the responsibility an auditor bears in relation to errors in performing an audit. Among societal and ethical aspects, a reasoning about the accounting and auditing industry linked to trust is highlighted.

No description available.

Os circuladores tradicionais são amplamente utilizados em telecomunicações e defesa militar para o simultâneo envio e recepção de sinais por um único meio. Esses circuitos passivos, fabricados a partir de materiais ferromagnéticos, possuem a desvantagem do aumento de dimensões, peso e custos de fabricação com a diminuição da frequência de operação definida no projeto destes dispositivos, inviabilizando sua aplicação em frequências abaixo de 500 MHz. O circulador ativo surgiu como uma alternativa aos tradicionais, tendo aplicações em frequências desde o nível DC até a ordem de dezenas de gigahertz. As suas maiores aplicações ocorrem quando são necessários dispositivos compactos, de baixo custo e de baixa potência. Os primeiros circuitos propostos possuíam uma grande limitação em termos de frequência de operação e de potência entregue à carga. Entretanto, com os avanços tecnológicos na eletrônica, tais problemas podem ser amenizados atualmente. Neste trabalho é apresentado o desenvolvimento de um circuito circulador ativo para a utilização em instrumentação eletrônica, em particular para a operação em frequências na ordem das utilizadas em equipamentos de ultrassom Doppler de ondas contínuas, na faixa de 2 MHz a 10 MHz. As possíveis vantagens da implementação de circuladores em sistemas de ultrassom estão relacionadas ao incremento da relação sinal-ruído, aumento da área de recepção do transdutor, simplificação da construção do transdutor, simplificação do circuito de demodulação/ processamento, e maior isolação entre os circuitos de transmissão e recepção de sinais. Na fase inicial, o circulador ativo proposto é modelado por equacionamento, utilizando-se tanto o modelo ideal dos amplificadores operacionais como o seu modelo de resposta em frequência. Simulações computacionais foram executadas para confirmar a validade do equacionamento. Um circuito montado em placa de prototipagem rápida foi apresentado, e testes de prova de conceito em baixas frequências foram realizados, mostrando uma grande semelhança entre o teórico, o simulado e o experimental. A segunda parte contou com o projeto do circuito circulador para a operação em maiores frequências. O circuito proposto é composto por três amplificadores operacionais de realimentação por corrente e vários componentes passivos. Uma análise de sensibilidade utilizando os métodos de Monte-Carlo e análise do pior caso foi aplicada, resultando em um perfil de comportamento frente às variações dos componentes do circuito e às variações da impedância de carga. Uma placa de circuito impressa foi projetada, utilizando-se de boas práticas de leiaute para a operação em altas frequências. Neste circuito montado, foram realizados os seguintes testes e medições: comportamento no domínio do tempo, faixa dinâmica, nível de isolação em relação à amplitude do sinal, largura de banda, levantamento dos parâmetros de espalhamento, e envio e recepção de sinais por transdutor de ultrassom Doppler de ondas contínuas. Os resultados dos testes de desempenho foram satisfatórios, apresentando uma banda de transmissão de sinais para frequências de 100 MHz, isolação entre portas não consecutivas de 39 dB na frequência de interesse para ultrassom Doppler e isolação maior que 20 dB para frequências de até 35 MHz. A faixa dinâmica excedeu a tensão de 5 Vpp, e o circuito teve bom comportamento no envio e na recepção simultânea de sinais pelo transdutor de ultrassom. / Traditional circulators are widely used in both telecommunications and military defense for sending and receiving signals simultaneously through a single medium. These passive circuits which are manufactured from ferromagnetic materials, have the disadvantages of having suffered an increase in dimensions, weight, and manufacturing costs along with the decrease in the operation frequency established in the designs of such devices, thus preventing their useful employment in frequencies below 500 MHz. The active circulator emerged as an alternative to the traditional ones, and has applications on frequencies ranging from a DC level to levels involving dozens of gigahertz. It is applicable when compact devices are made necessary, at a low cost, and for low frequencies. The first circuits to be introduced had a major limitation in terms of operating frequency and power delivered to the load. However, due to technological advances in electronics, problems such as the aforementioned can now be minimized. This research work presents the development of an active circulator circuit to be used in electronic instrumentation, particularly for operation at frequencies such as those used in continuous wave Doppler ultrasound equipment, ranging from 2 MHz to 10 MHz. The advantages made possible by implementing ultrasound systems with circulators are related to an increase in the signal-to-noise ratio, an increase in the transducers reception area, a simplified construction of the transducer, simplification of the demodulation/processing circuit, and a greater isolation between the transmission circuits and signal reception. In the initial phase, the proposed active circulator was modeled by means of an equating method, using both the ideal model of operational amplifiers and the model of frequency response. Computer simulations were carried out in order to confirm the validity of the equating method. A circuit mounted upon a breadboard was introduced and proof of concept assessments were performed at low frequencies, showing a great similarity among the theoretical, simulated and experimented data. The second phase is when the circulator circuits design was developed in order make its operation at higher frequencies possible. The proposed circuit is comprised of three currentfeedback operational amplifiers and several passive components. A sensitivity analysis was carried out using Monte-Carlo methods and worst-case analyses, resulting in a certain behavioral profile influenced by variations in circuit components and variations in load impedance. A printed circuit board was designed, employing good practice layout standards so that operation at high frequencies would be achieved. The following evaluations and measurements were performed on the circuit that was assembled: time domain behavior, dynamic range, isolation level relative to signal amplitude, bandwidth, survey of the scattering parameters, and transmission and reception of signals by a continuous wave Doppler ultrasound transducer. The results of the performance tests were satisfactory, presenting a 100 MHz signal transmission band, isolation between non-consecutive ports of 39 dB at the frequency of interest to the Doppler ultrasound, and an isolation greater than 20 dB for frequencies of up to 35 MHz. The dynamic range exceeded the 5Vpp and the circuit performed satisfactorily in the simultaneous transmission and reception of signals through the ultrasound\'s transducer.

As a result of development pressures and water resource struggles, once rural, spatially segregated coastal commercial fishing villages along the U.S. portion of the Gulf of Mexico are increasingly tourist frontiers for elites and the emergent businesses that cater to them. Over the course of the twentieth century, water events, from coastal land loss to hurricane destruction to natural disaster, have fast-tracked development projects that have allowed for the expansion of the tourism sector, and relaxed policies to encourage bold new economic development initiatives that often put poor coastal communities and their environment in jeopardy. This outcome is not universal across the northern Gulf Coast, but contingent on a number of local factors overlooked in the literature on coastal tourism and water policy development. This paper investigates the local nuances that have emerged as responses to global and regional development pressures by focusing on the ways in which local values and policy decisions have influenced the spread of coastal urbanization. An intensive analysis will examine the layered effects of changing land-use patterns and tourism growth pressures on three at-risk coastal communities in Louisiana, Mississippi and Florida, in the United States. This paper will test the hypothesis that coastal communities affected by a similar set of development pressures respond to these forces in different ways, depending on complex local and regional variabilities. The paper’s focus is centered on Northern Gulf Coast tourism growth patterns from post-World War II through 2018, and employs a mixed method, multiple-sited case-study design.

Aquesta tesi està dedicada al disseny i a l'anàlisi d'estructures de dades multidimensionals, és a dir, estructures de dades que serveixen per emmagatzemar registres $K$-dimensionals que solen representar-se com a punts en l'espai $[0,1]^K$. Aquestes estructures tenen aplicacions en diverses àrees de la informàtica com poden ser els sistemes d'informació geogràfica, la robòtica, el processament d'imatges, la world wide web, el data mining, entre d'altres. Les estructures de dades multidimensionals també es poden utilitzar com a indexos d'estructures de dades que emmagatzemen, possiblement en memòria externa, dades més complexes que els punts.Les estructures de dades multidimensionals han d'oferir la possibilitat de realitzar operacions d'inserció i esborrat de claus dinàmicament, a més de permetre realitzar cerques anomenades associatives. Exemples d'aquest tipus de cerques són les cerques per rangs ortogonals (quins punts cauen dintre d'un hiper-rectangle donat?) i les cerques del veí més proper (quin és el punt més proper a un punt donat?).Podem dividir les contribucions d'aquesta tesi en dues parts: La primera part està relacionada amb el disseny d'estructures de dades per a punts multidimensionals. Inclou el disseny d'arbres binaris $K$-dimensionals al·leatoritzats (Randomized $K$-d trees), el d'arbres quaternaris al·leatoritzats (Randomized quad trees) i el d'arbres multidimensionals amb punters de referència (Fingered multidimensional trees).La segona part analitza el comportament de les estructures de dades multidimensionals. En particular, s'analitza el cost mitjà de les cerques parcials en arbres $K$-dimensionals relaxats, i el de les cerques per rang en diverses estructures de dades multidimensionals. Respecte al disseny d'estructures de dades multidimensionals, proposem algorismes al·leatoritzats d'inserció i esborrat de registres per als arbres $K$-dimensionals i per als arbres quaternaris. Aquests algorismes produeixen arbres aleatoris, independentment de l'ordre d'inserció dels registres i desprès de qualsevol seqüència d'insercions i esborrats. De fet, el comportament esperat de les estructures produïdes mitjançant els algorismes al·leatoritzats és independent de la distribució de les dades d'entrada, tot i conservant la simplicitat i la flexibilitat dels arbres $K$-dimensionals i quaternaris estàndard. Introduïm també els arbres multidimensionals amb punters de referència. Això permet que les estructures multidimensionals puguin aprofitar l'anomenada localitat de referència en cerques associatives altament correlacionades.I respecte de l'anàlisi d'estructures de dades multidimensionals, primer analitzem el cost esperat de las cerques parcials en els arbres $K$-dimensionals relaxats. Seguidament utilitzem aquest resultat com a base per a l'anàlisi de les cerques per rangs ortogonals, juntament amb arguments combinatoris i geomètrics. D'aquesta manera obtenim un estimat asimptòtic precís del cost de les cerques per rangs ortogonals en els arbres $K$-dimensionals aleatoris. Finalment, mostrem que les tècniques utilitzades es poden estendre fàcilment a d'altres estructures de dades i per tant proporcionem una anàlisi exacta del cost mitjà de cerques per rang en estructures de dades com són els arbres $K$-dimensionals estàndard, els arbres quaternaris, els tries quaternaris i els tries $K$-dimensionals. / Esta tesis está dedicada al diseño y al análisis de estructuras de datos multidimensionales; es decir, estructuras de datos específicas para almacenar registros $K$-dimensionales que suelen representarse como puntos en el espacio $[0,1]^K$. Estas estructuras de datos tienen aplicaciones en diversas áreas de la informática como son: los sistemas de información geográfica, la robótica, el procesamiento de imágenes, la world wide web o data mining, entre otras.Las estructuras de datos multidimensionales suelen utilizarse también como índices de estructuras que almacenan, posiblemente en memoria externa, datos complejos.Las estructuras de datos multidimensionales deben ofrecer la posibilidad de realizar operaciones de inserción y borrado de llaves de manera dinámica, pero además deben permitir realizar búsquedas asociativas en los registros almacenados. Ejemplos de búsquedas asociativas son las búsquedas por rangos ortogonales (¿qué puntos de la estructura de datos están dentro de un hiper-rectángulo dado?) y las búsquedas del vecino más cercano (¿cuál es el punto de la estructura de datos más cercano a un punto dado?).Las contribuciones de esta tesis se dividen en dos partes:La primera parte está dedicada al diseño de estructuras de datos para puntos multidimensionales, que incluye el diseño de los árboles binarios $K$-dimensionales aleatorios (Randomized $K$-d trees), el de los árboles cuaternarios aleatorios (Randomized quad trees), y el de los árboles multidimensionales con punteros de referencia (Fingered multidimensional trees).La segunda parte contiene contribuciones al análisis del comportamiento de las estructuras de datos para puntos multidimensionales. En particular, damos el análisis del costo promedio de las búsquedas parciales en los árboles $K$-dimensionales relajados y el de las búsquedas por rango en varias estructuras de datos multidimensionales.Con respecto al diseño de estructuras de datos multidimensionales, proponemos algoritmos aleatorios de inserción y borrado de registros para los árboles $K$-dimensionales y los árboles cuaternarios que producen árboles aleatorios independientemente del orden de inserción de los registros y después de cualquier secuencia de inserciones y borrados intercalados. De hecho, con la aleatorización garantizamos un buen rendimiento esperado de las estructuras de datos resultantes, que es independiente de la distribución de los datos de entrada, conservando la flexibilidad y la simplicidad de los árboles $K$-dimensionales y de los árboles cuaternarios estándar. También proponemos los árboles multidimensionales con punteros de referencia, una técnica que permite que las estructuras de datos multidimensionales exploten la localidad de referencia en búsquedas asociativas que se presentan altamente correlacionadas.Con respecto al análisis de estructuras de datos multidimensionales, comenzamos dando un análisis preciso del costo esperado de las búsquedas parciales en los árboles $K$-dimensionales relajados. A continuación, utilizamos este resultado como base para el análisis de las búsquedas por rangos ortogonales, combinándolo con argumentos combinatorios y geométricos. Como resultado obtenemos un estimado asintótico preciso del costo de las búsquedas por rango en los árboles $K$-dimensionales relajados. Finalmente, mostramos que las técnicas utilizadas pueden extenderse fácilmente a otras estructuras de datos y por tanto proporcionamos un análisis preciso del costo promedio de búsquedas por rango en estructuras de datos como los árboles $K$-dimensionales estándar, los árboles cuaternarios, los tries cuaternarios y los tries $K$-dimensionales. / This thesis is about the design and analysis of point multidimensional data structures: data structures that store $K$-dimensional keys which we may abstract as points in $[0,1]^K$. These data structures are present in many applications of geographical information systems, image processing or robotics, among others. They are also frequently used as indexes of more complex data structures, possibly stored in external memory.Point multidimensional data structures must have capabilities such as insertion, deletion and (exact) search of items, but in addition they must support the so called {em associative queries}. Examples of these queries are orthogonal range queries (which are the items that fall inside a given hyper-rectangle?) and nearest neighbour queries (which is the closest item to some given point?).The contributions of this thesis are two-fold:Contributions to the design of point multidimensional data structures: the design of randomized $K$-d trees, the design of randomized quad trees and the design of fingered multidimensional search trees;Contributions to the analysis of the performance of point multidimensional data structures: the average-case analysis of partial match queries in relaxed $K$-d trees and the average-case analysis of orthogonal range queries in various multidimensional data structures.Concerning the design of randomized point multidimensional data structures, we propose randomized insertion and deletion algorithms for $K$-d trees and quad trees that produce random $K$-d trees and quad trees independently of the order in which items are inserted into them and after any sequence of interleaved insertions and deletions. The use of randomization provides expected performance guarantees, irrespective of any assumption on the data distribution, while retaining the simplicity and flexibility of standard $K$-d trees and quad trees.Also related to the design of point multidimensional data structures is the proposal of fingered multidimensional search trees, a new technique that enhances point multidimensional data structures to exploit locality of reference in associative queries.With regards to performance analysis, we start by giving a precise analysis of the cost of partial matches in randomized $K$-d trees. We use these results as a building block in our analysis of orthogonal range queries, together with combinatorial and geometric arguments and we provide a tight asymptotic estimate of the cost of orthogonal range search in randomized $K$-d trees. We finally show that the techniques used apply easily to other data structures, so we can provide an analysis of the average cost of orthogonal range search in other data structures such as standard $K$-d trees, quad trees, quad tries, and $K$-d tries.

In theoretical computer science, various notions of efficiency are used for algorithms. The most commonly used notion is worst-case efficiency, which is defined by requiring polynomial worst-case running time. Another commonly used notion is average-case efficiency for random inputs, which is roughly defined as having polynomial expected running time with respect to the random inputs. Depending on the actual notion of efficiency one uses, the approximability of a combinatorial optimization problem can be very different. In this dissertation, the approximability of three classical combinatorial optimization problems, namely Independent Set, Coloring, and Shortest Common Superstring, is investigated for different notions of efficiency. For the three problems, approximation algorithms are given, which guarantee approximation ratios that are unachievable by worst-case efficient algorithms under reasonable complexity-theoretic assumptions. The algorithms achieve polynomial expected running time for different models of random inputs. On the one hand, classical average-case analyses are performed, using totally random input models as the source of random inputs. On the other hand, probabilistic analyses are performed, using semi-random input models inspired by the so called smoothed analysis of algorithms. Finally, the expected performance of well known greedy algorithms for random inputs from the considered models is investigated. Also, the expected behavior of some properties of the random inputs themselves is considered.

Os circuladores tradicionais são amplamente utilizados em telecomunicações e defesa militar para o simultâneo envio e recepção de sinais por um único meio. Esses circuitos passivos, fabricados a partir de materiais ferromagnéticos, possuem a desvantagem do aumento de dimensões, peso e custos de fabricação com a diminuição da frequência de operação definida no projeto destes dispositivos, inviabilizando sua aplicação em frequências abaixo de 500 MHz. O circulador ativo surgiu como uma alternativa aos tradicionais, tendo aplicações em frequências desde o nível DC até a ordem de dezenas de gigahertz. As suas maiores aplicações ocorrem quando são necessários dispositivos compactos, de baixo custo e de baixa potência. Os primeiros circuitos propostos possuíam uma grande limitação em termos de frequência de operação e de potência entregue à carga. Entretanto, com os avanços tecnológicos na eletrônica, tais problemas podem ser amenizados atualmente. Neste trabalho é apresentado o desenvolvimento de um circuito circulador ativo para a utilização em instrumentação eletrônica, em particular para a operação em frequências na ordem das utilizadas em equipamentos de ultrassom Doppler de ondas contínuas, na faixa de 2 MHz a 10 MHz. As possíveis vantagens da implementação de circuladores em sistemas de ultrassom estão relacionadas ao incremento da relação sinal-ruído, aumento da área de recepção do transdutor, simplificação da construção do transdutor, simplificação do circuito de demodulação/ processamento, e maior isolação entre os circuitos de transmissão e recepção de sinais. Na fase inicial, o circulador ativo proposto é modelado por equacionamento, utilizando-se tanto o modelo ideal dos amplificadores operacionais como o seu modelo de resposta em frequência. Simulações computacionais foram executadas para confirmar a validade do equacionamento. Um circuito montado em placa de prototipagem rápida foi apresentado, e testes de prova de conceito em baixas frequências foram realizados, mostrando uma grande semelhança entre o teórico, o simulado e o experimental. A segunda parte contou com o projeto do circuito circulador para a operação em maiores frequências. O circuito proposto é composto por três amplificadores operacionais de realimentação por corrente e vários componentes passivos. Uma análise de sensibilidade utilizando os métodos de Monte-Carlo e análise do pior caso foi aplicada, resultando em um perfil de comportamento frente às variações dos componentes do circuito e às variações da impedância de carga. Uma placa de circuito impressa foi projetada, utilizando-se de boas práticas de leiaute para a operação em altas frequências. Neste circuito montado, foram realizados os seguintes testes e medições: comportamento no domínio do tempo, faixa dinâmica, nível de isolação em relação à amplitude do sinal, largura de banda, levantamento dos parâmetros de espalhamento, e envio e recepção de sinais por transdutor de ultrassom Doppler de ondas contínuas. Os resultados dos testes de desempenho foram satisfatórios, apresentando uma banda de transmissão de sinais para frequências de 100 MHz, isolação entre portas não consecutivas de 39 dB na frequência de interesse para ultrassom Doppler e isolação maior que 20 dB para frequências de até 35 MHz. A faixa dinâmica excedeu a tensão de 5 Vpp, e o circuito teve bom comportamento no envio e na recepção simultânea de sinais pelo transdutor de ultrassom. / Traditional circulators are widely used in both telecommunications and military defense for sending and receiving signals simultaneously through a single medium. These passive circuits which are manufactured from ferromagnetic materials, have the disadvantages of having suffered an increase in dimensions, weight, and manufacturing costs along with the decrease in the operation frequency established in the designs of such devices, thus preventing their useful employment in frequencies below 500 MHz. The active circulator emerged as an alternative to the traditional ones, and has applications on frequencies ranging from a DC level to levels involving dozens of gigahertz. It is applicable when compact devices are made necessary, at a low cost, and for low frequencies. The first circuits to be introduced had a major limitation in terms of operating frequency and power delivered to the load. However, due to technological advances in electronics, problems such as the aforementioned can now be minimized. This research work presents the development of an active circulator circuit to be used in electronic instrumentation, particularly for operation at frequencies such as those used in continuous wave Doppler ultrasound equipment, ranging from 2 MHz to 10 MHz. The advantages made possible by implementing ultrasound systems with circulators are related to an increase in the signal-to-noise ratio, an increase in the transducers reception area, a simplified construction of the transducer, simplification of the demodulation/processing circuit, and a greater isolation between the transmission circuits and signal reception. In the initial phase, the proposed active circulator was modeled by means of an equating method, using both the ideal model of operational amplifiers and the model of frequency response. Computer simulations were carried out in order to confirm the validity of the equating method. A circuit mounted upon a breadboard was introduced and proof of concept assessments were performed at low frequencies, showing a great similarity among the theoretical, simulated and experimented data. The second phase is when the circulator circuits design was developed in order make its operation at higher frequencies possible. The proposed circuit is comprised of three currentfeedback operational amplifiers and several passive components. A sensitivity analysis was carried out using Monte-Carlo methods and worst-case analyses, resulting in a certain behavioral profile influenced by variations in circuit components and variations in load impedance. A printed circuit board was designed, employing good practice layout standards so that operation at high frequencies would be achieved. The following evaluations and measurements were performed on the circuit that was assembled: time domain behavior, dynamic range, isolation level relative to signal amplitude, bandwidth, survey of the scattering parameters, and transmission and reception of signals by a continuous wave Doppler ultrasound transducer. The results of the performance tests were satisfactory, presenting a 100 MHz signal transmission band, isolation between non-consecutive ports of 39 dB at the frequency of interest to the Doppler ultrasound, and an isolation greater than 20 dB for frequencies of up to 35 MHz. The dynamic range exceeded the 5Vpp and the circuit performed satisfactorily in the simultaneous transmission and reception of signals through the ultrasound\'s transducer.

In theoretical computer science, various notions of efficiency are used for algorithms. The most commonly used notion is worst-case efficiency, which is defined by requiring polynomial worst-case running time. Another commonly used notion is average-case efficiency for random inputs, which is roughly defined as having polynomial expected running time with respect to the random inputs. Depending on the actual notion of efficiency one uses, the approximability of a combinatorial optimization problem can be very different. In this dissertation, the approximability of three classical combinatorial optimization problems, namely Independent Set, Coloring, and Shortest Common Superstring, is investigated for different notions of efficiency. For the three problems, approximation algorithms are given, which guarantee approximation ratios that are unachievable by worst-case efficient algorithms under reasonable complexity-theoretic assumptions. The algorithms achieve polynomial expected running time for different models of random inputs. On the one hand, classical average-case analyses are performed, using totally random input models as the source of random inputs. On the other hand, probabilistic analyses are performed, using semi-random input models inspired by the so called smoothed analysis of algorithms. Finally, the expected performance of well known greedy algorithms for random inputs from the considered models is investigated. Also, the expected behavior of some properties of the random inputs themselves is considered.