P1 - Teoria da Computação e Compiladores - FHO Uniararas

Prévia do material em texto

UNIARARAS - Fundação Hermínio Ometto 
Av. Dr. Maximiliano Baruto, 500 - Jd. Universitário | Araras - SP - CEP: 13607-339 - Tel: (19) 3543-
1400 
 
 
PROVA 1º BIMESTRE - 2º SEMESTRE/2017 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1) De acordo com a Teoria da Computação, o que são algoritmos? (0,5 Pontos) 
 
2) Dos itens abaixo, quais NÃO são características de um algoritmo? (1 Ponto) 
A. Possui comandos ambíguos que permitem a dupla interpretação. 
B. Passos finitos. 
C. Os passos obedecem a uma ordem específica. 
D. Não há garantia de repetibilidade na sua transcrição x execução. 
 
3) É impossível estudar compiladores sem estudar as linguagens de programação. Já 
o contrário é possível: podemos estudar linguagens sem conhecer nada sobre 
compiladores. De acordo com esta afirmação, descreva o que é um compilador. 
(1 Ponto) 
 
4) Defina a máquina de Turing e de um exemplo de sistema moderno que adote os 
conceitos definidos por Turing? (1 Ponto) 
 
5) Em LISP qual dos comando resulta na adição de dois elementos numéricos e a sua 
multiplicação? (1 Ponto) 
A. (+ 3 4) * 7 
B. (* (+ 3 4 7)) 
C. (* (+ 3 4) 7) 
D. (+ (3 4) *(7)) 
E. (+ 3 4 * 7) 
 
6) Defina Expressões Regulares e cite um exemplo de vocabulário (2 Pontos) 
 
7) O que é uma Autômato Finito e qual das opções abaixo pode ser considerado um 
exemplo: (1,5 pontos) 
 
A B C 
 
 
 
NOME: __________________________________________________________________________ 
 
RA: ____________________________ CURSO: Engenharia de Computação 
 
DISCIPLINA: Teoria da Computação e Compiladores DATA: 16/10/2017 
 
PROFESSOR: Ms. Paulo C. Barreto da Silva SÉRIE: 10º Semestre SALA: NE 19 
 
ASSINATURA: _______________________ ATIVIDADES: ______ PROVA: ______ MÉDIA: _______ 
 
 
 
Para preenchimento do professor 
Favor preencher todos os dados corretamente 
8) Em uma Linguagem quando dois conjuntos são aglutinados definimos como sendo 
uma concatenação de linguagens. Adotado a técnica de concatenação que vimos 
em aula, fala a concatenação dos conjuntos X e Y: X = {a,b,c} Y = {abb,ba}. 
(1 Ponto) 
 
9) A Pesquisa Seqüencial ou Linear é definida como qual forma de pesquisa? Cite em 
que estrutura sua aplicabilidade se dá, por meio de um exemplo. (1 Ponto) 
 
 
 
 RESPOSTAS
 
 
 
1) São sequência de passos que obedecem uma ordem específica de conjunto de números e passos finitos,
onde não possui comandos ambíguos, não resultando duplo sentido na interpretação.
 
2) A e D
 
3) Linguagem é a notação para a escrita do algoritmo. Nela usamos os comandos printf, scanf, etc. O compilador
é responsável por transformar o bloco semântico compreensível à maquina.
 
4) Forma conceitual de se colocar um racicionio em uma sequência q pode ser repetida, atraves da soma e sub é
possível representar qualquer algoritmo. É uma máquina teórica. Exemplo: calculadora (von neumann).
 
5) C
 
6) Expressões regulares são um formalismo usado para definir o formato correto de uma cadeia de caracteres.
Ex.: a+ b c* (Define que as cadeias válidas são aquelas que iniciam com uma sequência não vazia de simbolos
'a', seguidos de exatamente um simbolo 'b', seguido de uma sequencia possivelmente vazia de simbolos 'c').
 
7) C
 
8) XY = {aabb,aba,babb,bba,cabb,cba}
 
9) Forma de pesquisa em vetores ou lista. Um exemplo de sua aplicidade é por meio de tabela, onde é facil
de implementar e suportado por todas as LP, mas uma desvantagem é que o desempenho para grandes massas
de dados é ruim.