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!