Teoria da Computação¶

Introdução - Conceitos Básicos¶

Computação¶

computação = estudo dos processos que manipulam dados de forma sistemática
- Envolve desde operações matemáticas básicas até sistemas complexos de inteligência artificial.
- Fazer o cômputo de (algo)
- Avaliar por meio de cálculo
- Calcular, orçar
- Contar

Computador¶

computador = máquina capaz de processar informações de acordo com um conjunto de instruções (programa)
- opera por meio de componentes como processador, memória e dispositivos de entrada/saída.
- o que faz cálculos
- entrada, programa, saída
Quem veio primeiro: a computação ou o computador?
- computação

Teoria da Computação¶

Teoria da Computação = área da ciência da computação que estuda os fundamentos matemáticos dos algoritmos e da computabilidade
objetivo principal = entender os limites do que pode ser computado e como fazê-lo de maneira eficiente
Provide insight about the problem-solving capabilities of real computers
The study of efficient computation, models of computational processes, and their limits

Máquina de Turing¶

máquina de Turing = modelo de um computador de propósito geral
- modelo teórico de computação que descreve um dispositivo abstrato capaz de manipular símbolos em uma fita infinita de acordo com um conjunto de regras
- fundamental para definir o conceito de computabilidade

Autômato¶

autômato = modelo matemático de computação que representa uma máquina abstrata capaz de processar uma sequência de símbolos de acordo com um conjunto de regras pré-definidas
amplamente usado para modelar sistemas computacionais, linguagens formais e protocolos de comunicação

Máquinas de Estado Finitas – FSM¶

máquina de estado finita - FSM = modelo matemático que pode estar em um de um número finito de estados e transita entre eles com base em entradas
- FSM = Finite State Machines
usada para modelar sistemas de controle, protocolos de comunicação e reconhecimento de padrões
Determinística (DFA - Deterministic Finite Automaton) = sempre há uma única transição possível para cada entrada
Não Determinística (NFA - Nondeterministic Finite Automaton) = pode haver múltiplas transições possíveis para uma mesma entrada

Autômatos Finitos¶

autômatos finitos = tipo específico de máquina de estado finita usados principalmente para processar e reconhecer linguagens regulares
podem ser representados como
- Autômato Finito Determinístico (DFA) = cada estado tem transições únicas para cada símbolo de entrada
- Autômato Finito Não Determinístico (NFA) = pode ter múltiplas transições para um mesmo símbolo, incluindo transições vazias - ε-transições
os autômatos finitos são fundamentais na construção de analisadores léxicos de compiladores e no reconhecimento de padrões em textos

Linguagens Formais¶

Conceitos básicos¶

linguagens formais = conceito fundamental na Teoria da Computação e são usadas para descrever e definir linguagens de programação, expressões regulares e gramáticas matemáticas
Elas são formadas por um alfabeto e um conjunto de regras gramaticais que determinam quais sequências de símbolos pertencem à linguagem.

Componentes de uma Linguagem Formal¶

Uma linguagem formal L é definida como um conjunto de palavras formadas a partir de um alfabeto Σ e geradas por regras específicas.
Alfabeto - Σ = Conjunto finito de símbolos
- Exemplo - Σ={0,1} na linguagem binária
Palavra / String = Sequência finita de símbolos do alfabeto
- Exemplo - "101", "0011"
Gramática = Conjunto de regras que define como palavras válidas podem ser formadas

Hierarquia de Chomsky¶

No estudo das linguagens formais, Noam Chomsky definiu uma hierarquia de gramáticas baseada no seu nível de complexidade

Tipo	Classe de Linguagem	Modelo de Reconhecimento
Tipo 0	Linguagens Recursivamente Enumeráveis	Máquina de Turing
Tipo 1	Linguagens Sensíveis ao Contexto	Máquina Linearmente Limitada
Tipo 2	Linguagens Livre de Contexto	Autômato de Pilha
Tipo 3	Linguagens Regulares	Autômato Finito

Linguagens Regulares → Usadas em expressões regulares e reconhecidas por autômatos finitos
Linguagens Livres de Contexto → Fundamentais para linguagens de programação, reconhecidas por autômatos de pilha
Linguagens Sensíveis ao Contexto → Mais poderosas, usadas para algumas regras de linguagens naturais e compiladores
Linguagens Recursivamente Enumeráveis → As mais gerais, reconhecidas por Máquinas de Turing

Relação com Compiladores e Expressões Regulares¶

Linguagens Regulares = são usadas na análise léxica de compiladores e expressões regulares
Linguagens Livres de Contexto = definem a sintaxe das linguagens de programação
- exemplo = gramáticas BNF
Linguagens Sensíveis ao Contexto = aparecem na análise semântica de compiladores
As linguagens formais são essenciais para a construção de compiladores, reconhecimento de padrões e inteligência artificial

Síntese¶

1. Teoria da Computação¶

Computação: Estudo dos processos de manipulação de dados por máquinas para resolver problemas.
Máquinas de Turing: Modelos matemáticos fundamentais para entender a computação. Elas podem simular qualquer algoritmo que um computador moderno pode executar.
Problema da Parada (Halting Problem): Problema que afirma que não existe um algoritmo universal que determine se um programa vai parar ou entrar em loop infinito.
Teoria da Complexidade Computacional: Estudo de quanto tempo e recursos (como memória) um algoritmo precisa para resolver um problema, geralmente expressos em função do tamanho da entrada.
Classe P: Problemas que podem ser resolvidos por algoritmos com tempo polinomial.
Problemas NP: Problemas para os quais, se dada uma solução, ela pode ser verificada em tempo polinomial.
NP-completo: Classe de problemas que são pelo menos tão difíceis quanto os problemas mais difíceis da classe NP.
Máquinas de Turing Determinísticas e Não Determinísticas: A diferença principal é que uma máquina de Turing determinística sempre tem uma única transição possível, enquanto a não determinística pode ter várias possibilidades.

2. Linguagens Formais e Gramáticas¶

Alfabeto: Conjunto de símbolos básicos.
Cadeia de caracteres: Sequência finita de símbolos do alfabeto.
Linguagem Formal: Conjunto de cadeias sobre um alfabeto.
Gramáticas: Regras que definem como formar cadeias válidas de uma linguagem.
- Gramática Regular: Pode ser descrita por autômatos finitos ou expressões regulares.
- Gramática Livre de Contexto: Pode ser descrita por autômatos de pilha e é mais poderosa que a gramática regular.
Autômato Finito (DFA, NFA): Modelos de máquinas para reconhecer linguagens regulares.
Autômato de Pilha (PDA): Aceita linguagens livres de contexto.
Máquina de Turing: Modelo universal para reconhecer qualquer linguagem que pode ser computada (decidível).

3. Relações¶

Relação: Um conjunto de pares ordenados.
Propriedades das Relações:
- Reflexiva: Para todo a, (a,a) ∈ R
  - todo elemento se relaciona com ele mesmo
- Simétrica: Se (a,b)∈R(a, b) \in R, então (b,a)∈R(b, a) \in R
  - a inversão dos elementos do par ordenado segue verdadeira
  - em alguns casos, permite multiplicar equação por -1
  - inverte a relação
- Transitiva: Se (a,b)∈R(a, b) \in R e (b,c)∈R(b, c) \in R, então (a,c)∈R(a, c) \in R.
- Antissimétrica: Se (a,b)∈R(a, b) \in R e (b,a)∈R(b, a) \in R, então a=ba = b.
  - toda antissimétrica é simétrica, mas nem toda simétrica é antissimétrica
  - antissimetria é um caso especial de simetria
  - ao colocar os elementos iguais, chega-se em um valor válido na relação
  - se dois elementos são mutuamente relacionados, eles devem ser o mesmo elemento
  - Para testar se uma relação é antissimétrica, verifique se, para cada par (a,b) e (b,a), é necessário que a=ba = ba=b. Se houver um par (a,b) e (b,a) com a≠b, a relação não é antissimétrica
- Irreflexiva: Para todo aa, (a,a)∉R(a, a) \notin R.
Produto Cartesiano: A×BA \times B é o conjunto de todos os pares (a,b)(a, b) onde a∈Aa \in A e b∈Bb \in B.
Conjunto das Partes: O conjunto de todos os subconjuntos de um conjunto AA, denotado por P(A)P(A).
Relação Inversa: A relação inversa de RR, denotada R−1R^{-1}, é formada trocando os elementos dos pares ordenados.

4. Conjuntos e Operações¶

Domínio: O conjunto de todos os primeiros elementos de um par ordenado de uma relação.
Imagem: O conjunto de todos os segundos elementos de um par ordenado de uma relação.
Contradomínio: O conjunto de todos os elementos que poderiam ser segundos elementos, mas não necessariamente fazem parte da imagem.
Diferença entre Imagem e Contradomínio: A imagem é o conjunto de elementos realmente atingidos pela relação, enquanto o contradomínio é o conjunto de todos os possíveis elementos de saída.
Produto Cartesiano: O produto A×BA \times B é o conjunto de pares formados por um elemento de AA e um de BB.
Subpalavra: Uma sequência contínua de símbolos de uma palavra.
Concatenação: A operação de unir duas cadeias de caracteres, formando uma nova cadeia.

5. Complexidade e Computabilidade¶

Complexidade Computacional: A análise do tempo e espaço necessários para resolver um problema usando um algoritmo. A complexidade pode ser expressa em termos de tempo (quanto tempo um algoritmo leva) e espaço (quantos recursos de memória são necessários).
Classe P: Problemas que podem ser resolvidos em tempo polinomial.
Classe NP: Problemas cujas soluções podem ser verificadas em tempo polinomial, mas não necessariamente resolvidas de forma eficiente.
NP-completo: Problemas que são pelo menos tão difíceis quanto qualquer outro problema NP.

A Teoria da Computação estuda os limites e a eficiência de algoritmos e modelos computacionais, como as Máquinas de Turing e autômatos. Ela também lida com problemas de complexidade computacional, linguagens formais, e gramáticas. A análise de relações e suas propriedades é central em matemática discreta.