Frequência de 99 - Universidade de Coimbra
Transcrição
Frequência de 99 - Universidade de Coimbra
UNIVERSIDADE DE COIMBRA FACULDADE DE CIÊNCIAS E TECNOLOGIA Departamento de Engenharia Informática Pólo II da Universidade, Pinhal de Marrocos 3030 Coimbra, Portugal Tel.: 790000 — Fax: 701266 PLANEAMENTO E ESCALONAMENTO ANO LECTIVO 1998/99 Exame de Recurso, 8/6/99 Duração: 2h (+ 15m de tolerância) 1ª Questão (12 valores) Asterix e Obelix têm que transportar um menir através de um tunel para o oferecerem a ZáZá. Obelix pode pegar num menir e transportá-lo. Asterix pode transportar um menir desde que antes beba poção mágica, mas para pegar nele precisa da ajuda do Obelix: como tem braços pequenos, precisa que o Obelix pegue no menir para lho pôr às costas. Túnel Como o túnel é estreito e baixo, Obelix não consegue passar por ele juntamente com o menir. Asterix, por ser mais pequeno, consegue. a) Escreva os operadores necessários à formalização deste domínio. Utilize para tal a sintaxe do Prodigy 1 Prova Escrita de Frequência de Planeamento e Escalonamento, 8/6/99 b) Diga, justificando, que tipo de extensões ao algoritmo POP básico deverá considerar para que seja possível resolver problemas com os operadores apresentados. c) Considerando os operadores da alínea a), mostre graficamente o plano parcial que um planeador construído com base no algoritmo POP com as extensões referidas na alínea b) gerará, considerando como estado inicial a situação descrita na figura, e como objectivos: Asterix junto a ZáZá; Obelix junto a ZáZá; menir junto a ZáZá, pousado no chão (ZáZá é frágil). d) Assinale uma situação em que o POP, durante a construção do plano parcial, detecte uma ameaça; explique de que forma o POP resolve essa ameaça. 2ª Questão (8 valores) Considere a lógica temporal de 1ª ordem (Thomas Dean) apresentada nas aulas, com o tempo representado por inteiros. Considere ainda que são conhecidos, para as proposições-fluentes A, B, C e D, e para as proposições-eventos E1 e E2, as seguintes fórmulas: holds(1, A) ∀ t [holds(t, A) ∧ holds(t, E1) ⇒ holds(t+1, B)] ∀ t [holds(t, ¬A) ∧ holds(t, E1) ⇒ holds(t+1, D)] ∀ t [holds(t, B) ∧ holds(t, E2) ⇒ holds(t+1, C)] Suponha que ocorre o evento E1 no tempo 2 e E2 no tempo 3. a) Descreva qual a interpretação mais preferida nos tempos 1, 2, 3 e 4, de entre as que resultam da aplicação da Lei da Inércia do Senso Comum. b) Descreva qual a interpretação menos preferida nos tempos 1, 2, 3 e 4, de entre as que resultam da aplicação da Lei da Inércia do Senso Comum. c) Considere agora que está a armazenar informação temporal numa base de dados recorrendo a tokens representados por fórmulas do tipo holds( α, ψ), onde α é um intervalo e ψ uma fórmula lógica. Escreva as regras causais correspondentes ao seguinte texto: Se ocorre E1 quando A é verdade, B passa a ser verdade; se ocorre E1 quando A é falso, D passa a ser verdade; se ocorre E2 quando B é verdade, C passa a ser verdade Escreva ainda o Mapa Temporal que se obtém utilizando Projecção e Persistence Clipping, sabendo que inicialmente se conhece holds((0-1), A), holds(2, E1) e holds(3, E2). 2