| |
|
Description: |
Existem problemas que não podem ser resolvidos por algoritmos e que se dizem, por isso mesmo, indecidíveis, mas muitos outros há para os quais é possível construir algoritmos para a sua resolução . No entanto, esses algoritmos possuem ``ordens de complexidade'' tão grandes que se dizem ser ``ineficientes''. O famoso Problema do Caixeiro Viajante encontra-se neste último caso, sendo classificado como NP-completo. Mas o que significa ``NP-completo''? E será que não é possivel encontrar um algoritmo ``eficiente'' para estes problemas? De facto, não basta identificar um problema e garantir que existe (pelo menos) uma solução para ele... cada vez mais se torna necessário saber se ele pode ser efectivamente resolvido em tempo e espaço de memória finitos.
Area(s):
|
|
Date: |
|
| Start Time: |
11:00 |
|
Speaker: |
Ana Maria de Almeida (Universidade de Coimbra, Portugal)
|
|
Place: |
Room 17A
|
| Research Groups: |
-Numerical Analysis and Optimization
|
|
See more:
|
<Main>
|
|
