Ciencia da Computacao Processamento de ffucoes, Reconhecimento de Linguagens e Solucionabilidade de problemas, Organizacao e Busca da informacao, Compreensao das Imagens, Raciocionio e Robotica
1. Problema
2. Conjunto ɉ uma estrutura que agrupa objetos e constitui uma base para construir estruturas mais complexas. ɉ uma coleção, sem repetição e sem qualquer ordenação, de objetos denominados elementos. Elemento pode ser um objeto concreto ou abstrato.

As relalações entre elementos e conjuntos são: persistencia, sub conjuntos, igualdade de conjuntos.

As operações de conjuntos são: união (+), interseção (*), complemento (não), diferença (-) (derivada da da composição complemento e interseção), conjunto de partes e produto cartesiano.

União


Interseção



A relação sobre dois conjuntos A e B é definida como um subconjunto de A x B.

Uma função é um mapeamento que associa elementos de um conjunto denominado dominio e elementos de outro conjunto chamado de contradominio.
3. Algoritmo ɉ uma lista finita de instruções que tem por objetivo resolver um problema.

Caracteristicas:
1.    Solução de um problema
2.    Tem descrição finita e não ambigua
3.    ɉ intuitivo
4.    Deve consistir de passos discretos, executáveis mecanicamente em um tempo finito.

Ex.: Problema:
       Mostar o fatorial de um número de 1 a 9
       
       Soluçãoo:
fatorial = 1;
Para numero = 1 até 9 com incremento de 1 for (i=1; i<10; i++ ){
fatorial = fatorial * numero;
mostrar número, "!=",fatorial, branco
4. Máquinas O objetivo de uma máquina é suprir todas as informações para que a computação de um programa possa ser descrita. Portanto cabe a máquina suprir o significado (dar semantica) aos identificadores das operações e testes.
Assim cada identificador de operação e teste interpretado pela máquina deve ser associado a uma transformação na estrutura de memória e a uma funçãoo verdade, respectivamente. Nore-se que:
  • nem todo o identificador de operaçãoo ou teste é definido em uma máquina
  • para cada identificador de operação ou teste definido em uma máquina, existe sómente uma função associada.
Adicionalmente, a máquina deve descrever o armazenamento ou recuperaaçãoo de informaações na estrutura de memória.

Os computadores atuais, seguem a máquina de Turing (1950) . Usam linguagem recursivamente enumeravel e sensivel ao contexto.
O ponto de partida de Turing foi analisar a situaação na qual uma pessoa, equipada com um instrumento de escrita e um apagador , realiza cálculos em uma folha de papel , organizada em quadrados.O trabalho da pessoa é :
  • ler um simbolo de um quadrado;
  • alterar um simbolo em um quadrado;
  • mover os olhos para outro quadrado;
Quando é encontrada alguma representação que satisfaça para a resposta desejada, a pessoa termina os cálculos.

A maquina é constituida de 3 partes:
  • Fita. Usada como dispositivo de entrada, saida e memória de trabalho
  • Unidade de controle. Reflete o estado corrente da máquina (numero finito e predefinido de estados). Posui uma unidade de leitura e gravação (cabeça da fita), naqual acessa uma cálcula da fita de cada vez e semovimenta da esquerda para direita.
  • Programa, Função Programa ou Função de Transição. Função que define o estado da máquina e comanda as leituras dos simbolos, as gravações dos simbolos e o sentido de movimento da cabeça.
A fita é finita a esquerda e infinita a direita. cada calculo armazena um simbolo.
Os simbolos podem:
  • pertencer ao alfabeto de entrada;
  • pertencer ao alfabeto auxiliar;
  • ser branco; 
  • ser marcador de inicio de fita;

  Tem o seguinte desenho:

5. Referencia
  1. Diverio,Tiaraj Asmuz . Teoria da computação. Maquinas Universais e computabilidade. 2008,1ed,Bookman.
  2. Ramos, Marcus Vinicius Midena. Linguagens Formais. teoria, modelagem e implementação. 2009, Bookman.
  3. Gersting, Judith L. Fundamentos matemáticos para a Ciência da computação. 2003, 5a ed. , LTC.
  4. Brookshear, Clenn. Ciência da Computação Uma visão abrangente. 2003, 7a. ed. ,Bookman.
  5. Sebesta, Robert W. Conceitos de Linguagens de programaação. 2002, 5a. ed. , Bookman.
6. Maqinas Universais Máquinas Deterministicas ou não deterministicas sem pilha
Máquinas Universais - algoritimos que sempre param Máquinas Não Deterministicas com uma pilha A máquina pode tentar diversos caminhos alternativos para uma mesma situação

menor poder computacional  de Máquinas Não Deterministicas com uma pilha ---------------->   Máquinas Deterministicas ou não deterministicas sem pilha

O modelo mais utilizado como formalização de algoritimo é a máquina de Turing, proposta em 1936 (20 anos antes do primeiro computador digital). É um mecanismo simples em que uma pessoa realiza calculos, usando um instrumento de escrita e um apagador.
O modelo formal é baseado em uma fita (usada para entrada, saida e rascunho) uma unidade de controle e um programa.
Na verdade a maquina de Touring é um programa para a maquina Universal..
Os seguintes modelos são equivalentes a maquina de Turing:
  • Maquina Norma. Uma máquina registradora, sendo que o conjunto de registradores é infinito.
  • Máquina de Post. Baseada na estrutura de dados do tipo fila (o primeiro dado aramazenado é o primero a ser recuperado.
  • Máquinas de Pilhas. Baseado na estrutura de dados do tipo pilha (o ultimo dado armazenado éo primeiro a ser recuperado), onde são necessários pelo menos duas pilhas para simular o mesmo poder computacional de uma fita ou fila.
7. Linguagens Máquinas Deterministicas ou não deterministicas sem pilha
É um conjunto, finito ou infinito, de cadeias de comprimento finito, formadas pela concatenação de lementos de um alfabeto finito e não vazio.  Linguagens são automatos ou seja maquinas abstratas.
Os mecanismos de geração formal de linguagem comumente usados para descrever a léxica, sintaxe, semantica e bolocs de construsão chamados de gramatica.

8. Linguagens
  • Sintaxe e Semantica
    Sintaxe éa forma de suas expressões de suas instruções e de suas unidades de programa.

    Semantica é o significado destes três.


    Ex.: sintaxe do if       if (<expr>) <instrução> 
           semântica do if    se o valor da expressãofor verdadeiro, a instrução será selecionada

    Método mais comum para descrever a sintaxe: a gramatica livre de contexto (também conhecida como Forma de Backus-Naur  BNF).
    A gramática de atributos pode ser usada para descrever tanto a sintaxe como a semantica estatica das linguagens de programaação
    Métodos formais para descrever a semantica  - operacional, axiomática e denotacional.

  • Hierarquia de linguagens segundo ChomskyLinguagem enumeraveis recursivamente
    Correspondem a classe das maquinas universais. Portanto podem ser recnhecidas mecanicamente.
  • Linguagem enumeraveis recursivamente
  • São todas as linguagens que podem ser reconhecidas mecanicamente e para quais sempre existe um algoritimo de reconhecimento que sempre para qualquer entrada. Inclui a grande maioria das linguagens aplicadas. Podem ser tanto ineficientes tanto em termos de processamento como recursos de memória 
  • Linguagens livres de contexto 
    Incluem linguagens de programação como Algol e Pascal. Os melhoores algoritimos de reconhecimento reconhecidos possuem tempo de processamento proporcional ao tamnhao da entrada elevado ao cubo.
    O tempo de reconhecimento de uma palavra é diretamente proporcional ao dobro do comprimento da entrada
  •  Linguagens livres do contexto deterministico
    Editores de textos e protocolos de comunicação. O tempo de reconhecimento de uma palavra é diretamente proporcional ao comprimento da entrada. 
  • Linguagens livres de contexto
    Editores de textos e protocolos de comunicacãoo. O tempo de reconhecimento de uma palavra é diretamente proporcional ao comprimento da entrada. Incluem linguagens de programação como Algol e Pascal. Os melhoores algoritimos de reconhecimento reconhecidos possuem tempo de processamento proporcional ao tamnhao da entrada elevado ao cubo.  
  • Linguagens Recursivas
    mais restritas de Linguagem enumeraveis recursivamente para Linguagens regulares
9. Automatoas finitos
É uma máquina que possue um número finito  de estados. Tem a capacidade de resolver um problema por ele mesmo.
10. Otimização Maquina com menor número de estado que desempenha amesma função (algoritimo coloring)

Ferramentas para otimização podem ser: Tabela de decisões, máquinas de estado e grafos e Diagramas de Karnugh
http://pt.wikipedia.org/wiki/Mapa_de_Karnaugh
http://www-ihs.theoinf.tu-ilmenau.de/~sane/projekte/karnaugh/embed_karnaugh.html

  • Tabela de decisões
    São automatas constituidos de 2 partes:
    logica combinacional  ==>  estados de transição
    Lógica é o estudo dos principios e métodos usados para destinguir sentençasverdadeiras e sentenças falsas.

    Proposiçãouma construção (sentença, frase, pensamento) a que se pode atribuir juizo. O tipo de juizo é verdadeiro ou falso.

  • Maquina de estado
    São sistemas alggebricos que modelam um comportamento de aplicativos, projeto de hardware de sistemas digitais, engenharia de software, no estudo da computação e das linguagens.
    Finalidade:
       tradutores ou atomatoas finitos com saida
       reconhecedores de linguagem
    Elementos:
       automata finito - saida limitada a ligica binária (aceita / rejeita). gera uma palavra de saida.
       saidas - (de transisãoo - maquina de mealy) (de estado - maquina de Moore) - não pode ser lida ou seja não pode ser usada                      como memoria auxiliar.
       estado - armazena informações sobre o passado. Armazena as mudanças desde a entrada num estado atéo presente momento.                 representado por um numero circulado.
       transições - indica uma mudança de estado. Á‰ descrita por uma condição
       ações - éa descrição de uma atividade que deve ser realizada em determinado momento. Ações de entrada (no estado) executa                 a ação quando entra no estado. A ação de saida : executa quando sai do estado.. A ação de transição: executa quando                       ocorre uma determinda transição
       diagrama de estado - representa uma máquina de estado finita.
    Processo:
      determinação do grafico de estado
       tabela de estado
       eliminação de estados equivalentes
       designação de estados auxiliares
       mapas de transição (tabelas de estado e de estados auxiliares)
       mapas de entrada (mapas de transição e das tabelas de entrada)
       mapa de saida (estados auxiliares e tabela de estado)

  • Grafos
    É um conjunto não vazio de n's (vertices) e um conjunto de arcos (arestas) tais que cada arco conecta dois  sistemas algébricos
link Arquivo origem: WCienciaComputacao.xml. referencia