Módulo 0 — Nivelamento: Roteiro de Conteúdo
Apresentação
Esta disciplina tem uma característica que a distingue de quase todas as anteriores do curso: ela cobra, no mesmo semestre e com o mesmo peso, rigor matemático e competência de programação. Numa semana você demonstra formalmente que uma linguagem não pode ser reconhecida por determinado modelo de máquina; na semana seguinte implementa o algoritmo que reconhece as que podem. As duas exigências vêm de lugares diferentes da sua formação, e é comum que uma delas esteja mais adormecida que a outra.
O Módulo 0 existe para acordar as duas antes que o semestre comece a cobrá-las. Ele não é recuperação para quem ficou para trás nem conteúdo novo: é revisão dirigida daquilo que você já viu em disciplinas anteriores e que voltará a ser usado aqui, quase sempre de uma forma um pouco diferente da que você conheceu.
Sobre a origem deste roteiro. O projeto pedagógico do curso não estabelece pré-requisito formal para esta disciplina — não há travamento de matrícula. O que existe é a progressão curricular: ao chegar ao sexto termo, você cursou um conjunto conhecido de disciplinas, e é dele que este roteiro parte. Cada bloco abaixo indica explicitamente de qual disciplina o conteúdo vem e o que a ementa oficial dela previa, para que você saiba exatamente onde reencontrar o material caso precise de mais que uma revisão.
O conteúdo vem de cinco frentes. A base matemática formal vem de Matemática Discreta, do primeiro termo, e é a que sustenta todo o eixo teórico do curso. As estruturas de dados vêm da disciplina homônima, do segundo termo, e reaparecem em praticamente todas as fases do compilador. A maturidade de programação vem de Pensamento Computacional e Programação e de Programação Orientada a Objetos, do primeiro e do segundo termos. A visão de grafos vem de Resolução de Problemas de Grafos, do quarto termo. E a visão de máquina vem de Arquitetura e Organização de Computadores e de Design de Processador de Computador, do terceiro e do quinto termos.
Objetivos do Nivelamento
Ao final deste módulo, você deve ser capaz de operar com fluência a notação de conjuntos, relações e funções, porque é nela que todos os modelos formais do curso serão definidos — um autômato é literalmente uma quíntupla de conjuntos e funções, e não há como entender a definição sem estar confortável com o vocabulário.
Você deve ser capaz de conduzir uma demonstração por indução e de reconhecer a estrutura de uma prova por contradição, porque as duas técnicas aparecem em todos os resultados centrais da primeira metade da disciplina, e a demonstração de que uma linguagem não é regular é, na sua essência, uma prova por contradição bem organizada.
Você deve estar confortável com pilhas, árvores e estruturas de busca por chave, e saber escolher entre elas com base no padrão de uso previsto — não porque serão ensinadas de novo, mas porque cada fase do compilador escolhe uma delas, e escolher mal tem custo que se paga por meses.
Você deve conseguir programar com autonomia em uma linguagem de sistemas, lidando com estruturas encadeadas e com a gestão explícita de memória, já que o projeto do semestre é construído assim.
E deve ter presente o vocabulário básico de arquitetura — registrador, conjunto de instruções, pilha de execução, organização de memória — porque é o destino para onde o compilador traduz, e a última parte do curso fica opaca sem ele.
Pré-requisitos
Pré-requisito: Notação matemática de conjuntos, relações e funções
Origem: Matemática Discreta, 1º termo. A ementa oficial prevê teoria intuitiva dos conjuntos, operações com conjuntos, álgebra de conjuntos, relações, relações de equivalência, relações de ordem, funções, coleções de conjuntos, cardinalidade.
Abra a definição formal de qualquer modelo desta disciplina e você encontrará a mesma coisa: uma tupla cujos componentes são conjuntos e funções entre eles. Quem não lê essa notação com naturalidade gasta a energia decifrando a forma e não sobra atenção para o conteúdo.
A revisão deve cobrir a notação de conjuntos e suas operações, com atenção especial ao conjunto vazio e às armadilhas que ele produz. Relações binárias e suas propriedades, com destaque para relações de equivalência e para a noção de partição induzida por uma equivalência — este último ponto merece cuidado, porque o algoritmo de minimização de autômatos é, do começo ao fim, um refinamento sucessivo de partições, e quem não tem a noção clara acompanha o algoritmo sem entender o que ele faz. Funções, com domínio, contradomínio e imagem bem distinguidos, e a diferença entre função total e parcial, que reaparece na discussão sobre completude da função de transição. Produto cartesiano, porque a construção que combina dois autômatos opera sobre ele. E a noção de conjunto de partes, porque o algoritmo de determinização constrói estados que são, literalmente, conjuntos de estados.
Profundidade: revisão de notação e de fluência operacional. Não é reestudo da teoria de conjuntos — é retomar o vocabulário até que ler uma definição formal não custe esforço.
Pré-requisito: Técnicas de demonstração
Origem: Matemática Discreta, 1º termo. A ementa oficial prevê técnicas de demonstração: prova direta, prova por contradição, indução finita.
Esta é a competência que mais separa quem atravessa a primeira metade da disciplina com tranquilidade de quem sofre nela. E é também a mais frequentemente adormecida, porque muitos estudantes não escrevem uma demonstração desde o primeiro termo.
A revisão deve retomar a estrutura de uma prova direta e o que significa, exatamente, ter demonstrado algo. A prova por contradição, com atenção à sua forma lógica: supor o oposto, derivar um absurdo, concluir. E a indução finita, tanto na forma simples quanto na forma forte, com prática deliberada em enunciados sobre cadeias e sobre estruturas definidas recursivamente — que é como praticamente tudo neste curso é definido.
Vale um alerta específico. A demonstração mais importante da disciplina, a de que certa linguagem não pode ser reconhecida por um autômato finito, tem uma estrutura lógica com quantificadores alternados que é fonte inesgotável de erro. Quem chega ao sexto módulo sem estar confortável com a diferença entre “para todo” e “existe” — e, principalmente, com a ordem em que eles aparecem — vai produzir demonstrações que parecem certas e não são. Se houver um único tópico deste nivelamento em que vale investir tempo extra, é este.
Profundidade: revisão com prática. Não basta reconhecer as técnicas; é preciso conseguir escrever uma demonstração completa e correta sobre um enunciado simples.
Pré-requisito: Estruturas de dados e escolha de representação
Origem: Estrutura de Dados, 2º termo. A ementa oficial prevê tipos abstratos de dados, listas lineares e suas generalizações, pilhas e filas, árvores binárias, de busca e balanceadas, análise e complexidade de algoritmos, métodos de pesquisa.
Um compilador é, sob certo ângulo, um passeio pelas estruturas de dados clássicas. A pilha aparece no analisador sintático e na máquina de execução. A árvore aparece como representação do programa e é percorrida repetidamente. A busca por chave aparece na tabela de símbolos, que é consultada muito mais vezes do que modificada. Nada disso será reensinado — mas tudo será usado, e será usado bem ou mal conforme o que você lembrar.
A revisão deve retomar a pilha e suas operações, com atenção ao que significa uma pilha como memória auxiliar de uma máquina abstrata. Árvores binárias e percursos, sobretudo o percurso em profundidade, que é a forma como praticamente todas as fases finais do compilador processam o programa. Estruturas de busca por chave, com o compromisso entre as alternativas: a tabela de símbolos tem padrão de uso muito assimétrico, e escolher a estrutura pelo padrão de uso, e não pelo hábito, é exatamente o tipo de decisão que o curso quer exercitar. E a noção básica de complexidade, suficiente para discutir por que um algoritmo com pior caso exponencial pode, ainda assim, ser a escolha certa na prática — situação que aparece no quinto módulo e desconcerta quem nunca separou pior caso de caso típico.
Profundidade: revisão de uso e, principalmente, de critério de escolha. As implementações não precisam ser refeitas; o raciocínio sobre qual estrutura serve a qual padrão de acesso, sim.
Pré-requisito: Grafos dirigidos e percursos
Origem: Resolução de Problemas de Grafos, 4º termo. A ementa oficial prevê conceitos básicos de grafos dirigidos e não dirigidos, passeios, caminhos, circuitos, conexidade, estruturas de dados para representação de grafos, percursos em largura e em profundidade, ordenação topológica.
Vale enunciar de forma direta, porque a conexão não é sempre percebida: um autômato é um grafo dirigido rotulado. Os estados são vértices, as transições são arestas, e reconhecer uma cadeia é percorrer um caminho. Quase tudo que você fará com autômatos nos primeiros módulos é um algoritmo de grafos com outro nome.
A revisão deve retomar grafos dirigidos, caminhos e circuitos, e a noção de alcançabilidade — que é o que fundamenta a eliminação de estados inúteis. As formas de representar um grafo em memória, com o compromisso entre elas, porque essa é a primeira decisão de projeto do módulo três e ela condiciona todo o resto do semestre. E os percursos em largura e em profundidade, que aparecem tanto no cálculo do fecho de transições vazias quanto na construção do autômato determinizado.
Se sobrar tempo, vale relembrar ordenação topológica, que reaparece no último bloco quando o compilador precisa determinar ordem de avaliação a partir de um grafo de dependências.
Profundidade: revisão dos conceitos e dos percursos, com ênfase na tradução mental entre o vocabulário de grafos e o de autômatos.
Pré-requisito: Maturidade de programação em linguagem de sistemas
Origem: Pensamento Computacional e Programação, 1º termo, e Programação Orientada a Objetos, 2º termo. As ementas oficiais preveem, respectivamente, os fundamentos de programação com variáveis, operadores, expressões e estruturas de controle, e os conceitos de classes, objetos, encapsulamento, herança e polimorfismo, com análise e projeto orientados a objetos.
O projeto do semestre é um programa de médio porte, construído de forma cumulativa durante quinze módulos, em uma linguagem que expõe a gestão de memória. Isso exige mais do que saber a sintaxe.
A revisão deve garantir conforto com estruturas encadeadas e com a distinção entre valor e referência, porque a estrutura central do curso é um grafo cíclico e manipular grafos cíclicos por referência é a origem mais comum de defeito em projetos como este. Deve garantir também conforto com alocação e liberação de memória, e com o que acontece quando uma delas é esquecida. Do lado da organização, o que importa é a capacidade de dividir um programa em módulos com responsabilidades claras e interfaces explícitas — um compilador é, por natureza, um sistema de fases que se comunicam, e a qualidade dessas interfaces determina se o projeto cresce ou empaca.
Vale ainda revisar a disciplina de tipos: declarar tipos explicitamente, entender o que o compilador verifica e o que não verifica, e tratar aviso de compilação como problema a resolver e não como ruído a ignorar. O projeto exige compilação sem nenhum aviso sob configuração estrita, e quem tem o hábito de conviver com avisos vai estranhar no começo.
Profundidade: revisão prática, verificada por um pequeno programa que compile limpo sob a configuração estrita da disciplina. É o único bloco em que a verificação é escrever código, não responder questão.
Pré-requisito: Vocabulário de arquitetura e modelo de execução
Origem: Arquitetura e Organização de Computadores, 3º termo, e Design de Processador de Computador, 5º termo. As ementas oficiais preveem, respectivamente, estrutura interna do processador, registradores, unidade lógica e aritmética, conjuntos de instruções, arquiteturas RISC e CISC e hierarquia de memória; e arquitetura de Von Neumann, registradores, conjunto de instruções, modos de endereçamento, pilhas, linguagem de montagem e caminho de dados de um processador específico.
O compilador traduz para alguma coisa, e essa coisa é uma máquina. O terceiro bloco do curso fica opaco para quem não tem presente o que é um registrador, o que é um conjunto de instruções e como um programa se organiza na memória enquanto executa.
A boa notícia é que este pré-requisito é o mais recente da sua formação e provavelmente o mais fresco. A revisão pode ser breve: retomar a organização de Von Neumann e o ciclo de execução; o conceito de conjunto de instruções e a diferença entre uma arquitetura com muitas instruções especializadas e outra com poucas instruções regulares, que reaparece quando o curso discutir para que tipo de máquina gerar código; a noção de modo de endereçamento; e a pilha como estrutura de execução, distinta da pilha como estrutura de dados abstrata — distinção que importa no módulo sobre ambientes de execução.
Quem cursou Design de Processador de Computador tem uma vantagem específica: já viu um conjunto de instruções concreto e uma linguagem de montagem real. Essa experiência é diretamente aplicável quando o curso projetar o conjunto de instruções da máquina abstrata para a qual o compilador vai gerar código.
Profundidade: revisão de vocabulário e de modelo mental. Não é preciso reprojetar um processador; é preciso não estranhar os termos quando eles voltarem.
Mapa para a Disciplina
A tabela abaixo mostra onde cada pré-requisito é efetivamente cobrado. Ela serve a dois propósitos: justificar por que a revisão vale o tempo investido, e permitir que você volte a um bloco específico quando sentir dificuldade em um módulo determinado.
| Pré-requisito | Onde é cobrado | Como aparece |
|---|---|---|
| Conjuntos, relações e funções | Módulos 2 a 6, 8 e 9 | Toda definição formal é uma tupla de conjuntos e funções; a minimização é refinamento de partições; a determinização constrói estados que são conjuntos de estados |
| Técnicas de demonstração | Módulos 4, 5, 6 e 9 | Equivalência entre modelos, correção dos algoritmos, e a demonstração de não regularidade do módulo 6, que é o ponto de maior exigência formal do semestre |
| Estruturas de dados | Módulos 3, 5, 10, 12 e 13 | Representação de autômatos, pilha do analisador sintático, tabela de símbolos, pilha da máquina de execução |
| Grafos dirigidos e percursos | Módulos 3, 4, 5 e 15 | Autômatos são grafos dirigidos rotulados; o fecho de transições vazias e a determinização são percursos; o grafo de fluxo de controle do módulo 15 |
| Maturidade de programação | Módulos 3 a 15 | Todo o projeto, do primeiro código ao compilador completo |
| Vocabulário de arquitetura | Módulos 13 e 14 | Ambientes de execução, organização da memória, projeto do conjunto de instruções da máquina de destino |
Como usar este módulo. Não é preciso revisar tudo antes de começar. A leitura recomendada é a seguinte: percorra os blocos agora, de forma rápida, apenas para identificar quais deles descrevem algo que você não lembra bem. Concentre a revisão nesses.
Se o tempo for curto, priorize nesta ordem: técnicas de demonstração, notação de conjuntos e relações, e maturidade de programação. Os três primeiros módulos da disciplina cobram exatamente isso, e são também os pré-requisitos mais difíceis de recuperar depois, no meio do semestre, com o projeto já andando.
O vocabulário de arquitetura pode esperar — ele só é cobrado no décimo terceiro módulo, e há tempo de sobra para retomá-lo durante o semestre.