A robótica educativa no ensino e aprendizagem de conceitos de programação e algoritmos

Relatório da Prática de Ensino Supervisionada, Ensino de Informática, Universidade de Lisboa, 2013

Classificação e previsão de cardiotocogramas usando algoritmos baseados em redes neuronais

Mestrado em Computação e Instrumentação Médica

Heurísticas de pesquisa local para problemas de máquina única

O escalonamento é uma das decisões mais importantes no funcionamento de uma linha de produção. No âmbito desta dissertação foi realizada uma descrição do problema do escalonamento, identificando alguns métodos para a optimização dos problemas de escalonamento. Foi realizado um estudo ao caso do problema de máquina única através do teste de várias instâncias com o objectivo de minimizar o atraso pesado, aplicando uma Meta-Heurística baseada na Pesquisa Local e dois algoritmos baseados no SB. Os resultados obtidos reflectem que os algoritmos baseados no SB apresentaram resultados mais próximos do óptimo, em relação ao algoritmo baseado na PL. Os resultados obtidos permitem sustentar a hipótese de não existirem algoritmos específicos para os problemas de escalonamento. A melhor forma de encontrar uma solução de boa qualidade em tempo útil é experimentar diferentes algoritmos e comparar o desempenho das soluções obtidas.

La resolució de problemes. 'La resolución de problemas'.

Reflexión sobre los beneficios de la integración de la resolución de problemas matemáticas; la resolución de un problema matemático va más allá de la aplicación de reglas y algoritmos.

Estado situacional de los algoritmos genéticos en los negocios internacionales

La computación evolutiva y muy especialmente los algoritmos genéticos son cada vez más empleados en las organizaciones para resolver sus problemas de gestión y toma de decisiones (Apoteker & Barthelemy, 2000). La literatura al respecto es creciente y algunos estados del arte han sido publicados. A pesar de esto, no hay un trabajo explícito que evalúe de forma sistemática el uso de los algoritmos genéticos en problemas específicos de los negocios internacionales (ejemplos de ello son la logística internacional, el comercio internacional, el mercadeo internacional, las finanzas internacionales o estrategia internacional). El propósito de este trabajo de grado es, por lo tanto, realizar un estado situacional de las aplicaciones de los algoritmos genéticos en los negocios internacionales.

Sobre problemas multiplicativos relacionados con la división de fracciones.

Se investiga el modelo de enseñanza de la división de fracciones y su efecto en las los estudiantes de ESO. El autor estudia la manera en que abordan distintos tipos de problemas multiplicativos que involucran división de fracciones. Se realiza un análisis histórico-epistemológico con las variables: contextos, modelos físicos, constructos, algoritmos y la estructura dimensional de los problemas. Se concluye que el modelo usual de enseñanza condiciona el reconocimiento de la operación que hay que realizar y el enfoque de resolución cuando los problemas con fracciones están en contexto. En concreto los estudiantes tienden a utilizar el esquema cuaternario de la regla de tres con preferencia al esquema ternario de ley de composición.

El desarrollo de las habilidades de adición y sustracción y sus algoritmos : un enfoque cognitivo.

Determinar el papel jugado por los tipos de conteo en el desarrollo de habilidades para la resolución de problemas y algoritmos de adición y sustracción. Analizar la importancia de la estructura semántica y sintáctica de estos problemas a la hora de elaborar estrategias de resolución de los mismos. Elaborar un modelo de sistematización de estos procesos. Muestreo aleatorio estratificado -los estratos fueron los cuatro primeros niveles de EGB- en los colegios públicos de Cartagena. Tomando como marco base el modelo de sistematización de adición sustracción de Heimer y Trueblood (1978), se elaboró un modelo alternativo que recogía, además, las investigaciones del Departamento de Psicología Evolutiva y de la Educación de la Universidad de Murcia sobre adquisiciones numéricas y procesos de cuantificación. Alternativamente se realizó un proceso de integración de los modelos de conteo planteados por la Psicología Cognitiva actual. Para determinar cómo estos modelos se integraban en la sistematización de los procesos de adición y sustracción elaborados por nosotros, se procedió a realizar un estudio correlacional que implicó el control de las siguientes variables: tipos de conteo y habilidades aritméticas. Prueba de aplicación colectiva, sobre conceptos implicados en adición y sustracción. Se completó esta prueba con otra de tipo individual, tomada de Secada y Fuson (en preparación) que a su vez fue adaptada de una tarea usada por Steffe, Spikes y Hirstein, (1976). Escalograma de Guttman para la jerarquización de los items de la prueba colectiva. Un análisis de regresión permitió la validación de esta prueba. Debido a la alta colinealidad encontrada en las variables implicadas en el análisis de regresión, se realizó una prueba no paramétrica (X de Pearson) para explicar las posibles interacciones y las habilidades aritméticas estudiadas. Un análisis de Cluster permitió agrupar los items de la prueba colectiva, y otro, los sujetos. Diferencias significativas en la resolución de las operaciones de adición y sustracción entre los sujetos que utilizaban el 'conteo parcial' y los que usaban una subrutina de 'conteo total'. Quedó reflejada una clara y progresiva evolución paralela en el desarrollo del conteo y las habilidades aritméticas de base. Los conceptos subyacentes a las operaciones de adición y sustracción no se comprendían , es decir, los niños habían aprendido a resolver estas operaciones (y sus algoritmos) de forma mecánica. La enseñanza de las operaciones aritméticas presta mayor atención a los productos que a los procesos, es decir, está más interesada por los resultados del aprendizaje que por el aprendizaje en sí mismo. La dificultad básica de la sustracción sobre la adición viene reflejada por la propia dificultad del pensamiento para hacerse reversible. El uso de estrategias adecuadas de conteo puede facilitar la comprensión de las operaciones y conseguir una mejor automatización de las mismas.

Trabajos para la mejora de ayudantes interactivos para la docencia de algoritmos combinatorios.

Resumen basado en el de la publicación

Los aportes de la tecnología informática al aprendizaje grupal interactivo : la resolución de problemas a través de foro de discusión y de chat.

Resumen basado en el de la publicación

Problem Solving Teaching Guide : its Way of Use, and the Effect on Students. 'Guía docente de resolución de problemas : su modo de uso, y el efecto en los estudiantes'.

Resumen basado en el de la publicación

Enseñanza de la Recursividad mediante Problemas Combinatorios Equivalentes.

Resumen basado en el de la publicación

Novos algoritmos para roteamento de circuitos VLSI

Este trabalho apresenta novos algoritmos para o roteamento de circuitos integrados, e discute sua aplicação em sistemas de síntese de leiaute. As interconexões têm grande impacto no desempenho de circuitos em tecnologias recentes, e os algoritmos propostos visam conferir maior controle sobre sua qualidade, e maior convergência na tarefa de encontrar uma solução aceitável. De todos os problemas de roteamento, dois são de especial importância: roteamento de redes uma a uma com algoritmos de pesquisa de caminhos, e o chamado roteamento de área. Para o primeiro, procura-se desenvolver um algoritmo de pesquisa de caminhos bidirecional e heurístico mais eficiente, LCS*, cuja aplicação em roteamento explora situações específicas que ocorrem neste domínio. Demonstra-se que o modelo de custo influencia fortemente o esforço de pesquisa, além de controlar a qualidade das rotas encontradas, e por esta razão um modelo mais preciso é proposto. Para roteamento de área, se estuda o desenvolvimento de uma nova classe de algoritmos sugerida em [JOH 94], denominados LEGAL. A viabilidade e a eficiência de tais algoritmos são demonstradas com três diferentes implementações. Devem ser também estudados mecanismos alternativos para gerenciar espaços e tratar modelos de grade não uniforme, avaliando-se suas vantagens e sua aplicabilidade em outros diferentes contextos.

Otimização de pré-formas e matrizes em problemas bidimensionais de forjamento

Este trabalho apresenta uma sistemática para realizar a otimização numérica de pré-formas e de matrizes em problemas de forjamento axissimétricos e em estado plano de deformações. Para este fim, desenvolveu-se um código computacional composto basicamente de três módulos: módulo de pré-processamento, módulo de análise e módulo de otimização. Cada um destes foi elaborado acrescentando rotinas em programas comerciais ou acadêmicos disponíveis no GMAp e no CEMACOM. Um programa gerenciador foi desenvolvido para controlar os módulos citados no processo de otimização. A abordagem proposta apresenta uma nova função objetivo a minimizar, a qual está baseada em uma operação booleana XOR (exclusive or) sobre os dois polígonos planos que representam a geometria desejada para o componente e a obtida na simulação, respectivamente. Esta abordagem visa eliminar possíveis problemas geométricos associados com as funções objetivo comumente utilizadas em pesquisas correlatas. O trabalho emprega análise de sensibilidade numérica, via método das diferenças finitas. As dificuldades associadas a esta técnica são estudadas e dois pontos são identificados como limitadores da abordagem para problemas de conformação mecânica (grandes deformações elastoplásticas com contato friccional): baixa eficiência e contaminação dos gradientes na presença de remalhamentos. Um novo procedimento de diferenças finitas é desenvolvido, o qual elimina as dificuldades citadas, possibilitando a sua aplicação em problemas quaisquer, com características competitivas com as da abordagem analítica Malhas não estruturadas são tratadas mediante suavizações Laplacianas, mantendo as suas topologias. No caso de otimização de pré-formas, o contorno do componente a otimizar é parametrizado por B-Splines cujos pontos de controle são adotados como variáveis de projeto. Por outro lado, no caso de otimização de matrizes, a parametrização é realizada em termos de segmentos de reta e arcos de circunferências. As variáveis de projeto adotadas são, então, as coordenadas das extremidades das retas, os raios e centros dos arcos, etc. A sistemática é fechada pela aplicação dos algoritmos de programação matemática de Krister Svanberg (Método das Assíntotas Móveis Globalmente Convergente) e de Klaus Schittkowski (Programação Quadrática Sequencial – NLPQLP). Resultados numéricos são apresentados mostrando a evolução das implementações adotadas e o ganho de eficiência obtido.

Uma fundamentação teórica para a complexidade estrutural de problemas de otimização

Com o objetivo de desenvolver uma fundamentação teórica para o estudo formal de problemas de otimização NP-difíceis, focalizando sobre as propriedades estruturais desses problemas relacionadas à questão da aproximabilidade, este trabalho apresenta uma abordagem semântica para tratar algumas questões originalmente estudadas dentro da Teoria da Complexidade Computacional, especificamente no contexto da Complexidade Estrutural. Procede-se a uma investigação de interesse essencialmente teórico, buscando obter uma formalização para a teoria dos algoritmos aproximativos em dois sentidos. Por um lado, considera-se um algoritmo aproximativo para um problema de otimização genérico como o principal objeto de estudo, estruturando-se matematicamente o conjunto de algoritmos aproximativos para tal problema como uma ordem parcial, no enfoque da Teoria dos Domínios de Scott. Por outro lado, focaliza-se sobre as reduções entre problemas de otimização, consideradas como morfismos numa abordagem dentro da Teoria das Categorias, onde problemas de otimização e problemas aproximáveis são os objetos das novas categorias introduzidas. Dentro de cada abordagem, procura-se identificar aqueles elementos universais, tais como elementos finitos, objetos totais, problemas completos para uma classe, apresentando ainda um sistema que modela a hierarquia de aproximação para um problema de otimização NP-difícil, com base na teoria categorial da forma. Cada uma destas estruturas matemáticas fornecem fundamentação teórica em aspectos que se complementam. A primeira providencia uma estruturação interna para os objetos, caracterizando as classes de problemas em relação às propriedades de aproximabilidade de seus membros, no sentido da Teoria dos Domínios, enquanto que a segunda caracteriza-se por relacionar os objetos entre si, em termos de reduções preservando aproximação entre problemas, num ponto de vista externo, essencialmente categorial.

Análise da complexidade computacional de problemas de estatística descritiva com entradas intervalares

A Estatística é uma ferramenta indispensável em todos os campos científicos. A Estatística descritiva é usada para sintetizar dados. O principal problema desta área está relacionado aos valores de uma amostra, os quais geralmente possuem erros que ocorrem durante a obtenção dos dados. Um dos objetivos deste trabalho é apresentar uma forma de representação para os valores amostrais que considera os erros contidos nestes valores. Esta representação é realizada através de intervalos. A literatura mostra que foram realizadas pesquisas somente em problemas de calcular os valores intervalares das medidas de dispersão variância, covariância e coeficiente de correlação, que a utilização da computação intervalar na solução de problemas de medidas de dispersão intervalar sempre fornece solução com intervalos superestimados (intervalos com amplitude grande), e que ao procurar uma solução com intervalos de amplitude pequena (através da computação da imagem intervalar), o problema passa a pertencer a classe de problemas NP-Difícil. Com o objetivo principal de analisar a complexidade computacional dos problemas de computar os valores dos indicadores estatísticos descritivos com entradas intervalares, e realizar uma classificação quanto a classe de complexidade, a presente tese apresenta: i) definições intervalares de medidas de tendência central, medidas de dispersão e separatrizes; ii) investigação da complexidade de problemas das medidas de tendência central média, mediana e moda, das medidas de dispersão amplitude, variância, desvio padrão, coeficiente de variação, covariância, coeficiente de correlação e das separatrizes e iii) representação intervalar dos valores reais, de tal modo que garante a qualidade de aproximação nos intervalos solução calculado através da extensão intervalar Primeiramente, apresentamos uma abordagem intervalar para os indicadores estatísticos e propomos algoritmos para a solução dos problemas de computar os intervalos de medidas de tendência central intervalar, dispersão intervalar e separatrizes intervalares. Tais algoritmos utilizam a aritmética intervalar definida por Moore, a extensão intervalar e foram projetados para serem executados em ambientes intervalares como IntLab e Maple Intervalar. Por meio da análise da complexidade computacional verificamos que os problemas de medidas de tendência central, dispersão e separatrizes, com entradas intervalares, pertencem à classe de problemas P. Este trabalho apresenta, portanto, algoritmos de tempo polinomial que calculam os intervalos dos indicadores estatísticos com entradas intervalares, e que retornam como solução intervalos com qualidade de aproximação. Os resultados obtidos no desenvolvimento do trabalho tornaram viável a computação da Estatística Descritiva Intervalar.