Fundamentos de Algoritmos e Análise de Complexidade Flashcards

1
Q

Defina e explique o que significa dizer que uma função possui complexidade O(n).

A

De maneira formal, dizer que uma função f(x) é O(n) quer dizer que ∃ k > 0 ∃ n0 ∀n>n0 f(n) <= k * n. Em outras palavras, isso quer dizer que, para uma entrada suficientemente grande, o tempo de execução será sempre de uma ordem menor ou igual a n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

A expressão x = O(n) pode ser escrita como O(n) = x. Verdadeiro ou falso? Justifique.

A

Falso. x = O(n) não significa que x é igual a O(n), mas sim que x pertence ao conjunto das funções para o qual a definição de O(n) se aplica. Em outras palavras, x = O(n) deve ser entendido como “x é/pertence a O(n)” ao invés de “x é igual a O(n)”.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Explique, de forma sucinta, o significado das notações O, Ω, Θ, o e ω. Quai operador aritmético melhor resume o significado dessas notações?

A
  • f(x) = o(g(x)) : f(x) será sempre inferior a g(x). <
  • f(x) = O(g(x)): f(x) nunca será maior que g(x). <=
  • f(x) = Θ(g(x)): f(x) nunca será nem muito maior nem muito menor que g(x). ≈
  • f(x) = Ω(g(x)): f(x) nunca será menor que g(x). >=
  • f(x) = ω(g(x)): f(x) será sempre maior que g(x). >
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Explique de forma sucinta os seguintes paradigmas de computação:
- Gananciosos
- Força-bruta
- Dividir e Conquistar
- Programação dinâmica

A
  • Gananciosos: Resolver um problema buscando sempre a melhor opção em cada momento
  • Força-bruta: Testar todas as opções até encontrar uma que satisfaça o problema
  • Dividir e conquistar: Pegar um problema complexo e dividi-lo até problemas independentes com solução trivial. Então, combinar essas soluções triviais para obter uma solução do problema complexo.
  • Programação Dinâmica: Pegar um problema complexo e dividi-lo até problemas simples que se conectam. Então, usar conhecimento obtido nos problemas simples para resolver os problemas complexos.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Como demonstrar de maneira formal que um loop dentro de um algoritmo é correto?

A

Usando indução:
- Primeiro, mostra-se o caso base (ou seja, que o algoritmo é correto antes de entrar no loop).

  • Então, mostra-se o caso indutivo (ou seja, se ele era correto antes de entrar no loop, ele permanece correto antes da próxima iteração).
  • Por último, demonstra-se que o loop é finito (junto com suas implicações baseadas na condição de término).
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Como obter a relação de recorrência da quantidade de operações necessárias para resolver um problema recursivo com a técnica dividir para conquistar?

A

Primeiro, calcule a quantidade de operações envolvidas no passo base, T(0).

A seguir, calcule D(n), a quantidade de operações necessárias para dividir o problema de tamanho n em a problemas de tamanho n/b. Então, calcule C(n), a quantidade de operações necessárias para transformar as a soluções de problemas de tamanho n/b em uma solução para o problema de tamanho n. Por último, para obter a relação de recorrência, some D(n) com C(n) e a * T(n/b).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Um algoritmo O(n²) é mais lento para entradas suficientemente grandes que um algoritmo O(n). Verdadeiro ou falso? Justifique.

A

Falso. Pela definição da notação O, um algoritmo que sempre executa em tempo constante também é O(n²) e por consequência pode ser mais rápido que um algoritmo que executa em velocidade linear.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Um algoritmo Θ(n²) é sempre mais lento que um algoritmo Θ(n). Verdadeiro ou falso? Justifique.

A

Falso. Análise assintótica calcula a velocidade para valores grandes o suficiente para tornarem irrelevantes as constantes dos valores menores. Para entradas pequenas, um algoritmo que precisa de n² operações para ser executado é mais rápido que um algoritmo que precisa de 1000 * n operações.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

O que a função Θ(n) representa na seguinte equação?
2n² + 3n + 1 = 2n² + Θ(n). Qual a vantagem desse tipo de representação?

A

Nesse caso, Θ(n) representa uma função qualquer que pertence ao conjunto das funções Θ(n).

A vantagem desse tipo de representação é que permite o estudo da complexidade de algoritmos sem ter necessariamente que especificar todas as operações de menor ordem envolvidas.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

O que a função Θ representa na seguinte equação?
2n² + Θ(n) = Θ(n²). Como interpretar essa equação?

A

Nesse caso, Θ representa uma função qualquer que pertence ao conjunto das funções especificadas como parâmetro.

A expressão indica que, não importa qual função você escolha para Θ(n), existe uma forma de escolher uma função pertencente a Θ(n²) que satisfaz a equação.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Como deve-se interpretar convencionalmente a expressão T(n) = O(1) para n < 3. Por que essa convenção é considerada um abuso da notação?

A

Pela convenção, deve-se entender a expressão como “existe uma constante c tal que T(n) <= c quando n < 3”.

Essa convenção é considerada um abuso porque a notação big O nesse caso diz que existem constantes c e n0 tais que para qualquer n > n0, T(n) <= c. Se a constante n0 for maior ou igual a 3, não é possível inferir nada, tornando a expressão sem sentido.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Enumere quais notações (entre O, Ω, Θ, o e ω) possuem as seguintes propriedades:
- Transitividade
- Reflexividade
- Simetria

A
  • Todas elas são transitivas (ou seja, f(n) = O(g(n)) e g(n) = O(h(n)) implica em f(n) = O(h(n)).
  • O, Ω e Θ são reflexivas (ou seja, f(n) = O(f(n))
  • Somente Θ é simétrica (ou seja, f(n) = Θ(g(n)) se e somente se g(n) = Θ(f(n)) ).
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Quais propriedades uma recorrência T(n) tem que possuir para ser considerada algorítmica? Quando isso é convencionalmente usado?

A

Ela deve, para algum valor constante pré-defindo n0 > 0, seguir duas propriedades:
1 - Para todo n < n0, T(n) = Θ(1)
2 - Para todo n >= n0, todo caminho de recursão alcança um dos casos base em um número finito de invocações recursivas.

Convencionalmente, quando uma recorrência é definida sem um caso base explícito, assumimos que ela seja algorítmica.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Cite e explique de forma sucinta quatro formas diferentes de definir o comportamento assintótico de algoritmos cujo comportamento pode ser descrito por uma relação de recorrência.

A
  • Método da substituição: Dê um palpite para o comportamento assintótico e verifique se ele está correto usando indução matemática.
  • Método da árvore recursiva: Modele a recorrência como uma árvore onde cada nó representa o custo de uma etapa e então some o valor desses nós.
  • Teorema mestre: Se a recorrência é da forma T(n) = a T(n/b) + f(n) (a > 0 e b > 1 constantes, custo de dividir e combinar f(n)), ela pode ser resolvida usando um dos três casos do Teorema Mestre.
  • Método Akra-Bazzi: Método geral para resolver recorrência usando cálculo. Capaz de lidar com recorrências mais complicadas que as abordadas pelo Teorema Mestre.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Qual o princípio por trás do algoritmo de Strassen para multiplicação de matrizes ?

A

Visto que o custo de multiplicar duas matrizes é consideravelmente maior que o custo de somá-las, o algoritmo de Strassen usa um conjunto estratégico de somas e subtrações de matrizes para substituir uma das multiplicações necessárias.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Onde está o erro na seguinte prova que T(n) = 2T(n/2) + Θ(n) possui complexidade O(n)?

T(n) = 2T(n/2) + Θ(n)
<= 2 * O(n/2) + Θ(n)
<= 2 * O(n) + Θ(n)
= O(n)

A

O erro está no fato de que a constante c implícita na notação O(n) não é necessariamente a mesma em cada linha. Para construir uma prova usando indução estrutural, é necessário demonstrar que a constante c da primeira e da última linha trata-se da mesma constante.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

No contexto de comportamento assintótico de funções de recorrência, por que recomenda-se evitar o uso de notações assintóticas no método da substituição?

A

Para que a demonstração por indução matemática seja válida, é necessário que a mesma constante satisfaça a a recorrência para todo n > n0. Por outro lado, notações assintóticas incluem uma ou mais constantes que não necessariamente permanecem as mesmas durante o desenvolvimento da prova. Por isso, recomenda-se nomear as constantes de forma explícita.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Onde está o erro na seguinte prova que T(n) = 2T(n/2) + Θ(n) possui complexidade O(n)?

T(n) = 2T(n/2) + Θ(n)
<= 2(c*n/2) + Θ(n)
<= cn + Θ(n)
= O(n)

A

O erro está no fato de que a prova por indução tem por objetivo mostrar que T(n) <= cn para todo n > n0. Ao provarmos isso, demonstramos por consequência que T(n) pertence ao conjunto O(n), algo que não foi demonstrado nesta prova.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Quais são as condições para a aplicação do Teorema Mestre para a resolução de recorrências?

A

T(n) deve ser uma recorrência da forma a * T(n/b) + f(n) com a > 0, b > 1 e f(n) definida para reais grandes o suficiente. a * T(n/b) também pode ser escrita como a’ * T(⌈n/b⌉) + a ‘’ * T(⌊n/b⌋), com a’ + a’’ = a.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Quais são os três casos do Teorema Mestre para resolução de recorrências?

A

1 - Se existir uma constante ε > 0 tal que f(n) = O(n ^ (log b a - ε) ), então T(n) = Θ(n^logb a)

2 - Se existir uma constante k >= 0 tal que f(n) = Θ(n ^log(b a) * lg ^ k n), então T(n) = Θ (n^logb a * lg^(k+1) n)

3 - Se existir uma constante ε > 0 tal que f(n) = Ω(n^(log b a + ε)) e se f(n) satisfaz a condição de regularidade a * f(n/b) <= c f(n) para alguma constante c < 1 para todo n grande o suficiente, então T(n) = Θ(f(n)).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

De maneira simplificada, como identificar qual caso do Teorema mestre deve ser utilizada em um determinado problema?

A

De maneira simplificada, basta comparar a função f(n) com a função n ^ (log b a).

Se a segunda função cresce (polinomialmente) mais rápido que a primeira, devemos aplicar o primeiro caso. Se ambas crescem aproximadamente na mesma taxa, devemos aplicar o segundo caso. Se a primeira cresce (polinomialmente) mais rápido que a segunda, aplicamos o terceiro caso.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

O que é uma árvore geradora de um grafo? E uma árvore geradora mínima?

A

Uma árvore geradora um subgrafo conexo e acíclico de um grafo não-direcionado. Árvore geradora mínima é uma árvore geradora que minimiza o peso total de suas arestas.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Dê três exemplos de circunstâncias que podem levar o Teorema Mestre a não ser aplicável.

A

1 - A função de recorrência não ser da forma a * T(n/b) + f(n).
2 - A função n^(log b a) não crescer polinomialmente mais rápido que f(n). Por exemplo, na função T(n) = 2T(n/2) + n/lg n, f(n) cresce logaritmicamente mais rápido que n^(log 2 2) = n.
3 - A função f(n) não crescer polinomialmente mais rápido que n^(log b a). Acontece, nesse caso, o caso reverso doanterior.
4 - As função f(n) e n ^ (log b a) não puderem ser comparadas assintoticamente. Por exemplo, f(n) pode ser uma função definida por partes em que cada parte se compara de forma diferente a n ^ (log b a).
5 - O caso ser similar ao apresentado no caso 3 do Teorema Mestre, porém a função f(n) não satisfazer a condição de regularidade a*f(n/b) <= c f(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Qual a forma geral da recorrência de Akra-Bazzi? Qual a vantagem de usá-la sobre o Teorema Mestre?

A

A forma geral da recorrência de Akra-Bazzi é T(n) = f(n) + Σ ai T(n/bi).

A maior vantagem da recorrência de Akra-Bazzi é que ela pode ser usada para lidar com situações onde a recorrência divide o problema principal em sub problemas de tamanhos diferentes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Como usar o método de Akra-Bazzi para resolver recorrências?

A

Primeiro, deve-se encontrar o número p tal que Σ ai/bi^p = 1. Com isso, o método de Akra-Bazzi diz que a solução da recorrência T(n) será Θ(n^p(1 + integral de 1 até n de f(x)/x^(p+1))).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Qual o objetivo do Casamento Estável? Quais termos são relevantes para compreender o problema?

A

Dado uma série de preferências entre homens e mulheres, construir um processo de casamento sem pares instáveis. Um par instável entre um homem h e uma mulher m ocorre quando h prefere m a sua esposa e m prefere h ao seu marido.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

O que é um emparelhamento em um grafo? O que é um emparelhamento perfeito? No contexto do problema do Casamento Estável, podemos dizer que um emparelhamento perfeito é sinônimo de emparelhamento estável?

A

Um emparelhamento é um conjunto de arestas de um grafo em que nenhum vértice aparece mais de uma vez no conjunto. Um emparalhamento perfeito é um emparelhamento que contém todas as arestas do grafo. Não é sinônimo de emparelhamento estável (que tem a ver com a ordem de preferência).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

No contexto do problema do Casamento Estável, quais são as 3 condições para um par (h, m) ser considerado instável em um emparelhamento perfeito M?

A

1 - (h, m) não pode pertencer a M
2 - h deve preferir m à m’ designada pelo emparelhamento.
3 - m deve preferir h ao h’ designado pelo emparelhamento.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Descreva de maneira simplificada o algoritmo de Gale-Shapley para o problema do Casamento Estável.

A

1 - Defina um dos grupos para escolher e outro para ser escolhido
2 - Escolha um membro aleatório x do grupo de quem escolhe. Faça uma proposta para o membro do outro grupo melhor rankeado que ainda não foi proposto por x.
3 - Se o membro proposto estiver sozinho ou se preferir x ao par designado, adicione um par envolvendo x e remova seu par atual se necessário. Caso contrário, ele rejeita a proposta
4 - Repita o processo até todos os membros escolhedores estiverem pareados ou tiverem realizado propostas para todos do outro grupo.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

Descreva de maneira simplificada o funcionamento do algoritmo de Gale-Shapley para o problema do Casamento Estável.

A
  • Cada membro do par escolhedor reveza propostas de pareamento em ordem decrescente de preferência
  • Uma vez pareado, um membro do grupo escolhido nunca fica desemparelhado, apenas troca por um par de preferência superior
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

No problema do Casamento Estável, definindo satisfação como sendo o quão próximo o par designado se aproxima do par ideal, qual o resultado do algoritmo de Gale-Shapley para a satisfação de quem escolhe e de quem é escolhido?

A

O algoritmo de Gale-Shapley maximiza a satisfação de quem escolhe enquanto minimiza a satisfação de quem é escolhido.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

Descreva, de maneira resumida, o que acontece com o número de iterações no pior caso da execução do algoritmo de Gale-Shapley.

A

O algoritmo de Gale-Shapley termina quando todos são pareados e, uma vez pareado, um escolhido nunca fica sem par. Por isso, no pior dos casos nós temos os n escolhedores fazendo propostas para n-1 escolhidos e um escolhedor fazendo uma proposta para o n-ésimo escolhido, resultado em n*(n-1) + 1 iterações.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

Explique como construir as preferências dos escolhedores e dos escolhidos de modo que o algoritmo de Gale-Shapley execute o pior caso. O que é necessário que aconteça na execução para que ele resulte no absoluto pior caso?

A

Construiremos as preferências dos escolhedores e escolhidos da seguinte forma:
- Para os primeiros n-1 escolhedores, sua i-ésima preferência será diferente da i-ésima preferência dos outros n-1 escolhedores.
- A preferência dos primeiros n-1 escolhidos é em ordem contrária à dos escolhedores (ou seja, a primeira opção de um escolhido será a pessoa que tem ele como última opção e vice-versa).
- O n-ésimo escolhido será a última opção dos n escolhedores.
- A ordem do n-ésimo escolhedor e escolhido não importa.
- O n-ésimo escolhedor será a opção n-i-1 do seu i-ésimo escolhido (ou seja, ele será sempre uma opção melhor que a designada em cada momento).

Para que o algoritmo execute no absoluto pior caso, é necessário que a n-ésima pessoa seja a última a escolher na primeira rodada. Desta forma, o algoritmo começará formando n-1 pares em que os escolhedores ficam com sua primeira opção e os escolhidos ficam com a última. A n-ésima pessoa fará uma proposta para alguém que considera ela sua penúltima opção que fará a troca, resultado em uma pessoa sem par que então fará uma proposta para alguém que a considera sua penúltima opção e assim por diante.

O resultado final são n propostas aceitas por ausência de par e todas as outras aceitas envolvendo troca de pares.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

Quando podemos dizer que um grafo é uma árvore?

A

Quando o grafo é conectado e não possui ciclos.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

Qual condição um grafo precisa ter para ser considerado conectado? E fortemente conectado?

A

Um grafo é conectado se e somente se, para qualquer par de vértices u e v, existe um caminho entre u e v. Ele será fortemente conectado se for um grafo direcionado e, para qualquer par de vértices u e v, existir um caminho entre u e v e entre v e u.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

Quantas arestas possui uma árvore com n vértices?

A

N - 1 arestas.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

De maneira resumida, como funciona o algoritmo BFS? Explique em termos de camadas.

A

O algoritmo BFS começa na raiz. Na primeira iteração, ele explora a primeira camada (ou seja, todos os vértices diretamente conectados à raiz). Na segunda, ele explora a segunda camada (ou seja, todos os vértices conectados aos vértices conectados à raiz) e assim por diante até nenhum vértice novo ser encontrado.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

Defina camadas no contexto do algoritmo BFS.

A

A primeira camada são o os elementos diretamente conectados à raiz. Se temos as camadas 1, 2, …, j, a camada j+1 será composta por todos os elementos que estão conectados a j e não aparecem em nenhuma camada anterior.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

Entre BFS e DFS, qual é melhor para encontrar a menor rota até um ponto? Por quê?

A

BFS. Na sua definição, BFS funciona explorando primeiro os elementos a uma distância 1 da raiz, seguido pela distância 2, 3 e assim por diante. Desta forma, em uma etapa n, o BFS descobre todos os pontos alcançáveis em n passos, encontrando assim a menor distância.

DFS, por outro lado, escolhe um caminho e segue ele até o final. Isso quer dizer que um vértice conectado tanto à raiz quanto à camada n pode ser encontrado primeiro explorando o caminho mais longo e não o mais curto.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

Como funciona a representação de grafos por matrizes de adjacência? E por listas de adjacência? Cite vantagens e desvantagens de se usar um ao invés do outro.

A

Em uma matriz de adjacência, o grafo é representado como uma matriz n x n sendo n o número de vértices. Se existir uma conexão entre dois vértices i, j, m[i][j] será igual a 1, caso contrário, será um valor padrão.

Em uma lista de adjacência, o grafo é representado como uma lista com n listas representando os vértices. Cada uma dessas n listas representa os elementos conectados diretamente a n.

A matriz de adjacência tem como principal desvantagem o uso de memória na ordem de n². Sua maior vantagem é a identificação mais rápida se um vértice (u, v) existe em um grafo. A lista de adjacência, por outro lado, usa memória na ordem de m + n e por isso funciona melhor para listas esparsas.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

O que é um grafo bipartido ? Qual a condição que um grafo precisa atender para ser considerado bipartido. Dê um exemplo de aplicação desse conceito.

A

Um grafo bipartido é um grafo que pode ser dividido em 2 conjuntos a e b de forma que não exista nenhuma aresta entre elementos do mesmo conjunto. Um grafo é bipartido se e somente se ele não possui ciclos com um número ímpar de vértices.

Uma aplicação desse conceito é o problema do Casamento Estável que pode ser modelado como um grafo bipartido em que um grupo representa os escolhedores e o outro os escolhidos.

42
Q

De que forma podemos usar o algoritmo de BFS para identificar se um grafo conexo é bipartido ou não?

A

Para identificar se um grafo é bipartido, podemos usar o algoritmo BFS para construir uma árvore de busca em largura. O grafo será bipartido se e somente se não possuir nenhuma aresta entre vértices da mesma camada.

43
Q

Em qual situação, num grafo BFS, podemos ter uma aresta conectando vértices cuja diferença de nível é maior que 1? Que nome damos a essa aresta?

A

Para termos arestas conectando vértices em camadas cuja diferença é maior que 1, é necessário que o grafo seja direcionado e a aresta parta de um vértice em uma camada inferior e aponte para uma camada superior. A esse tipo de aresta, damos o nome de back edge.

44
Q

Quais são as 4 principais classificações para arestas em um grafo após a execução de um algoritmo como BFS/DFS?

A
  • Tree Edge: Aresta que está presente no grafo e na árvore correspondente
  • Cross Edge: Aresta que está presente apenas no grafo e conecta dois elementos sem relação direta na árvore correspondente
  • Back Edge: Aresta que está presente apenas no grafo e conecta uma aresta em um nível inferior a uma aresta em um nível superior
  • Forward Edge: Aresta que está presente apenas no grafo e conecta uma aresta em um nível superior a uma aresta em um nível inferior.
45
Q

Quais tipos de arestas podem ser encontrados em um grafo BFS? Justifique.

A

Tree Edge (por definição) e Cross Edge. Se o grafo for direcionado, pode ser encontrado também back edge.

Forward edge não pode existir em uma árvore BFS porque ela parte de uma camada superior e aponta para uma camada inferior. Visto que o BFS explora em camadas, se essa aresta existir no grafo, será incluída como uma tree edge.

46
Q

Quais tipos de arestas podem ser encontrados em um grafo DFS? Justifique.

A

Tree Edge (por definição) e back Edge. Se o grafo for direcionado, pode ser encontrado também forward edge e cross edge.

Em um grafo não direcionado, todas as arestas são descobertas pelo último elemento a ser visitado. Por isso, uma aresta entre dois vértices dependentes será ou uma Tree Edge (se for explorada pelo vértice na camada superior) ou uma Back Edge (se for explorada pelo vértice na camada inferior).

Da mesma forma, uma potencial cross Edge seria incluída ou como uma tree edge (se os vértices pertencessem a árvores diferentes) ou uma back edge (se possuírem algum descendente em comum).

47
Q

Como identificar back edges em um grafo DFS?

A

Mantenha uma lista L com todos os vértices que estão sendo explorados mas ainda não foram finalizados. Ao explorar uma aresta nova, ela será uma back edge se e somente se ela conectar dois vértices que ainda não foram finalizados.

48
Q

Como identificar back edges em um grafo BFS?

A

Ao explorar uma aresta nova, ela será uma back edge se e somente se ela conectar um vértice que não foi finalizado a um vértice que já foi.

49
Q

Como identificar forward edges em um grafo DFS?

A

Mantenha em cada vértice uma variável contendo o tempo em que a exploração começou e o tempo no qual a exploração terminou. Uma aresta é uma forward edge se e somente se a exploração do vértice de origem começou antes da exploração do vértice de destino.

50
Q

Como identificar cross edges em um grafo DFS?

A

Mantenha em cada vértice uma variável contendo o tempo em que a exploração começou e o tempo no qual a exploração terminou. Uma aresta é uma forward edge se e somente se a exploração do vértice de origem começou depois da exploração do vértice de destino.

51
Q

Como identificar cross edges em um grafo BFS?

A

Mantenha uma lista L com todos os vértices que estão sendo explorados mas ainda não foram finalizados. Ao explorar uma aresta nova, ela será uma cross se e somente se ela conectar dois vértices que ainda não foram finalizados.

52
Q

Como identificar um ciclo em um grafo a partir dos tipos de suas arestas, do tipo do grafo e do algoritmo usado?

A

Independente do algoritmo ou do grafo utilizado, uma back edge sempre indica um ciclo. No caso de um BFS em um grafo não direcionado, uma Cross Edge também indica um ciclo.

53
Q

Qual propriedade relaciona as arestas de um grafo G que conectam dois pontos x e y com os níveis no qual esses pontos aparecerão dentro da árvore BFS formada a partir de G ? Que conclusão podemos tirar sobre as arestas que estão no grafo mas não estão na árvore?

A

Se (x,y) é uma aresta em um grafo G, x e y aparecerão na árvore BFS ou no mesmo nível ou em níveis consecutivos. A consequência que podemos tirar é que as arestas presentes em G que não estão na árvore conectam sempre vértices que estão ou no mesmo nível ou em níveis consecutivos.

54
Q

Qual é a complexidade do algoritmo BFS em função de seus vértices e arestas?

A

O (m + n)

55
Q

O que podemos afirmar sobre as arestas presentes em um grafo que não estão presentes na respectiva árvore DFS ?

A

As arestas que estão presentes no grafo conectarão sempre elementos que são descendentes diretos na árvore BFS.

56
Q

O que significa dizer que dois vértices u e v são mutuamente alcançáveis em um grafo G?

A

Significa que o grafo G é direcionado e existe um caminho entre u e v e um caminho entre v e u.

57
Q

Explique, de forma simples, o funcionamento de um algoritmo capaz de detectar se um grafo G é fortemente conectado com complexidade de tempo igual ou inferior a O(V + E).

A
  • Escolha um nó aleatório s ∈ G.
  • Rode BFS ou DFS no nó s.
  • Reverta a direção das arestas de G (ou, em outras palavras, calcule a reversa/transposta do grafo G).
  • Execute o mesmo algoritmo no grafo G revertido.
  • Retorne verdadeiro se e somente se todos os vértices foram alcançados por ambos os algoritmos
58
Q

Explique, de forma simples, o algoritmo de Kosaraju para detecção de Componentes Fortemente Conectados.

A
  • Rode DFS no grafo G, registrando os tempos de finalização de cada vértice.
  • Reverta a direção das arestas de G (ou, em outras palavras, calcule a reversa/transposta do grafo G).
  • Execute o mesmo algoritmo no grafo G revertido, começando pelas últimas arestas a serem finalizadas.
  • Após finalizar cada aresta, remova ela e as arestas alcançadas. Elas formam um SCC.
  • Repita o processo até não restarem mais vértices.
59
Q

Explique, de forma simples, o algoritmo de Tarjan para detecção de Componentes Fortemente Conectados.

A
  • Comece com um vértice aleatório v.
  • Defina tanto o índice de v e seu ancestral mais velho para uma variável tempo. Incremente essa variável e coloque v na pilha.
  • Percorra todos os vértices diretamente alcançáveis por v. Após percorrer cada vértice, atualize o ancestral mais velho de v para o menor valor entre o ancestral mais velho atual e o do vértice explorado.
  • Se após explorar todos os vértices, o ancestral mais velho é o próprio v, v é a raiz de um SCC.
  • Remova os elementos da pilha até v ser removido. Esses elementos compõe um SCC. v não poderá mais ser explorado e por isso não inteferirá com outros SCCs.
  • Repita o processo até todos os vértices terem sido explorados
60
Q

Qual a intuição por trás do algoritmo de Kosaraju para detecção de SCCs?

A

Sabemos que os SCCs em um grafo formam um DAG. O algoritmo de Kosaraju usa o DFS para obter a ordenação topológica desse DAG. Ao reverter as arestas e executar o algoritmo a partir do último a finalizar, estamos começando pelo componente no DAG que não leva a nenhum outro componente. Por consequência, as únicas arestas alcançáveis a partir desse vértice são as do SCC correspondente.

61
Q

Qual a intuição por trás do algoritmo de Tarjan para detecção de SCCs?

A

A intuição do algoritmo de Tarjan envolve armazenar os vértices explorados em uma pilha e manter em cada o tempo de descoberta do vértice e o tempo de descoberta do vértice mais antigo alcançável a partir daquele vértice. Cada vértice que não alcançou nenhum mais antigo é a raiz de um SCC e cada vértice explorado por ele (identificável a partir da pilha) fazem parte do componente.

62
Q

O que é um componente fortemente conectado em um grafo G?

A

Em um grafo (direcionado) G, um componente fortemente conectado é um componente de tamanho maximal de vértices mutuamente alcançáveis.

63
Q

Qual a diferença entre máximo e maximal?

A

Máximo se refere ao maior valor possível (ou seja, o maior valor global). Maximal se refere ao maior valor alcançável a partir do caminho escolhido (ou seja, o maior valor local).

64
Q

O que é um DAG?

A

DAG (directed acyclical graph) é um grafo direcionado que não possui ciclos.

65
Q

Como podemos identificar se um grafo direcionado é G é acíclico a partir de sua respectiva árvore DFS? Por que isso ocorre?

A

Um grafo G é acíclico se e somente se não existir nenhuma árvore DFS formada a partir de G com arestas do tipo back (ou seja, arestas que saem de um nível inferior e alcançam um nível superior em uma árvore).

66
Q

O que a ordenação topológica de um grafo?

A

É uma ordenação dos vértices do grafo como v1, v2, …, vn de modo que toda aresta entre vértices (vi, vj) possua i < j.

67
Q

Cite duas aplicações para ordenação topológica.

A

Ordenação topológica é um conceito muito útil para representar grafos que representam relações de precedência na vida real. Exemplos:

  • Relação entre matérias e seus pré-requisitos em uma faculdade
  • Relação entre bibliotecas e suas dependências em um projeto
  • Organização de tarefas em um projeto profissional: indicar que uma tarefa x precisa ser completada antes de uma y ser iniciada.
68
Q

Qual é a relação entre ordenação topológica e o conceito de um DAG?

A

G é um DAG se e somente se G possui uma ordenação topológica.

69
Q

Qual é a relação entre o conceito de um DAG e o conceito de Componentes Fortemente Conectados (SCC)? Por que essa relação é verdadeira?

A

Os componentes fortemente conectados em um grafo direcionado formam, de maneira coletiva, um DAG.

É fácil notar que essa relação é verdadeira pela definição de DAG (grafo direcionado sem ciclos) e componente fortemente conectado (ciclo maximal). Se os SCC não formam um DAG, isso quer dizer que existe um ciclo. Um ciclo implica que seus vértices são mutuamente alcançáveis, o que os tornaria um SCC.

70
Q

Explique, de forma simples, o funcionamento de um algoritmo simples capaz de obter a ordenação topológica de um DAG.

A
  • Itere pelo grafo e salve em uma lista “contador” a quantidade de arestas apontadas para cada vértice. Crie uma lista vazia para representar a ordenação topológica.
  • Selecione uma aresta qualquer com 0 arestas apontadas (ela sempre existirá, pela definição de um DAG) que ainda não esteja na ordenação topológica.
  • Adicione ela ao final da ordenação topológica.
  • Decremente o contador de todos os vértices com arestas vindo do grafo selecionado.
  • Repita as três etapas anterioras até a ordenação topológica conter todas as arestas.
71
Q

Explique, de forma simples, o funcionamento de um algoritmo baseado em DFS capaz de obter a ordenação topológica de um DAG.

A
  • Construa um algoritmo BFS que mantém, em cada aresta, seu tempo de descoberta e de finalização.
  • Execute esse em um grafo até todas arestas terem sido ordenadas.
  • A ordenação topológica será dada pela ordenação decrescente das arestas em termos de tempo de finalização.
72
Q

Demonstre o porquê de o algoritmo da ordenação topológica possuir complexidade de tempo igual a O(V + E). Quais decisões de implementação são cruciais para que essa complexidade seja atingida?

A

O algoritmo pode ser dividido nas seguintes etapas:
1 - Inicialização -> itera por todas as arestas ( O( E) )

2 - Seleção dos primeiros vértices -> Itera por todos os vértices ( O(V) ).

Aqui, surge a primeira decisão importante. É necessário selecionar todos os vértices que possuem 0 arestas ao invés de selecionar apenas um. Desta forma, evitamos a necessidade de iterar novamente sobre os vértices.

3 - Decrementar o valor das arestas conectadas -> Ao final do algoritmo, esse processo acontecerá E vezes e por isso é O(E)

4 - Selecionar o(s) próximo(s) vértice(s) -> Por estarmos selecionando todos os vértices sem conexão em um DAG, sabemos que após decrementar os contadores, ao menos um dos vértices envolvidos terá valor 0. Desta forma, detectar o(s) próximo(s) vértice(s) ocorre em O(1).

5 - Repetições -> Esse processo de selecionar um vértice ocorrerá V vezes.

Ao final, temos O(E) + O(V) + O(E) + V*O(1) = O(E + V)

73
Q

De maneira simplificada, como funciona e para que serve o algoritmo de Dijkstra? Qual pré-requisito deve ser atingido para que ele funcione?

A

O algoritmo de Dijkstra é um algoritmo capaz de encontrar o menor caminho entre um vértice de origem e todos os outros vértices alcançáveis em um grafo.

De maneira resumida, ele funciona armazenando a distância entre o vértice de origem e os vértices da fronteira e, a cada iteração, adiciona à fronteira o vértice conectado a um vértice da fronteira que minimiza a soma entre o custo para chegar no vértice da fronteira e o custo para sair deste vértice para o próximo.

Para que o algoritmo de Dijkstra obtenha o menor caminho, é necessário que as arestas não possuam valores negativos.

74
Q

Por que o algoritmo de Dijkstra não retorna o menor caminho se há arestas com peso negativo?

A

O algoritmo de Dijkstra adiciona ao conjunto dos nós conhecidos sempre o nó com menor caminho total. Isso garante o menor caminho, visto que se a aresta entre A e B é identificada como o caminho mais curto no conjunto, no pior dos cenários, isso garante que qualquer caminho alternativo até B possui, no mínimo, a mesma distância. Todavia, se os pesos podem ser negativos, existe a possibilidade de existir um caminho inicialmente mais longo que resulta em um caminho total mais rápido.

75
Q

Cite dois exemplos de razões pela qual arestas com peso negativo aumentam a complexidade do problema do menor caminho.

A
  • Arestas com peso negativo inviabilizam a estratégia do algoritmo de Dijkstra de identificar sempre os vértices mais próximos da origem a cada iteração.
  • A presença de ciclos negativos em um algoritmo que não limita quantas vezes a mesma aresta pode fazer parte do resultado pode tornar o resultado indeterminado.
76
Q

O que é o diâmetro de um grafo?

A

É a maior distância mínima entre um part de vértices presentes no grafo.

77
Q

Por que, em uma árvore BFS de um grafo não-direcionado, podemos afirmar que não existem arestas entre vértices cuja diferença de nível é maior que 1?

A

O funcionamento do algoritmo BFS implica que todos os vértices conectados a um vértice no nível anterior são explorados antes de um próximo nível ser iniciado. Por consequência, se existisse uma aresta entre dois vértices vi e vj, i < j, j-i > 1, essa aresta seria explorada na camada i+1.

78
Q

O que é o ciclo mínimo de um grafo direcionado? E de um grafo não-direcionado?

A

O ciclo mínimo de um grafo direcionado são duas arestas que conectam (a, b) e (b,a). No caso de um grafo não-direcionado, são três arestas que conectam (a,b), (b,c) e (c,a).

79
Q

Como usar DFS para obter a ordem topológica de um grafo?

A

Execute uma versão ligeiramente modificada do DFS que mantém, além dos vértices explorados, os momentos nos quais os vértices são descobertos e finalizados. Retorne os vértices em ordem decrescente de tempo de finalização.

80
Q

Defina os seguintes termos no contexto de grafos:
- Caminho
- Corte
- Cutset

A
  • Caminho: Sequência de arestas que conectam uma sequência de nós
  • Corte: Partição de nós em duas componentes não vazias complementares.
  • Cutset: Conjunto de todas as arestas com exatamente um vértice em cada lado do corte.
81
Q

Defina os seguintes termos no contexto de grafos:
- Ciclo Fundamental
- Cutset Fundamental

A
  • Ciclo Fundamental: Em uma árvore geradora que não contém uma aresta E que liga dois vértices V e W existe um caminho entre os vértices V e W que não passa por E. Ao adicionarmos E, então, criamos um ciclo conhecido como ciclo fundamental.
  • Cutset fundamental: Em uma árvore geradora que contém uma aresta E que liga dois vértices V e W, o único caminho de V para W é pela aresta E. Ao removermos E, então, criamos um cutset conhecido como cutset fundamental.
82
Q

O que podemos afirmar sobre a intersecção entre ciclos e cutsets?

A

Um ciclo e um cutset vão sempre se intersectar em um número par de vértices.

83
Q

Como funciona o algoritmo de Boruvka para encontrar a árvore geradora mínima? Qual regra ela utiliza? Quais decisões de projeto devem ser levadas em consideração para seu funcionamento correto? Por quê?

A

Repita o seguinte processo até existir apenas uma árvore:
- Aplique a regra azul ao cutset de cada árvore.
- Colora todas as arestas selecionadas de azul.

Para que o algoritmo funcione de forma correta, é necessário incluir um critério de desempate para duas arestas com o mesmo peso. Caso contrário, corre o risco de se criar ciclos ao conectar cortes.

84
Q

O que é a regra vermelha e a regra azul? Em qual contexto elas se aplicam?

A

Regra vermelha e regra azul são regras usadas para identificar arestas que pertencem (ou não) à solução do problema da árvore geradora mínima.

Regra vermelha:
- Selecione um ciclo C no grafo sem nenhuma aresta vermelha.
- Colora de vermelho a aresta de maior custo. Ela não fará parte da árvore geradora mínima.

Regra azul:
- Selecione um cutset C num grafo que não inclua nenhuma aresta azul.
- Colora de azul a aresta de menor custo. Ela fará parte da árvore geradora mínima.

85
Q

Como funciona o algoritmo de Prim para encontrar a árvore geradora mínima? Qual regra ela utiliza? Qual sua complexidade otimizada e quais decisões de projeto devem ser levadas em consideração para isso?

A
  • Comece com S = {um nó qualquer}. T = {}.
  • Adicione a T uma aresta com custo mínimo com um terminal em S.
  • Adicione a outra extremidade a S.
  • Repita o processo até todas as arestas estarem em S.

O algoritmo de Prim é baseado na regra azul. Em sua versão otimizada, sua complexidade é O ((V+E) log (V)) e para isso deve ser seguido o mesmo princípio do algoritmo de Dijkstra.

86
Q

Como funciona o algoritmo de Kruskal para encontrar a árvore geradora mínima? Qual regra ela utiliza? Qual sua complexidade otimizada e quais decisões de projeto devem ser levadas em consideração para isso?

A
  • Ordene as arestas em ordem crescente de custo.
  • Para cada aresta E, adicione ela a T caso ela não forme um ciclo com as arestas já presentes em T. Caso contrário, descarte E.
  • Repita até as arestas em T formarem uma árvore geradora.

O algoritmo de Kruskal é baseado na regra azul. Sua complexidade otimizada é O(E log E). Para isso, é necessário usar uma estrutura de dados capaz de identificar ciclos com complexidade mínima, de preferência, a estrutura union-find.

87
Q

Como funciona o algoritmo de Kruskal revertido para encontrar a árvore geradora mínima? Qual regra ela utiliza?

A
  • Ordene as arestas em ordem decrescente de custo e coloque todas elas em T.
  • Para cada aresta em T, remova-a a não ser que sua remoção crie um corte.

Esse algoritmo é baseado na regra vermelha.

88
Q

O que é uma rede de fluxo?

A

É um grafo direcionado com origem s, alvo t em que cada aresta possui uma capacidade c >= 0.

89
Q

O que é um corte em uma rede de fluxo? Como se mede sua capacidade?

A

É uma partição (A, B) dos nós com s ∈ A e t ∈ B. Sua capacidade é a soma das capacidades das arestas de A para B.

90
Q

Em uma rede de fluxo, o que é um fluxo? Qual é seu valor?

A

Um fluxo é uma função f que satisfaz:
- Para cada e ∈ F, 0 <= f(e) <= c(e) (ou seja, a cada aresta é designada um valor menor igual à sua capacidade).
- Com exceção do vértice inicial e o final, para todos os outros vértices, a soma dos fluxos que entram é igual à soma dos fluxos que saem (lei da conservação de fluxo).

O valor de um fluxo é dado pela diferença do fluxo que sai no vértice inicial e o fluxo que entra do vértice inicial.

91
Q

Descreva um algoritmo ganancioso simples capaz de encontrar um fluxo máximo de A até B. Por que ele não encontra o melhor resultado?

A
  • Comece com f(e) = 0 para todas as arestas.
  • Encontre um caminho p entre s e t de modo que todas as arestas tenham f(e) < c(e) (ou seja, o fluxo seja menor que a capacidade).
  • Aumente o fluxo de todas as arestas em p.
  • Repita até parar.

O maior problema desse algoritmo é o fato que uma vez que uma aresta tenha chegado à sua capacidade máxima, ela nunca será esvaziada. Isso quer dizer que uma escolha ruim de arestas pode impedir que o algoritmo encontre o resultado ideal.

92
Q

O que é uma rede residual de fluxo? O que ela representa? Para que ela serve?

A

É uma rede de fluxo que serve como contraponto a um fluxo em uma rede. A rede residual possui as arestas da rede original com capacidade c(e) - f(e) (ou seja, a capacidade do fluxo em uma direção é a capacidade restante da rede) junto com arestas reversas com capacidade f(e) (ou seja, a capacidade da aresta reversa é o próprio fluxo).

A principal utilidade da rede residual de fluxo é a identificação dos caminhos da rede original que podem ser desfeitos.

93
Q

No contexto de redes de fluxo, o que é um caminho aumentante?

A

É um caminho simples s -> t na rede residual Gf.

94
Q

O que é o gargalo da capacidade de um caminho aumentante P?

A

É a capacidade residual mínima de qualquer aresta em P.

95
Q

Como funciona o algoritmo de ford-fulkerson do caminho aumentante?

A
  • Comece com f(e) = 0 para cada aaresta e ∈ E.
  • Encontre um caminho p entre s e t na rede residual Gf.
  • Aumente o fluxo no caminho p.
  • Repita até travar
96
Q

O que diz o lema do valor de fluxo?

A

Seja f um fluxo qualquer em um corte (A, B) qualquer. O fluxo de f é o fluxo líquido que passa pelo corte (A, B).

val(f) = soma do fluxo que sai de A - soma do fluxo que entra em A.

97
Q

O que diz a lei da dualidade fraca no contexto de redes de fluxo?

A

Seja f um fluxo qualquer e (A, B) um corte qualquer. Então val(f) <= cap(A,B).

98
Q

O que é um problema de fluxo máximo? O que é um problema de corte mínimo? Qual a relação entre eles? Como essa relação é conhecida ?

A

O problema do fluxo máximo envolve encontrar o maior fluxo possível em uma rede. O problema do corte mínimo é encontrar o corte em uma rede que possui o menor fluxo possível. A relação entre eles é que o fluxo máximo é o fluxo que passa por um corte mínimo. Essa relação é conhecida como dualidade forte.

99
Q

O que diz o teorema do caminho aumentante no contexto de redes de fluxo?

A

Ele diz que um fluxo f é máximo se e somente se não possui caminhos aumentantes.

100
Q

Qual a complexidade do algoritmo de Ford-Fulkerson? Qual condição as capacidades devem possuir para que ele garantidamente termine? Dê exemplos de casos extremos.

A

O algoritmo de Ford-Fulkerson, no pior caso, possui complexidade de tempo O(mnc). Ele sempre irá terminar se todas as capacidades forem números racionais.

  • Uma aresta possui capacidade ordens de magnitude menor que as outras.
  • Uma aresta possui capacidade r que satisfaz a relação r² = 1 - r.
101
Q

Dê dois exemplos de heurísticas que ajudam a melhorar o desempenho do algoritmo de Ford-Fulkerson.

A
  • Priorizar as arestas com maior gargalo de capacidade.
  • Priorizar caminhos mais curtos.