RUI CUNHAMSIAD 2007/08 - ISCTE

A Complexidade nos Sistemas

O que é um sistema Complexo?

Costumamos dizer que algo é complexo quando estamos perante uma grande quantidade de componentes e de interacções entre eles. A complexidade existe em diversos quadrantes: social, biológico, fisico, cientifico.

Caracteristicas de um sistema complexo

Tipos de Aproximações à Complexidade dos Sistemas

Mecanismos de redução da complexidade

Teoria Computacional ≠ Teoria da Complexidade Computacional

Teoria Computacional

Quais os problemas de decisão para os quais existem algoritmos

Teoria da Complexidade Computacional

Quais os problemas de decisão para os quais existem algoritmos eficientes

A teoria da Complexidade e os seus conceitos

• O principal foco da teoria da complexidade está na manipulação da informação e na forma como esta é transformada apartir de uma representação (a que é dada) para outra representação (a que é pretendida).

Exemplo: a solução de um problema é meramente uma representação da informação que foi dada,ou seja, uma representação em que a resposta está explicita e não implicita.

Métricas de Complexidade

Tempo e Espaço

Ao número de instruções máquina que um programa executa durante o seu tempo de execução dá-se o nome de complexidade temporal.

Ao número de células de memória usada por um algoritmo dá-se o nome de complexidade espacial.

c*n2

Onde c é uma constante associada a factores externos (cpu,memória,algoritmo usado,etc) cujo valor pode sempre ser reduzido, ao invés de n2 que permanece inalterável.

O que significa que o c é uma variável pouco importante para o tempo de execução, o que significa que este tipo de complexidade é especifica numa notação-O

O(n2). (O é o chamado simbolo de Landau)

O(n2) corresponde a um conjunto de funções que não crescem mais rápidamente no tempo que a função n2, ou seja, todas as funções que têm como n2 o seu limite superior.

Classes de Complexidade

• Exemplos

• TEMPO ( n ) existe um algoritmo que, para um input de comprimento n , executa n passos.

• TEMPO ( n^2 ) existe um algoritmo que, para um input de comprimento n , executa n^2 passos.

• TEMPO ( 2^n ) existe um algoritmo que, para um input de comprimento n , executa 2^n passos.

Alguns exemplos de sistemas complexos

Caracteristica / Ramo Financeiro Ambiente Saude

Agente Investidores Animais Médicos,Enfermeiros

Heterogeneidade Informação sobre o riscoHabitos

alimentares,acasalamentoHealth status risk behavior

Organização Mercados Financeiros Migração, Cadeia Alimentar Unidades de Saude

Adaptação Aprendizagem Caça, Acasalamento Estratégias de Seguro

Feedback Sucesso ou Insucesso Sucesso ou InsucessoComportamento vs Cuidados

Saude

Dinamica Alterações do preço das acçõesCompetição no grupo

Interacção Predador-PresaEntrar /Abandonar Unidade

Saude

Comportamento Movimentos do Mercado Extinção , NichosSucesso ou Insucesso da

Unidade de Saude

Integração de Sistemas

Integrar ≠ Juntar tudoPara cada componente do sistema há que garantir:

O seu papel individual O seu contributo para o exterior A forma como se relaciona com os

demais componentes

O corpo humano é um exemplo de um sistema integrado!