The NP-complete k-SAT problem - decide wether a given formula is satisfiable - is of fundamental importance in theoretical computer science. In this dissertation we study random 4-SAT formulas with > 116 n^2 clauses. These formulas are almost surly unsatisfiable. Here we show the existence of a polynomial time algorithm that certifies the unsatisfiability. Therefore we study the discrepancy of hypergraphs and multigraphs. We also combine spectral techniques with approximation algorithms to achieve the new result. Our new algorithm is adaptable for Not-All-Equal-4-SAT and the 2-colouring of 4-uniform hypergraphs. We also extends the Hajos construction of non k-colourable graphs to non k-colourable uniform hypergraphs. / Das NP-vollständige Problem k-SAT ist von zentraler Bedeutung in der theoretischen Informatik. In der Dissertation werden zufällige 4-SAT-Formeln mit > n^2 vielen Klauseln studiert. Diese Formeln sind mit hoher Wahrscheinlichkeit unerfüllbar. Hier wird erstmalig die Existenz eines Algorithmus gezeigt, der diese Unerfüllbarkeit effizient verifiziert. Hierfür wird die geringe Diskrepanz von Hypergrpahen und Multigraphen betrachtet. Der Schlüssel zu diesem Algorithmus liegt in der Kombination von spektralen Techniken mit Approximationsalgorithmen der klassischen kombinatorischen Optimierung. Der vorgestellte Algorithmus kann auf den effizienten Nachweis der Unerfüllbarkeit von Not-All-Equal-4-SAT-Formeln und die Nicht-2-Färbbarkeit von 4-uniformen Hypergraphen erweitert werden. Es wird ebenfalls eine Erweiterung der Hajos-Konstruktion nicht k-färbbarer Graphen auf nicht k-färbbare uniforme Hypergraphen angegeben.

A Engenharia de Ventos Baseada em Desempenho (Performance-based Wind Engineering - PBWE) é uma filosofia de projeto que preconiza identificar e quantificar as incertezas envolvidas no projeto estrutural a fim de assegurar níveis previsíveis de desempenho às edificações, não mais gerenciando o risco através da clássica abordagem determinística. Contudo, devido à recente proposição da metodologia, ainda há poucos estudos relacionados à PBWE, cada qual apresentando diferentes limitações. Assim, o presente trabalho propõe uma adaptação da metodologia da Engenharia de Ventos Baseada em Desempenho à análise probabilística do comportamento de torres metálicas, avaliando diferentes modelos de cálculo para estimativa das forças do vento neste tipo de estrutura. Para tanto, investigou-se as incertezas envolvidas na caracterização do campo de ventos e da resistência estrutural e foram analisados quatro métodos distintos para a estimativa das forças de vento em torres metálicas: dois procedimentos de cálculo correspondentes à norma brasileira de ventos ABNT NBR 6123:1988 (ABNT, 1988), a metodologia de Davenport (1993) e a de Holmes (1994). Um estudo de caso envolvendo a estimativa da confiabilidade de uma torre de telecomunicação também foi conduzido. Constatou-se que ambos os procedimentos de cálculo admitidos conduzem a níveis de segurança de mesma ordem de grandeza e que a elaboração de projetos de torres considerando a direção de incidência do vento como sendo a mais desfavorável à estrutura é demasiadamente conservadora. Como contribuição, verifica-se que o projeto ótimo de torres pode ser alcançado com base no nível de segurança desejado para diferentes velocidades máxima de vento associadas a intervalos de recorrência específicos. / Performance-based Wind Engineering (PBWE) is a design philosophy that aims to identify and quantify the uncertainties involved in the structural design in order to ensure predictable performance levels to buildings, no longer managing risk through the classical deterministic approach. However, due to the recent proposal of the methodology, there are few studies related to PBWE, each presenting different limitations. Thus, this paper proposes an adaptation of the Performance-based Wind Engineering methodology to the probabilistic analysis of the behavior of steel towers, evaluating different calculation models for estimating wind forces on this type of structure. To this end, uncertainties involved in the characterization of the wind field and structural strength were investigated and four different methods for the estimation of wind forces on steel towers were analyzed: two procedures relative to the Brazilian winds standard ABNT NBR 6123:1988 (ABNT, 1988), and the methodologies of Davenport (1993) and Holmes (1994). A case study concerning the reliability estimation of a telecommunication tower was also conducted. It was found that both assumed calculation procedures lead to security levels of the same order of magnitude and that the design of towers considering that the wind always blows from the worst direction is too conservative. As a contribution, it is found that the optimum design of towers can be achieved based on the desired security level for different maximum wind speeds associated to specific recurrence intervals.

The concept of reinforcement was developed in late 20th century and since then till the recent past there are many works carried out on the effect of fibers in imparting strength and stiffness to the soil. Experimental investigations on fiber reinforced soils showed an increase in shear strength and reduction in post peak loss of strength due to the reinforcement. Analytical/mechanistic models are developed to predict the stress-strain response of fiber reinforced soil (under discrete framework, energy dissipation methods, force equilibrium methods etc). Numerical investigations are also carried out, and it was observed that the presence of random reinforcing material in soils make the stress concentration diffuse more and restrict the shear band formation. Soil properties vary from point to point at micro level and influence stress mobilization. Hence, there is a need to carry out probabilistic analysis to capture the effects of uncertainties and variability in soil and their influence on stress-strain evolution. In the present thesis an attempt has been made to propose a mechanistic model that predicts the stress-strain response of fiber reinforced soil and also considers the effect of anisotropy of fibers. A stochastic/probabilistic model is developed that predicts the stochastic stress-strain response of fiber reinforced soil. In addition, probabilistic analysis is carried out to observe the effect of number of fibers across the shear plane in imparting shear resistance to soil. The mechanistic model and stochastic models are validated with reference to the experimental results of consolidated undrained (CU) triaxial tests on coir fiber reinforced red soil for different fiber contents. The entire thesis is divided into six chapters. Chapter-wise description is given below. Chapter one presents a general introduction to the works carried out on fiber reinforced soils and also the investigations carried out on probabilistic methodologies that takes into account the soil variability. Thus, the chapter gives an outline of the models developed under mechanistic and probabilistic frameworks in the thesis. The objectives and organization of the thesis are also presented. Chapter two presents a detailed review of literature on the role of fibers in fiber reinforced soil. The details of experimental investigations carried out and models developed are explained briefly. Also, the literature pertaining to the role of variability in soil on its engineering behavior is presented. Based on the literature presented in this chapter, concluding remarks are made. Chapter three presents the details of a new mechanistic model developed based on modified Cam-clay model. This model considers the effect of fiber content and also the effect of anisotropy due to fibers. The predictions from the mechanistic model are compared with the experimental results. Under anisotropic condition, as angles of inclination of fiber vary from 0° to 90° with the bedding plane, it is observed that the strength increment in the reinforced soil is not as significant as that observed in isotropic case. Horizontal fibers turn out to be most effective since they are subjected to maximum extension thereby inducing tensile resistance which in turn contributes for strength increase in fiber reinforced soil. Chapter four presents a new approach to predict the stochastic stress-strain response of soil. Non-homogeneous Markov chain (multi-level homogeneous Markov chain) modeling is used in the prediction of stochastic response of soil. The statistical variations in the basic variables are taken into account by considering the response quantities (viz. stress at a given strain or settlement at a given load level) as random. A bi-level Homogeneous Markov chain predicts the stochastic stress-strain response efficiently. The predicted results are in good agreement with the experimental results. An illustration of this model is done to predict the stochastic load-settlement response of cohesionless soil. A simple tri-level homogeneous Markov chain model is proposed to predict settlements of soil at a given load for an isolated square footing subjected to axial compression. A parametric study on the effect of correlation coefficient on the prediction of settlements is performed. Chapter five presents the results of probabilistic analysis carried out to determine the effect of number of fibers across the shear plane in improving the shear strength of soil. It is observed that as the percentage of fibers in the specimen increases, the probability of failure of specimen under the same stress condition reduces and thus the reliability of the fiber reinforced soil system increases. In Chapter six, a summary of the important conclusions from the various studies reported in the dissertation are presented.

This thesis deals with economic evaluation case study of Ekofarm construction using applications Crystal Ball and Pertmaster Risk Project. The thesis represents the fundamental characteristics of the investment project and methods of its evaluation. There are introduced basic features of both applications on probabilistic risk analysis performed by simulation method Latin Hypercube Sampling. The case study is described in detail including breeding system and method of financing. This is linked to the calculation of economic fundamentals and creation of project cash flow. The result is probabilistic analysis which is output from tested software tools, and its evaluation.

[pt] Na prática geotécnica, a estabilidade de taludes é atualmente estudada apenas com análises determinísticas, obtendo-se o valor do Fator de Segurança (FS) da estrutura geotécnica. Estas análises são simplificadas, pois fornecem valores de FS sem considerar a variabilidade intrínseca dos solos e rochas. Desprezar as incertezas dos parâmetros geotécnicos pode levar a resultados pouco confiáveis sobre a segurança de taludes. Análises fundamentadas em conceitos estatísticos, chamadas probabilísticas, passam ser mais frequentes na geotecnia por permitirem considerar efeitos da variabilidade inerente aos materiais. Estas análises incorporam elementos estatísticos que possibilitam tratar FS como uma função e estudar suas propriedades. Como resultados finais, os métodos probabilísticos fornecem o índice de confiabilidade (beta) e a probabilidade de ruptura (Pr) da estrutura averiguada. Este trabalho aplica análises determinísticas e probabilísticas de um talude de 200m de altura da Mina do Cauê, Itabira, MG. A estabilidade do talude foi analisada por cinco métodos determinísticos usuais e três probabilísticos (FOSM, EP e MC). Os resultados indicam que a fixação da superfície crítica de ruptura fornece, em geral, valores de beta e Pr semelhantes aos obtidos quando a superfície pode variar livremente. Com a superfície crítica fixa observou-se, também, que os resultados de beta e Pr do talude variam significativamente com o método de equilíbrio limite adotado. Após comparação dos resultados, pode-se recomendar o uso de análises probabilísticas FOSM com base no método de Morgenstern-Price em análises semelhantes ao caso estudado. / [en] In current geotechnical practice, slope stability assessments are usually carried out only based on deterministic methods, obtaining a value of Safety Factor (FS). These analyses are simplified because the FS values do not consider the natural variability of soils and rocks. Disregarding the uncertainties inherent to geotechnical parameters may lead to unreliable results of slope safety. Probabilistic analyses, based on statistical concepts, have become more frequent in geotechnical practice, as they allow incorporating the materials intrinsic variability. These analyses are based on statistical elements that allow treating the FS as a function and studying its properties. The probabilistic methods indicate the reliability index (beta) and the probability of failure (Pr) of the verified geotechnical structure. This work presents deterministic and probabilistic analyses of a 200m high slope at the Cauê Mine, located in Itabira, Minas Gerais, Brazil, with basis on five usual deterministic methods and three probabilistic techniques (FOSM, Point Estimates and Monte Carlo). The results indicate that fixing the critical deterministic surface generally gives values of beta and Pr similar to those achieved when the surface is free to vary. It was also concluded that, with a fixed critical surface, beta and Pr results change significantly, when different Limit Equilibrium methods are adopted. It is recommended to use probabilistic FOSM analysis with Morgenstern and Price stability method in analyses similar to the one presented herein.

No description available.

The NP-complete k-SAT problem - decide wether a given formula is satisfiable - is of fundamental importance in theoretical computer science. In this dissertation we study random 4-SAT formulas with > 116 n^2 clauses. These formulas are almost surly unsatisfiable. Here we show the existence of a polynomial time algorithm that certifies the unsatisfiability. Therefore we study the discrepancy of hypergraphs and multigraphs. We also combine spectral techniques with approximation algorithms to achieve the new result. Our new algorithm is adaptable for Not-All-Equal-4-SAT and the 2-colouring of 4-uniform hypergraphs. We also extends the Hajos construction of non k-colourable graphs to non k-colourable uniform hypergraphs. / Das NP-vollständige Problem k-SAT ist von zentraler Bedeutung in der theoretischen Informatik. In der Dissertation werden zufällige 4-SAT-Formeln mit > n^2 vielen Klauseln studiert. Diese Formeln sind mit hoher Wahrscheinlichkeit unerfüllbar. Hier wird erstmalig die Existenz eines Algorithmus gezeigt, der diese Unerfüllbarkeit effizient verifiziert. Hierfür wird die geringe Diskrepanz von Hypergrpahen und Multigraphen betrachtet. Der Schlüssel zu diesem Algorithmus liegt in der Kombination von spektralen Techniken mit Approximationsalgorithmen der klassischen kombinatorischen Optimierung. Der vorgestellte Algorithmus kann auf den effizienten Nachweis der Unerfüllbarkeit von Not-All-Equal-4-SAT-Formeln und die Nicht-2-Färbbarkeit von 4-uniformen Hypergraphen erweitert werden. Es wird ebenfalls eine Erweiterung der Hajos-Konstruktion nicht k-färbbarer Graphen auf nicht k-färbbare uniforme Hypergraphen angegeben.