Curso de Lógica de Programação Avançado

Nos dois primeiros cursos da trilha você aprendeu a resolver problemas: montar a lógica, escrever o laço, tratar a lista. Agora a régua sobe. O avançado é sobre PROJETAR a solução: escolher a estrutura de dados que guarda a informação do jeito certo e o algoritmo que age sobre ela com eficiência. Este módulo de abertura explica essa virada, apresenta o tipo abstrato de dados (o contrato entre o que uma estrutura faz e como ela faz) e desenha o mapa das estruturas e algoritmos que você vai dominar.

• O salto para o avançado: de resolver a projetar
• Tipo abstrato de dados: o contrato antes do código
• O mapa do avançado: estruturas guardam, algoritmos agem

A pilha é a primeira estrutura abstrata deste curso, e uma das mais úteis. A regra dela cabe numa frase: o último a entrar é o primeiro a sair. É a lógica de uma pilha de pratos, do botão desfazer, do voltar do navegador e da própria forma como o computador organiza as chamadas de funções. Neste módulo você aprende a pensar em pilha, a empilhar e desempilhar só pelo topo, e a usar essa estrutura para resolver um problema clássico: checar se os parênteses de uma expressão estão balanceados.

• O que é uma pilha (LIFO)
• Empilhar, desempilhar e espiar o topo
• A pilha de chamadas e o botão desfazer
• Parênteses balanceados com uma pilha

A pilha atende sempre o último que chegou. A fila faz o contrário e o mais justo: o primeiro a entrar é o primeiro a sair, exatamente como a fila do banco ou do caixa do mercado. Este módulo ensina o comportamento FIFO, as duas pontas da fila (a frente de onde se sai e o fim onde se entra), as operações de enfileirar e desenfileirar, a fila de prioridade que fura a ordem por bons motivos, e como decidir entre pilha e fila em cada problema.

• O que é uma fila: o comportamento FIFO
• Enfileirar e desenfileirar: as operações da fila
• Fila de prioridade: quando furar a fila é justo
• Pilha ou fila: escolhendo a estrutura certa

O vetor guarda os valores encostados um no outro, numerados por índice. A lista ligada faz diferente: espalha os valores pela memória e amarra cada um ao próximo por uma ligação, como os vagões de um trem. Você não chega a um valor pelo índice, chega seguindo a corrente. Em troca, inserir e remover no meio fica barato: basta religar duas ligações, sem empurrar ninguém. Este módulo ensina o nó, a inserção barata, a escolha entre lista e vetor e as variações dupla e circular.

• O nó e a ligação: a corrente de dados
• Inserir e remover: só religar ponteiros
• Lista ligada ou vetor: cada um no seu forte
• Listas duplas e circulares: variações da corrente

Pilha, fila e lista guardam dados em fila indiana, um atrás do outro. A árvore quebra essa linha: cada nó pode apontar para vários outros abaixo de si, formando ramos que descem de uma raiz até as folhas. É a estrutura por trás das pastas do computador, do organograma da empresa e dos menus que se abrem em submenus. Este módulo ensina a anatomia da árvore, a árvore binária, a árvore de busca binária (que acha um valor cortando o problema pela metade) e as três formas de percorrer uma árvore.

• O que é uma árvore: raiz, nós e folhas
• Árvore binária: no máximo dois filhos
• Árvore de busca binária: menores à esquerda, maiores à direita
• Percorrer uma árvore: em-ordem, pré-ordem e pós-ordem

A árvore organiza uma hierarquia, mas boa parte das relações do mundo não tem chefe nem raiz: amigos que se conhecem, cidades ligadas por estradas, páginas que apontam umas para as outras. Essas redes pedem uma estrutura mais livre, o grafo, feito de vértices (os pontos) e arestas (as ligações). Este módulo apresenta a anatomia do grafo, seus tipos (dirigido ou não, com peso ou sem), as duas formas clássicas de guardá-lo na memória e como enxergar grafos escondidos em problemas do dia a dia.

• O que é um grafo: vértices e arestas
• Tipos de grafo: dirigido, não dirigido e com peso
• Representar um grafo: lista e matriz de adjacência
• O mundo como grafo: redes, mapas e rotas

Ter um grafo desenhado não adianta se você não sabe andar por ele. Este módulo ensina as duas maneiras clássicas de visitar os vértices: a busca em largura, que explora por camadas usando uma fila, e a busca em profundidade, que vai fundo primeiro usando pilha ou recursão. Com a busca em largura você acha o caminho mais curto em número de passos, e com o conjunto de visitados você evita andar em círculos para sempre.

• Busca em largura: explorar por camadas
• Busca em profundidade: ir fundo primeiro
• Achar o caminho mais curto com a busca em largura
• Visitados e ciclos: como não andar em círculos

Você já sabe que uma função pode chamar a si mesma e parar num caso base. Agora vem o que a recursão faz de verdade quando é bem usada: quebrar um problema grande em metades (dividir para conquistar), enxergar o trabalho total numa árvore de chamadas, tentar caminhos e voltar quando dão errado (backtracking) e decidir com clareza quando a recursão vale mais que um laço. São as técnicas por trás do merge sort, da busca binária e da solução de labirintos.

• Dividir para conquistar: quebrar, resolver e juntar
• A árvore de recursão: enxergar o trabalho total
• Backtracking: tentar um caminho e voltar
• Recursão ou iteração: qual escolher

No intermediário você ordenou com bolha, seleção e inserção. Funcionam, mas ficam lentos quando a lista cresce, porque comparam quase tudo com quase tudo. Este módulo mostra a virada de chave: aplicar dividir para conquistar à ordenação. O merge sort divide a lista pela metade e intercala as metades ordenadas. O quick sort escolhe um pivô e particiona. Os dois chegam a O(n log n), a faixa que dá conta de milhões de itens, e no fim você aprende a escolher qual usar.

• Por que O(n log n) ganha de O(n ao quadrado)
• Merge sort: dividir e intercalar
• Quick sort: pivô e partição
• Escolher o algoritmo certo

A recursão é elegante, mas ingênua ela pode ser um desperdício assustador: o Fibonacci recursivo refaz o mesmo cálculo milhões de vezes. Este módulo mostra o problema, a cura e a filosofia por trás dela. A memoização guarda cada resultado numa tabela e reusa em vez de recalcular. A marca que pede essa técnica são os subproblemas sobrepostos, o mesmo pedacinho aparecendo de novo e de novo. E a programação dinâmica vira o jogo de cabeça para baixo: em vez de descer quebrando o problema, sobe montando a resposta a partir dos casos pequenos, como quem conta os degraus de uma escada.

• Recalcular à toa: o Fibonacci ingênuo
• Memoização: anotar para não recalcular
• Subproblemas sobrepostos: a marca que pede a técnica
• A ideia da programação dinâmica: de baixo para cima

No intermediário você usou o dicionário como uma caixa mágica: dá a chave, recebe o valor, quase na hora. Este módulo abre a caixa. Por dentro há um vetor comum e uma função hash que transforma a chave num número de posição, mandando a busca direto ao lugar certo em vez de olhar item por item. Você vai entender a função de dispersão, o problema das colisões e as duas saídas clássicas (encadeamento e sondagem), e por fim por que tudo isso resulta num custo O(1) em média, e quando esse quase instantâneo começa a falhar.

• A tabela hash: o dicionário por dentro
• A função hash: espalhar bem as chaves
• Colisões: quando duas chaves querem o mesmo balde
• Por que a busca é quase instantânea

Nem todo programa é só cálculo. Uma catraca, um semáforo, o campo de senha e a tela de um jogo têm uma coisa em comum: guardam uma situação atual e mudam de situação segundo regras fixas quando algo acontece. Essa ideia tem nome, máquina de estado, e é uma das ferramentas mais úteis para domar a lógica confusa dos if aninhados. Este módulo ensina a enxergar estados e transições, a modelar um semáforo, a validar entradas como um autômato e a organizar as telas de um jogo.

• Estados e transições: a situação que o sistema guarda
• Modelar um semáforo: estado atual mais evento
• Validar com uma máquina: a entrada como autômato
• O jogo como máquina de estado: telas e eventos

Um programa que funciona resolve o problema de hoje; um programa bem organizado aguenta a mudança de amanhã. Este módulo ensina a projetar: dividir o código em módulos com uma responsabilidade cada, esconder o COMO atrás de uma interface simples, medir acoplamento e coesão para saber quando uma peça está saudável, e definir invariantes, as promessas que uma estrutura mantém sempre. É a diferença entre empilhar código e construir algo que você consegue mudar sem medo.

• Dividir o programa em módulos
• Interface e implementação: usar sem saber o como
• Acoplamento e coesão: a saúde de um módulo
• Invariantes: a promessa que o código mantém

Um dado pode ser mudado no lugar ou copiado com a alteração, deixando o original intacto. Uma função pode só devolver um resultado ou também mexer no mundo lá fora, salvando um arquivo ou mandando um e-mail. Escolher bem entre essas opções é o que separa código confuso de código que se testa em segundos e roda em paralelo sem susto. Este módulo destrincha mutável x imutável, a função pura a fundo, o efeito colateral isolado na borda e a previsibilidade que abre caminho para a concorrência.

• Mutável ou imutável: mudar no lugar ou copiar
• Função pura a fundo: só entra e sai
• Efeito colateral controlado: isolar na borda
• Previsibilidade e concorrência: rodar em paralelo

Chegou a hora de juntar as peças. Neste projeto você constrói um Mapa de Rotas: um programa que acha o caminho entre dois pontos de uma rede. Primeiro modela a rede como um grafo, depois acha o menor caminho com busca em largura usando uma fila e um conjunto de visitados, monta o programa inteiro e, por fim, traduz o pseudocódigo para uma linguagem de verdade. É o encerramento da Trilha Lógica, e a ponte para escrever código em uma linguagem.

• O projeto: Mapa de Rotas
• Achar o menor caminho com busca em largura
• Montando o programa completo
• Do pseudocódigo à linguagem