Questões de Teoria da Computação

Explore questões resolvidas de Teoria da Computação. Acesse respostas e explicações detalhadas para estudar e evoluir.

92% confiança
Leia o texto a seguir: Expressões regulares, também conhecidas como Regex, são strings de caracteres segurados em regras sintáticas que possibilitam a descrição de strings de caracteres. Fazem parte das linguagens regulares, que são um subgrupo de linguagens formais que têm grande importância na tecnologia da informação e, principalmente, no desenvolvimento de software. Especificação de expressões regulares é um exemplo de definição
computacao expressoes-regulares linguagens-formais
96% confiança
A complexidade também pode ser vista como uma propriedade do problema, o que significa dar uma medida independente do tratamento dado ao problema, independente do caminho percorrido na busca da solução e, portanto, independente de algoritmos. Alguns problemas são bem-comportados, isto é, permitem chegar a limites de complexidades bem definidos, outros estão em classes com contornos não bem claros. Marque a classe e a definição corretas:
classes-de-complexidade complexidade-computacional computacao
93% confiança
Para a correta modelagem de sistemas complexos, torna-se necessário adotar uma formalidade matemática para garantir o correto desenvolvimento do projeto. Dito isso, uma máquina determinística de estado finito ou aceitador determinístico de estado finito é dada por (ver Fórmula 1), sendo assim, pode-se dizer que:
automatos-finitos linguagens-formais teoria-da-computacao
92% confiança
Sobre a hierarquia de Chomsky podemos afirmar que:
computacao hierarquia-de-chomsky linguagens-formais
97% confiança
Os problemas de decisão consistem na verificação (decisão) da veracidade ou não de determinada questão para o problema (o qual exige uma resposta SIM ou NAO). Dentre as alternativas a seguir, qual está correta em se tratando de um exemplo de problema de decisão? Selecione a resposta:
computacao problemas-de-decisao teoria-da-computacao
95% confiança
Problemas decidíveis, porém difíceis, para os quais possivelmente não existe algoritmo que os resolvam em tempo polinomial, é denominado de:
complexidade-de-algoritmos computacao teoria-da-computacao
96% confiança
Os problemas que precisam ser resolvidos computacionalmente podem ser classificados de acordo com a sua computabilidade. Assinale a alternativa correta a respeito dessa classificação de problemas.
complexidade-computacional computacao teoria-da-computacao
78% confiança
Problemas incomputáveis não podem ser resolvidos por algoritmos com um número finito de passos. Marque V para verdadeiro e F para falso para as afirmações a respeito dessa categoria de problemas: ( ) Problemas que não podem ser resolvidos em uma máquina de Turing podem ser resolvidos via cálculo lambda. ( ) Se dois programas computam o mesmo resultado para qualquer entrada, então eles processam a mesma linguagem. ( ) Um problema que pode ser resolvido por um algoritmo computacional pode ser resolvido por uma máquina de Turing. ( ) A versão mais eficiente de um algoritmo pode ser obtida por meio de uma máquina de Turing com fita de tamanho infinito. Assinale a alternativa que apresenta a sequência correta:
computabilidade computacao maquinas-de-turing
88% confiança
A solução para dado problema pode ser obtida por meio da descrição de um algoritmo que o resolva. Para isso, no entanto, é fundamental que se analise a computabilidade do problema. Sobre o conceito de computabilidade, leia as assertivas a seguir. I. Se um problema em um cenário prático é dito computável, então qualquer algoritmo que o resolva pode ser empregado. II. Um algoritmo de complexidade O(cn) é dito intratável, já que o seu tempo de resposta é inviável para um problema prático. III. Algoritmos que resolvem problemas incomputáveis têm complexidade de tempo inviável para situações práticas. IV. Um algoritmo com complexidade O(n!) é menos eficiente do que qualquer algoritmo para problemas tratáveis. Quais estão corretas?
complexidade-de-algoritmos computabilidade computacao
96% confiança
Verificar se uma linguagem é regular é fundamental, pois, em caso positivo, será possível solucionar determinado problema de forma simples e com tempo de execução ótimo. Existem algumas maneiras de verificar se uma linguagem é regular. Um exemplo é por meio do uso de AFDs. Por outro lado, há a possibilidade de verificar se dada linguagem é não regular. Para isso, uma das formas mais utilizadas é o lema do bombeamento. Com base Σ = {a, b}, analise as linguagens a seguir e marque a opção referente a uma linguagem não regular.
lema-do-bombeamento linguagens-formais linguagens-regulares
78% confiança
As operações de fechamento, ou operações de fecho, sob linguagens regulares, podem ser definidas como aquelas que, quando aplicadas a elas, produzem uma nova linguagem também regular. Considere as informações a seguir: Dada uma linguagem regular L = {00, 01, 11, 011} sob Σ = {0, 1}. Analise as cadeias a seguir e informe quais fazem parte da linguagem L: 1- 00011100011 2- 00111010000 3- 11010001111 4- 01101000100 5- 11011110111 Selecione a resposta:
fecho-de-kleene linguagens-formais linguagens-regulares
95% confiança
Semelhante ao uso nas linguagens regulares, também é possível utilizar operadores diretamente nos símbolos, pois, dada uma Linguagem L = {a}, se pode representá-la simplesmente por a. Desse modo, ao inserir o operador estrela, sobre a, por exemplo, teremos como resultado {ε, a, aa, aaa,...}. Tendo em vista o exposto, dadas as linguagens a seguir, marque a opção que representa uma linguagem que produz uma cadeia que começa e termina com o mesmo símbolo, considerando que ∑={a,b}:
expressoes-regulares linguagens-formais teoria-da-computacao
96% confiança
Pode-se afirmar que a propriedade de fecho consiste em um conjunto de operações sobre as linguagens regulares que produzem uma nova linguagem também regular. Essas operações têm como intuito possibilitar a união, a interseção, a concatenação, entre outras operações sobre as linguagens regulares. Visto isso, considere as operações de união e concatenação. Assim, dadas as linguagens L1 = {a, aaa, b}, L2 = {bb, c} e L3 = {aa, cc, d} sobre o ∑ = {a, b, c, d}, informe qual é a linguagem obtida por L4 = ( L1 ∪ L2).L3 . Selecione a resposta:
linguagens-formais linguagens-regulares teoria-da-computacao
96% confiança
As linguagens de programação imperativa podem ser classificadas como completas quanto a Turing. Analise as questões e assinale a que representa uma síntese do que significa ser completa quanto a Turing.
computacao linguagens-de-programacao teoria-da-computacao
86% confiança
Autômatos finitos possuem diversas aplicações práticas, como na detecção de sequências de caracteres em um texto. A função programa do autômato abaixo apresenta um autômato que reconhece sequências sobre o alfabeto Σ = {a, b, c} e uma gramática livre de contexto que gera um subconjunto de Σ, em que λ representa a palavra vazia. Autômato: M = (S, Σ, δ, s0, F), onde S = {0, 1, 2, 3, 4, 5}, s0 = 0 (estado inicial), F = {5}, Σ = {a, b, c}. A função δ pode ser representada pela tabela abaixo (Tabela 1). A gramática é apresentada em Gramática 1. Analisando a gramática e o autômato acima, conduz-se que:
automatos-finitos-e-expressoes-regulares linguagens-formais teoria-da-computacao