Teoria da Computação

===========================================

E-mail para suporte: george.marra@unialfa.com.br 

GitHub

 https://github.com/GeorgeMendesMarra/GeorgeMendesMarra

===========================================

Teoria da Computação

📚 Apresentação da Disciplina

    A disciplina de Teoria da Computação apresenta os fundamentos matemáticos e conceituais que permitem compreender o que pode ser computado, como os problemas computacionais podem ser representados e quais são os limites da computação.

    O estudo parte da relação entre hardware, software, algoritmos e modelos abstratos de computação, avançando para conceitos fundamentais de computabilidade, Máquinas de Registradores, Máquina de Turing e Tese de Church-Turing.

    A disciplina também estabelece uma conexão entre a teoria e situações concretas da sociedade e da indústria de tecnologia, utilizando filmes, documentários e estudos de caso para discutir temas como criptoanálise, software livre, privacidade, vigilância, algoritmos e acesso ao conhecimento.

    Por fim, os conceitos são relacionados a tecnologias contemporâneas, incluindo criptografia, blockchain, criptomoedas e computação quântica, permitindo compreender como os fundamentos da computação teórica continuam presentes nas tecnologias atuais.

 

 🎯 Objetivos
 

Objetivo Geral

    Compreender os fundamentos da Teoria da Computação, seus modelos formais, seus conceitos de computabilidade e seus limites, relacionando-os à evolução histórica da computação e às tecnologias contemporâneas.

 

Objetivos Específicos

Ao final da disciplina, o estudante deverá ser capaz de:

* compreender a relação entre hardware, software, algoritmos e máquinas;
* compreender o conceito de computabilidade efetiva;
* diferenciar problemas computáveis e indecidíveis;
* compreender o funcionamento de modelos abstratos de computação;
* estudar Máquinas de Registradores;
* compreender a estrutura e o funcionamento da Máquina de Turing;
* compreender a importância da Tese de Church-Turing;
* identificar os limites teóricos da computação;
* relacionar computabilidade e algoritmos;
* analisar aplicações da computação teórica em criptografia;
* compreender conceitos computacionais presentes em blockchain;
* analisar os impactos da complexidade computacional;
* compreender os fundamentos conceituais da computação quântica;
* relacionar teoria, tecnologia, sociedade e ética.
 

 🧠 Eixo 1 — Fundamentos da Teoria da Computação

    O primeiro eixo estabelece os fundamentos necessários para compreender a computação como uma área científica.

1. Programas e Máquinas

Estudo da relação entre máquina física e programa, abordando:

* Hardware;
* Software;
* Instruções;
* Algoritmos;
* Processamento de dados;
* Arquitetura de computadores;
* Arquitetura de von Neumann;
* Memória;
* Processador;
* Execução de instruções.

O objetivo é compreender como um algoritmo pode ser transformado em uma sequência de instruções executáveis por uma máquina. 
 

2. Computabilidade Efetiva

    A computabilidade constitui um dos conceitos centrais da disciplina.

São estudadas questões fundamentais como:

> O que pode ser calculado por um computador?

E, principalmente:

> Existem problemas que nenhum computador pode resolver?

A partir dessas questões são introduzidos os conceitos de:

* Problemas computáveis;
* Problemas não computáveis;
* Problemas indecidíveis;
* Algoritmos;
* Funções computáveis;
* Limites da computação.

    O estudo permite compreender que determinados problemas não podem ser solucionados por um algoritmo, independentemente da quantidade de memória, velocidade ou poder de processamento disponível. 
 

 🤖 3. Modelos de Computação
 

Máquinas de Registradores

As Máquinas de Registradores constituem um modelo simplificado de computação baseado em:

* Registradores;
* Armazenamento de números;
* Operações aritméticas;
* Incremento e decremento;
* Desvios;
* Execução sequencial de instruções.

Esse modelo permite estudar a computação de maneira abstrata, eliminando características específicas de computadores reais.
 

 Máquina de Turing

A Máquina de Turing constitui um dos principais modelos matemáticos utilizados para formalizar o conceito de computação.

O modelo é composto fundamentalmente por:

* Uma fita potencialmente infinita;
* Uma cabeça de leitura e escrita;
* Um conjunto de estados;
* Um alfabeto;
* Uma função de transição.

A partir desses elementos é possível representar algoritmos e processos computacionais de forma matemática.

A Máquina de Turing é utilizada como referência para discutir o alcance e os limites da computação.
 

 📐 4. Tese de Church-Turing

A Tese de Church-Turing constitui um dos conceitos fundamentais da Teoria da Computação.

A ideia central é estabelecer que aquilo que pode ser considerado efetivamente computável pode ser representado por um modelo formal de computação como a Máquina de Turing.

O estudo dessa tese permite discutir:

* O conceito de algoritmo;
* Computabilidade;
* Modelos formais;
* Limites computacionais;
* Problemas indecidíveis;
* Relação entre diferentes modelos de computação.

    A tese é fundamental para compreender que a Teoria da Computação não trata apenas de computadores físicos, mas também da própria definição matemática do que significa calcular.
 

 🎬 Eixo 2 — Teoria da Computação através do Cinema

    A disciplina utiliza filmes e documentários como instrumentos de contextualização e análise crítica.

    A proposta é utilizar obras cinematográficas para aproximar conceitos abstratos da realidade histórica, tecnológica e social.

 🎥 Revolution OS

O documentário Revolution OS (2001) é utilizado para discutir:

* Software livre;
* Código-fonte;
* Linux;
* GNU;
* Open Source;
* Propriedade do software;
* Controle sobre o código;
* Desenvolvimento colaborativo.

    A análise permite relacionar o código-fonte à ideia de algoritmo e discutir a importância do acesso ao conhecimento tecnológico.
 

 🎥 Enigma e O Jogo da Imitação

    Os filmes Enigma (2001) e O Jogo da Imitação (2014) permitem contextualizar:

* Alan Turing;
* Criptoanálise;
* Máquina de Turing;
* Busca computacional;
* Força bruta;
* Espaço de estados;
* Criptografia;
* Segunda Guerra Mundial.

    A análise evidencia como problemas matemáticos e computacionais podem ser transformados em processos automatizados de busca e análise. 
 

 🎥 Swordfish — A Senha

    O filme Swordfish (2001) é utilizado para discutir conceitos relacionados a:

* Criptografia;
* Segurança computacional;
* Complexidade;
* Senhas;
* Chaves criptográficas;
* Espaço de busca;
* Tempo computacional.

    A obra serve como ponto de partida para discutir a diferença entre um problema teoricamente computável e um problema que pode ser computacionalmente inviável em determinado período de tempo.
 

 🎥 Citizenfour

O documentário Citizenfour (2014) permite discutir:

* Vigilância;
* Privacidade;
* Processamento massivo de dados;
* Algoritmos;
* Computação em larga escala;
* Segurança da informação;
* Relações entre tecnologia, Estado e sociedade.

    A discussão amplia a Teoria da Computação para além da questão "o que uma máquina consegue calcular?", incorporando também a questão:

> Quem controla os dados, os algoritmos e a infraestrutura computacional?
 

 🎥 O Menino da Internet

O documentário O Menino da Internet é utilizado para discutir:

* Aaron Swartz;
* Software livre;
* Open Access;
* Conhecimento aberto;
* Código;
* Dados;
* Algoritmos;
* Acesso à informação; Propriedade intelectual.

    A obra permite estabelecer uma discussão interdisciplinar envolvendo Computação, Ciência, Educação, Direito e Sociedade.
 

 🌐 Eixo 3 — Aplicações Contemporâneas

    A Teoria da Computação não está limitada aos modelos clássicos desenvolvidos no século XX.

    Seus conceitos continuam sendo fundamentais para compreender tecnologias atuais.
 

 🔐 Criptografia e Blockchain

    A disciplina relaciona conceitos de computação teórica com mecanismos utilizados na criptografia moderna e nas redes blockchain.

São estudados conceitos como:

* Funções matemáticas;
* Funções de hash;
* Criptografia;
* Verificação de integridade;
* Chaves criptográficas;
* Prova de trabalho;
* Busca computacional;
* Blockchain;
* Criptomoedas.

    No caso do blockchain, a computação aparece tanto na utilização de funções criptográficas quanto na execução de processos computacionais destinados à validação e à construção de registros.
 

 ⚛️ Computação Quântica

A disciplina também introduz a Computação Quântica como uma evolução dos modelos computacionais tradicionais.

São apresentados conceitos como:

* Qubits;
* Superposição;
* Computação quântica;
* Algoritmos quânticos;
* Complexidade computacional;
* Algoritmo de Shor;
* Criptografia pós-quântica.

    Um dos pontos fundamentais é compreender que a computação quântica não elimina o conceito de computabilidade, mas pode modificar profundamente a eficiência com que determinados problemas podem ser resolvidos.
 

 🚫 Limites da Computação

    Um dos principais resultados da disciplina é compreender que nem todo problema pode ser solucionado por um algoritmo.

Entre os conceitos fundamentais estão:

* Problemas decidíveis;
* Problemas indecidíveis;
* Problema da Parada;
* Computabilidade;
* Algoritmos;
* Limites dos modelos computacionais.

Essa discussão conduz a uma das perguntas fundamentais da disciplina:

> Existem problemas que nenhum computador poderá resolver?

A resposta é sim.

    A compreensão desses limites diferencia o estudo científico da computação da simples utilização de computadores e linguagens de programação.

 

🔄 Integração dos Conteúdos

A disciplina pode ser compreendida por meio da seguinte sequência:


                    TEORIA DA COMPUTAÇÃO
                            │
          ┌─────────────────┼─────────────────┐
          │                                │                                │
          ▼                               ▼                                ▼
     FUNDAMENTOS        MODELOS            LIMITES
          │                                  │                           │
          ▼                                 ▼                           ▼
      Algoritmos      Registradores     Indecidibilidade
      Programas       Turing            Problema da Parada
      Máquinas        Computabilidade   Computabilidade
          │                 │                 │
          └─────────────────┼─────────────────┘
                            │
                            ▼
                    APLICAÇÕES PRÁTICAS
                            │
        ┌───────────────────┼───────────────────┐
        ▼                   ▼                   ▼
    Criptografia        Blockchain       Computação Quântica
        │                   │                   │
        └───────────────────┼───────────────────┘
                            ▼
                       SOCIEDADE
                            │
              ┌─────────────┼─────────────┐
              ▼             ▼             ▼
          Privacidade     Código       Conhecimento
          Vigilância      Aberto        Científico



 

🎓 Competências Desenvolvidas

Ao concluir a disciplina, espera-se que o estudante desenvolva capacidade para:

* compreender os fundamentos científicos da Computação;
* formalizar problemas computacionais;
* compreender diferentes modelos de computação;
* analisar algoritmos sob uma perspectiva teórica;
* identificar problemas computáveis e indecidíveis;
* compreender os limites dos computadores;
* relacionar computação teórica com criptografia;
* compreender conceitos computacionais relacionados ao blockchain;
* reconhecer impactos da computação quântica;
* analisar criticamente o impacto da tecnologia na sociedade;
* relacionar ciência da computação, tecnologia e questões éticas;
* desenvolver pensamento lógico e abstrato.
 

 🔥 Síntese da Disciplina

A disciplina pode ser resumida em quatro grandes perguntas:
 

 1. O que é computação?

Estudo dos conceitos de algoritmos, programas, máquinas e modelos computacionais.
 

 2. O que pode ser computado?

Estudo da computabilidade e dos modelos formais, especialmente a Máquina de Turing.
 

 3. O que não pode ser computado?

Estudo dos problemas indecidíveis e dos limites fundamentais da computação.
 

 4. Como esses conceitos aparecem no mundo real?

Aplicação dos conhecimentos em:

* Criptografia;
* Criptoanálise;
* Blockchain;
* Criptomoedas;
* Segurança;
* Privacidade;
* Software livre;
* Acesso ao conhecimento;
* Computação quântica.
 

 📌 Conceito Central

> A Teoria da Computação investiga os fundamentos, as possibilidades e os limites do processo de computação.

Mais do que aprender uma tecnologia específica, o estudante aprende a compreender o que significa computar, quais problemas podem ser resolvidos por algoritmos e quais permanecem fora do alcance de qualquer máquina computacional.

Essa perspectiva permite compreender que tecnologias aparentemente diferentes — como sistemas operacionais, criptografia, inteligência artificial, blockchain e computação quântica — possuem uma base conceitual comum: algoritmos, dados, modelos computacionais e limites matemáticos.