Doctor en Ciencias de la Ingeniería, Mención Modelación Matemática / The first part of this thesis concerns monochromatic cycle partitions. We make the following three contributions. Our first result is that for any colouring of the edges of the complete bipartite graph $K_{n,n}$ with 3 colours there are 5 disjoint monochromatic cycles which together cover all but $o(n)$ vertices of the graph. In the same situation, 18 disjoint monochromatic cycles together cover all vertices. Next we show that given any $2$-local edge-colouring of the edges of the balanced complete bipartite graph $K_{n,n}$, its vertices can be covered with at most $3$ disjoint monochromatic paths. And, we can cover all vertices of any complete or balanced complete bipartite $r$-locally edge-coloured graph with $O(r^2)$ disjoint monochromatic cycles. We also determine the $2$-local bipartite Ramsey number of a path: Every $2$-local edge-colouring of the edges of $K_{n,n}$ contains a monochromatic path on $n$ vertices. Finally, we prove that any edge-colouring in red and blue of a graph on $n$ vertices and of minimum degree $2n/3 + o(n)$ admits a partition into three monochromatic cycles. This confirms a conjecture of Pokrovskiy approximately. The second part of this thesis contains two independent results about (proper) edge-colouring and parameter estimation respectively. With regards to edge-colouring, we conjecture that any graph $G$ with treewidth $k$ and maximum degree $\Delta(G)\geq k + \sqrt{k}$ satisfies $\chi'(G)=\Delta(G)$. In support of the conjecture we prove its fractional version. Concerning parameter estimation we study, for any fixed monotone graph property $\mathcal{P}=\text{Forb}(\mathcal{\mathcal{F}})$, the sample complexity of estimating a bounded graph parameter $z_{\mathcal{\mathcal{F}}}$ that, for an input graph $G$, counts the number of {spanning} subgraphs of $G$ that satisfy $\mathcal{P}$. Using a new notion of vertex partitions, we improve upon previous upper bounds on the sample complexity of estimating $z_{\mathcal{\mathcal{F}}}$.

Made available in DSpace on 2014-06-12T17:39:40Z (GMT). No. of bitstreams: 2 arquivo6931_1.pdf: 2770678 bytes, checksum: 56abc1e9ebe7d0b4bfc3fa9b7bd71858 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2006 / Em projetos de digitalização de alto volume de documentos, a imagem dos documentos digitalizados pode ser gerada com vários defeitos acarretando dificuldades desde a sua leitura até sua transcrição automática. Além disso, o alto volume de documentos a serem processados gera a necessidade de automatização do processo de digitalização e à procura por melhores soluções para esses problemas. Esta dissertação aborda os seguintes problemas encontrados nos documentos digitalizados monocromáticos: detecção e remoção de borda preta e; detecção e correção da orientação e enviesamento. Um novo filtro para remoção de borda preta foi desenvolvido, testado em 21 mil documentos e comparado com várias ferramentas comerciais. Um novo algoritmo de detecção de orientação e enviesamento com capacidade de estimar a rotação em qualquer ângulo com uma precisão de 0,1º foi desenvolvido e comparado com outro método da literatura. Um segundo algoritmo de detecção de enviesamento foi proposto com o objetivo de aumentar o desempenho do processamento. Observaram-se três problemas na correção de rotação do algoritmo clássico: pontos brancos, contorno acidentado e desconexão de parte dos objetos. Um algoritmo de correção de rotação foi proposto com capacidade de corrigir os três problemas. Um método quantitativo para medir a degradaçãodos algoritmos de correção de rotação foi introduzido e utilizado para comparar o novo algoritmo com outros da literatura. Além dos filtros, duas arquiteturas para processamento de documentos digitalizados monocromáticos foram estudadas: seqüencial e cluster. Um ambiente visual, intitulado BigBatch, foi construído com ambas as arquiteturas. A arquitetura em grid foi apenas especulada

Submitted by Eduarda Figueiredo (eduarda.ffigueiredo@ufpe.br) on 2015-03-06T13:53:56Z No. of bitstreams: 2 Dissertação Ednardo Jerônimo Mariano.pdf: 6874063 bytes, checksum: 791258ac65e7483a77dc6e6d559019f6 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-03-06T13:53:56Z (GMT). No. of bitstreams: 2 Dissertação Ednardo Jerônimo Mariano.pdf: 6874063 bytes, checksum: 791258ac65e7483a77dc6e6d559019f6 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2012-01-31 / A digitalização de grandes quantidades de documentos através de scanners de linha de produção geralmente incorpora na imagem defeitos que acarretam dificuldades desde a sua leitura até sua transcrição automática. Tais defeitos devem ser removidos, obtendo imagens de documentos com melhor qualidade, através de técnicas de processamento de imagens digitais. Devido à grande quantidade de documentos, essas técnicas devem ser rápidas e capazes de abranger a maior parte das falhas nessas imagens. Esta dissertação apresenta um novo algoritmo para remoção de bordas ruidosas cujo tempo de processamento chegou a ser reduzido em até 62% em relação ao algoritmo de Ávila-Lins, com qualidade semelhante, quando testado num conjunto de cinco mil imagens.