Completions of epsilon-dense partial Latin squares

A classical question in combinatorics is the following: given a partial Latin square $P$, when can we complete $P$ to a Latin square $L$? In this paper, we investigate the class of textbf{$epsilon$-dense partial Latin squares}: partial Latin squares in which each symbol, row, and column contains no more than $epsilon n$-many nonblank cells. Based on a conjecture of Nash-Williams, Daykin and H"aggkvist conjectured that all $frac{1}{4}$-dense partial Latin squares are completable. In this paper, we will discuss the proof methods and results used in previous attempts to resolve this conjecture, introduce a novel technique derived from a paper by Jacobson and Matthews on generating random Latin squares, and use this novel technique to study $ epsilon$-dense partial Latin squares that contain no more than $delta n^2$ filled cells in total.

In Chapter 2, we construct completions for all $ epsilon$-dense partial Latin squares containing no more than $delta n^2$ filled cells in total, given that $epsilon < frac{1}{12}, delta < frac{ left(1-12epsilonright)^{2}}{10409}$. In particular, we show that all $9.8 cdot 10^{-5}$-dense partial Latin squares are completable. In Chapter 4, we augment these results by roughly a factor of two using some probabilistic techniques. These results improve prior work by Gustavsson, which required $epsilon = delta leq 10^{-7}$, as well as Chetwynd and H"aggkvist, which required $epsilon = delta = 10^{-5}$, $n$ even and greater than $10^7$.

If we omit the probabilistic techniques noted above, we further show that such completions can always be found in polynomial time. This contrasts a result of Colbourn, which states that completing arbitrary partial Latin squares is an NP-complete task. In Chapter 3, we strengthen Colbourn's result to the claim that completing an arbitrary $left(frac{1}{2} + epsilonright)$-dense partial Latin square is NP-complete, for any $epsilon > 0$.

Colbourn's result hinges heavily on a connection between triangulations of tripartite graphs and Latin squares. Motivated by this, we use our results on Latin squares to prove that any tripartite graph $G = (V_1, V_2, V_3)$ such that begin{itemize} item $|V_1| = |V_2| = |V_3| = n$, item For every vertex $v in V_i$, $deg_+(v) = deg_-(v) geq (1- epsilon)n,$ and item $|E(G)| > (1 - delta)cdot 3n^2$ end{itemize} admits a triangulation, if $epsilon < frac{1}{132}$, $delta < frac{(1 -132epsilon)^2 }{83272}$. In particular, this holds when $epsilon = delta=1.197 cdot 10^{-5}$.

This strengthens results of Gustavsson, which requires $epsilon = delta = 10^{-7}$.

In an unrelated vein, Chapter 6 explores the class of textbf{quasirandom graphs}, a notion first introduced by Chung, Graham and Wilson cite{chung1989quasi} in 1989. Roughly speaking, a sequence of graphs is called "quasirandom"' if it has a number of properties possessed by the random graph, all of which turn out to be equivalent. In this chapter, we study possible extensions of these results to random $k$-edge colorings, and create an analogue of Chung, Graham and Wilson's result for such colorings.

Convex Relaxation for Low-Dimensional Representation: Phase Transitions and Limitations

There is a growing interest in taking advantage of possible patterns and structures in data so as to extract the desired information and overcome the curse of dimensionality. In a wide range of applications, including computer vision, machine learning, medical imaging, and social networks, the signal that gives rise to the observations can be modeled to be approximately sparse and exploiting this fact can be very beneficial. This has led to an immense interest in the problem of efficiently reconstructing a sparse signal from limited linear observations. More recently, low-rank approximation techniques have become prominent tools to approach problems arising in machine learning, system identification and quantum tomography.

In sparse and low-rank estimation problems, the challenge is the inherent intractability of the objective function, and one needs efficient methods to capture the low-dimensionality of these models. Convex optimization is often a promising tool to attack such problems. An intractable problem with a combinatorial objective can often be "relaxed" to obtain a tractable but almost as powerful convex optimization problem. This dissertation studies convex optimization techniques that can take advantage of low-dimensional representations of the underlying high-dimensional data. We provide provable guarantees that ensure that the proposed algorithms will succeed under reasonable conditions, and answer questions of the following flavor:

More specifically, i) Focusing on linear inverse problems, we generalize the classical error bounds known for the least-squares technique to the lasso formulation, which incorporates the signal model. ii) We show that intuitive convex approaches do not perform as well as expected when it comes to signals that have multiple low-dimensional structures simultaneously. iii) Finally, we propose convex relaxations for the graph clustering problem and give sharp performance guarantees for a family of graphs arising from the so-called stochastic block model. We pay particular attention to the following aspects. For i) and ii), we aim to provide a general geometric framework, in which the results on sparse and low-rank estimation can be obtained as special cases. For i) and iii), we investigate the precise performance characterization, which yields the right constants in our bounds and the true dependence between the problem parameters.

Herramienta software para el análisis de rendimiento de redes 4G

[ES]El objetivo de este proyecto ha sido desarrollar una herramienta software que permita medir el rendimiento de redes con tecnología móvil 4G, también conocida como LTE. Para ello se ha creado un sistema software que está compuesto por una aplicación móvil y un servidor de aplicaciones. El sistema en conjunto realiza la función de recoger indicadores de calidad de la red móvil de diversa índole, que posteriormente son procesados utilizando herramientas software matemáticas, para así obtener gráficas y mapas que permiten analizar la situación y el rendimiento de una red 4G concreta. El desarrollo del software ha llegado a nivel de prototipo y se han realizado pruebas reales con él obteniendo resultados positivos de funcionamiento.

Atlas digital: uma contribuição para o sistema de informação do município de São João de Meriti-RJ

Um Atlas Digital é um atlas que foi concebido através de técnicas computacionais e que, consequentemente, pode ser acessado através de um computador. Estruturado em um ambiente gráfico, além dos mapas, pode-se contar também com textos, fotografias, dados estatísticos, gráficos e tabelas. Por estar em meio digital existe a possibilidade de utilização de uma expressiva gama de temas, formatos e escalas. Nesta dissertação apresenta-se um protótipo de Atlas Digital como uma colaboração ao Sistema de Informação Municipal SIM, para o município de São João de Meriti, RJ. O referido SIM, que tem como meta os serviços municipais, visa atender ao próprio município, ao cidadão e a outros interessados na cidade, sendo as suas informações fundamentais para a melhoria da gestão das prefeituras. A pesquisa foi direcionada para o tema da habitabilidade, que consiste num conjunto de condições voltadas para a construção de habitat saudável, abrangendo temas físicos, psicológicos, sociais, culturais e ambientais. Dentro do tema habitabilidade, foram trabalhados os subtemas relativos a infraestrutura de abastecimento de água, esgoto, coleta de lixo, saúde e educação, esses subtemas foram confrontados entre si para uma comparação entre os bairros do município. O SIM e a habitabilidade são contemplados no plano diretor da cidade e representa uma grande parte da sustentação teórica da dissertação. A modelagem e implementação do protótipo do Atlas Digital foram feitas com auxílio de softwares gratuitos, sendo possível acessar mapas temáticos e outras informações sobre São João de Meriti

Estimativa do erro de discretização analítico na solução de equações diferenciais utilizando o Método de Volumes Finitos

As análises de erros são conduzidas antes de qualquer projeto a ser desenvolvido. A necessidade do conhecimento do comportamento do erro numérico em malhas estruturadas e não-estruturadas surge com o aumento do uso destas malhas nos métodos de discretização. Desta forma, o objetivo deste trabalho foi criar uma metodologia para analisar os erros de discretização gerados através do truncamento na Série de Taylor, aplicados às equações de Poisson e de Advecção-Difusão estacionárias uni e bidimensionais, utilizando-se o Método de Volumes Finitos em malhas do tipo Voronoi. A escolha dessas equações se dá devido a sua grande utilização em testes de novos modelos matemáticos e função de interpolação. Foram usados os esquemas Central Difference Scheme (CDS) e Upwind Difference Scheme(UDS) nos termos advectivos. Verificou-se a influência do tipo de condição de contorno e a posição do ponto gerador do volume na solução numérica. Os resultados analíticos foram confrontados com resultados experimentais para dois tipos de malhas de Voronoi, uma malha cartesiana e outra triangular comprovando a influência da forma do volume finito na solução numérica obtida. Foi percebido no estudo que a discretização usando o esquema CDS tem erros menores do que a discretização usando o esquema UDS conforme literatura. Também se percebe a diferença nos erros em volumes vizinhos nas malhas triangulares o que faz com que não se tenha uma uniformidade nos gráficos dos erros estudados. Percebeu-se que as malhas cartesianas com nó no centróide do volume tem menor erro de discretização do que malhas triangulares. Mas o uso deste tipo de malha depende da geometria do problema estudado

Análise comparativa dos modelos de cálculo dos retornos anormais utilizando o evento recompra de ações na Bovespa

Este trabalho tem por objetivo verificar se há diferença quanto ao nível de significância estatística no cálculo do retorno anormal realizado através de quatro modelos estatísticos utilizados em estudos de eventos, tendo como objeto de estudo empresas no mercado de ações no Brasil durante o período de março de 2003 até julho de 2010 na Bovespa. Considerando a importância do cálculo do retorno anormal nos estudos de eventos, bem como possíveis variações de resultados decorrentes da escolha do modelo de cálculo, este estudo utiliza um tema bastante conhecido, qual seja, o anúncio de recompra de ações feito pela própria companhia emissora dos títulos. A metodologia utilizada nesta pesquisa foi quantitativa, utilizando o estudo de corte transversal. Os resultados apontam que há diferença entre os níveis de significância encontrados. Ao analisar o gráfico dos modelos calculados no período da janela do evento, verificou-se que as empresas que recompraram ações a fizeram quando os papéis estavam com retorno anormal acumulado negativo e, após a recompra, os papéis tiveram retornos anormais acumulados positivos. Recalculou-se os dois modelos que utilizam o Ibovespa em sua fórmula de cálculo, através de um Ibovespa sem ponderação e conclui-se que os resultados apontam na direção de se evitar o uso de índices ponderados de mercado, preferindo a utilização de carteiras compostas apenas com uma ação para cada empresa componente da carteira de controle. Após este recálculo, verificou-se que o modelo que era menos próximo dos demais graficamente era o modelo de retorno ajustado ao mercado ponderado. Por fim, as evidências empíricas indicam que o mercado de capitais brasileiro ajusta tempestivamente os papéis das empresas que realizaram recompra de ações, em linha com o que prescreve a hipótese do mercado eficiente na sua forma semiforte.

Treewidth: theory and applications to computer science

This report is an introduction to the concept of treewidth, a property of graphs that has important implications in algorithms. Some basic concepts of graph theory are presented in the first chapter for those readers that are not familiar with the notation. In Chapter 2, the definition of treewidth and some different ways of characterizing it are explained. The last two chapters focus on the algorithmic implications of treewidth, which are very relevant in Computer Science. An algorithm to compute the treewidth of a graph is presented and its result can be later applied to many other problems in graph theory, like those introduced in the last chapter.

Estudo da incapacidade definitiva para o serviço na Marinha do Brasil: contribuição da enfermagem

Trata-se de um estudo que teve como objeto as incapacidades definitivas para o serviço na Marinha do Brasil com o seguinte problema de pesquisa: quais as causas das incapacidades definitivas para o serviço na Marinha do Brasil, no 1 Distrito, nos períodos de cinco e dez anos de vigência do Programa de Atenção às Doenças Profissionais (PADP)? Considerando o interesse na temática e a especificidade do objeto de estudo selecionou-se como objetivo geral: discutir as incapacidades definitivas para o serviço na Marinha do Brasil, no período de cinco e dez anos após a implantação do PADP no 1 Distrito. E, como objetivos específicos: analisar o perfil dos militares considerados incapacitados para o serviço, na área do 1 Distrito da Marinha do Brasil, no ano de 2005 e no ano de 2010; identificar as incapacidades definitivas para o serviço na Marinha do Brasil no ano de 2005 e 2010 ocorridas no 1 Distrito e; propor adequações ao PADP baseadas no resultado deste estudo. Baseou-se no modelo de pesquisa não experimental, retrospectivo e documental. Foi utilizada como técnica de trabalho a abordagem quantitativa e descritiva, através de um estudo documental dos registros de incapacidades definitivas para o serviço ocorridas no 1 Distrito da Marinha do Brasil no ano de 2005 e no ano de 2010, respectivamente 05 e 10 anos após a implantação do PADP. O local do estudo foi o Centro de Perícias Médicas da Marinha (CPMM), estrutura organizacional central do Subsistema Médico Pericial, situado no Complexo do Hospital Central da Marinha. Os dados foram coletados durante os meses de julho e agosto do ano de 2011, no Sistema Informatizado Naval de Inspeções de Saúde (SINAIS), não sendo realizado qualquer contato com os militares considerados incapacitados para o serviço, que fizeram parte deste estudo. Utilizou-se um formulário fechado para o registro dos dados que posteriormente foram digitalizados e computados por meio de análise percentual, utilizando-se o programa Microsoft Excel 2007. Posteriormente, foram demonstrados em tabelas e gráficos, sendo discutidos à luz do referencial teórico da Saúde do Trabalhador e sustentado por bases conceituais. Para melhor apresentação dos dados, estes foram organizados a partir dos seguintes temas: perfil dos militares considerados incapacitados para o serviço na Marinha do Brasil, as principais incapacidades e suas correlações com o trabalho e, propostas ao Programa de Atenção às Doenças Profissionais da Marinha. O estudo viabilizou sugestões de melhorias na aplicação do PADP, visando à redução do número de casos de incapacidades para o serviço na Marinha do Brasil.

Fatores associados a óbito e hospitalizações em uma clínica de insuficiência cardíaca

Trata-se de um estudo descritivo, retrospectivo, com abordagem quantitativa cujo objetivo geral foi descrever e analisar o perfil epidemiológico dos pacientes com Insuficiência Cardíaca atendidos pela Clinica de IC de um Hospital Universitário. Os objetivos específicos orientam-se para:(a)Caracterizar os casos de Insuficiência Cardíaca segundo variáveis demográficas, variáveis clínicas, de diagnóstico e co morbidades;(b)Comparar as características clínicas e demográficas dos pacientes conforme grupos etiológicos identificados e fração de ejeção;(c)Determinar a taxa de mortalidade e hospitalização dos pacientes acompanhados pela clínica. Os dados analisados neste estudo são oriundos de um banco de dados onde são alocadas informações dos pacientes em atendimento ambulatorial da referida clinica.Para a análise dos dados foi utilizada a estatística descritiva, freqüências e porcentagens assim como tabelas e gráficos para a demonstração dos dados levantados.Os mesmos foram analisados através do software SPSS v.18.0, no qual se utilizou a estatística multivariada e curvas de sobrevida de Kaplan-Meyer.Os resultados apontam para uma predominância masculina de 60,1%, com idade de 63,5 anos. Na caracterização quanto à classe funcional observa-se que a predominante é a classe funcional I e II com 73,6% do total. Os pacientes assistidos apresentam uma média de 42% da fração de ejeção do ventrículo esquerdo e 61,7% possuem etiologia não isquêmica. Em nosso estudo, descrevemos 71,8% de portadores de disfunção sistólica. Os pacientes com etiologia isquêmica tinham predomínio do sexo masculino(70,7%), e a etiologia não isquêmica com uma prevalência maior do sexo feminino(45,5%vs 29,3%;p<0,001). Além disso, os pacientes isquêmicos eram mais idosos (p<0,001), com historia familiar de DAC(p<0,041), presença de diabetes (p<0,001). A disfunção sistólica(FE<50%) era predominante no grupo de pacientes isquêmicos(77%vs 69%; p=0,048).As classes funcionais mais avançadas(III e IV) foram menos predominantes nos indivíduos isquêmicos(32,5%) em relação aos não isquêmicos(41,3%;p=0,041).O paciente de etiologia isquêmica recebeu tratamento farmacológico semelhante ao não isquêmico com exceção do uso de AAS(p<0,001).Esses indivíduos cursaram com maior numero de internações por outras causas exceto IC(p<0,001) e maior numero de óbitos(p=0,007).Em relação à fração de ejeção, observou-se que indivíduos com FE>50% tinham predomínio do sexo feminino(p=0,006),mais idosos(p<0,001),de etiologia não isquêmica(p=0,048) e classes funcionais I e II(p=0,025).Indivíduos com FE<50% eram mais graves, apresentando maior número de internações por IC(37,8%vs20%;p<0,001), e internações por outras causas(27,2%vs17,5%;p=0,018) e maior número de óbitos (18%vs8,4%;p=0,005) do que os com fração de ejeção preservada. O resultado desse estudo teve como finalidade o conhecimento do perfil de uma população própria, com o objetivo de aprimorar a assistência prestada a ela. Os enfermeiros de Clínicas de IC, juntos com os profissionais da equipe multidisciplinar, desempenham papel fundamental no acompanhamento, orientação e educação desses pacientes.

Contributions on agreement in dynamic distributed systems

139 p.

Análisis de redes de los proyectos de innovación europeos “Leonardo da Vinci”: un ensayo empírico preliminar

[Castellano] En este trabajo se realiza un ensayo empírico preliminar de los proyectos de innovación europeos “Leonardo da Vinci”. La metodología que se utiliza a lo largo del trabajo es el análisis de redes. Se observan grafos e indicadores de redes y se comparan la situación de los agentes que forman las redes. Además no solamente se analiza la situación de los agentes, sino la similitud y causalidad estructural existente entre las redes que conforman dichos proyectos. Este ensayo empírico preliminar da lugar a una futura modelización o a la aplicación de la metodología en otras materias.

Reação do mercado às republicações de demonstrações contábeis no Brasil no período de 2000 a 2011

Este trabalho tem por objetivo verificar se há impacto das republicações das demonstrações contábeis das empresas com ações negociadas na Bovespa no período de 2000 a 2010, no preço de suas ações. O estudo parte do pressuposto de que o mercado Brasileiro de ações é semiforte. A metodologia utilizada nesta pesquisa foi em parte qualitativa ao descrever a amostra e suas características assim como quantitativa na forma dos testes de diferenças de média. Os resultados dos testes mostram que ao se analisar toda a amostra como um único grupo, os retornos anormais encontrados não mostraram diferença significativa em comparação com os valores esperados calculados, mas quando analisados em segmentações distintas pelo tipo de motivação à republicação, foram encontrados evidências de que há diferença significativa entre as amostras das republicações das demonstrações contábeis voluntárias e obrigatórias. Assim como também foram encontrados evidências de que pode haver diferença significativa entre as amostras segmentadas pela natureza do erro apresentado com justificativa para a republicação da demonstração contábil, tanto nos casos de mensuração, quanto classificação e reconhecimento. A mesma evidência é apresentada nos gráficos das médias dos retornos anormais calculados para este estudo.

Dix ans de mesures de biomasses de zooplancton a la station cotière d'Abidjan: 1969-1979

Graphs of variations of zooplankton biomasses expressed as ash-free dry weight (i.e. organic matter) are presented for the 1969-1979 period. The graph of the average year shows: an enrichment season from mid-July till mid-November in which the biomass is 2.3 times higher than the rest of the year and characterized by a slight decrease of the biomass in late August or early September. The warm season is divided into a period of moderate biomass from November till February, a period of moderate biomass from November till February and a period of steady decline of the biomass till the start of the upwelling at the end of June.

Distribution et abondance des larves de thonidés dans l'Atlantique tropico-oriental. Étude des données de 1963 à 1974

From several sources of data, the authors study seasonal variations of larval abundance for five species of tuna in Eastern Tropical Atlantic and its relation to the hydrological conditions. Distributional maps and TS graphs are given.

Central area fisheries annual report 1994

The purpose of this report is to record key events/data and to outline the activities of the NRA Central Area Fisheries Function during 1994. The Rivers looked at include the Ribble, Lune, Hodder and Wyre. The issues that the report looks at includes Hydrological and meterological data, catch data for salmon and sea trout, fish kills, and fish stocking. It also lists the Micro-tag returns for 1994 and the six key objectives that the Central Area Fisheries Function has set itself for 1995. The report uses a range of different graphs and tables to display their data.