Introducao a Teoria da Computacao - CI059 (2.sem/2022)
=============================================
Turma: BCC2

seg 13:30 
qua 13:30 

Provas: Primeira Prova:  19/dez/2022 (segunda)
        Segunda Prova:   15/fev/2023 (quarta)
        Exame Final:     27/fev/2023 (segunda)

Livro Texto: 
  - Introducao a Teoria de Automatos, Linguagens e Computacao
    John E. Hopcroft, Jeffrey D. Ullman, Rajeev Motwani
    Editora Campus, 2003
  - Notas de aula do Prof. Murilo:
  https://www.inf.ufpr.br/murilo/teoria/notes/itc-22-2.pdf  

Bibliografia adicional:
  - Languages and Machines: An Introduction to the Theory of Computer Science
    Second Edition
    Thomas Sudkamp
    Addison-Wesley, 1998

  - Elementos de Teoria da Computacao
      Harry F. Lewis, C. H. Papadimitriou
      2a Edicao, Editora Bookman

  - Wood, D., Theory of Computation, John Wiley & Sons, 1987

Aula 1:
=======

1) Introducao a disciplina,
   sistema de avaliacao, bibliografia
   3 grandes areas: linguagens formais, computabilidade, complexidade

Motivacao:
  - a teoria da ciencia da computacao comecou com as perguntas:
    1) COMO ?   (as linguagens sao definidas)
        - estudo de gramaticas de Noam Chomsky
    2) O QUE ?  (o que conseguimos computar? o que e' um algoritmo?)
        - o algoritmo deve ser completo, finito e deterministico
            completo: sempre produz um resultado
            finito: tem uma sequencia finita de instrucoes
            deterministico: sempre produz o mesmo resultado para a mesma
                            entrada
        - necessidade de um modelo formal e abstrato de computacao
        - Exemplo: funcoes recursivas, calculo lambda, maquinas RAM,
          maquinas de Turing (provado que sao todos equivalentes)
        - Hipotese de Church-Turing: um problema tem uma solucao
algoritmica se e somente se pode ser resolvido por um dos sistemas
computacionais mencionados acima
        ==> problemas com solucao computacional ou sem solucao computacional
          Exemplo de problemas sem solucao:
          1) determinar se um programa termina para todas as entradas
possiveis
          2) determinar se dois programas computam a mesma funcao

  - depois preocupou-se com a pergunta?
    3) QUANTO CUSTA?  (computar)
       ==> problemas trataveis ou intrataveis
          Ex: intrataveis (tem solucao com recursos ilimitados): 
         computar todas as possiveis jogadas de xadrez com 1000 movimentos