Exatas

Brasil

Design Gráfico

pt-br

Teoria da Computação

A Teoria da Computação é uma disciplina que estuda os fundamentos matemáticos da computação. Durante as aulas, os alunos aprendem sobre modelos abstratos de computação, como autômatos e máquinas de Turing, além de conceitos como complexidade computacional e linguagens formais. A disciplina é importante para a compreensão dos limites e possibilidades da computação, e é fundamental para a formação de profissionais da área de tecnologia da informação, como programadores, desenvolvedores e cientistas da computação.

Exam

Text

ANALISE DE ALGORITMOS - ATIVIDADE 3 - Unidade de Estudo 4

RESTRICTED

Ciência da Computação

Graduate

Universidade Anhembi Morumbi

Cristiana Rodrigues

Outros

Other

1. Os conceitos que fundamentam a construção de estratégias gulosas são importantes para que uma modelagem precisa possa ser empregada durante a pr...

1. Os conceitos que fundamentam a construção de estratégias gulosas são importantes para que uma modelagem precisa possa ser empregada durante a proposição de soluções. Essa análise deve preceder, inclusive, a etapa de projeto de um algoritmo guloso. Nesse contexto, dado um conjunto { x1, x2, …, xn } de pontos na reta dos números reais, analise as asserções a seguir e a relação proposta entre elas. I. É possível projetar uma estratégia gulosa para encontrar o menor conjunto de intervalos fechados de comprimento 1 (um) contendo todos os pontos. Porque: II. A cada etapa da estratégia gulosa uma escolha local ótima pode ser feita de modo a garantir a obtenção de uma solução final ótima. Qual é a alternativa correta? a) A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. b) As asserções I e II são proposições falsas. c) Resposta correta d) As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. e) As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.

General Studies

Exercícios Para o Aprendizado: Compartilhando exercícios para auxiliar no aprendizado e aprimoramento de habilidades em diversas áreas do conhecimento. Vamos juntos praticar e aprimorar nossos conhecimentos através desses exercícios desafiadores!

Exercícios Para o Aprendizado

2. Os problemas que precisam ser resolvidos computacionalmente podem ser classificados de acordo com a sua computabilidade. Essa classificação é im...

2. Os problemas que precisam ser resolvidos computacionalmente podem ser classificados de acordo com a sua computabilidade. Essa classificação é importante, considerando que ela tem efeito direto sobre a viabilidade de construção de um algoritmo útil em cenários práticos. Considerando essas informações e os conteúdos estudados, assinale a alternativa correta a respeito dessa classificação de problemas. a) Todo problema que é NP-completo, mas não é NP-difícil, pode ter um algoritmo polinomial que o resolva. b) Resposta correta c) A descoberta de um algoritmo polinomial para um problema NP-completo pode tornar a igualdade P = NP verdadeira. d) Qualquer problema NP-difícil é possível de ter um certificado verificado em tempo polinomial. e) Encontrar a rota ótima para um trajeto de entrega de mercadorias em pontos específicos é um problema da classe P.

3. A recursão é uma poderosa técnica para modelagem e projeto de algoritmos. O uso dessa estratégia, porém, depende da correta identificação dos se...

3. A recursão é uma poderosa técnica para modelagem e projeto de algoritmos. O uso dessa estratégia, porém, depende da correta identificação dos seus dois principais elementos: um caso base que finaliza as chamadas recursivas e o passo de recursão. Suponha a situação em que a operação de adição em uma linguagem de programação é feita por um componente externo. Esse componente recebe como parâmetro dois números a serem somados e, internamente, ele faz uso dos operadores ++ para incrementar o valor de um número em 1 e -- para decrementar em 1. Considerando o Algoritmo Somador apresentado, assinale a alternativa correta a respeito de seu funcionamento. a) A etapa de combinação das soluções parciais, computadas em cada chamada recursiva, é feita em cada invocação do algoritmo. b) Resposta correta c) O passo recursivo da função de recorrência associada é T(i, j) = T(i -1, j + 1) para i > 0. d) Para a soma dos números i = 3 e j = 7, o algoritmo realiza 2 chamadas recursivas. e) A parada do algoritmo é garantida pelo incremento realizado no parâmetro j.

4. As classes de computabilidade possibilitam que os problemas sejam organizados de acordo com as suas características de tratabilidade computacion...

4. As classes de computabilidade possibilitam que os problemas sejam organizados de acordo com as suas características de tratabilidade computacional. Conhecer as relações entre essas classes e os problemas categorizados nelas é de grande importância para projetar algoritmos que possam ser aplicados em cenários reais. Considere um problema Y que pode ser resolvido usando um número polinomial de passos computacionais, acrescido de um número polinomial de chamadas a um outro problema X. Essa relação pode ser denotada por Y ≤p X. Isso quer dizer que X é pelo menos tão difícil quanto Y com relação ao tempo polinomial. Sabendo que, se X pode ser resolvido em tempo polinomial, isso vai implicar que Y também pode ser resolvido em tempo polinomial, analise as asserções a seguir e a relação proposta entre elas. I. Se X é um problema NP-completo, então X pode ser resolvido em tempo polinomial se, e somente se, P = NP. Porque: II. Nesse caso, qualquer outro problema Y pertencente a NP poderá ser resolvido em tempo polinomial. A seguir, assinale a alternativa correta. a) A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. b) As asserções I e II são proposições falsas. c) Resposta correta d) As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. e) As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.

6. A ordenação de dados em memória é uma das operações mais comuns executadas por algoritmos computacionais. Embora existam diferentes estratégias ...

6. A ordenação de dados em memória é uma das operações mais comuns executadas por algoritmos computacionais. Embora existam diferentes estratégias para esse tipo de operação, poucas delas conseguem alcançar um tempo computacional linear. Algoritmo Ordenação Linear Simplificada Entrada: Um vetor A de n inteiros cujos valores são 1 ou 2. Saída: Vetor A com os valores ordenados de forma não-decrescente Defina k ← 0 para i ← 1 até n faça se A[ i ] = 1, então k ← k + 1 para i ← 1 até k faça A[ i ] ← 1 para i ← k + 1 até n faça A[ i ] ← 2 retorna A Nesse contexto, considerando o algoritmo apresentado, analise as afirmativas a seguir e assinale V para a(s) verdadeira(s) e F para a(s) falsa(s). I. ( ) Para um vetor A contendo m posições com valor 1 e n posições com valor 2, o algoritmo realiza m + n operações de atribuições ao vetor A. II. ( ) O algoritmo é estável. III. ( ) Para qualquer sequência de valores aceitos pelo algoritmo, as primeiras posições do vetor A serão ocupadas pelo valor 2. IV. ( ) O maior valor possível para k é n. Agora, assinale a alternativa que apresenta a sequência correta: a) Resposta correta b) c) d) e)

Assinale V para a(s) verdadeira(s) e F para a(s) falsa(s).
I. ( ) Se as tarefas forem ordenadas pela quantidade de unidades de tempo para serem fin...

Assinale V para a(s) verdadeira(s) e F para a(s) falsa(s). I. ( ) Se as tarefas forem ordenadas pela quantidade de unidades de tempo para serem finalizadas (pi), então a complexidade do algoritmo será O(n log n). II. ( ) Um algoritmo guloso que processa as tarefas em ordem crescente de pi obtém a solução ótima para qualquer conjunto de tarefas. III. ( ) Considerando S composto apenas de duas tarefas a1 e a2 com p1 = 3 e p2 = 5, o tempo médio de finalização de S é independente da ordem de execução das tarefas. IV. ( ) Uma solução gulosa, baseada no tempo de processamento de cada tarefa, apresenta uma estrutura local ótima em cada iteração. Agora, assinale a alternativa que apresenta a sequência correta. V, V, F, V. V, V, F, V. V, V, F, F. V, F, V, F. F, V, F, V. F, F, V, V.

A função h é computável. Porque: Ela é capaz de retornar uma saída para qualquer instância de problema, em um número finito de passos. A seguir, as...

A função h é computável. Porque: Ela é capaz de retornar uma saída para qualquer instância de problema, em um número finito de passos. A seguir, assinale a alternativa correta. A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. As asserções I e II são proposições falsas. As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I. A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.

O algoritmo counting sort constitui uma alternativa eficiente para a ordenação de dados em memória, já que ele demanda um tempo computacional da or...

O algoritmo counting sort constitui uma alternativa eficiente para a ordenação de dados em memória, já que ele demanda um tempo computacional da ordem de Θ(n). No entanto, ele faz maior uso do espaço em memória, por precisar que vetores auxiliares sejam criados durante sua execução. Considerando a execução do algoritmo sobre um vetor A = {4, 1, 5, 0, 1, 6, 5, 1, 5, 3}, em que todos os valores são menores que k = 7, analise as afirmativas a seguir. I. Após o primeiro laço que inicializa cada posição do vetor auxiliar C com zero, o segundo laço finaliza com o vetor C = { 1, 3, 0, 1, 1, 3, 1 }. II. Ao término do terceiro laço, o vetor auxiliar C definido no corpo do algoritmo terá os seguintes valores armazenados {0, 3, 3, 4, 5, 8, 9}. III. A primeira iteração do último laço do algoritmo faz com que o valor 3 seja atribuído à posição 4 do vetor A. IV. A posição 4 corresponde à última posição do vetor A a ser preenchida pelo laço final do algoritmo. Está correto apenas o que se afirma em: II e III. III e IV. I e IV. I e II. I, II e III.

MaterialAggregator/Subjects/Materials/Recent

MaterialAggregator/Subjects/Questions/New

ANALISE DE ALGORITMOS - ATIVIDADE 3 - Unidade de Estudo 4

Conteudo restrito apenas para assinantes