Módulo Complementar III - Exercícios

Prévia do material em texto

29/03/2015 online.unip.br/imprimir/imprimirconteudo
http://online.unip.br/imprimir/imprimirconteudo 1/4
 Exercícios Extra
Exercício 1:
Com base no algoritmo:
 
 
            função BUSCA­POR­APROFUNDAMENTO­ ITERATIVO (problema)retorna
uma solução ou falha
                  entradas:  problema, um problema
                  para profundidade  0 até  faça
                                                resultado  BUSCA­EM­PROFUNDIDADE­LIMITADA(problema,
profundidade)
                        função  BPL­RECURSIVA(nó,problema,limite)retorna  uma  solução  ou
falha/corte
                  se resultado  corte  então retornar resultado
 
 Assinale a alternativa que contenha a afirmação ERRADA:
 
A ­ Trata­se de um   algoritmo de busca de aprofundamento iterativo. Este algoritmo consiste na
combinação dos benefícios da busca em profundidade com a busca em extensão. 
B ­ A execução deste algoritmo é realizada por níveis de verificação. Ele aumenta gradualmente o limite
de profundidade para cada nível de verificação até encontrar o nó­objetivo. Para cada nível o algoritmo é
re­inicializado. 
C ­ Apesar dos estados serem gerados várias vezes, este fator não implica na geração de um custo
computacional muito alto, pois,   em uma árvore com o mesmo fator de ramificação em cada nível, a
maior parte dos nós estão nos níveis inferiores. 
D ­ Em geral, o aprofundamento iterativo é o método de busca sem informação preferido quando existe
um espaço de busca grande e a profundidade da solução não é conhecida . 
E ­ A aplicação do algoritmo de busca de aprofundamento iterativo é uma combinação de busca em
profundidade com a de busca uniforme que resulta em um algoritmo ótimo e completo com uma
complexidade de tempo e espaço exponenciais. 
Comentários:
Essa disciplina não é ED ou você não fez comentários
Exercício 2:
A função de avaliação em um algoritmo deve ser estabelecida com base:
A ­ Em nenhum critério relacionado ao tipo de algoritmo, ou seja, algoritmos de busca sem informação
podem utilizar esta função para uma avaliação final do custo de caminho resultante de sua aplicação. 
B ­ Deve expressar um critério para busca baseado no estado inicial e final da árvore de busca ou do grafo
29/03/2015 online.unip.br/imprimir/imprimirconteudo
http://online.unip.br/imprimir/imprimirconteudo 2/4
de busca. 
C ­ No custo do caminho do nó expandido, pois, expressa a distância percorrida do estado inicial até o nó
em verificação. 
D ­ Na ação à ser tomada a partir da expansão de um determinado nó. Esta função deverá ser decisiva na
busca pela solução ótima e com menor profundidade. 
E ­ Em uma estimativa da distância do nó expandido até o nó­objetivo. Certamente, uma função de
avaliação bem elaborada conduz um algoritmo de busca pela melhor escolha em uma marcha direta para
o nó­objetivo. 
Comentários:
Essa disciplina não é ED ou você não fez comentários
Exercício 3:
A função de avaliação em um algoritmo de busca gulosa consiste em:
A ­ Uma função heurística, h(n) que representa a menor distância em linha reta, h DLR , entre o nó e o
nó­objetivo . 
B ­ Uma função assintótica, denotada por h(n) , que representa o custo computacional mínimo para
execução do algoritmo. 
C ­ Uma função genérica que representa o custo do nó expandido adicionado o custo de cada passo para
se chegar ao nó­objetivo. 
D ­ Uma função exponencial que depende do número de expansões ocasionadas no algoritmo e do
número de ramificações de cada nó. Também é denotada de O( . ). 
E ­ Uma função que representa a distância entre dois estados diferentes do espaço de estado. Sua
eficiência na busca pela melhor escolha é duvidosa devido a possibilidade de existirem diversos caminhos
que podem levar ao nó­objetivo. 
Comentários:
Essa disciplina não é ED ou você não fez comentários
Exercício 4:
Uma heurística h(n) é dita admissível se, e somente se:
A ­ Possui um comportamento exponencial em relação ao custo de caminho; 
B ­ Calcula a soma de todos os custos de passo para chegar do nó em questão ao objetivo; 
C ­ Nunca superestime o custo para alcançar o objetivo. 
D ­ Nunca subestime o custo para alcançar o objetivo. 
E ­ Resulta sempre no custo ótimo para alcançar o objetivo. 
Comentários:
Essa disciplina não é ED ou você não fez comentários
Exercício 5:
Seja a árvore binária abaixo a representação de um espaço de estados para um problema p, em que o estado
inicial é a, e i e f são estados finais. Um algoritmo de busca em largura primeiro forneceria a seguinte sequencia de
estados como primeira alternativa a um caminho­solução para o problema p:
29/03/2015 online.unip.br/imprimir/imprimirconteudo
http://online.unip.br/imprimir/imprimirconteudo 3/4
 
A ­ a b d h e i 
B ­ a b c d e f 
C ­ a b e i 
D ­  a c f 
E ­ a b d e f 
Comentários:
Essa disciplina não é ED ou você não fez comentários
Exercício 6:
Considere as afirmações sobre resolução de problemas em IA.
I. Busca pela melhor escolha é um tipo de busca heurística .
II. Satisfação de restrições é uma das formas de solução de problemas em IA.
III. O procedimento Alfa­Beta  pode permitir  a  poda de boa parte  de  uma árvore  de  busca em um  jogo de dois
jogadores.
São corretas:
A ­ Apenas II 
B ­ Apenas I e II 
C ­ Apenas I e III 
D ­ Apenas II e III 
E ­ I, II e III 
Comentários:
Essa disciplina não é ED ou você não fez comentários
Exercício 7:
Considere h(x) como uma função heurística que define a distância de x até a meta; considere ainda hr(x) como a
distancia real de x até a meta. h(x) é dita admissível  se e somente se:
29/03/2015 online.unip.br/imprimir/imprimirconteudo
http://online.unip.br/imprimir/imprimirconteudo 4/4
A ­ $ n h ( n ) £ h r (x ) 
B ­ " n h ( n ) £ h r (x ) 
C ­ " n h ( n ) > h r (x ) 
D ­ $ n h ( n ) > h r (x ) 
E ­ $ n h ( n ) < h r (x ) 
Comentários:
Essa disciplina não é ED ou você não fez comentários
Exercício 8:
Considerando que h(n) é o custo estimado do nó n até o objetivo, em relação a busca informada, pode­se afirmar
que:
A ­ a busca gulosa minimiza h ( n ). 
B ­ a busca A* minimiza h ( n ). 
C ­ a busca de custo uniforme minimiza h ( n ). 
D ­ (d) a busca gulosa minimiza h ( n ) somente se a heurística for admissível. 
E ­ a busca A* minimiza h ( n ) somente se a heurística for admissível. 
Comentários:
Essa disciplina não é ED ou você não fez comentários
Exercício 9:
 
Os  algoritmos  genéticos  são  técnicas  de  busca  de  Inteligência  Artificial  e  tiveram  um  amplo  impacto  sobre
problemas de otimização, como layout de circuitos e escalonamento de prestação de serviços.
Com relação à versão mais comum dessa técnica, considere as afirmativas a seguir.
I. O  funcionamento  dos  algoritmos  genéticos  começam  com um  conjunto  de  k  estados  gerados  aleatoriamente
chamado de população.
II.  Para  cada  par  selecionado,  é  escolhido  ao  acaso  um  ponto  de  crossover  dentre  as  posições  na  cadeia  do
indivíduo.
III. A função fitness de cada indivíduo deverá definir qual é o melhor ponto de crossoverdos pares selecionados.
IV. A  fase de mutação dos algoritmos genéticos é obrigatória  e  deve  seguir  uma ordem aleatória  para garantir
vantagens em seus resultados.
Assinale a alternativa correta.
 
A ­ Somente as afirmativas I e II são corretas. 
B ­ Somente as afirmativas I e IV são corretas. 
C ­ Somente as afirmativas III e IV são corretas. 
D ­ Somente as afirmativas I, II Somente as afirmativas II, III e IV são corretas.  e III são corretas. 
E ­ Somente a afirmativa I esta  correta. 
Comentários:
Essa disciplina não é ED ou você não fez comentários