Teoria da Computação

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

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

GitHub

 https://github.com/GeorgeMendesMarra/GeorgeMendesMarra

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

BLOCO 1: Fundamentos da Teoria da Computação (Ementa Clássica)

1. Noções de Programas e Máquinas

    A disciplina começa estabelecendo a diferença entre hardware (a máquina física) e software (o programa/instruções). Estuda-se a arquitetura de von Neumann, onde instruções e dados residem na mesma memória, e como algoritmos são traduzidos em sequências de instruções elementares que a máquina é capaz de executar.
 

2. Noção de Computabilidade Efetiva

    Este é o coração da disciplina. Define-se o que é um problema computável (aquele que pode ser resolvido por um algoritmo) e o que é um problema indecidível (aquele para o qual é matematicamente impossível criar um algoritmo, independentemente do poder de processamento). Isso introduz o conceito de limites da computação.

3. Máquinas de Registradores e Máquina de Turing

*   Máquinas de Registradores: Modelo teórico mais simples, que simula um computador real com registradores (memórias) que armazenam números inteiros e executam operações básicas (somar, subtrair, pular).

*   Máquina de Turing (MT): É o modelo matemático mais poderoso. Consiste em uma fita infinita, uma cabeça de leitura/escrita e um conjunto de estados. Todo algoritmo que existe ou pode existir pode ser executado por uma Máquina de Turing. É o padrão ouro da computabilidade.

4. Teste (Tese) de Church

    Criada por Alonzo Church e Alan Turing, esta tese afirma que: "Qualquer função que seja intuitivamente computável pode ser calculada por uma Máquina de Turing". Ou seja, se um problema não pode ser resolvido por uma MT, ele não pode ser resolvido por nenhum computador do mundo real. Isso formaliza o conceito de "algoritmo" e define o limite máximo do que a computação clássica pode fazer.
 

BLOCO 2: Análise Fílmica (Aplicação dos Conceitos na Prática e na História)

    Os filmes a seguir não são apenas entretenimento, mas sim estudos de caso sobre os limites da computação, criptoanálise e o impacto social das tecnologias.

*   Revolution OS (2001) – O Software e o Código como Algoritmo: O documentário mostra a batalha entre software proprietário (Microsoft) e código aberto (Linux). Na ótica da Teoria da Computação, o filme ilustra que o código-fonte (o algoritmo) é a "fita da Máquina de Turing" da era moderna. O acesso ao código define quem controla a "máquina" e quem pode provar sua eficiência.

*   Enigma (2001) e O Jogo da Imitação (2014) – A Prova da Computabilidade e a Máquina de Turing: Ambos retratam Alan Turing e a quebra da máquina Enigma nazista. Análise: Mostram na prática a Máquina de Turing e o Teste de Church. A máquina "Bombe" construída por Turing era uma versão física do conceito de busca exaustiva (força bruta) e redução de espaço de estados. Turing comprovou que, ao contrário do que se pensava, a criptografia da Enigma era computável (quebra possível) desde que houvesse processamento suficiente e um algoritmo correto.

*   Swordfish (A Senha, 2001) – A Complexidade Computacional e a Criptografia de Dados: O filme explora a ideia de quebrar um sistema bancário. Análise: O filme aborda a complexidade de tempo de um algoritmo. A criptografia de 128 bits discutida no filme (mesmo que de forma exagerada) ilustra a diferença entre problemas P (fáceis de resolver) e NP (onde verificar a resposta é fácil, mas encontrá-la leva tempo exponencial). O "código" é o algoritmo, e a "senha" é a chave que o torna intratável.

*   Citizenfour (2014) – Privacidade, Computabilidade e Vigilância: Documentário sobre Edward Snowden. Análise: Mostra a computação aplicada à vigilância global. A NSA opera no limite da computabilidade efetiva, utilizando poder de processamento massivo para quebrar sistemas que, teoricamente, eram seguros. Apresenta o dilema: a Tese de Church garante que se o algoritmo existir, a máquina o rodará. A grande questão é quem controla a máquina e o algoritmo.

* O Menino da Internet (2020) - O filme aborda o ativismo pelo Código Aberto (Open Source) e pelo Acesso Livre (Open Access) à produção acadêmica e científica. Ele defendia que os algoritmos, códigos-fonte e artigos científicos, que são a base da computabilidade, não podem ser propriedade privada de editoras. O Reddit: Vocês podem discutir como os algoritmos do Reddit (que ele ajudou a criar) organizam a informação de forma colaborativa. A Enciclopédia: O ato de baixar a enciclopédia mostra que, para Swartz, o conhecimento é apenas um conjunto de dados. Na Teoria da Computação, o dado é a entrada da Máquina de Turing; se o dado existe, a máquina pode processá-lo. O JSTOR e o MIT: Um choque entre a computação teórica (onde tudo é possível e permissível) e a computação legal/prática (onde o acesso é controlado por leis de propriedade intelectual). Análise Teórica: Swartz personifica a luta pela democratização dos algoritmos e do conhecimento. Seu primeiro grande ato foi baixar massivamente a Encyclopaedia Britannica (a grande enciclopédia, rival da Barsa) e liberá-la, acreditando que o conhecimento é um bem comum que não deveria ser restrito. Isso dialoga diretamente com a Tese de Church: se um algoritmo (ou dado) pode ser processado por uma Máquina de Turing, ele deveria ser acessível a qualquer máquina.

BLOCO 3: Aplicações Contemporâneas (Expandindo a Teoria para o Mundo Real)

    A Teoria da Computação clássica não é apenas história; ela é a base das tecnologias que usamos hoje.
 

1. Criptografia e Criptomoedas (Blockchain)

*   Teoria: A segurança da criptografia moderna (como RSA e ECDSA) baseia-se em funções de mão única (fáceis de calcular, muito difíceis de inverter) e em problemas NP.
*   Blockchain: É uma estrutura de dados (uma lista encadeada) imutável. A Teoria da Computação garante que, se você tem o hash (resultado do algoritmo), pode verificar a integridade dos dados. O algoritmo de consenso (como o Proof-of-Work do Bitcoin) é um problema de busca: o sistema literalmente obriga os computadores a realizarem milhões de operações de hash até encontrar um valor específico, comprovando o gasto de energia computacional.
 

2. Computação Quântica – O Fim da Tese de Church Clássica?

*   A Tese de Church fala sobre máquinas clássicas. A computação quântica introduz os Qubits (bits quânticos), que podem ser 0, 1 ou ambos ao mesmo tempo (superposição).
*   Impacto: Ela não quebra a Tese de Church (ela ainda é computável), mas muda drasticamente a complexidade (tempo). Algoritmos como o de Shor mostram que um computador quântico pode fatorar números primos (a base da criptografia atual) em minutos, enquanto uma Máquina de Turing clássica levaria milhares de anos. Isso redefine o que é "praticável" versus "impraticável".
 

 🔥 Resumo Final (Mapa Mental para Prova)

1.  Conceito: O que pode ser calculado? -> Máquina de Turing e Tese de Church.
2.  Limite: O que não pode ser calculado? -> Problemas indecidíveis (ex: o Problema da Parada).
3.  Prática (Filmes):
    *   Criptoanálise e limites de hardware (Jogo da Imitação, Enigma).
    *   O controle do código e software (Revolution OS).
    *   O colapso da privacidade via algoritmos massivos (Citizenfour).
    *   Infraestrutura global da computação (O Menino da Internet).
4.  Futuro: A criptografia de hoje depende de um problema computacional (fatoração de números). A computação quântica ameaça essa computabilidade. As criptomoedas e o blockchain usam hash criptográfico e busca de prova de trabalho para garantir confiança descentralizada, tudo regido pelas leis da Máquina de Turing.