Análise de Complexidade de Algoritmos
62 Questions
2 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Qual é o principal objetivo do trabalho prático descrito?

  • Otimizar a utilização de recursos
  • Resolver o problema de Job-Shop com a técnica de branch-and-bound
  • Comparar a eficiência de diferentes algoritmos de otimização
  • Utilizar as capacidades de programação paralela através do modelo de partilha de memória (correct)

    • Em que consiste o problema de Job-Shop?

  • Distribuição de tarefas entre várias máquinas
  • Otimização da sequência de operações em uma máquina única
  • Alocação de recursos para a concretização de um trabalho (correct)
  • Minimização do tempo de produção de um trabalho

    • Como são as sequências de máquinas para cada trabalho?

  • Sempre a mesma para todos os trabalhos
  • Diferente para cada trabalho, mas a ordem é aleatória
  • Diferente para cada trabalho, e a ordem precisa ser respeitada (correct)
  • Inexistente, pois apenas uma máquina é utilizada

    • Qual é a restrição fundamental no problema de Job-Shop?

    <p>A ordem das operações para cada trabalho</p> Signup and view all the answers

    Como isso afeta a resolução do problema de Job-Shop?

    <p>complica a resolução do problema</p> Signup and view all the answers

    Qual técnica de otimização pode ser utilizada para resolver o problema de Job-Shop?

    <p>Algoritmo de branch-and-bound</p> Signup and view all the answers

    Qual é a complexidade computacional do problema de Job-Shop?

    <p>NP-difícil</p> Signup and view all the answers

    Qual é a importância do problema de Job-Shop em Pesquisa Operacional?

    <p>É um problema fundamental em Pesquisa Operacional</p> Signup and view all the answers

    Qual é o objetivo da abordagem de atribuição de tempos de início no problema de Job-Shop?

    <p>Atribuir tempos de início às operações respeitando a sua duração</p> Signup and view all the answers

    Que técnica de otimização é mencionada como capaz de encontrar a melhor solução ótima para o problema de Job-Shop?

    <p>Branch-and-Bound</p> Signup and view all the answers

    Qual é o nome dado à abordagem que executa uma operação e apenas uma operação em cada instante de tempo, sem intervalos?

    <p>Case Sequencial</p> Signup and view all the answers

    O que é construído pela abordagem de Branch-and-Bound para encontrar a melhor solução ótima para o problema de Job-Shop?

    <p>Uma árvore de pesquisa</p> Signup and view all the answers

    Qual é o critério para considerar uma solução válida no problema de Job-Shop?

    <p>Que respeite as restrições do problema</p> Signup and view all the answers

    O que é o pior caso possível no problema de Job-Shop?

    <p>O tempo necessário para executar todas as operações, uma de cada vez, até estarem todas concluídas</p> Signup and view all the answers

    Qual é o objetivo da atribuição de tempos de início no problema de Job-Shop?

    <p>Minimizar o tempo total de produção</p> Signup and view all the answers

    Qual é a característica da abordagem de Branch-and-Bound mencionada no texto?

    <p>É uma abordagem que constrói uma árvore de pesquisa</p> Signup and view all the answers

    Qual é a restrição mais importante a ser considerada no problema de escalonamento de produção?

    <p>As operações de cada trabalho têm de ser realizadas por ordem.</p> Signup and view all the answers

    O que é o objetivo principal do problema de escalonamento de produção?

    <p>Minimizar o tempo de execução total do escalonamento.</p> Signup and view all the answers

    Quais são as duas restrições mais importantes do problema de escalonamento de produção?

    <p>As operações de cada trabalho têm de ser realizadas por ordem e uma máquina só consegue executar uma operação de cada vez.</p> Signup and view all the answers

    Em que ordem devem ser realizadas as operações de cada trabalho?

    <p>Em ordem sequencial.</p> Signup and view all the answers

    Qual é o nome do algoritmo que pode ser utilizado para resolver o problema de escalonamento de produção?

    <p>Algoritmo de Branch-and-Bound.</p> Signup and view all the answers

    Qual é o objetivo secundário do problema de escalonamento de produção?

    <p>Minimizar o tempo de execução total do escalonamento.</p> Signup and view all the answers

    Quais são as variáveis mais importantes a serem consideradas no problema de escalonamento de produção?

    <p>Todos os acima.</p> Signup and view all the answers

    O que é um escalonamento válido no contexto do problema de escalonamento de produção?

    <p>Um plano de escalonamento que considera as restrições das operações de cada trabalho.</p> Signup and view all the answers

    Qual é o tipo de problema que o Job-Shop se enquadra?

    <p>Problema de otimização combinatória</p> Signup and view all the answers

    Qual é a técnica de otimização mencionada no texto como capaz de encontrar a melhor solução ótima para o problema de Job-Shop?

    <p>Branch-and-Bound</p> Signup and view all the answers

    Qual é a restrição fundamental no problema de Job-Shop?

    <p>Ordem de execução das operações</p> Signup and view all the answers

    Qual é o objetivo da abordagem de atribuição de tempos de início no problema de Job-Shop?

    <p>Encontrar a melhor sequência de operações</p> Signup and view all the answers

    Qual é a característica da abordagem de Branch-and-Bound mencionada no texto?

    <p>É um algoritmo exaustivo</p> Signup and view all the answers

    Qual é o nome da abordagem que executa uma operação e apenas uma operação em cada instante de tempo, sem intervalos?

    <p>Sequencial</p> Signup and view all the answers

    Qual é a característica fundamental de uma solução válida no problema de Job-Shop?

    <p>Respeitar a duração de cada operação</p> Signup and view all the answers

    Que técnica de otimização pode ser utilizada para encontrar uma solução melhor do que a pior solução possível?

    <p>Branch &amp; Bound</p> Signup and view all the answers

    Qual é a principal diferença entre a abordagem sequencial e a abordagem de Branch & Bound?

    <p>A abordagem de Branch &amp; Bound é mais precisa</p> Signup and view all the answers

    Por que a abordagem de Branch & Bound não pode encontrar uma solução pior do que a pior solução possível?

    <p>Porque respeita a duração de cada operação</p> Signup and view all the answers

    O que é construído pela abordagem de Branch & Bound para encontrar a melhor solução ótima para o problema de Job-Shop?

    <p>Uma árvore de pesquisa</p> Signup and view all the answers

    Qual é a restrição fundamental a ser considerada no problema de Job-Shop?

    <p>A duração de cada operação</p> Signup and view all the answers

    O que é o pior caso possível no problema de Job-Shop?

    <p>O tempo necessário para executar todas as operações, uma de cada vez, até estarem todas concluídas</p> Signup and view all the answers

    Qual é a característica da solução algorítmica para o problema de Job-Shop?

    <p>Deve ser melhor do que a pior solução possível</p> Signup and view all the answers

    Qual é a principal informação armazenada na estrutura Schedule?

    <p>Hora de início e fim de uma operação específica numa máquina</p> Signup and view all the answers

    Qual é a função da função compare_shedules()?

    <p>Ordenar operações pelo tempo de início</p> Signup and view all the answers

    Qual é a informação contida em cada linha do ficheiro de entrada?

    <p>Identificador de máquina e tempo de processamento da operação</p> Signup and view all the answers

    Qual é a estrutura que representa o estado atual do processo?

    <p>Node</p> Signup and view all the answers

    Qual é o objetivo da função auxiliar para a escrita dos resultados?

    <p>Escrever o melhor tempo encontrado no ficheiro de saída</p> Signup and view all the answers

    Qual é a informação utilizada para preencher a estrutura de dado job?

    <p>Ficheiro de entrada</p> Signup and view all the answers

    Qual é a característica da estrutura job?

    <p>Tem um conjunto de operações e um número máximo de operações que precisa de ser realizado</p> Signup and view all the answers

    Qual é o propósito do array temporário criado para os cronogramas das operações?

    <p>Ordenar operações pelo tempo de início</p> Signup and view all the answers

    Qual é o propósito do uso do OpenMP na implementação paralela do algoritmo de Job-Shop?

    <p>Marcar um bloco de código como uma tarefa que pode ser executada de forma assíncrona</p> Signup and view all the answers

    Como as threads são inicializadas na implementação paralela do algoritmo de Job-Shop?

    <p>Através da diretiva #pragma omp parallel</p> Signup and view all the answers

    Qual é o número de threads utilizado na implementação paralela do algoritmo de Job-Shop?

    <p>Número de threads definido pelo usuário</p> Signup and view all the answers

    Como as chamadas recursivas de função são tratadas na implementação paralela do algoritmo de Job-Shop?

    <p>São encapsuladas dentro de uma tarefa paralela</p> Signup and view all the answers

    Qual é a estrutura de dados utilizada na implementação paralela do algoritmo de Job-Shop?

    <p>Estruturas job, operation, Schedule e node</p> Signup and view all the answers

    Qual é o objetivo da utilização do lock do OpenMP na implementação paralela do algoritmo de Job-Shop?

    <p>Garantir a exclusão mútua durante a leitura e escrita das variáveis compartilhadas</p> Signup and view all the answers

    Como os ramos da árvore de decisão são explorados nas threads paralelas?

    <p>De forma concorrente</p> Signup and view all the answers

    Qual é o algoritmo utilizado na implementação paralela do Job-Shop?

    <p>Branch and Bound</p> Signup and view all the answers

    Como são protegidas as variáveis best_time e best_node de atualizações concorrentes em um ambiente paralelo?

    <p>Utilizando-se o lock OpenMP para garantir exclusividade.</p> Signup and view all the answers

    Qual é o objetivo da utilização do lock OpenMP em relação às variáveis best_time e best_node?

    <p>Garantir que as atualizações sejam feitas de forma exclusiva.</p> Signup and view all the answers

    Como são utilizadas as variáveis best_time e best_node no programa paralelo?

    <p>São utilizadas para leitura e escrita, protegidas por um lock.</p> Signup and view all the answers

    Qual é a função do lock no programa paralelo?

    <p>Garantir que as atualizações sejam feitas de forma exclusiva.</p> Signup and view all the answers

    Como são utilizadas as variáveis locais new_node e node no programa paralelo?

    <p>São utilizadas de forma independente em cada thread.</p> Signup and view all the answers

    Qual é a vantagem de utilizar variáveis locais em cada thread no programa paralelo?

    <p>Garantir que as threads trabalhem de forma independente.</p> Signup and view all the answers

    Quais são as variáveis globais partilhadas para leitura no programa paralelo?

    <p>NUM_MACHINES e NUM_JOBS.</p> Signup and view all the answers

    Qual é a razão pela qual as variáveis best_time e best_node precisam ser protegidas em um ambiente paralelo?

    <p>Para evitar que as atualizações sejam feitas concorrentemente.</p> Signup and view all the answers

    Study Notes

    Problema de Job-Shop

    • O problema de Job-Shop é a alocação de recursos para a concretização de um trabalho, envolvendo várias máquinas que realizam operações.
    • Cada trabalho é uma sequência de operações, em que cada operação tem de ser feita numa máquina específica.
    • A ordem das máquinas para cada trabalho tem de ser respeitada, e uma operação de um trabalho só pode começar quando a operação anterior desse mesmo trabalho já terminou.

    Abordagens para Atribuição dos Tempos de Início

    • Existem várias abordagens para atribuir tempos de início às operações, como o método sequencial, que atribui um tempo de início a todas as operações, respeitando a sua duração.
    • Outras abordagens válidas incluem Branch & Bound e Shifting Bottleneck.

    Restrições do Problema

    • As operações de cada trabalho têm de ser realizadas por ordem.
    • Uma máquina só consegue executar uma operação de cada vez.

    Características do Problema

    • Um trabalho não depende dos restantes trabalhos, ou seja, os trabalhos são independentes entre si.
    • As operações de um trabalho não interferem com as operações dos restantes trabalhos, desde que a máquina esteja livre.

    Objetivo do Problema

    • O objetivo é apresentar um escalonamento válido, definindo um tempo de início para cada operação, de modo a cumprir as restrições.
    • O segundo objetivo é otimizar o tempo de execução total do escalonamento.

    Introdução ao Trabalho Prático de Job-Shop

    • O trabalho prático de Job-Shop é um problema de programação de máquinas que envolve a atribuição de tempos de início para operações em máquinas diferentes.
    • O objetivo é encontrar a melhor solução que minimize o tempo total de produção.

    Descrição do Problema

    • O problema de Job-Shop é representado por uma estrutura de dados que inclui jobs, operações e máquinas.
    • Cada job é composto por várias operações que devem ser realizadas em máquinas específicas.

    Abordagem para Atribuição dos Tempos de Início

    • Existem várias abordagens para a atribuição de tempos de início, incluindo o método sequencial e o método Branch-and-Bound.
    • O método sequencial atribui um tempo de início às operações de cada job, respeitando a duração de cada operação.
    • O método Branch-and-Bound constrói uma árvore de pesquisa que registra as várias soluções encontradas e o seu resultado.

    Implementação Sequencial

    • A implementação sequencial utiliza o método Branch-and-Bound para encontrar a melhor solução.
    • O método Branch-and-Bound é uma abordagem que constrói uma árvore de pesquisa que registra as várias soluções encontradas e o seu resultado.

    Implementação Paralela com Partilha de Memória

    • A implementação paralela utiliza o método Branch-and-Bound em paralelo, dividindo o processo em várias threads.
    • Cada thread trabalha de forma independente para explorar diferentes combinações de escalonamento de jobs.
    • A implementação paralela utiliza o OpenMP para sincronizar as threads e garantir a exclusão mútua durante a leitura e escrita das variáveis compartilhadas.

    Proposta de Particionamento

    • A proposta de particionamentodivide o processo em várias threads que trabalham de forma independente para explorar diferentes combinações de escalonamento de jobs.

    Implementação do Algoritmo Paralelo

    • A implementação do algoritmo paralelo utiliza o OpenMP para sincronizar as threads e garantir a exclusão mútua durante a leitura e escrita das variáveis compartilhadas.
    • Cada thread executa a função Branch and Bound de forma independente, utilizando a mesma estrutura de dados utilizada na implementação sequencial.

    Características do Programa Paralelo

    • O programa paralelo utiliza variáveis globais partilhadas, como jobs, best time e best node, que são protegidas por um lock para garantir operações seguras em ambientes paralelos.
    • O programa paralelo também utiliza variáveis locais de cada thread, como new node e node, que são utilizadas para explorar diferentes combinações de escalonamento de jobs.

    Studying That Suits You

    Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

    Quiz Team

    Related Documents

    18885MarianaCarvalho_30035ThalissonSchumaber_30036RubenMachado.pdf

    Description

    Este quiz aborda conceitos de análise de complexidade de algoritmos, incluindo o melhor e pior caso possível, e como calcular o tempo de produção. Teste seu conhecimento sobre este tópico importante em ciência da computação.

    More Like This

    Big Theta Notation in Algorithm Complexity
    3 questions

    Big Theta Notation in Algorithm Complexity

    MemorableMaxwell avatar
    MemorableMaxwell
    Understanding Space Complexity in Algorithms
    17 questions

    Understanding Space Complexity in Algorithms

    GladRainbowObsidian avatar
    GladRainbowObsidian
    Computational Complexity of Frequent Itemset Mining
    10 questions

    Computational Complexity of Frequent Itemset Mining

    GlisteningLongBeach avatar
    GlisteningLongBeach
    Algorithm Complexity
    18 questions

    Algorithm Complexity

    IndebtedNash avatar
    IndebtedNash
    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser