Por favor, use este identificador para citar o enlazar este ítem: http://bibdigital.epn.edu.ec/handle/15000/24450
Título: Aplicaciones de estructuras de datos a problemas matemáticos: implementación del problema de seleccionar de un conjunto de puntos dado, los subconjuntos de cuatro puntos colineales.
Autor: Chulde Ortiz, Joshua Israel
Palabras clave: MATEMÁTICAS
PUNTOS COLINEALES
ALGORITMO
ESTRUCTURAS DE DATOS
HEAPSORT
Fecha de publicación: mar-2023
Editorial: Quito : EPN, 2023.
Citación: Chulde Ortiz, J.I. (2023). Aplicaciones de estructuras de datos a problemas matemáticos: implementación del problema de seleccionar de un conjunto de puntos dado, los subconjuntos de cuatro puntos colineales. 48 páginas. Quito : EPN.
Resumen: Among years, computational geometry has proposed various problems of interest, from which a large number of tools have been deployed. Those tools have helped to solve these particular problems, also, providing new tools to address more practical and efficient for both new and old problems. One of these questions is the problem of collinear points. The collinear points problem proposes that, given a set of points, find and report all possible subsets of collinear points. This document addresses two possible solutions to this problem and proposes a comparison of their performance. The first algorithm, labeled as brute force, analyses all possible combinations of points to determine collinearity. The algorithm does not use efficient tools to reach its solution. While second algorithm, addressed as intelligent, will take advantage of data structure tools such as binary trees and efficient data ordering algorithms in order to reach the same solution, but handling the initial set in a better way. The algorithms will be implemented in the programming language C++. They will be tested with randomly generated instances of different sizes. At the end, the efficiency of the algorithms will be compared.
Descripción: La geometría computacional a lo largo de los años ha planteado varios problemas de interés, a partir de los cuales se ha desplegado una gran cantidad de herramientas que ayudan a la resolución de estos precisos problemas, y a su paso, proporcionan nuevas herramientas para abordar de manera más práctica y eficiente tanto nuevos como antiguos problemas. Una de estas cuestiones es el problema de puntos colineales. El problema de puntos colineales propone encontrar y reportar dentro de un conjunto de puntos dado, todos los posibles subconjuntos de puntos colineales contenidos en el conjunto. El presente trabajo aborda dos posibles soluciones a este problema y plantea realizar una comparación en la eficiencia del rendimiento de las mismas. El primero de los algoritmos escogidos, denominado de fuerza bruta, utiliza el principio de analizar todas las posibles combinaciones de puntos para determinar colinealidad, siendo éste, como su nombre lo indica, el algoritmo que no emplea herramientas eficientes para llegar a su solución. El segundo algoritmo, denominado inteligente, aprovechará herramientas de estructuras de datos como los árboles binarios y algoritmos eficientes de ordenación de datos para poder llegar a la misma solución que el primer algoritmo, con la diferencia de manejar de mejor manera el arreglo inicial y resolver el problema en menor tiempo. Los algoritmos serán implementados en el lenguaje de programación C++ siendo puestos a prueba con instancias de distintos tamaños generadas aleatoriamente. Al finalizar, se comparará la eficiencia de los algoritmos.
URI: http://bibdigital.epn.edu.ec/handle/15000/24450
Tipo: bachelorThesis
Aparece en las colecciones:TIC - Ingeniería Matemática Aplicada

Ficheros en este ítem:
Fichero Descripción TamañoFormato 
CD 13374.pdf2,37 MBAdobe PDFVisualizar/Abrir


Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.