Algoritmos antiguos de cálculo.

El artículo forma parte de un dossier titulado: La cultura matemática

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

Resumen tomado de la publicación

Creación de un espacio virtual para la asignatura Algoritmos Geométricos del título del Grado en Ingeniería Informática.

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.

Algoritmos e matemáticas. 'Algoritmos y matemáticas'.

Resumen tomado de la publicació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.

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.

Algoritmos para o posicionamento de células em circuitos VLSI

Este trabalho faz uma análise ampla sobre os algoritmos de posicionamento. Diversos são extraídos da literatura e de publicações recentes de posicionamento. Eles foram implementados para uma comparação mais precisa. Novos métodos são propostos, com resultados promissores. A maior parte dos algoritmos, ao contrário do que costuma encontrar-se na literatura, é explicada com detalhes de implementação, de forma que não fiquem questões em aberto. Isto só possível pela forte base de implementação por trás deste texto. O algorítmo de Fidduccia Mateyeses, por exemplo, é um algorítmo complexo e por isto foi explicado com detalhes de implementação. Assim como uma revisão de técnicas conhecidas e publicadas, este trabalho oferece algumas inovações no fluxo de posicionamento. Propõe-se um novo algorítimo para posicionamento inicial, bem como uma variação inédita do Cluster Growth que mostrta ótimos resultados. É apresentada uma série de evoluções ao algorítmo de Simulated Annealling: cálculo automático de temperatura inicial, funções de perturbação gulosas (direcionadas a força), combinação de funções de perturbação atingindo melhores resultados (em torno de 20%), otimização no cálculo de tamanho dos fios (avaliação das redes modificadas e aproveitamento de cálculos anteriores, com ganhos em torno de 45%). Todas estas modificações propiciam uma maior velocidade e convergência do método de Simulated Annealling. É mostrado que os algorítmos construtivos (incluindo o posicionador do Tropic, baseado em quadratura com Terminal Propagation) apresentam um resultado pior que o Simulated Annealling em termos de qualidade de posicionamento às custas de um longo tempo de CPD. Porém, o uso de técnicas propostas neste trabalho, em conjunto com outras técnicas propostas em outros trabalhos (como o trabalho de Lixin Su) podem acelerar o SA, de forma que a relação qualidade/tempo aumente.

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.

Algoritmos adaptativos para o método GMRES(m)

Nesse trabalho apresentamos algoritmos adaptativos do M´etodo do Res´ıduo M´ınimo Generalizado (GMRES) [Saad e Schultz, 1986], um m´etodo iterativo para resolver sistemas de equa¸c˜oes lineares com matrizes n˜ao sim´etricas e esparsas, o qual baseia-se nos m´etodos de proje¸c˜ao ortogonal sobre um subespa¸co de Krylov. O GMRES apresenta uma vers˜ao reinicializada, denotada por GMRES(m), tamb´em proposta por [Saad e Schultz, 1986], com o intuito de permitir a utiliza¸c˜ao do m´etodo para resolver grandes sistemas de n equa¸c˜oes, sendo n a dimens˜ao da matriz dos coeficientes do sistema, j´a que a vers˜ao n˜ao-reinicializada (“Full-GMRES”) apresenta um gasto de mem´oria proporcional a n2 e de n´umero de opera¸c˜oes de ponto-flutuante proporcional a n3, no pior caso. No entanto, escolher um valor apropriado para m ´e dif´ıcil, sendo m a dimens˜ao da base do subespa¸co de Krylov, visto que dependendo do valor do m podemos obter a estagna¸c˜ao ou uma r´apida convergˆencia. Dessa forma, nesse trabalho, acrescentamos ao GMRES(m) e algumas de suas variantes um crit´erio que tem por objetivo escolher, adequadamente, a dimens˜ao, m da base do subespa¸co de Krylov para o problema o qual deseja-se resolver, visando assim uma mais r´apida, e poss´ıvel, convergˆencia. Aproximadamente duas centenas de experimentos foram realizados utilizando as matrizes da Cole¸c˜ao Harwell-Boeing [MCSD/ITL/NIST, 2003], que foram utilizados para mostrar o comportamento dos algoritmos adaptativos. Foram obtidos resultados muito bons; isso poder´a ser constatado atrav´es da an´alise das tabelas e tamb´em da observa ¸c˜ao dos gr´aficos expostos ao longo desse trabalho.