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.
