Fundamentos de Algoritmos e Análise de Complexidade Flashcards
Defina e explique o que significa dizer que uma função possui complexidade O(n).
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
A expressão x = O(n) pode ser escrita como O(n) = x. Verdadeiro ou falso? Justifique.
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)”.
Explique, de forma sucinta, o significado das notações O, Ω, Θ, o e ω. Quai operador aritmético melhor resume o significado dessas notações?
- 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). >
Explique de forma sucinta os seguintes paradigmas de computação:
- Gananciosos
- Força-bruta
- Dividir e Conquistar
- Programação dinâmica
- 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.
Como demonstrar de maneira formal que um loop dentro de um algoritmo é correto?
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).
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?
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).
Um algoritmo O(n²) é mais lento para entradas suficientemente grandes que um algoritmo O(n). Verdadeiro ou falso? Justifique.
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.
Um algoritmo Θ(n²) é sempre mais lento que um algoritmo Θ(n). Verdadeiro ou falso? Justifique.
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.
O que a função Θ(n) representa na seguinte equação?
2n² + 3n + 1 = 2n² + Θ(n). Qual a vantagem desse tipo de representação?
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.
O que a função Θ representa na seguinte equação?
2n² + Θ(n) = Θ(n²). Como interpretar essa equação?
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.
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?
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.
Enumere quais notações (entre O, Ω, Θ, o e ω) possuem as seguintes propriedades:
- Transitividade
- Reflexividade
- Simetria
- 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)) ).
Quais propriedades uma recorrência T(n) tem que possuir para ser considerada algorítmica? Quando isso é convencionalmente usado?
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.
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.
- 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.
Qual o princípio por trás do algoritmo de Strassen para multiplicação de matrizes ?
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.
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)
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.
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?
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.
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)
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.
Quais são as condições para a aplicação do Teorema Mestre para a resolução de recorrências?
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.
Quais são os três casos do Teorema Mestre para resolução de recorrências?
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)).
De maneira simplificada, como identificar qual caso do Teorema mestre deve ser utilizada em um determinado problema?
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.
O que é uma árvore geradora de um grafo? E uma árvore geradora mínima?
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.
Dê três exemplos de circunstâncias que podem levar o Teorema Mestre a não ser aplicável.
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) para alguma constante c < 1
Qual a forma geral da recorrência de Akra-Bazzi? Qual a vantagem de usá-la sobre o Teorema Mestre?
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.
Como usar o método de Akra-Bazzi para resolver recorrências?
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))).
Qual o objetivo do Casamento Estável? Quais termos são relevantes para compreender o problema?
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.
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?
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).
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?
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.
Descreva de maneira simplificada o algoritmo de Gale-Shapley para o problema do Casamento Estável.
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.
Descreva de maneira simplificada o funcionamento do algoritmo de Gale-Shapley para o problema do Casamento Estável.
- 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
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?
O algoritmo de Gale-Shapley maximiza a satisfação de quem escolhe enquanto minimiza a satisfação de quem é escolhido.
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.
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.
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?
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.
Quando podemos dizer que um grafo é uma árvore?
Quando o grafo é conectado e não possui ciclos.
Qual condição um grafo precisa ter para ser considerado conectado? E fortemente conectado?
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.
Quantas arestas possui uma árvore com n vértices?
N - 1 arestas.
De maneira resumida, como funciona o algoritmo BFS? Explique em termos de camadas.
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.
Defina camadas no contexto do algoritmo BFS.
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.
Entre BFS e DFS, qual é melhor para encontrar a menor rota até um ponto? Por quê?
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.
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.
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.
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.
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.
De que forma podemos usar o algoritmo de BFS para identificar se um grafo conexo é bipartido ou não?
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.
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?
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.
Quais são as 4 principais classificações para arestas em um grafo após a execução de um algoritmo como BFS/DFS?
- 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.
Quais tipos de arestas podem ser encontrados em um grafo BFS? Justifique.
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.
Quais tipos de arestas podem ser encontrados em um grafo DFS? Justifique.
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).
Como identificar back edges em um grafo DFS?
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.
Como identificar back edges em um grafo BFS?
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.
Como identificar forward edges em um grafo DFS?
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.
Como identificar cross edges em um grafo DFS?
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.
Como identificar cross edges em um grafo BFS?
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.
Como identificar um ciclo em um grafo a partir dos tipos de suas arestas, do tipo do grafo e do algoritmo usado?
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.
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?
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.
