DATA WAREHOUSE E DATA MINING

TIPOS DE SIMULADORES E LINGUAGENS DE SIMULAÇÃO

O QUE É SIMULAÇÃO?

          Os processos de modelagem e simulação estão intimamente vinculados, portanto, pode-se defini-los como uma experimentação computacional, onde usamos modelos de um sistema real ou idealizado para o estudo de problemas reais de natureza complexa, com o objetivo de testar diferentes alternativas operacionais a fim de encontrar e propor melhores formas de operação que visem a otimização do sistema como um todo. Contudo, vale ressaltar, que a simulação propriamente dita nada mais é do que a experimentação, etapa posterior à construção do modelo conceitual e da modelagem computacional, ou seja, trata-se da fase de testes.

Figura 1: Etapas do Processo de Modelagem e Simulação

Como observado no esquema acima, a simulação é a terceira etapa – executada após a construção do modelo conceitual e legitimação do modelo computacional – onde serão consideradas e testadas as diversas alternativas propostas. Nesta fase ocorrerão testes experimentais para a realização das análises pertinentes, a fim de avaliar o efeito de possíveis alterações antes que elas sejam executadas de fato. Dessa forma, o ponto central do processo de simulação é testar várias soluções para um determinado problema antes que as mesmas sejam implementadas, ou seja, os recursos somente serão investidos em propostas exaustivamente avaliadas e que tenham o retorno comprovado.

Situações onde podem ser aplicadas a Modelagem e a Simulação:

- Saber qual melhor estratégia adotar para um investimento futuro, como iniciar uma operação ou projeto novo ou mesmo ampliar e desenvolver um já existente.

- Identificar gargalos e pontos críticos do processo. Exemplo: estoques desnecessários, recursos ociosos, setups desnecessários etc.

- Conceber uma ideia ou compreensão mais clara do processo no qual se deseja melhorar.

- Testar novas alternativas e métodos antes de sua implementação de fato, a fim de evitar interferências no processo em uso naquele momento.

TIPOS DE SIMULADORES

            Simulador é um software com a capacidade de reproduzir o comportamento de um sistema, ou seja, simuladores reproduzem situações que não estão ocorrendo de fato.

Os dois principais tipos de simuladores são:

Simuladores de interface gráfica e orientados a objeto

Esses simuladores apresentam como principais características:

- Interface gráfica de comunicação com o usuário;

- Desenvolvimento de modelos orientados a objeto;

- Criam animações do modelo executado;

- Fornecem relatórios sobre os modelos executados;

- Fornecem ferramentas estatísticas para tratamento dos dados utilizados na simulação.

             Exemplo: ARENA, PROMODEL, AUTOMOD, entre outros.

Simuladores interativos e inteligentes

           Simuladores e interativos e inteligentes são considerados como a nova tendência. Podem-se destacar como principais características:

- Emprego de recursos de realidade virtual;

- Inteligência Artificial;

- Sistemas Especialistas.

O QUE É LINGUAGEM DE SIMULAÇÃO?

       Geralmente, modelos de simulação são muito complicados e possuem várias interações dentro dos elementos de um sistema, além disso, muitas destas interações se modificam ao longo da execução do programa. Pensando nisso, começou-se a desenvolver linguagens especiais que simplificavam a tradução, quando comparadas às linguagens genéricas.

Características:

- Fornece a maioria dos aspectos necessários à programação;

- Reduz o trabalho de programador;

- Fornece um framework natural para modelagem;

- Possibilita a fácil alteração dos modelos;

- Facilita a detecção de erros

Principais Vantagens:

- Modelador já conhece a linguagem;

- Disponibilidade;

- Reduz o tempo de execução;

- Possibilita certa flexibilidade de programação;

- Custos menores de programação.

TIPOS DE LINGUAGENS DE SIMULAÇÃO

Linguagens de simulação contínuas:

- CSMP, DYNAMO

- Equações diferenciais

- Usadas em engenharia química

Linguagens de simulação de eventos discretos:

- SIMULA, GPSS

Combinadas:

- SIMSCRIPT e GASP

- Permitem simulações discretas, contínuas ou combinadas.

LINGUAGEM DE SIMULAÇÃO GPSS

A primeira versão do GPSS (General Purpose Simulation System) foi lançada em 1961 pela IBM. E por ser a principal linguagem de simulação da IBM, a empresa desenvolveu um grande número de aplicações nestes mais de 50 anos de existência do GPSS. Inicialmente, a ideia de projetar o GPSS foi a de inventar uma ferramenta que pudesse ser usada por não especialistas, o que acabou por motivar a representação gráfica dos modelos.

Assim, um modelo GPSS é um diagrama de blocos, por onde fluem transações, que são as entidades temporárias do sistema. Atualmente, as versões disponíveis mais conhecidas são GPPS/H, GPSS World e WebGPSS. Além disso, diversas ferramentas de simulação, como a linguagem ARENA, foram fortemente influenciadas pelo GPSS.

Blocos GPSS

Na linguagem GPSS, um modelo é descrito através de um diagrama de blocos. Funciona da seguinte forma: existe um conjunto de blocos à disposição do programador, os quais podem ser interconectados para representar um sistema. A figura abaixo mostra os desenhos dos principais blocos no ambiente WebGPSS.

Figura 2: Principais Blocos do GPSS.

           O bloco GENERATE é usado para gerar transações (Exemplos: pessoa em um supermercado, navio em um porto, mensagem em uma rede, etc.). Essas transações são as entidades temporárias do modelo e fluem pelo sistema, passando de bloco em bloco. Quando uma transação entra num bloco, a ação correspondente ao bloco é executada. Lembrando que, cada tipo de bloco exerce uma função específica sobre as entidades do modelo. Ressalta-se ainda, que:

- A maioria das entidades de um modelo não precisa ser declarada;

- As informações de saída são geradas automaticamente;

- Cada transação possui um conjunto de atributos, que podem ser testados e alterados durante a vida da transação;

- Quando uma transação entra num bloco, os seus atributos podem ser usados para moldar a ação a ser executada pelo bloco;

- Um mesmo bloco pode reter diversas transações;

- Cópias de uma transação podem ser geradas pelo bloco SPLIT;

- Uma transação é removida do sistema quando entra num bloco TERMINATE;

- O bloco TERMINATE possui um operando que é usado para decrementar o contador de FIM_DE_SIMULAÇÃO, assim quando o contador atinge zero, a simulação termina (o valor inicial do contador é estabelecido no comando START, responsável por colocar o modelo em funcionamento);

- No final da execução do modelo, os resultados da simulação são mostrados automaticamente.

Principais Entidades do GPSS

Entidades básicas

- Blocos (que formam o diagrama)

- Transações (que fluem pelo diagrama)

Equipamentos

- Recursos ou “facilidades” (facilities)

- Depósitos (storages)

- Chaves lógicas (logical switches)

Tipos de Blocos

- GENERATE e TERMINATE: Criar e destruir transações.

- ASSIGN: Alterar parâmetros de transações.

- TEST e TRANSFER: Desviar o fluxo de transações.

- ADVANCE: Fazer uma transação esperar por um período de tempo.

- SEIZE/RELEASE: Requisitar/liberar recurso.

- ENTER/LEAVE: Requisitar/liberar um depósito.

- QUEUE, TABULATE: Coletar estatísticas.

- SPLIT: Duplicar transações.

- LINK: Encadear transações à filas.

EXEMPLO DE APLICAÇÃO DA LINGUAGEM DE PROGRAMAÇÃO GPSS

Barbearia em GPSS

Empreendimento: Barbearia do João com 3 cadeiras na sala de espera

CAD          STORAGE                                  3         ; 3 cadeiras na sala de estar

                  GENERATE                           10,2

                  TEST LE                             S$CAD,2,DESISTE

                   ENTER                              CAD,1

                   SEIZE                                 BARB

                   LEAVE                              CAD,1

                  ADVANCE                            12,2

                   RELEASE                          BARB

                   DESISTE TERMINATE            1

Resultado da Simulação

Figura 3: Resultado da Simulação usando o GPSS.

OBSERVAÇÃO:

Cadeias do GPSS

- Cadeia dos Eventos Correntes (Current Event Chain – CEC): contém as transações a serem movimentadas no tempo atual;

- Cadeia dos Eventos Futuros (Future Event Chain – FEC): contém as transações a serem movimentadas no tempo futuro (ordenadas pelo tempo em que devem ser movimentadas).

REFERÊNCIAS

Disponível em: <http://www.inf.ufsc.br/~guiga/ine5101/LivroPF/Cap%201.pdf> Acesso em: 01/06/2014.

Disponível em: <http://paginas.fe.up.pt/~feliz/newSim_cap11_PI.pdf> Acesso em: 02/06/2014.

Disponível em: <http://simulacaoemodelacaocomputacional.blogspot.com.br/2007/10/tipos-de-simuladores.html> Acesso em: 02/06/2014.

Disponível em: < http://www.scielo.br/pdf/prod/v9n1/v9n1a02> Acesso em: 03/06/2014.

SISTEMAS ESPECIALISTAS

Definição de Sistema Especialista (SE)

            Um sistema especialista ou Expert System é um sistema computacional que simula a estratégia de resolução de problemas de um ser humano em alguma área do conhecimento bem específica. No entanto, um SE não possuiu a capacidade cognitiva de um especialista humano, porém, na ausência deste torna-se uma ferramenta importante para resolução de problemas.

Figura 1: Sistemas Especialistas dentro da IA (Inteligência Artificial).

Um SE, normalmente, desempenha as atividades de Interpretação, Predição, Diagnóstico, Síntese, Planejamento, Monitoramento, Correção de falhas, Instrução e Controle.

Utilização de Sistemas Especialistas

Na maioria das vezes, os SE são empregados em situações nas quais o ser humano não está disponível. Contudo, em alguns casos, a interação entre o especialista humano e os SE é benéfica. Exemplificando:

- Em situações de "stress", pois a capacidade de resolução de problemas dos seres humanos diminui consideravelmente. Exemplo: operadores de processo diante de alarmes.

- Em situações nas quais a velocidade de resolução de problemas é uma exigência. Exemplo: monitoramento em tempo real.

- Em situações em que a padronização das ações tomadas por diferentes profissionais é essencial. Exemplo: operadores de processo de diferentes turnos atuam de forma diferenciada diante de uma mesma situação, o que poderá acarretar variações no produto final.

Deficiências de um SE

- A capacidade de aprendizagem é natural para o ser humano, porém, limitada para a máquina.

- O ser humano é criativo diante das variadas situações, porém, a criatividade é outro ponto fraco da máquina.

- O ramo de atuação é abrangente para o ser humano, mas pequeno para a máquina.

- A capacidade de interação do ser humano com o mundo exterior é elevada por causa de sua percepção aguçada, contudo, para a máquina essa capacidade é limitada.

Principais Vantagens de um SE

- Atuação consistente, independente de fatores circunstanciais;

- Total disponibilidade;

- Ausência de fadiga;

- Ausência de incompatibilidades pessoais;

- Facilidade de transferência e replicação;

- Velocidade na determinação dos problemas;

- Exige pequeno número de pessoas para interagir com o sistema;

- Estabilidade;

- Integração de ferramentas.

Classificação dos Sistemas Especialistas

Os atributos mais importantes para a classificação dos Sistemas Especialistas são:

- Forma de representação do conhecimento: os SE são denominados baseados em regras, orientados a objetos, etc.

- Operação da máquina de inferência: os SE podem ser orientados por dados, objetivos ou ambos. Neste último caso, quando as duas estratégias de inferência forem empregadas.

- Interface com o usuário: destacam-se neste atributo os recursos que o SE dispõe para interagir com o usuário. Exemplo: recursos gráficos, sonoros, etc.

- Operação on-line ou off-line: ressalta se o SE atua ou não em tempo real e ligado a um sistema físico.

- Capacidade de extensão: enfatiza-se a capacidade de ampliação ou adaptação do conhecimento do sistema às necessidades das pessoas.

Componentes de um SE

Um SE é composto, essencialmente, por uma Base de Conhecimento, composta de fatos e regras, comportando o conhecimento adquirido do especialista humano; Mecanismo de Inferência, que controla o processo dedutivo da base de conhecimento; e Interface com o Usuário.

As bases de conhecimentos compreendem os objetos e os atributos. Os objetos são as conclusões a que o Sistema deve chegar, enquanto que, atributos são as propriedades que servem para caracterizar os objetos. Por exemplo, em um SE específico de diagnóstico de doenças, os objetos são as doenças e os atributos desses objetos são seus respectivos sintomas. Assim, a resposta do sistema será o diagnóstico da doença a partir dos sintomas.

Os mecanismos de inferência podem ser divididos em dois tipos: Encadeamento para diante e Encadeamento para traz. No primeiro caso, selecionam-se atributos até obter uma combinação que caracterize um objeto. Enquanto que, no segundo, é escolhido um objeto para ser a hipótese de estudo, em seguida, busca-se determinar a viabilidade da aceitação dessa hipótese pela ocorrência ou não dos atributos adequados. Logo, trata-se de um método de tentativas e erros, onde prosseguisse até que encontrar a hipótese correta.

Um SE poderá apresentar outros componentes, dependendo do software de suporte empregado em seu desenvolvimento. Veja abaixo:

- Editores dedicados: acompanham o processo de inferência minuciosamente, visando corrigir falhas no desempenho do sistema.

- Editores gráficos: suportam a implementação de recursos gráficos, que aumentam a capacidade interativa do SE.

- Interfaces para outros sistemas de informação: suportam o acesso do SE a informação armazenada na base de dados, planilhas eletrônicas, etc.

- Módulo de explicação: fornecem a sequência de heurística empregada para obter certa conclusão.

Implementação de um SE

A implementação restringisse, basicamente, à implementação das estratégias de resolução de problemas utilizada pelos especialistas humanos em um domínio do conhecimento. Assim, a fonte do conhecimento é o próprio especialista do domínio, além de textos, manuais etc. Na verdade, uma das tarefas mais difíceis, na implantação de um SE, é justamente sistematizar o procedimento de resolução de problemas do especialista humano. Logo, uma das principais dificuldades é a análise subjetiva baseada na percepção humana, extremamente complicada de ser reproduzida em computador.

Exemplos de SE

Exemplos clássicos de SE:

- MYCIN – usado para diagnosticar doenças infecciosas.

- PROSPECTOR – utilizado para coletar informações geológicas.

- LOGIC THEORIST – trata-se de SE empregado para provar teoremas.

Exemplos de SE em microcomputadores:

- Diversas ferramentas do tipo "shell" permitem o desenvolvimento de SE em microcomputadores. Exemplo: EXPERT-EASE, M-1, INSIGHT, ARBORIST, EXSYS, ES/P, PERSONAL CONSULTANT, GURU, NEXPERT e outras.

- É possível utilizar outras linguagens de programação, além das "shells", como BASIC, FORTRAN, ALGOL, PASCAL, FORTH e outras. Além disso, há linguagens de programação que foram criadas para facilitar o desenvolvimento de aplicações de IA, tais como LISP, PROLOG e LOGO.

NOTA: “Shell” é uma linguagem de script usada em vários operacionais, com diferentes dialetos, e que depende do interpretador de comandos utilizado. Um exemplo de interpretador é o bash, usado na maioria das distribuições GNU/Linux.

REFERÊNCIAS

  

Disponível em: <http://www.dee.ufma.br/~lpaucar/teaching/ia2000-1/cap4.html> Acesso em: 27/05/2014.

Disponível em: <http://www.din.uem.br/ia/especialistas/basese.html> Acesso em: 27/05/2014.

                                                                                                                    

Disponível em: <www.ic.uff.br/~ferraz/IA/Ppt/SistemasEspecialistas/Expert01.ppt> Acesso em: 29/05/2014.

TEORIA DAS FILAS

A Teoria das Filas tem o objetivo de avaliar o comportamento de um sistema de filas e seus parâmetros, como:

ü  Tempo de espera médio;

ü  Probabilidade de formação de fila;

ü  Porcentagem de clientes rejeitados pelo sistema;

ü  Probabilidade de um cliente esperar mais do que o tempo estimado;

ü  Número médio de clientes na fila;

ü  Probabilidade de que todos os servidores estejam ociosos.

DESCRIÇÃO DE UM SISTEMA DE FILAS

A teoria das filas é uma aplicação do processo estocástico de tempo contínuo chamado também de Processo de Markov.

A figura abaixo mostra os componentes básicos de um sistema de filas. Os clientes potenciais e atuais são representados por círculos pequenos e podem ser pessoas, máquinas, partes ou qualquer outro ente. Os atendentes são representados por quadrados e podem ser qualquer tipo de fonte, tais como, pessoas, máquinas, oficina de reparos, que executam uma função.

Figura 1: Componentes básicos de um sistema de filas.

Fonte: www.paulonacaratti.eti.br

Os clientes que chegam ao sistema entram em atendimento imediatamente se algum dos atendentes está ocioso. Se todos os atendentes estão ocupados, o cliente espera na fila até que um atendente esteja livre. Depois de um período finito de tempo, o cliente sai do sistema. Os detalhes do processo dependem dos valores dos parâmetros e suposições adotadas pelos componentes do sistema.

A fonte de input, também conhecida como população de chamada, é um grupo de clientes potenciais que podem precisar dos serviços oferecidos pelo sistema. A fonte de input está caracterizada por seu tamanho N, que geralmente é assumido infinito por motivos de modelagem e a distribuição de probabilidade, descrevendo os tempos de chegada.

A fila de espera é o número de clientes esperando ser atendidos, e podem estar concentrados num lugar fixo como num banco ou podem estar distribuídos no tempo e espaço como aviões preparados para aterrissar. A disciplina da fila de espera define as regras pelas quais os clientes são selecionados para atendimento.

O mecanismo de atendimento é o processo pelo qual os clientes são atendidos. A suposição geral é que o atendimento é providenciado por um ou mais atendentes idênticos operando em paralelo. No caso de ter uma rede de filas de espera, várias configurações serão consideradas. As características do atendimento são o número de atendentes S, e a distribuição de probabilidade do tempo de atendimento.

Um sistema de filas é a combinação das filas de espera e os atendentes. O número de clientes no sistema é a primeira medida para analisar o sistema de filas de espera. Seu número representa o estado do sistema.

Figura 2: Rede de Transição de Estados de um Sistema de Filas

Fonte: http://www.decom.fee.unicamp.br

Na figura acima, os estados estão representados por pequenos círculos com um número indicando a quantidade de clientes nesse estado. O estado zero é um estado vazio quando não existem clientes e todos os atendentes estão ociosos.

Vale ressaltar que Estado é o número total de clientes no sistema. Ou seja, o número de clientes na fila de espera mais o número de clientes que estão sendo atendidos.

Nos estados de 1 até n, todos os clientes estão sendo atendidos e ninguém está na fila de espera. Para estados maiores que n, todos os atendentes estão ocupados e alguns clientes estão na fila de espera. Os arcos ou setas representam eventos. Uma chegada denominada pela letra λ, causa ao sistema aumentar em um, enquanto que uma saída denominada por μ, é a causa do número no sistema decrescer em um.

Posto que ambos os tempos de chegada e atendimento sejam variáveis aleatórias, o estado do sistema é um processo estocástico. Para sistemas estáveis, existem probabilidades em estados estáveis do número de clientes no sistema.

A teoria das filas envolve fórmulas para calcular as probabilidades em estado estável de diferentes configurações do sistema de filas. A maioria delas requer que os tempos de chegada e os tempos de atendimento sejam governados pela distribuição exponencial de probabilidade. Resultados aproximados existem quando as distribuições não são exponenciais.

Dadas as probabilidades em estado estável, se calcula uma variedade de variáveis que interessam ao desenhista ou operador de um sistema de filas. Estas englobam o valor esperado do número de clientes no sistema, o valor esperado do tempo que um cliente fica no sistema, a eficiência dos atendentes etc. Os termos average são sinônimos com os termos estatísticos média ou valor esperado. O valor esperado de número e tempo também pode ser calculado para a fila de espera e para o atendimento.

Um sistema de filas é descrito basicamente por três características: Processo de chegada; Disciplina da fila: SIRO (atendimento em ordem randômica), FCFS (o primeiro a chegar é o primeiro a ser atendido), LCFS (o último a chegar é o primeiro a ser atendido pelo servidor) etc.; e Processo de atendimento.

FILA M/M/1

Fila M/M/1 é um modelo amplamente usado devido a suas distribuições de probabilidades que descrevem o processo de entrada e o processo de serviço de uma forma matemática simples.

Oferece um modelo mais realístico para sistemas de fila reais, pois os padrões de chegada de cliente em sistemas reais seguem uma distribuição de probabilidade de Poisson. Assim, as mensagens chegam com distribuição de Poisson, entram em um buffer infinito com uma distribuição de tempo de serviço exponencial e são manipuladas por um servidor na base primeiro a chegar primeiro a ser servido (FCFS – First Come First Served). Observe o esquema abaixo:

Figura 3: Esquema de uma fila M/M/1

Fonte: http://www.decom.fee.unicamp.br

As mensagens (jobs) que chegam ao buffer são armazenadas em fila e esperam pelo serviço de um único elemento de processamento (servidor único). As mensagens que chegam ao buffer podem vir de um grupo de fontes que são diretamente conectadas ao nó (fila de mensagens) ou elas podem vir de uma linha externa que é conectada a outro nó.

A fonte de mensagem pode ser finita ou infinita. Um sistema de fontes finitas não pode ter uma fila de serviço arbitrariamente longa, mas quanto maior for o número de fontes de mensagens maior será a taxa de chegada de mensagem. E em um sistema de fontes infinitas, o comprimento da fila de serviço é ilimitado, e a taxa de chegada de mensagem não é afetada pelo número de fontes.

Mensagens chegam no buffer a uma taxa de λ mensagens/segundo e possuem um comprimento de X unidades de dados (bits, bytes, caracteres, etc.). Assume-se que todas as mensagens possuem mesmo comprimento L. Além disso, funções em um nó são caracterizadas pela taxa de serviço e pela disciplina da fila.

Taxa de serviço = número de jobs deixando o nó por unidade de tempo de serviço. Taxa de serviço pode ser dependente da carga, isto é, pode depender do comprimento da fila.

Disciplina da fila = regra utilizada para determinar a ordem na qual os jobs enfileirados recebem o serviço.

Exemplo: fila de bancos, supermercados, etc.

Se uma mensagem chega e existem n mensagens a sua frente no buffer, então o tempo total T para processar essa mensagem consiste no tempo w gasto esperando na fila mais o tempo de processamento s:

Onde:

T: Tempo total de espera ou tempo de atraso.

μ = C/L: Taxa de serviço (mensagens/segundo).

Figura 4: Modelo de uma fila de servidor único.

Fonte: http://www.decom.fee.unicamp.br

REFERÊNCIAS

Disponível em: <www.paulonacaratti.eti.br/aluno/EPR/PO2_Notas_Aula.doc> Acesso em: 20/04/2014.

Disponível em: <www.uece.br/mpcomp/index.php/arquivos/doc.../175-dissertacao-16‎.pdf> Acesso em: 20/04/2014.

Disponível em: <www.lee.eng.uerj.br/~gil/filas/Filas.pdf> Acesso em: 20/04/2014.

Disponível em: <http://www.decom.fee.unicamp.br/~baldini/IE509/ParteIII.pdf> Acesso em: 22/04/2014.