Computação 2 de X - Números

A evolução da computação sempre esteve intrinsecamente ligada à matemática. Antes da origem da ciência da computação, a computação nasceu dentro das universidades, nos departamentos de matemática, onde se destacaram algumas das maiores mentes, que estudaram os algoritmos e o que conhecemos hoje como problemas computáveis.

Por isso, neste conjunto de postagens, pretendemos passar por toda ou quase toda a história da computação como conhecemos hoje. Desde os primórdios da matemática até as grandes inovações atuais e o que elas trouxeram de novo para a computação.

Vamos começar no principio, no desenvolvimento dos números.

A descoberta dos números, segundo [1] e [2], foi um dos passos fundamentais na evolução do ser humano. Segundo [1], a sensação de quantidades é compartilhada por todos os animais, mas a descoberta da contagem é o que separa o ser humano primitivo dos outros animais, neste momento cria-se uma relação entre duas ou várias quantidades, onde um elemento de uma quantidade corresponde a um elemento de outra quantidade.

Essa descoberta iniciou principalmente com a criação de animais domésticos. Imagine-se como um criador de ovelhas, se você tiver somente a sensação de quantidades, quando alguns animais se perdem você nunca saberá quantos foram. Mas se você tiver um monte de pedras, cada uma representando uma ovelha, saberá quantas pedras estão sobrando com relação a quantidade de ovelhas que retornaram, haverá mais pedras do que ovelhas.

Segundo [1], anos após a descoberta da contagem houve a passagem da contagem de objetos, como pedras e ovelhas, para a representação abstrata de número. Uma quantidade de objetos agora poderia ser representada por números. Um monte de pedras agora contém quatro pedras, um rebanho de ovelhas agora contém quatro ovelhas, e o quatro é agora uma entidade livre de associação a um objeto específico, uma abstração.

A partir daí passou-se a representar os números de forma escrita, nas civilizações antigas, baseando-se na repetição de símbolos. E foi dado um passo o a criação da aritmética, fundamental para a computação e para a evolução científica humana.

Referências:

[1] Cléuzio Fonseca Filho. História da Computação - O caminho do pensamento e da tecnologia. Porto Alegre. EDPUCRS. 2007.

[2] Sanjoy, Dasgupta; Christo Papadimitriu; Umesh Vazirani. Algoritmos. São Paulo. McGraw-Hill. 2009.

Fonte das Imagens:
Contando Ovelhas: https://escolassempatria.blogspot.com.br/2013/06/como-surgiram-os-numeros.html

Computação 1 de X

Segundo o dicionário Michaelis a palavra computação vem da junção de computar+ação que significa a ação de computar; computo. Informalmente é o conjunto de operações matemáticas ou lógicas que se executam por meio de regras práticas previamente estabelecidas. Segundo o mesmo dicionário temos a partir de agora três definições que podem nos mover a pensar no que realmente é a computação:

1. "Utilização de computador para resolução de qualquer problema ou aplicação de qualquer espécie”. Nesta definição temos a computação como algo que surgiu após a origem do computador, em meados do século 20 e o utilizarmos para resolução de problemas através e algoritmos.
2. "Cálculo”. Nesta definição temos a computação com sua origem na matemática, quando a utilizamos para solucionar problemas através do trabalho com números.
3. “Processamento de dados”. Aqui temos a computação como algo com um conjunto de entradas discretas que através de processos retorna uma saída discreta. O que pode nos trazer de volta a origem da matemática e sua utilização em diferentes formas, como a física, biologia, química entre outras áreas que trabalham como dados e através de algum mecanismo matemático retorna alguma informação.

Segundo o Google, a etimologia da palavra computação vem do Latin computatĭo, -ōnis que significa: “cálculo, computação, conta”, do radical de computātum, superlativo do verbo no latin computāre que significa “contar, calcular, computar”, proverbio informal do inglês computation'id.'

Como você pode perceber a definição de computação está muito ligada a origem dos computadores eletrônicos, mas a computação tem uma origem muito mais antiga. Esta série de postagens objetiva apresentar aos leitores um pouco da história da computação, abrangendo desde a origem da palavra computação, e suas origens matemáticas, até a sua história mais recente, da computação como ciência, linguagens de programação, a criação dos computadores eletrônicos, e o futuro da computação.

Referências:

Dicionário on-line Michaelis. http://michaelis.uol.com.br/moderno/portugues/index.php?lingua=portugues-portugues&palavra=computa%E7%E3o. Acessado em 02/03/2016. Editora Melhoramentos Ltda.

Otimização Combinatória

Otimização é o processo de buscar a melhor solução dentre um conjunto de soluções disponíveis para um problema.

Possui três elementos: as varáveis de decisão (parâmetros para solução do problema), função objetivo (função a ser maximizada e minimizada) e as restrições (define o espaço de soluções desejadas).

Em um sistema de produção as variáveis de decisão podem representar as quantidades produzidas de determinados objetivos; a função objetivo pode ser o interesse relacionado aos custos na produção,(maximizar os ganhos ou minimizar os custos); e as restrições podem ser as limitações operacionais do processo de produção, como quantidade de objetos a serem utilizados.

Otimização Combinatória tenta determinar valores a variáveis de decisão, de modo que uma função desenvolvida utilizando essas variáveis seja otimizada na presença de um conjunto de restrições e pesos associados as variáveis.

Um problema que pode ser modelado como um grafo, pode ser dito como um Problema de Otimização Combinatória.

Podem ser de cinco classes:

• Problemas de conexão: Árvores, Caminho e Emparelhamento. Ex: Árvore Geradora Miníma, N-Rainhas, Caminho Mínimo, e Emparelhamento Bipartido, etc.
• Problemas de Fluxo em Redes: Processo de otimização da distribuição de itens originados em um vértice e consumidos em outros vértices. Ex: Transporte, Alocação, Problema do Transbordo, etc.
• Problema do Caixeiro Viajante: Encontrar o menor custo que se inicie e termine em um vértice passando pelos demais, sem repetição.
• Problemas de Roteamento: Atender demandas localizadas nas arestas ou nos vértices de uma rede. Problema do Carteiro Chines, Roteamento de Veículos e Escala de Tripulação.
• Problemas de Cobertura e Particionamento: É quando se procura o menor conjunto de vértices/arestas tal que toda(o) aresta/vértice do grafo incida em um(a) destes(as) vértices/arestas. Ex: Localização de Facilidades, Localização de Antenas e Radares.

Um conjunto de soluções viáveis, nesse tipo de problema, é muito grande, embora finito. Impossibilitando o uso de busca bruta, que testa todos os valores de soluções possíveis. Para algumas classes é possível utilizar métodos exatos de resolução, a Programação Matemática. Para outras há a necessidade de métodos não-exatos, tais como Heurísticas (Busca Gulosa, Busca em Profundidade, Algoritmo de Dijkstra, Algoritmo de Kruskal, etc) ou Metaheurísticas (Busca Tabu, Algoritmos Genéticos ou Colônia de Formigas).

Fonte: Pires, M. G. Abordagem Neuro-Genética para Mapeamento de Problemas de Conexão em Otimização Combinatória. Tese (Doutorado) - Escola de Engenharia de São Carlos, Universidade de São Paulo. 2009.

Sistemas Híbridos Inteligentes

Segundo Osorio e Vieira (1999) Sistemas Híbridos Inteligentes, de maneira geral, são sistemas que integram dois ou mais métodos diferentes para a solução de um problema.

Neste post não irei listar minuciosamente todos os sistemas híbridos existentes (quem sabe em postagens futuras possa abranger mais o assunto) mas sim apresentar uma visão mais geral sobre os tipos de Sistemas Híbridos Inteligentes mais comuns.

Os sistemas híbridos são úteis pois permitem que uma técnica complemente a outra, cobrindo as suas deficiências, obtendo um melhor desempenho.

Em se tratando de Machine Learning, usar sistemas híbridos pode também trazer a vantagem deste poder adquirir novas informações, fazendo com que esse sistema não tenha apenas uma visão limitada pelas suas restrições.

Os Sistemas Híbridos Inteligentes procuram de certa forma "imitar" o modo como os seres humanos solucionam um problema ao usar diferentes modos de raciocínio. Isso é realizado de formas diversas, uma delas é através da combinação das diferentes técnicas, buscando trocar informações e conhecimento entre seus módulos, o que dá a característica de evolução no tempo. Outra é através da utilização de representações de conhecimento através de regras difusas, probabilísticas, regras e predicados lógicos.

Temos assim um sistema mais robusto e que aceita algumas contradições e conflitos cognitivos entre seus módulos. Mas se for bem explorado pode trazer grandes vantagens.

Existem muitos tipos de Sistemas Híbridos Inteligentes Osorio e Vieira (1999) listaram alguns deles dando ênfase aos sistemas que utilizam os paradigmas de representação do conhecimento por meio simbólico, compreensível ao ser humano (Lógica, Redes semânticas, Frames, scripts), e métodos conexionista (Redes Neurais Artificiais).

São eles:

• Sistemas Simbólico-Difusos: Integram lógica nebulosa (lógica fuzzy) e sistemas especialistas baseados em conhecimento e/ou regras.
• Sistemas Simbólico-Genéticos: Normalmente compostos por algum método de computação evolutiva, responsável pela aquisição do conhecimento, e de um módulo simbólico, responsável pela implementação de mecanismos de inferência simbólica.
• Sistemas Neuro-Genéticos: Utilizam, também, de computação evolutiva, na tentativa de contornar os problemas de escolha da arquitetura da rede neural.
• Sistemas Neuro-CBR: Integração de uma rede neural e um sistema baseado em casos permitindo fazer generalização sobre um conjunto de exemplos de um problema.
• Sistemas Neuro-Simbólicos: É considerado o método mais estudado. Combina a representação conexionista com a representação simbólica, esse tipo de Sistema Híbrido Inteligente pode ser subdividido em outras três categorias
• Sistemas Neuro-Fuzzy: A lógica nebulosa e as redes conexionistas são combinadas.
• Sistemas Neuro-IDT: Combinam a rede neural com árvores de decisão.
• Sistemas Neuro-KBS: Combinam a rede neural com sistemas baseados em conhecimento.

Fonte: Osório, F. e Vieira, R. Sistemas Híbridos Inteligentes. XIX congresso da SBC. ENIA'99 - Encontro Nacional de Inteligência Artificial. 1999