UNIVERSIDADE FEDERAL RURAL DO SEMI-ÁRIDO … · Teoria da Computação -Aula 01 7. Terceira Unidade: Seminários Teoria da Computação -Aula 01 8 ... –ProfªDanielle. Teoria da

UNIVERSIDADE FEDERAL RURAL DO SEMI-ÁRIDO

CURSO: CIÊNCIA DA COMPUTAÇÃO

Prof.ª Danielle Casillo

� Nome: Teoria da Computação� Créditos: 4 – 60 horas� Período: 2010.2

Horário: segundas e quintas das 20:40 às � Horário: segundas e quintas das 20:40 às 22:20

� Professora: Danielle Simone S. Casillo� Página: www.ufersa.edu.br� Sigaa: www.sig.ufersa.edu.br� Contato: [email protected]

Teoria da Computação - Aula 01 2

� Os alunos serão preparados para o estudo eaprofundamento da semântica e lógica dacomputação do ponto de vista decomputabilidade; observando as linguagenscomputabilidade; observando as linguagenscomo modelos computacionais eexaminando a sua expressividade.


� Serão fornecidos os fundamentosmatemáticos de dois importantesparadigmas de programação: lógica efuncional.funcional.

� No aspecto prático, orientar-se-á aoestudante no tratamento de problemassimples e na implementação das soluçõescom técnicas lógicas e funcionais.


� Ensino:� Aulas teóricas, estudos individuais e em grupo,

resolução de exercícios.� Avaliação:

� Provas escritas;� Trabalhos realizados individualmente e/ou em grupo;� Trabalhos realizados individualmente e/ou em grupo;� Seminários.

� Data das avaliações:� 16/09/2010 - 1ª avaliação� 25/10/2010 - 2ª avaliação� 18 a 25/11/2010 - Seminários� 02/12/2010 – Reposição� 09/12/2010 - 4ª avaliação


� Primeira Unidade:� Introdução e Conceitos Básicos� Programas� Máquinas� Máquinas� Computações e Funções Computadas� Equivalência de Programas e Máquinas� Verificação da Equivalência Forte de

Programas


� Segunda Unidade:� Máquinas Universais

� Codificação de Conjuntos Estruturados� Máquina de Registradores NORMA� Máquina de Registradores NORMA� Máquina de Turing� Máquina de Post� Máquina com Pilhas� Autômatos com Duas Pilhas

� Funções Recursivas� Linguagem Lambda


� Terceira Unidade:� Seminários


� BÁSICA:� Notas de Aula – Profª Danielle.� Teoria da Computação – MáquinasUniversais e Computabilidade.Tiarajú Asmuz Diverio e Paulo BlauthTiarajú Asmuz Diverio e Paulo BlauthMenezes. 2ª Edição. Ed. Bookman.2008.

� COMPLEMENTAR:� Introdução à Teoria da Computação.

Michael Sipser. 2ª Edição. Ed.Thompson. 2007.


� A importância da Teoria para a Prática é imensa!� A teoria para esta ciência se faz necessário para

“iluminar o caminho” dos cientistas da computação“iluminar o caminho” dos cientistas da computação(práticos), dos engenheiros em computação, dosanalistas de sistemas, em fim de todos os profissionaisque usem a computação como objeto de estudo ou detrabalho. Mas antes de entender o que seria uma teoriapara a ciência da computação vamos entender o queseria Ciência da Computação.


� Computação: tudo o que um computador poderealizar.

� Mas o que é um computador?� Hardware e tecnologia.� Hardware e tecnologia.� Ex: calculadora, elevador, máquina de vender

refrigerante, CD player, impressora, ....

� A teoria nos fornece conceitos e princípios paranos ajudar entender a natureza geral daCiência do Computador.


� Definição: é o estudo dos algoritmos, suasaplicações e de sua implementação, naforma de software, bem como dasestruturas matemáticas indispensáveis àestruturas matemáticas indispensáveis àformulação precisa dos conceitosfundamentais da teoria dacomputabilidade e da computaçãoaplicada.


� Antes de 1920: computador era um termo associadoa pessoas que realizavam cálculos.

� Após 1920: a expressão máquina computacionalcomeçou a ser usada para referir-se a qualquermáquina que realize o trabalho de um profissionalcomputador.computador.

� O termo máquina computacional acabou perdendoespaço para o termo reduzido computador em 1940.Alan Turing, conhecido como pai da Ciência daComputação, inventou a Máquina de Turing, queposteriormente evoluiu para o computadormoderno.


“Ciência da computação tem tanto a vercom o computador como a Astronomia como telescópio, a Biologia com o microscópio,ou a Química com os tubos de ensaio. Aou a Química com os tubos de ensaio. ACiência não estuda ferramentas, mas o quefazemos e o que descobrimos com elas.”

Edsger Dijkstra


� O campo dessa disciplina inclui um vastoleque de tópicos especiais, desde projetosde máquinas até programação.

� Para estudar os princípios básicos dacomputação, construiremos modelosabstratos de computadores e computação,estes modelos contém as característicasimportantes que são comuns tanto aohardware quanto ao software.


�� ComputaçãoComputação pode ser definida como asolução de um problema ou, formalmente, ocálculo de uma função, através de umalgoritmo.algoritmo.


� A área de TC (Teoria daComputação) procurafornecer fundamentosmatemáticos rigorosospara as diversas áreas dapara as diversas áreas dacomputação.


• A TC introduz conceitos fundamentais que sãodesenvolvidos em outras áreas. A abordagem dereconhecimento de linguagens é a base de todo oestudo das Linguagens Formais, Semântica Formal,Compiladores, e todo o conjunto de disciplinas quetratam de Linguagens de programação.

� A teoriateoria dada computaçãocomputação, um subcampo daciência da computação e matemática, buscadeterminar quais problemas podem sercomputados em um dado modelo decomputados em um dado modelo decomputação.

� Existem 3 áreas centrais da Teoria daComputação:� Autômatos� Computabilidade� Complexidade


� Estas áreas são interligadas pela seguintequestão: Quais são as capacidades elimitações fundamentais doscomputadores?computadores?� Para cada uma das três áreas – autômatos,

computabilidade e complexidade – essaquestão é interpretada diferentemente.

� Iremos definir estas três áreas em ordemreversa porque começando do final vocêpode entender melhor a razão para o início.


� Teoria da Complexidade:� Os problemas computacionais vem em diferentes

variedades: alguns são fáceis e outros difíceis.� Ex: Problema da ordenação – Fácil

Criptografia – DifícilCriptografia – Difícil� O que faz alguns problemas computacionalmente

difíceis ou fáceis?� Entender qual o aspecto do problema é a raiz da

dificuldade;� Encontrar soluções que se aproximam da solução

perfeita;� Alguns problemas são difíceis somente na situação do

pior caso.Teoria da Computação - Aula 01 20

� Teoria da Computabilidade:� Classifica os problemas por meio da separação entre

os que são solúveis e os que não o são.� Ex: determinar se um enunciado matemático é

verdadeiro ou falso.verdadeiro ou falso.

� As teorias da computabilidade e complexidadeestão intimamente relacionadas.� Na teoria da complexidade, o objetivo é classificar os

problemas como fáceis ou difíceis;� Na teoria da computabilidade a classificação é feita

por meio da classificação dos que são solúveis ounão.


� Teoria dos Autômatos:� Lida com as definições e propriedades de modelos

matemáticos de computação.� Autômatos finitos: usados em processamento de� Autômatos finitos: usados em processamento de

textos, compiladores e projeto de hardware.� Gramática livre-do-contexto: usado em linguagem de

programação, inteligência artificial.


� A TTeoriaeoria dada ComputaçãoComputação teve início nosprimeiros anos do século XX, antes da invençãodos modernos computadores eletrônicos.

� Naquela época, os matemáticos estavamtentando descobrir quais problemastentando descobrir quais problemasmatemáticos poderiam ser resolvidos por ummétodo simples, e quais não poderiam. Oprimeiro passo estava em definir o significadode um "método simples" para resolver oproblema. Em outras palavras, eles precisavamde um modelo formal da computação.


� Na década de 1920, computador era associadoa pessoas que realizavam cálculos;

� O termo máquina computacional referia-se aqualquer máquina que realize cálculos;qualquer máquina que realize cálculos;

� Os fundamentos matemáticos da ciência dacomputação moderna começaram a serdefinidos por Gödel com seu Teorema daIncompletude, que mostra que existem limitesno que pode ser provado ou desaprovado emum sistema formal.


� Diversos modelos diferentes da computaçãoforam propostos pelos primeirospesquisadores.� Máquina de Turing: propunha a construção� Máquina de Turing: propunha a construção

de uma máquina universal, executando aprogramação que lhe for passada;

� Funções Recursivas: compostas para operardiretamente sobre os números;

� Cálculo-Lambda: similar às FunçõesRecursivas.


� Todos estes formalismos são equivalentes emtermos de poder computacional, ou seja,qualquer computação que possa ser realizadacom um modelo pode ser realizada comcom um modelo pode ser realizada comqualquer um dos outros modelos.

� As questões relativas à possibilidade derealizar certos tipos de computação emdeterminados tipos de máquinas são estudadaspela Teoria da Computabilidade.


� Alan Turing propôs, em 1936 um formalismopara representação de procedimentos efetivos.A intenção do modelo de Turing, denominado“Máquina de Turing”, foi simular, tantoquanto possível, as atitudes humanasquanto possível, as atitudes humanasrelacionadas à computação.

� Foi o primeiro trabalho a identificar programasescritos para uma “máquina computável”.


� Assim, define-se programa como sendo umprocedimento efetivo, que permitedescrever todos os procedimentos possíveisque podem ser executados em umque podem ser executados em umcomputador.


� Linguagem: é uma forma precisa de expressarproblemas, permitindo um desenvolvimentoformal adequado ao estudo dacomputabilidade.As definições que seguem são construídas� As definições que seguem são construídasusando como base a noção de símbolo oucaractere, que é uma entidade abstrata básica,não sendo definida formalmente. Letras edígitos são exemplos de símbolosfrequentemente usados.


� Definição: Alfabeto� É um conjunto finito de símbolos ou caracteres.

� Um conjunto infinito não é um alfabeto.� O conjunto vazio é um alfabeto.

� Exemplo de alfabetos:� {a, b, c};� conjunto vazio.

� Exemplo de conjuntos que não são alfabetos:� Conjunto dos números naturais;� {a, b, aa, ab, ba, bb, aaa, ...}.


� Cadeia de Símbolos, Palavra.� É uma sequência de zero ou mais símbolos

(do conjunto) justapostos.� Uma Palavra é uma Cadeia de Símbolos� Uma Palavra é uma Cadeia de SímbolosFinita.

� Exemplo:� abcb é uma palavra sobre o alfabeto {a, b, c};


� Uma cadeia sem símbolos é uma palavraválida.� εεεε denota a cadeia vazia ou palavra vazia.� O símbolo ∑ representa um alfabeto, então:

� ∑* denota o conjunto de todas as palavras possíveis� ∑* denota o conjunto de todas as palavras possíveissobre ∑;

� ∑+ denota ∑* - {εεεε}

� Exemplo:� Se ∑∑∑∑ = {a, b}, então:

� ∑∑∑∑+ = {a, b, aa, ab, ba, bb, aaa,...}� ∑∑∑∑* = {εεεε , a, b, aa, ab, ba, bb, aaa,...}


� Comprimento ou tamanho de uma palavraw, representado por w, é o número desímbolos que compõem a palavra.

� Exemplo:� Exemplo:� abcb = 4� εεεε = 0;


� Prefixo e Sufixo� Um Prefixo (respectivamente, Sufixo) de uma

palavra é qualquer sequência inicial(respectivamente, final) de símbolos da palavra.Uma Subpalavra de uma palavra é qualquerUma Subpalavra de uma palavra é qualquersequência de símbolos contígua da palavra.

� Exemplo:� Relativamente à palavra abcb, tem-se que:

� εεεε, a, ab, abc, abcb são os prefixos;� εεεε, b, cb, bcb, abcb são os respectivos sufixos.

� Qualquer prefixo ou sufixo de uma palavra é uma subpalavra.


� Linguagem formal é um conjunto de palavrassobre um alfabeto.

� Exemplo: Suponha o alfabeto ∑ = {a, b}. Então:� O conjunto vazio e o conjunto formado pela� O conjunto vazio e o conjunto formado pela

palavra vazia são linguagens sobre ∑∑∑∑. Obviamente,Ø ≠≠≠≠ { εεεε }.

� O conjunto de palíndromos (palavras que tem amesma leitura da esquerda para a direita e vice-versa) sobre ∑∑∑∑ é um exemplo de linguageminfinita.� ε, a, b, aa, bb, aaa, aba, bab, bbb, aaaa,...


� Concatenação de palavras associa a cada parde palavras uma palavra formada pelajustaposição da primeira com a segunda.� A operação de concatenação satisfaz às seguintes

propriedades (suponha v, w, t palavras):propriedades (suponha v, w, t palavras):� Associatividade: v(wt) = (vw)t� Elemento neutro à esquerda e à direita: εw = w = wε


� Exemplo de concatenação de palavras:� Suponha o alfabeto ∑∑∑∑ = {a, b}.� Então, para as palavras v = baaaa e w = bb,

tem-se que:tem-se que:� vw = baaaabb

� vεεεε = v = baaaa


� A concatenação sucessiva de uma palavra érepresentada na forma de um expoente.

wn em que n é o número de concatenaçõessucessivas

Exemplo:� Exemplo:� Sejam w uma palavra e a um símbolo, então:

� w3 = www� w1 = w� a5 = aaaaa� an = aaa...a (o símbolo a repetido n vezes)


� Sequências e uplas� Uma sequência de objetos é uma lista desses

objetos na mesma ordem.� Ex: (7, 21, 57)

� Em um conjunto a ordem não importa, mas em� Em um conjunto a ordem não importa, mas emuma sequência sim.� Portanto, (7, 21, 57) não é o mesmo que (57, 7, 21).

� Como os conjuntos, sequências podem ser finitasou infinitas. As sequências finitas são chamadas deuplas.� Ex: (7, 21, 57) é uma 3-upla (tripla).� Uma 2-upla (dupla) é também chamada de par.


� Conjuntos:� Se A e B são dois conjuntos, o produto cartesiano

ou produto cruzado de A e B, descrito como A x B,é o conjunto de todos os pares nos quais oprimeiro elemento é um membro de A e oprimeiro elemento é um membro de A e osegundo é um membro de B.� Ex: Se A = {1, 2} e B = {x, y, z}

A x B = {(1, x), (1, y), (1, z), (2, x), (2, y), (2, z)}

� Se temos o produto cartesiano de um conjuntocom si próprio, usamos a abreviação.� Ex:


� Funções e Relações� Função: é um objeto que estabelece um

relacionamento de entrada-saída.� Ex: f é uma função cujo valor de saída é bbaf =)(� Ex: f é uma função cujo valor de saída é b

quando o valor de entrada é a.

� O conjunto de entradas possíveis para umafunção é chamado seu domínio e as saídascontradomínio.� Ex:


CDf →:

baf =)(

1. Marque os conjuntos que são alfabetos:a) Conjunto dos números naturais [ ]b) Conjuntos dos números primos [ ]c) Conjunto das letras do alfabeto brasileiro [ ]c) Conjunto das letras do alfabeto brasileiro [ ]d) Conjunto dos algarismos romanos [ ]e) Conjunto {a, b, c, d} [ ]f) Conjunto das partes de {a, b, c} [ ]g) Conjunto das vogais [ ]h) Conjunto das letras gregas [ ]


2. Dê os possíveis prefixos e sufixos de cadauma das seguintes palavras:

a) teoriaa) teoriab) aaac) AbccBad) UFERSAe) abcabc


Documents

UNIVERSIDADE FEDERAL RURAL DO SEMI-ÁRIDO … · Teoria da Computação -Aula 01 7. Terceira Unidade: Seminários Teoria da Computação -Aula 01 8 ... –ProfªDanielle. Teoria da