Introdução à Teoria da Computação

Pré-requisitos

Não subestime os pré-requisitos obrigatórios pois este curso, apesar de introdutório e em nível de graduação, é um curso muito difícil. Você pode até considerar que este curso é mais matemático do que computacional: realmente, Teoria da Computação tem muito mais em comum com a matemática do que com a computação e computadores. Você precisará de conforto com os seguintes pré-requisitos:

1. MATEMÁTICA DISCRETA: é o pilar central e um pré-requisito absoluto para entender Teoria da Computação. Se você não tiver conforto em matemática discreta você parecerá estar decifrando hieróglifos egípcios antes da descoberta da Pedra de Roseta. Você precisa ter conforto em:
   • Conjuntos, relações e funções: domínio/contradomínio, função injetora/sobrejetora, composição de funções, união, intersecção, complemento, produto cartesiano;
   • Lógica matemática (proposicional e de predicados): implicação, quantificadores, negação, seguir uma cadeia lógica, quantificadores;
   • Métodos de prova: direta, contradição, contrapositiva, indução. Este é o ponto onde os alunos mais falham: o curso exige que você prove teoremas por indução matemática (importante para provar propriedades de loops e recursividade) e por contradição (importante para provar que certos problemas são indecidíveis);
   • Grafos: os autômatos são modelados como grafos dirigidos e é importante entender nós, arestas, caminhos, ciclos e árvores;
   • Contagem básica e combinatória: importante para o estudo de complexidade.
2. PROGRAMAÇÃO, ALGORITMOS E ESTRUTURAS DE DADOS: você não precisa ser um expert em Linguagem C (a linguagem usada no curso), mas precisa absolutamente de:
   • Pensamento computacional: dominar o pensamento computacional e métodos de resolução de problemas complexos (decomposição, reconhecimento de padrões, abstrações, algoritmos e estruturas de dados);
   • Expressão de algoritmos: em pseudo-código, fluxogramas ou linguagem C; representação e manipulação de strings;
   • Linguagem C: quando exemplificarmos conceitos de modo concreto, usaremos C;
   • Corretude: argumentar por que um algoritmo funciona;
   • Análise assintótica básica: Big-O, Big-Ômega, Theta, crescimento de funções, noções de comportamente no pior caso; complexidade de tempo e espaço, classes de complexidade;
   • Estruturas de dados: difereça entre estruturas de dados e tipos abstratos de dados (TADs), principais TADs da computação (pilha, fila, queue, deque, dicionários, etc.), principais estruturas de dados da computação (variáveis, arrays, listas, árvores, grafos)
   • Recursividade: a Teorida da Computação usa muito funções recursivas e recursividade, você deve ter muito conforto com isso.
3. ESTRUTURAS FORMAIS: os pré-requisitos a seguir não são absolutamente necessários (talvez) mas, de qualquer forma, seu aprendizado será muito mais fácil com eles:
   • Linguagens formais: esse conteúdo será estudado por nós mas, se você já tiver feito um outro curso ou estudado sobre linguagens formais (expressões regulares, gramática e linguagens, parsing), seu estudo será mais fácil;
   • Compiladores: um curso introdutório sobre compiladores pode facilitar seu entendimento da Teoria da Computação.
4. GERAIS: são pré-requisitos difíceis de serem obtidos apenas com uma ou outra disciplina da computação, mas que facilitarão muito seu aprendizado:
   • Maturidade matemática: isso aqui vai bem além da matemática discreta, incluindo por exemplo cálculo e álgebra linear. Você não vai usar integrais ou derivadas em Teoria da Computação, mas seu cérebro precisa estar treinado a lidar com abstrações, definições rigorosas e formalismo simbólico;
   • Capacidade de abstração: você deve ter conforto em lidar com conceitos e demonstrações puramente abstratas, sem depender de exemplos concretos o tempo todo; o exemplo concreto ajuda muito no começo mas, depois, você precisa passar para o nível abstrato;
   • Leitura técnica: definição, teorema, prova.