Algoritmos de Dijkstra e Huffman: Questões sobre Caminho Mínimo e Compressão de Dados

PERGUNTA 1 Na determinação do caminho mínimo entre dois vértices de um grafo o algoritmo de se aplica a problemas que podem ser representados por um grafo simples e em que os pesos são O Huffman conexo arestas positivo O Strasson acíclico vértices distintos O Prim não conexo vértices iguais O Dijkstra conexo pesos positivo O Huffman conexo arestas iguais PERGUNTA 2 Com relação ao procedimento utilizado pelo algoritmo de Huffman para a construção de uma árvore binária para o problema de compressão de dados de um arquivo podemos afirmar que I A construção da árvore é realiza no sentido da base pera a raiz da árvore final de baixo para cima II Para um arquivo que contenha n símbolos caracteres distintos Inicialmente cada símbolo representará um nó rotulado com a sua frequência de ocorrência III Durante a execução do algoritmo de Huffman serão realizadas n1 intercalações para um arquivo contendo n símbolos distintos O As afirmações I e III estão corretas Nenhuma das afirmações está correta Todas as afirmações estão corretas Somente a afirmação I está correta As afirmações I e III estão corretas PERGUNTA 3 Em relação ao algoritmo de Dijkstra podemos afirmar que I O algoritmo de Dijkstra se aplica a problemas que podem ser representados por um grafo simples conexo e com pesos em que os pesos são positivos II O algoritmo de Dijkstra utiliza a estratégia de divisão e conquista para resolver o problema de caminho mínimo em um grafo III O algoritmo de Dijkstra nos fornece a solução para encontrarmos o caminho com peso mínimo entre dois vértices de um grafo simples conexo e com peso em que os pesos são positivos O Todas as afirmações estão corretas Nenhuma das afirmações está correta As afirmações I e III estão corretas As afirmações II e III estão corretas Somente a afirmação I está correta PERGUNTA 4 Na representação do através de uma cada representa um que foi codificado O algoritmo de Strassen matriz binária valor vetor O problema do caminho mínimo árvore binária aresta peso O código de Huffman árvore binária folha símbolo O problema de seleção de atividades fila elemento tempo O algoritmo de Dijkstra recursão instância vetor PERGUNTA 5 Em relação a algoritmos gulosos podemos afirmar que I Algoritmos gulosos normalmente são utilizados em problemas de otimização embora nem sempre produzam soluções ótimas II Um algoritmo guloso a cada passo buscará uma escolha que parece ser a melhor ótima no momento em questão III A estratégia dos algoritmos gulosos de resolver sucessivamente problemas menores até atingirem uma solução global leva forçosamente ao projeto de algoritmos recursivos O Somente a afirmação I está correta O Todas as afirmações estão corretas O As afirmações I e II estão corretas O Nenhuma das afirmações está correta O As afirmações II e III estão corretas PERGUNTA 6 Em relação ao problema conhecido como problema do caminho mínimo podemos afirmar que I Tanto o algoritmo de Dijkstra quanto o algoritmo de Huffman utilizam a estratégia gulosa para solução desse problema II O problema do caminho mínimo possui importantes aplicações na área de redes de computadores ou de comunicação em que as redes podem ser modeladas através de grafos e onde se deseja que a informação em um nó da rede seja enviada a outro nó do modo mais eficiente possível III A determinação do caminho mínimo pode ser aplicado a redes de transporte de cadeias logísticas em que os produtos de uma localidade têm que ser enviados a outra O Todas as afirmações estão corretas O As afirmações I e III estão corretas O Nenhuma das afirmações está correta O As afirmações II e III estão corretas O Somente a afirmação I está correta 1 PERGUNTA 7 Em relação as estratégias utilizadas para compactação compressão de dados de forma eficiente em um arquivo contendo símbolos caracteres podemos afirmar I Uma estratégia é codificar símbolos pouco frequentes através de sequências mais longas de bits e utilizar sequência mais curtas de bits para símbolos mais frequentes com isso a quantidade total de espaço deverá ser reduzida II A codificação de símbolos em sequências de bits de tamanhos desiguais pode levar a problemas de ambiguidade na decodificação por isso é necessário a utilização de códigos de prefixo III A representação dos símbolos e a construção de códigos de compressão de dados podem ser descritos através de uma série de ações executadas em árvores binárias O Nenhuma das afirmações está correta O Somente a afirmação I está correta O As afirmações II e III estão corretas O Todas as afirmações estão corretas O As afirmações I e III estão corretas PERGUNTA 1 A se aplica quando os se isto é quando os subproblemas subsubproblemas O indução matemática casos base somam possuem O programação dinâmica subproblemas sobrepõem compartilham O recorrência algoritmos intercalam misturam O técnica gulosa problemas misturam compõem O divisão e conquista algoritmos dividem não possuem PERGUNTA 2 Na programação dinâmica a é utilizada para que o algoritmo resolva subproblemas O recursão forçar repetidamente não resolvidos O pilha evitar sempre recorrentes O divisão forçar vários concomitantemente O tabela garantir sempre recorrentes O memoização evitar novamente já resolvidos PERGUNTA 3 Quando um problema apresenta subestrutura ótima podemos afirmar que I A solução ótima para o problema incorpora soluções ótimas para subproblemas relacionados II A solução ótima para o problema é na verdade subótima III A programação dinâmica não pode ser aplicada para resolver o problema pois só é aplicável em problemas que apresentam estrutura ótima O Todas as afirmações estão corretas O As afirmações II e III estão corretas O Nenhuma das afirmações está correta O As afirmações I e III estão corretas O Somente a afirmação I está correta PERGUNTA 4 No problema do corte de barras um algoritmo que buscasse a solução que maximizasse o lucro no corte de uma barra de comprimento de n metros em que n é um inteiro e onde se tem a opção de cortar a barra em pedaços de tamanhos i 1 i n um inteiro sendo que para cada comprimento de corte o lucro distinto Se esse algoritmo utilizasse força bruta para determinar qual a opção de cortes que maximiza o lucro na venda esse algoritmo teria que analisar quantas possibilidades O n² O n lgn O n O 2ⁿ1 O n1 2 PERGUNTA 5 O custo computacional em termos de número de multiplicações para a multiplicação da cadeia de matrizes A B C D parentizada na forma A x B x C x D em que as dimensões das matrizes número de linhas x número de colunas é como segue A é uma matriz 10 x 20 B uma matriz 20 x 1 C uma matriz 1 x 10 e D uma matriz 10 x 10 O 400 O 8000 O 40000 O 620 O 250 PERGUNTA 6 No problema de multiplicação de cadeias de matrizes podemos afirmar que I A ordem que as multiplicações são feitas pode alterar o custo computacional da multiplicação II A reordenação troca de posição das matrizes é a estratégia utilizada pelos algoritmos para otimização do cálculo III Determinar a parentização corresponde a determinar qual a ordem em que as matrizes serão multiplicadas O Nenhuma das afirmações está correta O Todas as afirmações estão corretas O Somente a afirmação I está correta O As afirmações II e III estão corretas O As afirmações I e III estão corretas PERGUNTA 7 Em relação à memoização é correto afirmar I É uma técnica que consiste em a salvar o resultado dos subproblemas resolvidos de modo que possam ser consultados posteriormente evitando resolver subproblemas que já foram resolvidos II Na programação dinâmica pode ser feio uso da memoização III Na programação dinâmica algoritmos na forma bottomup fazem uso de memoização O Todas as afirmações estão corretas O Somente a afirmação I está correta O As afirmações I e II estão corretas O As afirmações II e III estão corretas O Nenhuma das afirmações está correta PERGUNTA 1 Na determinação do caminho mínimo entre dois vértices de um grafo o algoritmo de se aplica a problemas que podem ser representados por um grafo simples e com em que os pesos são Huffman conexo arestas positivo Strasson acíclico vértices distintos Prim não conexo vértices iguais Dijkstra conexo pesos positivo Huffman conexo arestas iguais PERGUNTA 2 Com relação ao procedimento utilizado pelo algoritmo de Huffman para a construção de uma árvore binária para o problema de compressão de dados de um arquivo podemos afirmar que A construção da árvore é realiza no sentido da base para a raiz da árvore final de baixo para cima Para um arquivo que contenha n símbolos caracteres distintos Inicialmente cada símbolo representará um nó rotulado com a sua frequência de ocorrência Durante a execução do algoritmo de Huffman serão realizadas n1 intercalações para um arquivo contendo n símbolos distintos As afirmações I e III estão corretas Nenhuma das afirmações está correta Todas as afirmações estão corretas Somente a afirmação I está correta As afirmações I e III estão corretas PERGUNTA 3 Em relação ao algoritmo de Dijkstra podemos afirmar que I O algoritmo de Dijkstra se aplica a problemas que podem ser representados por um grafo simples conexo e com pesos em que os pesos são positivos II O algoritmo de Dijkstra utiliza a estratégia de divisão e conquista para resolver o problema de caminho mínimo em um grafo III O algoritmo de Dijkstra nos fornece a solução para encontrarmos o caminho com peso mínimo entre dois vértices de um grafo simples conexo e com peso em que os pesos são positivos Todas as afirmações estão corretas Nenhuma das afirmações está correta As afirmações I e III estão corretas As afirmações II e III estão corretas Somente a afirmação I está correta PERGUNTA 4 Na representação do através de uma cada representa um que foi codificado algoritmo de Strassen matriz binária valor vetor problema do caminho mínimo árvore binária aresta peso código de Huffman árvore binária folha símbolo problema de seleção de atividades fila elemento tempo algoritmo de Dijkstra recursão instância vetor PERGUNTA 5 Em relação a algoritmos gulosos podemos afirmar que I Algoritmos gulosos normalmente são utilizados em problemas de otimização embora nem sempre produzam soluções ótimas II Um algoritmo guloso a cada passo buscará uma escolha que parece ser a melhor ótima no momento em questão III A estratégia dos algoritmos gulosos de resolver sucessivamente problemas menores até atingirem uma solução global leva forçosamente ao projeto de algoritmos recursivos Somente a afirmação I está correta Todas as afirmações estão corretas As afirmações I e II estão corretas Nenhuma das afirmações está correta As afirmações II e III estão corretas PERGUNTA 6 Em relação ao problema conhecido como problema do caminho mínimo podemos afirmar que Tanto o algoritmo de Dijkstra quanto o algoritmo de Huffman utilizam a estratégia gulosa para solução desse problema O problema do caminho mínimo possui importantes aplicações na área de redes de computadores ou de comunicação em que as redes podem ser modeladas através de grafos e onde se deseja que a informação em um nó da rede seja enviada a outro nó do modo mais eficiente possível A determinação do caminho mínimo pode ser aplicado a redes de transporte de cadeias logísticas em que os produtos de uma localidade têm que ser enviados a outra Todas as afirmações estão corretas As afirmações I e III estão corretas Nenhuma das afirmações está correta As afirmações II e III estão corretas Somente a afirmação I está correta 4 PERGUNTA 7 Em relação às estratégias utilizadas para compactação compressão de dados de forma eficiente em um arquivo contendo símbolos caracteres podemos afirmar Uma estratégia é codificar símbolos pouco frequentes através de sequências mais longas de bits e utilizar sequência mais curtas de bits para símbolos mais frequentes com isso a quantidade total de espaço deverá ser reduzida A codificação de símbolos em sequências de bits de tamanhos desiguais pode levar a problemas de ambiguidade na decodificação por isso é necessário a utilização de códigos de prefixo III A representação dos símbolos e a construção de códigos de compressão de dados podem ser descritos através de uma série de ações executadas em árvores binárias Nenhuma das afirmações está correta Somente a afirmação I está correta As afirmações II e III estão corretas Todas as afirmações estão corretas As afirmações I e III estão corretas PERGUNTA 1 A se aplica quando os se isto é quando os subproblemas subsubproblemas indução matemática casos base somam possuem programação dinâmica subproblemas sobrepõem compartilham recorrência algoritmos intercalam misturam técnica gulosa problemas misturam compõem divisão e conquista algoritmos dividem não possuem PERGUNTA 2 Na programação dinâmica a é utilizada para que o algoritmo resolva subproblemas recursão forçar repetidamente não resolvidos pilha evitar sempre recorrentes divisão forçar vários concomitantemente tabela garantir sempre recorrentes memoização evitar novamente já resolvidos PERGUNTA 3 Quando um problema apresenta subestrutura ótima podemos afirmar que I A solução ótima para o problema incorpora soluções ótimas para subproblemas relacionados II A solução ótima para o problema é na verdade subótima III A programação dinâmica não pode ser aplicada para resolver o problema pois só é aplicável em problemas que apresentam estrutura ótima Todas as afirmações estão corretas As afirmações II e III estão corretas Nenhuma das afirmações está correta As afirmações I e III estão corretas Somente a afirmação I está correta PERGUNTA 4 No problema do corte de barras um algoritmo que buscasse a solução que maximizasse o lucro no corte de uma barra de comprimento de n metros em que n é um inteiro e onde se tem a opção de cortar a barra em pedaços de tamanhos i 1 i n um inteiro sendo que para cada comprimento de corte o lucro distinto Se esse algoritmo utilizasse força bruta para determinar qual a opção de cortes que maximiza o lucro na venda esse algoritmo teria que analisar quantas possibilidades n² n lgn n 2ⁿ1 n1 5 PERGUNTA 5 O custo computacional em termos de número de multiplicações para a multiplicação da cadeia de matrizes A B C D parentizada na forma A x B x C x D em que as dimensões das matrizes número de linhas x número de colunas é como segue A é uma matriz 10 x 20 B uma matriz 20 x 1 C uma matriz 1 x 10 e D uma matriz 10 x 10 400 8000 40000 620 250 PERGUNTA 6 No problema de multiplicação de cadeias de matrizes podemos afirmar que I A ordem que as multiplicações são feitas pode alterar o custo computacional da multiplicação II A reordenação troca de posição das matrizes é a estratégia utilizada pelos algoritmos para otimização do cálculo III Determinar a parentização corresponde a determinar qual a ordem em que as matrizes serão multiplicadas Nenhuma das afirmações está correta Todas as afirmações estão corretas Somente a afirmação I está correta As afirmações II e III estão corretas As afirmações I e III estão corretas PERGUNTA 7 Em relação à memoização é correto afirmar I É uma técnica que consiste em a salvar o resultado dos subproblemas resolvidos de modo que possam ser consultados posteriormente evitando resolver subproblemas que já foram resolvidos II Na programação dinâmica pode ser feio uso da memoização III Na programação dinâmica algoritmos na forma bottomup fazem uso de memoização Todas as afirmações estão corretas Somente a afirmação I está correta As afirmações I e II estão corretas As afirmações II e III estão corretas Nenhuma das afirmações está correta 5 PERGUNTA 5 O custo computacional em termos de número de multiplicações para a multiplicação da cadeia de matrizes A B C D parentizada na forma A x B x C x D em que as dimensões das matrizes número de linhas x número de colunas é como segue A é uma matriz 10 x 20 B uma matriz 20 x 1 C uma matriz 1 x 10 e D uma matriz 10 x 10 400 8000 40000 620 250 PERGUNTA 6 No problema de multiplicação de cadeias de matrizes podemos afirmar que I A ordem que as multiplicações são feitas pode alterar o custo computacional da multiplicação II A reordenação troca de posição das matrizes é a estratégia utilizada pelos algoritmos para otimização do cálculo III Determinar a parentização corresponde a determinar qual a ordem em que as matrizes serão multiplicadas Nenhuma das afirmações está correta Todas as afirmações estão corretas Somente a afirmação I está correta As afirmações II e III estão corretas As afirmações I e III estão corretas PERGUNTA 7 Em relação à memoização é correto afirmar I É uma técnica que consiste em a salvar o resultado dos subproblemas resolvidos de modo que possam ser consultados posteriormente evitando resolver subproblemas que já foram resolvidos II Na programação dinâmica pode ser feio uso da memoização III Na programação dinâmica algoritmos na forma bottomup fazem uso de memoização Todas as afirmações estão corretas Somente a afirmação I está correta As afirmações I e II estão corretas As afirmações II e III estão corretas Nenhuma das afirmações está correta PERGUNTA 1 Na determinação do caminho mínimo entre dois vértices de um grafo o algoritmo de se aplica a problemas que podem ser representados por um grafo simples e com em que os pesos são Huffman conexo arestas positivo Strassen acíclico vértices distintos Prim não conexo vértices iguais Dijkstra conexo pesos positivo Huffman conexo arestas iguais PERGUNTA 2 Com relação ao procedimento utilizado pelo algoritmo de Huffman para a construção de uma árvore binária para o problema de compressão de dados de um arquivo podemos afirmar que I A construção da árvore é realiza no sentido da base para a raiz da árvore final de baixo para cima II Para um arquivo que contenha n símbolos caracteres distintos Inicialmente cada símbolo representará um nó rotulado com a sua frequência de ocorrência III Durante a execução do algoritmo de Huffman serão realizadas n1 intercalações para um arquivo contendo n símbolos distintos As afirmações II e III estão corretas Nenhuma das afirmações está correta Todas as afirmações estão corretas Somente a afirmação I está correta As afirmações I e III estão corretas PERGUNTA 3 Em relação ao algoritmo de Dijkstra podemos afirmar que I O algoritmo de Dijkstra se aplica a problemas que podem ser representados por um grafo simples conexo e com pesos em que os pesos são positivos II O algoritmo de Dijkstra utiliza a estratégia de divisão e conquista para resolver o problema de caminho mínimo em um grafo III O algoritmo de Dijkstra nos fornece a solução para encontrarmos o caminho com peso mínimo entre dois vértices de um grafo simples conexo e com peso em que os pesos são positivos Todas as afirmações estão corretas Nenhuma das afirmações está correta As afirmações I e III estão corretas As afirmações II e III estão corretas Somente a afirmação I está correta PERGUNTA 4 Na representação do através de uma cada representa um que foi codificado algoritmo de Strassen matriz binária valor vetor problema do caminho mínimo árvore binária aresta peso código de Huffman árvore binária folha símbolo problema de seleção de atividades fila elemento tempo algoritmo de Dijkstra recursão instância vetor PERGUNTA 5 Em relação a algoritmos gulosos podemos afirmar que I Algoritmos gulosos normalmente são utilizados em problemas de otimização embora nem sempre produzam soluções ótimas II Um algoritmo guloso a cada passo buscará uma escolha que parece ser a melhor ótima no momento em questão III A estratégia dos algoritmos gulosos de resolver sucessivamente problemas menores até atingirem uma solução global leva forçosamente ao projeto de algoritmos recursivos Somente a afirmação I está correta Todas as afirmações estão corretas As afirmações I e II estão corretas Nenhuma das afirmações está correta As afirmações II e III estão corretas PERGUNTA 6 Em relação ao problema conhecido como problema do caminho mínimo podemos afirmar que I Tanto o algoritmo de Dijkstra quanto o algoritmo de Huffman utilizam a estratégia gulosa para solução desse problema II O problema do caminho mínimo possui importantes aplicações na área de redes de computadores ou de comunicação em que as redes podem ser modeladas através de grafos e onde se deseja que a informação em um nó da rede seja enviada a outro nó do modo mais eficiente possível III A determinação do caminho mínimo pode ser aplicado a redes de transporte de cadeias logísticas em que os produtos de uma localidade têm que ser enviados a outra Todas as afirmações estão corretas As afirmações I e III estão corretas Nenhuma das afirmações está correta As afirmações II e III estão corretas Somente a afirmação I está correta PERGUNTA 7 Em relação às estratégias utilizadas para compactação compressão de dados de forma eficiente em um arquivo contendo símbolos caracteres podemos afirmar Uma estratégia é codificar símbolos pouco frequentes através de sequências mais longas de bits e utilizar sequência mais curtas de bits para símbolos mais frequentes com isso a quantidade total de espaço deverá ser reduzida I A codificação de símbolos em sequências de bits de tamanhos desiguais pode levar a problemas de ambiguidade na decodificação por isso é necessário a utilização de códigos de prefixo II A representação dos símbolos e a construção de códigos de compressão de dados podem ser descritos através de uma série de ações executadas em árvores binárias Nenhuma das afirmações está correta Somente a afirmação I está correta As afirmações II e III estão corretas Todas as afirmações estão corretas As afirmações I e III estão corretas PERGUNTA 1 A se aplica quando os se isto é quando os subproblemas subsubproblemas indução matemática casos base somam possuem programação dinâmica subproblemas sobrepõem compartilham recorrência algoritmos intercalam misturam técnica gulosa problemas misturam compõem divisão e conquista algoritmos dividem não possuem PERGUNTA 2 Na programação dinâmica a é utilizada para que o algoritmo resolva subproblemas recursão forçar repetidamente não resolvidos pilha evitar sempre recorrentes divisão forçar vários concomitantemente tabela garantir sempre recorrentes memoização evitar novamente já resolvidos PERGUNTA 3 Quando um problema apresenta subestrutura ótima podemos afirmar que I A solução ótima para o problema incorpora soluções ótimas para subproblemas relacionados II A solução ótima para o problema é na verdade subótima III A programação dinâmica não pode ser aplicada para resolver o problema pois só é aplicável em problemas que apresentam estrutura ótima Todas as afirmações estão corretas As afirmações II e III estão corretas Nenhuma das afirmações está correta As afirmações I e III estão corretas Somente a afirmação I está correta PERGUNTA 4 No problema do corte de barras um algoritmo que buscasse a solução que maximizasse o lucro no corte de uma barra de comprimento de n metros em que n é um inteiro e onde se tem a opção de cortar a barra em pedaços de tamanhos i 1 i n um inteiro sendo que para cada comprimento de corte o lucro distinto Se esse algoritmo utilizasse força bruta para determinar qual a opção de cortes que maximiza o lucro na venda esse algoritmo teria que analisar quantas possibilidades n² n lgn n 2n1 n1 PERGUNTA 5 O custo computacional em termos de número de multiplicações para a multiplicação da cadeia de matrizes A B C D parentizada na forma A x B x C x D em que as dimensões das matrizes número de linhas x número de colunas é como segue A é uma matriz 10 x 20 B uma matriz 20 x 1 C uma matriz 1 x 10 e D uma matriz 10 x 10 400 8000 40000 620 250 PERGUNTA 6 No problema de multiplicação de cadeias de matrizes podemos afirmar que I A ordem que as multiplicações são feitas pode alterar o custo computacional da multiplicação II A reordenação troca de posição das matrizes é a estratégia utilizada pelos algoritmos para otimização do cálculo III Determinar a parentização corresponde a determinar qual a ordem em que as matrizes serão multiplicadas Nenhuma das afirmações está correta Todas as afirmações estão corretas Somente a afirmação I está correta As afirmações II e III estão corretas As afirmações I e III estão corretas PERGUNTA 7 Em relação à memoização é correto afirmar I É uma técnica que consiste em a salvar o resultado dos subproblemas resolvedos de modo que possam ser consultados posteriormente evitando resolver subproblemas que já foram resolvidos II Na programação dinâmica pode ser feio uso da memoização III Na programação dinâmica algoritmos na forma bottomup fazem uso de memoização Todas as afirmações estão corretas Somente a afirmação I está correta As afirmações I e II estão corretas As afirmações II e III estão corretas Nenhuma das afirmações está correta