Consulta rápida

Glossário

As palavras novas das aulas, explicadas em uma ou duas frases.

Os termos estão em ordem alfabética. Cada um indica a aula onde aparece pela primeira vez.

Aliasing: Quando dois ponteiros apontam para a mesma variável. Alterar por um deles também muda o que o outro “vê”. Aparece em: Ponteiros
Backtracking: Técnica que testa todas as escolhas possíveis: faz uma escolha, resolve o resto e, ao voltar, desfaz a escolha e experimenta a outra. Aparece em: Funções recursivas
Busca binária: Procura em uma lista ordenada olhando o meio e descartando a metade onde o valor não pode estar. 1 milhão de itens em no máximo 20 passos. Aparece em: Funções recursivas
Caso base: O caso pequeno que uma função recursiva resolve sem chamar a si mesma. É o que faz a recursão parar. Aparece em: Funções recursivas
Ciclo (de uma permutação): Seguindo as setas “posição → onde o elemento deveria estar”, você volta ao ponto de partida. Cada volta é um ciclo. Aparece em: Selection sort
Complexidade e notação O: Forma de dizer como o trabalho cresce com o tamanho n da entrada, sem se prender a segundos. O(n): cresce junto com n. O(n²): dobrar n quadruplica o trabalho. O(log n): cresce muito devagar. Aparece em: Visão geral
Comportamento indefinido: Situação em que a linguagem C não garante nada: o programa pode travar, dar resultado errado ou parecer funcionar. Exemplos: ler fora de um vetor, usar ponteiro solto, estourar um int. Aparece em: Ponteiros
Deslocamento: No insertion sort, copiar um elemento uma posição para a direita para abrir espaço para a chave. Custa uma escrita no vetor. Aparece em: Insertion sort
Desreferenciar: Seguir o endereço guardado em um ponteiro para chegar à variável apontada. Em C, é o *p. Aparece em: Ponteiros
Endereço: O “lugar” de uma variável na memória. Em C, &x dá o endereço de x. Aparece em: Ponteiros
Estabilidade (ordenação estável): Uma ordenação é estável quando elementos empatados mantêm a ordem em que chegaram. Ex.: em um ranking, quem se inscreveu antes continua à frente em caso de empate. Aparece em: Bubble sort
Força bruta: Solução que testa todas as possibilidades, sem esperteza. Costuma ser lenta, mas é ótima para conferir se uma solução rápida está certa. Aparece em: Visão geral
Invariante: Uma garantia que continua verdadeira a cada repetição de um laço. Ex.: no bubble sort, “depois de k passagens, as k últimas posições estão prontas”. Aparece em: Bubble sort
Inversão: Um par de elementos em que o maior aparece antes do menor. Mede o quanto um vetor está bagunçado: um vetor ordenado tem 0 inversões. Aparece em: Bubble sort
Memoização: Guardar o resultado de uma chamada na primeira vez que é calculado e reaproveitá-lo nas vezes seguintes, em vez de recalcular. Aparece em: Funções recursivas
Merge sort: Algoritmo de ordenação que divide o vetor ao meio, ordena cada metade e intercala as duas. Muito mais rápido que os três desta revisão para listas grandes. Aparece em: Bubble sort
NULL: Valor especial de ponteiro que significa “não aponta para nada”. Nunca desreferencie um ponteiro NULL. Aparece em: Ponteiros
Overflow (estouro): Quando o resultado de uma conta não cabe no tipo. Um int de 32 bits vai só até cerca de 2,1 bilhões; passar disso é comportamento indefinido. Aparece em: Funções recursivas
Passagem (bubble sort): Um percurso completo do bubble sort pelo vetor, comparando todos os vizinhos da parte ainda não pronta. Aparece em: Bubble sort
Passagem por valor: Em C, toda função recebe cópias dos argumentos. Para alterar uma variável de quem chamou, passa-se o endereço dela. Aparece em: Struct
Permutação: Uma lista com os números de 0 a n − 1, cada um aparecendo exatamente uma vez, em alguma ordem. Aparece em: Selection sort
Pilha de chamadas: Área da memória onde ficam as chamadas de função em andamento. Cada chamada recursiva ocupa um pedaço até retornar. Aparece em: Funções recursivas
Poda: No backtracking, abandonar um caminho assim que fica claro que ele não leva a nenhuma solução. Aparece em: Funções recursivas
Ponteiro: Variável que guarda um endereço. int *p declara um ponteiro para int. Aparece em: Ponteiros
Ponteiro solto: Ponteiro que aponta para algo que já deixou de existir, como uma variável local de uma função que já retornou. Usá-lo é comportamento indefinido. Aparece em: Ponteiros
Pré-condição: O que precisa ser verdade antes de chamar uma função para que ela funcione. Ex.: “n >= 1” ou “o vetor está ordenado”. Aparece em: Struct
Preenchimento (padding): Bytes vazios que o compilador coloca entre os campos de uma struct para alinhar cada campo na memória. Por isso sizeof de uma struct pode ser maior que a soma dos campos. Aparece em: Struct
Registro (struct): Uma variável que agrupa vários campos relacionados, como nome e nota de um aluno. Em C, é criado com struct. Aparece em: Struct
Stack overflow: Quando a pilha de chamadas enche, normalmente por recursão profunda demais ou sem caso base. O programa é encerrado. Aparece em: Funções recursivas
Vetor k-ordenado: Vetor em que cada elemento está no máximo k posições longe do lugar onde deveria estar. Aparece em: Insertion sort