Seminário de Otimização Combinatória


      Alcançabilidade em Sistemas Híbridos e o 
   algoritmo de Chernikova para Programação Linear

           Guilherme Albuquerque Pinto

         Sexta-feira, 30 de agosto de 2002
              Sala 96 (IC2), 13:00hs

Sumário:

Um sistema híbrido, neste contexto, é um sistema dinâmico
qualquer com evolução contínua e discreta bem caracterizadas,
de forma que técnicas puramente discretas
(ex. máquinas de estados) ou puramente contínuas (ex. teoria
de controle) não geram bons modelos do sistema. Nos últimos
15 anos foram surgindo alguns formalismos híbridos, e também
ferramentas automáticas, que permitem, até certo ponto,
modelagem e verificação de propriedades para esse tipo de sistema.

Uma das ferramentas que têm obtido sucesso nessa área
é o HyTech (Hybrid Technology), da Univ. de Berkeley.

Esse seminário vai procurar dar uma idéia de como Teoria de
Poliedros é usada na solução do problema básico em verificação,
a alcançabilidade; e como um obscuro algoritmo para
programação linear acabou sendo usado como a primitiva
básica da ferramenta HyTech.