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.

Escola, complexidade e construção do conhecimento

o estudo da relação entre a complexidade do conhecimento e sua construção no ambiente escolar apóia-se na Epistemologia Genética e no paradigma da complexidade. A investigação se delineou como um estudo qualitativo, inspirado na metodologia de Estudo de Caso. O problema de pesquisa procurou indagar a repercussão da fragmentação dos conteúdos programáticos em disciplinas nos anos finais do Ensino Fundamental. Os dados foram coletados através de múltiplas fontes de evidência. Realizaram-se entrevistas, inspiradas na abordagem clínica piagetiana, com alunos e professores; - observações diretas do tipo participante como observador e análise documental. Os dados coletados indicam que as práticas escolares apresentam pressupostos epistemológicos e paradigmáticos que se apóiam no senso comum e estendem-se em métodos empiristas/aprioristas e reducionistas. O pensamento do aluno é manipulado de forma a se enquadrar ao modelo escolar. A fala é reduzida a uma mera ação prática, pois, embora exercida, o professor desconsidera a importância do diálogo. Por sua vez, os exercícios apresentam-se como dois lados de uma mesma moeda. Podem manifestar-se como promotores de técnicas empiristas, quando colocados sob a forma de repetição para a memorização. Todavia, podem se revelar como um recurso extremamente valioso quando colocam um problema, apresentam desafios e permitem a testagem de hipóteses do sujeito. Já os conteúdos programáticos visam a uma eterna diferenciação do objeto de estudo, a qual se configura como uma simples fragmentação capaz de eliminar qualquer dimensão do conhecimento enquanto totalidade. O tempo da aprendizagem acaba por se igualar com aquele que o professor gasta para expor a informação ao aluno. Isso o relega a uma posição passiva que retira o caráter de equilíbrio dinâmico do conhecimento, pois esse sempre se apresenta como um produto pronto e acabado. A escola, então, tem um desconhecimento do próprio conhecimento e o senso comum, que é empirista/apriorista no campo epistemológico, é reducionista em sua dimensão paradigmática.

Co-responsabilidade acadêmico-administrativa : gestão da ordem e da desordem na universidade

O produto de algumas pesquisas em andamento, especialmente de estudos que se propõem a refletir sobre as conseqüências hegemônicas da globalização do capitalismo na Educação Superior, apontam para a disseminação de técnicas de stricto sensu empresarial, objetivando o aprimoramento da gestão acadêmico-administrativa das universidades. Contrapondo-se a essas concepções, em cujas epistemologias, não raro, identifica-se a coação, sobretudo, da autonomia acadêmica, o presente trabalho apresenta a hipótese da co-responsabilidade como uma proposta capaz de suscitar a integração das dimensões pedagógicas e econômico-financeiras que se configuram, normalmente, dissociadas no interior das Instituições de Ensino Superior (IES). A partir desse pressuposto, especialmente centrado nos processos decisórios das IES, admite-se a possibilidade do êxito da gestão administrativa, ou seja, a manutenção e o acréscimo das receitas destinadas à melhoria das condições de oferta dos cursos (bibliotecas, laboratórios, incentivo à dedicação e capacitação docente, pesquisa, extensão etc) como atrelada ao êxito da gestão pedagógica, ou seja, do aprimoramento do ensino e da qualidade das aprendizagens e vice-versa. Embora essas duas injunções, se atreladas a paradigmas simplificadores, dever-se-iam anular em um círculo vicioso, o presente estudo fundamenta-se na teoria da complexidade (de Edgar Morin), por meio da qual se torna possível compreender a organização dos sistemas através de antagonismos (de ordem e desordem), mesmo, aparentemente, contraditórios. Como exemplo prático de implementação desse modelo teórico, esta tese mostra uma experiência vivenciada na Universidade Católica de Pelotas (Brasil), capaz de corroborar a premissa proposta.

O elogio da escola : de mulher para mulher, uma escola imaginada

Esta tese trata das significações atribuídas à instituição escolar, seus saberes e as relações destes com a vida mesma por trinta mulheres em processos de Letramento. A pesquisa que epistemologicamente se funda na teoria do Imaginário Social e na teoria da Complexidade colocou em pauta exatamente este ponto: quais os sentidos atribuídos à escola para um grupo de mulheres migrantes que apresentaram o desejo de estudar e escolarizar os filhos. O grupo de interlocutoras da investigação é composto por mulheres com pouca escolaridade, que estão cursando programas de Alfabetização, mulheres que voltaram a estudar depois de uma pausa para escolarizarem os filhos e mulheres que nunca se afastaram da escola e hoje trabalham nela como educadoras. Critério organizador da amostra a posteriori, a migração – de espaço e/ou de sentido - une essas mulheres. A escolha da Etnometodologia orientou o percurso investigativo e, dentre os procedimentos metodológicos adotados, devem ser destacados os roteiros de pesquisa respondidos por escrito, entrevistas individuais gravadas em áudio, elaboração do diário de campo e categorização dos sentidos atribuídos que compuseram o imaginário instituído e instituinte O objeto da investigação permitiu compreender quais os sentidos que este grupo de mulheres atribui à escola – sentidos já instituídos socialmente, restritos à funcionalidade instrumental de escola –, e a produção de outros ainda não instituídos – inscritos no campo da arte, da paixão, do sonho, da superação, da auto-estima, dos relacionamentos interpessoais e do movimento. A partir dessa polissemia foi possível contrariar hipóteses afirmadas pelo olhar moderno e acadêmico; foi possível também uma aproximação aos sentidos ainda não instituídos, desejos de escola que a tornam maior do que é: o elogio da escola.

Teoria da decisão sob incerteza e a hipótese da utilidade esperada : conceitos analíticos e paradoxos

A teoria da utilidade esperada (EU) é a teoria da decisão mais influente já desenvolvida. A EU é o core da teoria econômica sob incerteza, presente na maior parte dos modelos econômicos que modelam situações de incerteza. Porém, nas últimas três décadas, as evidências experimentais têm levantado sérias dúvidas quanto à capacidade preditiva da EU – gerando grandes controvérsias e uma vasta literatura dedicada a analisar e testar suas propriedades e implicações. Além disso, várias teorias alternativas (teorias não-EU, geralmente, generalizações da EU) têm sido propostas. O objetivo deste trabalho é analisar e avaliar a teoria da utilidade esperada (objetiva) através de uma revisão da literatura, incorporando os principais conceitos desenvolvidos ao longo do tempo. Além disso, este trabalho desenvolve algumas análises originais sobre representação gráfica e propriedades da teoria da utilidade esperada. O trabalho adota uma perspectiva histórica como fio condutor e utiliza uma representação da incerteza em termos de loterias (distribuições de probabilidade discretas). Em linhas gerais, o roteiro de análise do trabalho é o seguinte: princípio da expectância matemática; Bernoulli e a origem da EU; teoria da utilidade sem incerteza; axiomatização da EU; representação gráfica e propriedades da EU; comportamento frente ao risco; medidas de aversão ao risco; dominância estocástica; paradoxos da EU e a reação dos especialistas frente aos paradoxos A conclusão é que existem fortes evidências experimentais de que a EU é sistematicamente violada. Porém, a existência de violações não foi ainda suficientemente testada em experimentos que permitam o aprendizado (tal como pode ocorrer em situações de mercado), onde existe a possibilidade de que as preferências evoluam e que haja uma convergência de comportamento para a EU (ainda que esta possibilidade não se aplique a situações singulares ou que ocorram com pouca freqüência). É possível que testes deste tipo venham a confirmar, em maior ou menor grau, as violações da EU. Mas mesmo que isto ocorra, não significa que a EU não seja útil ou que deva ser abandonada. Em primeiro lugar, porque a EU representou um grande avanço em relação ao princípio da expectância matemática, seu antecessor. Em segundo lugar, porque a EU implica em uma série de propriedades analiticamente convenientes, gerando instrumentos de análise bastante simples (de fato, permitiu a explicação de numerosos fenômenos econômicos), contrastando com a maior complexidade envolvida com o uso das teorias não-EU. Neste cenário, faz mais sentido pensar na EU sendo eventualmente complementada por teorias não-EU do que, sendo abandonada.

Os sistemas de terminação de suínos : uma análise econômica e ambiental a partir da teoria dos conjuntos fuzzi

A escolha do sistema de terminação de suínos e controle de dejetos, que melhor contemple os valores sociais atuais, implica considerar, simultaneamente, pelo menos dois aspectos disciplinarmente distintos - o econômico e o ambiental - o que eleva a complexidade da escolha. Conjuntos fuzzy, por traduzir ordenadamente a percepção expressa pela linguagem, o entendimento relevante porém impreciso da realidade, é uma ferramenta conveniente para o estudo desta situação, a respeito da qual diversos especialistas possuem apreciável conhecimento parcial. Analisa-se o custo de produção de terminadores de suínos da encosta do Vale do Caí, utilizando-se conjuntos fuzzy para identificar causas necessárias e/ou suficientes para o alcance de um baixo custo de produção. Posteriormente, é apresentado um modelo fuzzy para a combinação dos custos de produção com as percepções de suinocultores e de agrônomos quanto ao impacto ambiental da suinocultura.

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.

Avaliação da compressão de dados e da qualidade de imagem em modelos de animação gráfica para web : uma nova abordagem baseada em complexidade de Kolmogorov

Este trabalho versa sobre a avaliação da compressão de dados e da qualidade de imagens e animações usando-se complexidade de Kolmogorov, simulação de máquinas e distância de informação. Complexidade de Kolmogorov é uma teoria da informação e da aleatoriedade baseada na máquina de Turing. No trabalho é proposto um método para avaliar a compressão de dados de modelos de animação gráfica usando-se simulação de máquinas. Também definimos formalmente compressão de dados com perdas e propomos a aplicação da distância de informação como uma métrica de qualidade de imagem. O desenvolvimento de uma metodologia para avaliar a compressão de dados de modelos de animação gráfica para web é útil, a medida que as páginas na web estão sendo cada vez mais enriquecidas com animações, som e vídeo, e a economia de banda de canal tornase importante, pois os arquivos envolvidos são geralmente grandes. Boa parte do apelo e das vantagens da web em aplicações como, por exemplo, educação à distância ou publicidade, reside exatamente na existência de elementos multimídia, que apoiam a idéia que está sendo apresentada na página. Como estudo de caso, o método de comparação e avaliação de modelos de animação gráfica foi aplicado na comparação de dois modelos: GIF (Graphics Interchange Format) e AGA (Animação Gráfica baseada em Autômatos finitos), provando formalmente que AGA é melhor que GIF (“melhor” significa que AGA comprime mais as animações que GIF). Foi desenvolvida também uma definição formal de compressão de dados com perdas com o objetivo de estender a metodologia de avalição apresentada Distância de informação é proposta como uma nova métrica de qualidade de imagem, e tem como grande vantagem ser uma medida universal, ou seja, capaz de incorporar toda e qualquer medida computável concebível. A métrica proposta foi testada em uma série de experimentos e comparada com a distância euclidiana (medida tradicionalmente usada nestes casos). Os resultados dos testes são uma evidência prática que a distância proposta é efetiva neste novo contexto de aplicação, e que apresenta, em alguns casos, resultados superiores ao da distância euclidiana. Isto também é uma evidência que a distância de informação é uma métrica mais fina que a distância euclidiana. Também mostramos que há casos em que podemos aplicar a distância de informação, mas não podemos aplicar a distância euclidiana. A métrica proposta foi aplicada também na avaliação de animações gráficas baseadas em frames, onde apresentou resultados melhores que os obtidos com imagens puras. Este tipo de avaliação de animações é inédita na literatura, segundo revisão bibliográfica feita. Finalmente, neste trabalho é apresentado um refinamento à medida proposta que apresentou resultados melhores que a aplicação simples e direta da distância de informação.

Modelagem de um sistema de gestão da pecuária leiteira sob os preceitos da teoria das restrições

As mudanças ocorridas no macroambiente do agronegócio do leite no Brasil trazem a necessidade de re-fazer as concepções acerca de sua gestão. As práticas gerenciais precisam romper o conservadorismo e buscar uma adequação ao momento vivido sem os vícios de sua cultura. Na concepção de um sistema de gestão da pecuária leiteira, adaptado à realidade das unidades de produção familiares, inseriram-se conceitos da teoria das restrições por meio da estratégia de pesquisa-ação, no noroeste gaúcho-município de São Luiz Gonzaga. A pesquisa foi dividida em três passos: o primeiro passo selecionou, por meio de entrevistas focais, uma unidade de produção representativa de cada sistema com base em uma tipologia segmentada em três sistemas (especializado; intermediário e tradicional); o segundo serviu para testar o sistema de gestão da pecuária leiteira em cada uma das três unidades de produção escolhidas; o terceiro analisou e discutiu os resultados obtidos nas entrevistas, visitas e em documentos. A pesquisa evidenciou a aplicabilidade do sistema de gestão da pecuária leiteira nos três sistemas estudados, utilizando os princípios e a lógica de decisão da teoria das restrições. Os princípios do modelo de decisão da teoria das restrições permitiram tornar mais ágil e coerente o processo de tomada de decisão, assim como as medidas de desempenho da teoria das restrições tornaram a tarefa mais fácil e aplicável. A abordagem sistêmica da teoria das restrições se adequou à complexidade dos sistemas de produção da pecuária leiteira.

A concepção do campo organizacional sustentável sob a ótica da complexidade : uma análise do módulo I do Programa Pró-Guaíba

O presente estudo visa, a partir de uma noção dos componentes da sustentabilidade, aliada ao paradigma moriniano da complexidade e dos pressupostos da teoria neoinstitucional, analisar o papel do Programa Pró-Guaíba na estruturação de um campo organizacional sustentável. Para isso, buscou-se na análise do conteúdo de evidências empíricas, obtidas em fontes de dados primárias (entrevistas em profundidade) e secundárias (pesquisa documental), elementos que propiciassem uma melhor compreensão dos principais aspectos subjacentes a essa questão. Assim, o conceito de sustentabilidade proposto pelo Programa pôde ser melhor evidenciado possibilitando a sua avaliação, tanto no âmbito dos Subprogramas, como na análise do Programa como um todo. Da mesma forma, o arcabouço teórico adequado à compreensão do papel do Programa Pró-Guaíba na estruturação do campo organizacional foi desenvolvido propiciando, uma perspectiva complexificada dos processos institucionais, assim como, uma solução alternativa aos paradoxos da abordagem neoinstitucionalista. Assim, os aspectos que confirmam a estruturação do campo organizacional em decorrência das ações do Programa são evidenciados, contudo, não como um “fato dado como certo” como pressupõe alguns autores da análise neoinstitucional, mas como elementos que compõem um “campo organizacional ativo”, concebido dialogicamente a partir de interações que integram a unidade complexa Programa/campo/sustentabilidade a qual, por sua vez, institucionaliza/desinstitucionaliza recursiva e retroativamente os componentes do sistema por intermédio de processos complexos e dialógicos de adaptação e seleção, de forma a aumentar suas perspectivas de permanência e sobrevivência na ecoorganização mais ampla da qual faz parte.

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.