Glossário do Curso de Lógica de Programação Avançado

Todos os termos do curso em um só lugar, com definições simples. Use a busca para achar rápido.

Acesso direto por índice: A capacidade do vetor de chegar a qualquer posição num único passo, calculando onde ela está a partir do índice. Chegar ao item 0 ou ao item 900 custa o mesmo. A lista ligada não tem isso: chega a uma posição percorrendo a corrente.
Acesso sequencial: O jeito da lista ligada de alcançar um valor: seguindo as ligações desde a cabeça, nó por nó. Chegar ao décimo nó custa dez passos. É o oposto do acesso direto do vetor, e a principal desvantagem da lista.
Acoplamento: O grau de dependência entre módulos. Alto acoplamento é ruim: uma peça conhece detalhes demais da outra, e mudar uma quebra a outra. Baixo acoplamento é o alvo: as peças conversam por interfaces enxutas e sabem o mínimo umas das outras, então podem mudar de forma independente.
Algoritmo: Uma sequência clara e finita de passos que resolve um problema ou realiza uma tarefa. Enquanto a estrutura de dados guarda a informação, o algoritmo é o método que age sobre ela: buscar, ordenar, percorrer, transformar. Busca em largura e ordenação são exemplos de algoritmos.
Altura da árvore: O comprimento do caminho mais longo da raiz até uma folha, contado em ligações. Uma árvore com só a raiz tem altura 0. Uma árvore baixa e larga é rasa; uma árvore alta e fina se aproxima de uma lista. A altura influencia a rapidez das buscas.
Aresta: A ligação entre dois vértices de um grafo. Representa uma relação: uma amizade, uma estrada, um link, uma transição. Se dois vértices têm uma aresta entre eles, dizemos que são vizinhos ou adjacentes.
Árvore binária: Uma árvore em que todo nó tem no máximo dois filhos: um filho à esquerda e um filho à direita. Um nó pode ter zero, um ou dois filhos, mas nunca três ou mais. É a árvore mais estudada porque a limitação a dois lados simplifica algoritmos e cria estruturas eficientes.
Árvore de busca binária (BST): Uma árvore binária com uma regra de ordem: para cada nó, todos os valores da subárvore esquerda são menores que ele e todos os da direita são maiores. Essa organização permite buscar, inserir e remover valores descendo por comparações, cortando o conjunto pela metade a cada passo quando a árvore está equilibrada.
Árvore de recursão: Desenho que representa todas as chamadas de uma função recursiva: a chamada inicial é a raiz, e cada chamada que ela faz é um filho. Ler a árvore revela quantas chamadas acontecem e quão fundo elas vão, o que estima o custo total do algoritmo.
Autômato de estados: Uma máquina de estado usada para reconhecer se uma sequência de símbolos (as letras de um texto, por exemplo) segue um padrão. Cada símbolo lido dispara uma transição. A palavra autômato acentua esse uso de leitura passo a passo, muito comum na validação de formatos e na busca de padrões.
Backtrack (voltar): O ato de recuar para o vértice anterior quando o caminho atual não tem mais para onde ir. É o movimento que dá à busca em profundidade a chance de tentar as saídas que ainda não foram exploradas, sem perder o rastro de onde já esteve.
Backtracking: Técnica de resolver problemas experimentando caminhos: escolhe uma opção, avança, e se chega a um beco sem saída, desfaz a última escolha e tenta a próxima. Explora as possibilidades como quem anda num labirinto, voltando sempre que a rota não leva ao objetivo.
Balanceamento com pilha: Técnica que usa uma pilha para verificar se uma expressão está balanceada: cada abre é empilhado e cada fecha desempilha o abre correspondente. Se sobra ou falta algo no fim, ou se um fecha não casa com o topo, a expressão está desbalanceada.
Balde (slot): Cada posição do vetor interno de uma tabela hash. A função de dispersão manda cada chave para um balde. Guardar é colocar o par chave-valor no balde calculado; buscar é ir ao balde calculado e conferir. O nome balde ajuda a imaginar que, se precisar, mais de uma coisa pode cair ali.
Beco sem saída (poda): Ponto em que a tentativa atual não pode dar certo, seja porque viola uma regra, seja porque não há para onde ir. Reconhecê-lo cedo e voltar (podar) evita explorar um ramo inútil, o que faz o backtracking ser muito mais rápido do que testar todas as combinações às cegas.
Busca em largura: Algoritmo que explora um grafo por camadas: primeiro visita a origem, depois todos os vizinhos dela, depois os vizinhos dos vizinhos, e assim por diante. Por avançar de camada em camada, a primeira vez que ela alcança o destino é pelo caminho mais curto em número de passos.
Busca em largura (BFS): Forma de percorrer um grafo em ondas a partir de um vértice inicial: primeiro os vizinhos diretos, depois os vizinhos deles, e assim por diante. Usa uma fila para guardar a ordem de visita. A sigla vem do inglês Breadth-First Search.
Busca em profundidade (DFS): Forma de percorrer um grafo que segue um caminho até o fundo antes de tentar outro. Ao chegar num vértice sem vizinhos novos, ela volta ao anterior e tenta outra saída. Usa uma pilha, muitas vezes a própria pilha de chamadas da recursão. A sigla vem de Depth-First Search.
Busca por comparação: Achar um valor na BST comparando-o com o nó atual: se for igual, encontrou; se for menor, desce à esquerda; se for maior, desce à direita. Cada comparação elimina um ramo inteiro, o que torna a busca muito mais rápida que percorrer tudo, desde que a árvore esteja bem distribuída.
Cabeça da lista: A referência para o primeiro nó da lista ligada. É o único ponto de entrada: a partir da cabeça você alcança todos os outros nós seguindo as ligações. Perder a cabeça é perder a lista inteira, porque não há como voltar ao começo.
Cache: Uma memória rápida onde se guardam resultados já obtidos para reusar depois. Na memoização, o cache costuma ser uma tabela em que a chave é a entrada (por exemplo n) e o valor é a resposta já calculada para aquela entrada.
Caminho mais curto em passos: A rota entre dois vértices com o menor número de arestas, sem considerar pesos ou distâncias. Cada passo conta igual. Num labirinto sem atalhos ponderados, é o menor número de casas a atravessar; numa rede social, o menor número de intermediários.
Ciclo: Um caminho num grafo que sai de um vértice e volta a ele passando por arestas distintas. Onde há ciclo, é possível dar uma volta e retornar ao ponto de partida. Um grafo sem nenhum ciclo é chamado de acíclico, e a árvore é o exemplo clássico.
Ciclo de estados: Uma sequência de estados que volta ao início, como verde, amarelo, vermelho e de novo verde no semáforo. O ciclo se repete indefinidamente, cada volta disparada pelos eventos na ordem certa. Nem toda máquina é cíclica, mas a do semáforo é um exemplo limpo de ciclo.
Coesão: O grau de foco de um módulo num único assunto. Alta coesão é bom: tudo dentro do módulo trabalha para o mesmo objetivo. Baixa coesão é ruim: o módulo é uma gaveta de bagunça com funções que nada têm a ver umas com as outras, difícil de nomear e de entender.
Colisão: O caso em que duas chaves diferentes recebem o mesmo índice da função hash e, portanto, disputam o mesmo balde. Não é um defeito da função, é uma consequência de haver mais chaves possíveis do que posições no vetor. Toda tabela hash precisa de uma regra para resolver colisões.
Concorrência: Situação em que várias tarefas avançam ao mesmo tempo, ou intercaladas, dentro do mesmo programa. Aproveita máquinas com vários núcleos para fazer mais em menos tempo, mas cria o risco de tarefas disputarem o mesmo dado.
Condição de corrida: Bug que surge quando o resultado depende da ordem, imprevisível, em que tarefas concorrentes leem e escrevem um dado compartilhado. Como duas mãos mexendo no mesmo caderno ao mesmo tempo, o valor final vira uma loteria difícil de reproduzir.
Conjunto de visitados: Uma coleção que anota quais vértices já foram vistos durante a busca. Antes de entrar num vértice, o algoritmo consulta esse conjunto: se o vértice já está lá, ele é ignorado. É o que impede a busca de voltar em círculos.
Dado imutável: Dado que não muda depois de criado. Para alterar, você não mexe no original: cria uma cópia nova com a diferença desejada. O valor antigo continua exatamente como estava, o que evita mudanças por acidente à distância.
Dado mutável: Dado que pode ser alterado no próprio lugar depois de criado. Acrescentar, remover ou trocar um valor muda o objeto original, e todos os trechos que apontam para ele passam a ver a mudança. Listas costumam ser mutáveis na maioria das linguagens.
De baixo para cima: Estratégia de começar pelos casos base, já conhecidos, e ir preenchendo uma tabela em direção ao caso maior. O oposto da recursão memoizada, que parte do caso grande e desce. Os dois chegam à mesma resposta por caminhos invertidos.
Desenfileirar (dequeue): A operação que remove e devolve o elemento da frente da fila, o mais antigo dos que esperam. Equivale a ser chamado no guichê. Em inglês é chamada de dequeue. Sempre remove pela frente, nunca do meio ou do fim.
Distribuição uniforme: A propriedade de espalhar as chaves de forma equilibrada pelo vetor, sem concentrar muitas na mesma posição. Quando a distribuição é uniforme, cada escaninho recebe mais ou menos a mesma quantidade de chaves, e a tabela mantém a busca rápida. Distribuição ruim amontoa chaves e derruba o desempenho.
Dividir para conquistar: Estratégia de resolver um problema grande partindo-o em subproblemas menores do mesmo tipo, resolvendo cada um (em geral por recursão) e combinando as respostas parciais numa resposta final. Aparece na busca binária, no merge sort e no quick sort.
Efeito colateral: Qualquer coisa que uma função faz além de devolver um resultado a partir dos argumentos: escrever na tela, salvar um arquivo, alterar um dado compartilhado, chamar a rede, ler o relógio. Efeitos são necessários, mas quando espalhados tornam o programa imprevisível.
Em-ordem, pré-ordem e pós-ordem: Os três percursos por profundidade de uma árvore binária. Em-ordem visita o filho esquerdo, depois a raiz, depois o direito. Pré-ordem visita a raiz primeiro, depois esquerdo e direito. Pós-ordem visita esquerdo e direito primeiro e a raiz por último. Muda só a posição da raiz na visita.
Empilhar (push) e desempilhar (pop): As duas operações centrais da pilha. Empilhar (push, em inglês) coloca um novo item no topo. Desempilhar (pop) retira o item do topo e o devolve. Ambas mexem exclusivamente no topo, mantendo a regra LIFO.
Encadeamento: Estratégia de tratar colisões guardando, em cada balde, uma lista com todos os pares que caíram ali. Quando duas chaves colidem, ambas ficam na mesma lista do balde. Buscar é ir ao balde e percorrer sua lista curta. Também chamado de encadeamento separado.
Enfileirar (enqueue): A operação que adiciona um elemento no fim da fila. Equivale a chegar e ir para o final da fila do banco. Em inglês é chamada de enqueue. Nunca insere no meio nem na frente: sempre no fim.
Escolher a estrutura: A decisão de projeto que casa o comportamento de uma estrutura com o que o problema pede. Entre pilha e fila, a pergunta central é: o problema quer atender o último que chegou (pilha) ou o primeiro que chegou (fila)?
Espiar o topo (peek): Operação que mostra qual é o item do topo sem removê-lo da pilha. Serve para consultar quem está por cima antes de decidir o que fazer. Ao contrário do desempilhar, o espiar não altera a pilha.
Estado: A situação atual em que um sistema se encontra, escolhida de um conjunto pequeno e bem definido de situações possíveis. Numa catraca, os estados são travada e liberada. O sistema está sempre em exatamente um estado por vez, e é esse estado que decide como ele reage ao que acontece.
Estado de aceitação: O estado (ou estados) em que o autômato deve terminar para considerar a entrada válida. Ao acabar de ler o texto, se a máquina parou num estado de aceitação, a entrada casa com o padrão; se parou em outro estado, a entrada é rejeitada. Também chamado de estado final.
Estado de tela: Cada tela ou modo distinto de um aplicativo ou jogo, visto como um estado da máquina: menu, jogando, pausa, fim. O sistema mostra e reage segundo o estado de tela atual, e só troca de tela quando um evento dispara a transição correspondente.
Estouro de pilha (stack overflow): Erro que acontece quando a pilha de chamadas cresce além do limite disponível, em geral por chamadas que nunca param, como uma recursão sem caso base. A pilha enche até estourar, e o programa é interrompido.
Estrutura de dados: A forma como a informação fica organizada na memória para ser guardada e acessada. Lista, pilha, fila, árvore, tabela hash e grafo são estruturas diferentes, cada uma boa para um tipo de acesso. Escolher a estrutura certa costuma resolver metade do problema.
Estruturas vs algoritmos: A divisão que organiza o curso. As estruturas de dados (pilha, fila, lista, árvore, hash, grafo) respondem à pergunta onde e como os dados ficam guardados. Os algoritmos (busca, ordenação, percurso) respondem à pergunta como agir sobre esses dados. As duas famílias se combinam.
Evento de interface: Uma ação que pode disparar uma transição entre telas: tocar num botão, apertar pausa, o personagem perder toda a vida, o tempo acabar. É o gatilho; o estado atual decide se aquele evento tem efeito e para qual tela ele leva.
Expressão balanceada: Expressão em que todo símbolo de abertura tem um fechamento correspondente, na ordem correta e do tipo certo. Por exemplo, ([]) é balanceada, mas ([)] e (( não são. É requisito básico de fórmulas matemáticas e de código-fonte.
Fase de combinação: O passo em que as respostas dos pedaços menores são reunidas na resposta do problema todo. Em algoritmos como o merge sort é onde mora o trabalho de verdade: intercalar duas metades já ordenadas numa única lista ordenada.
Fator de carga: A razão entre a quantidade de itens guardados e o número de posições do vetor. Um fator de carga baixo (vetor com folga) mantém poucos itens por balde e a busca rápida; um fator alto (vetor lotado) aumenta as colisões e derruba o desempenho. Muitas tabelas crescem o vetor quando esse fator passa de um limite.
Fibonacci: Sequência clássica em que cada número é a soma dos dois anteriores: 0, 1, 1, 2, 3, 5, 8, 13 e assim por diante. Os dois primeiros (0 e 1) são o caso base; do terceiro em diante, fib de n é fib de n menos 1 mais fib de n menos 2.
Fila (FIFO): Estrutura de dados em que o primeiro elemento a entrar é o primeiro a sair. FIFO vem do inglês First In, First Out. É o modelo da fila do banco: quem chegou antes é atendido antes. O oposto da pilha, que é LIFO.
Fila de prioridade: Variação da fila em que cada elemento carrega uma prioridade, e o próximo a sair é o de maior prioridade, não o que chegou primeiro. Quando dois têm a mesma prioridade, o critério de desempate costuma ser a ordem de chegada.
Filho esquerdo e filho direito: Os dois possíveis filhos de um nó numa árvore binária, identificados pela posição. A esquerda e a direita não são intercambiáveis: numa árvore de busca, o lado esquerdo guarda valores menores e o direito, maiores. Trocar os lados muda o significado da árvore.
Frente e fim da fila: As duas pontas de uma fila. O fim é onde novos elementos entram (o final da fila do banco). A frente é onde os elementos saem (o guichê). Diferente da pilha, que mexe só numa ponta, a fila trabalha com as duas.
Função hash: A regra que transforma uma chave num índice do vetor. Recebe uma chave qualquer e devolve sempre um número inteiro dentro da faixa de posições. Uma boa função hash é rápida de calcular, sempre gera o mesmo índice para a mesma chave e distribui chaves diferentes por posições variadas.
Função pura: Função que satisfaz duas condições: o resultado depende apenas dos argumentos recebidos, e ela não causa nenhum efeito no mundo externo. Consequência prática: as mesmas entradas produzem sempre a mesma saída, sem surpresas.
Garantia do código: O que um módulo assegura a quem o usa: uma propriedade em que se pode confiar sem verificar toda vez. A invariante é a garantia por dentro; ela permite que quem usa o módulo assuma certas coisas como certas, o que simplifica o programa inteiro que depende dele.
Grafo acíclico: Um grafo que não tem nenhum ciclo: não existe volta que retorne ao ponto de partida. Toda árvore é acíclica. Muitos problemas ficam mais simples nesses grafos, porque a busca nunca corre o risco de reencontrar um vértice por outro caminho.
Grafo dirigido: Grafo em que cada aresta tem um sentido, representado por uma seta. A ligação vale só na direção da seta: de A para B não implica de B para A. Serve para relações de mão única, como seguir alguém numa rede ou uma rua de sentido único.
Grau de separação: Numa rede modelada como grafo, a distância entre duas pessoas medida em número de arestas (amizades) no menor caminho entre elas. A ideia dos seis graus de separação diz que quase todos estão a poucos passos de qualquer outro na rede.
Implementação: O como interno: o código que faz a interface funcionar por baixo. Estruturas de dados, algoritmos e detalhes que ficam escondidos. Enquanto a interface continua a mesma, a implementação pode mudar (ficar mais rápida, corrigir um erro) sem afetar quem usa o módulo por fora.
In-place: Algoritmo que ordena reorganizando os elementos dentro da própria lista, usando pouca ou nenhuma memória extra além da entrada. O quick sort é in-place; o merge sort clássico não é, porque cria listas novas para intercalar.
Intercalar (merge): Juntar duas listas já ordenadas numa única lista ordenada, comparando os elementos da frente de cada uma e escolhendo sempre o menor para colocar no resultado. Como é preciso olhar cada elemento só uma vez, intercalar duas listas de tamanho total n custa apenas n passos.
Interface e implementação: A interface é o conjunto de operações que uma estrutura oferece a quem a usa, o contrato público. A implementação é o código concreto que cumpre esse contrato por dentro. A mesma interface pode ter várias implementações diferentes, todas válidas se respeitarem o contrato.
Interface pública: O conjunto de funções e comportamentos que um módulo oferece para o mundo de fora usar. É o contrato: os nomes, o que cada um recebe e o que devolve. Quem usa o módulo depende só disso. Uma boa interface é pequena, clara e estável, porque quebrar a interface quebra todos os que dependem dela.
Invariante: Uma condição que uma estrutura ou função mantém sempre verdadeira, antes e depois de cada operação da interface. Na árvore de busca binária, a invariante é que os menores ficam à esquerda e os maiores à direita. É a promessa que o módulo faz e nunca quebra enquanto usado pela interface.
Iteração: Repetir um bloco de código com um laço (enquanto, para), mantendo o estado em variáveis que você atualiza a cada volta. É a alternativa à recursão para repetição; não usa a pilha de chamadas, então não corre o risco de estourá-la por profundidade.
LIFO: Sigla de Last In, First Out, ou último a entrar, primeiro a sair. É a regra que define a pilha: quem chegou por último fica no topo e sai antes de todos os que chegaram antes. O oposto é FIFO, a regra da fila, que você verá no próximo módulo.
LIFO x FIFO: Os dois comportamentos opostos de ordem. LIFO (pilha) atende o último a entrar; inverte a ordem de chegada, útil para desfazer e voltar. FIFO (fila) atende o primeiro a entrar; preserva a ordem, útil para justiça e cronologia.
Lista circular: Variação em que o último nó, em vez de apontar para o nada, aponta de volta para o primeiro, formando um anel. Não tem fim natural, então quem percorre precisa de outra condição de parada, como voltar ao ponto de partida.
Lista de adjacência: Forma de guardar um grafo em que cada vértice tem uma lista com os seus vizinhos. Ocupa espaço proporcional ao número de arestas e é eficiente para grafos esparsos, aqueles com poucas ligações por vértice.
Lista duplamente ligada: Variação em que cada nó guarda duas ligações: uma para o próximo e outra para o anterior. Permite percorrer a corrente nos dois sentidos e facilita remover um nó tendo só ele em mãos, já que dá para alcançar o anterior direto.
Mapa de pais: Tabela que guarda, para cada vértice visitado, de quem ele foi descoberto na busca. Se Parque foi alcançado a partir de Norte, o mapa de pais diz que o pai de Parque é Norte. Seguindo os pais do destino para trás, chega-se à origem e se reconstrói o caminho.
Matriz de adjacência: Grade quadrada em que a célula da linha A com a coluna B guarda se existe (1) ou não (0) uma aresta de A para B. Consulta se dois vértices são vizinhos em um passo, mas ocupa espaço proporcional ao número de vértices ao quadrado.
Memoização: Técnica de guardar o resultado de um cálculo numa tabela na primeira vez que ele é feito e, nas próximas, devolver o valor guardado em vez de recalcular. O nome vem de memorando, uma nota; a função passa a anotar o que já descobriu.
Merge sort: Algoritmo de ordenação que divide a lista pela metade de forma recursiva até sobrarem pedaços de um elemento (já ordenados por definição) e depois intercala esses pedaços de volta, sempre juntando duas partes ordenadas numa parte maior ordenada. Custo O(n log n) garantido, no melhor e no pior caso.
Modelagem: O ato de traduzir um problema do mundo real para uma estrutura que o programa entende. No Mapa de Rotas, modelar é decidir que cada ponto da rede vira um vértice e cada ligação direta entre dois pontos vira uma aresta. Uma boa modelagem torna o algoritmo quase óbvio; uma ruim complica tudo.
Modelar com grafo: Transformar um problema real num grafo, decidindo o que cada vértice representa e o que cada aresta representa. É a etapa criativa que antecede o algoritmo: escolher bem vértice e aresta faz o problema virar caminhada num grafo.
Módulo: Uma parte do programa que agrupa funções e dados ligados a uma mesma tarefa, com um limite claro em volta. Pode ser um arquivo, uma pasta ou um conjunto de funções relacionadas. A ideia é que cada módulo cuide de um assunto e seja usado pelos outros por fora, sem que ninguém precise conhecer suas entranhas.
Nó: A peça básica de uma lista ligada. Guarda duas coisas: um valor (o dado que interessa) e uma ligação, que é a referência para o próximo nó da corrente. O último nó aponta para o nada, sinalizando o fim da lista.
Nó (raiz, pai, filho, folha): Cada elemento de uma árvore é um nó. A raiz é o nó do topo, o único sem pai. Um nó que aponta para outros é o pai deles, e eles são seus filhos. Um nó sem filhos, na ponta de um ramo, é uma folha. Todo nó, menos a raiz, tem exatamente um pai.
Nó anterior: Numa lista ligada simples, o nó que aponta para o nó que você quer inserir depois dele ou remover. Como as ligações só vão para frente, para mexer num nó você precisa ter em mãos o anterior, pois é a ligação dele que será religada.
Núcleo puro e borda impura: Padrão de organização em que a lógica que decide fica em funções puras (o núcleo) e os efeitos ficam numa camada fina em volta (a borda). O núcleo calcula o que fazer; a borda apenas executa. Também chamado de núcleo funcional com casca imperativa.
O(n ao quadrado): Custo que cresce com o quadrado do tamanho da entrada. Se a lista dobra, o trabalho fica quatro vezes maior; se multiplica por dez, o trabalho cresce cem vezes. É a marca dos métodos simples de ordenação, como bolha, seleção e inserção, que comparam quase cada par de elementos.
O(n log n): Custo de um pouco mais que linear. O fator log n cresce muito devagar: dobrar a lista soma só uma unidade a esse fator. É a faixa dos métodos eficientes de ordenação por comparação, como merge sort e quick sort, e é o melhor que se consegue ordenando por comparações.
Ordenação estável: Ordenação que preserva a ordem original entre elementos de mesmo valor. Se dois itens têm a mesma chave, o que vinha antes continua antes depois de ordenar. Importa quando se ordena por uma chave sem querer bagunçar uma ordenação anterior, como ordenar por sobrenome mantendo a ordem por nome.
Partição: Passo do quick sort que reorganiza a lista em torno do pivô: todos os elementos menores ficam à esquerda dele, os maiores à direita. Ao terminar, o pivô está exatamente na posição que teria na lista ordenada, e nunca mais precisa ser movido.
Percurso de árvore: Visitar todos os nós de uma árvore numa ordem definida. Numa lista, há uma ordem óbvia; numa árvore ramificada, não. Os percursos mais usados numa árvore binária são três: em-ordem, pré-ordem e pós-ordem, que diferem no momento em que o nó atual é visitado em relação a seus filhos.
Peso da aresta: Um número associado a uma aresta que mede o custo daquela ligação: distância, tempo, preço, força da relação. Um grafo com peso permite perguntar não só se há caminho, mas qual o caminho mais barato ou mais curto.
Pilha (stack): Estrutura de dados que guarda itens uns sobre os outros e obedece à regra LIFO: o último item colocado é o primeiro a ser retirado. Só o item do topo pode ser lido ou removido. É como uma pilha de pratos ou uma pilha de livros na mesa.
Pilha de chamadas (call stack): A pilha que o computador usa para controlar as chamadas de funções. Quando uma função chama outra, a atual é empilhada com o ponto de retorno; quando a chamada termina, ela é desempilhada e a execução volta de onde parou. É o que permite funções chamarem funções e sempre voltarem ao lugar certo.
Prioridade: O valor de importância ou urgência associado a um elemento na fila de prioridade. Pode ser um número (quanto maior, mais urgente) ou um nível (alta, média, baixa). É a prioridade, não a chegada, que decide a ordem de atendimento.
Profundidade da recursão: O número de chamadas empilhadas ao mesmo tempo, ou seja, a altura da árvore de recursão. Cada nível fica esperando o de baixo terminar. Profundidade demais pode estourar a pilha de chamadas do programa (o erro de estouro de pilha).
Programação dinâmica: Técnica para resolver problemas com subproblemas sobrepostos montando a resposta a partir dos casos menores, guardados numa tabela. Na forma de baixo para cima, resolve primeiro os pequenos e combina até chegar ao grande, sem recursão.
Projetar uma solução: Ir além de fazer o programa funcionar: decidir como os dados são guardados e como são processados, pensando em desempenho, clareza e mudança futura. É a diferença entre um código que roda hoje com dez itens e um que continua rápido e legível com dez milhões.
Quick sort: Algoritmo de ordenação que escolhe um elemento como pivô, particiona a lista em menores e maiores que o pivô e aplica o mesmo processo em cada parte. Costuma ser o mais rápido na prática (custo médio O(n log n)), mas pode degradar para O(n ao quadrado) se o pivô cair sempre mal.
Recálculo redundante: Refazer um cálculo cujo resultado já foi obtido antes, sem necessidade. Na recursão ingênua do Fibonacci, o mesmo valor (como fib de 3) é calculado do zero muitas vezes, uma em cada galho da árvore de chamadas que precisa dele.
Recursão em cauda: Caso especial em que a chamada recursiva é a última coisa que a função faz, sem cálculo pendente depois dela. Algumas linguagens transformam essa forma num laço automaticamente (otimização de chamada em cauda), eliminando o custo de pilha. Quando existe, aproxima a recursão da eficiência do laço.
Religar ponteiros: Mudar para onde as ligações apontam, sem tocar nos valores. Inserir ou remover na lista ligada é essencialmente isso: reapontar uma ou duas ligações para encaixar ou tirar um nó da corrente. O trabalho é fixo, não depende do tamanho da lista.
Responsabilidade única: O princípio de que cada módulo (ou função) deve ter um motivo só para mudar, porque cuida de uma coisa só. Se calcular imposto e desenhar o boleto vivem juntos, uma mudança na aparência arrisca quebrar a conta. Separar dá a cada parte um trabalho e uma fronteira.
Sintaxe: O conjunto de regras de escrita de uma linguagem: quais palavras usar, como pontuar, como abrir e fechar blocos. Duas linguagens podem expressar a mesma lógica com sintaxes bem diferentes. A sintaxe muda de linguagem para linguagem; a lógica por baixo é a mesma.
Subestrutura ótima: Propriedade de um problema cuja melhor solução pode ser montada a partir das melhores soluções dos seus pedaços menores. Se a resposta do todo depende das respostas das partes, resolver as partes e combiná-las resolve o todo.
Subproblemas sobrepostos: Característica de um problema em que, ao ser quebrado em partes, as mesmas partes menores reaparecem muitas vezes. É a marca que faz a memoização valer a pena: guardar essas partes evita recalculá-las. O Fibonacci é o exemplo canônico.
Tabela de transições: A lista completa das regras de uma máquina de estado, no formato estado atual mais evento leva ao próximo estado. Ela é a fonte de verdade da máquina: se uma combinação de estado e evento não está na tabela, nada acontece. É o mesmo diagrama de setas escrito em forma de tabela.
Tabela hash: Estrutura que associa chaves a valores usando um vetor e uma função de dispersão. Em vez de procurar a chave percorrendo a coleção, a função calcula em qual posição do vetor a chave mora, e a estrutura vai direto lá. É a implementação mais comum do dicionário (também chamado de mapa ou tabela de associação).
Tempo constante (O(1)): Custo que quase não cresce com o tamanho da coleção: seja com dez ou dez milhões de itens, a operação leva mais ou menos o mesmo número de passos. Na tabela hash, buscar pela chave é O(1) em média porque o cálculo do índice leva direto ao balde, sem varrer os dados.
Teste de mesa: Executar o programa na mão, em papel ou de cabeça, anotando o valor de cada variável a cada passo. Serve para conferir a lógica antes de rodar no computador. Num algoritmo de grafo, o teste de mesa acompanha a fila, o conjunto de visitados e o mapa de pais mudando a cada iteração.
Tipo abstrato de dados (TAD): A descrição de uma estrutura pelo que ela faz, e não pelo como faz por dentro. Define as operações disponíveis e como elas se comportam, deixando de fora os detalhes internos. Pilha, fila e lista são exemplos de tipos abstratos: cada um é um contrato de operações.
Traduzir código: Reescrever uma lógica já pensada, como um pseudocódigo, na sintaxe de uma linguagem de programação. Não é reinventar a solução, é transcrever passo a passo cada construção (decisão, laço, estrutura) para a forma que aquela linguagem exige.
Transição: A regra que leva o sistema de um estado para outro quando algo acontece. Uma transição diz: estando no estado A, se acontecer o evento X, vá para o estado B. Sem um evento correspondente, o sistema fica parado no estado em que está.
Transparência referencial: Propriedade de uma expressão que pode ser trocada pelo seu resultado sem mudar o comportamento do programa. Funções puras têm essa propriedade: chamar somar(2, 3) é o mesmo que escrever 5, porque nada mais acontece além de devolver o valor.
Vértice: Cada ponto de um grafo, também chamado de nó. Representa uma coisa da rede: uma pessoa, uma cidade, uma página, um estado. Um grafo é, antes de tudo, um conjunto de vértices que podem ou não estar ligados entre si.
Vértice de origem (predecessor): Para cada vértice descoberto na busca, é o vértice a partir do qual ele foi alcançado. Guardar esse predecessor forma uma trilha de migalhas: seguindo de origem em origem, do destino até o início, você reconstrói o caminho inteiro.