Synthesis of FPGA-based accelerators implementing recursive algorithms

O desenvolvimento de sistemas computacionais é um processo complexo, com múltiplas etapas, que requer uma análise profunda do problema, levando em consideração as limitações e os requisitos aplicáveis. Tal tarefa envolve a exploração de técnicas alternativas e de algoritmos computacionais para optimizar o sistema e satisfazer os requisitos estabelecidos. Neste contexto, uma das mais importantes etapas é a análise e implementação de algoritmos computacionais. Enormes avanços tecnológicos no âmbito das FPGAs (Field-Programmable Gate Arrays) tornaram possível o desenvolvimento de sistemas de engenharia extremamente complexos. Contudo, o número de transístores disponíveis por chip está a crescer mais rapidamente do que a capacidade que temos para desenvolver sistemas que tirem proveito desse crescimento. Esta limitação já bem conhecida, antes de se revelar com FPGAs, já se verificava com ASICs (Application-Specific Integrated Circuits) e tem vindo a aumentar continuamente. O desenvolvimento de sistemas com base em FPGAs de alta capacidade envolve uma grande variedade de ferramentas, incluindo métodos para a implementação eficiente de algoritmos computacionais. Esta tese pretende proporcionar uma contribuição nesta área, tirando partido da reutilização, do aumento do nível de abstracção e de especificações algorítmicas mais automatizadas e claras. Mais especificamente, é apresentado um estudo que foi levado a cabo no sentido de obter critérios relativos à implementação em hardware de algoritmos recursivos versus iterativos. Depois de serem apresentadas algumas das estratégias para implementar recursividade em hardware mais significativas, descreve-se, em pormenor, um conjunto de algoritmos para resolver problemas de pesquisa combinatória (considerados enquanto exemplos de aplicação). Versões recursivas e iterativas destes algoritmos foram implementados e testados em FPGA. Com base nos resultados obtidos, é feita uma cuidada análise comparativa. Novas ferramentas e técnicas de investigação que foram desenvolvidas no âmbito desta tese são também discutidas e demonstradas.

Novos saberes básicos dos alunos, novas competências dos professores : um estudo no âmbito da supervisão da formação de professores do 1º ciclo do ensino básico na Universidade de Aveiro

As mudanças sociais que, na actualidade, pressionam e desafiam a Escola, nomeadamente quanto aos papéis, funções e desempenho dos professores, implicam a necessidade de repensar a sua formação para que possam responder mais adequadamente aos desafios emergentes. Estes têm particularmente a ver com os novos saberes que essas condições exigem a todos os cidadãos e que são entendidos, do ponto de vista epistemológico, como saberes para agir responsavelmente. Assim, o principal objectivo deste estudo consiste em aprofundar o conhecimento acerca das ambiências e culturas de formação inicial de professores do 1. º Ciclo do Ensino Básico na Universidade de Aveiro, nomeadamente dos processos de supervisão ao nível da disciplina de Prática Pedagógica, tendo em consideração que as características de monodocência dos profissionais deste ciclo de ensino pressupõem um perfil de competência específico. A investigação, de natureza qualitativa, desenvolveu-se de acordo com as abordagens próprias da complexidade e da sistémica, das quais relevamos os princípios da totalidade em que os fenómenos são percebidos como sistemas globais e dinâmicos e da recursividade ao admitirmos a possibilidade de uma relação dialéctica entre os diversos subsistemas considerados. Do ponto de vista metodológico, no sentido de construir uma visão integrada do objecto em estudo, foi utilizado um conjunto de procedimentos específicos (mixed-methods), nomeadamente análise documental, inquirição por questionário e por entrevista semi-estruturada. O questionário foi aplicado à totalidade de licenciados em Ensino do 1.º Ciclo do Ensino Básico pela Universidade de Aveiro, compreendendo o período de 1998 até 2005. A entrevista foi realizada junto de supervisores (cooperantes e institucionais) que vêm acompanhando os núcleos de Prática Pedagógica, no decurso e ao longo do 4.º ano da referida Licenciatura. Quanto aos resultados do estudo, estes podem ser lidos em função de três eixos. Relativamente ao primeiro, que genericamente se refere à evolução dos saberes básicos dos alunos, os contributos parecem sugerir a necessidade de alicerçar os processos de ensino/aprendizagem não apenas nas literacias ler, escrever e contar, como também no desenvolvimento de saberes básicos de natureza geral e transversal, percebidos como competências, tais como aprender a pensar, aprender a aprender, aprender a comunicar e a resolver problemas, numa perspectiva de aprender a ser. O segundo eixo de leitura tem a ver com as competências requeridas aos professores para o desenvolvimento desses saberes estruturantes. De acordo com os dados recolhidos na fase extensiva do estudo, estes parecem coerentes com a revisão de literatura realizada, bem como com os normativos legais que, em Portugal, enquadram o perfil de desempenho dos professores do 1.º Ciclo. Porém, sugerem a necessidade de interligar as dimensões saber, saber-fazer e saber ser, com ênfase nesta última. À semelhança dos resultados referidos no ponto anterior, também o referencial de competências proposto para os professores integra as dimensões saber, saber fazer e saber ser, no qual são valorizadas as competências de reflexão crítica, de aprender a aprender e, de igual forma, o conhecimento profissional nas suas múltiplas dimensões. O terceiro eixo relaciona-se com a qualidade das ambiências e culturas de formação e supervisão. De forma geral, os dados apontam que ambientes que possibilitem uma dimensão de prática curricular alargada em contextos diversificados, que valorizem os princípios da pessoalidade e respeito pelo Outro e que estimulem a reflexão crítica, a auto-implicação dos formandos, o desenvolvimento de competências pessoais e de desenvolvimento profissional (destacando-se as competências para aprender a aprender, a comunicar, a investigar e reflectir), parecem adequar se melhor ao desenvolvimento pessoal e profissional destes professores, no contexto das sociedades contemporâneas. Assim, é possível verificar que os eixos considerados remetem para um conjunto recursivo de saberes e competências que, em diferentes níveis, implicam um compromisso com a acção, numa visão de mundo comprometida com as ideias de bem comum, ou seja, de cidadania universal.

Limited range coverage problems

Tal como o título indica, esta tese estuda problemas de cobertura com alcance limitado. Dado um conjunto de antenas (ou qualquer outro dispositivo sem fios capaz de receber ou transmitir sinais), o objectivo deste trabalho é calcular o alcance mínimo das antenas de modo a que estas cubram completamente um caminho entre dois pontos numa região. Um caminho que apresente estas características é um itinerário seguro. A definição de cobertura é variável e depende da aplicação a que se destina. No caso de situações críticas como o controlo de fogos ou cenários militares, a definição de cobertura recorre à utilização de mais do que uma antena para aumentar a eficácia deste tipo de vigilância. No entanto, o alcance das antenas deverá ser minimizado de modo a manter a vigilância activa o maior tempo possível. Consequentemente, esta tese está centrada na resolução deste problema de optimização e na obtenção de uma solução particular para cada caso. Embora este problema de optimização tenha sido investigado como um problema de cobertura, é possível estabelecer um paralelismo entre problemas de cobertura e problemas de iluminação e vigilância, que são habitualmente designados como problemas da Galeria de Arte. Para converter um problema de cobertura num de iluminação basta considerar um conjunto de luzes em vez de um conjunto de antenas e submetê-lo a restrições idênticas. O principal tema do conjunto de problemas da Galeria de Arte abordado nesta tese é a 1-boa iluminação. Diz-se que um objecto está 1-bem iluminado por um conjunto de luzes se o invólucro convexo destas contém o objecto, tornando assim este conceito num tipo de iluminação de qualidade. O objectivo desta parte do trabalho é então minimizar o alcance das luzes de modo a manter uma iluminação de qualidade. São também apresentadas duas variantes da 1-boa iluminação: a iluminação ortogonal e a boa !-iluminação. Esta última tem aplicações em problemas de profundidade e visualização de dados, temas que são frequentemente abordados em estatística. A resolução destes problemas usando o diagrama de Voronoi Envolvente (uma variante do diagrama de Voronoi adaptada a problemas de boa iluminação) é também proposta nesta tese.

Geometric optimization on visibility problems: metaheuristic and exact solutions

Os problemas de visibilidade têm diversas aplicações a situações reais. Entre os mais conhecidos, e exaustivamente estudados, estão os que envolvem os conceitos de vigilância e ocultação em estruturas geométricas (problemas de vigilância e ocultação). Neste trabalho são estudados problemas de visibilidade em estruturas geométricas conhecidas como polígonos, uma vez que estes podem representar, de forma apropriada, muitos dos objectos reais e são de fácil manipulação computacional. O objectivo dos problemas de vigilância é a determinação do número mínimo de posições para a colocação de dispositivos num dado polígono, de modo a que estes dispositivos consigam “ver” a totalidade do polígono. Por outro lado, o objectivo dos problemas de ocultação é a determinação do número máximo de posições num dado polígono, de modo a que quaisquer duas posições não se consigam “ver”. Infelizmente, a maior parte dos problemas de visibilidade em polígonos são NP-difíceis, o que dá origem a duas linhas de investigação: o desenvolvimento de algoritmos que estabelecem soluções aproximadas e a determinação de soluções exactas para classes especiais de polígonos. Atendendo a estas duas linhas de investigação, o trabalho é dividido em duas partes. Na primeira parte são propostos algoritmos aproximados, baseados essencialmente em metaheurísticas e metaheurísticas híbridas, para resolver alguns problemas de visibilidade, tanto em polígonos arbitrários como ortogonais. Os problemas estudados são os seguintes: “Maximum Hidden Vertex Set problem”, “Minimum Vertex Guard Set problem”, “Minimum Vertex Floodlight Set problem” e “Minimum Vertex k-Modem Set problem”. São também desenvolvidos métodos que permitem determinar a razão de aproximação dos algoritmos propostos. Para cada problema são implementados os algoritmos apresentados e é realizado um estudo estatístico para estabelecer qual o algoritmo que obtém as melhores soluções num tempo razoável. Este estudo permite concluir que as metaheurísticas híbridas são, em geral, as melhores estratégias para resolver os problemas de visibilidade estudados. Na segunda parte desta dissertação são abordados os problemas “Minimum Vertex Guard Set”, “Maximum Hidden Set” e “Maximum Hidden Vertex Set”, onde são identificadas e estudadas algumas classes de polígonos para as quais são determinadas soluções exactas e/ou limites combinatórios.

Problems of minimal aerodynamic resistance

Nesta tese estamos preocupados com o problema da resistência mínima primeiro dirigida por I. Newton em seu Principia (1687): encontrar o corpo de resistência mínima que se desloca através de um médio. As partículas do médio não interagem entre si, bem como a interação das partículas com o corpo é perfeitamente elástica. Diferentes abordagens desse modelo foram feitas por vários matemáticos nos últimos 20 anos. Aqui damos uma visão geral sobre estes resultados que representa interesse independente, uma vez que os autores diferentes usam notações diferentes. Apresentamos uma solução do problema de minimização na classe de corpos de revolução geralmente não convexos e simplesmente conexos. Acontece que nessa classe existem corpos com resistência menor do que o mínimo da resistência na classe de corpos convexos de revolução. Encontramos o infimum da resistência nesta classe e construimos uma sequência regular de corpos que aproxima este infimum. Também apresentamos um corpo de resistência nula. Até agora ninguém sabia se tais corpos existem ou não, evidentemente o nosso corpo não pertence a nenhuma classe anteriormente analisado. Este corpo é não convexo e não simplesmente conexo; a forma topológica dele é um toro, parece um UFO extraterrestre. Apresentamos aqui várias famílias de tais corpos e estudamos as suas propriedades. Também apresentamos um corpo que é natural de chamar um corpo "invisíveis em uma direção", uma vez que a trajectória de cada partícula com a certa direcção coincide com a linha recta fora do invólucro convexo do corpo. ABSTRACT: In this thesis we are concerned with the problem of minimal resistance first addressed by I. Newton in his Principia (1687): find the body of minimal resistance moving through a medium. The medium particles do not mutually interact, and the interaction of particles with the body is perfectly elastic. Different approaches to that model have been tried by several mathematicians during the last 20 years. Here we give an overview of these results that represents interest in itself since all authors use different notations. We present a solution of the minimization problem in the class of generally non convex, simply connected bodies of revolution. It happens that in this class there are bodies with smaller resistance than the minimum in the class of convex bodies of revolution. We find the infimum of the resistance in this class, and construct a sequence of bodies which approximates this infimum. Also we present a body of zero resistance. Since earlier it was unknown if such bodies exists or not, evidently our body does not belong to any class previously examined. The zero resistance body found by us is non-convex and non-simply connected; topologically it is a torus, and it looks like an extraterrestrial UFO. We present here several families of such bodies and study their properties. We also present a body which is natural to call a body "invisible in one direction", since the trajectory of each particle with the given direction, outside the convex hull of the body, coincides with a straight line.

Location-routing problems of semi-obnoxious facilities: approaches and decision support

A presente tese resulta de um trabalho de investigação cujo objectivo se centrou no problema de localização-distribuição (PLD) que pretende abordar, de forma integrada, duas actividades logísticas intimamente relacionadas: a localização de equipamentos e a distribuição de produtos. O PLD, nomeadamente a sua modelação matemática, tem sido estudado na literatura, dando origem a diversas aproximações que resultam de diferentes cenários reais. Importa portanto agrupar as diferentes variantes por forma a facilitar e potenciar a sua investigação. Após fazer uma revisão e propor uma taxonomia dos modelos de localização-distribuição, este trabalho foca-se na resolução de alguns modelos considerados como mais representativos. É feita assim a análise de dois dos PLDs mais básicos (os problema capacitados com procura nos nós e nos arcos), sendo apresentadas, para ambos, propostas de resolução. Posteriormente, é abordada a localização-distribuição de serviços semiobnóxios. Este tipo de serviços, ainda que seja necessário e indispensável para o público em geral, dada a sua natureza, exerce um efeito desagradável sobre as comunidades contíguas. Assim, aos critérios tipicamente utilizados na tomada de decisão sobre a localização destes serviços (habitualmente a minimização de custo) é necessário adicionar preocupações que reflectem a manutenção da qualidade de vida das regiões que sofrem o impacto do resultado da referida decisão. A abordagem da localização-distribuição de serviços semiobnóxios requer portanto uma análise multi-objectivo. Esta análise pode ser feita com recurso a dois métodos distintos: não interactivos e interactivos. Ambos são abordados nesta tese, com novas propostas, sendo o método interactivo proposto aplicável a outros problemas de programação inteira mista multi-objectivo. Por último, é desenvolvida uma ferramenta de apoio à decisão para os problemas abordados nesta tese, sendo apresentada a metodologia adoptada e as suas principais funcionalidades. A ferramenta desenvolvida tem grandes preocupações com a interface de utilizador, visto ser direccionada para decisores que tipicamente não têm conhecimentos sobre os modelos matemáticos subjacentes a este tipo de problemas.

Educar (para) o pensar : desenvolvimento de competências reflexíveis em professores e alunos do 1º CEB : contributos da "Filosofia para Crianças"

O presente estudo inscreve-se na área científica da Formação de Professores, incidindo, particularmente, na compreensão do processo de desenvolvimento das competências reflexivas percebidas como factor de promoção do seu próprio desenvolvimento profissional e pessoal, do desenvolvimento da capacidade de pensar dos seus alunos, da revalorização dos processos curriculares de ensino-aprendizagem e de inovação dos contextos educacionais. Num contexto de complexidade, incerteza e mudança, importa repensar estratégias de formação de professores e de alunos para que possam constituir-se como fatores potenciadores do desenvolvimento da competência reflexiva. Estratégias que convocam, quer o professor, quer o aluno, para um tipo de questionamento de maior exigência reflexiva e consideradas potenciadoras do pensamento crítico, criativo e de cuidado com o outro, numa perspetiva educativa centrada no cuidar, que valoriza a dimensão humana, a atuação responsável, ética e solidária, em todos os planos da vida. Neste estudo propomo-nos retomar algumas das estratégias de formação já configuradas no movimento Filosofia para Crianças e que se constituíram como um programa de formação em contexto, no qual se procurou aprofundar e compreender as múltiplas dimensões e modos como interatuam os diferentes participantes da relação educativa em práticas curriculares reconfiguradas à luz dos pressupostos que sustentam este estudo. Do ponto de vista metodológico, a investigação inscreve-se num paradigma de natureza qualitativa e interpretativa, de matriz hermenêutica e ecológica, configurando uma abordagem de tipo complexo, e com características de estudo de caso, que considera indispensável a participação ativa do sujeito na construção do conhecimento próprio, bem como o carácter de imprevisibilidade e de recursividade das condições e subsistemas em que tal ocorre. No sentido de construir uma visão integrada do objeto em estudo, foram desenvolvidos procedimentos específicos (mixed-methods), nomeadamente análise documental, entrevista semiestruturada, observação participante e inquirição por questionário. O estudo, que decorreu na região centro do país, envolveu 5 professoras do 1.º Ciclo do Ensino Básico, 100 alunos do mesmo nível de ensino e os seus pais/encarregados de educação, inquiridos através de questionário e desenvolveu-se em duas fases. A primeira destinou-se à formação teórico-prática das professoras e, na segunda, foram desenvolvidas sessões práticas de Filosofia para Crianças com os alunos. Os portfolios reflexivos construídos pelos participantes e pela investigadora principal constituíram outra fonte da informação recolhida no estudo empírico. Os resultados do estudo situam-se a quatro níveis: no que respeita aos saberes básicos, ao perfil de competência dos professores, à sua formação e às estratégias e recursos considerados como potenciadores de um pensar de mais elevada qualidade. Quanto ao primeiro nível, o presente estudo releva o carácter estruturante e epistémico de aprender a pensar (bem), salientando que este se processa numa maior amplitude e profundidade dos conteúdos da própria reflexão, às quais subjaz uma visão ampla de cidadania planetária e socialmente comprometida, evidenciando uma ampliação do quadro referencial dos saberes básicos e considerados imprescindíveis para a educação dos cidadãos. A um segundo nível, salienta-se a exigência de um perfil de competência profissional que permita aos professores desenvolver nos seus alunos um pensar de qualidade e, simultaneamente, melhorar a sua própria competência reflexiva. Neste sentido, o estudo aponta para a continuidade das respostas que têm vindo a ser equacionadas por vários autores nacionais e internacionais que, ao abordarem a problemática da formação, do conhecimento profissional e do desenvolvimento identitário dos professores, têm acentuado a importância dos modelos crítico-reflexivos da formação e de uma supervisão ecológica, integradora, não standard e humanizada, no desenvolvimento das sociedades contemporâneas. Conforme os dados sugerem, admite-se que a formação integral dos cidadãos passa pela inclusão e interligação de diferentes áreas do conhecimento que, concertada e complementarmente, possam contribuir para o desenvolvimento da sensibilidade, do pensamento crítico e criativo, de uma cultura da responsabilidade e de uma atitude ética mais ativa e interventiva. Neste sentido, reafirma-se a importância de um trajeto formativo que promova a efetiva articulação entre teoria e a prática, o diálogo crítico-reflexivo entre saberes científicos e experiência, que focalize o profissional na sua praxis e saliente a sua conexão com o saber situado em contexto vivencial e didático- -pedagógico. Realça-se a pertinência de dinâmicas formativas que, a exemplo de “comunidades de investigação/aprendizagem”, na sua aceção de redes de formação que, na prossecução de projetos e propósitos comuns, incentivam a construção de itinerários próprios e de aprendizagens individuais, mobilizando processos investigativos pessoais e grupais. Evidencia-se a valorização de práticas promotoras da reflexão, do questionamento, da flexibilidade cognitiva como eixos estruturadores do pensamento e da ação profissional e como suporte do desenvolvimento profissional e pessoal, corroborando a importância dos processos transformadores decorrentes da experiência, da ação e da reflexão sobre ela. Finalmente, no que respeita às estratégias e recursos, os dados permitem corroborar a riqueza e o potencial do uso de portfolios reflexivos no desenvolvimento de competências linguísticas, comunicacionais, reflexivas e meta-reflexivas e o entendimento de que o processo de construção da identidade profissional ocorre e desenha-se numa dinâmica reflexiva- -prospetiva (re)confirmadora ou (re)configuradora de ideias, convicções, saberes e práticas, ou seja, identitária. De igual modo, a investigação releva a importância da construção de portfolios, por parte dos alunos, para o desenvolvimento da qualidade do seu pensamento, sublinhando-se o seu carácter inovador nesta área. Evidencia-se, ainda, a diversidade de estratégias que respeitem os interesses, necessidades e expectativas dos alunos e o seu contexto de vida, tal como o recurso a materiais diversificados que, atentos ao conteúdo da mensagem, possibilitem a autonomia do pensamento, o exercício efetivo da reflexão crítica e do questionamento, na sua articulação com as grandes questões que sempre despertaram a curiosidade humana e cuja atualidade permanece. Materiais e recursos que estabeleçam o diálogo entre razão e imaginação, entre saber e sensibilidade, que estimulem o envolvimento dos alunos na resolução de problemas e na procura conjunta de soluções e na construção de projetos individuais na malha dos projetos comuns. Reafirma-se, pois, a importância da humanização do saber, a educação pensada como vivência solidária de direitos e deveres. Uma perspetiva educacional humanista que assenta nas trajetórias de vida, na recuperação de experiências pessoais e singulares, que procura compreender a identidade como um processo em (re)elaboração permanente. O presente estudo integra-se na rede de cooperação científica Novos saberes básicos dos alunos no século XXI, novos desafios à formação de professores sendo que, e na linha das investigações produzidas neste âmbito, destaca que o alargamento das funções do professor do 1.º Ciclo do Ensino Básico, que colocando a tónica da ação pedagógica no como se aprende e para quê e na possibilidade de aprender e incorporar o imprevisível, incide no desenvolvimento de um conjunto de capacidades que vão para além das tradicionalmente associadas ao ensinar a ler, escrever e contar. Releva-se, pois, a pertinência da criação de ambientes educativos nos quais professores e alunos entreteçam, conjunta e coerentemente, conhecer, compreender, fazer, sentir, dizer, ver, ouvir e (con)viver em prol de uma reflexão que nos encaminhe no sentido de ser(mos) consciência.

Polyhedral study of mixed integer sets arising from inventory problems

“Branch-and-cut” algorithm is one of the most efficient exact approaches to solve mixed integer programs. This algorithm combines the advantages of a pure branch-and-bound approach and cutting planes scheme. Branch-and-cut algorithm computes the linear programming relaxation of the problem at each node of the search tree which is improved by the use of cuts, i.e. by the inclusion of valid inequalities. It should be taken into account that selection of strongest cuts is crucial for their effective use in branch-and-cut algorithm. In this thesis, we focus on the derivation and use of cutting planes to solve general mixed integer problems, and in particular inventory problems combined with other problems such as distribution, supplier selection, vehicle routing, etc. In order to achieve this goal, we first consider substructures (relaxations) of such problems which are obtained by the coherent loss of information. The polyhedral structure of those simpler mixed integer sets is studied to derive strong valid inequalities. Finally those strong inequalities are included in the cutting plane algorithms to solve the general mixed integer problems. We study three mixed integer sets in this dissertation. The first two mixed integer sets arise as a subproblem of the lot-sizing with supplier selection, the network design and the vendor-managed inventory routing problems. These sets are variants of the well-known single node fixed-charge network set where a binary or integer variable is associated with the node. The third set occurs as a subproblem of mixed integer sets where incompatibility between binary variables is considered. We generate families of valid inequalities for those sets, identify classes of facet-defining inequalities, and discuss the separation problems associated with the inequalities. Then cutting plane frameworks are implemented to solve some mixed integer programs. Preliminary computational experiments are presented in this direction.

A recursive construction of the regular exceptional graphs with least eigenvalue -2

In spectral graph theory a graph with least eigenvalue 2 is exceptional if it is connected, has least eigenvalue greater than or equal to 2, and it is not a generalized line graph. A ðk; tÞ-regular set S of a graph is a vertex subset, inducing a k-regular subgraph such that every vertex not in S has t neighbors in S. We present a recursive construction of all regular exceptional graphs as successive extensions by regular sets.