t3

Terceiro Trabalho de Inteligência Artificial / Sistemas Inteligentes

Entrega: 29/04/2016

5 de Abril de 2016

Assuma que lhe foi pedido para fazer um programa para planeamento de viagens. O programa é muito simples, mas deve ser capaz de responder questões do tipo:
- Em que dias da semana há um vôo direto de Londres para Ljubljana?
- Como posso chegar de Ljubljana a Edinburgh na quinta-feira?
- Tenho que visitar Milão, Ljubljana e Zurique, começando meu vôo a partir de Londres na terça-feira e retornando para Londres na sexta-feira. Em que seqüência devo visitar estas cidades de forma que eu não tenha mais que um vôo por dia?
O programa deve estar baseado no banco de dados com informações de vôos (ver Figura 1), onde timetable(Place1,PLace2,List_of_flights) representa a informação sobre cada vôo com Place1 sendo origem, Place2, destino, e List_of_flights, uma lista contendo informações sobre cada vôo, estruturada da seguinte forma: hora de saída/hora de chegada/número do vôo/lista de dias.

Figure 1: Base de dados de vôos
$\begin{figure}\hrulefill \begin{center} \begin{verbatim}timetable(edinburgh,lo... ... [ 7:55/8:45/sr620/alldays]).\end{verbatim} \end{center}\hrulefill \end{figure}$

Seu primeiro problema é encontrar rotas entre duas cidades num determinado dia da semana. A rota pode ser programada como: route(Place1,Place2,Day,Route), que satisfaz os seguintes critérios:
- o ponto de partida da rota é Place1;
- o ponto de chegada da rota é Place2;
- todos os vôos devem estar agendados para o mesmo dia da semana (Day);
- todos os vôos em Route devem estar na relação timetable;
- deve haver tempo suficiente para transferência entre vôos.
A rota deve estar estruturada numa lista da seguinte forma: From-To:número do vôo:Tempo de partida.
Você pode precisar também dos seguintes predicados auxiliares:
- flight(Place1,PLace2,Day,Flight_num,Dep_time,Arr_time) que diz que existe um vôo entre Place1 e Place2 no dia da semana Day com tempos de chegada e partida.
- deptime(Route,Time), tempo de partida de Route é Time.
- transfer(Time1,Time2), há uma diferença de pelo menos 40 minutos entre Time1 e Time2 suficiente para fazer a transferência de um vôo para outro.
Escreva um programa em Prolog, utilizando a informação dada, que responda aos três tipos de perguntas apresentados acima. A terceira pergunta poderá ser escrita como uma combinação de chamadas ao predicado route/4.
Escreva o mesmo programa utilizando uma linguagem (imperativa/procedural) da sua escolha.
Escreva um programa em Prolog, utilizando DCG (Definite Clause Grammar), que faça análise de frases em português. Uma parte de uma gramática para o português é dada na Figura 2, onde a primeira sentença fala sobre a estrutura de frases no singular e a segunda fala sobre a estrutura de frases no plural. Esta sintaxe é aceita por Prolog! (consultar ``Definite Clause Grammars'' - DCGs em qualquer livro sobre Prolog). Uma sentença é composta por uma frase nominal seguida por uma frase verbal. Parte das regras que definem uma frase nominal estão representadas pela cláusula frase_nom.
Defina o restante da gramática (frases verbais, complementos) e um dicionário de palavras (verbos, nomes, adjetivos, etc) e utilize o conjunto de frases da Figura 2 para testar seu programa. Atenção aos apóstrofes que devem ser utilizados quando as palavras nas frases começam com letra maiúscula!

Figure 2: Subconjunto de estrutura da língua portuguesa
$\begin{figure}\hrulefill \begin{center} \begin{verbatim}sentenca --> frase_no... ...f. frase_nom_p --> subst_p_m.\end{verbatim} \end{center}\hrulefill \end{figure}$

Figure 3: Conjunto de frases para teste (ao alto, frases corretas; embaixo, frases incorretas)
$\begin{figure}\hrulefill \begin{center} \begin{verbatim}EXEMPLOS DE FRASES CO... ...O',sino,bateu,na,meninas],[]).\end{verbatim} \end{center}\hrulefill \end{figure}$

Faça uma pequena modificação no seu programa para que este retorne a estrutura gramatical das frases analisadas. Por exemplo, a consulta sentenca(X,['A',vida,corre],[]) deveria retornar na variável X o valor:
sent(frase_nom(artigo('A'),substantivo(vida)),frase_verbal(verbo(corre))).
Observe que a frase do conjunto de exemplos corretos ``O sino bateu na menina'' é sintaticamente correta, mas é semanticamente incorreta. Há técnicas para codificação de gramáticas com semântica associada, porém este tema está fora do escopo deste curso e deste trabalho.
Escreva o mesmo programa utilizando uma linguagem (imperativa/procedural) da sua escolha.

**Figure 1:** Base de dados de vôos
$\begin{figure}\hrulefill \begin{center} \begin{verbatim}timetable(edinburgh,lo... ... [ 7:55/8:45/sr620/alldays]).\end{verbatim} \end{center}\hrulefill \end{figure}$

**Figure 2:** Subconjunto de estrutura da língua portuguesa
$\begin{figure}\hrulefill \begin{center} \begin{verbatim}sentenca --> frase_no... ...f. frase_nom_p --> subst_p_m.\end{verbatim} \end{center}\hrulefill \end{figure}$

**Figure 3:** Conjunto de frases para teste (ao alto, frases corretas; embaixo, frases incorretas)
$\begin{figure}\hrulefill \begin{center} \begin{verbatim}EXEMPLOS DE FRASES CO... ...O',sino,bateu,na,meninas],[]).\end{verbatim} \end{center}\hrulefill \end{figure}$

Juntem-se em grupos de 2 elementos. Ambos devem participar nas duas implementações (imperativa e declarativa - Prolog) e discutir sobre facilidades/dificuldades de implementação de cada um dos paradigmas.

Entregar:

trabalho escrito com a descrição da implementação.
Organização do trabalho escrito:

Introdução (diferenças entre linguagens imperativas e declarativas, vantagens e desvantagens de representações utilizando os dois tipos de linguagens)

Descrição/Representação do problema em Prolog

Descrição/Representação do problema em outra linguagem

Comentários sobre representação do conhecimento e facilidades/dificuldades de implementação nas duas linguagens

Comentários Finais e Conclusões
enviar o código fonte dos programas, como compilar e formato da entrada para cada problema, isto é, um pequeno manual de como correr os programas (pode ser um 'help' ou 'readme'). Além disso, em que ambiente foi compilado (tipos e versões do SO e da linguagem). Seu programa deve correr na minha máquina (com fedora instalado). Não assuma que eu tenho uma IDE (Integrated Development Environment) de qualquer tipo. O programa deve correr na linha de comando.
A submissão será através do Moodle UP. Por favor, não inclua caracteres acentuados no nome do ficheiro de submissão.

Todos os trabalhos serão apresentados em data a combinar. Os dois componentes do grupo deverão estar presentes durante a apresentação. Quem nao estiver presente vai ter nota zero!

About this document ...

Next: About this document ...

Inês de Castro Dutra 2016-04-05