Grátis: Num exercício de pesquisa, peça aos alunos que demonstrem como o Teorema da Recursão (Kleene) é usado para construir programas autorreferenciais e ... – Questões Respondidas

Algoritmos

Outros

Num exercício de pesquisa, peça aos alunos que demonstrem como o Teorema da Recursão (Kleene) é usado para construir programas autorreferenciais e por que isso prejudica a existência de verificadores universais. No enunciado, descreva o teorema: para qualquer função computável que transforma descrições de programas, existe um programa que, ao ser transformado, age como ponto fixo; isto é, programas podem obter sua própria descrição e agir sobre ela. Explique como essa autorreferência permite construir um programa que consulta um hipotético verificador e age para gerar contradição (por exemplo, invertendo o resultado), assim provando impossibilidade. Peça que os alunos conectem esse argumento com a prova do problema da parada.
Como o Teorema da Recursão contribui para as provas de impossibilidade de analisadores universais?
A) Transforma qualquer propriedade indecidível em decidível.
B) Afirma que toda propriedade semântica é decidível se a autoria for proibida.
C) Mostra que nenhum programa pode se autorreferir.
D) Demonstra que oráculos resolvem todas as limitações.
E) Permite construir programas que obtêm sua própria descrição, possibilitando contradições (autorreferência) quando combinados com verificadores hipotéticos, o que prova impossibilidade. Correta

Progresso com Exercícios

há 2 meses

Progresso com Exercícios

há 2 meses

Gabarito - Prova - ANÁLISE DE COMPUTABILIDADE E COMPLEXIDADE DE ALGORITMOS

Anhanguera

Respostas

Ed

há 2 meses

A resposta correta é a alternativa E. Explicação: O Teorema da Recursão de Kleene permite que programas obtenham sua própria descrição e atuem sobre ela, criando autorreferência. Essa autorreferência possibilita construir programas que, ao consultar um verificador universal hipotético, podem gerar contradições (por exemplo, invertendo o resultado do verificador). Isso é fundamental para provar a impossibilidade da existência de verificadores universais, como na prova do problema da parada. Portanto, a alternativa correta é: E) Permite construir programas que obtêm sua própria descrição, possibilitando contradições (autorreferência) quando combinados com verificadores hipotéticos, o que prova impossibilidade.

Essa resposta te ajudou?

0

0

Ainda não achou a resposta?

Integrado com os principais modelos de IA do mercado
Respostas em segundos
IA treinada para estudantes brasileiros.

Evolua sua forma de estudar

Cadastre-se ou realize login

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

Gabarito - Prova - ANÁLISE DE COMPUTABILIDADE E COMPLEXIDADE DE ALGORITMOS

Anhanguera

Mais perguntas desse material

Num problema de otimização combinatória com grandes dimensões, um pesquisador explora algoritmos de programação dinâmica que dependem de múltiplos parâmetros (por exemplo, DP com estados (i, j, k)). Ele precisa estimar rapidamente quando a DP será impraticável e quando técnicas como compressão de estados, transformações FFT para convoluções, ou algoritmo de divide and conquer optimization podem reduzir custo. Peça que o aluno explique sob quais condições cada técnica aplica (p. ex. convolução quando DP envolve soma/combinação de tipos convolucionais; divide and conquer optimization quando quadrangle inequality ou monotonicity hold) e dê um exemplo.
Quando é apropriado usar otimização por divide and conquer (D&C optimization) para acelerar um DP quadrático?
A) Quando o problema é NP-completo e sem heurísticas.
B) Quando o DP tem estados independentes e triviais.
C) Quando se quer aumentar o espaço em detrimento do tempo exponencial.
D) Quando a tabela DP já é linear.
E) Quando a função de transição satisfaz monotonicidade do ponto de corte (quadrangle inequality/Monge/monotone optima), permitindo reduzir custo de Θ(n²) para Θ(n log n) ou Θ(n) por nível via D&C. Correta

Um time de produto precisa escolher entre duas versões de um módulo que processa listas: uma versão faz uma passagem simples (procura linear) para verificar uma propriedade e outra faz ordenação seguida de buscas binárias. Para fundamentar a decisão, o engenheiro pede um texto curto que compare comportamento de pior caso e caso médio, explique o significado de notação Big O e dê recomendação quando priorizar algoritmos com menor crescimento assintótico em n. Inclua também como o caso médio pode depender de pressupostos sobre distribuição de dados.
Qual alternativa resume corretamente o que a notação Big O representa na análise de algoritmos?
A) Big O expressa um limite superior assintótico do custo (tempo ou espaço) em função do tamanho da entrada, abstraindo constantes e termos de ordem inferior. Correta
B) Big O mostra que um algoritmo é indecidível.
C) Big O descreve o desempenho apenas no melhor caso.
D) Big O indica o tempo exato em segundos que um algoritmo levará numa máquina específica.
E) Big O é aplicável apenas a algoritmos recursivos.

Num trabalho escrito, peça aos alunos que justifiquem a indecidibilidade de certas propriedades semânticas de programas usando o Teorema de Rice. No enunciado, explique com clareza: propriedades semânticas dependem do comportamento computacional (o que o programa faz), não da forma sintática; Teorema de Rice afirma que qualquer propriedade não trivial (nem verdadeira para todas as máquinas nem falsa para todas) que dependa somente do comportamento é indecidível. Dê exemplos: "o programa aceita alguma cadeia que contém ‘abc’?" (semântica não trivial → indecidível) e contraste com propriedades sintáticas (por exemplo, tamanho do código) que podem ser decidíveis. Solicite argumento formal sucinto.
Qual enunciado sintetiza corretamente o Teorema de Rice?
A) Toda propriedade sintática de um programa é indecidível.
B) Rice prova que HALT é decidível.
C) Toda propriedade não trivial que dependa apenas do comportamento (semântica) dos programas é indecidível. Correta
D) Propriedades semânticas triviais são sempre indecidíveis.
E) Apenas propriedades sobre o tamanho do código são indecidíveis.

Um time de engenharia precisa entender limites teóricos: foi levantada a questão "por que todo algoritmo de ordenação por comparação tem limite inferior Ω(n log n)?" Você deve redigir um esboço didático que explique a prova baseada em árvores de decisão (permutations, comparações como nós internos e folhas como permutações) e por que isso implica um limite de comparações necessárias no pior caso. Inclua também observações sobre como algoritmos não comparativos (Counting, Radix) contornam esse limite usando propriedades dos dados e restrições sobre o universo de chaves.
Qual a razão central para o limite inferior Ω(n log n) para ordenações baseadas em comparação?
A) Porque uma árvore de decisão que representa todas as permutações possíveis tem pelo menos n! folhas, e comparar pares só gera bifurcações; o log2(n!) = Θ(n log n) fornece o menor número de comparações necessário no pior caso. Correta
B) Porque Merge Sort usa espaço extra.
C) Porque n log n é escolhido arbitrariamente por convenção.
D) Porque a complexidade depende apenas do modelo RAM.
E) Porque QuickSort é indecidível.

Ao avaliar a aplicabilidade dos algoritmos implementados no simulador, a equipe levanta uma discussão: "existência de algoritmo significa solução prática?" A aula explica distinção entre decidibilidade (existência) e viabilidade (complexidade), pedindo aos alunos que avaliem cenários em que um algoritmo existe, mas é impraticável por custo exponencial.
Um colega afirma: "Se existe um algoritmo para um problema, então ele é necessariamente viável em aplicações reais."
A) Correta quando o problema é NP.
B) Correta — existência do algoritmo garante viabilidade prática.
C) Correta somente se o algoritmo roda em máquina de Turing.
D) Incorreta — decidibilidade e viabilidade são sinônimos.
E) Incorreta — algoritmo existente assegura apenas decidibilidade; viabilidade depende de complexidade (tempo/ memória). Correta

Como coordenador de qualidade, você deve redigir um memorando para a gerência explicando o que fazer quando um problema necessário para a operação (por exemplo, garantir que disparadores em um sistema bancário nunca causem loops infinitos) é indecidível em geral. No enunciado, descreva que, apesar da indecidibilidade teórica, há um leque de técnicas práticas: restrição do domínio (limitar linguagem ou padrões aceitos), uso de fragmentos decidíveis (por exemplo, restrições sintáticas), análise estática com abstrações, execução simbólica com bound checks, heurísticas e testes extensivos, além de políticas operacionais (timeouts, monitoramento). Peça que a gerência entenda que essas medidas aumentam confiança mas não garantem perfeição.
Diante de um problema indecidível na prática, qual recomendação técnica é a mais adequada?
A) Aplicar técnicas aproximadas: restrição de domínio, verificações em fragmentos decidíveis, análise simbólica e heurísticas, aceitando ausência de garantia absoluta. Correta
B) Traduzir o problema para uma máquina de Turing multifita para eliminar a indecidibilidade.
C) Usar exclusivamente testes dinâmicos, pois garantem correção total.
D) Aumentar memória dramáticamente resolve a indecidibilidade.
E) Abandonar qualquer tentativa de verificação; nada pode ser feito.

Num capítulo introdutório sobre decidibilidade e complexidade, você foi incumbido de escrever um texto que explique a diferença entre "decidível" e "viável" para alunos iniciantes. Use exemplos concretos: ordenar uma lista de 10 números (praticamente trivial) versus resolver instâncias grandes de problemas NP completos (por exemplo, Caixeiro Viajante) que, embora decidíveis, podem ser inviáveis. Explique o papel das classes de complexidade — especialmente P — e por que P é considerada a classe de problemas "viáveis" na prática. Discuta também a distinção entre problema ser decidível e ser solucionável em tempo polinomial; inclua comentários sobre verificabilidade (NP) e a importância desses conceitos para engenharia de software e criptografia.
Qual das opções corresponde à classe usualmente associada a problemas considerados viáveis (solucionáveis em tempo polinomial)?
A) Indecidíveis
B) NP-completo
C) P Correta
D) RE (recursively enumerable)
E) Graus de Turing

O exercício final do projeto solicita que os alunos formalizem procedimentos para demonstrar a equivalência funcional entre os dois simuladores (Norma e Turing) que implementam o fatorial. A equipe requer critérios mínimos: definição do domínio válido, modo de codificação das entradas/saídas, tradução automática entre representações, protocolo de comparação de resultados e política para tratar execuções muito longas ou não terminantes durante a demonstração.
Para demonstrar formalmente a equivalência funcional entre os dois simuladores que computam o fatorial, qual combinação de elementos é fundamental?
A) Garantir que, para cada entrada válida (mesma representação ou representações mutuamente traduzíveis), ambos terminem com a mesma saída (interpretação unívoca), independentemente do número de passos; além disso, prover tradução de codificações entre os modelos. Correta
B) Garantir que ambos sejam não determinísticos.
C) Garantir que ambos usem a mesma codificação de entrada, produzam bitwise o mesmo conteúdo de memória e executem o mesmo número de passos.
D) Garantir que ambos sejam implementados em mesma linguagem de programação.
E) Garantir que ambos usem apenas INC/DEC/JZ.

há um segmento que explica a Hipótese (Tese) de Church-Turing para estudantes: por que diferentes formalismos (λ-cálculo, máquinas de Turing, máquinas de registradores) têm o mesmo poder expressivo em termos do que é computável. Esse trecho é usado para justificar por que o simulador pode comparar modelos distintos sem perda conceitual.
A Tese de Church-Turing, conforme o conteúdo da Unidade 1, afirma, em termos gerais:
A) Que computadores quânticos podem resolver problemas indecidíveis.
B) Que qualquer função efetivamente computável pode ser calculada por uma máquina de Turing. Correta
C) Que autômatos finitos conseguem resolver qualquer problema computacional.
D) Que o cálculo λ é mais expressivo que a máquina de Turing.
E) Que todos os problemas são solucionáveis em tempo polinomial.