Exatas

Brasil

Ciência da Computação

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

Ativ 4 Linguagens Formais e Autômatos 1 de 1

RESTRICTED

Graduate

Faculdade das Américas

Renan Silva

Outros

Antropologia

Antropologia I é uma disciplina que introduz os alunos aos conceitos fundamentais da antropologia, como cultura, sociedade, diversidade cultural, etnocentrismo, relativismo cultural, entre outros. Durante as aulas, os alunos aprendem sobre as diferentes abordagens teóricas da antropologia, bem como as metodologias de pesquisa utilizadas pelos antropólogos. A disciplina é importante para estudantes de diversas áreas, como ciências sociais, humanas e biológicas, que desejam compreender a complexidade das sociedades humanas e as diferentes formas de organização social e cultural.

Other

Leia o trecho abaixo: [...] Após o final da guerra, Turing seguiu trabalhando com criptografia e computação. Entre 1945 e 1947 trabalhou no projeto...

Leia o trecho abaixo: [...] Após o final da guerra, Turing seguiu trabalhando com criptografia e computação. Entre 1945 e 1947 trabalhou no projeto do ACE (Automatic Computing Engine) e escreveu um artigo com o primeiro projeto detalhado de computador capaz de guardar instruções computacionais na memória [...]. 'Computadores e inteligência' (Computer Machinery and Intelligence, no original em inglês) foi publicado na revista de filosofia Mind em outubro de 1950 e é precursor da inteligência artificial (o termo só seria criado em 1956). É um artigo no qual Turing, motivado pela experiência com os primeiros computadores digitais e adotando um tom bastante especulativo, se coloca a pergunta: 'as máquinas podem pensar?' A questão que despertava interesse filosófico para Turing há 70 anos desperta hoje interesse generalizado na medida em que temos computadores potentes, onipresentes e interconectados, coleta massiva de dados e muita pesquisa na área de aprendizagem de máquina. No artigo, Turing re-apresenta de forma sucinta seu modelo teórico de computador e propõe um (o jogo da que hoje chamamos de Teste de Turing quando jogado por uma máquina. A conjectura que os computadores do futuro serão capazes de passar no teste, isso é, serão de seres humanos, e discute com algumas das objeções da época a essa ideia. Na última seção, ainda sugere uma ideia do que hoje chamamos de 'aprendizagem por reforço'. A leitura artigo é um interessante passeio por algumas de suas ideias e principalmente pelo seu jeito de pensar e argumentar [...].
Com base nas informações sobre máquinas de Turing e em sua relação com a inteligência artificial, avalie as seguintes asserções e a relação proposta entre elas.
I. Uma máquina de Turing é um modelo complexo que pode ler símbolos no papel, tem memória interna e pode escrever símbolos. É um modelo bastante elaborado de como fazemos cálculos.
II. Uma semelhança prática importante dos computadores modernos de hoje com as máquinas de Turing é a velocidade. A velocidade com que elas podem ler, escrever e mudar de estado é crucial.
As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I.
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.

General Studies

Questões Para o Saber: Compartilhando questões para auxiliar no aprendizado e aprimoramento de habilidades em diversas áreas do conhecimento. Vamos juntos aprender mais sobre os assuntos que nos interessam através dessas questões desafiadoras!

Questões Para o Saber

Leia o trecho abaixo: [...] A máquina de Turing seria equipada com uma fita perfurada de comprimento infinito, preenchida em intervalos regulares c...

Leia o trecho abaixo: [...] A máquina de Turing seria equipada com uma fita perfurada de comprimento infinito, preenchida em intervalos regulares com símbolos de um conjunto finito e um ponteiro que marcaria a posição real em que a máquina se encontrava, dentro de um conjunto limitado de 'estados internos' possíveis. Entretanto, em cada operação a máquina leria o símbolo inscrito na posição correspondente na fita e para cada combinação de posição e símbolo lido um programa especificaria um novo símbolo inscrever na mesma fita ou um movimento a ser efetuado pelo ponteiro, que poderia deslocar-se para a esquerda, para a direita, ou parar. Com esta máquina abstrata, Turing pretendia conseguir definições matematicamente precisas algoritmos, ou procedimentos mecânicos. Ainda muito utilizada na abordagem a teorias como a da computação ou da complexidade, a máquina de Turing compreenderia então, e mais precisamente, quatro elementos: Uma fita dividida em células contíguas, cada qual contendo um símbolo de um alfabeto finito, que por sua vez contém, entre outros, um símbolo nulo especial. Esta fita seria infinitamente extensível para a esquerda e para a direita, e que as células que não tivessem sido preenchidas com um símbolo contivessem o carácter especial nulo. Um dispositivo de leitura e gravação que se movimentasse para a esquerda e para a direita nessa fita, e conseguisse interpretar e escrever os símbolos. Um outro dispositivo que registasse cada estado da máquina de Turing, sendo que o número de estados diferentes seria sempre finito e compreenderia um estado inicial de arranque, que iniciaria o dispositivo de registro. Uma tabela de ações que comandaria os movimentos da máquina, dizendo-lhe que símbolo escrever, para onde o dispositivo de leitura e gravação, e decidiria qual o seu novo estado, em função do símbolo acabado de ler e do estado em que a máquina se encontrasse no momento. Se porventura não existisse qualquer entrada na tabela de ações para uma dada combinação de símbolo e estado, então a máquina consideraria o programa concluído e pararia.
Considerando o texto sobre o funcionamento da máquina de Turing, avalie as afirmações abaixo:
I. Uma máquina de Turing consiste em uma fita infinitamente longa, que foi dividida em células.
II. A direção em que o ponteiro se move depende de um conjunto de instruções fornecidas à máquina.
III. O ponteiro é incapaz de apagar símbolos e escrever novos símbolos nas células.
IV. O ponteiro pode se mover para a esquerda ou para a direita e pode ler os símbolos escritos nas células.
É correto o que se afirma em III e IV, apenas.
É correto o que se afirma em II e IV, apenas.
É correto o que se afirma em I, apenas.
É correto o que se afirma em I e III, apenas.
É correto o que se afirma em II e IV, apenas.

Leia o trecho abaixo: Definição O que significa Máquina de Turing Não Determinística (NTM)? Uma máquina de Turing não determinística é um tipo teór...

Leia o trecho abaixo: Definição O que significa Máquina de Turing Não Determinística (NTM)? Uma máquina de Turing não determinística é um tipo teórico de computador no qual comandos específicos podem permitir uma gama de ações, em vez de um comando específico que leva a apenas uma ação permitida no modelo determinístico de computação. Onde a programação determinística é uma condição simples de X leva à ação uma configuração de máquina de Turing não determinística teoricamente permitiria que a entrada X levasse a uma variedade de ações Y (matriz) [...]. As máquinas de Turing não determinísticas podem realmente fornecer uma direção para o futuro da computação inteligente ou artificialmente inteligente. Ao desvincular o trabalho computacional do paradigma determinístico, os computadores poderiam aprender a resolver problemas mais complicados e mais como humanos. Um tipo de máquina de Turing não determinística é a máquina de Turing probabilística. Aqui, a matriz de ações (Y) mencionada acima é determinada por meio de alguma distribuição de probabilidade. Outra maneira de dizer isso é que quando a máquina tem mais de uma escolha, ela vai para um modelo probabilístico, analisa esse modelo e faz uma escolha de acordo. Existem muitas outras maneiras de solicitar uma máquina de Turing não determinística, mas o princípio é que o computador deve escolher a partir de um conjunto de opções disponíveis. Alguns modelos de Turing não determinísticos em uma configuração de aprendizado de máquina podem consistir em o computador seguir caminhos lógicos até um fim aceito ou rejeitado e, em seguida, voltar e escolher uma ação de acordo. Como os especialistas apontam, as máquinas de Turing não determinísticas são diferentes dos modelos de computação quântica. Na computação quântica, a confluência de bits binários em qubits amplia o paradigma e torna os processos de computação mais elaborados e sofisticados. Na máquina de Turing não determinística, conforme explicado, é a disponibilidade de escolhas de acordo com as entradas que afasta o modelo de computação do determinismo puro.
Considerando as informações apresentadas sobre as máquinas de Turing determinísticas e não determinísticas, avalie as afirmações abaixo:
I. Do ponto de vista da computabilidade, uma máquina de Turing probabilística é equivalente a uma máquina de Turing não determinística.
II. Uma máquina de Turing não determinística é uma máquina de Turing modificada para executar uma computação aleatória.
III. A diferença entre uma máquina de Turing determinística e uma máquina de Turing não determinística é a mesma entre um AFD e um AFN.
IV. Uma máquina de Turing não determinística é uma variante da máquina de Turing simples.
É correto o que se afirma em I e III, apenas.
É correto o que se afirma em II, III e IV, apenas.
É correto o que se afirma em I e III, apenas.
É correto o que se afirma em III e IV, apenas.
É correto o que se afirma em IV, apenas.

Observe a imagem e leia o texto abaixo: Turing Machine Considerado o 'pai da computação', o britânico Alan Turing formulou, na década de 1930, um m...

Observe a imagem e leia o texto abaixo: Turing Machine Considerado o 'pai da computação', o britânico Alan Turing formulou, na década de 1930, um modelo teórico que seria responsável pela criação de conceitos como o algoritmo e o desenvolvimento dos computadores modernos. Conhecido como Máquina de Turing, o dispositivo escrevia e interpretava símbolos limitados em 0, 1 e conjunto vazio - basicamente, a estruturação das linhas de códigos atuais. Inspirado pelo filme Jogo da Imitação, o entusiasta por tecnologia Richard J. Ride passou seis meses desenvolvendo uma Máquina de Turing em madeira, em um processo que envolveu tentativa e erro até o funcionamento do dispositivo [...]. Turing também teve um papel decisivo na Segunda Guerra Mundial. Em uma mansão vitoriana na cidade de Bletchley, um grupo de gênios contratados pelo serviço de inteligência britânico foi reunido durante para desvendar o código militar alemão gerado pela Enigma, máquina de criptografia supostamente impenetrável. Com a equipe, o matemático começou a trabalhar na produção de uma máquina chamada 'a bomba'. O instrumento identificava pontos fracos da codificação e foi responsável por revelar a posição dos submarinos alemães. Com as diversas informações interceptadas, o grupo também pode ter colaborado para encurtar a duração da guerra [...].
Com base no texto, assinale a alternativa que apresenta informações corretas sobre as invenções de Turing:
Turing formulou um modelo prático usado na criação de conceitos, como algoritmo e desenvolvimento de computadores modernos.
Sua invenção, conhecida como Máquina de Turing, escrevia e interpretava símbolos limitados em 0, 1 e conjunto vazio.
Richard J. Ride passou seis meses desenvolvendo uma máquina chamada a bomba.
Um grupo de gênios, incluindo Ride, foi reunido para desvendar o código militar alemão gerado pela Enigma.
A máquina 'Jogo da Imitação' identificava pontos fracos da codificação e era responsável por identificar a posição de submarinos.

Leia o trecho abaixo: [...] Após o final da guerra, Turing seguiu trabalhando com criptografia e computação. Entre 1945 e 1947 trabalhou no projeto do ACE (Automatic Computing Engine) e escreveu um artigo com o primeiro projeto detalhado de computador capaz de guardar instruções computacionais na memória [...]. 'Computadores e inteligência' (Computer Machinery and Intelligence, no original em inglês) foi publicado na revista de filosofia Mind em outubro de 1950 e é precursor da inteligência artificial (o termo só seria criado em 1956). É um artigo no qual Turing, motivado pela experiência com os primeiros computadores digitais e adotando um tom bastante especulativo, se coloca a pergunta: 'as máquinas podem pensar?' A questão que despertava interesse filosófico para Turing há 70 anos desperta hoje interesse generalizado na medida em que temos computadores potentes, onipresentes e interconectados, coleta massiva de dados e muita pesquisa na área de aprendizagem de máquina. No artigo, Turing re-apresenta de forma sucinta seu modelo teórico de computador e propõe um (o jogo da que hoje chamamos de Teste de Turing quando jogado por uma máquina. A conjectura que os computadores do futuro serão capazes de passar no teste, isso é, serão de seres humanos, e discute com algumas das objeções da época a essa ideia. Na última seção, ainda sugere uma ideia do que hoje chamamos de 'aprendizagem por reforço'. A leitura do artigo é um interessante passeio por algumas de suas ideias e principalmente pelo seu jeito de pensar e argumentar [...].
Com base nas informações sobre máquinas de Turing e em sua relação com a inteligência artificial, avalie as seguintes asserções e a relação proposta entre elas.
I. Uma máquina de Turing é um modelo complexo que pode ler símbolos no papel, tem memória interna e pode escrever símbolos. É um modelo bastante elaborado de como fazemos cálculos.
II. Uma semelhança prática importante dos computadores modernos de hoje com as máquinas de Turing é a velocidade. A velocidade com que elas podem ler, escrever e mudar de estado é crucial.
As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I.
As asserções I e II são proposições falsas.
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.

Leia o trecho abaixo: [...] A máquina de Turing seria equipada com uma fita perfurada de comprimento infinito, preenchida em intervalos regulares com símbolos de um conjunto finito e um ponteiro que marcaria a posição real em que a máquina se encontrava, dentro de um conjunto limitado de 'estados internos' possíveis. Entretanto, em cada operação a máquina leria o símbolo inscrito na posição correspondente na fita e para cada combinação de posição e símbolo lido um programa especificaria um novo símbolo a inscrever na mesma fita ou um movimento a ser efetuado pelo ponteiro, que poderia deslocar-se para a esquerda, para a direita, ou parar. Com esta máquina abstrata, Turing pretendia conseguir definições matematicamente precisas de algoritmos, ou procedimentos mecânicos. Ainda muito utilizada na abordagem a teorias como a da computação ou da complexidade, a máquina de Turing compreenderia então, e mais precisamente, quatro elementos: Uma fita dividida em células contíguas, cada qual contendo um símbolo de um alfabeto finito, que por sua vez contém, entre outros, um símbolo nulo especial. Esta fita seria infinitamente extensível para a esquerda e para a direita, e que as células que não tivessem sido preenchidas com um símbolo contivessem o carácter especial nulo. Um dispositivo de leitura e gravação que se movimentasse para a esquerda e para a direita nessa fita, e conseguisse interpretar e escrever os símbolos. Um outro dispositivo que registasse cada estado da máquina de Turing, sendo que o número de estados diferentes seria sempre finito e compreenderia um estado inicial de arranque, que iniciaria o dispositivo de registro. Uma tabela de ações que comandaria os movimentos da máquina, dizendo-lhe que símbolo escrever, para onde o dispositivo de leitura e gravação, e decidiria qual o seu novo estado, em função do símbolo acabado de ler e do estado em que a máquina se encontrasse no momento. Se porventura não existisse qualquer entrada na tabela de ações para uma dada combinação de símbolo e estado, então a máquina consideraria o programa concluído e pararia.
Considerando o texto sobre o funcionamento da máquina de Turing, avalie as afirmações abaixo:
I. Uma máquina de Turing consiste em uma fita infinitamente longa, que foi dividida em células.
II. A direção em que o ponteiro se move depende de um conjunto de instruções fornecidas à máquina.
III. O ponteiro é incapaz de apagar símbolos e escrever novos símbolos nas células.
IV. O ponteiro pode se mover para a esquerda ou para a direita e pode ler os símbolos escritos nas células.
É correto o que se afirma em III e IV, apenas.
É correto o que se afirma em II e IV, apenas.
É correto o que se afirma em I, apenas.
É correto o que se afirma em I e III, apenas.
É correto o que se afirma em II e IV, apenas.

MaterialAggregator/Subjects/Materials/Recent

MaterialAggregator/Subjects/Questions/New

Ativ 4 Linguagens Formais e Autômatos 1 de 1

Conteudo restrito apenas para assinantes