Técnicas básicas de computabilidad

La Teoría de la Computabilidad es una disciplina encuadrada en la Informática Teórica que tiene como objetivo establecer los límites lógicos que presentan los sistemas informáticos a la hora de resolver problemas mediante el diseño de algoritmos. Frente a las disciplinas y técnicas que día a día amplían el campo de aplicabilidad práctica de los computadores, esta teoría establece una serie de barreras insalvables por ninguna tecnología digital de procesamiento de la información. Los métodos propios de la Teoría de la Computabilidad pueden ser extraordinariamente complejos, sin embargo, existe un núcleo de resultados fundamentales que son abordables mediante técnicas más asequibles, y que tienen la virtud de reflejar razonablemente el concepto central de indecidibilidad computacional. Este informe incluye una descripción de los conceptos y técnicas que configuran ese núcleo básico de la Teoría. Su propósito es dar cuenta de la primera batería de resultados relacionados con la incomputabilidad de algunos problemas conocidos y relevantes en Informática. Los resultados se presentan utilizando como estándar de programación los programas-while, incluyéndose una explicación detallada y sistemática de la técnica de Diagonalización, además de resultados tan importantes como la tesis de Church-Turing, la función universal o el problema de parada.

El método de reducción en Teoría de la Computabilidad

La Teoría de la Computabilidad es una disciplina encuadrada en la Informática Teórica que tiene como objetivo establecer los límites lógicos que presentan los sistemas informáticos a la hora de resolver problemas mediante el diseño de algoritmos. Estos resultados proporcionan importantes herramientas que se utilizan para demostrar tanto la computabilidad como la incomputabilidad de muchas funciones relevantes. Los primeros problemas incomputables que se encontraron lo fueron allá por la década de los años 30. El problema de parada es el primer y más conocido ejemplo de problema no resoluble mediante técnicas algorítmicas: ningún ordenador, por muy potente que sea, puede anticipar el comportamiento de los programas en ejecución, y decidir de antemano si terminarán o no. Este problema nos proporciona un soporte intuitivo para anticipar la incomputabilidad de otros problemas relacionados y un procedimiento para resolverlos: el método de diagonalización. Sin embargo para determinados problemas también incomputables hay que recurrir a otros métodos. Este texto incluye una descripción de otra técnica básica de Teoría de la Computabilidad: la Reducción. La base del método estriba en demostrar que ciertos pares de problemas están fuertemente relacionados de modo que si el segundo tiene solución algorítmica entonces el primero debe tenerla necesariamente también. Esta relación se establece por medio de funciones transformadoras computables, que permiten convertir de manera automática las instancias positivas del primer problema en instancias positivas del segundo. Esta técnica se utiliza muy a menudo porque resulta comparativamente más sencilla que la diagonalización, ya que en general requiere menos esfuerzo para demostrar la incomputabilidad de un mismo problema.

Firmas electrónicas y su régimen de aplicación, análisis de la normativa en el Ecuador

La presente tesis se ocupa del análisis de la normativa vigente en el Ecuador sobre la Firma Electrónica y su régimen de aplicación. Con el objeto de determinar la problemática actual en la estructura de la normativa en el tratamiento de la Firma Electrónica y, si se encuentra acorde con la normativa internacional. En esta investigación se analiza la Firma Electrónica, teniendo como referencia la firma digital; se examina también la criptografía, rama de las matemáticas, que utilizando fórmulas o algoritmos transforma mensajes ininteligibles a su forma original, siendo la criptografía asimétrica la empleada para crear firmas digitales a través de la utilización de claves. Para su funcionamiento la Firma Electrónica necesita la utilización de los denominados certificados de Firma Electrónica, y la intervención de una tercera parte de confianza o conocida como entidad de certificación. Finalmente tenemos el estudio de los organismos encargados de la promoción, difusión de los servicios electrónicos, de regulación y control de las entidades de certificación. Lo anteriormente expresado se desarrolla en tres capítulos. El capítulo primero sobre La Firma Electrónica. El capítulo segundo que trata sobre el certificado de Firma Electrónica y entidades de certificación de información. El capítulo tercero relativo a los organismos como el COMEXI, CONATEL y la Superintendencia de Telecomunicaciones.

Adaptive device with underlying mechanism defined by a programming language

An adaptive device is made up of an underlying mechanism, for instance, an automaton, a grammar, a decision tree, etc., to which is added an adaptive mechanism, responsible for allowing a dynamic modification in the structure of the underlying mechanism. This article aims to investigate if a programming language can be used as an underlying mechanism of an adaptive device, resulting in an adaptive language.

A Gestão de custos interorganizacionais e a contabilidade de livros abertos em uma montadora de veículos automotores na região do grande ABC

SOARES, Iderlan Charles. A gestão de custos interorganizacionais e a contabilidade de livros abertos em uma montadora de veículos automotores na região do Grande ABC. 2011. 112f. Dissertação (Mestrado em Administração) - Universidade Municipal de São Caetano do Sul, São Caetano do Sul, 2011.

O processo de comercialização de créditos de carbono em empresas instaladas no Brasil

Tese apresentada ao Programa de Pós-graduação em Administração - Doutorado da Universidade Municipal de São Caetano do Sul.

Influência do protocolo agroambiental na gestão ambiental de indústrias do setor sucroenergético da microrregião de Assis/SP: um estudo de múltiplos casos

Tese apresentada ao Programa de Pós-graduação em Administração - Doutorado da Universidade Municipal de São Caetano do Sul

A cultura organizacional e a centralidade nas redes sociais: um estudo exploratório em uma empresa de serviços

O presente artigo apresenta uma pesquisa de campo sobre cultura organizacional e redes sociais que foi realizada junto a uma empresa prestadora de serviços. A questão central de pesquisa é: Como os valores da cultura organizacional se interligam as redes sociais? O objetivo foi verificar se existe a influência da cultura da organização nas características dos grupos sociais, com ênfase na centralidade. A literatura nacional e internacional evidencia que trabalhar com a centralidade significa identificar a posição em que o ator se encontra em relação às trocas e à comunicação na rede; a centralidade em uma rede traz a ideia de poder, isto é, quanto mais central é o indivíduo, mais bem posicionado ele está em relação às trocas e a comunicação como destacam Hanneman e Riddle (2005). Em relação aos procedimentos métodológicos,trata-se de um estudo exploratório de natureza quantitativo; o levantamento feito através de dois questionários elaborados por Nelson (2006) e Nelson e Vasconcelos (2007). O primeiro relativo à cultura organizacional denominado Perfil de Valores Agregados (PVA), que identifica a presença e as prioridades atribuídas dentro de uma organização quanto aos temas: Trabalho “tarefa”, Relações “sociais”, Controle “poder“ e Cognição “Pensamento”. O segundo relativo às redes formadas cujo instrumento constituiu-se da apresentação de uma lista com todos os participantes da pesquisa e foi solicitado a cada membro que informasse sobre a natureza dos contatos adjacentes a cada nome. Os campos nome e cargo já foram entregues pré-preenchidos pelos pesquisadores, os campos aprovações e número de e-mails recebidos e enviados foram preenchidos por meio de estimativa do respondente e o campo dependência foi respondido respeitando-se uma escala de 1 a 6, onde 1 representava pouca e 6 muita dependência da outra pessoa. Utilizou-se uma amostra de 58 respondentes, todos funcionários próprios da empresa prestadora de serviços. Os dados foram tratados pela técnica estatística nãoparamétrica Mann Whitney para os valores da cultura e para os dados das redes Sociais os índices foram apurados por meio do software Ucinet 6.0 de Borgatti, Everett, e Freeman (2002). Os resultados mostraram que os elementos centrais, ou seja, aqueles que têm o maior número de contatos na rede têm um maior alinhamento dos seus valores com os padrões da cultura organizacional e se concluiu que estes podem influenciar e participar na disseminação dos valores presentes na cultura organizacional. O que se pode perceber ao se analisar relação de nomes e funções dos colaboradores é que os quatro atores mais centrais da rede (centralidade) exercem funções gerenciais ou exercem algum tipo de liderança dentro da organização pesquisada; o primeiro é gerente de departamento pessoal, o segundo elemento mais central é gerente do departamento jurídico, o terceiro elemento mais central e sub-gerente operacional e trabalha diretamente com o Gerente Operacional, o quarto elemento é supervisor operacional. Os benefícios e a minimização de custos nas interações sociais caso a empresa utilize estes elementos centrais em programas de coaching ou mentoring, ou em outras ações de mudança, pode favorecer a retirada dos colaboradores da sua zona de conforto e ajudar a disseminar mais rapidamente a Missão, Visão e Valores Organizacionais.

Proposta de uma arquitetura especial para simulação lógica

O objetivo deste trabalho é a proposta de uma arquitetura especial para simulação lógica (AESL). As técnicas e modelos utilizados no processo de simulação lógica são brevemente revistos. É definida uma taxonomia para AESL sob a qual são analisadas diversas propostas de AESL relatadas na literatura. Uma taxonomia já existente é comparada com a proposta. A AESL definida é programável para diferentes algoritmos de simulação lógica. O detalhamento da AESL é, então, incrementado pela implementação de um algoritmo particular. Uma linguagem de simulação discreta é utilizada na construção de um modelo da arquitetura. Os resultados da simulação deste modelo permitem avaliar o desempenho da AESL e otimizar sua estrutura. Uma comparação com outras arquiteturas conclui a análise.

Dimensionamento de pilares esbeltos de concreto armado

O objetivo deste trabalho é o dimensionamento de pilares esbeltos de concreto armado, sob cargas de curta e longa duração, baseado numa análise realística das deformações do mesmo. Apresenta-se três algoritmos numéricos para a obtencão das relações momento fletor-esforço normal-curvatura de uma seção arbitrária de concreto armado, sob flexo-compressão normal. Inclue-se as deformações específicas de fluência e retração do concreto na análise, através de uma alteração nas referidas relações. Apresenta-se alguns critérios de normas, relativos ao dimensionamento de pilares esbeltos de concreto armado e uma comparação dos mesmos, entre si e com o algoritmo numérico desenvolvido. Considerações da NB-1/78 relativas ao projeto de pilares são analisadas, verificando o nivel da precisão obtida. Um procedimento simplificado para a inclusão da fluência do concreto no dimensionamento, proposto pelo CEB, é testado e uma solução para pilares de concreto armado com engastamento elástico simétrico é apresentada, para verificar o nível: do erro cometido ao se estender o conceito de comprimento de flambagem a pilares de concreto armado. Uma série de exemplos experimentais são apresentados, onde a solução numérica para o dimensionamento tem sua precisão verificada. Diversas tabelas foram desenvolvidas para o dimensionamento de pilares esbeltos com secão transversal retangular e armadura simétrica. Todo o estudo é restrito ao caso de flexo-compressão normal.

Paralelização de métodos de resolução de sistemas lineares esparsos com o DECK em um Cluster de PCs

O objetivo desta dissertação é a paralelização e a avaliação do desempenho de alguns métodos de resolução de sistemas lineares esparsos. O DECK foi utilizado para implementação dos métodos em um cluster de PCs. A presente pesquisa é motivada pela vasta utilização de Sistemas de Equações Lineares em várias áreas científicas, especialmente, na modelagem de fenômenos físicos através de Equações Diferenciais Parciais (EDPs). Nessa área, têm sido desenvolvidas pesquisas pelo GMC-PAD – Grupo de Matemática da Computação e Processamento de Alto Desempenho da UFRGS, para as quais esse trabalho vem contribuindo. Outro fator de motivação para a realização dessa pesquisa é a disponibilidade de um cluster de PCs no Instituto de Informática e do ambiente de programação paralela DECK – Distributed Execution and Communication Kernel. O DECK possibilita a programação em ambientes paralelos com memória distribuída e/ou compartilhada. Ele está sendo desenvolvido pelo grupo de pesquisas GPPD – Grupo de Processamento Paralelo e Distribuído e com a paralelização dos métodos, nesse ambiente, objetiva-se também validar seu funcionamento e avaliar seu potencial e seu desempenho. Os sistemas lineares originados pela discretização de EDPs têm, em geral, como características a esparsidade e a numerosa quantidade de incógnitas. Devido ao porte dos sistemas, para a resolução é necessária grande quantidade de memória e velocidade de processamento, característicos de computações de alto desempenho. Dois métodos de resolução foram estudados e paralelizados, um da classe dos métodos diretos, o Algoritmo de Thomas e outro da classe dos iterativos, o Gradiente Conjugado. A forma de paralelizar um método é completamente diferente do outro. Isso porque o método iterativo é formado por operações básicas de álgebra linear, e o método direto é formado por operações elementares entre linhas e colunas da matriz dos coeficientes do sistema linear. Isso permitiu a investigação e experimentação de formas distintas de paralelismo. Do método do Gradiente Conjugado, foram feitas a versão sem précondicionamento e versões pré-condicionadas com o pré-condicionador Diagonal e com o pré-condicionador Polinomial. Do Algoritmo de Thomas, devido a sua formulação, somente a versão básica foi feita. Após a paralelização dos métodos de resolução, avaliou-se o desempenho dos algoritmos paralelos no cluster, através da realização de medidas do tempo de execução e foram calculados o speedup e a eficiência. As medidas empíricas foram realizadas com variações na ordem dos sistemas resolvidos e no número de nodos utilizados do cluster. Essa avaliação também envolveu a comparação entre as complexidades dos algoritmos seqüenciais e a complexidade dos algoritmos paralelos dos métodos. Esta pesquisa demonstra o desempenho de métodos de resolução de sistemas lineares esparsos em um ambiente de alto desempenho, bem como as potencialidades do DECK. Aplicações que envolvam a resolução desses sistemas podem ser realizadas no cluster, a partir do que já foi desenvolvido, bem como, a investigação de précondicionadores, comparação do desempenho com outros métodos de resolução e paralelização dos métodos com outras ferramentas possibilitando uma melhor avaliação do DECK.

Uma Proposta de especificação formal e fundamentação teórica para simulated annealing

Os algoritmos baseados no paradigma Simulated Annealing e suas variações são atualmente usados de forma ampla na resolução de problemas de otimização de larga escala. Esta popularidade é resultado da estrutura extremamente simples e aparentemente universal dos algoritmos, da aplicabilidade geral e da habilidade de fornecer soluções bastante próximas da ótima. No início da década de 80, Kirkpatrick e outros apresentaram uma proposta de utilização dos conceitos de annealing (resfriamento lento e controlado de sólidos) em otimização combinatória. Esta proposta considera a forte analogia entre o processo físico de annealing e a resolução de problemas grandes de otimização combinatória. Simulated Annealing (SA) é um denominação genérica para os algoritmos desenvolvidos com base nesta proposta. Estes algoritmos combinam técnicas de busca local e de randomização. O objetivo do presente trabalho é proporcionar um entendimento das características do Simulated Annealing e facilitar o desenvolvimento de algoritmos com estas características. Assim, é apresentado como Simulated Annealing e suas variações estão sendo utilizados na resolução de problemas de otimização combinatória, proposta uma formalização através de um método de desenvolvimento de algoritmos e analisados aspectos de complexidade. O método de desenvolvimento especifica um programa abstrato para um algoritmo Simulated Annealing seqüencial, identifica funções e predicados que constituem os procedimentos deste programa abstrato e estabelece axiomas que permitem a visualização das propriedades que estes procedimentos devem satisfazer. A complexidade do Simulated Annealing é analisada a partir do programa abstrato desenvolvido e de seus principais procedimentos, permitindo o estabelecimento de uma equação genérica para a complexidade. Esta equação genérica é aplicável aos algoritmos desenvolvidos com base no método proposto. Uma prova de correção é apresentada para o programa abstrato e um código exemplo é analisado com relação aos axiomas estabelecidos. O estabelecimento de axiomas tem como propósito definir uma semântica para o algoritmo, o que permite a um desenvolvedor analisar a correção do código especificado para um algoritmo levando em consideração estes axiomas. O trabalho foi realizado a partir de um estudo introdutório de otimização combinatória, de técnicas de resolução de problemas, de um levantamento histórico do uso do Simulated Annealing, das variações em torno do modelo e de embasamentos matemáticos documentados. Isto permitiu identificar as características essenciais dos algoritmos baseados no paradigma, analisar os aspectos relacionados com estas características, como as diferentes formas de realizar uma prescrição de resfriamento e percorrer um espaço de soluções, e construir a fundamentação teórica genérica proposta.

Método de otimização de produtos e processos medidos por múltiplas características de qualidade

Esta dissertação pretende consolidar um método quantitativo, flexível e genérico que possa ser útil na otimização experimental dos mais variados produtos e processos industriais medidos por múltiplas variáveis de resposta. O que se pretende com o método é identificar o ajuste ótimo dos fatores controláveis, ou seja, aquele que reduz os custos devido à má qualidade de um produto considerando também os custos de matéria-prima e energia gastos na fabricação desse produto. A redução dos custos gerados pela má qualidade de um produto é alcançada através da minimização dos desvios das variáveis de resposta dos seus valores alvos e maximização da robustez do produto ou processo aos fatores de ruído e a possíveis oscilações nos fatores controláveis, pois toda vez que uma variável de resposta desvia-se do seu valor alvo ou apresenta variabilidade, existe uma perda financeira experimentada pelo seu usuário. Ao longo do texto, faz-se uma revisão da literatura existente sobre o assunto, apresentam-se as etapas do método que devem ser cumpridas e algumas ferramentas consideradas eficientes no cumprimento dessas etapas. Logo após, realizam-se estudos práticos para validar o método e, baseado nesses estudos e no referencial teórico, conclui-se sobre o assunto.

Geração de sombras em objetos modelados por geometria sólida construtiva

Atualmente os sistemas computacionais mais sofisticados são aqueles que apresentam imagens gráficas. Devido às características de alta velocidade de processamento e excelente resultado na geração de imagens o uso da Computação Gráfica se dá em diversas áreas como a indústria, pesquisa, publicidade, entretenimento, medicina, treinamento, dentre outras. Este trabalho aborda dois assuntos clássicos na Computação Gráfica, Geometria Sólida Construtiva (CSG) e Sombras Projetadas. Ambos são muito importantes para esta linha de pesquisa da Ciência da Computação. A Geometria Sólida Construtiva é utilizada na modelagem de objetos e as sombras projetadas são necessárias para aumentar o realismo das imagens. Geometria sólida construtiva (CSG) é uma técnica para a modelagem de sólidos, que define sólidos complexos pela composição de sólidos simples (primitivas). Isso inclui também a composição de objetos já combinados, até que se chegue a um objeto mais complexo. Um fator muito importante e necessário na obtenção de imagens realistas e que deve ser considerado é a utilização de sombras, pois estas são eficazes no realismo e impressão espacial de objetos tridimensionais. As sombras estabelecem diversos níveis de profundidade na imagem, fazem uma pontuação geométrica na cena de modo a evitar que os objetos não pareçam estar flutuando no ar. Este trabalho consiste em apresentar uma proposta para a geração de sombras em objetos modelados pela Geometria Sólida Construtiva. Para tanto foram estudados os assuntos referentes à modelagem de objetos por CSG, algoritmos para a geração de sombras “bem delimitadas” e formas de gerar sombras na Geometria Sólida Construtiva. O processo de geração de sombras em cenas modeladas por CSG, através da aplicação das mesmas operações booleanas envolvidas na modelagem dos objetos, sobre as sombras nem sempre apresenta resultados corretos. Diante disso, foram investigadas outras formas de solucionar o problema. Dentre estas, uma alternativa é a realização de transformações na árvore binária CSG, através de outras operações, envolvendo o uso de complemento com operações de união e interseção, para a modelagem do objeto e geração da sombra correspondente. Com base nos estudos realizados foram implementados dois protótipos que exibem a sombra projetada de objetos modelados por CSG. Na implementação do protótipo A utilizaram-se as técnicas tradicionais de modelagem de sólidos e sombra projetada. Os resultados obtidos com este protótipo serviram de referência. No protótipo B os resultados foram obtidos através da aplicação da zona ativa das primitivas na modelagem dos objetos e a sombra é projetada durante o processo de avaliação de contornos do sólido. Os resultados obtidos com este protótipo são comparados com os resultados do protótipo A e são apresentados como forma de exibir a aplicação do método proposto.

Representação na forma normal disjuntiva para a flexibilidade de seqüência na manufatura

A crescente demanda por produtos de melhor qualidade, diferenciados e com custos competitivos tem forçado as manufaturas a se tornarem flexíveis, capacitando-as a responder às mudanças impostas pelo mercado. A flexibilidade permite que as empresas alcancem a customização desejada através da capacitação do sistema de responder e atuar em tempo real, mesmo em um ambiente de incertezas. Para atuar em tempo real, os sistemas de manufatura precisam de representações eficientes dos planos de produção. Muitas vezes, a atuação em tempo real torna-se inviável devido ao crescimento exponencial no número de planos de produção para cada máquina ou operação adicionada ao sistema. Uma possível solução para este problema é uso de representações adequadas para o espaço de estados. A escolha de uma representação adequada para o espaço de estados influencia na capacidade de reposta em tempo real, pois determina o desempenho computacional do sistema através da utilidade e eficiência dos algoritmos desenvolvidos, tornando possível explorar problemas clássicos de flexibilidade, tais como, seqüenciamento, otimização, etc. Entretanto, a geração de uma representação que trabalhe com o espaço de estados completo de uma manufatura é considerada um problema não polinomial (NP). Esta particularidade dificulta o desenvolvimento de algoritmos que trabalhem com uma manufatura flexível. Assim, a geração de uma representação, que trabalhe com pouca memória computacional e permita o desenvolvimento de heurísticas eficientes, é um importante desafio para uma avaliação efetiva da flexibilidade. Este trabalho objetiva o desenvolvimento de uma representação para o espaço de estados de uma manufatura com flexibilidade de seqüência. Na construção desta representação são aplicadas técnicas de modelagem baseadas na teoria dos grafos e nos princípios de álgebra booleana. Inicialmente, os grafos são utilizados para representar todas as seqüências de operações de uma manufatura, posteriormente estas seqüências são convertidas em formas normais disjuntivas (FND). Por fim, é apresentada uma possível aplicação da representação na FND em modelos de programação linear.