Algoritmos meta-heurísticos para a solução do problema do caixeiro viajante com múltiplas caronas

The Traveling Salesman with Multiple Ridesharing (TSP-MR) is a type of the Capacitated Traveling Salesman, which presents the possibility of sharing seats with passengers taking advantage of the paths the salesman travels through his cycle. The salesman shares the cost of a path with the boarded passengers. This model can portray a real situation in which, for example, drivers are willing to share parts of a trip with tourists that wish to move between two locations visited by the driver’s route, accepting to share the vehicle with other individuals visiting other locations within the cycle. This work proposes a mathematical formulation for the problem, and an exact and metaheuristics algorithms for its solution, comparing them.

Estratégias distribuídas para a coexistência de redes de banda larga sem fio em bandas não-licensiadas

The increasing demand for Internet data traffic in wireless broadband access networks requires both the development of efficient, novel wireless broadband access technologies and the allocation of new spectrum bands for that purpose. The introduction of a great number of small cells in cellular networks allied to the complimentary adoption of Wireless Local Area Network (WLAN) technologies in unlicensed spectrum is one of the most promising concepts to attend this demand. One alternative is the aggregation of Industrial, Science and Medical (ISM) unlicensed spectrum to licensed bands, using wireless networks defined by Institute of Electrical and Electronics Engineers (IEEE) and Third Generation Partnership Project (3GPP). While IEEE 802.11 (Wi-Fi) networks are aggregated to Long Term Evolution (LTE) small cells via LTE / WLAN Aggregation (LWA), in proposals like Unlicensed LTE (LTE-U) and LWA the LTE air interface itself is used for transmission on the unlicensed band. Wi-Fi technology is widespread and operates in the same 5 GHz ISM spectrum bands as the LTE proposals, which may bring performance decrease due to the coexistence of both technologies in the same spectrum bands. Besides, there is the need to improve Wi-Fi operation to support scenarios with a large number of neighbor Overlapping Basic Subscriber Set (OBSS) networks, with a large number of Wi-Fi nodes (i.e. dense deployments). It is long known that the overall Wi-Fi performance falls sharply with the increase of Wi-Fi nodes sharing the channel, therefore there is the need for introducing mechanisms to increase its spectral efficiency. This work is dedicated to the study of coexistence between different wireless broadband access systems operating in the same unlicensed spectrum bands, and how to solve the coexistence problems via distributed coordination mechanisms. The problem of coexistence between different networks (i.e. LTE and Wi-Fi) and the problem of coexistence between different networks of the same technology (i.e. multiple Wi-Fi OBSSs) is analyzed both qualitatively and quantitatively via system-level simulations, and the main issues to be faced are identified from these results. From that, distributed coordination mechanisms are proposed and evaluated via system-level simulations, both for the inter-technology coexistence problem and intra-technology coexistence problem. Results indicate that the proposed solutions provide significant gains when compare to the situation without distributed coordination.

Verificación de algoritmos y estructuras de datos en Dafny

La verificación formal de un programa es la demostración de que este funciona de acuerdo a una descripción del comportamiento esperado en toda posible ejecución. La especificación de lo deseado puede utilizar técnicas diversas y entrar en mayor o menor detalle, pero para ganarse el título de formal esta ha de ser matemáticamente rigurosa. El estudio y ejercicio manual de alguna de esas técnicas forma parte del currículo común a los estudios de grado de la Facultad de Informática y del itinerario de Ciencias de la Computación de la Facultad de Ciencias Matemáticas de la Universidad Complutense de Madrid, como es el caso de la verificación con pre- y postcondiciones o lógica de Hoare. En el presente trabajo se explora la automatización de estos métodos mediante el lenguaje y verificador Dafny, con el que se especifican y verifican algoritmos y estructuras de datos de diversa complejidad. Dafny es un lenguaje de programación diseñado para integrar la especificación y permitir la verificación automática de sus programas, con la ayuda del programador y de un demostrador de teoremas en la sombra. Dafny es un proyecto en desarrollo activo aunque suficientemente maduro, que genera programas ejecutables.

Aceleración de algoritmos de estimación de movimiento mediante OpenCL

El flujo óptico y la estimación de movimiento es área de conocimiento muy importante usado en otros campos del conocimiento como el de la seguridad o el de la bioinformática. En estos sectores, se demandan aplicaciones de flujo óptico que realicen actividades muy importantes con tiempos de ejecución lo más bajos posibles, llegando a tiempo real si es posible. Debido a la gran complejidad de cálculos que siguen a este tipo de algoritmos como se observará en la sección de resultados, la aceleración de estos es una parte vital para dar soporte y conseguir ese tiempo real tan buscado. Por lo que planteamos como objetivo para este TFG la aceleración de este tipo de algoritmos mediante diversos tipos de aceleradores usando OpenCL y de paso demostrar que OpenCL es una buena herramienta que permite códigos paralelizados con un gran Speedup a la par que funcionar en toda una diversa gama de dispositivos tan distintos como un GPU y una FPGA. Para lo anteriormente mencionado trataremos de desarrollar un código para cada algoritmo y optimizarlo de forma no especifica a una plataforma para posteriormente ejecutarlo sobre las diversas plataformas y medir tiempos y error para cada algoritmo. Para el desarrollo de este proyecto partimos de la teoría de dos algoritmos ya existentes: Lucas&Kanade monoescala y el Horn&Schunck. Además, usaremos estímulos para estos algoritmos muy aceptados por la comunidad como pueden ser el RubberWhale o los Grove, los cuales nos ayudarán a establecer la corrección de estos algoritmos y analizar su precisión, dando así un estudio referencia para saber cual escoger.

Utilização de pulsos de radiofrequência fortemente modulados no processamento de informação quântica via ressonância magnética nuclear

Nesta dissertação apresentamos um trabalho de desenvolvimento e utilização de pulsos de radiofreqüência modulados simultaneamente em freqüência, amplitude e fase (pulsos fortemente modulados, SMP, do inglês Strongly Modulated Pulses) para criar estados iniciais e executar operações unitárias que servem como blocos básicos para processamento da informação quântica utilizando Ressonância Magnética Nuclear (RMN). As implementações experimentais foram realizas em um sistema de 3 q-bits constituído por spins nucleares de Césio 133 (spin nuclear 7/2) em uma amostra de cristal líquido em fase nemática. Os pulsos SMP´s foram construídos teoricamente utilizando um programa especialmente desenvolvido para esse fim, sendo o mesmo baseado no processo de otimização numérica Simplex Nelder-Mead. Através deste programa, os pulsos SMP foram otimizados de modo a executarem as operações lógicas desejadas com durações consideravelmente menores que aquelas realizadas usando o procedimento usual de RMN, ou seja, seqüências de pulsos e evoluções livres. Isso tem a vantagem de reduzir os efeitos de descoerência decorrentes da relaxação do sistema. Os conceitos teóricos envolvidos na criação dos SMPs são apresentados e as principais dificuldades (experimentais e teóricas) que podem surgir devido ao uso desses procedimentos são discutidas. Como exemplos de aplicação, foram produzidos os estados pseudo-puros usados como estados iniciais de operações lógicas em RMN, bem como operações lógicas que foram posteriormente aplicadas aos mesmos. Utilizando os SMP\'s também foi possível realizar experimentalmente os algoritmos quânticos de Grover e Deutsch-Jozsa para 3 q-bits. A fidelidade das implementações experimentais foi determinadas utilizando as matrizes densidade experimentais obtidas utilizando um método de tomografia da matriz densidade previamente desenvolvido.

Veicular conceitos matemáticos em estudantes cegos no ensino superior politécnico: pertinência da utilização do multiplano.

Os processos de ensino e de aprendizagem de conceitos matemáticos a estudantes cegos no Ensino Superior, revestem-se de uma complexidade acrescida, advinda da incapacidade sensorial destes estudantes que lhes dificulta ou mesmo impossibilita perceção dos conceitos que se apoiam em representações visuais. Neste âmbito, pretendeu-se identificar alternativas possíveis para ultrapassar essas barreiras, avaliando a pertinência da utilização de produto de apoio, nomeadamente o Multiplano, para a transmissão de conceitos matemáticos transversais aos cursos de Engenharia do Ensino Superior Politécnico a estudantes cegos. O estudo pretendeu identificar as dificuldades sentidas pelos docentes e pelos estudantes cegos na transmissão e assimilação de conceitos matemáticos sobretudo de índole mais visual e gráfica. Pretendeu ainda identificar as estratégias utilizadas pelos docentes para a transmissão desses mesmos conceitos. O estudo aqui reproduzido, de abordagem qualitativa, configura-se num estudo de caso descritivo-exploratório, obtendo-se dados com recurso a questionários aos docentes do Departamento de Matemática (DMAT) da Escola Superior de Tecnologia e Gestão (ESTG) do Instituto Politécnico de Leiria (IPL) e a entrevistas aos três estudantes cegos da área da Engenharia que se encontravam a frequentar a Instituição e também a docentes que lhes lecionaram as Unidades Curriculares de Álgebra Linear, Análise Matemática e Estatística. Contou ainda com a realização de Observações Diretas, com a aplicação do Multiplano a conceitos matemáticos de índole mais gráfica culminado num grupo de discussão com as partes envolvidas. Da análise identificaram-se as estratégias e dificuldades sentidas tanto pelos docentes do DMAT da ESTG como pelos estudantes cegos na transmissão e assimilação de conceitos matemáticos com predominante representação gráfica. Sobressaiu ainda da análise que quando abordados sem recurso ao Multiplano, em geral os conceitos matemáticos foram transmitidos com sucesso aos estudantes cegos, apesar de em alguns casos com restrições e noutros terem sido excluídos devido à sua forte componente gráfica. O estudo evidencia a falta de ferramentas de apoio nesta área e a pertinência da aplicação do Multiplano a vários conceitos matemáticos de difícil abordagem devido à sua componente gráfica.

Os conceitos de "Cultura Esportiva" e "Habitus Esportivo" : Distanciamentos e aproximaçoes

This work deals with two concepts which serve as a support for studies on sport: "sport culture" and "sport habitus". We aim to identify points of intersection and differences between them in the Brazilian field of Physical Education. We conclude that sport culture concept corresponds to the descriptive and structural dimensions of culture conformation in relation to sport in contemporary society, marked by the phenomenon of economic globalization. This concept refers to the symbolic conception of culture that understands the meanings and directions assigned to the sport phenomenon and to its practice by different individuals and social groups. The sport habitus gradually acquired through the exposure of social agents to the logic of the sport field, corresponds to a willingness to think, to make sense and to act in this space. Not everything that is culturally produced in sports is incorporated in the form of sport habitus, but the habitus is based on aspects of culture. That is, the sport culture has a plurality of manifestations that are not always incorporated in the form of a habitus. The aspect that differentiates the manipulation of concepts of culture and sport habitus is the analytical focus of each, working with both in a complementary manner might become a theoretical and methodological option that contributes to the enlargement of the analysis.

Os conceitos de "Cultura Esportiva" e "Habitus Esportivo" : Distanciamentos e aproximaçoes

This work deals with two concepts which serve as a support for studies on sport: "sport culture" and "sport habitus". We aim to identify points of intersection and differences between them in the Brazilian field of Physical Education. We conclude that sport culture concept corresponds to the descriptive and structural dimensions of culture conformation in relation to sport in contemporary society, marked by the phenomenon of economic globalization. This concept refers to the symbolic conception of culture that understands the meanings and directions assigned to the sport phenomenon and to its practice by different individuals and social groups. The sport habitus gradually acquired through the exposure of social agents to the logic of the sport field, corresponds to a willingness to think, to make sense and to act in this space. Not everything that is culturally produced in sports is incorporated in the form of sport habitus, but the habitus is based on aspects of culture. That is, the sport culture has a plurality of manifestations that are not always incorporated in the form of a habitus. The aspect that differentiates the manipulation of concepts of culture and sport habitus is the analytical focus of each, working with both in a complementary manner might become a theoretical and methodological option that contributes to the enlargement of the analysis.

Síndroma compartimental aguda ou das locas: Conceitos essenciais

A síndroma compartimental aguda define-se como sendo a falência da circulação intersticial por conflito de espaço. Representa, habitualmente, uma severa complicação das lesões traumáticas, podendo envolver potencialmente qualquer compartimento do organismo. Mais frequente em fraturas de alta energia cinética e em lesões por esmagamento dos membros, é uma verdadeira emergência ortopédica, por forma a conseguir-se a redução da pressão intracompartimental e restabelecer a perfusão dos tecidos em sofrimento. Assim, a fasciotomia cirúrgica descompressiva, em tempo oportuno, pode evitar a isquémia irreversível dos tecidos mioneurais contidos nos diferentes compartimentos osteomiofasciais, isto é, as retrações fibrosas musculares, a necrose muscular, as lesões nervosas permanentes, a perda permanente da função e, como última consequência, a amputação dos membros. A definição da melhor altura para a fasciotomia nem sempre é uma tarefa fácil, envolvendo critérios clínicos e, também, a determinação do valor da pressão intracompartimental, mormente nos doentes em estado de inconsciência. Nos casos em que houver dúvidas e nos doentes em risco de desenvolver esta complicação, é defensável efetuar uma fasciotomia precoce, mesmo sabendo que pode ser desnecessária, uma vez que as complicações relacionadas com as fasciotomias tardias são devastadoras. Com efeito, o risco de infeção e de septicémia são elevados, a taxa de amputações é considerável e, por vezes, perde-se a vida. As sequelas da síndrome compartimental aguda são uma das causas frequentes de litigância contra os cirurgiões ortopedistas.

PREDIÇÃO DE LINKS EM REDES SOCIAIS ACADÊMICAS: UMA ANÁLISE DA INFLUÊNCIA DAS CARACTERÍSTICAS DA REDE NA EFICÁCIA DOS ALGORITMOS BASEADOS NA TOPOLOGIA

A predição de links em redes sociais tem sido objeto de estudo em um crescente número de artigos científicos e comerciais devido à grande oferta de bases de dados com representações das relações entre pessoas e também devido à facilidade de acesso a recursos computacionais para análise dessas redes. Prever conexões em redes sociais acadêmicas contribui para o crescimento científico, facilitando a colaboração entre pesquisadores com potencial de contribuição mútua. Este trabalho busca identificar as características das redes levam a uma maior eficiência na predição de links feita por algoritmos baseados na topologia. As características serão isoladas conjuntos de dados e alguns experimentos serão repetidos com diferentes algoritmos para buscar identificar tendências. As análises feitas neste trabalho poderão ajudar a compreender melhor a dinâmica das redes sociais acadêmicas e também contribuir na escolha dos melhores algoritmos de predição de link para cada tipo de rede social.

Plataforma de simulación de aberraciones ópticas vía implementación de las características de un SLM y reconstrucción de fase usando algoritmos basados en los sensores de Hartmann-Shack

Dada la importancia que hoy día presenta dentro del ámbito de la óptica, la implementación y conocimiento de dispositivos capaces tanto de generar aberraciones ópticas bien caracterizadas como de censarlas, se presenta a lo largo de este trabajo el desarrollo de una interfaz gráfica en MATLAB, que permita simular el funcionamiento tanto de un sensor de frente de onda de Hartamnn-Shack (HS), así como la simulación de dispositivos capaces de modificar frentes de onda como los SLM, adicionando algoritmos de propagación y cálculo de centroides -- Para ello, se implementarán en primer lugar máscaras de fase que generen frentes de onda aberrados a partir de la modulación en fase de moduladores espaciales de luz o SLM, tanto a través de funciones lente de primer orden en representación de las aberraciones constantes, como de fase cuadrática en representación de las aberraciones de bajo orden y adicionalmente como combinaciones lineales de polinomios de Zernike -- Todo lo anterior se simulará teniendo en cuenta las características técnicas de los SLM, como lo son el número de pixeles en x y en y, el tamaño de estos y la curva de calibración de los moduladores espaciales, tanto para una relación lineal como para una relación no lineal -- Posteriormente se simularán las dos propagaciones sufridas por los haces de luz desde el SLM hasta el CCD (dispositivo de carga acoplada), pasando a través de la matriz de multilentes del HS (MLA), a partir de la implementación de algoritmos de propagación de un solo paso, que nos permitirán observar sobre el plano del CDD el mapa de spots necesario para el censado de las superficies -- Continuaremos con la construcción de algoritmos para determinar los centroides de dicho mapa y sus respectivas coordenadas, seguiremos con la implementación de algoritmos de reconstrucción modal empleados por sensores de frente de onda de Hartmann-Shack, y finalmente compararemos el grado de error existente entre las superficies generadas y las superficies censadas a través del cálculo de su error cuadrático medio