Programação

  • Introdução



    Nesta primeira aula apresentaremos a estrutura do curso como um todo, livro texto, e a forma de avaliação. Faremos um breve histórico sobre o interesse geral da academia e de todo o resto da humanidade no conceito de inteligência e sua reprodução por máquinas e mecanismos. Introduziremos o conceito de agente inteligente, que é fundamental para a inteligência de máquina, seja embarcada ou distribuída em sistemas inteligentes. 

    O curso está dividido em uma parte teórica e uma parte prática. Gostaríamos de ter a capacidade de desenvolver pequenos programas inteligentes (lidaremos com software somente). A parte prática será trabalhada via este site, embora algumas das aulas "teóricas" tratarão de exercícios, exemplos práticos, e programas. Entretanto, não será possível inserir um curso de programação lógica em uma disciplina com dois créditos apenas. Portanto usaremos tutoriais e uma referência bibliográfica de apoio (Programming in Prolog, W. F Clocksin, C.S. Mellish, Springer, 2003). Um tutorial online para programação será usado (veja link abaixo).

    Para programação, uma versão online do SWI Prolog será usado (ver link abaixo). Com isso eliminaremos problemas de instalação, particularidades com sistemas operacionais, etc.

  • Resolução de problemas simples com regras



    Reunião no Dartmouth College para discutir a "inteligência Artificial".


    Nesta aula vamos começar a tratar da resolução de problemas de forma inteligente. A idéia é capacitar máquinas (computadores) para resolver problemas, uma capacidade normalmente associada a sistemas (humanos) inteligentes. Já vimos as limitações que esta inteligência de máquina pode ter, mas ainda assim, seria uma evolução tecnológica considerável ter sistemas capazes de fazer planos, aprender analizar padrões ou dar apoio à decisão. Ao invés de introduzir este tópico de maneira formal vamos abordá-lo (inicialmente) de forma simples com alguns problemas que podem ser tratados com "regras", agindo sobre uma base de fatos.

    Podemos sofisticar o nível de abstração destas regras (a distância para os "fatos") e também o número de regras tornando os programas mais complicados e mais "inteligentes".  Mas é ainda possível ver as limitações e também as possibilidades que surgem para aplicações, especialmente em automação. Aproveitamos para introduzir a linguagem Prolog e exercitar a sua aplicação no Swish SWI Prolog.

    Terminaremos propondo um avanço na forma de resolver problemas que nos aproxima ainda mais da modelagem estado-transição (ou dos "transition systems"). Novamente vamos entrar neste assunto de forma prática para colocar mais tarde a abordagem formal. A aplicação no momento seria um sistema automático para jogos.


    Cerca de 30% da emissão de passagens em companhias aéreas é feita usando Prolog.

    Uma matéria divulgada pela SICStus Prolog, que faz um ambiente de programação Prolog onde se pode produzir programas de interesse de mercado. Veja o link a abaixo...


     



  • Métodos e paradigmas para resolução de problemas



    Vamos agora avançar um pouco no entendimento dos tipos principais de problema e nos métodos para trata-los. A diferença entre um sistema algorítmico normal e um sistema inteligente está nos métodos de resolução de problemas e notadamente (no nível de abordagem deste curso) na capacidade de automatizar a resolução de problemas. Vamos portanto focar nos aspectos conceituais desta automação e nos algoritmos de apoio, o que começa com os algoritmos de busca. Veremos que a ligação entre os métodos de aplicação da inteligência artificial na engenharia (especialmente planning) e a base conceitual da IA começa pelos algoritmos de busca e especialmente de busca informada. Estes serão melhor explorados na aula que vem. 

    Devemos nos preparar para o primeiro trabalho em grupo, e portanto a turma deverá se dividir em grupos de quatro. Também colocaremos um novo chat para que todos possam colocar as dúvidas e também a formação dos grupos. Cada grupo deve propor um "problema" a ser resolvido com um programa inteligente baseado em regras e busca não informada. Faz parte do exercício a definição do problema e o discernimento sobre o que consiste de fato em uma aplicação prática da IA (aplicações simples, por favor!).

    •  Duvidas e formação dos grupos Chat
      Restrito Disponível se: Você faz parte de T-PMR3510-2018250
    •  Formação de grupos para o primeiro trabalho Fórum
      Restrito Disponível se: Você faz parte de T-PMR3510-2018250
  • Resolução de problemas por humanos e por máquinas




    Vamos retornar à nossa discussão sobre resolução de problemas, agora considerando a diferença entre a resolução de problemas por humanos e por máquinas. Aproveitaremos então para introduzir os sistemas baseados em regras, e os sistemas especialistas agora avançando na discussão sobre os métodos básicos de inferência. Um sistema especialista é composto por três elementos básicos: a interface com o usuário, a base de conhecimento e a máquina de inferência. A primeira não será objeto deste curso, embora seja muito importante e às vezes crucial para o sucesso comercial de várias aplicações de IA, como mostraremos na aula. A segunda é justamente o objeto da discussão na aula de hoje. A terceira, será parcialmente delegada para a máquina prolog e para a programação, e será discutida com mais detalhes mais adiante.

    Nas aulas seguintes discutiremos a representação de conhecimento, e em seguida os algoritmos de busca e busca informada. Em paralelo discutiremos as técnicas de programação em Prolog e a implementação do primeiro trabalho.

    Como leitura suplementar acrescentamos um artigo de Allen Newel e Herbert Simon sobre as diferenças entre "human problem solving and machine problem solving". Os que quiserem explorar mais este tema são fortemente aconselhados a ler este artigos. Mesmo para os demais o artigo é muito interessante e instigante e complementa com mais detalhes o tópico de discussão desta aula.


  • Resolução de problemas por máquinas: Algoritmos de busca




    Na aula passada discutimos conceitualmente as estratégias de resolução de problemas por humanos e máquinas, com o objetivo de fazer uma clara distinção entre os dois processos e deixar claro as limitações da máquina (no caso o computador no seu modelo von Neuman sequencial) para tratar de processos normalmente associados a humanos. A proposta de ter um método geral para resolução de qualquer problema (que discutiremos mais detalhadamente nas próximas aulas) está ligado a esta referência (humana) e é uma discussão antiga, como vimos no histórico das primeiras aulas.

    Partiremos do paradigma estado/transição para tratar do problema da resolução de problemas por máquinas, tomando como exemplo o exercício que foi dado para as equipes recentemente formadas. Discutiremos em primeiro lugar os algoritmos de busca não-informada e nas aulas seguintes os algoritmos de busca informado, o conceito de heurística e conhecimento tácito, muito importante para a elaboração de sistemas especialistas. Lembrando que estamos discutindo os conceitos clássicos da IA. 

    Apresentaremos algumas "boas práticas" no desenvolvimento de software para inteligencia artificial, novamente tomando como base o exercicio-programa. 

  • Introduzindo estruturas para os processos de busca





    Nesta aula vamos fazer um breve parêntese na discussão dos algoritmos de busca para inserir um tópico pertinente à implementação, que é a introdução de estruturas, como lista e árvore. Estas estruturas são implementadas de maneira mais direta nas linguagens procedurais, mas em Prolog, como em outras linguagens declarativas interpretadas (como Lisp, APL, etc.) as estruturas são a base para processos eficientes de chamada recursiva, como veremos nos exemplos.

    A razão para anteciparmos a discussão sobre implementação é municiar as equipes para o andamento do trabalho de grupo, deixando-os livres para pensar somente o núcleo inteligente do projeto e não nos aspectos periféricos que poderiam demandar habilidade de programação em Prolog, o que certamente não é o caso da maioria. Por outro lado manteremos estes procedimentos bem simples, mesmo sabendo que existem opções mais eficientes e/ou mais elegantes para implementar a mesma coisa. A prioridade é que seja mais fácil de entender o programa em caso de ser preciso fazer o "tracing" para debugar o código.

    Prosseguiremos depois com a discussão qualitativa dos métodos de busca já que sua implementação começará a ficar mais clara. 

    Nesta aula também faremos uma breve discussão sobre o cronograma de execução do trabalho em grupo. 

  • Algoritmos de busca informada



    Vamos a partir desta aula mudar o foco da discussão sobre os algoritmos de busca usados em IA da busca clássica não-informada para a busca informada, onde se pode usar heurísticas obtidas de conhecimento tácito ou explicito para orientar a escolha do caminho na árvore de busca. Esperamos portanto obter uma melhor performance, comparado aos métodos clássicos e assim justificar o uso de IA para problemas que têm um custo proibitivo por métodos convencionais, ou mesmo que não chegam a uma resposta, utilizando métodos otimizados. A barganha é portanto obter uma solução próxima do ótimo mas em um tempo aceitável.

    Começaremos a discussão pelo best-first, e aplicaremos este algoritmo para um exemplo já bem conhecido que o 8-Puzzle, ou o jogo dos tiles, que é o exercício em grupo que estamos considerando. Aproveito para lembrar que o milestone para este exercício, que seria hoje foi adiado de uma semana, em função de termos perdido a aula passada.

  • Tópico atual

    O Agoritmo A* e a busca informada




    Vamos agora introduzir o algoritmo de busca A* e suas propriedades. Temos já um bom resumo dos algoritmos de busca não-informada, contida no material da UVA disponibilizado no site depois da aula passada. Agora daremos um passo definitivo para ter um algoritmo de busca otimizante com performance exponencial. No entanto, dependendo do número de estados e da qualidade da heurística uma resposta (se existir) pode ser obtida em um tempo razoável, como veremos na resolução de alguns jogos. Vamos nos concentrar novamente no 8-Puzzle ou jogo dos tiles, para dar mais suporte ao trabalho em grupo. 

    Também apresentaremos os detalhes da competição já marcada para o dia 31 de outubro próximo.