Lista 1

1. Defina Inteligncia. O que e um comportamento inteligente de uma maquina?

Resp: Inteligncia a capacidade de se deparar com um problema e puder ser capaz de resolv-lo, essa habilidade de criar uma soluo diante de uma situao denominamos inteligncia. Define-se por comportamento inteligente de uma mquina, a capacidade dela arcar com um determinado problema, e conseguir solucion-lo atravs da busca de uma da melhor ordem de estados possveis para encontrar a soluo.

2. Comente o surgimento da IA e as expectativas iniciais da rea. A Inteligncia Artificialresolveu todas as propostas iniciais da rea?

Resp: No final da dcada de 70, a ideia de inteligncia artificial teve grande destaque em seu principio com os feitos de Alan Turing na 2 Guerra Mundial , quando estava decifrando o cdigo dos alemes, resolveu ter a ideia de criar um computador que pudesse pensar.Inicialmente a expectativa de ter um computador que pudesse solucionar problemas era grandiosa, uma revoluo para o mundo moderno, entretanto a realidade diferente da teoria, era necessria uma quantidade muito grande de informaes para realizar condies muito simples que poderiam ser resolvidas manualmente por humanos com bem menos requisitos.Ento chegaram concluso que s seria vivel o uso dela para alguma especificao, no problemas comuns.Somente na dcada de 80-90, determinou-se a possibilidade de solues mais rpidas, finalmente foi possvel fazer o algoritmo ser capaz de ser ensinado para solucionar um problema.

3. Defina os seguintes termos: estado, espao de estados arvore de busca, no de busca,estado inicial, estado final, estado objetivo, ao, funo sucessor, fator de ramificao,comprimento da soluo.

Resp:Estado: a denominao de passos de dentro de um espao de busca.Espao de Arvore de Busca: uma representao do conjunto de possveis escolhas de um dado problema, uma ou mais das quais soluo do problema.Espao de Estados: Em cada passo so definidas escolhas para chegar aos demais estados, essas aes so definidas Espao de Estados.N de Busca: cada n representa um possvel caminho na buscaEstado Inicial: Representa o ponto inicial do problemaEstado Final: O ltimo estado do espao de busca, aps ele no tem mais alternativas.Estado Objetivo: O estado do resultado a se alcanar, o estado que satisfaz a meta.Ao: So as escolhas dos passos, respeitando as regras determinadas em um algoritmo.Funo Sucessora: Gera os estados vlidos que resultam da tentativa de executar as aes. So as regras que o sistema aceitar para serem aplicadas para passar de um estado para o prximo.Fator de ramificao: a diviso entre os caminhos de um estado.Comprimento da soluo: A distncia necessria para chegar ao estado objetivo.

4. Fornea o estado inicial, o estado objetivo, a funo sucessora e a funo de custo para cada um dos itens a seguir:

Resp:

a) Um macaco com um metro de altura esta em uma sala em que algumas bananasesto suspensas no teto, a 2,5 metros de altura. Ele gostaria de alcanar as bananas. A salacontem dois engradados empilhveis, moveis e escalveis, com um metro de altura cada.

b) Voc tem 3 jarros com capacidade para 12, 8 e 3 litros, respectivamente, e aindauma torneira de agua. E possvel encher os jarros ou esvazia-los passando agua de um paraoutro ou derramando no cho. Voc precisa medir exatamente um litro.

Resp:a) Estado inicial: Macaco e as bananas suspensa em 2,5 metros de altura.Estado objetivo: Alcanar as bananas Funo Sucessora: A escolha dos mveis, ou os engradados para subir neles.Funo de custo: Cada escolha de um objeto custa 1 passo.

b) Estado Inicial: 3 jarros de 12,8 e 3 litros vaziosEstado Objetivo: Conseguir medir exatamente 1 litro de um dos jarrosFuno Sucessora: Encher o balde 12 ou 8 ou 3, ou os trs baldes. Funo de Custo: Cada passo custa um espao, uma ao custa um espao.

a

5. Qual e a diferena entre uma busca informada e uma busca no informada?

Resp:

Uma busca informada refere-se a um espao de busca com uma informao que pode ou no auxiliar na busca do estado objetivo, tambm chamado Busca Heurstica.Uma busca no informada refere-se a uma busca sem nenhuma informao como auxlio, tambm chamado de Busca Cega, ir gerar todas as possibilidades possveis at chegar ao estado objetivo.

6. Como funcionam as buscas em profundidade e em largura? Descreva as vantagens edesvantagens de cada uma.

Resp:

Dentro de um tipo de Busca Cega, a busca em profundidade varre uma folha inteira e volta, ramo por ramo. A busca em Largura varre por nveis.Se a busca por caminhos longos ou infinitos, a busca em profundidade funciona mal, principalmente dependendo onde est o estado objetivo.Nesse caso o melhor fazer uma busca por nveis usando a busca por largura.Se a busca por comprimentos parecidos, tanto a busca por profundidade quanto a largura so igualmente eficientes. Entretanto a de largura pode causar um desperdcio maior de tempo e memria em seu consumo, a de profundidade no usa tanto quanto a de largura.

7. As buscas em profundidade e em largura so timas e completas? Explique a sua resposta.

Resp:

A Busca em profundidade no completa (ela pode encerrar antes de alcanar o seu objetivo), devido a seu mtodo de busca mantm na memria o caminho de todo os ns anteriores, afinal ela vai ter que retroceder (backtrack) aps a vasculha de um ramo. No recomendado utilizar ela para situaes em que h muitos ramos nas divises da soluo.

A Busca em largura completa, mas no considerada tima, ela varre todos os nveis em sua busca, tem um gasto bem maior de memria, ela garante a varredura de todos os nveis at o ltimo.

8. Quais os critrios de avaliao das estratgias de busca?

Resp: - Completude A certeza de se achar a soluo-Custo do Tempo- O gasto do tempo para se encontrar a soluo-Custo da memria Gasto necessrio para realizar a busca-Otimizao da Soluo- As estratgias para encontrar a melhor soluo

9. De um exemplo de problema em que a busca em largura funcionaria melhor do que abusca em profundidade. De um exemplo de problema em que a busca em profundidadefuncionaria melhor do que a busca em largura. Justifique os exemplos.

Resp:

A busca em profundidade gasta pouca memria e mais fcil de implementar. Dependendo do comprimento do caminho, se for de igual comprimento ou um problema menor, ela mais vantajosa que as demais.A busca por largura gasta mais memria e bem mais difcil de implementar. Se o caminho for longo e de infinitas possibilidades, a busca de profundidade funciona mal, nesse caso a busca de largura melhor, varrer os nveis causa uma amplitude melhor dependendo de onde o estado objetivo estiver.

10. O que e uma heurstica? E uma funo heurstica? Toda funo heurstica e admissvel?Apresente exemplos que ilustre esta questo.

Resp:Heuristica uma dica, um auxlio para a soluo de um problema.Funo Heurstica trabalhar uma busca com base em uma dica que pode ser ajudar ou no em um problema,elas estimam o caminho mais barato do estado atual at o estado final. Especficas para cada tipo de problemaNo, nem toda heurstica pode ser admissvel, no h 100% de chance de a dica dada para a busca possa ser confivel, h a possibilidade da heurstica no auxiliar e piorar a busca da funo heurstica.

11. Explique os algoritmos de busca gulosa e A*.

Busca Gulosa ela escolhe o caminho mais curto, ela analisa atravs de estimativas o caminho mais curto do estado inicial para o final, no releva a importncia do custo em seu trajeto

Busca A*- Procura o melhor caminho para a soluo, faz uma estimativa em todas as etapas de custo e o menor caminho a se seguir, entretando guarda na memria os respectivos caminhos porque pode ele pode retornar para testar todas as possibilidades encontradas. Ele garante o melhor resultado.

12. Considere o espao de busca a seguir. Cada n rotulado por uma letra. Cada no objetivo representado por um circulo duplo. Existe uma heurstica estimada para cada dado n (indicada por um valor ao lado do n). Arcos representam os operadores e seus custos associados.

Para cada um dos algoritmos a seguir, liste os nos visitados na ordem em que eles soexaminados, comeando pelo no A.

Algoritmo de Busca em Largura; Algoritmo de Busca em Profundidade; Algoritmo de Busca Gulosa; Algoritmo A*.

Largura: A-B-C-D-E-F-G-H-I-J-K Profundidade-A-B-D-E-H-I-C-F-G-J-K Gulosa: A-B-E-I-C-G-KA*: A-B-E-I-C-G-K

13. Para os algoritmos de busca cega e busca heurstica comente o custo de tempo e memoria.

Busca Cega - no releva o custo de tempo em sua tcnica, mas gasta pouca memria em relao a Heurstica, e mais fcil de implementarBusca Heurstica Utiliza e avalia estimativa de custo de um estado para outro(A*) e busca o menor caminho(Gulosa e A*), utilizada para encontrar a melhor soluo possvel(A*). Utiliza uma proporo boa da memria devido a armazenar os estados anteriores caso precise para analisar as estimativas dos demais estados, analisa para encontrar a melhor soluo.

14. Explique as tcnicas de busca heurstica de subida da encosta e tempera simulada.Subida da encosta Esse mtodo permite avaliar a condio de um estado para outro, sempre procurando o melhor estado para se estar, ele avalia os possveis caminhos a partir de seu estado, ao encontrar entre essas opes um melhor estado para se estar, ele avana para o prximo estado, mesmo que haja um melhor estado depois, se haver um pior entre eles, a busca no avana devido a ele ser pior que o que se encontra. Caractersticas: Seleciona o primeiro vizinho que seja melhor. Problema: tende a convergir para uma soluo que um mximo local e no para o mximo global. irrevogvel.

Tempera Simulada - Esse mtodo baseado no processo de mudana de estados fsicos da matria, inicia-se com uma temperatura elevada permitindo transies de elevados nveis de energia, mas depois de certo tempo, ela se resfria e s transies mais baixas so permitidas. O objetivo alcanar uma estrutura molecular com um mnimo de energia, mas existe a possibilidade de poder transitar a um estado de maior energia.

15. Com relao aos algoritmos genticos:a) Apresente, de forma simplificada, os passos seguidos por este modelo.b) O que representa um indivduo dentro de uma populao?c) Como os indivduos de uma populao podem ser selecionados e recombinados?d) Por que a taxa de mutao deve existir e apresentar sempre baixa probabilidade deocorrncia?

a) O Ciclo : Populao -> Codificao -> Seleo -> Cruzamento -> Mutao -> Populao...b) Um individuo significa em termos computacionais uma cadeia de bits (cromossomo) representados por nmeros binrios, podem ser um individuo bom ou ruim avaliado pelo teste de aptido dependendo do cdigo gentico, mais prximo de uma possvel soluo.c)Os indivduos atravs de um teste de aptido so avaliados para designar se ele bom ou ruim, ao definir a aptido de um indivduo com outro, nesse momento caso esses indivduos passam por um cruzamento entre eles, recombinando seus dados at criar um individuo melhor. uma tcnica empregada para gerar uma nova soluo, atravs do cruzamento de indivduos.d) Mutao uma modificao, a insero de um individuo novo que foi gerado de uma populao, o cruzamento gera um individuo melhor que os anteriores, a mutao pode causar uma mudana que no era possvel no cdigo gentico do individuo, podendo melhorar ou pior.Ele tem uma baixa probabilidade de ocorrncia devido a ser um operador unrio, ele aplicado em uma taxa de probabilidade de 0.01.

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------