Algoritmos Flashcards
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.
Qual o paradigma usado pelo algoritmo de Strassen?
Dividir para Conquistar
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.
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 a abordagem 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.
Explique, de forma simples, o algoritmo de Kosaraju para detecção de Componentes Fortemente Conectados.
- 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.
Explique, de forma simples, o algoritmo de Tarjan para detecção de Componentes Fortemente Conectados.
- 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
Qual a intuição por trás do algoritmo de Kosaraju para detecção de SCCs?
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.
Qual a intuição por trás do algoritmo de Tarjan para detecção de SCCs?
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.
Explique, de forma simples, o funcionamento do algoritmo de Kahn para a ordenação topológica de um DAG.
- 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.
Demonstre o porquê de o algoritmo de Kahn 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?
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)
De maneira simplificada, como funciona e para que serve o algoritmo de Dijkstra? Qual pré-requisito deve ser atingido para que ele funcione?
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.
Construa o pseudocódigo do algoritmo de Dijkstra.
- Marque a distância do vértice inicial como 0 e todas as outras como infinito
- Marque o antecessor de todos os vértices como desconhecido
- Enquanto houver um vértice não visitado, faça:
- Escolha o vértice S com menor distância
- Para cada vizinho de S, atualize a distância como sendo o menor valor entre a distância atual e a distância de S somada à aresta.
- Se a distância do vizinho de S foi atualizada, atualize também seu antecessor para S.
- Após fazer isso para cada vizinho de S, marque-o como visitado e repita o processo
Qual parte do algoritmo de Dijkstra mais se beneficia de otimizações? Dê dois exemplos de otimizações possíveis, sua complexidade assintótica e a complexidade assintótica do algoritmo de Dijkstra não-otimizado.
O algoritmo de Dijkstra não otimizado possui complexidade O(V²). A parte mais susceptível a otimizações é o processo de encontrar o vizinho com menor distância; ao usarmos uma fila de prioridade, a complexidade é melhorada para O(E log V). Ao usarmos um heap fibonacci, a complexidade é melhorada para O(E + V log V)
Dê dois exemplos de adaptações que podem ser feitas para o algoritmo de Dijkstra funcionar para grafos não direcionados.
1 - Troque cada aresta direcionada por duas arestas antiparalelas de mesmo peso.
2 - Ao analisar cada vértice, considere também as arestas incidentes.
Por que o algoritmo de Dijkstra não retorna o menor caminho se há arestas com peso negativo?
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.
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ê?
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.
Como funciona a contração no algoritmo de Boruvka para encontrar a árvore geradora mínima? Qual a vantagem de fazer a contração?
Após cada iteração do algoritmo, a contração unifica a árvore gerada em um único supervértice. Para isso, remova todas as arestas internas e, entre as externas paralelas, mantenha apenas as de menor custo.
Ao fazer a contração, o algoritmo de Boruvka pode ser simplifcado para, a cada iteração, encontrar a aresta de menor custo associada a cada vértice.
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?
- 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.
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?
- 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.
Como funciona o algoritmo de Kruskal revertido para encontrar a árvore geradora mínima? Qual regra ela utiliza?
- 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.
Como funciona o algoritmo de ford-fulkerson do caminho aumentante?
- 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
Quais são os dois tipos possíveis de aumentação no algoritmo de Dinitz?
- Normal (tamanho do caminho mínimo não muda)
- Especial (tamanho do caminho mínimo aumenta)
Qual é o pseudocódigo do algoritmo de Dinitz para o fluxo máximo?
1 - Construa o grafo de nível para a rede residual de fluxo.
2 - Encontre o fluxo máximo envolvendo caminhos que possuem exatamente um vértice em cada nível.
3 - Repita as etapas anteriores até não ser possível construir nenhum caminho.
Defina a complexidade assintótica dos seguintes algoritmos:
- Dinitz
- Ford-Fulkerson
- Caminho aumentante mais curto
- Escalonamento de capacidade
- Dinitz: O(m n²).
- Ford–Fulkerson: O(m n C).
- Caminho aumentante mais curto: O(m² n).
- Escalonamento de capacidade: O(m² log C).
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.
O algoritmo de Ford-Fulkerson, no pior caso, possui complexidade de tempo O(m * n * c). 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.
Como funciona o algoritmo de escalonamento de capacidade ?
- Defina um fator de escala Δ.
- Crie um grafo residual Gf contendo apenas as arestas com capacidade maior ou igual a Δ.
- Aplique o algoritmo de Ford-Fulkerson em Gf.
- Após o término, divida Δ por 2 e repita até um grafo Gf contendo todas as arestas originais.
Dê dois exemplos de heurísticas que ajudam a melhorar o desempenho do algoritmo de Ford-Fulkerson.
- Priorizar as arestas com maior gargalo de capacidade.
- Priorizar caminhos mais curtos.
Construa um algoritmo capaz de contar as inversões em um array (uma inversão ocorre quando existem dois elementos ai e aj tais que i < j mas ai > aj). Qual a sua complexidade? Qual algoritmo famoso possui funcionamento similar a este?
O princípo do algoritmo é o mesmo do merge sort e:
- Recursivamente, divida a lista em n/2 listas até cada lista ter tamanho 1.
- Ao combinar as listas, conte as inversões nesse nível e então ordene-as. Visto que as listas de tamanho n/2 estão ordenadas, não é necessário comparar todos os elementos; se o i-ésimo elemento da lista da esquerda é menor que o j-ésimo elemento da lista da direita, ele também é menor que os elementos posteriores a j.
A complexidade é a mesma do Merge Sort; ele realiza o merge sort e faz a contagem de inversões durante a etapa do merge, sem custo assintótico adicional.
Construa um algoritmo que encontre o k-ésimo menor elemento em um array desordenado com complexidade de tempo O(n) no caso médio.
- Escolha um elemento aleatório p em um array.
- Crie três arrays auxiliares: menor, maior e igual. Itere pelo array e coloque cada item no array correspondente.
- Identifique o sub-array onde o k-ésimo elemento está e repita o processo.
Construa um algoritmo que encontre, de maneira eficiente, os dois pontos mais próximos em um plano cartesiano.
- Divida recursivamente a lista de n pontos em listas de n/2 pontos até cada lista ter um elemento.
- Ao combinar as listas, salve em uma variável o valor da menor distância entre dois elementos no array à esquerda e a menor distância entre dois elementos no array à direita.
- Para identificar a menor distância entre elementos de lados opostos, começamos identificando a menor das distâncias salvas na etapa anterior.
- Remova do processo todos os elementos com distância maior até a divisória. Entre os elementos restantes, ordene-os pelo eixo y.
- Compare cada elemento com os elementos do lado oposto com até 7 posições de diferença. Registre a menor distância encontrada.
- Retorne a menor das três distâncias encontradas e repita o processo de forma recursiva.
Qual paradigma e abordagem produz a solução ótima para o problema de agendar tarefas em um dia de modo que o máximo de tempo possível seja ocupado?
Paradigma ganancioso, agendando tarefas (compatíveis) em ordem crescente de hora de término.
Qual paradigma e algoritmo produz a solução ótima para o problema de agendar tarefas em um dia de modo a maximizar o valor obtido por elas? Qual a complexidade base desse algoritmo? Como melhorá-la?
Paradigma dinâmico.
- Comece ordenando as atividades em ordem crescente de término.
- Para cada atividade, guarde o valor p(j) = maior i < j tal que as atividades i e j são compatíveis
- Para cada elemento i, calcule o maior valor entre o maior valor obtido escolhendo o elemento i e o maior valor não escolhendo esse elemento. Para isso, use o valor p(j) para acessar o próximo elemento compatível com j.
A complexidade básica desse algoritmo é exponencial, visto que ele realiza a mesma operação várias vezes. É possível reduzi-la para n log n armazenando os valores calculados em um cache, de modo que cada cálculo seja realizado apenas uma vez.
Qual paradigma e algoritmo produz a solução ótima para o problema do subarray contíguo com soma máxima? Qual o nome e a complexidade desse algoritmo?
Paradigma dinâmico.
- Itere por todos os elementos do array. Para cada elemento, armazene nele o maior entre o próprio elemento e o elemento somado ao valor salvo no elemento anterior
- A maior soma em um subarray contíguo é o maior valor armazenado nesse processo. Se for necessário identificar os elementos do subarray, basta começar no elemento com soma máxima e iterar pelos elementos à esquerda.
O algoritmo é conhecido como algoritmo de Kadane e possui complexidade O(n).
Qual paradigma e algoritmo produz a solução ótima para o problema de armazenar itens em uma sacola de modo a maximizar o valor total? Qual a complexidade base desse algoritmo? Como melhorá-la?
Paradigma dinâmico.
- Para cada item, calcule o maior valor entre o maior valor obtido ao colocá-lo na sacola e tentar colocar o próximo (com o peso disponível reduzido) ou não colocar o elemento e tentar colocar o próximo na sacola. Retorne o maior valor obtido pelo processo.
A complexidade básica desse algoritmo é exponencial, visto que ele realiza a mesma operação várias vezes. É possível reduzi-la para n log n armazenando os valores calculados em uma tabela (N x (W + 1)) em que N são os itens 0, 1, 2, …, n e W é o peso máximo, com o valor T[i][j] representando o máximo valor obtível com o elemento i em uma mochila com capacidade j.
Qual o pressuposto principal do algoritmo do valor máximo armazenável em uma mochila? Por que esse pressuposto é necessário? De que forma é possível fazer adaptações nessa solução para ser aplicável a esse tipo de situação?
O pressuposto usado é o de que os pesos na mochila são valores inteiros. Isso é necessário porque a tabela armazena todas as combinações possíveis de pesos e itens menor que o peso limite. Para aplicar o problema a pesos não inteiros, é necessário convertê-los para inteiro, potencialmente multiplicando-os por uma potência de 10 grande o suficiente para torná-los inteiros.
