Paralelización de algoritmos evolutivos como práctica para una asignatura de Arquitectura de Computadores.

Resumen tomado de la publicación

Compresión de los algoritmos de las operaciones aritméticas en estudiantes de magisterio.

Se expone un estudio sobre dos campos sistema de numeración decimal y algoritmos usuales de las operaciones aritméticas. La investigación estudia los conocimientos que tienen los alumnos de magisterio en dichas áreas. Se explica solamente el campo correspondiente a los algoritmos. Se presentan los resultados generales y un análisis de las respuestas de 82 protocolos de una muestra de 467 sujetos correspondiente al plan de estudios de 1971.

Las dificultades cognitivas (Buggy) en operaciones en las que intervienen algoritmos aritméticos y su tratamiento educativo con programaciones hipermedia.

El estudio persigue comprender los procesos algorítmicos implicados en el aprendizaje de resta, tanto a nivel conceptual como a nivel procedimental, así como la incidencia de la metodología utilizada por el maestro en la producción de los mismos. Para el desarrollo de la investigación, se establecen tres momentos, un primer momento en el que se aborda el marco curricular del área de matemáticas, un segundo momento de estudio del marco teórico general en el que se sustenta el núcleo temático de la investigación, constituido por el análisis de los errores que comenten los niños en el algoritmo de la resta, y un último momento, en el que se desarrolla la investigación. La investigación se desarrolla a través de un marco científico-empírico. Empírico, porque pretende obtener conocimiento por vía de la experiencia y, científico, porque se pretende utilizar métodos rigurosos, en función de la naturaleza del problema, las características de las variables y los objetivos de la investigación. Todo ello desde un paradigma cognitivo. A su vez, la investigación se divide en cuatro estudios, un primer estudio de corte descriptivo-correlacional, y desde el punto de vista de la estrategia de recogida de información, de corte transversal, posteriormente se desarrolla un estudio piloto de corte naturalista, donde la obtención de datos se lleva a cabo a través de grabaciones de los niños y por lo tanto, el análisis de los datos tiene un carácter cualitativo. Un tercer estudio relacionado con los errores dominantes en tercer curso de educación primaria, por último un cuarto estudio, sobre la intervención de los desarrollos hipermedia en el aprendizaje de la resta. El estudio se compone de variables dependientes e independientes, dentro de las dependientes se encuentran: tiempo en solucionar la prueba, nivel de adquisición de conceptos previos para la ejecución correcta del algoritmo de la resta, nivel de aciertos en total de restas, categoría de error en cada resta, total de errores en el total de restas, por otro lado, entre las independientes, se destacan: colegios, cursos, ciclos y sexo. En relación con la muestra utilizada para el estudio, está compuesta por 354 alumnos de segundo a sexto de educación primaria, de cuatro centros de la provincia de Salamanca. Los instrumentos utilizados para la investigación quedan definidos en la siguiente manera: recogida de información a través de cuestionarios a alumnos y profesores, recogida de verbalizaciones de los niños en el momento de la aplicación de la prueba (mediante grabación en video), análisis de datos a través del SPSS, conversión de archivo audio a ordenador mediante Sound Scriber, transcripción de las verbalizaciones con el programa Nudis. Durante el aprendizaje del algoritmo de la resta en nuestras aulas se producen errores (bugs), en el estudio se evidencian en torno al 55,5 por ciento de errores de manera estable. Estos errores disminuyen con el proceso de enseñanza, pero algunos son sistemáticos y se pueden observar en niños más experimentados. Para mejorar esta situación, es necesario que las distintas fases de adquisición del algoritmo de la resta, se aborden a nivel pedagógico, a través de procesos didácticos ordenados y sistematizados, teniendo en cuenta el momento evolutivo propio para su correcta adquisición.

Aplicación de algoritmos evolutivos como técnica de minería de datos para la mejora de cursos hipermedia adaptativos basados en Web.

Resumen basado en el de la publicación

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

Resumen basado en el de la publicación

Problemas en la implementación de algoritmos de routing de alta complejidad en dispositivos móviles: el caso Itiner@

La aparición de terminales de telefonía móvil cada vez más potentes abre un nuevo abanico de posibilidades en cuanto a usos y aplicaciones. Sin embargo, y dadas las limitaciones tanto de memoria como de CPU que tienen estos dispositivos, algunas de las aplicaciones potenciales resultan muy difíciles o incluso imposibles de llevar a la práctica. Este es el caso, por ejemplo, de aplicaciones de cálculo de rutas. En el contexto del proyecto Itiner@, un asistente para rutas turísticas completamente autónomo que debe funcionar incluso sin conexión a Internet, todos los procesos deben ejecutarse íntegramente de forma local en el dispositivo móvil. Dado que es un proyecto orientado al ocio, es importante que la experiencia del usuario sea satisfactoria, por lo que además de poder ejecutar el algoritmo de cálculo de rutas, el sistema debe hacerlo de forma rápida. En este sentido, los algoritmos recursivos habituales son demasiado costosos o lentos para su uso en Itiner@ y ha sido necesario reinventar este tipo de algoritmos en función de las limitaciones que tienen estos dispositivos. En el presente trabajo se presenta el proceso seguido y las dificultades encontradas para implementar un algoritmo recursivo de cálculo de rutas que se ejecute íntegramente en un dispositivo móvil Android de forma eficiente. Así, finalmente se llega a un algoritmo recursivo de cálculo de rutas para dispositivos móviles que se ejecuta de forma más eficiente frente a algoritmos directamente portados a dispositivos móviles. La principal contribución del trabajo es doble: por un lado ofrece algunas guías útiles al desarrollo de algoritmos más eficientes para dispositivos móviles; y por el otro, muestra un algoritmo de cálculo de rutas que funciona con un tiempo de respuesta aceptable, en un entorno exigente, como es el de las aplicaciones de turismo en móviles

Cálculo da complexidade exata de algoritmos do tipo divisão-e-conquista através das equações características

A equação de complexidade de um algoritmo pode ser expressa em termos de uma equação de recorrência. A partir destas equações obtém-se uma expressão assintótica para a complexidade, provada por indução. Neste trabalho, propõem-se um esquema de solução de equações de recorrência usando equações características que são resolvidas através de um "software" de computação simbólica, resultando em uma expressão algébrica exata para a complexidade. O objetivo é obter uma forma geral de calcular a complexidade de um algoritmo desenvolvido pelo método Divisão-e-Conquista.

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.

Um Algoritmo para indução de árvores e regras de decisão

A classificação é uma das tarefas da Mineração de Dados. Esta consiste na aplicação de algoritmos específicos para produzir uma enumeração particular de padrões. Já a classificação é o processo de gerar uma descrição, ou um modelo, para cada classe a partir de um conjunto de exemplos dados. Os métodos adequados e mais utilizados para induzir estes modelos, ou classificadores, são as árvores de decisão e as regras de classificação. As regras e árvores de decisão são populares, principalmente, por sua simplicidade, flexibilidade e interpretabilidade. Entretanto, como a maioria dos algoritmos de indução particionam recursivamente os dados, o processamento pode tornar-se demorado, e a árvore construída pode ser muito grande e complexa, propensa ao overfitting dos dados, que ocorre quando o modelo aprende detalhadamente ao invés de generalizar. Os conjuntos de dados reais para aplicação em Mineração de Dados são, atualmente, muito grandes, e envolvem vários milhares de registros, sendo necessária, também, uma forma de generalizar estes dados. Este trabalho apresenta um novo modelo de indução de classificadores, em que o principal diferencial do algoritmo proposto é a única passada pelo conjunto de treinamento durante o processo de indução, bem como a sua inspiração proveniente de um Sistema Multiagente. Foi desenvolvido um protótipo, o Midas, que foi validado e avaliado com dados de repositórios. O protótipo também foi aplicado em bases de dados reais, com o objetivo de generalizar as mesmas. Inicialmente, foi estudado e revisado o tema de Descoberta de Conhecimento em Bases de Dados, com ênfase nas técnicas e métodos de Mineração de Dados. Neste trabalho, também são apresentadas, com detalhes, as árvores e regras de decisão, com suas técnicas e algoritmos mais conhecidos. Finalizando, o algoritmo proposto e o protótipo desenvolvido são apresentados, bem como os resultados provenientes da validação e aplicação do mesmo.

ANAC : uma ferramenta para a automatização da análise da complexidade de algoritmos

A análise de um algoritmo tem por finalidade melhorar, quando possível, seu desempenho e dar condições de poder optar pelo melhor, dentre os algoritmos existentes, para resolver o mesmo problema. O cálculo da complexidade de algoritmos é muito dependente da classe dos algoritmos analisados. O cálculo depende da função tamanho e das operações fundamentais. Alguns aspectos do cálculo da complexidade, entretanto, não dependem do tipo de problema que o algoritmo resolve, mas somente das estruturas que o compõem, podendo, desta maneira, ser generalizados. Com base neste princípio, surgiu um método para o cálculo da complexidade de algoritmos no pior caso. Neste método foi definido que cada estrutura algorítmica possui uma equação de complexidade associada. Esse método propiciou a análise automática da complexidade de algoritmos. A análise automática de algoritmos tem como principal objetivo tornar o processo de cálculo da complexidade mais acessível. A união da metodologia para o pior caso, associada com a idéia da análise automática de programas, serviu de motivação para o desenvolvimento do protótipo de sistema ANAC, que é uma ferramenta para análise automática da complexidade de algoritmos não recursivos. O objetivo deste trabalho é implementar esta metodologia de cálculo de complexidade de algoritmos no pior caso, com a utilização de técnicas de construção de compiladores para que este sistema possa analisar algoritmos gerando como resultado final a complexidade do algoritmo dada em ordens assintóticas.

Um Estudo de técnicas de aceleração para algoritmos de análise de timing funcional baseados em geração automática de teste

Este trabalho tem como objetivo estudar e avaliar técnicas para a aceleração de algoritmos de análise de timing funcional (FTA - Functional Timing Analysis) baseados em geração automática de testes (ATPG – Automatic Test Generation). Para tanto, são abordados três algoritmos conhecidos : algoritmo-D, o PODEM e o FAN. Após a análise dos algoritmos e o estudo de algumas técnicas de aceleração, é proposto o algoritmo DETA (Delay Enumeration-Based Timing Analysis) que determina o atraso crítico de circuitos que contêm portas complexas. O DETA está definido como um algoritmo baseado em ATPG com sensibilização concorrente de caminhos. Na implementação do algoritmo, foi possível validar o modelo de computação de atrasos para circuitos que contêm portas complexas utilizando a abordagem de macro-expansão implícita. Além disso, alguns resultados parciais demonstram que, para alguns circuitos, o DETA apresenta uma pequena dependência do número de entradas quando comparado com a dependência no procedimento de simulação. Desta forma, é possível evitar uma pesquisa extensa antes de se encontrar o teste e assim, obter sucesso na aplicação de métodos para aceleração do algoritmo.

Detecção de dano estrutural por algoritmos genéticos e sensibilidade modal

A área de pesquisa de testes não-destrutivos é muito importante, trabalhando com o diagnóstico e o monitoramento das condições dos componentes estruturais prevenindo falhas catastróficas. O uso de algoritmos genéticos para identificar mudanças na integridade estrutural através de mudanças nas respostas de vibração da estrutura é um método não-destrutivo que vem sendo pesquisado. Isto se deve ao fato de que são vantajosos em achar o mínimo global em situações difíceis de problemas de otimização, particularmente onde existem muitos mínimos locais como no caso de detecção de dano. Neste trabalho é proposto um algoritmo genético para localizar e avaliar os danos em membros estruturais usando o conceito de mudanças nas freqüências naturais da estrutura. Primeiramente foi realizada uma revisão das técnicas de detecção de dano das últimas décadas. A origem, os fundamentos, principais aspectos, principais características, operações e função objetivo dos algoritmos genéticos também são demonstrados. Uma investigação experimental em estruturas de materiais diferentes foi realizada a fim de se obter uma estrutura capaz de validar o método. Finalmente, se avalia o método com quatro exemplos de estruturas com danos simulados experimentalmente e numericamente. Quando comparados com técnicas clássicas de detecção dano, como sensibilidade modal, os algoritmos genéticos se mostraram mais eficientes. Foram obtidos melhores resultados na localização do que na avaliação das intensidades dos danos nos casos de danos propostos.

Formação de grupos colaborativos em um ambiente multiagente interativo de aprendizagem na internet : um estudo de caso utilizando sistemas multiagentes e algoritmos genéticos

Este texto apresenta a tese de doutorado em Ciência da Computação na linha de pesquisa de Inteligência Artificial, dentro da área de IAD – Inteligência Artificial Distribuída (mais especificamente os Sistemas Multiagentes – SMA). O trabalho aborda a formação de grupos colaborativos em um ambiente multiagente interativo de aprendizagem na web, através da utilização de técnicas de Inteligência Artificial. O trabalho apresenta a definição e implementação de uma arquitetura de agentes modelados com algoritmos genéticos, integrada a um ambiente colaborativo de aprendizagem, o TelEduc. Inicialmente faz-se um breve estudo sobre as áreas envolvidas na tese: Informática na Educação, Educação a Distância, Inteligência Artificial, Inteligência Artificial Distribuída e Inteligência Artificial Aplicada à Educação. Abordam-se, também, as áreas de pesquisa que abrangem os Sistemas Multiagentes e os Algoritmos Genéticos. Após este estudo, apresenta-se um estudo comparativo entre ambientes de ensino e aprendizagem que utilizam a abordagem de agentes e a arquitetura proposta neste trabalho. Apresenta-se, também, a arquitetura de agentes proposta, integrada ao ambiente TelEduc, descrevendo-se o funcionamento de cada um dos agentes e a plataforma de desenvolvimento. Finalizando o trabalho, apresenta-se o foco principal do mesmo, a formação de grupos colaborativos, através da implementação e validação do agente forma grupo colaborativo. Este agente, implementado através de um algoritmo genético, permite a formação de grupos colaborativos seguindo os critérios estabelecidos pelo professor. A validação do trabalho foi realizada através de um estudo de caso, utilizando o agente implementado na formação de grupos colaborativos em quatro turmas de cursos superiores de Informática, na Região Metropolitana de Porto Alegre, em disciplinas que envolvem o ensino de programação de computadores.

Simulação multi agente em mercados financeiros artificiais utilizando algoritmos genéticos

Com o objetivo de estabelecer uma metodologia capaz segregar momentos de mercado e de identificar as características predominantes dos investidores atuantes em um determinado mercado financeiro, este trabalho emprega simulações geradas em um Mercado Financeiro Artificial baseado em agentes, utilizando um Algoritmo Genético para ajustar tais simulações ao histórico real observado. Para tanto, uma aplicação foi desenvolvida utilizando-se o mercado de contratos futuros de índice Bovespa. Esta metodologia poderia facilmente ser estendida a outros mercados financeiros através da simples parametrização do modelo. Sobre as bases estabelecidas por Toriumi et al. (2011), contribuições significativas foram atingidas, promovendo acréscimo de conhecimento acerca tanto do mercado alvo escolhido, como das técnicas de modelagem em Mercados Financeiros Artificiais e também da aplicação de Algoritmos Genéticos a mercados financeiros, resultando em experimentos e análises que sugerem a eficácia do método ora proposto.