Nos ultimos anos o uso de tecnicas de aprendizado computacional tornou se uma das tarefas comumente realizadas, pois tem inumeras aplicacoes de reconhecimento de padroes, tais como: reco- nhecimento de voz, classificacao de texto, reconhecimento facial, diagnostico por imagens medicas, entre outras. Dessa forma, um grande numero de tecnicas que lidam com este tipo de problema tem sido desenvolvido ate o momento. Neste trabalho apresentamos uma alternativa para melhorar a taxa acerto de classificacao do classificador binario SLS, que apresentou resultados comparaveis com as SVMs. Nesse metodo, o Gradiente Descendente e utilizado para otimizar a posicao final dos conjuntos de segmentos de reta que representarao cada classe. Embora convirja rapidamente a um valor otimo, muitas vezes e possivel o algoritmo parar em uma regiao de otimos locais, que nao representa o minimo global. Dado esse problema, foram utilizados diferentes algoritmos evolutivos em combinacao com o Gradiente Descendente a fim de melhorar a acuracia do classificador SLS. Adicionalmente a aplicacao de algoritmos evolutivos na fase de treinamento do classificador SLS, foram exploradas duas propostas: (i) explorar o uso de diferente numero de segmentos de reta para representar a distribuicao de dados de cada classe. Dado que no algoritmo original do metodo SLS o numero de segmentos de reta e igual para cada classe, o qual pode significar alguma perda de acuracia ou sobreposicao dos segmentos de reta; (ii) estimar a melhor combinacao de segmentos de reta a serem usados para cada classe. O uso de diferentes quantidades de segmentos de reta por classe pode ser de ajuda na obtencao de melhores porcentagens de acerto, mas determinar uma quantidade otima que permita representar cada classe, e um trabalho dificil. Assim, usamos o algoritmo X-Means, que e um algoritmo de agrupamento, para estimar o numero de segmentos de reta. As propostas exibiram bons resultados que possibilitam a aplicacao do classificador SLS, com um algoritmo de treinamento hibrido, em problemas reais. / During the past years, the use of machine learning techniques have become into one of the most frequently performed tasks, due to the large amount of pattern recognition applications such as: voice recognition, text classification, face recognition, medical image diagnosis, among others. Thus, a great number of techniques dealing with this kind of problem have been developed until now. In this work, we propose an alternative training algorithm to improve the accuracy of the SLS binary Classifier, which produces good results that can be compared to Support Vector Machines. In that classifier, the Gradient Descent method has been used to optimize the final positions of two sets of straight line segments that represent each class. Although, this method quickly converges to an optimum, it is possible that the algorithm stops at a local optimum region, which does not guarantee a global minimum. Given that problem, we combine evolutive optimization algorithms with the gradient descent method to improve the accuracy of the SLS Classifier. In addition to our proposal of using evolutive algorithms, we also developed two proposals: (i) we explore the use of different number of straight line segments to represent the data distribution. Since the original SLS classifier algorithm uses the same number of segments for each class, which could lead to a loss of accuracy or straight line segments overlapping. So, using different number of segments could be the way to improve the accuracy; (ii) estimate the best combination of straight line segments to represent each class. Finding an optimal combination, can be a very difficult problem, so we propose the X-Means algorithm to determine the number of segments. The proposed methodology showed good results which can be used to solve some other real problems with the SLS classifier using the proposed hybrid training algorithm.

This thesis consists of two parts: digital geometry and discrete optimization. In the first part we study the structure of digital straight line segments. We also study digital curves from a combinatorial point of view. In Paper I we study the straightness in the 8-connected plane and in the Khalimsky plane by considering vertical distances and unions of two segments. We show that we can investigate the straightness of Khalimsky arcs by using our knowledge from the 8-connected plane. In Paper II we determine the number of Khalimsky-continuous functions with 2, 3 and 4 points in their codomain. These enumerations yield examples of known sequences as well as new ones. We also study the asymptotic behavior of each of them. In Paper III we study the number of Khalimsky-continuous functions with codomain Z and N. This gives us examples of Schröder and Delannoy numbers. As a byproduct we get some relations between these numbers. In Paper IV we study the number of Khalimsky-continuous functions between two points in a rectangle. Using a generating function we get a recurrence formula yielding this numbers.   In the second part we study an analogue of discrete convexity, namely lateral convexity. In Paper V we define by means of difference operators the class of lateral convexity. The functions have plus infinity in their codomain. For the real-valued functions we need to check the difference operators for a smaller number of points. We study the relation between this class and integral convexity. In Paper VI we study the marginal function of real-valued functions in this class and its generalization. We show that for two points with a certain distance we have a Lipschitz property for the points where the infimum is attained. We show that if a function is in this class, the marginal function is also in the same class. / At the time of the doctoral defense, the following papers were unpublished and had a status as follows: Paper 4: Submitted. Paper 5: Manuscript. Paper 6: Manuscript.

Nos ultimos anos o uso de tecnicas de aprendizado computacional tornou se uma das tarefas comumente realizadas, pois tem inumeras aplicacoes de reconhecimento de padroes, tais como: reco- nhecimento de voz, classificacao de texto, reconhecimento facial, diagnostico por imagens medicas, entre outras. Dessa forma, um grande numero de tecnicas que lidam com este tipo de problema tem sido desenvolvido ate o momento. Neste trabalho apresentamos uma alternativa para melhorar a taxa acerto de classificacao do classificador binario SLS, que apresentou resultados comparaveis com as SVMs. Nesse metodo, o Gradiente Descendente e utilizado para otimizar a posicao final dos conjuntos de segmentos de reta que representarao cada classe. Embora convirja rapidamente a um valor otimo, muitas vezes e possivel o algoritmo parar em uma regiao de otimos locais, que nao representa o minimo global. Dado esse problema, foram utilizados diferentes algoritmos evolutivos em combinacao com o Gradiente Descendente a fim de melhorar a acuracia do classificador SLS. Adicionalmente a aplicacao de algoritmos evolutivos na fase de treinamento do classificador SLS, foram exploradas duas propostas: (i) explorar o uso de diferente numero de segmentos de reta para representar a distribuicao de dados de cada classe. Dado que no algoritmo original do metodo SLS o numero de segmentos de reta e igual para cada classe, o qual pode significar alguma perda de acuracia ou sobreposicao dos segmentos de reta; (ii) estimar a melhor combinacao de segmentos de reta a serem usados para cada classe. O uso de diferentes quantidades de segmentos de reta por classe pode ser de ajuda na obtencao de melhores porcentagens de acerto, mas determinar uma quantidade otima que permita representar cada classe, e um trabalho dificil. Assim, usamos o algoritmo X-Means, que e um algoritmo de agrupamento, para estimar o numero de segmentos de reta. As propostas exibiram bons resultados que possibilitam a aplicacao do classificador SLS, com um algoritmo de treinamento hibrido, em problemas reais. / During the past years, the use of machine learning techniques have become into one of the most frequently performed tasks, due to the large amount of pattern recognition applications such as: voice recognition, text classification, face recognition, medical image diagnosis, among others. Thus, a great number of techniques dealing with this kind of problem have been developed until now. In this work, we propose an alternative training algorithm to improve the accuracy of the SLS binary Classifier, which produces good results that can be compared to Support Vector Machines. In that classifier, the Gradient Descent method has been used to optimize the final positions of two sets of straight line segments that represent each class. Although, this method quickly converges to an optimum, it is possible that the algorithm stops at a local optimum region, which does not guarantee a global minimum. Given that problem, we combine evolutive optimization algorithms with the gradient descent method to improve the accuracy of the SLS Classifier. In addition to our proposal of using evolutive algorithms, we also developed two proposals: (i) we explore the use of different number of straight line segments to represent the data distribution. Since the original SLS classifier algorithm uses the same number of segments for each class, which could lead to a loss of accuracy or straight line segments overlapping. So, using different number of segments could be the way to improve the accuracy; (ii) estimate the best combination of straight line segments to represent each class. Finding an optimal combination, can be a very difficult problem, so we propose the X-Means algorithm to determine the number of segments. The proposed methodology showed good results which can be used to solve some other real problems with the SLS classifier using the proposed hybrid training algorithm.

Made available in DSpace on 2016-04-27T16:56:59Z (GMT). No. of bitstreams: 1 dissertacao_olga_corbo.pdf: 11888785 bytes, checksum: 9fd54776e71e1d194c1bd940375f91fc (MD5) Previous issue date: 2005-08-16 / We have conducted this study to contribute to education of future teachers, by proposing the use of golden section as a context to explore the notion of incommensurable magnitudes. We have based our study on the notion of jeux de cadres , introduced by Douady (1986) in Mathematics Didactic, and used the Didactic Engineering research methodology. Our research was developed on the following hypothesis: a teaching sequence about the golden section which favors an interaction among different knowledge domains can advance the comprehension and/or development of the notion of incommensurability of straight line segments . For this study, we have attempted to determine if the process of successive divisions based on Euclids algorithm helped foster the development of the notion of incommensurability of straight line segments in the future teachers. Furthermore, we verified whether they used the jeux de cadres to solve some problems presented in the sequence and how it contributed to develop the notion of golden rectangle and the notion of incommensurable straight line segments. Finally, we determined if they have established a relationship between the golden rectangle characteristics and the notion of incommensurability of straight line segments, by offering a proof of the incommensurability of the sides of the golden rectangle. The results seem to indicate some progress in relation to the answers provided in the pre-test, which allows us to conclude that the golden section can be a favorable context for the comprehension and/or development of the notion of incommensurable straight line segments. The examination of the students performance have also shown that the sequence can promote an interaction among different knowledge domains, allowing a connection between certain geometric constructions and irrational numbers. At the end, we discuss some limitations observed during the development of this study, whose analysis can serve as a starting point for new investigations on the same theme. / O presente estudo foi realizado com o objetivo de contribuir para a formação inicial de professores de Matemática, propondo a utilização da seção áurea como contexto para explorar a noção de incomensurabilidade de segmentos de reta. Tomando como referencial teórico a noção de jogos de quadros , introduzida por Douady (1986) na Didática da Matemática e usando a metodologia de pesquisa denominada Engenharia Didática, desenvolvemos nosso trabalho com base na hipótese de que uma seqüência de ensino sobre a seção áurea, cuja realização favoreça a articulação entre quadros distintos de conhecimentos, pode propiciar a compreensão e/ou desenvolvimento da noção de incomensurabilidade de segmentos de reta . Por este estudo, examinamos se o processo das divisões sucessivas baseado no algoritmo de Euclides propiciou aos sujeitos de nossa pesquisa o desenvolvimento da noção de incomensurabilidade de segmentos de reta. Analisamos, ainda se os participantes recorriam à mudança de quadros para a resolução de algumas das situações apresentadas na seqüência e de que forma essa estratégia contribuiu para introduzir a noção de retângulo áureo e a noção de incomensurabilidade de segmentos de reta. Finalmente, examinamos se estabeleciam uma relação entre as características do retângulo áureo e a noção de incomensurabilidade de segmentos de reta, por meio da elaboração de uma justificativa de que os lados do retângulo áureo são segmentos incomensuráveis entre si. Os resultados indicam que houve um avanço em relação às respostas apresentadas no pré-teste, permitindo-nos concluir que a seção áurea pode ser um contexto favorável à compreensão e/ou desenvolvimento da noção de segmentos incomensuráveis. O exame do desempenho dos estudantes revelou também que a seqüência desenvolvida pode favorecer a inter-relação entre quadros distintos de conhecimentos, possibilitando que seja estabelecido um elo de ligação entre determinadas construções geométricas e números irracionais. Nas considerações finais, são discutidas as limitações observadas durante a realização deste trabalho, cuja análise poderá servir como ponto de partida para novas investigações sobre o mesmo tema.