Quais são as duas fases do bloqueio em duas fases (2PL)?

Crescimento: adquirir bloqueios sem liberá-los. Encolhimento: liberar bloqueios sem adquirir novos. Com bloqueios adequados para leituras e escritas conflitantes, 2PL garante escalonamentos serializáveis por conflito, mas impasses continuam possíveis.

Por que quicksort pode levar Θ(n²) e como a aleatoriedade ajuda?

Partições repetidamente desequilibradas, como escolher sempre a menor chave entre chaves distintas, causam trabalho quadrático. Com chaves distintas ou tratamento adequado de duplicatas, pivôs aleatórios dão tempo esperado O(n log n). A mediana de três é uma heurística útil, não uma garantia para o pior caso.

O que é uma leitura suja e qual primeiro nível padrão a impede?

Ler dados não confirmados de outra transação, independentemente de ela ser depois desfeita. READ COMMITTED e os níveis padrão superiores proíbem leituras sujas.

Como funciona a ordenação por inserção e de que depende seu custo em dados quase ordenados?

Ela insere cada item em um prefixo ordenado. A versão usual com deslocamentos ou trocas adjacentes leva Θ(n+I), sendo I o número de inversões. É linear quando I=O(n); uma entrada pequena não muda o pior caso Θ(n²).

O que torna estável um algoritmo de ordenação?

Itens com chaves iguais mantêm sua ordem relativa original. Merge sort pode ser estável se escolher primeiro o item da esquerda em empates; o quicksort usual no próprio vetor geralmente é instável. A estabilidade depende da implementação.

Como a busca em profundidade detecta um ciclo em um grafo dirigido?

DFS aprofunda a exploração usando recursão ou uma pilha explícita. Uma aresta para um vértice ainda ativo no caminho DFS atual é de retorno e comprova um ciclo dirigido; apontar para qualquer vértice já visitado não basta.

Como se comparam matriz de adjacência e listas de adjacência comuns?

Com V vértices e E arestas, a matriz usa O(V²) espaço e verifica uma aresta em O(1). As listas usam O(V+E); procurar (u,v) em uma lista não ordenada custa O(deg(u)), sendo deg(u) o comprimento dessa lista.

Como a busca em largura encontra caminhos mínimos em um grafo não ponderado?

BFS usa uma fila FIFO e explora por distância em número de arestas. Marcar um vértice ao inseri-lo na fila evita visitas repetidas. O primeiro caminho descoberto até um vértice alcançável tem o menor número de arestas.

Por que árvores B+ são úteis para índices e consultas por intervalo?

A alta ramificação mantém a árvore baixa e reduz acessos a páginas. Chaves ordenadas e folhas encadeadas permitem percorrer intervalos. Índices hash visam buscas por igualdade e não oferecem por si só o mesmo acesso ordenado por intervalo.

O que é uma ordem topológica e como o algoritmo de Kahn a encontra?

Em um DAG, cada aresta u→v coloca u antes de v. Retira-se repetidamente um vértice de grau de entrada zero, removendo suas arestas de saída e enfileirando os novos vértices de grau zero. Se saírem menos de V vértices, há um ciclo dirigido.

Como diferem memoização e programação dinâmica de baixo para cima?

A memoização avalia subproblemas sob demanda, geralmente por recursão, e guarda os resultados. A abordagem de baixo para cima avalia estados quando suas dependências já estão disponíveis, normalmente preenchendo uma tabela.

Como INNER JOIN e LEFT JOIN diferem?

INNER JOIN retorna combinações de linhas que satisfazem a condição de junção. LEFT JOIN também mantém cada linha esquerda sem correspondência, com NULL nas colunas direitas. Várias correspondências podem produzir várias linhas por linha esquerda.

O que significam as propriedades ACID de uma transação?

Atomicidade: todos os efeitos ou nenhum. Consistência: transações corretas preservam restrições e invariantes da aplicação. Isolamento: a concorrência respeita o nível escolhido. Durabilidade: efeitos confirmados sobrevivem às falhas cobertas pelas garantias configuradas.

O que a busca binária exige e quando leva O(log n)?

Ela divide repetidamente o intervalo de busca ao meio em dados ordenados segundo o critério de comparação. Em um vetor com acesso por índice O(1) e comparações de tempo constante, buscar entre n elementos custa O(log n).

Qual é a recorrência para o comprimento da maior subsequência comum (LCS)?

L[i,j] é o comprimento da LCS de prefixos de comprimentos i,j. L[0,j]=L[i,0]=0. Se os últimos caracteres coincidem, L[i,j]=1+L[i−1,j−1]; senão, L[i,j]=max(L[i−1,j],L[i,j−1]). A tabela completa usa O(mn) tempo e espaço.

O que exigem a primeira, segunda e terceira formas normais?

1FN: valores atômicos. 2FN: 1FN e nenhum atributo não primo depende de uma parte própria de qualquer chave candidata. 3FN: 1FN e, em toda dependência não trivial X→A, X é superchave ou A é primo. Um atributo primo pertence a alguma chave candidata.

O que é uma leitura fantasma e como evitá-la?

Repetir uma consulta com predicado encontra outro conjunto de linhas correspondentes após alterações confirmadas por outra transação. SERIALIZABLE a impede no modelo padrão; algumas implementações, como REPEATABLE READ do PostgreSQL, também a impedem em um nível inferior.

Como Bellman–Ford trata arestas negativas e detecta um ciclo negativo alcançável?

Relaxa todas as arestas até V−1 vezes. Uma melhora adicional a partir de um vértice alcançável revela um ciclo negativo alcançável da origem. O pior caso custa O(VE); vértices alcançáveis desse ciclo não têm custo mínimo finito.

Como o WAL apoia a durabilidade do PostgreSQL com commit síncrono normal?

Os registros necessários chegam ao armazenamento durável antes da confirmação do commit e antes da gravação das páginas alteradas. Após uma falha, o WAL pode reproduzir alterações ausentes nas páginas. O commit assíncrono pode perder transações recentes já confirmadas.

Como funciona o merge sort padrão para vetores e quais são seus custos?

Ele ordena recursivamente duas metades e as intercala em tempo linear. A versão padrão leva Θ(n log n) tempo e O(n) espaço auxiliar, supondo comparações de tempo constante.

O que é uma leitura não repetível e qual nível padrão a impede?

Ao reler uma linha, seus dados mudaram ou ela desapareceu após outra transação confirmar uma atualização ou exclusão. REPEATABLE READ e SERIALIZABLE impedem essa anomalia.

Quais são o tempo no pior caso e o espaço extra do heapsort no próprio vetor?

Construir o heap custa O(n); as extrações somam O(n log n). Com descida iterativa no vetor de entrada, heapsort leva O(n log n) no pior caso e usa O(1) espaço extra.

Como WHERE e HAVING diferem em uma consulta agrupada?

WHERE filtra linhas de entrada antes do agrupamento. HAVING filtra os grupos resultantes e pode usar condições com agregações, como COUNT(*)>1.

Por que a programação dinâmica é útil em muitos problemas de otimização?

A subestrutura ótima permite expressar um ótimo por meio de ótimos dos subproblemas. Quando eles se sobrepõem, guardar as respostas evita trabalho repetido. Os estados e a recorrência precisam representar corretamente o problema original.

Quando Dijkstra é válido e qual é um custo usual com heap?

Com pesos não negativos, ele fixa repetidamente o vértice com menor distância provisória. Uma implementação com listas de adjacência e heap binário mínimo leva O((V+E) log V). Arestas negativas podem invalidar o argumento de distância definitiva.

Como um algoritmo guloso difere da programação dinâmica?

O guloso assume uma escolha local e exige prova de que essas escolhas preservam um ótimo. A programação dinâmica compara alternativas por uma recorrência e reutiliza resultados. O ótimo global exige modelo e recorrência corretos, não apenas o nome “DP”.

Quando counting sort ou radix sort podem levar tempo linear?

Counting sort custa O(n+k) para n chaves em um intervalo de k valores. Radix sort com d passadas estáveis por dígitos e base b custa O(d(n+b)). Só são lineares quando esses parâmetros permitem; exploram a estrutura das chaves além das comparações.

Qual é uma ordem lógica simplificada de processamento de uma consulta SQL SELECT?

Sem CTEs, funções de janela nem operações de conjuntos: FROM/JOIN → WHERE → GROUP BY e agregações → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET. É um modelo lógico, não necessariamente a ordem física escolhida pelo otimizador.

Como Kruskal e Prim constroem uma árvore geradora mínima?

Em um grafo conexo, não dirigido e ponderado, Kruskal considera arestas por peso crescente e usa Union–Find para rejeitar ciclos. Prim expande uma árvore escolhendo uma aresta de peso mínimo que conecta a árvore a um vértice externo.

Como diferem chaves primárias e estrangeiras no PostgreSQL?

A primária identifica linhas por valores únicos e não NULL. A estrangeira exige correspondência com valores da chave referenciada, segundo suas regras de NULL. Pode referenciar uma chave UNIQUE elegível ou uma primária da mesma tabela ou de outra.

Qual é a recorrência padrão da mochila 0/1 com capacidade inteira W?

D[i,w] é o melhor valor usando os primeiros i itens, capacidade w e pesos inteiros positivos wᵢ. D[0,w]=0. Se wᵢ>w, copia-se D[i−1,w]; senão, usa-se max(D[i−1,w],vᵢ+D[i−1,w−wᵢ]). O tempo O(NW) é pseudopolinomial.

Como diferem índices clustered e nonclustered de armazenamento por linhas no SQL Server?

O clustered armazena as linhas em ordem de chave, então há no máximo um por tabela. O nonclustered possui suas próprias chaves e localizadores de linhas e pode incluir outras colunas. Termos e detalhes de armazenamento variam entre sistemas.

Algoritmos, grafos, programação dinâmica e bancos de dados relacionais

32 cartões de revisão de graduação sobre ordenação, algoritmos de grafos, programação dinâmica, SQL, índices e transações. Requer programação básica, estruturas de dados e SQL.

Level: basic
Languages: pt-br → pt-br
Cards: 32
Markdown: Algoritmos, grafos, programação dinâmica e bancos de dados relacionais (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
1	Quais são as duas fases do bloqueio em duas fases (2PL)?	Crescimento: adquirir bloqueios sem liberá-los. Encolhimento: liberar bloqueios sem adquirir novos. Com bloqueios adequados para leituras e escritas conflitantes, 2PL garante escalonamentos serializáveis por conflito, mas impasses continuam possíveis.
2	Por que quicksort pode levar Θ(n²) e como a aleatoriedade ajuda?	Partições repetidamente desequilibradas, como escolher sempre a menor chave entre chaves distintas, causam trabalho quadrático. Com chaves distintas ou tratamento adequado de duplicatas, pivôs aleatórios dão tempo esperado O(n log n). A mediana de três é uma heurística útil, não uma garantia para o pior caso.
3	O que é uma leitura suja e qual primeiro nível padrão a impede?	Ler dados não confirmados de outra transação, independentemente de ela ser depois desfeita. READ COMMITTED e os níveis padrão superiores proíbem leituras sujas.
4	Como funciona a ordenação por inserção e de que depende seu custo em dados quase ordenados?	Ela insere cada item em um prefixo ordenado. A versão usual com deslocamentos ou trocas adjacentes leva Θ(n+I), sendo I o número de inversões. É linear quando I=O(n); uma entrada pequena não muda o pior caso Θ(n²).
5	O que torna estável um algoritmo de ordenação?	Itens com chaves iguais mantêm sua ordem relativa original. Merge sort pode ser estável se escolher primeiro o item da esquerda em empates; o quicksort usual no próprio vetor geralmente é instável. A estabilidade depende da implementação.
6	Como a busca em profundidade detecta um ciclo em um grafo dirigido?	DFS aprofunda a exploração usando recursão ou uma pilha explícita. Uma aresta para um vértice ainda ativo no caminho DFS atual é de retorno e comprova um ciclo dirigido; apontar para qualquer vértice já visitado não basta.
7	Como se comparam matriz de adjacência e listas de adjacência comuns?	Com V vértices e E arestas, a matriz usa O(V²) espaço e verifica uma aresta em O(1). As listas usam O(V+E); procurar (u,v) em uma lista não ordenada custa O(deg(u)), sendo deg(u) o comprimento dessa lista.
8	Como a busca em largura encontra caminhos mínimos em um grafo não ponderado?	BFS usa uma fila FIFO e explora por distância em número de arestas. Marcar um vértice ao inseri-lo na fila evita visitas repetidas. O primeiro caminho descoberto até um vértice alcançável tem o menor número de arestas.
9	Por que árvores B+ são úteis para índices e consultas por intervalo?	A alta ramificação mantém a árvore baixa e reduz acessos a páginas. Chaves ordenadas e folhas encadeadas permitem percorrer intervalos. Índices hash visam buscas por igualdade e não oferecem por si só o mesmo acesso ordenado por intervalo.
10	O que é uma ordem topológica e como o algoritmo de Kahn a encontra?	Em um DAG, cada aresta u→v coloca u antes de v. Retira-se repetidamente um vértice de grau de entrada zero, removendo suas arestas de saída e enfileirando os novos vértices de grau zero. Se saírem menos de V vértices, há um ciclo dirigido.
11	Como diferem memoização e programação dinâmica de baixo para cima?	A memoização avalia subproblemas sob demanda, geralmente por recursão, e guarda os resultados. A abordagem de baixo para cima avalia estados quando suas dependências já estão disponíveis, normalmente preenchendo uma tabela.
12	Como INNER JOIN e LEFT JOIN diferem?	INNER JOIN retorna combinações de linhas que satisfazem a condição de junção. LEFT JOIN também mantém cada linha esquerda sem correspondência, com NULL nas colunas direitas. Várias correspondências podem produzir várias linhas por linha esquerda.
13	O que significam as propriedades ACID de uma transação?	Atomicidade: todos os efeitos ou nenhum. Consistência: transações corretas preservam restrições e invariantes da aplicação. Isolamento: a concorrência respeita o nível escolhido. Durabilidade: efeitos confirmados sobrevivem às falhas cobertas pelas garantias configuradas.
14	O que a busca binária exige e quando leva O(log n)?	Ela divide repetidamente o intervalo de busca ao meio em dados ordenados segundo o critério de comparação. Em um vetor com acesso por índice O(1) e comparações de tempo constante, buscar entre n elementos custa O(log n).
15	Qual é a recorrência para o comprimento da maior subsequência comum (LCS)?	L[i,j] é o comprimento da LCS de prefixos de comprimentos i,j. L[0,j]=L[i,0]=0. Se os últimos caracteres coincidem, L[i,j]=1+L[i−1,j−1]; senão, L[i,j]=max(L[i−1,j],L[i,j−1]). A tabela completa usa O(mn) tempo e espaço.
16	O que exigem a primeira, segunda e terceira formas normais?	1FN: valores atômicos. 2FN: 1FN e nenhum atributo não primo depende de uma parte própria de qualquer chave candidata. 3FN: 1FN e, em toda dependência não trivial X→A, X é superchave ou A é primo. Um atributo primo pertence a alguma chave candidata.
17	O que é uma leitura fantasma e como evitá-la?	Repetir uma consulta com predicado encontra outro conjunto de linhas correspondentes após alterações confirmadas por outra transação. SERIALIZABLE a impede no modelo padrão; algumas implementações, como REPEATABLE READ do PostgreSQL, também a impedem em um nível inferior.
18	Como Bellman–Ford trata arestas negativas e detecta um ciclo negativo alcançável?	Relaxa todas as arestas até V−1 vezes. Uma melhora adicional a partir de um vértice alcançável revela um ciclo negativo alcançável da origem. O pior caso custa O(VE); vértices alcançáveis desse ciclo não têm custo mínimo finito.
19	Como o WAL apoia a durabilidade do PostgreSQL com commit síncrono normal?	Os registros necessários chegam ao armazenamento durável antes da confirmação do commit e antes da gravação das páginas alteradas. Após uma falha, o WAL pode reproduzir alterações ausentes nas páginas. O commit assíncrono pode perder transações recentes já confirmadas.
20	Como funciona o merge sort padrão para vetores e quais são seus custos?	Ele ordena recursivamente duas metades e as intercala em tempo linear. A versão padrão leva Θ(n log n) tempo e O(n) espaço auxiliar, supondo comparações de tempo constante.
21	O que é uma leitura não repetível e qual nível padrão a impede?	Ao reler uma linha, seus dados mudaram ou ela desapareceu após outra transação confirmar uma atualização ou exclusão. REPEATABLE READ e SERIALIZABLE impedem essa anomalia.
22	Quais são o tempo no pior caso e o espaço extra do heapsort no próprio vetor?	Construir o heap custa O(n); as extrações somam O(n log n). Com descida iterativa no vetor de entrada, heapsort leva O(n log n) no pior caso e usa O(1) espaço extra.
23	Como WHERE e HAVING diferem em uma consulta agrupada?	WHERE filtra linhas de entrada antes do agrupamento. HAVING filtra os grupos resultantes e pode usar condições com agregações, como COUNT(*)>1.
24	Por que a programação dinâmica é útil em muitos problemas de otimização?	A subestrutura ótima permite expressar um ótimo por meio de ótimos dos subproblemas. Quando eles se sobrepõem, guardar as respostas evita trabalho repetido. Os estados e a recorrência precisam representar corretamente o problema original.
25	Quando Dijkstra é válido e qual é um custo usual com heap?	Com pesos não negativos, ele fixa repetidamente o vértice com menor distância provisória. Uma implementação com listas de adjacência e heap binário mínimo leva O((V+E) log V). Arestas negativas podem invalidar o argumento de distância definitiva.
26	Como um algoritmo guloso difere da programação dinâmica?	O guloso assume uma escolha local e exige prova de que essas escolhas preservam um ótimo. A programação dinâmica compara alternativas por uma recorrência e reutiliza resultados. O ótimo global exige modelo e recorrência corretos, não apenas o nome “DP”.
27	Quando counting sort ou radix sort podem levar tempo linear?	Counting sort custa O(n+k) para n chaves em um intervalo de k valores. Radix sort com d passadas estáveis por dígitos e base b custa O(d(n+b)). Só são lineares quando esses parâmetros permitem; exploram a estrutura das chaves além das comparações.
28	Qual é uma ordem lógica simplificada de processamento de uma consulta SQL SELECT?	Sem CTEs, funções de janela nem operações de conjuntos: FROM/JOIN → WHERE → GROUP BY e agregações → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET. É um modelo lógico, não necessariamente a ordem física escolhida pelo otimizador.
29	Como Kruskal e Prim constroem uma árvore geradora mínima?	Em um grafo conexo, não dirigido e ponderado, Kruskal considera arestas por peso crescente e usa Union–Find para rejeitar ciclos. Prim expande uma árvore escolhendo uma aresta de peso mínimo que conecta a árvore a um vértice externo.
30	Como diferem chaves primárias e estrangeiras no PostgreSQL?	A primária identifica linhas por valores únicos e não NULL. A estrangeira exige correspondência com valores da chave referenciada, segundo suas regras de NULL. Pode referenciar uma chave UNIQUE elegível ou uma primária da mesma tabela ou de outra.
31	Qual é a recorrência padrão da mochila 0/1 com capacidade inteira W?	D[i,w] é o melhor valor usando os primeiros i itens, capacidade w e pesos inteiros positivos wᵢ. D[0,w]=0. Se wᵢ>w, copia-se D[i−1,w]; senão, usa-se max(D[i−1,w],vᵢ+D[i−1,w−wᵢ]). O tempo O(NW) é pseudopolinomial.
32	Como diferem índices clustered e nonclustered de armazenamento por linhas no SQL Server?	O clustered armazena as linhas em ordem de chave, então há no máximo um por tabela. O nonclustered possui suas próprias chaves e localizadores de linhas e pode incluir outras colunas. Termos e detalhes de armazenamento variam entre sistemas.