Teoria da Computação

Teoria da Computação

1. O que é a computação?

   • Raciocinar passos lógicos e matemáticos
     • Seguir algoritmos com entradas e saídas
       • O que é um Algoritmo?
         • É uma coleção de instruções simples para realizar uma tarefa
       • máximo de divisores
         • números primos
   • O que é uma solução computável?
     • capaz de calcular, computar, orçar, etc
   • Existem problemas sem solução computacional?
     • mais problemas não computáveis que computáveis

2. Ciência da Computação

   • spin-off da matemática
     • a matemática era capaz de prover algoritmos para resolver problemas
       • Será que um dia haveria resposta para tudo?
   • conhecimento sistematizado da computação
     • Tendo origem milenar, tendo influência da Grécia, Babilônia, etc

3. Os Paradoxos Matemáticos e Bertrand Russel

   • Bertrand não gostava da possibilidade de existir paradoxos de conjuntos
     • o conjunto de todos os conjuntos que não possuam a si próprios como elementos
       • Não existe conjunto de todos os conjuntos, nem classe de todas as classes.
     • Principia Mathematica (1.910, 1.912, 1.913), visando reescrever toda a matemática do zero, apoiando-a em fundamentos sólidos.
       • Demorou 362 páginas para demonstrar que 1+1=2

4. O Programa de Hilbert

   • encontrar uma formalização para toda a matemática
     • Fosse completa: provada com verdadeiro e falso
     • Fosse consistente: nenhuma coisa que é verdadeira poderia ser falsa também
       • Kurt Godel
         • Nenhum sistema formar poderoso o suficiente pode ao mesmo tempo ser completo e consistente
     • procedimento de decisão para dizer se uma proposição pode ou não ser provada a partir dos axiomas do sistema.
       • axiomas
         • Verdade tida como óbvia
       • Alan Turing
         • Existem problemas que algoritmos são incapazes de resolver
         • Formalizou a definição de Algoritmo junto com Alonzo Church
           • Máquina de Turing - 1936
           • Modelo de computação
             • fundamentação teórica para o desenvolvimento do computador como se conhece hoje
     • SPOILER: O PROGRAMA FALHOU

5. Linguagem

   • Trata de uma forma precisa de expressar problemas
     • Linguagem é um dos conceitos mais fundamentais em computação
   • Alfabeto
     • conjunto finito de símbolos ou caracteres
       • Teoria da Informação
         • Computação e expressão de códigos
   • linguagem de programação é o conjunto de todos os símbolos usados na construção de programas

Imagens e arquivos do mapa