Projete um algoritmo em linguagem descritiva que, dada a lista de adjacência de um grafo dirigido acíclico…

Questão

Projete um algoritmo em linguagem descritiva que, dada a lista de adjacência de um grafo dirigido acíclico (DAG) onde cada vértice v tem atributo duracao[v], calcule para cada vértice o menor tempo de término possível assumindo execução paralela ilimitada (ou seja, respeitar dependências).

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Entrada: lista de adjacência adj[], vetor duracao[v] para cada vértice. 1. Calcular indegree[v] para todos os vértices. 2. Inicializar fila Q vazia e vetor inicio[v] = 0. 3. Enfileirar todos os vértices com indegree 0 em Q. 4. Enquanto Q não estiver vazia: a. u = desenfileirar(Q). b. tempo_termino[u] = inicio[u] + duracao[u]. c. Para cada v em adj[u]: i. Atualizar inicio[v] = max(inicio[v], tempo_termino[u]). ii. Decrementar indegree[v]. iii. Se indegree[v] == 0 então enfileirar v em Q. 5. Ao final, tempo_termino[v] contém o menor tempo de término para cada vértice; o tempo total mínimo é max_v tempo_termino[v]. Complexidade: O(V + E) usando lista de adjacência. Observação: algoritmo corresponde a ordenação topológica (Kahn) propagando tempos de início mais cedo.

Explicação

O algoritmo utiliza a técnica de ordenação topológica para processar os vértices de um grafo dirigido acíclico, garantindo que as dependências entre as tarefas sejam respeitadas. Ao calcular o tempo de término de cada vértice com base nos tempos de término dos predecessores, ele assegura que o tempo total mínimo seja obtido de forma eficiente. A complexidade O(V + E) indica que o algoritmo é escalável e adequado para grafos grandes, mantendo a eficiência na propagação dos tempos.

Raio-X da questão

Questões parecidas com resolução

• Lia vai arrumar a mochila para a escola. Como ela pode dividir essa tarefa em partes pequenas?
• O blecaute que interrompeu o funcionamento de um centro comunitário levou os responsáveis a organizar o empréstimo de…
• Uma turma vai criar um aplicativo para organizar tarefas escolares. O grupo percebeu que tentar fazer tudo de uma vez…
• Em um projeto de programação, a turma precisa criar uma solução para várias turmas da escola, com a mesma lógica, mas…
• Uma família quer organizar as despesas do mês em um aplicativo escolar. O processo envolve somar gastos, separar por…
• Ao testar um programa de cadastro, os alunos perceberam que o erro estava apenas na parte que validava o nome do…

Todas as questões de Decomposição